Histoire de TAoCP

Si vous faites partie de la génération de développeurs qui ont appris à programmer dans des livres, vous connaissez sûrement ces bouquins écrits pour surfer sur une mode, pour essayer de se faire un nom. Des livres impersonnels, avec de la forme mais pas de fond. PHP disparaît des radars et avec lui une charrette d’auteurs insipides.

A l’opposé de ces livres de circonstance je vous présente : « The Art of Computer Programming » (TAoCP) de Donald Knuth, Professeur à Standford. Un ouvrage rédigé par un seul auteur sur toute une vie, sur un seul sujet : l’Algorithmique. La conception de l’ouvrage n’a pas été linaire, loin de là, et comme tout projet il a subit d’énormes retards et changements de direction.

Notes : Vous connaissez l’histoire de Git ? Et bien c’est un peu la même chose qui s’est passé pendant la rédaction/édition de The Art of Computer Programming  (TAoCP). En 1973, à l’occasion de la seconde édition du volume 2,  Knuth était insatisfait des systèmes de composition de page de l’époque. Il décide de faire une pause (de 1974 à 1996 !) pour concevoir l’outil qui lui convient pour rédiger son ouvrage (Tout comme Linus Torval écrit Git pour gérer le code du kernel Linux). Le résultat est metafont et TeX qui sont toujours utilisés en 2025 au travers de LaTeX et TeX Live

Pour convaincre ceux qui hésiteraient à se lancer dans l’achat (et la lecture) de cette œuvre je ne ferais pas mieux que ce post "Dix bonnes raisons de lire ou relire The Art of Computer Programming".

Dans sa forme actuelle (déc 2024) TAoCP est constitué de 5 volumes + un fascicule :

Volume 1: Fundamental Algorithms (1968, 3éme Édition 1997)
Volume 2: Seminumerical Algorithms (1969, 3éme Édition 1997)
Volume 3: Sorting and Searching (1973, 2éme Édition 1998)
Volume 4A: Combinatorial Algorithms, Part 1 (2011)
Volume 4B: Combinatorial Algorithms, Part 2 (2023)
+
Fascicule 7, Constraint Satisfaction (2025)  pour un futur volume 4C ?...

Les Volume 4A et 4B ont d’abord été publié (dans le désordre) sous forme de fascicules:

• Fascicule 0, Introduction to Combinatorial Algorithms and Boolean Functions (2008)
  Fascicule 1, Bitwise Tricks & Techniques; Binary Decision Diagrams (2009)
  Fascicule 2, Generating All Tuples and Permutations (2005),
  Fascicule 3, Generating All Combinations and Partitions (2005)
  Fascicule 4, Generating All Trees; History of Combinatorial Generation (2006)
  Ces cinq premiers fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4A - Combinatorial Algorithms Part 1"en 2011

• Fascicule 5, Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links (2019)
  Fascicule 6, Satisfiability (2015)
  Ces deux fascicules ont ensuite été regroupés et publiés sous le nom "Volume 4B - Combinatorial Algorithms Part 2" en 2023.

En prévision :

Volume 5: Syntactic algorithm,
Volume 6: The Theory of context-free languages
Volume 7: Compiler techniques

Ce dernier volume sur les compilateurs est en fait la raison initiale de tout ce travail. En effet, en 1962 Knuth travaillait sur des compilateurs Algol et Fortran et avait entamé l’écriture d’un livre sur ce sujet, mais il avait jugé qu’il fallait d’abord introduire des concepts fondamentaux  … Introduction qui a donné les 5 volumes actuels !

Les exemples ne sont pas écrits en C, ni Pascal, ni C++, ni Java, ni Rust. Mais avec MIX pour les 3 premiers volumes puis avec MMIX. C'est le langage d’une machine virtuelle avec une architecture RISC (ben oui, en 1968 on savait déjà ce qu’était une VM)