Engineering-Philosophie: Donald Knuth, Programmieren ist eine Kunst

Wichtigste Erkenntnisse

• Programmieren ist eine Kunst, nicht bloß Ingenieurwesen. Knuth nannte sein Lebenswerk mit Absicht The Art of Computer Programming und hält Code an einen Maßstab der Schönheit, den keine Testsuite messen kann.
• Code ist Literatur, für Menschen geschrieben. Das erste Publikum ist die nächste Person, die das Programm liest; der Compiler ist erst das zweite. Lesbarkeit ist eine erstrangige Ingenieuranforderung, keine Höflichkeit.
• Verausgabe Strenge nur dort, wo es zählt; verausgabe Zurückhaltung für den Rest. Beweise die Algorithmen, analysiere ihre Kosten genau, vollende das Handwerk bis zum letzten Schriftzeichen — und weigere dich, Mühe in die 97 % des Codes zu gießen, die nicht ins Gewicht fallen.
• „Verfrühte Optimierung” bedeutet: zuerst messen. Der berühmte Satz ist eine Mess-Disziplin, keine Ausrede für langsamen Code: Finde die entscheidenden wenigen Prozent durch Profiling, greife nur diese an und lass den Rest lesbar.

Das Prinzip

„Statt uns vorzustellen, unsere Hauptaufgabe sei es, einem Computer Anweisungen zu geben, was er tun soll, lasst uns vielmehr darauf konzentrieren, menschlichen Wesen zu erklären, was wir von einem Computer getan haben wollen.” — Donald Knuth¹

Ein einziger Satz fasst die ganze Haltung. Für Knuth ist ein Programm nicht in erster Linie ein auf eine Maschine gerichteter Anweisungsstrom; es ist ein Stück Schreiben, gerichtet an eine Person — den nächsten Leser, und das bist meist du selbst, ein halbes Jahr später, nachdem du alles vergessen hast. Der Compiler ist ein sekundäres Publikum. Das erste Publikum ist menschlich, und das Programm ist Literatur für dieses Publikum, oder es ist ein Misserfolg, so korrekt es auch laufen mag.

Darum nannte Knuth sein Lebenswerk The Art of Computer Programming und nicht The Science oder The Engineering davon. Er meint art wörtlich: ein Handwerk, das um der Qualität des geschaffenen Dings willen verfolgt wird, gehalten an einen Maßstab der Schönheit, den keine Testsuite misst. Die Disziplin, die daraus folgt, ist auf ganz bestimmte Weise anspruchsvoll. Sie sagt: Tu die kleine Zahl der Dinge, die wirklich zählen, und tu sie genau richtig. Beweise, dass deine Algorithmen korrekt sind. Analysiere ihre Kosten präzise, statt zu raten. Setze die Seite so, dass sie reibungslos gelesen werden kann. Und — der Teil, den jeder zitiert und fast jeder falsch liest — verausgabe dein Handwerk nicht auf die 97 % des Codes, die nicht ins Gewicht fallen, denn Mühe, die an die falsche Stelle gegossen wird, ist keine Handwerkskunst, sondern als Sorgfalt verkleidete Verschwendung.

So hat das Prinzip zwei Gesichter, die entgegengesetzt aussehen und in Wahrheit eines sind. Strenge überall dort, wo es zählt; Zurückhaltung überall dort, wo es nicht zählt. Die Kunst besteht darin, zu wissen, was was ist — und Knuths Antwort darauf, woher du es weißt, ist dieselbe Antwort, die durch diese ganze Reihe läuft: Du misst. Der berühmte Satz über verfrühte Optimierung ist keine Lizenz, langsamen Code zu schreiben. Er ist die Forderung, dass du die entscheidenden wenigen Prozent durch Belege findest, bevor du irgendetwas anrührst — dieselbe Überzeugung, dass Leistung eine Eigenschaft ist, die man einbaut und misst, keine Prüfung, die man am Ende anhängt.

Kontext

Donald Ervin Knuth wurde am 10. Januar 1938 in Milwaukee, Wisconsin, geboren.² Er erwarb Bachelor- und Masterabschluss am Case Institute of Technology — Case war beeindruckt genug, ihm den Master 1960 gleichzeitig mit dem Bachelor zu verleihen — und 1963 einen Doktortitel in Mathematik am Caltech.² 1969 trat er der Fakultät in Stanford bei, wurde 1977 Fletcher Jones Professor of Computer Science und übernahm 1990 einen Titel, den er im Grunde für sich selbst erfand: Professor of The Art of Computer Programming.² Er ist seit Jahren emeritierter Professor in Stanford und arbeitet noch immer, von Hand und per Post, an demselben Projekt, das ihn seit mehr als sechs Jahrzehnten beschäftigt.

Jenes Projekt begann als ein Zufall des Umfangs. 1962 beauftragte Addison-Wesley den jungen Knuth, ein Buch über Compiler zu schreiben.³ Er begann zu schreiben und kam zu dem Schluss, dass er nicht ehrlich erklären könne, wie man einen Compiler baut, ohne zuvor die grundlegende Theorie darunter darzulegen — Sortieren, Suchen, Datenstrukturen, die Analyse, wie lange Algorithmen tatsächlich brauchen. Aus dem einen Buch wurde eine geplante Reihe. Der erste Band, Fundamental Algorithms, erschien 1968. Der Plan wuchs schließlich auf sieben Bände an, und das Werk ist bis heute unvollendet.³ American Scientist nannte es später eines der etwa hundert Bücher, die ein Jahrhundert der Wissenschaft geprägt haben, und die New York Times nannte es „die maßgebliche Abhandlung der Profession”.³ Es ist, nach vernünftigem Konsens, das Nächste, was die Informatik einer Bibel hat.

1974 erhielt Knuth den ACM A.M. Turing Award — die höchste Auszeichnung des Computerwesens — „für eine Reihe bedeutender Beiträge zur Analyse von Algorithmen und zum Entwurf von Programmiersprachen, und insbesondere für seine bedeutendsten Beiträge zur ‚art of computer programming’ durch seine Reihe wohlbekannter Bücher”.⁴ Seine Turing-Vorlesung trug bezeichnenderweise den Titel „Computer Programming as an Art”.⁴

Das Werk

The Art of Computer Programming und die Analyse von Algorithmen

Knuth wird der Vater der Analyse von Algorithmen genannt, und der Titel ist verdient.² Vor TAOCP argumentierten Programmierer über Algorithmen weitgehend informell — dieser fühlt sich schneller an, jener scheint verschwenderisch. Knuths Projekt bestand darin, diese Argumentation auf ein strenges mathematisches Fundament zu stellen: genau herzuleiten, wie viele Operationen ein Algorithmus als Funktion seiner Eingabe ausführt, und dies mit derselben Präzision zu tun, die ein Mathematiker einem Theorem entgegenbringt. Er popularisierte die asymptotische „Groß-O”-Notation, die heute jeder Programmierer verwendet, um zu beschreiben, wie Kosten skalieren.² Es ging nie um die Notation; es ging um die Überzeugung, dass die Kosten eines Programms eine erkennbare Größe sind, die man berechnen sollte, kein Gefühl, das man haben sollte.

Die Bände selbst sind berühmt für eine Art obsessiver Vollständigkeit — jede Behauptung bewiesen, jeder Algorithmus analysiert, jeder Randfall behandelt — und für die Belohnungsschecks, die Knuth für jeden gefundenen Fehler anbietet. Der Scheck lautet über 2,56 $, was er als „one hexadecimal dollar” bezeichnet, denn 256 Cent sind 100 zur Basis sechzehn.⁵ Der Betrag ist ein Scherz; die Disziplin dahinter nicht. Knuth setzt Geld darauf, dass seine Arbeit korrekt ist, und lädt die Welt ein, ihm das Gegenteil zu beweisen. Der polierte, noch immer maßgebliche Zustand von TAOCP nach Jahrzehnten ist zum Teil ein Erzeugnis dieser stehenden Wette.⁵ (Er hörte 2008 nach einem Bankbetrug auf, echte Schecks zu verschicken, und stellt nun Zertifikate auf eine erfundene „Bank of San Serriffe” aus — die Strenge überlebte; die Papierspur wechselte das Format.)⁵

Verfrühte Optimierung und die entscheidenden 3 %

Der meistzitierte Satz der Softwaretechnik stammt von Knuth, und er wird fast immer falsch zitiert — entkleidet jener Teilsatzes, der ihm Bedeutung gibt. Hier ist die vollständige Passage, aus seinem Aufsatz von 1974 „Structured Programming with go to Statements” in ACM Computing Surveys:

„Programmierer verschwenden enorme Mengen an Zeit damit, über die Geschwindigkeit unkritischer Teile ihrer Programme nachzudenken oder sich darum zu sorgen, und diese Versuche, effizient zu sein, haben tatsächlich eine starke negative Wirkung, wenn man Debugging und Wartung bedenkt. Wir sollten kleine Effizienzgewinne vergessen, sagen wir in etwa 97 % der Zeit: verfrühte Optimierung ist die Wurzel allen Übels. Doch wir sollten unsere Gelegenheiten in jenen entscheidenden 3 % nicht verstreichen lassen.”⁶

Im Ganzen gelesen, ist es kein Argument gegen Leistung. Es ist ein Argument für Messung. Knuths Punkt ist empirisch: Ein Programm verbringt fast seine gesamte Zeit in einem winzigen Bruchteil seines Codes, und die anderen 97 % zu optimieren — die Teile, die kaum laufen — kostet echte Mühe, bringt fast nichts und macht den Code schwerer lesbar und schwerer zu vertrauen. Das „Übel” ist nicht die Optimierung. Das Übel ist, zu optimieren, bevor du weißt, wohin die Zeit geht — Handwerk auf Glauben statt auf Belege zu verausgaben. Die Disziplin, die er vorschreibt, ist das Gegenteil von Faulheit: Finde die entscheidenden 3 % durch Profiling, dann greife sie hart an.

Ein Wort zur Zuschreibung, denn sie ist jedem wichtig, der den Satz ehrlich zitiert. Der Satz erscheint in Knuths Aufsatz von 1974, in seiner eigenen Prosa. Doch fünfzehn Jahre später bezeichnete Knuth selbst ihn als „Hoare’s dictum” und schrieb ihn Tony Hoare zu — und als Hoare direkt gefragt wurde, lehnte auch er ihn ab, vermutete, er stamme vielleicht von Dijkstra, und sagte, man behandle ihn am besten als „common culture or folklore”.⁷ Die sauberste zutreffende Aussage lautet also so: Der Wortlaut, den wir alle zitieren, ist Knuths, von Knuth 1974 veröffentlicht; den Gedanken weigerte er sich großzügig, allein für sich zu beanspruchen. Diese Weigerung ist selbst charakteristisch. Der Mann, der dich dafür bezahlt, seine Fehler zu finden, ist nicht daran interessiert, sich Verdienst anzueignen, von dem er nicht sicher ist, dass er ihm gebührt.

TeX, METAFONT und die digitale Typografie als Handwerk

1976 erhielt Knuth die Fahnenabzüge für die zweite Auflage von Band 2 und war entsetzt. Der Bleisatz, der die erste Auflage schön gemacht hatte, wurde durch frühen Fotosatz ersetzt, und das Ergebnis war hässlich — besonders die Mathematik sah falsch aus.³ Ein anderer hätte es als Preis des Fortschritts hingenommen. Knuth, der nicht zulassen konnte, dass seine eigenen Bücher schlecht gesetzt wurden, beschloss 1977, ein wenig Zeit darauf zu verwenden, etwas Besseres zu bauen. Aus dem bisschen Zeit wurde fast ein Jahrzehnt. Das Ergebnis war TeX, das Satzsystem, und METAFONT, das begleitende System zum Entwurf der Schriften selbst; beide wurden fertiggestellt und 1986 als Bücher veröffentlicht.³

Kein Abstecher seiner Laufbahn offenbart mehr. Ein Mathematiker unterbrach sein Hauptwerk für acht Jahre, um von Grund auf das Problem zu lösen, schöne Schriftzeichen auf eine Seite zu bringen — weil das Aussehen der Seite in seinem Denken nicht von der Qualität der Arbeit zu trennen war. TeX ist nach vierzig Jahren noch immer weltweit der Standard für den Satz von Mathematik. Es ist die denkbar klarste Aussage, dass für Knuth das Artefakt bis zum letzten Pixel des letzten Schriftzeichens reicht: Das Handwerk endet nicht beim Code. Es ist die Ingenieurfassung davon, die Rückseite des Zauns zu vollenden — der Teil, den der Leser nie bewusst bemerkt, ist der Teil, den er sich weigerte, schlecht zu machen.

Literarisches Programmieren

Wenn ein Programm dafür gedacht ist, von Menschen gelesen zu werden, dann ist die Art, wie wir es schreiben — in Compiler-Reihenfolge, mit nachträglich angeklebten Kommentaren — verkehrt herum. 1984 schlug Knuth in einem Aufsatz in The Computer Journal vor, es umzukehren. Er nannte die Praxis literate programming und baute ein System namens WEB, um sie umzusetzen.¹

Beim literate programming schreibt man ein einziges Dokument in der Reihenfolge des menschlichen Denkens — Prosa, die erklärt, was man beabsichtigt, mit Codefragmenten, die dort eingewoben werden, wo die Erklärung sie verlangt, in der Reihenfolge, die sich am besten liest. Zwei Werkzeuge verarbeiten es dann: tangle extrahiert den Code in der Reihenfolge, die der Compiler braucht, und weave erzeugt die formatierte, gesetzte Dokumentation, die ein Mensch liest.⁸ WEB kombinierte Pascal und TeX; das spätere CWEB, mit Silvio Levy, tat dasselbe für C.⁸ Knuths eigene Beschreibung lautet, dass „a program is best thought of as a web… the programmer’s task is to state those parts and those relationships, in whatever order is best for human comprehension”.⁸

Literate programming wurde nie zur gängigen Praxis, und das sollte man ehrlich aussprechen. Doch die Überzeugung darunter — dass die Erklärung nicht Dokumentation des Programms ist, sondern das Programm; dass Lesbarkeit eine erstrangige Ingenieuranforderung ist und keine Höflichkeit — hat sich still durchgesetzt. Es ist derselbe Instinkt, der uns Code schätzen lässt, der sich selbst erklärt, und es ist die tiefste Antwort, die Knuth auf die Frage gibt, wofür Programmieren da ist.

Die Methode

Die Methode ist über sechzig Jahre und vier Bereiche hinweg beständig — Algorithmen, Typografie, Sprachentwurf und das Schreiben selbst.

Schreibe zuerst für den menschlichen Leser. Die Maschine ist das zweite Publikum. Ein Programm wird, wie ein Beweis oder ein Absatz, danach beurteilt, ob die nächste Person ihm folgen kann. Literate programming ist diese Überzeugung, in ein Werkzeug gegossen.¹⁸

Beweise es, dann teste es. „Hüte dich vor Fehlern im obigen Code; ich habe ihn nur als korrekt bewiesen, nicht ausprobiert”, schrieb Knuth in einem Memo von 1977 — ein Satz, der gerade deshalb komisch ist, weil er der seltene Mensch ist, der seinen Code tatsächlich beweist.⁹ Der Scherz enthält die Disziplin: Korrektheit wird argumentiert, nicht angenommen, und ein Beweis ist notwendig, aber dennoch nicht hinreichend. Du schuldest beides.

Analysiere die Kosten; rate sie nicht. Die Laufzeit eines Algorithmus ist eine Größe, die mathematisch herzuleiten ist, keine Ahnung. Das ist der Gründungsakt der Analyse von Algorithmen, und darum liegt „Groß-O” in jedes Programmierers Mund.²

Miss, bevor du optimierst. Verfrühte Optimierung ist die Wurzel allen Übels, weil sie Handwerk auf Glauben verausgabt. Finde die entscheidenden 3 % durch Belege; optimiere nur dort; lass den Rest lesbar.⁶

Lass das Handwerk bis zum letzten Schriftzeichen laufen. Sein Lebenswerk acht Jahre lang anzuhalten, um TeX zu bauen, ist die Methode in ihrer reinsten Form: Die Qualität des Artefakts endet nicht dort, wo der Code endet. Sie endet am Rand der Seite.³

Schütze tiefe Konzentration. Knuth gab E-Mail am 1. Januar 1990 auf — „ich bin seither ein glücklicher Mann gewesen”, schrieb er — mit der Begründung, E-Mail sei für Menschen, deren Aufgabe es ist, über den Dingen zu stehen, während seine Aufgabe ist, am Grund der Dinge zu sein und einen Gegenstand tief genug zu studieren, um ihn gut erklären zu können.¹⁰ Die Weigerung gegenüber Unterbrechung ist keine Exzentrik; sie ist die Voraussetzung der Arbeit.

Einflusskette

Wer ihn prägte

Die mathematische Tradition, besonders Kombinatorik und Zahlentheorie. Knuth kam als Mathematiker zum Programmieren, und er brachte den nicht verhandelbaren Maßstab des Mathematikers — eine Behauptung ist kein Wissen, bevor sie bewiesen ist — in ein Feld, das sich bis dahin mit Intuition durchgeschlagen hatte. (Prägender Einfluss)

Addison-Wesleys Auftrag von 1962. Der Zufall, der die Bahn vorgab. Um ein Buch über Compiler gebeten, folgte Knuth dem Problem hinab bis zu seinen Grundlagen und kam nie wieder herauf; die Analyse von Algorithmen existiert in ihrer modernen Form, weil er sich weigerte, das einfache Buch zu schreiben, um das man ihn gebeten hatte. (Direkter Einfluss)

Bleisatz-Typografie und das gedruckte Buch. Sein Maßstab dafür, wie eine gesetzte Seite aussehen sollte, war von der Handwerkskunst einer früheren Druckära geformt — was genau der Grund ist, weshalb die fotogesetzten Fahnen von 1976 unerträglich waren und TeX notwendig wurde. (Prägender Einfluss)

Wen er prägte

Jeden arbeitenden Programmierer. Groß-O-Analyse, das strenge Studium von Algorithmen und TAOCP selbst sind Grundbildung. Eine Generation lernte von Knuth, was ein Algorithmus kostet, ob sie seine Bücher je aufschlug oder nicht.

Das mathematische und wissenschaftliche Verlagswesen der Welt. TeX und LaTeX sind das Substrat im Grunde jeder mathematischen Arbeit, jedes Physik-Preprints und jedes Fachbuchs, das in den letzten vierzig Jahren gesetzt wurde. Knuths achtjähriger Abstecher wurde zu Infrastruktur.

Die Kultur der Korrektheit und Lesbarkeit. Literate programming, die Belohnungsschecks, „proved it correct, not tried it” — diese setzten einen Ton. Die Erwartung, dass ernsthafter Code sowohl beweisbar richtig als auch angenehm zu lesen sein sollte, ist zum Teil Knuths Vermächtnis.

Der rote Faden

Knuth und Edsger Dijkstra sind die beiden großen Apostel der Korrektheit in dieser Reihe, und die fruchtbare Spannung zwischen ihnen ist das Lehrreichste daran. Beide schrieben von Hand, misstrauten der Maschine als Schiedsrichter der Wahrheit und bestanden darauf, dass ein Programm durchdacht und nicht bloß ausgeführt werden sollte. Doch wo Dijkstra meinte, Testen könne nur die Anwesenheit von Fehlern zeigen, nie ihre Abwesenheit — und sich stark zum Beweis als einzigem wirklichen Boden neigte — zwinkert Knuths „I have only proved it correct, not tried it” der Grenze des Beweises selbst zu: Er beweist und testet und zahlt dir, wenn beides daneben trifft. Pragmatismus innerhalb der Strenge. John Carmack sitzt auf derselben Achse vom anderen Ende — den Hotspot profilen, die Maschine bis auf ihr Fundament verstehen, die entscheidende Schleife angreifen — was genau Knuths „entscheidende 3 %” sind, nur auf die Hardware-Decke statt auf den Beweis gerichtet. Und Thompson und Ritchies Unix, in dem C so gebaut wurde, dass ein Betriebssystem gelesen und portiert statt von Hand an eine Maschine geschweißt werden konnte, ist derselbe Glaube, den Knuth explizit machte: Programme werden für Menschen geschrieben. (Reihen-Brücke)

Was ich daraus mitnehme

Die Lehre, die ich behalte, ist, dass der meistzitierte Satz meines Felds eine Mess-Disziplin im Kostüm eines Aphorismus ist. „Verfrühte Optimierung ist die Wurzel allen Übels” wird benutzt, um langsamen, faulen Code zu entschuldigen, was das genaue Gegenteil dessen ist, was Knuth meinte. Was er tatsächlich verlangt, ist schwerer als alles zu optimieren oder nichts: Profile zuerst, lokalisiere die entscheidenden 3 % durch Belege, gieße dein Handwerk in genau diese und lass den Rest lesbar. Das ist derselbe Maßstab wie Qualität als die einzige Variable — die Frage lautet nie „ist das schnell genug?” oder „ist das clever genug?”, sondern „habe ich Belege dafür, wo die Kosten tatsächlich liegen?” Es ist die Beweis-Schranke, angewandt auf Leistung: Eine Ahnung über den Hotspot ist kein Wissen, bevor du ihn gemessen hast.

In der Welt, in der ich jetzt baue — Agenten, Werkzeugschleifen, Modellaufrufe — sind Knuths beide Gesichter beide tragend. Die Zurückhaltung: Optimiere keinen Prompt und keinen Abrufpfad, den du nicht gemessen hast; fast die gesamte Latenz lebt in wenigen Aufrufen, und der Rest ist Rauschen, das du lesbar lassen solltest. Die Strenge: Wo es zählt, beweise es, teste es und setze etwas darauf, dass du recht hast. Und die literate-programming-Überzeugung ist die, die ich mit fünfzig Jahren am relevantesten finde — wenn ein System Code schneller erzeugen kann, als irgendjemand ihn lesen kann, hört zuerst für den menschlichen Leser zu schreiben auf, eine nette Geste zu sein, und wird zum Einzigen, das das System überprüfbar hält. Diese Überzeugung — dass Geschmack ein technisches System ist, das man misst und verteidigt, keine Stimmung, die man behauptet — läuft schnurstracks von einem Buchauftrag von 1962 zu einem Agenten-Gerüst von 2026.

FAQ

Was ist Donald Knuths Ingenieurphilosophie?

Knuth behandelt Programmieren als eine Kunst, deren erstes Publikum menschlich ist, nicht die Maschine: „menschlichen Wesen zu erklären, was wir von einem Computer getan haben wollen”.¹ Die Disziplin, die daraus folgt, paart anspruchsvolle Strenge mit bewusster Zurückhaltung — beweise Algorithmen als korrekt, analysiere ihre Kosten mathematisch und vollende das Handwerk bis hin zur gesetzten Seite, während du dich weigerst, Mühe darauf zu verausgaben, jene Teile eines Programms zu optimieren, die nicht ins Gewicht fallen. Welches was ist, klärt er durch Messung, was die wahre Bedeutung seines Satzes über verfrühte Optimierung ist.⁶

Was bedeutete „verfrühte Optimierung ist die Wurzel allen Übels” eigentlich?

Es ist eine Forderung nach Messung, keine Ablehnung von Leistung. Das vollständige Zitat von 1974 lautet: „Wir sollten kleine Effizienzgewinne vergessen, sagen wir in etwa 97 % der Zeit: verfrühte Optimierung ist die Wurzel allen Übels. Doch wir sollten unsere Gelegenheiten in jenen entscheidenden 3 % nicht verstreichen lassen.”⁶ Knuths Punkt ist, dass ein Programm fast seine gesamte Zeit in einem kleinen Bruchteil seines Codes verbringt; die anderen 97 % zu optimieren verschwendet Mühe und schadet der Lesbarkeit. Die Disziplin besteht darin, zuerst zu profilen, die entscheidenden wenigen Prozent zu finden und nur diese zu optimieren. Den Satz zu benutzen, um langsamen Code zu entschuldigen, kehrt seine Bedeutung um.

Hat Knuth das „verfrühte Optimierung”-Zitat erfunden, oder war es Hoare?

Der Wortlaut, den jeder zitiert, ist Knuths, veröffentlicht in seinem eigenen Computing Surveys-Aufsatz von 1974 „Structured Programming with go to Statements”.⁶ Fünfzehn Jahre später jedoch bezeichnete Knuth selbst ihn als „Hoare’s dictum” und schrieb ihn Tony Hoare zu; als Hoare direkt gefragt wurde, lehnte auch er die Urheberschaft ab, vermutete, er könne auf Dijkstra zurückgehen, und sagte, man behandle ihn am besten als „common culture or folklore”.⁷ Die ehrliche Zusammenfassung: Der Satz, wie wir ihn zitieren, ist Knuths, doch er lehnte großzügig ab, den Gedanken allein für sich zu beanspruchen.

Was hat Donald Knuth geschaffen?

Knuth schrieb The Art of Computer Programming (begonnen 1962, erster Band 1968, fortlaufend — die maßgebliche Abhandlung der Informatik) und begründete die moderne Analyse von Algorithmen, indem er die Groß-O-Notation popularisierte.²³ Frustriert über den schlechten Satz seiner eigenen Bücher, schuf er das TeX-Satzsystem und das METAFONT-Schriftsystem, beide 1986 veröffentlicht und noch immer Standard für mathematisches Verlagswesen.³ Er begründete außerdem literate programming und das WEB-System, die Praxis, Programme so zu schreiben, dass Menschen sie lesen.¹⁸ Er erhielt 1974 den ACM Turing Award.⁴

Quellen