The Computer Scientist Who Can’t Stop Telling Stories
Donald Knuth has worked his whole life to tell stories with and about computer programs.
Introduction
Donald Knuth is a computer scientist who came of age with his field. During the nascent years of computer programming in the middle of the last century, a candy company ran a contest that summoned his talents as a 13-year-old. The contest asked kids to determine how many words could be made from the letters of the candy’s name: Ziegler’s Giant Bar. It was a well-defined problem with distinct pieces, just the kind he loved.
“I had an obsessive-compulsive streak that drew me to digital, discrete problems. And I loved poring over large collections of information,” Knuth said.
Knuth methodically leafed through his family’s 2,000-page Funk & Wagnalls unabridged dictionary in the basement. He even convinced his parents he was sick, winning himself two weeks away from school to work on the problem. After labeling index cards with headings such as “Aa,” “Ab” and “Ba” based on the beginnings of possible words using letters from the candy’s name, he went down the dictionary’s columns noting words that qualified. He found that he could skip entire sections of the dictionary, such as pages for words starting with the letter “C,” or sections of the “B” words whose second letter was “U.”
The contest officials had identified approximately 2,000 words they could expect, but Knuth found more than 4,700. He was rewarded with a spot on television and chocolate for his entire class. He would go on to win many more accolades, including the first ACM Grace Murray Hopper Award, the National Medal of Science and the A.M. Turing Award.
Knuth eventually merged his dual loves of discrete digital problems and large collections of information in his magnum opus, The Art of Computer Programming — a book series he began writing as a graduate student in 1962 and has yet to complete. He published volume 1 in 1968, and the current version is in its 42nd printing. Volume 2 followed in 1969 and volume 3 in 1973. By then he was a computer science professor at Stanford University, but he worried that his work would prevent him from completing his books. So he took a leave of absence in 1990 and then retired in 1993 to spend the rest of his life completing the seven-volume set. Now 82, he’s hard at work on part B of volume 4, and he anticipates that the book will have at least parts A through F.
Knuth is currently working on volume 4, part B, of The Art of Computer Programming. He expects it to have at least four more parts, and the whole set to have three more volumes.
Jill Knuth
The Art of Computer Programming is more than a how-to manual. Just as Isaac Asimov and Eric Temple Bell wove narratives and characters into their science and math stories, Knuth delights in telling stories of computer science.
“The best way to communicate from one human being to another is through story,” he said.
This passion for communication helped him play another starring role in the story of computer science beyond his magnum opus. When his publisher sent him galley proofs for the second edition of volume 2 in the 1970s, Knuth was disturbed by the arrangement and appearance of the numbers, symbols and words on the pages. He flew to Los Angeles to see a machine that printed glossy magazines digitally, hoping it could provide aesthetic relief, but it was too expensive. Nonetheless, on that trip he began developing a computer language that would allow him to typeset mathematics digitally.
Back at Stanford, Knuth put aside The Art of Computer Programming for nearly a decade to develop TeX (pronounced “tech”), a sophisticated, game-changing program that put digital typography on a desktop computer. He made it open source, much to the benefit of professional mathematicians, computer scientists, economists, engineers, linguists, statisticians and anyone else who lacked technical symbols on their keyboards but understood the placement of complicated formulas better than their publishers. In a world of often ephemeral computer programs, TeX has endured as the gold standard for making scientific papers more beautiful and easier for experts to read and understand.
Knuth’s interest in storytelling also led him to develop a philosophy of literate programming — a method for writing computer programs as literary essays. A literate program intersperses source code with elegant prose written in a familiar language, such as English. The source code delivers functionality and efficiency, while the exposition addresses a human reader, rather than the computer’s compiler. Anyone who later updates or debugs a literate program will avoid the often time-consuming and costly problem of trying to understand the original programmer’s algorithms, design decisions and implementation strategies. Knuth is a computer scientist who understands that words matter.
Quanta Magazine spoke with Knuth in February at his home on the Stanford campus. The interview has been condensed and edited for clarity.
Have you always been interested in writing?
Early on, I was advised that the real world would be too hard for me. I didn’t expect to discover anything new, but I loved conveying my enjoyment of ideas in writing.
In sixth grade, a couple friends and I started a two-page paper on a ditto machine. We had jokes. In high school, every Monday night as the newspaper editor, I did an all-nighter to get the paper out. I saw my first line of type in college as the student paper copy editor. In my junior and senior years, we started the engineering and science review. For example, I wrote, “Th5E4 CH3EmIC2Al2 Ca3P4Er.” Every word was a chemical formula.
And that led to your magnum opus? Do you think of it as another story?
The Art of Computer Programming is a manifesto. It describes the way I love to do math and the way I wish I had been taught. Beginning on Page 1, I tell the story of algorithms. Most textbooks at the time didn’t explore the human side of discoveries. They just said, “This is how chemistry works,” or “This is how physics works.”
I also tell a technical story. I say, “Here’s something that doesn’t work, and here’s a way to solve that problem.” Instead of presenting only facts, I add drama. Science is much easier to learn if you know the sequence of discoveries. Also, I’m unable to resist a good story. I viewed myself not as a pioneer, but as a journalist.
Beyond the story, then, what’s The Art of Computer Programming about?
After two years of writing my book, I realized that its novelty was quantitatively determining how good a program is. I didn’t just want to say one program was better than another. I wanted to say one is 13.8% better than another, and explain how to compare them.
Author A would talk about algorithm A, and author B would talk about his competing algorithm B. And author A never wrote about algorithm B, and author B never wrote about algorithm A. Also, authors A and B used different computers. As a neutral journalist, I explained both from one point of view. Asking, “How good is an algorithm really?” is a fun problem. That’s the analysis of algorithms.
Is “the analysis of algorithms” just a different way of saying “the art of computer programming”?
I was at a Society for Industrial and Applied Mathematics conference in 1967 when somebody asked what I did. In those days, computer science was partitioned into numerical analysis, artificial intelligence and programming languages. That was it. I realized I needed a name for what I do.
My book’s novelty was its rigorous studies of how good the algorithms were. I decided that the next time I was asked this question, I would say, “Analysis of algorithms.” My definition was: If I’m interested in it, it’s the analysis of algorithms. It wasn’t a very good definition.
Later, I decided to justify it. I decided it was the quantitative study of how good an algorithm is, which I divided into two parts. One part considered all possible algorithms for a certain problem. The other part considered one particular algorithm for a certain problem.
Analysis of algorithms was going to be my life’s work. I told my publisher to change the title of my book to The Analysis of Algorithms. My publisher said, “That will never sell.” They made the right decision. Still, I was happy when, 40 years later, five or six books came out with the title Analysis of Algorithms.
But for you, programming is also about more than functionality. When you designed TeX, for example, you wanted to find “the most pleasing curve” that connects certain points. Were you trying to program beauty?
My program had to connect points in some way that reverse-engineered what a good calligrapher would do. The letter “S” comes to a point where the curvature changes from positive to negative. Then maybe it stays steady for a while. The letter’s designers followed some logic to make lines into letter shapes. I wanted to capture not only the design’s outcome, but the intelligence behind it. That’s like writing a computer program.
I talked to designers to understand what they were trying to achieve. The math was there to capture the design in a quantitative way. With mathematics, I put little dials on everything. I could say the letter “A” has got this point, that thickness, angles here, tapering there, a hump in the bottom and a certain serif length.
I never intended to replace designers. I only wanted to capture for future generations exactly what we were doing then. With TeX, a design is reproducible.
Did you anticipate TeX’s global acceptance or its ability to endure?
TeX was only supposed to be for my secretary and myself. Phyllis [Astrid Benson Winkler] was a wonderful secretary. She could read my handwriting and make it beautiful. Printing technology was going down the tubes because the tried-and-true methods were becoming too expensive. Nearly every piece of mathematics published in the 1970s looked atrocious. In the American Mathematical Monthly, the subscripts were in a different font from main-line text. I knew computer programming could make books look good again.
I finished debugging a trial version of TeX in April 1978. In May, I had 10 users. In June, I had 100 users. In July, I had 1,000. Each new group would say, “You’ve gotta have this feature.” Five years later, I released what is essentially the TeX we have now. That was designed for Americans. Then the Europeans started to use it. So in the 1980s, I made it work for world languages.
It sounds like discovery has always been part of your process. Does that remain true today?
I write an average of five new programs every week. Poets have to write poems. I have to write computer programs.
The ultimate test of whether I understand something is if I can explain it to a computer. I can say something to you and you’ll nod your head, but I’m not sure that I explained it well. But the computer doesn’t nod its head. It repeats back exactly what I tell it. In most of life, you can bluff, but not with computers.
“The best way to communicate from one human being to another is through story,” Knuth said. This approach allowed him to analyze algorithms more rigorously and neutrally.
You spend your days writing, but you also have other interests. How do you approach each day?
Jack London wrote 1,000 words every day before talking to anybody. He was totally, “Let me alone until I’ve got my thousand words!” Then he would drink or proofread the rest of the day. No, my scheduling principle is to do the thing I hate most on my to-do list. By week’s end, I’m very happy.
Really? How does doing what you hate make you happy?
It would be very easy for me to say, “Oh, let me be a genius and never clean the toilet.” But even cleaning toilets is doable. [My wife] Jill and I got uniforms that have a slot where the 409 cleaner fits. You go over there and squirt and feel good cleaning the toilet!
A person’s success in life is determined by having a high minimum, not a high maximum. If you can do something really well but there are other things at which you’re failing, the latter will hold you back. But if almost everything you do is up there, then you’ve got a good life. And so I try to learn how to get through things that others find unpleasant.
Knuth at his home in 2020. He retired in 1993 to complete his magnum opus, The Art of Computer Programming.
Jill Knuth
You also have many projects that have nothing to do with computer science, such as your musical composition, Fantasia Apocalyptica. You even built your house around a two-story pipe organ. Is this variety also part what makes you happy?
I wrote a couple of books, including Things a Computer Scientist Rarely Talks About, that are about theology — things you can’t prove — rather than mathematics or computer science. My life would not be complete if it was all about cut and dried things. The mystical things I don’t understand give me humility. There are things beyond my understanding.
In mathematics, I know when a theorem is correct. I like that. But I wouldn’t have much of a life if everything were doable. This knowledge doesn’t tear me apart. Rather, it ensures I don’t get stuck in a rut.
Does it matter if you finish The Art of Computer Programming?
Oh, I realize that computer science will keep living and developing. One scenario is that everybody will stop working on the kinds of computers we have now. They’ll all go to machine learning and use quantum computers. Then I could come to the end of the story of non-quantum computers. I’m happier when I can say, “This is the story’s end.” That’s the easiest way to imagine that I’ll finish. But I’m not answering your question.
Do you know the story of Tristram Shandy? Laurence Sterne, in the late 1700s, wrote an autobiographical book, The Life and Opinions of Tristram Shandy, Gentleman, which he published in fascicles, or installments. It has about 100 pages just on his first week of life. He wants the life story to be complete but, of course, he won’t make it. Sterne wrote Tristram Shandy’s story until he couldn’t write anymore.
I want to continue writing good content in the best way I know, and cover things for which I have something original to say. I’ll do as much of that as I can, instead of saying that I’ve got to finish by a certain deadline. I’ve been so fortunate riding waves and being born at a time that was just right for my particular peculiarity. I’ve now achieved all of my life’s goals except The Art of Computer Programming. I’m in a situation where I’ll continue telling whatever stories I find and passing them on.
Correction: April 17, 2020
This article previously misidentified the number of printings of volume 1 of The Art of Computer Programming and the year Knuth released TeX. Both have been corrected.
