In the nearly fifty years since beginning the book, ‘The Art of Computer Programming’, that has almost defined computer programming as much as it has defined him, Donald Knuth has received awards including the Kyoto Prize (1996), the Turing Award (1974), and the National Medal of Science (1979). He is an extraordinary man. As well as inventing ‘Literate Programming’ and writing the most important textbook on programming algorithms, he is also famous for designing and programming one of the most widely-used digital typesetting systems ever, even designing the fonts that went with it. He also pioneered the use of ‘Open-source’ software.

Knuth is a man of engaging charm and enthusiasms who combines a knowledge of history, music, art and mathematics with a unique insight into the art of computer programming.

Don Knuth has always viewed the stages of writing ‘The Art of Computer Programming’ as the most important project of his life.

Knuth’s full-time writing schedule means that he is ‘pretty much a hermit… concentrating intensively and uninterruptedly on one subject at a time, rather than swapping a number of topics in and out of his head. I’m unable to schedule appointments with visitors, travel to conferences or accept speaking engagements, or undertake any new responsibilities of any kind.’

The irony is that computer science nearly lost Knuth to its ranks because of his love of music (his house is built around a two-storey pipe organ that he designed himself) and says he intends to return to it once he has completed the expected seven volumes of ‘The Art of Computer Science’.

RM:

Don, the last time we spoke we touched on complexity and you said that simplicity was the only answer to this. Why is it important to find simple solutions to software problems?

DK:

It is important to find simple solutions instead of stopping as soon as a first solution is found.

I suppose people usually stop early because most problems do not have a simple solution; thus they figure there’s no reason to spend any time looking further. If we start with the assumption that a simple solution does exist, we’re much more likely to find one.

RM:

You have an essay about developing TeX where you talk about going over to a pure, destructive QA personality and trying your hardest to break code. Do you think most developers are good at that?

DK:

You are right that it takes a certain kind of mentality to create test cases that will detect subtle bugs. For example, I know that I’m not sneaky enough to ever become an expert on cryptography or computer security.

On the other hand I have been reasonably successful at designing torture tests for software that I’ve written, mostly by
   (1) imagining myself as the enemy of the system, rather than as its friend;
   (2) thinking of inputs that are legal but bizarre and unlikely ever to be useful;
   (3) embedding an incredibly complicated construction into another that’s even less scrutable.

Some parts of my test programs for TeX and METAFONT required many hours of thought before I could convince myself that the program did the right thing. But in the process I discovered bugs that I’m pretty sure wouldn’t have been found by any other method that I’ve ever heard about.

Even better results will presumably be obtained if several different people independently create the torture tests. I can imagine that test creation would be a satisfying career.

I guess I do tend to use systems in unexpected ways, and I get some satisfaction when this reveals a flaw. For example, I remember having fun while visiting my sister and playing with a `shoot-em-up’ game that my nephew showed me.

Since I’m kind of a pacifist, I tried shooting bullets at the wall, instead of trying to kill the hidden attackers. Sure enough, I could spell my name on that wall, by making bullet holes in an appropriate pattern. But later when I came back to that same position, after wandering around further in the game, my name was gone! I think that was a bug in the software.

Long ago when I was a teenager, probably in 1952 or 1953, I saw my first “computer game”, a demonstration of tic-tac-toe at a museum in Chicago where visitors were challenged to beat a machine.

The exhibit was designed by AT&T, and I think it was controlled by relay switches rather than by a real general-purpose computer.

‘Hmm. No Angry Birds here!’
(Don Knuth with an IBM 650 in 1958)

I knew that I could never win if I made normal responses; so I intentionally made the stupidest possible moves. The machine got to a position where it had two ways to beat me by completing three in a row. I decided not to block either possibility. In response, the machine made both of its winning moves … and this was clearly in violation of the rules. So I had won a moral victory.

Thus, it appears that an encouragement to “think outside the box” helps for designing test cases, just as it does in many other situations.

RM:

If you were to start over and design TeX today, would the advances in computing or your understanding change the design in dramatic ways or would it turn out mostly the same?

DK:

I’m not sure if anybody can still write such a program today, without paying a fortune to license patented ideas. But suppose we ignore such problems; then I would keep the system basically as it is now.

The only serious mistake that I regret making with respect to TeX is that I used binary arithmetic internally but decimal arithmetic in the user interface; I should have done all computations in decimal.

RM:

What would you suggest to someone who wants to be a better software > designer? Decide if they want to make money or whether they want to do science? Do you think we need better incentives to make better software?

DK:

I think existing incentives are working fine, except of course that I wish more people would discover the advantages of literate programming.

RM:

Is there any truth in the rumour that Chuck Moore had an influence on your thinking about algorithms or you having any influence on Chuck?

DK:

We haven’t intersected at all, as far as I know.

RM:

What’s your process look like when you’re doing exploratory programming and readying it for publication?

DK:

I write about five programs each week, on average, and I continue to enjoy making them “literate”. I often tear up the first draft or two, after I see how things are going, because algorithms tend to be full of surprises. I often make close studies of code written by the leading experts in whatever kind of application I’m currently studying; but I also try to rethink everything from scratch. I make many mistakes, but afterwards I try to help my readers to avoid them.

RM:

How do you define the idea of designing a programming language? Is it a tool to express ideas or a tool to express goals?

DK:

I think of a programming language as a tool to convert a programmer’s mental images into precise operations that a machine can perform. The main idea is to match the user’s intuition as well as possible. There are many kinds of users, and many kinds of application areas, so we need many kinds of languages.

I discuss language design in detail in Chapter 11 of my recent book ‘Selected Papers on Computer Languages’. I was asked in the 1960s to write about this topic, and the best way I could figure out to explain principles of good design was to violate them all and to present the design of BL\I, “Bad Language One”. But I hesitated for more than 40 years before publishing anything about BL\I, because I was afraid people might implement it and start to use it. Finally, when preparing that book, I decided to take a chance.

RM:

I realise this is an enormous question, but what is the link between the design of a language and the design of software written with that language?

DK:

The software writers who have particular ways of thinking about algorithms need a language that matches their thoughts so that they can efficiently transform those thoughts into working code.

Different thought processes result in different structures.

RM:

What are the major problems in the computer industry today?

DK:

D’uh. I’m just an academic who writes about programming; I never have understood industry or economics.

RM:

Do you prefer freedom or order? Do you prefer one way to do a single thing, or a thousand ways to reach the same goal?

DK:

(a) Freedom AND order. (b) I guess I prefer maybe three ways, having different characteristics, together with the knowledge of how to convert each of them into the other two.

RM:

In what ways do you think you have influenced the computer industry as a technologist and what lessons should people learn from your experience?

DK:

I can’t say what influence I’ve had, but I can summarize what I’ve been trying to accomplish during my career: I’ve attempted to organize many of the best ideas that have been discovered related to programming, and to explain them effectively, because I believe computer science is a beautiful body of knowledge.

I’m glad that this knowledge has proved to be very useful, although I would actually want to organize it and explain it even if the only motivation were intellectual curiosity and a desire to explore fascinating patterns.