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

Well, I’m seeing the same thing now that I’m writing about BDD structures. At the moment there are three or four packages of subroutines that work with BDDs but the thrust of what I’m writing now for The Art of Computer Programming is that you too can program simple versions of BDDs for lots of applications and it’ll go very far. You can use them for lots of different kinds of problems where you don’t need all the bells and whistles of these other packages and these things you can do are easy to understand and easy to put into programs you’re writing yourself.

Earlier this year I finished my section on bitwise tricks and techniques and these are things that have been a black art in the hacker community for years. I decided it’s time to say that there’s a theory of these things that you can understand the ideas, how they fit together. You can use them yourself with confidence. And you can build on things and do amazing things that last year you didn’t know how to do well at all. It went through the underground until now; it’s something that we might as well teach to people—something that deserves to be common knowledge.

I write a lot of programs and I can’t claim to be typical but I can claim that I get a lot of them working for a large variety of things and I would find it harder if I had to spend all my time learning how to use somebody else’s routines. It’s much easier for me to learn a few basic concepts and then reuse code by text-editing the code that previously worked.

Seibel:How has the way you think about programming changed from those earliest days to now?

Knuth:We already talked about literate programming—that’s a radical departure, that I’m viewing myself as an expositor rather than trying to just put together the right instructions. Dijkstra came out with that same evolution. In the end his programs were even more literate than mine in the sense that they didn’t even go into the machine. They were only literate.

And he was one of the people largely responsible for structured programming, where we saw patterns that we could use to scale up our program so that we could make larger programs and still keep our head straight. You write a program that’s ten times as big but you don’t have to lose ten times as much sleep over it because you have tools that allow you to put things together reliably in a larger system. That was definitely different.

So that’s one important aspect, the idea of the abstractions that we have to understand, the abstractions that allow us to deal with large systems and still be pretty confident that we’re in control and we know what we’re doing, even though they’re a mind-bogglingly complex things.

There are lots of other things that look like they’re important changes but to me they don’t seem to make that much difference. These are the surface, the different type of syntactic sugar and the different dialects of languages that we have. There are many different flavors that appeal to different personality types. Some people are more logical than I am, for example. They really like to have lots of parentheses, and things matching up and saying that, “I’m now going to start something,” and then at the end you say, “I’m now going to finish it.” And that’s not as appealing to me. That’s not the way I think. But that’s the way other people think and there’s no one best way to think.

To me one of the most important revolutions in programming languages was the use of pointers in the C language. When you have nontrivial data structures, you often need one part of the structure to point to another part, and people played around with different ways to put that into a higherlevel language. Tony Hoare, for example, had a pretty nice clean system but the thing that the C language added—which at first I thought was a big mistake and then it turned out I loved it—was that when xis a pointer and then you say, x + 1, that doesn’t mean one more byte after xbut it means one more node after x, depending on what xpoints to: if it points to a big node, x + 1jumps by a large amount; if xpoints to a small thing, x + 1just moves a little. That, to me, is one of the most amazing improvements in notation.

Seibel:So that’s certainly powerful compared to what preceded it. But since then, a lot of people have decided that having raw pointers to memory is pretty dangerous and that they’d rather have references that behave a lot like pointers but without some of the dangers.

Knuth:Pointers have gone out of favor to the point now where I had to flame about it because on my 64-bit computer that I have here, if I really care about using the capability of my machine I find that I’d better not use pointers because I have a machine that has 64-bit registers but it only has 2 gigabytes of RAM. So a pointer never has more than 32 significant bits to it. But every time I use a pointer it’s costing me 64 bits and that doubles the size of my data structure. Worse, it goes into the cache and half of my cache is gone and that costs cash—cache is expensive.

So if I’m really trying to push the envelope now, I have to use arrays instead of pointers. I make complicated macros so that it looks like I’m using pointers, but I’m not really. In a way it’s a small thing and it’s going out of fashion. But to me it was an important idea in notation at the lower levels; when I’m working and debugging and so on I’m still very grateful to Thompson and Ritchie. I don’t know who came up with that particular one.

Seibel:Are there any other important parts of your programming toolkit?

Knuth:Change files are something that I’ve got with literate programming that I don’t know of corresponding tools in any other programmers’ toolkits, so let me explain them to you.

I had written TeX and Metafont and people started asking for it. And they had 200 or 300 combinations of programming language and operating system and computer, so I wanted to make it easy to adapt my code to anybody’s system. So we came up with the solution that I would write a master program that worked at Stanford and then there was this add-on called a change file which could customize it to anybody else’s machine.

A change file is a very simple thing. It consists of a bunch of little blobs of changes. Each change starts out with a few lines of code. You match until you find the first line in the master file that agrees with the first line of your change. When you get to the end of the part of the change that was supposed to match the master file, then comes the part which says, “Replace that by these lines instead.”

Maybe the change says, “Replace these six lines by these twelve lines. Or by no lines. As soon as you get a match, you stick in the twelve that you changed. Then you go onto the next one.” You’ve got to write the changes in order—it doesn’t do anything intelligent for matching; it just says, “Go until you find the first line of the next change that has to match some line in the master file.”

It’s a system that only takes an hour to program and it’s good enough for the purpose. Then all the tools that we have for literate programming, the weave and tangle programs, will take the master file and the change file.

So every so often I’d have to release a new master program. All these hundreds of people around the world had their change files—maybe their six lines that were supposed to match mine no longer matched, so they might have to make some changes. But they wouldn’t have to do very much. Every time I would correct a bug it would almost automatically work—the bug fix would also apply to their program. This solved the problem very simply and it worked. Anybody could figure it out and do it.