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.
Seibeclass="underline" 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.
Seibeclass="underline" 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.
Seibeclass="underline" 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 MMIX simulator 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.
Seibeclass="underline" 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.
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.
Seibeclass="underline" 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.”