Cher lecteur,
À l’occasion de ce 10 janvier marquant l'anniversaire de Donald Knuth, cet article dresse le portrait de cet acteur incontournable du monde de l’informatique. Bien que son nom soit peu connu du grand public, ses contributions – algorithmes, théorèmes, logiciels et ouvrages – forment une œuvre impressionnante qui explore en profondeur l'Art de programmer.
Un étudiant brillant
Donald Ervin Knuth est né le 10 janvier 1938 à Milwaukee (Wisconsin), dans une famille croyante de tradition luthérienne. Son père jouant de l'orgue lors des cérémonies religieuses, Donald apprit naturellement à jouer du piano puis de l'orgue dès son plus jeune âge.
Pipe organ music is... is one of the great pleasures of life.
Comme de nombreuses figures emblématiques de l'informatique, Knuth démontra très tôt un intérêt pour la logique mathématique. Pourtant, malgré ses excellents résultats scolaires, il doutait de ses capacités et se considérait comme un élève peu doué.
À son arrivée à l’université en 1956, il opta d’abord pour un cursus en sciences physiques, estimant ne pas être suffisamment bon en mathématiques. C’est durant cette période qu’il découvrit l’IBM 650, un ordinateur de la faculté. En étudiant sa documentation technique, il comprit rapidement qu’il pouvait améliorer le code source du compilateur. Cette prise de conscience marqua un tournant dans sa carrière : il abandonna la physique pour se consacrer aux mathématiques et obtint un master en 1960, un diplôme décerné exceptionnellement à la place du baccalauréat en reconnaissance de son travail exceptionnel.
Continuant sur sa lancée, Knuth obtient un doctorat en mathématique en 1963 au California Institute of Technology à Pasadena.
Quelques mois plus tard, on lui demanda d’écrire un livre relatif à l’écriture de compilateurs. Rapidement, Knuth réalisa qu’il n’arriverait pas à traiter ce sujet sans auparavant établir des bases solides notamment sur la programmation en elle-même...
Un chercheur prolifique
Donald Knuth est un mathématicien de formation et a apporté des contributions majeures à des domaines alliant mathématiques et informatique. Voici quelques-unes de ses œuvres les plus marquantes :
- En algorithmique,
- il créé l’algorithme de Knuth-Morris-Pratt (recherche de sous-chaîne de caractères)
- et l’algorithme X (recherche en profondeur de couverture optimale avec backtracking).
- En algèbre et calcul formel, la procédure de complétion de Knuth-Bendix relative à la réécriture de structures algébriques.
- En combinatoire algébrique la correspondance de Robinson-Schensted-Knuth
- En calculabilité, il propose la notation des puissances itérées de Knuth permettant d’écrire des nombres très très, très grands.
- En informatique, il théorise un nouveau paradigme de programmation (Programmation lettrée) dont le but est de privilégier l'expression de la logique humaine lors de la rédaction du programme et de laisser le compilateur assembler le tout ensuite (40 ans avant les assistants IA ;) ).
- Il mettra ensuite en pratique ce paradigme en créant le langage WEB.
Pour ces différentes contributions, Donald Knuth a reçu plus d'une centaine de prix et d'honneurs à travers le monde… mais ce n’est pas encore pour cela qu’il est célèbre dans le domaine de l’informatique.
Un écrivain patient
The best way to communicate from one human being to another is through story.
Dans les années 60, au début de la carrière de Donald Knuth, l’informatique était un domaine de recherche totalement nouveau et cette branche n’avait pas encore d’identité propre. À l’époque, les informaticiens théoriciens étaient des mathématiciens ou des physiciens tandis que les informaticiens praticiens étaient principalement des ingénieurs électriciens.
Selon Donald Knuth, une conséquence de cela était que le niveau des publications scientifiques dans ce domaine était assez bas avec beaucoup de publications scientifiques simplement erronées. Le manque de relecteurs scientifiques compétents entraînait la publication d’erreur parfois grossières.
Il déclarera plus tard qu’une des motivations intrinsèques à approfondir les bases de la programmation informatique dans son livre, dont le thème premier était les compilateurs, était de réarranger dans le bon ordre les éléments d’une histoire qui avait jusqu’à présent été très mal racontée.
En 1965, un an après la demande initiale par sa faculté d’un livre dédié aux compilateurs, Knuth termina le premier jet d’un ouvrage de 3 000 pages manuscrites relatif aux compilateurs et aux algorithmes et plus largement à la programmation informatique.
Le projet littéraire de sa vie : The Art Of Computer Programming était né.
Devant l’ensemble des thèmes abordés par Knuth, il sera décidé de publier les livres en 6 puis 7 volumes dont les trois premiers volumes seront publiés entre 1968 et 1973.
Un être motivé par l’élégance
Arrêtons nous un instant dans la présentation de cette carrière déjà féconde car nous risquerions de passer à côté de l'essentiel.
Ces livres, ces concepts, ces théorèmes sont bien le résultat de ses travaux. Mais ... est-ce cette liste de productions qui rend Donald Knuth si unique ? Afin de lui rendre honneur, il est nécessaire de vous présenter sa principale caracteristique intellectuelle qui le définira en tant que chercheur, le concept qui sera le fil rouge de toutes ses réalisations : l’élégance intellectuelle.
Tout d'abord, il est important de rappeler que Donald Knuth se définit comme un mathématicien. Comme beaucoup de ces derniers, les travaux de Knuth seront guidés par la recherche de ce qui est communément appelé la “beauté mathématique”.
En effet, comme pour la musique, certains mathématiciens estiment que les mathématiques sont un art créatif sujet à la notion d’élégance ou de beauté. À ce titre, ils ne cherchent pas à "résoudre des problèmes" avec "une solution qui marche" mais au contraire, à "comprendre une curiosité" avant de l'expliquer de la manière la plus précise et épurée possible.
L'ensemble des réalisations de Donald Knuth répondront à cette contrainte du plaisir esthétique. Chaque étape de son travail; l'obtention d'un résultat, sa rédaction ainsi que sa publication doit satisfaire un critère de beauté intellectuelle.
Plus profondément, Knuth appliquera également ce critère à ses activités de loisirs et ses choix de vie.
Ayant un intérêt particulier pour la musique et principalement l’orgue, il recherche dans sa pratique musicale les mêmes sentiments de beauté, de perfection et de sérénité.
Cet aspect fondamental de l’éthique de travail de Donald Knuth qu'est la "recherche du beau" aura deux conséquences majeures :
- Sur le fond, un texte, une publication, un algorithme, un livre ou un théorème de Knuth ne doit pas seulement être efficace, il doit aussi être esthétique. Cela a souvent eu pour conséquence de retarder certaines publications de Knuth qui aimait prendre son temps jusqu'à être pleinement satisfait de ses résultats.
- Sur la forme, il sera rapidement confronté à la mise en page assez grossière de ses publications ... et n'en sera pas satisfait.
Un typographe moderne
En 1976, Knuth était occupé sur la seconde édition du Volume 2 de The Art Of Computer Programming. Ce volume ayant été remanié, il devait, avant d’être imprimé, être composé à nouveau.
Hein ?
En imprimerie (à l'époque), la composition est la tâche relative à la combinaison des caractères afin d’en faire des lignes de texte ensuite combinées en pages pouvant être imprimées. À l'époque, la composition se faisait en agençant une série de plombs qui allait servir à l’impression mécanique.
Or, en 1976, la technique préférée par Knuth (composition chaude) … n’existait plus et les éditeurs préféraient la technique de la photocomposition où les caractères sont basés sur des photographies.
Knuth estimait que la nouvelle technique rendait des résultats "hideux" par rapport à l'ancienne technique utilisée pour la première version de son ouvrage.
Pour Donald, la beauté du fond devait s'accompagner d'une élégance de la forme. Il décida alors de mettre son projet d'écriture en pause pour se consacrer à la résolution de son problème typographique.
La solution ? Créer un système de composition typographique révolutionnaire grâce à l’informatique (sans passer par la reproduction photographique). Ce système serait capable de composer le résultat attendu pour ses livres et de restituer avec élégance la complexité des formules mathématiques.
Ne désirant y consacrer "pas trop de temps", Donald Knuth obtient un résultat qu’il estima satisfaisant au bout de 5 années.
Pour cela, il créa le langage et le logiciel Metafont servant à composer des polices vectorielles ainsi que langage et logiciel TeX utilisé pour la rédaction de documents.
Dans l'exemple ci-dessous, l'input est un texte augmenté de balises indiquant au programme ce qu'il doit ensuite retourner comme texte correctement mis en page.
En 1989, soit plus de 10 ans après sa création, le logiciel TeX entrait dans sa version définitive et cette version est toujours employée aujourd’hui par des scientifiques à travers le monde !
À présent satisfait de son système typographique, Donald Knuth put continuer la rédaction de The Art of Computer Programming en TeX jusqu'à nos jours (le volume 4B a été publié en 2022).
Aujourd'hui, TeX (avec ses extensions telles que LaTeX, LuaTex, ConTeXt) reste le système de rédaction le plus utilisé par les étudiants et chercheurs en science. TeX restant une promesse d'une qualité typographique exceptionnelle.
À titre personnel, l'ensemble de mes productions importantes ont été faite avec LaTeX (étendant TeX), ce qui explique pourquoi ce langage était présent dans mon "Qui-est-ce ?" dédié aux langages de programmation.
Un géant
S'il ressemble à un mélange de Yoda et de Gutenberg, c'est parce que Donald Knuth est véritablement un géant du monde de l'informatique théorique.
Scientifique accompli, être humain aux passions particulières (tel que la construction d'un orgue à son domicile ou l'analyse algorithmique des chansons), il est également connu de la communauté pour son humour typiquement "geek".
Beware of bugs in the above code; I have only proved it correct, not tried it.
Par exemple, chaque faute découverte dans ses livres (théorique ou typographique) offre à celui qui la remarque une prime de 2,56 dollars. Parce que « 256 cents font un dollar hexadécimal ».
De même, les numéros de version des logiciels TeX et Metafont convergent vers un nombre particulier. TeX converge vers pi avec sa liste des versions "3", "3,1", "3,14", .., dont la dernière est "3,141592653" tandis que Metafont converge vers le nombre e.
Ayant cessé d'utiliser l'email depuis 1990, Donald se consacre actuellement à la rédaction de la suite de The Art of Computer Programming.
Mathématicien, algorithmicien, développeur de TeX, auteur de The Art of Computer Programming, papy geek, Donald Knuth est une personnalité profonde avec tellement de facettes qu'il y a toujours au moins un aspect pour lequel on a à apprendre de Donald Knuth.
