The things that I leave out are where somebody has a data structure thatsaves a factor of log log n only when n gets bigger than two to the million.And there are lots and lots of papers that are doing that. They’re playinggames where in principal, if computers were godlike, then we could havealgorithms that are faster. But even an algorithm like a balanced tree or AVLtree, I don’t use in my own programs unless I know that it’s going to be areally big tree.

Seibel: What do you use?

Knuth: I use an ordinary binary search tree with a little trick forrandomizing it that I just put in.

Seibel: Speaking of practical work, in the middle of working on The Art ofComputer Programming you took what turned into a ten-year break to writeyour typesetting system TeX. I understand you wrote the first version ofTeX completely away from the computer.

Knuth: When I wrote TeX originally in 1977 and ’78, of course I didn’thave literate programming but I did have structured programming. I wrote itin a big notebook in longhand, in pencil.

Six months later, after I had gone through the whole project, I started typinginto the computer. And did the debugging in March of ’78 while I hadstarted writing the program in October of ’77. The code for that is in theStanford archives—it’s all in pencil—and of course I would come back andchange a subroutine as I learned what it should be.

This was a first-generation system, so lots of different architectures werepossible and had to be discarded until I’d lived with it for a while and knewwhat was there. And it was a chicken-and-egg problem—you couldn’ttypeset until you had fonts but then you couldn’t have fonts until you couldtypeset.

But structured programming gave me the idea of invariants and knowinghow to make black boxes that I could understand. So I had the confidencethat the code would work when I finally would debug it. I felt that I wouldbe saving a lot of time if I waited six months before testing anything. I hadenough confidence that the code was approximately right.

Seibel: And the time savings would be because you wouldn’t spend timebuilding scaffolding and stubs to test incomplete code?

Knuth: Right.

Seibel: Other than the fact that they’re so nicely typeset now, do you thinkyour books would be very different if you hadn’t spent ten years writingTeX?

Knuth: Good question. The experience of using structured programming ina not purely academic way—in other words, I’m not just thinking aboutinvariants in toy programs, but in real programs—probably had a fairinfluence on how I’m describing algorithms in the new stuff I write now. Orif it hasn’t, it should.

I wouldn’t have known about caching and trends in the way computerschange and things like that if I was just going on in the same mold of goingfrom the literature to writing my books. While I was writing Volumes I, II,and III, I wasn’t writing programs like TeX that that would be more typicalof a large programming practice. They would be toy programs. So it gaveme more of a perspective on numbers and quantity.

It’s really amazing, though, when you’re writing a book, the influences thatwill make you choose different words. It’s mysterious how it gets in there.That’s the most important influence of writing TeX—that it gave me adifferent kind of a mental take on things so that my sentences come outdifferent. They’ll be a little bit less hedgy. There is a tone that comes out inthe whole thing, of confidence or something.

Seibel: Do you think you were a dramatically better programmer whenyou finished TeX than when you started?

Knuth: Well, yes, because of literate programming.

Seibel: So you had better tools, but had you actually improved your skills?

Knuth: I learned a terrific amount while I was doing it. One of the things Ilearned was how much software occupies the brain. It was a much moredifficult task than I expected. I couldn’t teach classes full-time and writesoftware full-time. I could teach classes full-time and write a book full-timebut software required so much attention to detail. It filled that much of mybrain to the exclusion of other stuff. So it gave me a special admiration forpeople who do large software projects—I would never have guessed itwithout having been faced with that myself.

Seibel: So programming is harder than writing books, and somewhere Iread something where you said that it’s impossible to estimate how long itwill take to write books. Does that then mean that it’s even harder toestimate how long programming will take?

Knuth: Yeah, right. That’s a very good corollary.

This year I’ve written probably three major programs which are pushing onehundred pages of code—literate code, with 8.5x11 pages. Two of them arerelated to each other, so it’s more like two and a half major programs. Andabout 150 small programs. Probably more than I did the previous year. So Iprogrammed galore this year on small programs but also, a couple of themwere things that took a month or more to do.

Seibel: And did you expect them to take a month?

Knuth: Well, I expected one of them to take a month. I knew that it wasn’tgoing to be easy but I didn’t know how much richness there was going tobe, so I added more features as I got to using them. I think it is always goingto be true that a person who manages programmers should not expect it tobe predictable.

Seibel: In addition to writing The Art of Computer Programming and TeX,you’re also the inventor of—and advocate for—literate programming, a wayof writing code so it can be more easily read by people. And you wrote WEBand CWEB, tools that implement literate programming languages based onPascal and C.

Knuth: So you say advocate—it’s sort of my shtick to say that this is good.But I also am the kind of guy that’s uncomfortable preaching or trying toconvert someone. I think programming is a lot like religion; people havetheir beliefs. Some people like to force their beliefs on others. Others say,you know, here’s what I think; I can’t prove that this is the best thing, but itsure works for me. Then you hope that other people will try it and come tothe same conclusion. But I don’t like going out and telling people what theyought to believe.

Seibel: Well, maybe you can explain why you like it so much and how itdiffers from illiterate programming.

Knuth: The first rule of writing is to understand your audience—the betteryou know your reader the better you can write, of course. The second rule,for technical writing, is say everything twice in complementary ways so thatthe person who’s reading it has a chance to put the ideas into his or herbrain in ways that reinforce each other.

So in technical writing usually there’s redundancy. Things are said bothformally and informally. Or you give a definition and then you say,“Therefore, such and such is true,” which you can only understand if you’veunderstood the definition.

Or you’ll say, “We define a equals the such-and-such to be the set of allleading elements.” So this informal term, the set of all leading elements, iscomplemented by the mathematical description of how we constructed theset a.

So literate programming is based on this idea that the best way tocommunicate is to say things both informally and formally that are related.And it just provides a natural framework for switching between the naturallanguage, English, and the formal language, C or Lisp or whatever is yourformal language, and putting this together. So that, to me, has to be a winfor documentation.

Now, the other thing is, as I write the program, I don’t have to present it inthe form that the compiler wants to see it. I present it in the form that Ithink is easiest for a reader to understand.