Bonjour à toutes et tous,
Quoi de mieux, en ce début d’année, qu’un exposé sur l’algorithme de
Knuth-Plass ?
Eh bien l’association GUTenberg a déjà tout prévu, et vous pourrez « venir
» écouter Didier Verna nous parler de standard de la composition
informatique jeudi 11 janvier à 20h en visio-conférence à l’adresse
suivante :
https://greenlight.virtualdata.cloud.math.cnrs.fr/b/max-9v4-9wc
Voici, s’il fallait vous convaincre, un petit résumé de Didier Verna :
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çons 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 (
https://www.youtube.com/watch?v=lI3V0YrlUSM), ou bien d’avoir lu ses
articles de blog intitulés « Anéantir Michel » (
Anéantir Michel, ou Pour en finir avec les livres moches : introduction, par Thomas Savary : STALKER - Dissection du cadavre de la littérature
).
En espérant vous y voir nombreux et nombreuse,
Maxime pour l’association GUTenberg
–
Maxime Chupin
Site personnel : Parabolicae | Accueil
Site professionnel : Maxime Chupin | Accueil
http://www.ceremade.dauphine.fr/~chupin/
adresse libre : xyz@xyz.tld