Philosophie de l'ingénierie : Donald Knuth, la programmation est un art

L’essentiel à retenir

• La programmation est un art, pas seulement de l’ingénierie. Knuth a intitulé l’œuvre de sa vie The Art of Computer Programming à dessein, tenant le code à un standard de beauté qu’aucune suite de tests ne sait mesurer.
• Le code est une littérature écrite pour les humains. Le premier public est la prochaine personne qui lira le programme ; le compilateur n’arrive qu’en second. La lisibilité est une exigence d’ingénierie de premier ordre, pas une politesse.
• Réservez la rigueur là où elle compte ; réservez la retenue pour le reste. Prouvez les algorithmes, analysez leur coût avec exactitude, menez le métier jusqu’au dernier glyphe — et refusez de dépenser des efforts sur les 97 % de code qui n’ont pas d’importance.
• « Optimisation prématurée » veut dire : mesurez d’abord. La célèbre phrase est une discipline de mesure, pas une excuse pour du code lent : trouvez les quelques pour cent critiques par le profilage, attaquez-les eux seuls, et laissez le reste lisible.

Le principe

« Au lieu d’imaginer que notre tâche principale est d’indiquer à un ordinateur quoi faire, concentrons-nous plutôt sur l’explication, à des êtres humains, de ce que nous voulons qu’un ordinateur fasse. » — Donald Knuth¹

Une seule phrase contient toute la posture. Pour Knuth, un programme n’est pas d’abord un flux d’instructions destiné à une machine ; c’est un texte destiné à une personne — le prochain lecteur, qui est généralement vous, six mois plus tard, ayant tout oublié. Le compilateur est un public secondaire. Le premier public est humain, et le programme est une littérature pour ce public, sinon c’est un échec, quelle que soit la correction de son exécution.

C’est pour cela que Knuth a intitulé l’œuvre de sa vie The Art of Computer Programming et non The Science ni The Engineering de celle-ci. Il entend art au sens littéral : un métier poursuivi pour la qualité de la chose fabriquée, tenu à un standard de beauté qu’aucune suite de tests ne mesure. La discipline qui en découle est exigeante d’une manière très précise. Elle dit : faites le petit nombre de choses qui comptent vraiment, et faites-les exactement bien. Prouvez la justesse de vos algorithmes. Analysez leur coût avec précision plutôt que de le deviner. Composez la page pour qu’elle se lise sans accroc. Et — la partie que tout le monde cite et que presque tout le monde lit de travers — ne dépensez pas votre métier sur les 97 % du code qui n’ont pas d’importance, car un effort versé au mauvais endroit n’est pas du savoir-faire, c’est du gaspillage déguisé en application.

Le principe a donc deux visages qui semblent opposés et n’en font qu’un. De la rigueur partout où elle compte ; de la retenue partout où elle ne compte pas. Le talent consiste à savoir distinguer l’un de l’autre — et la réponse de Knuth à la question comment le sait-on est la même qui traverse toute cette série : on mesure. La célèbre formule sur l’optimisation prématurée n’est pas un permis d’écrire du code lent. C’est une exigence : trouver les quelques pour cent critiques par la preuve avant de toucher à quoi que ce soit, la même conviction selon laquelle la performance est une propriété que l’on construit et que l’on mesure, pas un examen que l’on ajoute à la fin.

Contexte

Donald Ervin Knuth est né le 10 janvier 1938 à Milwaukee, dans le Wisconsin.² Il obtient une licence et une maîtrise au Case Institute of Technology — Case fut assez impressionné pour lui décerner la maîtrise en même temps que la licence en 1960 — puis un doctorat de mathématiques à Caltech en 1963.² Il rejoint le corps enseignant de Stanford en 1969, devient Fletcher Jones Professor of Computer Science en 1977, et reçoit en 1990 un titre qu’il a pour ainsi dire inventé pour lui-même : Professor of The Art of Computer Programming.² Il est professeur émérite à Stanford depuis des années et travaille toujours, à la main et par courrier, sur le même projet qui l’occupe depuis plus de six décennies.

Ce projet a commencé par un accident d’envergure. En 1962, Addison-Wesley charge le jeune Knuth d’écrire un livre sur les compilateurs.³ Il se met à écrire et conclut qu’il ne peut pas honnêtement expliquer comment construire un compilateur sans d’abord poser la théorie fondamentale qui le sous-tend — le tri, la recherche, les structures de données, l’analyse du temps que prennent réellement les algorithmes. Le livre unique devint une série planifiée. Le premier volume, Fundamental Algorithms, paraît en 1968. Le plan a fini par s’étendre à sept volumes, et l’œuvre demeure inachevée aujourd’hui.³ American Scientist l’a plus tard rangé parmi la centaine de livres ayant façonné un siècle de science, et le New York Times l’a qualifié de « traité de référence de la profession ».³ C’est, selon un consensus raisonnable, ce qui se rapproche le plus d’une bible pour l’informatique.

En 1974, Knuth reçoit le prix Turing de l’ACM — la plus haute distinction de l’informatique — « pour un certain nombre de contributions majeures à l’analyse des algorithmes et à la conception des langages de programmation, et en particulier pour ses contributions les plus marquantes à “l’art de la programmation” à travers sa série de livres bien connus ».⁴ Sa conférence Turing s’intitulait, fidèle à lui-même, « Computer Programming as an Art ».⁴

L’œuvre

The Art of Computer Programming et l’analyse des algorithmes

On appelle Knuth le père de l’analyse des algorithmes, et le titre est mérité.² Avant TAOCP, les programmeurs raisonnaient pour l’essentiel sur les algorithmes de manière informelle — celui-ci semble plus rapide, celui-là paraît dispendieux. Le projet de Knuth fut de poser ce raisonnement sur un socle mathématique rigoureux : dériver, exactement, le nombre d’opérations qu’un algorithme effectue en fonction de son entrée, et le faire avec la précision qu’un mathématicien apporte à un théorème. Il a popularisé la notation asymptotique « grand O » que tout programmeur utilise désormais pour décrire l’évolution du coût.² L’enjeu n’a jamais été la notation ; c’était la conviction que le coût d’un programme est une quantité connaissable que l’on doit calculer, non une impression que l’on doit avoir.

Les volumes eux-mêmes sont célèbres pour une sorte de complétude obsessionnelle — chaque affirmation prouvée, chaque algorithme analysé, chaque cas limite traité — et pour les chèques de récompense que Knuth offre pour toute erreur trouvée. Le chèque est de 2,56 $, ce qu’il décrit comme « un dollar hexadécimal », parce que 256 cents font 100 en base seize.⁵ Le montant est une plaisanterie ; la discipline qui l’accompagne ne l’est pas. Knuth mise de l’argent sur le fait que son travail est correct, et invite le monde à le prendre en défaut. L’état soigné et toujours faisant autorité de TAOCP, des décennies plus tard, est en partie le produit de ce pari permanent.⁵ (Il a cessé d’envoyer de vrais chèques en 2008 après une fraude bancaire, et émet désormais des certificats tirés sur une « Bank of San Serriffe » imaginaire — la rigueur a survécu ; la trace papier a changé de support.)⁵

L’optimisation prématurée et les 3 % critiques

La phrase la plus citée du génie logiciel est de Knuth, et elle est presque toujours citée de travers — amputée de la proposition qui lui donne son sens. Voici le passage complet, tiré de son article de 1974 « Structured Programming with go to Statements », paru dans ACM Computing Surveys :

« Les programmeurs gaspillent d’énormes quantités de temps à réfléchir, ou à se soucier, de la vitesse de parties non critiques de leurs programmes, et ces tentatives d’efficacité ont en réalité un fort impact négatif quand on considère le débogage et la maintenance. Nous devrions oublier les petites optimisations, disons dans environ 97 % des cas : l’optimisation prématurée est la racine de tous les maux. Pourtant, nous ne devrions pas laisser passer nos occasions dans ces 3 % critiques. »⁶

Lu en entier, ce n’est pas un argument contre la performance. C’est un argument en faveur de la mesure. Le propos de Knuth est empirique : un programme passe presque tout son temps dans une infime fraction de son code, et optimiser les 97 % restants — les parties qui s’exécutent à peine — coûte un effort réel, n’apporte presque rien, et rend le code plus difficile à lire et moins digne de confiance. Le « mal », ce n’est pas l’optimisation. Le mal, c’est d’optimiser avant de savoir où passe le temps — dépenser du métier sur une croyance plutôt que sur des preuves. La discipline qu’il prescrit est l’opposé de la paresse : trouvez les 3 % critiques par le profilage, puis attaquez-les sans relâche.

Un mot sur l’attribution, parce qu’elle importe à quiconque cite la phrase honnêtement. La phrase apparaît dans l’article de Knuth de 1974, dans sa propre prose. Mais quinze ans plus tard, Knuth lui-même y faisait référence comme au « dicton de Hoare », l’attribuant à Tony Hoare — et lorsqu’on a interrogé Hoare directement, il l’a désavouée à son tour, suggérant qu’elle pourrait être de Dijkstra et qu’il valait mieux la traiter comme relevant de « la culture commune ou du folklore ».⁷ L’énoncé exact le plus net est donc celui-ci : la formulation que nous citons tous est de Knuth, publiée par lui en 1974 ; l’idée, il a généreusement refusé de la revendiquer comme entièrement sienne. Ce refus est lui-même conforme au personnage. L’homme qui vous paie pour trouver ses erreurs ne tient pas à s’attribuer un mérite dont il n’est pas certain qu’il lui revienne.

TeX, METAFONT et la typographie numérique comme métier

En 1976, Knuth reçoit les épreuves de la deuxième édition du volume 2 et il est consterné. La composition au plomb chaud qui avait rendu la première édition magnifique était remplacée par les débuts de la photocomposition, et le résultat était laid — les mathématiques en particulier avaient l’air fausses.³ Une autre personne l’aurait accepté comme le prix du progrès. Knuth, qui ne pouvait laisser ses propres livres être mal composés, décide en 1977 de consacrer un peu de temps à construire quelque chose de mieux. Le peu de temps devint presque une décennie. Le résultat fut TeX, le système de composition, et METAFONT, le système compagnon pour concevoir les polices elles-mêmes ; tous deux furent achevés et publiés sous forme de livres en 1986.³

Aucun détour de sa carrière n’en révèle davantage. Un mathématicien a interrompu son grand œuvre pendant huit ans pour résoudre, à partir des premiers principes, le problème de poser de beaux caractères sur une page — parce que l’apparence de la page n’était pas séparable, à ses yeux, de la qualité du travail. TeX reste la norme mondiale pour la composition des mathématiques, quarante ans plus tard. C’est l’affirmation la plus claire possible que, pour Knuth, l’artefact s’étend jusqu’au dernier pixel du dernier glyphe : le métier ne s’arrête pas au code. C’est la version de l’ingénieur du soin apporté à l’arrière de la clôture — la partie que le lecteur ne remarque jamais consciemment est celle qu’il a refusé de bâcler.

La programmation lettrée

Si un programme est censé être lu par des humains, alors la façon dont nous l’écrivons — dans l’ordre du compilateur, avec des commentaires plaqués après coup — est à l’envers. En 1984, dans un article de The Computer Journal, Knuth propose d’inverser cela. Il appela cette pratique programmation lettrée (literate programming), et construisit un système nommé WEB pour la mettre en œuvre.¹

En programmation lettrée, vous écrivez un document unique dans l’ordre de la pensée humaine — de la prose expliquant ce que vous comptez faire, avec des fragments de code tissés là où l’explication les appelle, dans la séquence qui se lit le mieux. Deux outils le traitent ensuite : tangle extrait le code dans l’ordre dont le compilateur a besoin, et weave produit la documentation mise en forme et composée que lit une personne.⁸ WEB combinait Pascal et TeX ; le CWEB ultérieur, avec Silvio Levy, faisait de même pour le C.⁸ La description qu’en donne Knuth lui-même est qu’« un programme se conçoit mieux comme une toile [web]… la tâche du programmeur est d’énoncer ces parties et ces relations, dans l’ordre le plus propice à la compréhension humaine ».⁸

La programmation lettrée n’est jamais devenue une pratique courante, et il faut être honnête là-dessus. Mais la conviction qui la sous-tend — que l’explication n’est pas une documentation du programme mais qu’elle est le programme, que la lisibilité est une exigence d’ingénierie de premier ordre et non une politesse — l’a discrètement emporté. C’est le même instinct qui nous fait valoriser le code qui s’explique de lui-même, et c’est la réponse la plus profonde que Knuth donne à la question de savoir à quoi sert la programmation.

La méthode

La méthode est constante sur soixante ans et quatre domaines — les algorithmes, la typographie, la conception de langages, et l’écriture elle-même.

Écrivez d’abord pour le lecteur humain. La machine est le second public. Un programme, comme une preuve ou un paragraphe, se juge à la capacité de la prochaine personne à le suivre. La programmation lettrée est cette conviction faite outil.¹⁸

Prouvez-le, puis testez-le. « Méfiez-vous des bugs dans le code ci-dessus ; je l’ai seulement prouvé correct, je ne l’ai pas essayé », écrivit Knuth dans une note de 1977 — une phrase drôle précisément parce qu’il est l’une des rares personnes à vraiment prouver son code.⁹ La plaisanterie contient la discipline : la justesse s’argumente, elle ne se présume pas, et une preuve est nécessaire sans pour autant être suffisante. Vous devez les deux.

Analysez le coût ; ne le devinez pas. Le temps d’exécution d’un algorithme est une quantité à dériver mathématiquement, non une intuition. C’est l’acte fondateur de l’analyse des algorithmes, et c’est pourquoi le « grand O » est dans la bouche de tout programmeur.²

Mesurez avant d’optimiser. L’optimisation prématurée est la racine de tous les maux parce qu’elle dépense du métier sur une croyance. Trouvez les 3 % critiques par la preuve ; n’optimisez que là ; laissez le reste lisible.⁶

Laissez le métier courir jusqu’au dernier glyphe. Arrêter l’œuvre de sa vie pendant huit ans pour construire TeX, c’est la méthode à l’état le plus pur : la qualité de l’artefact ne s’arrête pas là où s’arrête le code. Elle se termine au bord de la page.³

Protégez la concentration profonde. Knuth a renoncé à l’e-mail le 1er janvier 1990 — « je suis un homme heureux depuis », écrivit-il — au motif que l’e-mail est fait pour les gens dont le métier est d’être au sommet des choses, alors que son métier à lui est d’être au fond des choses, à étudier un sujet assez profondément pour bien l’expliquer.¹⁰ Le refus de l’interruption n’est pas une excentricité ; c’est la condition préalable du travail.

Chaîne d’influence

Qui l’a façonné

La tradition mathématique, en particulier la combinatoire et la théorie des nombres. Knuth est venu à la programmation en mathématicien, et il a apporté le standard non négociable du mathématicien — une affirmation n’est pas un savoir tant qu’elle n’est pas prouvée — dans un champ qui se débrouillait jusque-là à l’intuition. (Influence formatrice)

La commande d’Addison-Wesley en 1962. L’accident qui a fixé la trajectoire. Sollicité pour un livre sur les compilateurs, Knuth a suivi le problème jusqu’à ses fondations et n’en est jamais remonté ; l’analyse des algorithmes existe sous sa forme moderne parce qu’il a refusé d’écrire le livre facile qu’on lui demandait. (Influence directe)

La typographie au plomb chaud et le livre imprimé. Son standard de ce à quoi une page composée devait ressembler s’est formé au contact du savoir-faire d’une époque antérieure de l’imprimerie — ce qui explique précisément pourquoi les épreuves photocomposées de 1976 étaient intolérables et pourquoi TeX devint nécessaire. (Influence formatrice)

Qui il a façonné

Tout programmeur en exercice. L’analyse en grand O, l’étude rigoureuse des algorithmes, et TAOCP lui-même sont une culture de base. Une génération a appris ce que coûte un algorithme grâce à Knuth, qu’elle ait ouvert ses livres ou non.

L’édition mathématique et scientifique mondiale. TeX et LaTeX sont le substrat de pour ainsi dire chaque article de mathématiques, chaque prépublication de physique et chaque ouvrage technique composé depuis quarante ans. Le détour de huit ans de Knuth est devenu une infrastructure.

La culture de la justesse et de la lisibilité. La programmation lettrée, les chèques de récompense, le « prouvé correct, pas essayé » — tout cela a donné le ton. L’attente qu’un code sérieux soit à la fois démontrablement juste et agréable à lire est, en partie, l’héritage de Knuth.

Le fil conducteur

Knuth et Edsger Dijkstra sont les deux grands apôtres de la justesse dans cette série, et la tension féconde entre eux est ce qu’elle a de plus instructif. Tous deux écrivaient à la main, se méfiaient de la machine comme arbitre de la vérité, et insistaient pour qu’un programme se raisonne, et non se contente de s’exécuter. Mais là où Dijkstra soutenait que le test ne peut montrer que la présence de bugs et jamais leur absence — et penchait fortement vers la preuve comme seul terrain solide — le « je l’ai seulement prouvé correct, je ne l’ai pas essayé » de Knuth fait un clin d’œil à la limite de la preuve elle-même : il prouve et teste, et vous paie quand les deux échouent. Du pragmatisme au sein de la rigueur. John Carmack se tient sur le même axe par l’autre bout — profiler le point chaud, comprendre la machine jusqu’à ses fondations, attaquer la boucle critique — ce qui est exactement les « 3 % critiques » de Knuth visant le plafond du matériel au lieu de la preuve. Et l’Unix de Thompson et Ritchie, où le C fut conçu pour qu’un système d’exploitation puisse être lu et porté plutôt que soudé à la main à une seule machine, est la même conviction que Knuth a rendue explicite : les programmes sont écrits pour les humains. (Pont de série)

Ce que j’en retiens

La leçon que je garde, c’est que la phrase la plus citée de mon domaine est une discipline de mesure déguisée en aphorisme. « L’optimisation prématurée est la racine de tous les maux » sert à excuser du code lent et paresseux, ce qui est l’exact inverse de ce que Knuth voulait dire. Ce qu’il exige en réalité est plus difficile que d’optimiser tout ou de n’optimiser rien : profilez d’abord, localisez les 3 % critiques par la preuve, versez votre métier dans exactement cela, et laissez le reste lisible. C’est le même standard que la qualité comme seule variable — la question n’est jamais « est-ce assez rapide ? » ni « est-ce assez astucieux ? » mais « ai-je des preuves de l’endroit où se trouve réellement le coût ? ». C’est la barrière de la preuve appliquée à la performance : une intuition sur le point chaud n’est pas un savoir tant que vous ne l’avez pas mesurée.

Dans le monde où je construis aujourd’hui — agents, boucles d’outils, appels de modèles — les deux visages de Knuth sont l’un et l’autre porteurs. La retenue : n’optimisez pas un prompt ou un chemin de récupération que vous n’avez pas mesuré ; presque toute la latence vit dans quelques appels, et le reste est du bruit qu’il faut laisser lisible. La rigueur : là où ça compte, prouvez-le, testez-le, et misez quelque chose sur le fait que vous avez raison. Et la conviction de la programmation lettrée est celle que je trouve la plus pertinente à cinquante ans de distance — quand un système peut générer du code plus vite que quiconque ne peut le lire, écrire d’abord pour le lecteur humain cesse d’être une coquetterie et devient la seule chose qui garde le système inspectable. Cette conviction — que le goût est un système technique que l’on mesure et que l’on défend, et non un ressenti que l’on affirme — court tout droit d’une commande de livre en 1962 jusqu’à un cadre d’agent en 2026.

FAQ

Quelle est la philosophie d’ingénierie de Donald Knuth ?

Knuth considère la programmation comme un art dont le premier public est humain, non la machine : « expliquer à des êtres humains ce que nous voulons qu’un ordinateur fasse ».¹ La discipline qui en découle associe une rigueur exigeante à une retenue délibérée — prouver la justesse des algorithmes, analyser leur coût mathématiquement, et mener le métier jusqu’à la page composée, tout en refusant de dépenser des efforts à optimiser les parties d’un programme qui n’ont pas d’importance. Il tranche entre les deux par la mesure, ce qui est le véritable sens de sa phrase sur l’optimisation prématurée.⁶

Que voulait dire au juste « l’optimisation prématurée est la racine de tous les maux » ?

C’est une exigence de mesure, non un rejet de la performance. La citation complète de 1974 est : « Nous devrions oublier les petites optimisations, disons dans environ 97 % des cas : l’optimisation prématurée est la racine de tous les maux. Pourtant, nous ne devrions pas laisser passer nos occasions dans ces 3 % critiques. »⁶ Le propos de Knuth est qu’un programme passe presque tout son temps dans une petite fraction de son code ; optimiser les 97 % restants gaspille de l’effort et nuit à la lisibilité. La discipline consiste à profiler d’abord, à trouver les quelques pour cent critiques, et à n’optimiser que ceux-là. Utiliser la phrase pour excuser du code lent en inverse le sens.

Knuth a-t-il inventé la citation sur l’« optimisation prématurée », ou était-ce Hoare ?

La formulation que tout le monde cite est de Knuth, publiée dans son propre article de 1974 dans Computing Surveys, « Structured Programming with go to Statements ».⁶ Quinze ans plus tard, cependant, Knuth lui-même y a fait référence comme au « dicton de Hoare » et l’a attribuée à Tony Hoare ; lorsqu’on a interrogé Hoare directement, il en a désavoué la paternité à son tour, a suggéré qu’elle pourrait remonter à Dijkstra, et a dit qu’il valait mieux la traiter comme relevant de « la culture commune ou du folklore ».⁷ Le résumé honnête : la phrase telle que nous la citons est de Knuth, mais il a généreusement refusé de revendiquer l’idée comme entièrement sienne.

Qu’a créé Donald Knuth ?

Knuth a écrit The Art of Computer Programming (commencé en 1962, premier volume en 1968, toujours en cours — le traité de référence de l’informatique) et a fondé l’analyse moderne des algorithmes, popularisant la notation grand O.²³ Frustré par la mauvaise composition de ses propres livres, il a créé le système de composition TeX et le système de polices METAFONT, tous deux publiés en 1986 et toujours standard pour l’édition mathématique.³ Il est aussi à l’origine de la programmation lettrée et du système WEB, la pratique consistant à écrire des programmes pour qu’ils soient lus par des humains.¹⁸ Il a reçu le prix Turing de l’ACM en 1974.⁴

Sources