Seibel Peter. Coders at Work

Подождите немного. Документ загружается.

Donald Knuth

585

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 higher-

level 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

x is a pointer and

then you say,

x + 1, that doesn’t mean one more byte after x but it means

one more node after

x, depending on what x points to: if it points to a big

node,

x + 1 jumps by a large amount; if x points to a small thing, x + 1 just

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

Donald Knuth

586

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

Donald Knuth

587

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.

The extreme example of this was when TeX was adapted to Unicode. They

had a change file maybe 10 times as long as the master program. In other

words, they changed from an 8-bit program to a 16-bit program but instead

of going through and redoing my master program, they were so into change

files that they just wrote their whole draft of what they called Omega as

change files, as a million lines of change files to TeX’s 20,000 lines of code

or something. So that’s the extreme.

But now I use change files all the time because I’m writing programs for

myself that I’m using writing my book—I’ve got lots of problems that I want

to solve and I want to experiment with different versions. Like yesterday I

wanted to find out how big a Boolean circuit is for multiplication of n-bit

numbers. I have a program that takes any Boolean function and finds out

how big its BDD is. So I’ve got a program that takes any Boolean function

and computes its BDD.

In my original program you input the truth table of the function online—it

says, “Give me a truth table,” and I type in a hexadecimal number, because I

had a lot of small functions that I’m using as examples. But it only works for

small 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 is

a function of 16 variables—there are 8 bits in x and 8 bits in y. So I write a

Donald Knuth

588

little change file that takes out this interactive dialog and replaces it with a

program that makes a truth table for multiplication.

Then I changed that by saying, “Let’s read the bits from right to left instead

of from left to right, which gives you a different BDD.” Or, “Let me try all

Boolean functions of six variables and I’ll run through them all and find out

which one has the largest BDD.” But all of these are customizations of my

original thing.

I’ll have maybe 15 variants of that program that are easily understood. This

was an unexpected spin-off from literate programming because of our need

for sending out master files to a lot of people that were changing it for their

own 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 the

kind of work you’re doing, where you want to do a lot of variations on

different 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 of

50 people. But I hope that the idea of an individual programmer writing

programs in order to learn something is not a dying breed.

Seibel: In your earliest days you were writing machine code; then you

found structured programming, which provided literally a structure for

organizing programs. And then you invented literate programming, which

gave you another way to structure programs. Since the invention of literate

programming, has there been anything else that’s as dramatically changed

the way you think about programming?

Knuth: I’ve got better debugging tools for literate programming; that’s

basically all.

Seibel: OK, let’s talk about debugging. What better tools do you have

now?

Donald Knuth

589

Knuth: It turned out that the inventors of the GNU debugger realized that

you could have preprocessors writing programs. So you can correlate the

low-level stuff to a high-level source in a completely different language. So

I’m writing in

CWEB but I still never have to look at the lower-level things

because it’ll flash my

CWEB source as I’m stepping through the program.

Seibel: So that’s a facility built into GDB which

CWEB takes advantage of?

Knuth: And was built into GDB because it was built into C to have

__LINE__ directives. We had to work to make use of the __LINE__directives,

but it works beautifully. The computer is sitting there with a binary

instruction but GDB knows that this came from something in my WEB

source file even though WEB came 10, 20 years after C. So it was a very

good, very forward-looking part of their design to make that work.

Seibel: So you use GDB. What other debugging techniques do you use?

Knuth: I’ll add a lot of code that will check to see if my data structures,

with all their redundancies, are properly done. This sanity checking might

slow the whole thing down by a factor of 100 if I turn it on.

For instance, I had a complicated data structure that involves reference

counts. So I’m writing some pretty complicated programs, and getting these

reference counts correct is mystifying. Every once in a while I have to

increase the reference count or decrease the reference count. But when a

pointer is in a register or is a parameter to a subroutine, does that count as

a reference in the data structure or not? So I’ve got the sanity check written

that goes through the millions of counts seeing how many references are

really made and are the numbers correct? Then I’ll do a little computation

and check the whole thing. That way errors will be detected billions of steps

before they would surface in a crash.

There was a program that does multiplication in a new way, so I tried it

exhaustively. I made 256 numbers and I multiplied each of them by each

other one, but after each one I would do a sanity check. I multiply 2 by 3—

fails! So I fixed that. And then something else. Finally I got it to where all

256 by 256 were working and getting the right answer.

Donald Knuth

590

So that’s an important debugging technique for me. Maybe ten percent of

the code is devoted to something that I don’t need except when I’m

debugging. And the sanity-check code also documents the data structure.

I’ll also write something that gives a nice symbolic form of a data structure

so I don’t have to decode a whole bunch of binary things. Then, if necessary,

I can print out a data structure in some decent structured form or I can

dump it out in a file and I can write another program that analyzes it to find

out what’s going wrong.

Seibel: Related to invariants and various kinds of assertions, folks like

Dijkstra would argue that we’ve got to put very formal assertions at every

step of our program so that we can then prove our programs correct. I’ve

read where you’ve talked about wanting to prove your programs “informally

correct;” what’s your take on the idea that we should go beyond that and

formally prove things correct?

Knuth: On one hand you have this impossibility of ever having something

proved. Somebody will say they have a program that’s verified and it’s only

verified because it met its specifications according to some verifier. But the

verifier might have a bug in it. The specifications might have bugs in them. So

you never know that the program is correct. You have more reason to

believe it, but you never get to the end of the loop. It’s theoretically

impossible.

The very first paper by Tony Hoare about formal proof, “Proof of a

Program: FIND,” was a great achievement and advanced the state of the art.

But there were two or three bugs in that proof. It hadn’t occurred to them

that you had to verify that subscripts lie in-bounds or something like this.

There’s always a chance for gaps. Still, he had verified it much more than

anybody else had at that point.

Now, the program that I did yesterday—I have no idea how I would state all

of the assertions that are there. I would never get done because I wouldn’t

have any more confidence in my assertions than I would in the program.

Or TeX, for example, is a formal mess. It was intended to be for human use,

not for computer use. To define what it means for TeX to be correct

Donald Knuth

591

would be incomprehensible. Some methods for formal semantics are so

complicated that nobody can comprehend the definition of correctness.

Seibel: When you were working on TeX you wrote a really horrendous

torture test of the program.

Knuth: Right.

Seibel: How do you get in the frame of mind to do that? Programmers

often tend to want to protect their baby, and so they don’t test as hard as

they could.

Knuth: Well, I’ve been a nitpicker all my life. So if I can get my kicks out of

finding errors then I just have to make sure that I forget that I was the

author of the program. I try to imagine that somebody else was the author.

But otherwise it’s fairly easy for me to get into attack mode. I don’t know

why.

For example, some of the best work I did for Burroughs Corporation was

to debug their hardware designs. Their engineers would show me the specs

for their computer and I would look at it and I would try to construct

examples where they would be off by 1 or something. I got more than 200

bugs out of their B-5000–series machines before they went into production,

although it had passed the simulators.

Seibel: So essentially you were inventing programs that were correct

according to the semantics of the language but the machine would then

execute incorrectly?

Knuth: Right. Certainly if their floating point isn’t calculating the right

product of two numbers, I would try to find examples of numbers where

the floating point didn’t work. But also there were cases where they were

implementing a stack in hardware and they had cases where registers would

be empty or not at the top of the stack and I would find scenarios where

their logic would get screwed up.

Seibel: Did you have a systematic way of doing that? How did you find

them?

Donald Knuth

592

Knuth: Am I just a mean guy? I don’t know. But if I’m trying to prove

something—a theorem in mathematics—instead of proving that it’s correct,

it’s easier for me, usually, to say, “Well, find a counterexample.” I can get

psyched up to find a hole in this or explain why it doesn’t work. And then

when I can’t find any holes, then I see the proof.

I think it’s just my personality that I like to attack things and find errors. My

juices are working when I’m playing the game as the opponent rather than if

I’m just sitting there trying to say, “Oh, yeah; now why is this working?”

Seibel: It’s curious that that’s what gets you going, yet your life’s work is

explaining things. Do you think that approach somehow feeds into how you

explain things?

Knuth: The only thing I can claim for my explanations is that I try to match

a natural brain process of seeing things in two different ways at a time in

order to understand something better. I think the key is usually to have a

stereo view instead of a one-dimensional view. I don’t know how that

affects this attacking business.

But when you’re attacking—when you’re playing the game, trying to defeat

something—it arouses competitive hormones or something that just

stimulates the brain in a way that probably just means that I’m trying more

than one way to get at it. A good explanation is a similar thing. A good

explanation somehow combines different viewpoints.

Seibel: Another thing that came out of working on TeX, which you

described in “The Errors of TeX,” was a log of every error that you found

in the program. Folks like the Software Engineering Institute people say that

part of a mature software-engineering process is keeping track of all your

bugs and learning how to prevent the same kind of errors in the future. But

you said that having kept this log, it doesn’t help you prevent future errors.

Knuth: Yeah. Though it’s hard to say that I wouldn’t have been even worse

without the log.

Seibel: But you didn’t feel like, “Ah, now that I’ve seen this I won’t do it

again.”

Donald Knuth

593

Knuth: I just got to recognize my sins. People keep coming back for

absolution, if you know theological terms.

Seibel: So you find yourself now making bugs in your programs and then

saying, “Oh, I’ve done it again, that same kind of bug.”

Knuth: Yeah.

Seibel: So why is that? Is there something about the nature of the mistakes

that makes it hard to distill a lesson that will prevent making them again?

Knuth: I think it’s probably more that I’ll try harder things. I always try

things that are at my limit. If I had to go back and write those kinds of

programs again, the easier ones, I wouldn’t make so many mistakes. But

now that I know some more, I’m trying to write harder stuff. So I make

mistakes because I’m always operating at my limit. If I only stay in

comfortable territory all the time, that’s not so much fun.

Seibel: So if you just kept writing typesetting systems for the rest of your

life?

Knuth: Yeah, I would get those pretty good. But we keep raising the bar

and then we stumble on it. We’re dealing with—as we said earlier—things

that are on the edge of what human beings can handle and more

complicated than have been done before.

If we restrict ourselves to the things that are really easy, then that’s not

satisfactory because our appetite is always to push the boundary and go

until it gets to something we can barely do. And once we’ve got to there,

then we’re going to want to push that boundary and so on.

So inevitably we’re going to have bugs unless we decide we’re never going

to write anything that stretches our capabilities. So how are we going to do

it better? Every three years there’ll be another buzz word as to something

that’s going to solve all these problems and make it really work. Extreme

programming was one the last two or three years. Before that there was

something else. Somebody will come up with another supposedly silver

bullet and there’ll be a lot of people jumping on that bandwagon and then

they’ll find, “Oh, it’s still hard.”

Donald Knuth

594

Seibel: Has the kind of person who can be a good programmer changed

over time?

Knuth: Pretty much a constant in my experience, over a long period of

years, is that every time I’m exposed to 100 people from some population

or other, except majors in computer science, 2 of them are programmers in

the sense that they really resonate with the machine. Wasilla, Alaska, has

10,000 people, so it’s probably got 200 programmers.

Seibel: So has programming changed enough that the kind of person who

falls in that two percent has changed? Or is it still really the same?

Knuth: I don’t know—you can use the word programming in different

senses. We’re always making tools that are intended to make more of a

match between people’s brains and getting something done in a computer.

I’m mostly talking about the way a machine really works when the machine

is being pushed to the envelope rather than just getting an answer out.

We’ve got machines that are so powerful now that people who aren’t really

good at programming, in my esoteric sense, are able to get answers out of

these machines that would have taken a huge expert to do on old machines.

But with the new machines, the people that I’m talking about are going to be

doing the problems that couldn’t be handled by the old machines.

So there’s that change and then there’s the change that I’m really worried

about: that the way a lot of programming goes today isn’t any fun because

it’s just plugging in magic incantations—combine somebody else’s software

and start it up. It doesn’t have much creativity. I’m worried that it’s

becoming too boring because you don’t have a chance to do anything much

new. Your kick comes out of seeing fun results coming out of the machine,

but not the kind of kick that I always got by creating something new. The

kick now is after you’ve done your boring work then all of the sudden you

get a great image. But the work didn’t used to be boring.

Seibel: But you still find the kind of programming you do interesting?

Knuth: Oh my God, yes. I’ve got this need to program. I wake up in the

morning with sentences of a literate program. Before breakfast—I’m sure