You can write your code bottom-up and make subroutines that give youbigger and bigger things and your confidence builds because now you can domore things. Other people write top-down; they start out and say, “Well, Ihave 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. Andalmost always the way my final program comes out is in the order in which Iactually thought of the things myself. So I’ll start out and I’ll say, “I have thisproblem to solve, so first I’m going to have to solve this and then I’m goingto have to solve that.”

But then I say, “Now let’s start building some tools bottom-up.” We havethe goal in mind but we build a few bottom-up tools and then we’ll go backand do a little top-down. But in what order we do this is, first I write aboutwhat 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 alsoready to solve at the moment. Instead of postponing something ’til an evilday, if I’m ready to do it now, I get that out of the way. But it’s a differentorder—it’s neither top-down nor bottom-up. It’s psychologically, “What doI find is the thing that’s going to make me most satisfied to get done nextand I’m ready to do it?” It doesn’t have too many unknowns in it. So thefreedom to put the program into that human-understandable order is veryimportant to me.

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

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

I tried it only a limited amount at Stanford. I worked with a group ofundergraduates. They would write their programs on a summer project andI introduced them to this idea of literate programming. There were onlyseven of them working with me that summer. And six of them loved it tothe point that they’re still using it today. The seventh one hated it. His ideaof writing a literate program was to take an ordinary program and put awrapper 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 dramaticallyreorganized it into a different order for explication? It’s hard for me toimagine that stream of consciousness is always the best organizing principle.

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

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

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

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 complicatedthing 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 areall written in C that are pretty much state of the art for manipulatingBDDs—Boolean decision diagrams. This is the opposite of CWEB—this iswhat almost everyone in the world does when they’re developing packagesnow. They do it by means of fairly disciplined commenting conventions thatare understood by a large community. And the code is not real difficult tounderstand because it’s separated out into a logical form and you’ve gotthese header files and I can see the data structures and there are commentson each part of the data structure explaining what it’s doing. So this isanother style of programming that works.

Yet I can’t help but think that it’s considerably below what can be achievedwith literate programming. Because of lots of intangible things that I can’tprove. The most convincing to me was that I believe that I’ve written someprograms that I could not have written at all without literate programming.For example, the MMIX simulator would have been such an intellectualchallenge that if I had to do it in the conventional style, I don’t think I everwould have finished it. Just separating it out into subroutines wasn’t enoughto simplify it to make it intellectually manageable.

This is a simulator that takes an extremely general specification of acomputer: what functional units it has, how many instructions can executeat 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 apipeline of certain stages and this will simulate it. Would you be able tocalculate prime numbers faster if you had this machine? You don’t have tobuild the machine.

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

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

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

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

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

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

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