Bijlage M

An Interview with Donald Knuth

33

An Interview with Donald Knuth
DDJ chats with one of the world’s leading computer scientists

Jack Woehr
Dr. Dobb’s Journal∗
editors@ddj.net

April 1996
For over 25 years, Donald E. Knuth has generally been
considered one of the world’s leading computer scientists.
Although he’s authored more than 150 publications, it is
Knuth’s three-volume The Art of Computer Programming
which has become a staple on every programmer’s bookshelf. In 1974, Knuth was the recipient of computer science’s most prestigious prize, the Turing Award. He also
received the National Medal of Science in 1979.
In addition to his work developing fundamental algorithms
for computer programming, Knuth was a pioneer in computer typesetting with his TEX, METAFONT, and WEB applications. He has written on topics as singular as ancient
Babylonian algorithms and has penned a novel. Knuth currently is Professor Emeritus at Stanford University.
Born in Milwaukee, Knuth exhibited an early aptitude forpatterns, as evidenced by his creation of crossword puzzles
for the school newspaper. This ability culminated in theeighth grade when Knuth won a national contest sponsoredby a candy manufacturer. According to Dennis Shasha and
Cathy Lazere, authors of Out of Their Minds: The Livesand Discoveries of 15 Great Computer Scientists, the challenge was to compose as many words as possible using theletters in the phrase ‘Ziegler’s Giant Bar.’ The judges had
about 2500 words on their master list; Knuth came up withapproximately 4500 words without using apostrophes.
Still, it was music that Knuth chose to study at Case Institute (later Case Western Reserve) until he was offereda physics scholarship. This lead him to his first encounter
with a computer in 1956 — an IBM 650.

honorable term, but to some people a computer programmer is somebody who just follows instructions without understanding what he’s doing, one who just knows how to
get through the idiosyncrasies of some language.
To me, a computer scientist is somebody who has a wayof thinking, which resonates with computer programming.
The way a computer scientist views knowledge in generalis different from the way a mathematician views knowledge, which is different from the way a physicist views
knowledge, which is different from the way a chemist,
lawyer, or poet views knowledge.
There’s about one person in every fifty who has this peculiar way of viewing knowledge. These people discovered
each other at the time computers were born. There’s a profile of different intellectual capabilities which makes somebody resonate, which makes somebody really in tune withcomputer programming.
There were computers in the 19th century, the 17th century...I imagine there are computer scientists in the pygmy
forest. I haven’t really carried this out as an experiment,
but I imagine that people may not have machines but one
in fifty of them, wherever you go, has this profile, this ability. I’m not a sociologist, nor an anthropologist, but reading publications, reading literature, I can sense how muchpeople think like I do, even if they were writing from a different century.

DDJ: What distinguishes a ‘computer scientist’ from a‘computer programmer?’This is the true explanation of why computer science became a university department so fast all around the world.
The reason is not that computers are important tools for
mankind, or something like that. The reason is that there
were these people out there who had this way of thinking
that never had a home before. They get together, they cancommunicate high bandwidth to each other, the same kindof analogies are meaningful to them. All of a sudden they
could come together and work much more efficiently, notin someone else’s territory that wasn’t for them.

DK: The difference between a computer programmer anda computer scientist is a job-title thing. Edsgar Dijkstra
wants proudly to be called a ‘computer programmer,’ although he hasn’t touched a computer now for some years.
He wrote his really terrific essay on the Humble Programmer discussing this. To me, ‘computer programmer’ is an

There was a time when there were no physics departments,
there was ‘Natural Philosophy,’ which combined all kindsof different skills. Over the years, these strong areas of focus materialize, become recognized, and then they get aname. ‘Computer Science’ happens to be one of the more
recent ones to crystallize in this way.

In this interview, Knuth chats with frequent DDJ contributor Jack Woehr about these and other topics.
−−∗−−

∗

This article was published in Dr. Dobb’s Journal of April 1996, p. 16 – 22. Reprinted Courtesy of Dr. Dobb’s Journal.

Bijlage M

An Interview with Donald Knuth

34

DDJ: When can we buy volume four of The Art of Computer Programming?

DK: I have books that are going to exist no matter how thetechnology changes.

DK: I’m going to be putting it out 128 pages at a time, about
twice a year over the next eight years. I’m estimating it
now at a little more than 2000 pages. There will be volume
4-a, volume 4-b, and volume 4-c. Volume 4 in general is
combinatorial algorithms. Volume 4-a is about finding all
possibilities: There’s a lot to be said about generating themin good ways — problems where finding all reasonable solutions is not a trivial task. 4-b is going to be about graphand network algorithms, and 4-c is about combinatorial optimization. So 4-a is ‘find all arrangements,’ 4-b is ‘find arrangements that have to do with graphs and networks,’ and4-c is ‘find the best arrangement.’−−∗−−
DDJ: Has your digression into TEX and METAFONT been
profitable, as well as rewarding?
DK: I put it in the public domain, but I do get royalties on
the books. I give one-third of those to the user group. The
important thing, once you have enough to eat and a nicehouse, is what you can do for others, what you can contribute to the enterprise as a whole.

Into those 2000 pages, I have to compress about 200,000
pages of literature. I’ve been working on it a long time.
−−∗−−
DDJ: Is the hiatus between volumes 3 and 4 writer’s block,that you say, ‘If I study this more...’
DK: No, that’s a pretty good hypothesis. But I had started
volume 4 and then realized I had to work on typography.
There was a revolution in the printing industry. The printing industry became computer science. It changed frommetallurgy to bits, to 0s and 1s. There was no way to print
my books with the quality they had before.
I was going to take a year and give a computer scientist’s
answer to how to print books, and that took ten years. The
systems are in common use today. So I think I’m going to
be able to recoup that. It wasn’t that I didn’t have anything
to say in volume 4, but that I had this other thing to do thatwas very timely. My students and I worked very hard on
the desktop-publishing revolution.
−−∗−−
DDJ: One goes to accomplish a task on the computer andrealizes that to finish it requires another task, and to finish
that one requires another...
DK: Niklaus Wirth always wanted to design airplanes, but
he needed a better tool, so he designed many computer languages and microcomputers and so on. I needed to write
my books in some way that would be immune to changes
in technology, to capture the book in some electronic form
that wasn’t going to change when the printing establishment changed.
−−∗−−
DDJ: I’ve read the laments of the memorizers of Egypt
that were recorded by the scribes when introduced in theancient kingdom. You’re one who is not going to curse
the darkness, you’re getting ready for the time when books
aren’t printed anymore.

−−∗−−
DDJ: I wonder if that same philosophy informs your scientific discipline. To the vast majority of the computer literate, you made a large contribution in stating once and for
all how one, for instance, divides two binary numbers efficiently. A programmer wonders how to do something andreaches over his or her shoulder for ‘knuth,’ it’s like reaching for a ‘thermos.’
DK: I tried to write things up in a way that was jargon-free,so the nonspecialist would understand it. What I succeededin doing is making it so that the specialist can understand it,
but if I hadn’t tried to write jargon-free, then I would havewritten for specialists, and then the specialists wouldn’t beable to get it either. So I’ve been reasonably successful inboiling down a large volume of material, but still my books
aren’t easy reading except for specialists.
I’m about to publish a book, Selected Papers in Computer
Science, which is a collection of papers I’ve written over
the years for nonspecialists. It’s being published jointly by
the Center for the Study of Linguistics at Stanford (CLSI)
and the Cambridge University Press. It has 15 chapters,
each of which was an expository lecture. I enjoyed read-Bijlage M

An Interview with Donald Knuth35

ing them again, though I’ve edited them to take out sexist
language! I think this book is something that might be ofinterest to the scientific community as a whole.

than but also in templates. There are lots of little things like
this, and many things in the implementation, that you can’t
be sure the compiler will do anything reasonable with.

I plan eight books collecting all the papers I’ve written:
There’s going to be Selected Papers in Analysis of Algorithms, Selected Papers in Digital Typography, Selected
Papers in Fun and Games, Selected Papers in Programming Languages, and so on. This is the second volume; thefirst volume was Literate Programming.

Languages keep evolving, and that’s necessary. I find it impossible to write books for archival without resorting to theEnglish language, though. Whatever computer language isin fashion, you can guarantee that within a decade or two
it will be completely out of fashion. In my books, I try towrite things that aren’t trendy, but are things that are going
to be worth remembering for other generations. I’m trying
to distil what, in my best judgment, out of thousands andthousands of things that are coming out now, is most deserving to be remembered.

DDJ: What has the reward you offer for finding bugs in TEX
reached? I had heard it was up to $40.96.
DK: Oh, that! The reward doubled every year until itreached $655.36 and I froze it at 216 pennies. It wouldn’t
take another ten or fifteen years before it began to exceed
the GNP, you know! I paid out a couple of those last February.
−−∗−−
DDJ: That was the problem posed by the inventor of thechessboard in ancient India, who asked for one grain of
wheat on the first square, two on the second, four on thethird...
DK: It was al-Biruni in 10th-century Baghdad who explained how to calculate 264 efficiently by repeated squaring.
−−∗−−
DDJ: This is one of the computer scientists of other eras
about whom you spoke earlier.
DK: He was definitely a computer scientist. He knew
how many grains of wheat there were without doubling 64
times.
al-Khwārizmı̄, who lived about 150 years before that, gave
us his name as ‘algorithm.’ There were great books aboutchess already in the 9th century. The successor to Haroun
al-Rashid of the Thousand and One Nights, Caliph alMa’mun, established a great center of learning and a 25year flowering of art and science — al-Khwārizmı̄ published there about algebra and arithmetic and geography.
One of his books is about the Jewish calendar. I discuss
this in Selected Papers in Computer Science.
−−∗−−
DDJ: I understand you are not entirely a partisan of theC++ language.
DK: C++ has a lot of good features, but it has a lot of dirty
corners. If you don’t mind those, and you stick to stuff thatcan be counted well-portable, it’s just fine. There are many
constructions that are ambiguous, there’s no way to parsethem and decide what they mean, that you can’t trust thecompiler to do. For example, you use the ‘less-than’ and‘greater-than’ signs not only to mean less-than and greater-−−∗−−
DDJ: You’ve mentioned Edsgar Dijkstra. What do you
think of his work?
DK: His great strength is that he is uncompromising. It
would make him physically ill to think of programming in
C++.
−−∗−−
DDJ: There’s a great difference between his scrupulous examination of each and every algorithm, and the practice ofcommercial programming, where megabytes of code withknown and unknown bugs are thrust at the user.
DK: I know, I know...I’m somewhere in the middle. I try
to clean up all bugs and I try to write in such a way that,aware of the formal methods, I can be much more sure than
I would be without the formal methods. But I don’t see any
hope of proving everything in these large systems, because
the proof would be even more likely to have bugs!
−−∗−−
DDJ: Programs nowadays depend on huge bodies of codethat aren’t written by the main author.
DK: And you look at them and see how each spends most of
its time trying to defeat the other. It’s all these black boxes
you can’t open, so you have to build your own firewall.
This is nothing new. In the ’60s, someone invented the concept of a ‘jump trace.’ This was a way of altering the machine language of a program so it would change the next
branch or jump instruction to retain control, so you could
execute the program at fairly high speed instead of interpreting each instruction one at a time and record in a filejust where a program diverged from sequentiality. By processing this file you could figure out where the program
was spending most of its time.
So the first day we had this software running, we applied
it to our Fortran compiler supplied by, I suppose it was inthose days, Control Data Corporation. We found out it was
spending 87 percent of its time reading comments! TheBijlage M

An Interview with Donald Knuth

reason was that it was translating from one code system
into another into another.
−−∗−−
DDJ: GUIs haven’t made this any better.
DK: We now have so much more processing power that the
only people who see what’s happening are people writing
game programs, who need real high-speed animation. I got
new software at Christmas, and I’m really discouraged by
the number of failures that I noticed. I’m giving up the ideaof using this software to get much done. I’m going to go
back and write my books with good old reliable Emacs andTEX.
I still haven’t found an editor on the Macintosh where I
can create a 1-byte file that has the letter ‘a’ in it that I
can send to the PC and read on an Emacs-like editor. I got
optical-character-recognition software that has a choice of
50 output formats. Each one of them included all kinds offont-changing mechanisms, and so on. Finally, I found one
called ‘database text’ and if I output it in database text, thatwas what I was expected to get — raw ASCII characters.
It’s a natural way to get job security, to make computer systems that need one’s expertise.
My TEX system is trying to go the other way, so I wouldn’t
have to go through the professional typesetters, the professional font designers. I could still use these professionals,
but I could use them to provide added value. I didn’t haveto go through a level of writing something for them to do
and then check on it. I can write something, and they cantell me how to improve, but I don’t need to write somethingthat they already have on the menu.
−−∗−−
DDJ: Is the profile of a programmer (which we were discussing earlier) one of an individual who needs this sort ofcontrol?
DK: That’s an interesting concept, the need for power! I’ve
always thought of it more in other terms, that the psychological profiling is mostly the ability to shift levels of abstraction, from low level to high level. To see something
in the small and to see something in the large.
When you’re writing a program, you’re saying, ‘Add one
to the counter,’ but you know why you’re adding one to thecounter. You can step back and see a picture of the way aprocess is moving. Computer scientists see things simultaneously at the low level and the high level.
The other main characteristic of the computer scientist isdealing with nonuniformity of discreet, nonuniform things.
We have ten cases instead of one. We don’t have one lawof thermodynamics, or something. We have case one, casetwo, case three — each is different. We build models outof nonuniform parts. We’re so good at that, we don’t see
sometimes that a uniform part would work, if it would. But

36

people who are only good at the uniform things could neverbuild a model out of nonuniform parts, could never do thethings that a computer scientist does, because they have tofind a single rule that’s going to cover everything.
We have this aesthetic of cost, how much work it takes to do
things. If your mental model is APL, you optimize in different ways than if your mental model is a RISC machine.
−−∗−−
DDJ: When you look back at the first three volumes of The
Art of Computer Programming is there anything you wouldchange?
DK: I have about 900K of changes to the first three volumes, plus changes to other books that I’ve written, that I
plan to make available on my Web page. There are fourkinds of changes, and the different kinds are distinguishedtypographically.
One kind is a ‘bug’ and that means that I have to correct something that is technically wrong. One kind is an‘amendment,’ which means that there is some goodie thatdeserves to be in there. One kind is an ‘improvement,’
something which would go in a future edition of the book,but is probably not worth people’s writing it in their own
copy. The fourth thing is called a ‘plan,’ something still under construction, where the picture is changing so fast that
I don’t think it’s cost efficient for me to write on, since I’ll
just have to do it again, the kettle is still boiling, but I wish
to state that I intend to retool something in a certain way.
It will probably be a while before publishing changes sothat entire books can be available online. I don’t know how
to convert the present system to a better one that will still
have the proper incentive structure. There’s something allfouled up about the way that software is compensated andfont designers are compensated and musicians are compensated, and other intellectual-property rights issues. A scientist can be supported by the National Science Foundation but a font designer is not supported by a National FontFoundation. Both of them are doing things that contributeto the public good.
−−∗−−
DDJ: Is this just an expression of a love for symmetry, oris there a social injustice being performed here?
DK: I think that the fact that somebody’s expertise is in thefield of beauty and graceful strokes and another’s is in thefield of integrals and differential equations shouldn’t mean
they have completely different ways of getting paid.
The Free Software Foundation people are putting out good
stuff. It’s hard for the untrained person to wade through thejargon to install it. Richard Stallman and I don’t agree all
the way down the line, but he can be an effective arguer!
Stallman is one of my heroes, of course. He probably likes
some of the things I do, too!

Bijlage M

An Interview with Donald Knuth

It offends me when people get patents on trivial stuff that
we would expect any student to do. I come from a culture
where the compensation came because one’s work was recognized as advancing civilization. Of course, in literature
there were royalties, not grants. But mostly it was that people had done good work, so you figured they deserved acontinuing job. If I were to consider a strategy of becomingrich, it would be so I could support people who need support, who I consider are doing things for the future, like thedukes and duchesses used to support Mozart.
−−∗−−
DDJ: If you could climb in the pulpit and scold, exhort, andencourage every working programmer in the United States,
what would you tell them?
DK: The first thing I would say is that when you write a program, think of it primarily as a work of literature. You’retrying to write something that human beings are going toread. Don’t think of it primarily as something a computeris going to follow. The more effective you are at making
your program readable, the more effective it’s going to be:
You’ll understand it today, you’ll understand it next week,
and your successors who are going to maintain and modify
it will understand it.
Secondly, ideas that are mathematical in nature should be
the property of the world and not of the individual who
thinks of the theorem. I’d prefer that all but the most sophisticated algorithms be made public and that everybody
use them, and not that every time you use such-and-such amethod you should pay a nano-penny to some fund.
I wrote an open letter to the head of the U.S. Patent Commission, published in the current printing of the CWEB
manual. I said, ‘What if lawyers were to have rights to their37

precedents? What if people had patents on words of the
English language, and every author who wanted to write
a novel would have to check which words they were using
and pay royalties to the owners of those words? Can’t you
see how obvious it is that the quality of the legal system andthe quality of published books would go down? Because
you’re taking away the building blocks that people need to
do their job.’
The basic building blocks that software designers need to
do their jobs are algorithms and languages and mathematics. It’s traditionally impossible to patent a mathematicalformula, for very good reason. Anyone who would wish to
calculate the area of a circle and use πr 2 should have to pay
a royalty for that: It’s exact, it’s a universal thing. I thinkthat algorithms should be in exactly the same category. Algorithms are mathematics.
Algorithms are the building blocks to create large, useful systems. The service that you’re providing for people
is making those systems more accessible, packaging thembetter, giving better help on the phone, but not just having
a method that other people could put into another system.
I would encourage programmers to make their work known
the way mathematicians and scientists have done for centuries. It’s a comfortable, well-understood system and, you
get a lot of satisfaction knowing people like what you did.
The whole thing that makes a mathematician’s life worthwhile is that he gets the grudging admiration of three orfour colleagues.
Acknowledgments
The author wishes to acknowledge the help of Steven
R. Wheeler of Vesta Technology in Wheat Ridge, Colorado, in preparing for this conversation with Dr. Knuth.