Seibel: Did you ever find, even with that, that you still had people who had read 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’m talking about the early history of bit-oriented operations and I have the following sentence: “The Manchester Mark 1 computer, built about the same time as the EDSAC, included not only bitwise and but also or and exclusive or. When Alan Turing wrote its first programming manual in 1950 he remarked that bitwise not can be obtained by using exclusive or in combination with a row of ones.”

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

Well, actually, he had written other programming manuals, so what I said was correct but it was misinterpreted by people. So now I say, “When Alan Turing 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, you know, I actually said it correctly, but I know I still have to change it and make it better.

Seibel: When you publish a literate program, it’s the final form of the program, typically. And you are often credited with saying, “Premature optimization is the root of all evil.” But by the time you get to the final form it’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 literate program will say, “Here’s the obvious way to do it and then why we don’t follow that road?”

When you put subtle stuff in your program, literate programming shines because you don’t just have the code that does it but also your documentation. 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 a performance improvement and my application is one that the performance improvement is going to be appreciated. Or sometimes I’ll say, “This is tricky; I couldn’t resist being tricky today because it’s so cute.” So just for pure 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. I could.

Seibel: Is there any facility in CWEB for actually including code that isn’t part of 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 the documentation 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 the debugger. 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 in the documentation. So I can stop a program in the middle and I can call this subroutine and it’ll take a look and see how it’s doing, see how big things have gotten.

Seibel: So by the same token you could write, “Section one—here’s a naive implementation of this algorithm; section two—here’s a slightly souped-up version of section one; and section three, here’s the one we actually use which you would never understand if you hadn’t read the first two sections.”

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’ll never understand version two. And read version two or you’ll never understand version three.”

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

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

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

Combinatorial algorithms are fascinating because one good idea can save you ten orders of magnitude in running time. But I don’t sneer at ideas that save you twenty percent when you’re doing it a trillion times. Because if you can 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 really pay 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 was reviewing 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 programmers working for me using any of these tricks, I would fire them.” And so naturally I went out and looked at the book because I thought, “This is a book I want to see and learn from. Unfortunately, the tricks weren’t actually that good.”

Seibel: Were they really firing offenses?

Knuth: They were very weak, actually. It wasn’t presented systematically and everything, but I thought they were pretty obvious. It was a different culture entirely. But the guy who said he was going to fire people, he wants programming to be something where everything is done in an inefficient way because it’s supposed to fit into his idea of orderliness. He doesn’t care if the program is good or not—as far as its speed and performance—he cares about 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 worlds unto themselves so that everybody else can just set up a few parameters and our program will do it for them. So there’ll be a few programmers in the world who write the libraries, and then there are people who write the user manuals for these libraries, and then there are people who apply these libraries and that’s it.

The problem is that coding isn’t fun if all you can do is call things out of a library, if you can’t write the library yourself. If the job of coding is just to be finding 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 to open up the box and see what’s inside the box. It’s nice to have these black boxes but, almost always, if you can look inside the box you can improve it and make it work better once you know what’s inside the box. Instead people make these closed wrappers around everything and present the closure to the programmers of the world, and the programmers of the world aren’t allowed to diddle with that. All they’re able to do is assemble the parts. And so you remember that when you call this subroutine you put x0, y0, x1, y1 but when you call this subroutine it’s x0, x1, y0, y1. You get that right, and that’s your job.