Seibel: Did you ever find, even with that, that you still had people who hadread the thing and then sent you questions that made you think, “Wow,they really missed something here”?

Knuth: Of course. That always happens, but it’s a mistake in my exposition.Let me give you a simple example. In The Art of Computer Programming I’mtalking about the early history of bit-oriented operations and I have thefollowing sentence: “The Manchester Mark 1 computer, built about thesame time as the EDSAC, included not only bitwise and but also or andexclusive or. When Alan Turing wrote its first programming manual in 1950he remarked that bitwise not can be obtained by using exclusive or incombination with a row of ones.”

Now, in my sentence I’m saying, “Alan Turing wrote its first programmingmanual,” meaning the first programming manual for the Manchester Mark 1.But four or five readers independently said, I must have meant “his”: “WhenAlan Turing wrote his first programming manual in 1950”.

Well, actually, he had written other programming manuals, so what I saidwas correct but it was misinterpreted by people. So now I say, “When AlanTuring wrote the first programming manual for the Mark I, in 1950….”

Mathematical things: similarly I’ll get people who miss it. So then I’ll say, youknow, I actually said it correctly, but I know I still have to change it andmake it better.

Seibel: When you publish a literate program, it’s the final form of theprogram, typically. And you are often credited with saying, “Prematureoptimization is the root of all evil.” But by the time you get to the final formit’s not premature—you may have optimized some parts to be very clever.But doesn’t that make it hard to read?

Knuth: No. A good literate program will show its history. A good literateprogram will say, “Here’s the obvious way to do it and then why we don’tfollow that road?”

When you put subtle stuff in your program, literate programming shinesbecause you don’t just have the code that does it but also yourdocumentation. You say, “This is a dirty trick here, it works because—”and then you state very carefully the reasons and the assumptions.

I’ll use dirty tricks for two reasons. One is, if it’s really going to give me aperformance improvement and my application is one that the performanceimprovement is going to be appreciated. Or sometimes I’ll say, “This istricky; I couldn’t resist being tricky today because it’s so cute.” So just forpure pleasure. In any case, I document it; I don’t just put it in there.

Seibel: Would that be more in the prose?

Knuth: It’s in the prose part. I don’t show the code that I’ve taken out. Icould.

Seibel: Is there any facility in CWEB for actually including code that isn’t partof the application, so rather than just document it in the prose, you can say,“Here’s a really dirt-simple version of this function.”

Knuth: You just have the code but you never use it. It comes out in thedocumentation saying this code is never used.

Seibel: So it would just be a fragment that you would never reference?

Knuth: Yeah. Also, I have code in there that I can then invoke from thedebugger. I can say, “Call such-and-such with such-and-such parameters.”The subroutine is never actually called in the program itself, but it’s there inthe documentation. So I can stop a program in the middle and I can call thissubroutine and it’ll take a look and see how it’s doing, see how big thingshave gotten.

Seibel: So by the same token you could write, “Section one—here’s a naiveimplementation of this algorithm; section two—here’s a slightly souped-upversion of section one; and section three, here’s the one we actually usewhich you would never understand if you hadn’t read the first twosections.”

Knuth: Exactly. I have some programs on the Web that solve the 15 puzzle.And I go through three different versions. And I say, “Read version one or you’llnever understand version two. And read version two or you’ll neverunderstand version three.”

I write a whole variety of different kinds of programs. Sometimes I’ll write aprogram where I couldn’t care less about efficiency—I just want to get theanswer. I’ll use brute force, something that I’m guaranteed I won’t have tothink—there’ll be no subtlety at all so I won’t be outsmarting myself. ThereI’m not doing any premature optimization.

Then I can change that into something else and see if I get something thatagrees with my brute-force way. Then I can scale up the program and go tolarger cases. Most programs stop at that stage because you’re not going toexecute the code a trillion times. When I’m doing an illustration for The Artof Computer Programming I may change that illustration several times and thepeople who translate my book might have to redo the program, but itdoesn’t matter that I drew the illustration by a very slow method becauseI’ve only got to generate that file once and then it goes off to the publisherand gets printed in a book.

But right now I’m working on combinatorial algorithms, which are, bydefinition, humongous-size problems. So in order to have interestingexamples in my book I’ve got to write programs that solve problems thatreaders will say, “Oh, yeah, I couldn’t have done that just by simplemethods, so I need to learn something about the art of programming or it’lltake 100 years to solve this problem by the brute-force method.”

Combinatorial algorithms are fascinating because one good idea can saveyou ten orders of magnitude in running time. But I don’t sneer at ideas thatsave you twenty percent when you’re doing it a trillion times. Because if youcan save a hundred nanoseconds in a loop that’s being done a trillion times,I think you’re saving a day. If the code is going to be used a lot it can reallypay off so you’ve got to go to subtle tricks that aren’t easy to understand.

About a year ago I saw a review in Computing Reviews—the guy wasreviewing a book; the title was Programming Tricks or something like this.And the thrust of the review was, “If I ever caught any of the programmersworking for me using any of these tricks, I would fire them.” And sonaturally I went out and looked at the book because I thought, “This is abook I want to see and learn from. Unfortunately, the tricks weren’t actuallythat good.”

Seibel: Were they really firing offenses?

Knuth: They were very weak, actually. It wasn’t presented systematicallyand everything, but I thought they were pretty obvious. It was a differentculture entirely. But the guy who said he was going to fire people, he wantsprogramming to be something where everything is done in an inefficient waybecause it’s supposed to fit into his idea of orderliness. He doesn’t care ifthe program is good or not—as far as its speed and performance—he caresabout that it satisfies other criteria, like any bloke can be able to maintain it.Well, people have lots of other funny ideas.

People have this strange idea that we want to write our programs as worldsunto themselves so that everybody else can just set up a few parametersand our program will do it for them. So there’ll be a few programmers inthe world who write the libraries, and then there are people who write theuser manuals for these libraries, and then there are people who apply theselibraries and that’s it.

The problem is that coding isn’t fun if all you can do is call things out of alibrary, if you can’t write the library yourself. If the job of coding is just to befinding the right combination of parameters, that does fairly obvious things,then who’d want to go into that as a career?

There’s this overemphasis on reusable software where you never get toopen up the box and see what’s inside the box. It’s nice to have these blackboxes but, almost always, if you can look inside the box you can improve itand make it work better once you know what’s inside the box. Insteadpeople make these closed wrappers around everything and present theclosure to the programmers of the world, and the programmers of theworld aren’t allowed to diddle with that. All they’re able to do is assemblethe parts. And so you remember that when you call this subroutine you putx0, y0, x1, y1 but when you call this subroutine it’s x0, x1, y0, y1. You getthat right, and that’s your job.