Happy Birthday Prof. Knuth

Published on January 10, 2015.

by Hubert Behaghel

Donald Ervin Knuth is turning 77 today. He is by far the most fascinating person in the CS world to me. I am going to treat myself and play the total fanboy that I am by telling you my favourite facts about him.

Fact #1: One Book, One Life

Don Knuth, when 24, agrees to write a book about compilers. You know, something straightforward, à la “Compilers in action”: chapter 1 Lexers, chapter 2 Parsers, chapter 3 Generation. And few optimisations techniques in appendice to call it a day. Well, that didn’t work out as expected. Knuth quickly realises there is no proper framework to talk about marginal topics like data structures or algorithms. Remember it’s 1962, early days for our science. That’s all right, Knuth decides that instead of three chapters, he will write seven volumes and the title will now be The Art of Computer Programming. And that will be the undertaking of his life. Six years later in 1968, he publishes …volume 1: Fundamental Algorithms. Last release was in 2005 with volume 4a: Combinatorial Algorithms, Part 1. Expect volume 5 in 2020. I know! He will then be 82 and I am concerned too that we will never know how it ends… At least we know the title of the last volume: Compiler techniques. Still on track.

Fact #2: DIY Typesetting System

In 1977, after the release of the first version of the third volume, Knuth decides that enough is enough: the typesetting system in use by his publisher is frustratingly poor in quality. So he takes a sabbatical and starts writing his own¹. One year later, this is the first release of TeX². What a result! A “labor of love” according to his inventor but also of profound elegance. Speaking of which, Knuth also took the opportunity to invent a language to design vector font: METAFONT. No one will ever measure the magnitude of impact TeX has on today’s world. This becomes the de facto communication tool for ideas in academia. Particularly in Mathematics where it brings a standard and beautiful typography for formulas and equations. This illustrates perfectly one of Knuth’s principles that the very act of communicating one’s work clearly to other people will improve the work itself. We will get back to this later.

On top of TeX, Leslie Lamport would later add his own layer, LaTeX, the now dominant method for using TeX. I wish we had stopped there in terms of word processing in the software industry. If you’re not convinced, look at what you get from any document in Word 2013 and then admire a document produced by TeX82, e.g. The Only Probability Cheatsheet You’ll Ever Need. Don’t get distracted by the equations, feel the joy of your eyes skimming through this pure layout, watch out for those ligatures like in the double f in this off on line 2.

Or here to contemplate the power of those algorithms that optimise hypenation and spacing between words and letters to provide such a beautiful justification.

In TeX, this code:

\begin{align}
    E_0 &= mc^2                              \\
    E &= \frac{mc^2}{\sqrt{1-\frac{v^2}{c^2}}}
\end{align}

will produce this output:

\begin{align} E_0 &= mc^2 \\
E &= \frac{mc^2}{\sqrt{1-\frac{v^2}{c^2}}} \end{align}

Fact #3: Literate Programming

Ce que l’on conçoit bien s’énonce clairement,
Et les mots pour le dire arrivent aisément.

Whatever is well conceived is clearly said,
And the words to say it flow with ease.

– Boileau, The Art of Poetry (1674)

Ok, so we have mentioned this principle of Knuth’s that communicating one’s work clearly improves the work in itself. We also know of the dogfooding principle whereby using your own solution internally can be of great benefits in terms of design and usability³. What does that mean for TeX? In case you didn’t know, this is called Literate Programming. Knuth indeed coded TeX and METAFONT in TeX or more exactly in WEB. WEB is the first published literate programming environment. As you may have guessed, it was devised by Knuth. It uses TeX for typesetting and Pascal for the coding. In essence, a WEB file is a TeX file that describes and includes a program. With it, you can then tangle the source code ready for compilation and weave the document.

The literate programmer is more of an essayist. It is not totally surprising that it didn’t became mainstream as not all devs resonate with it. Yet TDD is no less radical while being mainstream. Anyways, I like to think it’s gently trending higher and higher. Some languages have native support for it (Haskell with .lhs, CoffeeScript with .litcoffee) and Docco is getting traction from various communities (e.g. Underscore.js, Jasmine to name a few in JS world alone).

It works really well for me. It makes the whole process of thinking, designing, testing and coding natural and pleasant. I use org-mode with org-babel. One day, I’ll have to show you that with a series of screencasts. But if you can’t wait, head over the literate source⁴ of the presentation featured in a recent post. From that simple file, you get the final presentation and the source code using 4 different programming languages⁵ which produces the material set included in it. Mind-blowing.

Oh, what a tangled web we weave
When first we practise to deceive!

– Sir Walter Scott, Marmion (1808), Canto VI, XVII

Fact #4: You Can’t Get Geekier

It’s actually a list of facts:

Asymptotic versioning: TeX version numbers asymptotically approach π. First version was 3, then 3.1, then 3.14, etc. For METAFONT, it’s e. Both are frozen and only accept fixes. When Knuth will pass away, versions will respectively become π and e and that will be the last change on those projects⁶.
If you find a bug or a typo in one of Knuth’s books or programs, you’ll get paid in hexadecimal dollars (0x$) as a deposit at the Bank of San Serriffe, “which is an offshore institution that has branches in Blefuscu and Elbonia on the planet Pincus”.
Knuth has a planet named after him.
In his spare time, he plays pipe organ which he designed.
He wrote a book that studies each verse 16 in chapter 3 of each book in the Bible: 3:16 Bible Texts Illuminated.

Famous Quotes

Beware of bugs in the above code; I have only proved it correct, not tried it.

Premature optimization is the root of all evil.

Fact #1: One Book, One Life

Fact #2: DIY Typesetting System

Fact #3: Literate Programming

Fact #4: You Can’t Get Geekier

Famous Quotes

Further Reading