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

There are lots of other things that look like they’re important changes butto 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 languagesthat we have. There are many different flavors that appeal to differentpersonality types. Some people are more logical than I am, for example.They really like to have lots of parentheses, and things matching up andsaying 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 notthe way I think. But that’s the way other people think and there’s no onebest way to think.

To me one of the most important revolutions in programming languageswas the use of pointers in the C language. When you have nontrivial datastructures, you often need one part of the structure to point to anotherpart, and people played around with different ways to put that into a higherlevellanguage. Tony Hoare, for example, had a pretty nice clean system butthe thing that the C language added—which at first I thought was a bigmistake and then it turned out I loved it—was that when x is a pointer andthen you say, x + 1, that doesn’t mean one more byte after x but it meansone more node after x, depending on what x points to: if it points to a bignode, x + 1 jumps by a large amount; if x points to a small thing, x + 1 justmoves a little. That, to me, is one of the most amazing improvements innotation.

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

Knuth: Pointers have gone out of favor to the point now where I had toflame about it because on my 64-bit computer that I have here, if I reallycare about using the capability of my machine I find that I’d better not usepointers because I have a machine that has 64-bit registers but it only has 2gigabytes 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 thesize of my data structure. Worse, it goes into the cache and half of mycache 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 insteadof pointers. I make complicated macros so that it looks like I’m usingpointers, but I’m not really. In a way it’s a small thing and it’s going out offashion. 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 toThompson 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 programmingthat 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 theyhad 200 or 300 combinations of programming language and operatingsystem and computer, so I wanted to make it easy to adapt my code toanybody’s system. So we came up with the solution that I would write amaster program that worked at Stanford and then there was this add-oncalled 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 ofchanges. Each change starts out with a few lines of code. You match untilyou find the first line in the master file that agrees with the first line of yourchange. When you get to the end of the part of the change that wassupposed 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 byno lines. As soon as you get a match, you stick in the twelve that youchanged. Then you go onto the next one.” You’ve got to write the changesin order—it doesn’t do anything intelligent for matching; it just says, “Gountil you find the first line of the next change that has to match some line inthe master file.”

It’s a system that only takes an hour to program and it’s good enough forthe purpose. Then all the tools that we have for literate programming, theweave 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 thesehundreds of people around the world had their change files—maybe theirsix lines that were supposed to match mine no longer matched, so theymight 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—thebug fix would also apply to their program. This solved the problem verysimply and it worked. Anybody could figure it out and do it.

The extreme example of this was when TeX was adapted to Unicode. Theyhad a change file maybe 10 times as long as the master program. In otherwords, they changed from an 8-bit program to a 16-bit program but insteadof going through and redoing my master program, they were so into changefiles that they just wrote their whole draft of what they called Omega aschange files, as a million lines of change files to TeX’s 20,000 lines of codeor something. So that’s the extreme.

But now I use change files all the time because I’m writing programs formyself that I’m using writing my book—I’ve got lots of problems that I wantto solve and I want to experiment with different versions. Like yesterday Iwanted to find out how big a Boolean circuit is for multiplication of n-bitnumbers. I have a program that takes any Boolean function and finds outhow big its BDD is. So I’ve got a program that takes any Boolean functionand computes its BDD.

In my original program you input the truth table of the function online—itsays, “Give me a truth table,” and I type in a hexadecimal number, because Ihad a lot of small functions that I’m using as examples. But it only works forsmall functions, the ones that I want to type in the truth table.Then I’ve got a big function like, “Multiply all pairs of 8-bit numbers.” This isa function of 16 variables—there are 8 bits in x and 8 bits in y. So I write alittle change file that takes out this interactive dialog and replaces it with aprogram that makes a truth table for multiplication.

Then I changed that by saying, “Let’s read the bits from right to left insteadof from left to right, which gives you a different BDD.” Or, “Let me try allBoolean functions of six variables and I’ll run through them all and find outwhich one has the largest BDD.” But all of these are customizations of myoriginal thing.

I’ll have maybe 15 variants of that program that are easily understood. Thiswas an unexpected spin-off from literate programming because of our needfor sending out master files to a lot of people that were changing it for theirown system; I’m now using it in a completely different way.

Seibel: It seems sort of obvious why that would be useful for you in thekind of work you’re doing, where you want to do a lot of variations ondifferent themes.

Knuth: Yeah, I’m writing a book.

Seibel: Do you think this mechanism could be more broadly applicable?

Knuth: I have no idea. I’m not sure how it would work if I was in a team of50 people. But I hope that the idea of an individual programmer writingprograms in order to learn something is not a dying breed.