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

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

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

You can write your code bottom-up and make subroutines that give you bigger and bigger things and your confidence builds because now you can do more things. Other people write top-down; they start out and say, “Well, I have this problem to solve, so first I’ll do this and then I’ll do this.”

When I write a literate program I can choose between these as I like. And almost always the way my final program comes out is in the order in which I actually thought of the things myself. So I’ll start out and I’ll say, “I have this problem to solve, so first I’m going to have to solve this and then I’m going to have to solve that.”

But then I say, “Now let’s start building some tools bottom-up.” We have the goal in mind but we build a few bottom-up tools and then we’ll go back and do a little top-down. But in what order we do this is, first I write about what I thought about the first day I had to work on this problem. And then, the next chapter would be the thing I decided to tackle next.

And I start to tackle the thing that’s most worrying to me but that I’m also ready to solve at the moment. Instead of postponing something ’til an evil day, if I’m ready to do it now, I get that out of the way. But it’s a different order—it’s neither top-down nor bottom-up. It’s psychologically, “What do I find is the thing that’s going to make me most satisfied to get done next and I’m ready to do it?” It doesn’t have too many unknowns in it. So the freedom to put the program into that human-understandable order is very important to me.

Now, why hasn’t this spread over the whole world and why isn’t everybody doing it? I’m not sure who it was who hit the nail on the head—I think it was Jon Bentley. Simplified it is like this: only two percent of the world’s population is born to be super programmers. And only two percent of the population is born to be super writers. And Knuth is expecting everybody to be both.

I don’t think we’re going to increase the total number of programmers in the world to more than two percent—I mean programmers who really resonate with the machine and that’s their bread and butter that they’ve been born to do. But now that people are blogging, I’ve seen a great rise in the average ability of ordinary everybody to express themselves. So the second part of that that argument isn’t so strong anymore.

I tried it only a limited amount at Stanford. I worked with a group of undergraduates. They would write their programs on a summer project and I introduced them to this idea of literate programming. There were only seven of them working with me that summer. And six of them loved it to the point that they’re still using it today. The seventh one hated it. His idea of writing a literate program was to take an ordinary program and put a wrapper around it and say, “This is module one,” and so on. Of course, Stanford admits people who are good writers, so this isn’t a random sample.

Seibel:Have you ever written a literate program where you dramatically reorganized it into a different order for explication? It’s hard for me to imagine that stream of consciousness is always the best organizing principle.

Knuth:It just hardly ever happened. I can’t remember going back and really changing the order of the chapters. It just always seemed like there was almost only one choice what to attack next. I can’t explain it exactly, but it just seemed that one would segue into the next.

Seibel:Do you write literate code for programs that no one but you will ever see?

Knuth:Exactly. This is what literate programming is so great for—I can talk to myself. I can read my program a year later and know exactly what I was thinking.

Seibel:Does that always work?

Knuth:Well, it’s often a lot harder to understand a year later than before. But compare that to what I had without it. It doesn’t make the complicated thing trivial, but it’s just way better than any other method I know.

I just printed out a small subset of a large collections of subroutines that are all written in C that are pretty much state of the art for manipulating BDDs—Boolean decision diagrams. This is the opposite of CWEB—this is what almost everyone in the world does when they’re developing packages now. They do it by means of fairly disciplined commenting conventions that are understood by a large community. And the code is not real difficult to understand because it’s separated out into a logical form and you’ve got these header files and I can see the data structures and there are comments on each part of the data structure explaining what it’s doing. So this is another style of programming that works.

Yet I can’t help but think that it’s considerably below what can be achieved with literate programming. Because of lots of intangible things that I can’t prove. The most convincing to me was that I believe that I’ve written some programs that I could not have written at all without literate programming. For example, the MMIXsimulator would have been such an intellectual challenge that if I had to do it in the conventional style, I don’t think I ever would have finished it. Just separating it out into subroutines wasn’t enough to simplify it to make it intellectually manageable.

This is a simulator that takes an extremely general specification of a computer: what functional units it has, how many instructions can execute at a time, the caching strategies, how the bus works, how the output works, how are you doing branch prediction, and how you maintain the pipeline.

So you can imagine a computer that would have six division units and a pipeline of certain stages and this will simulate it. Would you be able to calculate prime numbers faster if you had this machine? You don’t have to build the machine.

I’m not saying it’s impossible to take that program and put it into subroutines, but I would never have finished it that way. And also it’s only 170 pages and it is possible to understand it—I’m not the only person in the world who understands it.

Seibel:I read your literate reimplementation of the game Adventure and noticed that it seemed somewhat monolithic. It seemed like the literate style, because it lets you interpolate things, draws you away from breaking things down into subroutines.

Knuth:This is true. Instead of calling a subroutine, it’s like inline subroutines all the way through. The idea of a subroutine is there but it’s not in your final program as a subroutine. It’s more like a macro in some ways. But the thing is, at the conceptual level, the subroutine-calling mechanism isn’t necessary if you have some other way to do it in the language you’re using.

In Adventure I don’t think I actually removed subroutines from Don Woods’s Fortran program—I was taking his Fortran program and putting it into English and C. But it’s true that when you look at my code for TeX, the number of subroutines that you’re in, on the subroutine stack, might be 4 or 5 whereas a program written by somebody else, without literate programming, it might be 50 or 100.