Should I be a mathematician? Should I be a computer scientist? By this time I had learned that it was actually possible to do mathematical work as a computer scientist. I had analysis of algorithms to do. What would be a permanent home? My model of my life was going to be that I was going to make one move in my lifetime to a place where I had tenure, and I would stay there forever.

the crisis comes.

At Caltech, I was preparing my class lectures, or typing my book. I didn’t have time to do research. If I had a new idea, if I said “Here’s a problem that ought to be solved,” when was I going to solve it? Maybe on the airplane. We were doing a lot of experiments but I didn’t have time to sit down at home and work out the theory for it. I had attribute grammars coming up in February, and these reductions systems coming up in March, and I was supposed to be grinding out Volume Two of The Art of Computer Pro-

i told my new wife,
Jill, “i think i’m
going to write a book.”
Well, we had just
four months of bliss,
because the rest of
our marriage has
all been devoted to
this book. We still
have had happiness,
but really, i wake up
every morning and
i still haven’t finished
the book. So i try
to organize the rest
of my life around
this, as one main
unifying theme.

gramming. I was scheduled in June to lecture at a summer school in Copenhagen about how to parse, what’s called top-down parsing.

What happened then, in May, is I had a massive bleeding ulcer, and I was hospitalized. My body gave out. I was just doing all this stuff, and it couldn’t take it.

I learned about myself. The doctor showed me his textbook that described the typical ulcer patient: what people call the “Type A” personality. It described me to a T. All of the signs were there. I was an automaton, I think, basically. I saw a goal and I put myself to it, and I worked on it and pushed it through. I didn’t say no to people when they asked, “Don, can you do this for me?” At this point I saw I had this problem. I shouldn’t try to do the impossible.

he changes his lifestyle,
and moves to Stanford.

I wrote a letter to my publisher, framed in black, saying, “I’m not going to be able to get the manuscript of Volume Two to you this year. I’m sorry.” I resigned from 10 editorial boards. No more JACM, no more CACM. I gave up all of the editorships in order to cut down my workload. I started working on Volume Two where I left off at the time of the ulcer, but I would be careful to go to sleep and keep a regular schedule. I went to a conference in Santa Barbara on combinatorial mathematics and had three days to sit on the beach and develop the theory of attribute grammars, this idea of top-down and bottom-up parsing.

In February of 1968 I finally got the offer from Stanford. The committees were saying, “This guy is just 30 years old.” But when they looked at the book, they said, “Oh, there’s some credibility here.” That helped me.

 

Why he writes his books with a pencil. I love keyboards, but my manuscripts are always handwritten. The reason is that I type faster than I think. There’s a synchronization problem. I can think of ideas at about the rate I can write them down with a pencil. But with typing I’m going faster, so I have to sync, and my thoughts have to start up and stop again in a way that involves more of my brain.

three volumes of “the art” are
done, but it’s time for a pause.

Volume Four is about combinatorial algorithms. Combinatorial algorithms were such a small topic in 1962, when I made that Chapter Seven of my outline, that Johan Dahl asked me, “How did you ever think of putting in a chapter about combinatorial algorithms in 1962?” I said, “Well, the only reason was that it was the part I thought was most fun.” But there was almost nothing known about it at the time.

The way I look at it, this is where you’ve got to use some art. You’ve got to be really skillful, because one good idea can save you six orders of magnitude and make your program run a million times faster. People are coming up with these ideas all the time. For me, the combinatorial explosion was the explosion of research in combinatorics. Not the problems exploding, but the ideas were exploding. There’s that much more to cover now.

It’s true that in the back of my mind I was scared stiff that I can’t write Volume Four anymore. So maybe I was waiting for it to simmer down. Somebody did say to me once, after I solved the problem of typesetting, maybe I would start to look at binding or something, because I had to have some other reason [to delay]. I’ve certainly seen enough graduate student procrastinators in my life. Maybe I was in denial.

 

He solves the problem of typesetting? Stay tuned for Part II of this interview in the August issue and learn how Knuth interrupted his life’s work on The Art of Computer Programming to create a system that makes digitally produced books beautiful.

 

Edited by Len Shustek, Chair, Computer History Museum