An Interview With Donald Knuth
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
honorable term, but to some people a computer program-
considered one of the world’s leading computer scientists.
mer is somebody who just follows instructions without un-
Although he’s authored more than 150 publications, it is
derstanding what he’s doing, one who just knows how to
Knuth’s three-volume The Art of Computer Programming
get through the idiosyncrasies of some language.
which has become a staple on every programmer’s book-
To me, a computer scientist is somebody who has a way
shelf. In 1974, Knuth was the recipient of computer sci-
of thinking, which resonates with computer programming.
ence’s most prestigious prize, the Turing Award. He also
The way a computer scientist views knowledge in general
received the National Medal of Science in 1979.
is different from the way a mathematician views knowl-
In addition to his work developing fundamental algorithms
edge, which is different from the way a physicist views
for computer programming, Knuth was a pioneer in com-
knowledge, which is different from the way a chemist,
puter typesetting with his TEX, METAFONT, and WEB ap-
lawyer, or poet views knowledge.
plications. He has written on topics as singular as ancient
There’s about one person in every fifty who has this pecu-
Babylonian algorithms and has penned a novel. Knuth cur-
liar way of viewing knowledge. These people discovered
rently is Professor Emeritus at Stanford University.
each other at the time computers were born. There’s a pro-
Born in Milwaukee, Knuth exhibited an early aptitude for
file of different intellectual capabilities which makes some-
patterns, as evidenced by his creation of crossword puzzles
body resonate, which makes somebody really in tune with
for the school newspaper. This ability culminated in the
computer programming.
eighth grade when Knuth won a national contest sponsored
There were computers in the 19th century, the 17th cen-
by a candy manufacturer. According to Dennis Shasha and
tury...I imagine there are computer scientists in the pygmy
Cathy Lazere, authors of Out of Their Minds: The Lives
forest. I haven’t really carried this out as an experiment,
and Discoveries of 15 Great Computer Scientists, the chal-
but I imagine that people may not have machines but one
lenge was to compose as many words as possible using the
in fifty of them, wherever you go, has this profile, this abil-
letters in the phrase ‘Ziegler’s Giant Bar.’ The judges had
ity. I’m not a sociologist, nor an anthropologist, but read-
about 2500 words on their master list; Knuth came up with
ing publications, reading literature, I can sense how much
approximately 4500 words without using apostrophes.
people think like I do, even if they were writing from a dif-
Still, it was music that Knuth chose to study at Case In-
ferent century.
stitute (later Case Western Reserve) until he was offered
This is the true explanation of why computer science be-
a physics scholarship. This lead him to his first encounter
came a university department so fast all around the world.
with a computer in 1956 — an IBM 650.
The reason is not that computers are important tools for
In this interview, Knuth chats with frequent DDJ contribu-
mankind, or something like that. The reason is that there
tor Jack Woehr about these and other topics.
were these people out there who had this way of thinking
that never had a home before. They get together, they can
− − ∗ − −
communicate high bandwidth to each other, the same kind
of analogies are meaningful to them. All of a sudden they
DDJ: What distinguishes a ‘computer scientist’ from a
could come together and work much more efficiently, not
‘computer programmer?’
in someone else’s territory that wasn’t for them.
DK: The difference between a computer programmer and
There was a time when there were no physics departments,
a computer scientist is a job-title thing. Edsgar Dijkstra
there was ‘Natural Philosophy,’ which combined all kinds
wants proudly to be called a ‘computer programmer,’ al-
of different skills. Over the years, these strong areas of fo-
though he hasn’t touched a computer now for some years.
cus materialize, become recognized, and then they get a
He wrote his really terrific essay on the Humble Program-
name. ‘Computer Science’ happens to be one of the more
mer discussing this. To me, ‘computer programmer’ is an
recent ones to crystallize in this way.
∗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 Com-
DK: I have books that are going to exist no matter how the
puter Programming?
technology 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
DDJ: Has your digression into TEX and METAFONT been
combinatorial algorithms. Volume 4-a is about finding all
profitable, as well as rewarding?
possibilities: There’s a lot to be said about generating them
DK: I put it in the public domain, but I do get royalties on
in good ways — problems where finding all reasonable so-
the books. I give one-third of those to the user group. The
lutions is not a trivial task. 4-b is going to be about graph
important thing, once you have enough to eat and a nice
and network algorithms, and 4-c is about combinatorial op-
house, is what you can do for others, what you can con-
timization. So 4-a is ‘find all arrangements,’ 4-b is ‘find ar-
tribute to the enterprise as a whole.
rangements that have to do with graphs and networks,’ and
4-c is ‘find the best arrangement.’
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 print-
ing industry became computer science. It changed from
metallurgy 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 that
was very timely. My students and I worked very hard on
− − ∗ − −
the desktop-publishing revolution.
− − ∗ − −
DDJ: I wonder if that same philosophy informs your sci-
entific discipline. To the vast majority of the computer lit-
erate, you made a large contribution in stating once and for
DDJ: One goes to accomplish a task on the computer and
all how one, for instance, divides two binary numbers effi-
realizes that to finish it requires another task, and to finish
ciently. A programmer wonders how to do something and
that one requires another...
reaches over his or her shoulder for ‘knuth,’ it’s like reach-
DK: Niklaus Wirth always wanted to design airplanes, but
ing for a ‘thermos.’
he needed a better tool, so he designed many computer lan-
DK: I tried to write things up in a way that was jargon-free,
guages and microcomputers and so on. I needed to write
so the nonspecialist would understand it. What I succeeded
my books in some way that would be immune to changes
in doing is making it so that the specialist can understand it,
in technology, to capture the book in some electronic form
but if I hadn’t tried to write jargon-free, then I would have
that wasn’t going to change when the printing establish-
written for specialists, and then the specialists wouldn’t be
ment changed.
able to get it either. So I’ve been reasonably successful in
− − ∗ − −
boiling down a large volume of material, but still my books
aren’t easy reading except for specialists.
DDJ: I’ve read the laments of the memorizers of Egypt
I’m about to publish a book, Selected Papers in Computer
that were recorded by the scribes when introduced in the
Science, which is a collection of papers I’ve written over
ancient kingdom. You’re one who is not going to curse
the years for nonspecialists. It’s being published jointly by
the darkness, you’re getting ready for the time when books
the Center for the Study of Linguistics at Stanford (CLSI)
aren’t printed anymore.
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 Knuth
35
ing them again, though I’ve edited them to take out sexist
than but also in templates. There are lots of little things like
language! I think this book is something that might be of
this, and many things in the implementation, that you can’t
interest to the scientific community as a whole.
be sure the compiler will do anything reasonable with.
I plan eight books collecting all the papers I’ve written:
Languages keep evolving, and that’s necessary. I find it im-
There’s going to be Selected Papers in Analysis of Algo-
possible to write books for archival without resorting to the
rithms, Selected Papers in Digital Typography, Selected
English language, though. Whatever computer language is
Papers in Fun and Games, Selected Papers in Program-
in fashion, you can guarantee that within a decade or two
ming Languages, and so on. This is the second volume; the
it will be completely out of fashion. In my books, I try to
first volume was Literate Programming.
write things that aren’t trendy, but are things that are going
to be worth remembering for other generations. I’m trying
DDJ: What has the reward you offer for finding bugs in TEX
to distil what, in my best judgment, out of thousands and
reached? I had heard it was up to $40.96.
thousands of things that are coming out now, is most de-
DK: Oh, that! The reward doubled every year until it
serving to be remembered.
reached $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 Febru-
ary.
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
DDJ: That was the problem posed by the inventor of the
C++.
chessboard in ancient India, who asked for one grain of
wheat on the first square, two on the second, four on the
− − ∗ − −
third...
DK: It was al-Biruni in 10th-century Baghdad who ex-
DDJ: There’s a great difference between his scrupulous ex-
plained how to calculate 264 efficiently by repeated squar-
amination of each and every algorithm, and the practice of
ing.
commercial programming, where megabytes of code with
known 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,
DDJ: This is one of the computer scientists of other eras
aware of the formal methods, I can be much more sure than
about whom you spoke earlier.
I would be without the formal methods. But I don’t see any
DK: He was definitely a computer scientist.
He knew
hope of proving everything in these large systems, because
how many grains of wheat there were without doubling 64
the proof would be even more likely to have bugs!
times.
− − ∗ − −
al-Khw¯arizm¯ı, who lived about 150 years before that, gave
us his name as ‘algorithm.’ There were great books about
chess already in the 9th century. The successor to Haroun
DDJ: Programs nowadays depend on huge bodies of code
al-Rashid of the Thousand and One Nights, Caliph al-
that aren’t written by the main author.
Ma’mun, established a great center of learning and a 25-
DK: And you look at them and see how each spends most of
year flowering of art and science — al-Khw¯arizm¯ı pub-
its time trying to defeat the other. It’s all these black boxes
lished there about algebra and arithmetic and geography.
you can’t open, so you have to build your own firewall.
One of his books is about the Jewish calendar. I discuss
this in Selected Papers in Computer Science.
This is nothing new. In the ’60s, someone invented the con-
cept of a ‘jump trace.’ This was a way of altering the ma-
− − ∗ − −
chine 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 inter-
DDJ: I understand you are not entirely a partisan of the
preting each instruction one at a time and record in a file
C++ language.
just where a program diverged from sequentiality. By pro-
DK: C++ has a lot of good features, but it has a lot of dirty
cessing this file you could figure out where the program
corners. If you don’t mind those, and you stick to stuff that
was spending most of its time.
can be counted well-portable, it’s just fine. There are many
So the first day we had this software running, we applied
constructions that are ambiguous, there’s no way to parse
it to our Fortran compiler supplied by, I suppose it was in
them and decide what they mean, that you can’t trust the
those days, Control Data Corporation. We found out it was
compiler to do. For example, you use the ‘less-than’ and
spending 87 percent of its time reading comments! The
‘greater-than’ signs not only to mean less-than and greater-
Bijlage M
An Interview with Donald Knuth
36
reason was that it was translating from one code system
people who are only good at the uniform things could never
into another into another.
build a model out of nonuniform parts, could never do the
things that a computer scientist does, because they have to
− − ∗ − −
find a single rule that’s going to cover everything.
We have this aesthetic of cost, how much work it takes to do
DDJ: GUIs haven’t made this any better.
things. If your mental model is APL, you optimize in dif-
DK: We now have so much more processing power that the
ferent ways than if your mental model is a RISC machine.
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 idea
DDJ: When you look back at the first three volumes of The
of using this software to get much done. I’m going to go
Art of Computer Programming is there anything you would
back and write my books with good old reliable Emacs and
change?
TEX.
DK: I have about 900K of changes to the first three vol-
I still haven’t found an editor on the Macintosh where I
umes, plus changes to other books that I’ve written, that I
can create a 1-byte file that has the letter ‘a’ in it that I
plan to make available on my Web page. There are four
can send to the PC and read on an Emacs-like editor. I got
kinds of changes, and the different kinds are distinguished
optical-character-recognition software that has a choice of
typographically.
50 output formats. Each one of them included all kinds of
One kind is a ‘bug’ and that means that I have to cor-
font-changing mechanisms, and so on. Finally, I found one
rect something that is technically wrong. One kind is an
called ‘database text’ and if I output it in database text, that
‘amendment,’ which means that there is some goodie that
was what I was expected to get — raw ASCII characters.
deserves to be in there. One kind is an ‘improvement,’
It’s a natural way to get job security, to make computer sys-
something which would go in a future edition of the book,
tems that need one’s expertise.
but is probably not worth people’s writing it in their own
copy. The fourth thing is called a ‘plan,’ something still un-
My TEX system is trying to go the other way, so I wouldn’t
der construction, where the picture is changing so fast that
have to go through the professional typesetters, the profes-
I don’t think it’s cost efficient for me to write on, since I’ll
sional font designers. I could still use these professionals,
just have to do it again, the kettle is still boiling, but I wish
but I could use them to provide added value. I didn’t have
to state that I intend to retool something in a certain way.
to go through a level of writing something for them to do
and then check on it. I can write something, and they can
It will probably be a while before publishing changes so
tell me how to improve, but I don’t need to write something
that entire books can be available online. I don’t know how
that they already have on the menu.
to convert the present system to a better one that will still
have the proper incentive structure. There’s something all
− − ∗ − −
fouled up about the way that software is compensated and
font designers are compensated and musicians are compen-
DDJ: Is the profile of a programmer (which we were dis-
sated, and other intellectual-property rights issues. A sci-
cussing earlier) one of an individual who needs this sort of
entist can be supported by the National Science Founda-
control?
tion but a font designer is not supported by a National Font
Foundation. Both of them are doing things that contribute
DK: That’s an interesting concept, the need for power! I’ve
to the public good.
always thought of it more in other terms, that the psycho-
logical profiling is mostly the ability to shift levels of ab-
− − ∗ − −
straction, from low level to high level. To see something
in the small and to see something in the large.
DDJ: Is this just an expression of a love for symmetry, or
When you’re writing a program, you’re saying, ‘Add one
is there a social injustice being performed here?
to the counter,’ but you know why you’re adding one to the
DK: I think that the fact that somebody’s expertise is in the
counter. You can step back and see a picture of the way a
field of beauty and graceful strokes and another’s is in the
process is moving. Computer scientists see things simulta-
field of integrals and differential equations shouldn’t mean
neously at the low level and the high level.
they have completely different ways of getting paid.
The other main characteristic of the computer scientist is
The Free Software Foundation people are putting out good
dealing with nonuniformity of discreet, nonuniform things.
stuff. It’s hard for the untrained person to wade through the
We have ten cases instead of one. We don’t have one law
jargon to install it. Richard Stallman and I don’t agree all
of thermodynamics, or something. We have case one, case
the way down the line, but he can be an effective arguer!
two, case three — each is different. We build models out
Stallman is one of my heroes, of course. He probably likes
of nonuniform parts. We’re so good at that, we don’t see
some of the things I do, too!
sometimes that a uniform part would work, if it would. But
Bijlage M
An Interview with Donald Knuth
37
It offends me when people get patents on trivial stuff that
precedents? What if people had patents on words of the
we would expect any student to do. I come from a culture
English language, and every author who wanted to write
where the compensation came because one’s work was rec-
a novel would have to check which words they were using
ognized as advancing civilization. Of course, in literature
and pay royalties to the owners of those words? Can’t you
there were royalties, not grants. But mostly it was that peo-
see how obvious it is that the quality of the legal system and
ple had done good work, so you figured they deserved a
the quality of published books would go down? Because
continuing job. If I were to consider a strategy of becoming
you’re taking away the building blocks that people need to
rich, it would be so I could support people who need sup-
do their job.’
port, who I consider are doing things for the future, like the
The basic building blocks that software designers need to
dukes and duchesses used to support Mozart.
do their jobs are algorithms and languages and mathemat-
− − ∗ − −
ics. It’s traditionally impossible to patent a mathematical
formula, for very good reason. Anyone who would wish to
calculate the area of a circle and use πr2 should have to pay
DDJ: If you could climb in the pulpit and scold, exhort, and
a royalty for that: It’s exact, it’s a universal thing. I think
encourage every working programmer in the United States,
that algorithms should be in exactly the same category. Al-
what would you tell them?
gorithms are mathematics.
DK: The first thing I would say is that when you write a pro-
Algorithms are the building blocks to create large, use-
gram, think of it primarily as a work of literature. You’re
ful systems. The service that you’re providing for people
trying to write something that human beings are going to
is making those systems more accessible, packaging them
read. Don’t think of it primarily as something a computer
better, giving better help on the phone, but not just having
is going to follow. The more effective you are at making
a method that other people could put into another system.
your program readable, the more effective it’s going to be:
You’ll understand it today, you’ll understand it next week,
I would encourage programmers to make their work known
and your successors who are going to maintain and modify
the way mathematicians and scientists have done for cen-
it will understand it.
turies. It’s a comfortable, well-understood system and, you
get a lot of satisfaction knowing people like what you did.
Secondly, ideas that are mathematical in nature should be
The whole thing that makes a mathematician’s life worth-
the property of the world and not of the individual who
while is that he gets the grudging admiration of three or
thinks of the theorem. I’d prefer that all but the most so-
four colleagues.
phisticated algorithms be made public and that everybody
use them, and not that every time you use such-and-such a
method you should pay a nano-penny to some fund.
Acknowledgments
The author wishes to acknowledge the help of Steven
I wrote an open letter to the head of the U.S. Patent Com-
R. Wheeler of Vesta Technology in Wheat Ridge, Col-
mission, published in the current printing of the CWEB
orado, in preparing for this conversation with Dr. Knuth.
manual. I said, ‘What if lawyers were to have rights to their
