C’est la rentrée ! Exposé mensuel GUTenberg : algorithme de Knuth-Plass par Didier Verna

Bonjour à 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 » :

  ┌────
  │ https://www.juanasensio.com/archive/2023/06/13/aneantir-michel-houellebecq-pour-en-finir-livres-moches-par-thomas-savary.html
  └────

En espérant vous y voir nombreux,
--
Pour l'association GUTenberg, Denis Bitouzé