Jeudi 11 janvier 2024, à 20h en visioconférence, nous avons eu le plaisir d’écouter Didier Verna nous parler de l’algorithme de Knuth-Plass.
Malgré son âge, TeX est aujourd’hui encore un standard de-facto en matière de mise en forme typographique. Une part non négligeable de son succès est due à l’algorithme de justification de paragraphe dont il est équipé, le fameux « Knuth-Plass », conçu et développé entre 1977 et 1982, et que Donald Knuth lui-même a décrit comme « probablement l’algorithme le plus intéressant de TeX ». Mais le Knuth-Plass est un artefact un peu impressionnant, que l’on préfère en général tenir à distance...
Du point de vue de l’utilisation, sa très grande flexibilité se paye par un paramétrage complexe : rien moins que dix « curseurs » numériques permettent de jouer sur la machinerie interne, influençant par la même occasion le comportement des neuf autres. Du point de vue de l’implémentation, la littérature qui le décrit mélange de façon inextricable les principes généraux et les détails d’implémentation, le tout dans un pseudo-langage algorithmique très impératif et avec des structures de données de très bas niveau ; somme toute, dans un formalisme qui date... de son époque.
Dans cet exposé, je me propose de montrer qu’il est possible de s’approcher du Knuth-Plass sans qu’il morde. Nous commencerons par retracer les grandes lignes de son fonctionnement global ainsi que de sa paramétrisation. Ensuite, nous décrirons son fonctionnement interne en des termes suffisamment généraux et compréhensibles par tous. Nous verrons en particulier comment l’algorithme de départ a été optimisé, dans un contexte où la puissance de calcul (à la fois spatiale et temporelle) de l’époque était limitée. Enfin, si le temps l’autorise, nous verrons qu’il existe encore de nombreuses façon d’améliorer le Knuth-Plass à peu de frais, ou en allant jusqu’à s’affranchir de ces fameuses optimisations que la puissance des ordinateurs d’aujourd’hui a rendues essentiellement obsolètes.
Note : en pré-requis à cet exposé, il est fortement conseillé d’avoir suivi celui de Thomas Savary sur le package Lua-Typo, ou bien d’avoir lu ses articles de blog intitulés « Anéantir Michel ».
Support de présentation
Vidéo
La vidéo est visible sur :
