Peter Seibel - Coders at Work - Reflections on the craft of programming

What I try to work on is units that correspond to the way I have it in my head, rather than the way a logician might want it to be in some formal system. My programs are supposed to match my intuition more than somebody else’s rigid framework.

Of course, eventually it has to go into a computer, which is rigid, which has its precise rules of understanding. But to me the idea of the right kind of a program is something that matches the way I think as closely as possible rather than something that matches the machine as closely as possible. I have to find the way to do the conversion, but my source text tries to stay closer to my brain than to the machine.

I also believe that literate programming is a powerful style of documentation that can be used to communicate across groups of people. I had many people who understood the code for TeX well enough to construct scenarios where it would fail. I think more people, at one point in their life, understood that program than any other program of its size.

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 CWEBfor 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?