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

Knuth:Well, the proof of Fermat’s Last Theorem was one of those. It’s one of the most famous mathematical papers. And it happens all the time that I see books that I know wouldn’t have been written if the authors had had to go through channels the way they used to. It’s again a little bit of the black-box thing.

It used to be, you would have to type something up and that would go into a compositor and it would come back in galley proofs, and so on. You’re going through all kinds of levels of people who aren’t mathematicians and then coming out with the product at the end. So you don’t dare do anything that would confuse any of the people in that line.

But if you can see yourself what it’s going to look like, and you can make up a notation that isn’t in somebody’s style sheet because it just happens to be the right one for your problem, then you’re encouraged to do a much better job.

So this brings me great satisfaction all the time when I know that people have been able to cut through this and their creativity goes directly to the reader.

Seibel:Do you feel like programmers and computer scientists are aware enough of the history of our field? It is, after all, a pretty short history.

Knuth:There aren’t too many that are scholars. Even when I started writing my books in 1963, I didn’t think people knew what had happened in 1959. I was reading in American Scientist last week about people who had rediscovered an algorithm that Boyer and Moore had discovered in 1980. It happens all the time that people don’t realize the glorious history that we have. The idea that people knew a thing or two in the ’70s is strange to a lot of young programmers.

It’s inevitable that in such a complicated field that people will be missing stuff. Hopefully with things like Wikipedia, achievements don’t get forgotten the way they were before. But I wish I could also instill in more people the love that I have for reading original sources. Not just knowing that so-and-so gets credit for doing something, but looking back and seeing what that person said in his own words. I think it’s a tremendous way to improve your own skills.

It’s very important to be able to get inside of somebody else’s way of thinking, to decode their vocabulary, their notation. If you can understand something about the way they thought and the way they made a discovery, then that helps you make your own discoveries. I often read source materials of what brilliant people have said about this stuff in the past. It’ll be expressed in unusual ways by today’s conventions, but it’s worth it to me to penetrate their notation and to try to get into their idea.

For example I spent a good deal of time trying to look at Babylonian manuscripts of how they described algorithms 4,000 years ago, and what did they think about? Did they have while loops and stuff like this? How would they describe it? And to me this was very worthwhile for understanding about how the brain works, but also about how they discovered things.

A couple of years ago I found an old Sanskrit document from the 13th century that was about combinatorial math. Almost nobody the author knew would have had the foggiest idea what he was talking about. But I found a translation of this document and it was speaking to me. I had done similar kinds of thinking when I was beginning in computer programming.

And so to me reading source materials is great enrichment for my own life and creativity.

I was unable to pass that on to any of my students. There are people alive now in computer science who are doing this well—a few. But I could count on the fingers of one hand the people who love source materials the way I do.

I’ve got lots of collections of source code. I have compilers, the Digitek compilers from the 1960s were written in a very interesting way. They had their own language and they used identifiers that were 30 characters long but very descriptive, and their compilers ran circles around the competition at the time—this company made the state-of-the-art compilers of 1963 or ’64.

And I’ve got Dijkstra’s source code for the THE operating system. I haven’t read that. I’ve just skimmed it so far but I collected it because I’m sure it would be interesting to read if I had time.

One time I broke my arm—fell off a bike—and I had a month where I couldn’t do anything much, so I read source code that I had heard had some clever ideas in it that hadn’t been documented. I think those were all extremely important experiences for me.

Seibel:How do you tackle reading source code? Even reading something in a programming language you already know is a tricky problem.

Knuth:But it’s really worth it for what it builds in your brain. So how do I do it? There was a machine called the Bunker Ramo 300 and somebody told me that the Fortran compiler for this machine was really amazingly fast, but nobody had any idea why it worked. I got a copy of the source-code listing for it. I didn’t have a manual for the machine, so I wasn’t even sure what the machine language was.

But I took it as an interesting challenge. I could figure out BEGINand then I would start to decode. The operation codes had some two-letter mnemonics and so I could start to figure out “This probably was a load instruction, this probably was a branch.” And I knew it was a Fortran compiler, so at some point it looked at column seven of a card, and that was where it would tell if it was a comment or not.

After three hours I had figured out a little bit about the machine. Then I found these big, branching tables. So it was a puzzle and I kept just making little charts like I’m working at a security agency trying to decode a secret code. But I knew it worked and I knew it was a Fortran compiler—it wasn’t encrypted in the sense that it was intentionally obscure; it was only in code because I hadn’t gotten the manual for the machine.

Eventually I was able to figure out why this compiler was so fast. Unfortunately it wasn’t because the algorithms were brilliant; it was just because they had used unstructured programming and hand optimized the code to the hilt.

It was just basically the way you solve some kind of an unknown puzzle—make tables and charts and get a little more information here and make a hypothesis. In general when I’m reading a technical paper, it’s the same challenge. I’m trying to get into the author’s mind, trying to figure out what the concept is. The more you learn to read other people’s stuff, the more able you are to invent your own in the future, it seems to me.

We ought to publish code. The Lions Book is available. And Bill Atkinson’s programs are now publicly available thanks to Apple, and it won’t be too long before we’ll be able to read that. That’s well-documented code with lots of pioneering graphics algorithms in it.

Seibel:Certainly with open source there’s a lot more code out there to read than there use to be.

Knuth:Yeah, that’s right. But the more varieties of different kinds of notations are still useful—don’t only read the people who code like you.

The Art of Computer Programming , Donald Knuth (Addison-Wesley, 1997)

Beautiful Code: Leading Programmers Explain How They Think , Andy Oram, Greg Wilson (eds.) (O’Reilly, 2007)

Byte , Vol. 6, No. 8, “Smalltalk issue,” August 1981

Code Complete , Steve McConnell (Microsoft Press, 1993)

Compiling with Continuations , Andrew W. Appel (Cambridge University Press, 1992)

The Design and Analysis of Computer Algorithms , Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman (Addison-Wesley, 1974)