Seibel Peter. Coders at Work

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

Donald Knuth

595

poets must feel this—I have to go to the computer and write this paragraph

and then I can eat and I’m happy. It’s a compulsion; that I have to admit.

OK, let me show you the program I wrote yesterday. I’m multiplying huge

integers that are way bigger than the universe—they’re special integers that

you can compress the representation down, and so I can deal with them

even though I couldn’t represent them in an ordinary notation, and I’ve

been multiplying these integers that are inconceivably large and I’ve been

squaring them and finding out how they look after squaring them. I’m very

puzzled about what’s going on, but this is exciting to me.

Seibel: You’re an academic but also have worked on big systems and have

done some work in industry. How do you see the relation between

academic computer science and industrial practice?

Knuth: It’s gone in waves. In the ’60s the academics were way ahead of the

industry and the programs that were produced in industry, except for

maybe airline-reservation systems, were laughable to everybody in

universities.

By 1980 the situation had pretty much reversed and the programs that were

being written by people in universities were laughed at by the people in

industry because the universities had gone into theological mode and you

weren’t allowed to use

goto statements. I’m exaggerating to simplify, but

basically there were no-nos in university programs that were keeping

people’s hands tied, and the people in industry didn’t have to worry about

that.

But then in universities people came up with some better ideas about

networking and dealing with large pieces of data and so on, and got ahead.

So it goes back and forth. But the trend in a lot of the algorithm and data-

structure community has not been to my liking when they have lots of data

structures that are just . . . baroque is the only word I can think of. They’re

intricate and clever and you have to admire them for the intellectual

challenge, but I find them sterile. They don’t connect with life; they’re

working in another world. It’s an OK world and it’s got its structure, and

they’re friendly and nice people, but it doesn’t appeal to me personally and

it doesn’t really relate to practice.

Donald Knuth

596

I don’t know why it’s important to me if something relates to practice or

not. There are mathematicians who never think about anything finite, and

they hardly ever come down to countably infinite—they publish terrific

papers just talking about kinds of infinity that are mind-boggling and they’re

able to make sense out of it and that gives them satisfaction. And there are

similar things like that in algorithms. But for me I’m turned on much more

by the ideas that I would be able to use in my machine.

Seibel: In 1974 you said that by 1984 we would have “Utopia 84,” the sort

of perfect programming language, and it would supplant COBOL and

Fortran, and you said then that there were indications that such language is

very slowly taking shape. It’s now a couple of decades since ’84 and it

doesn’t seem like that’s happened.

Knuth: No.

Seibel: Was that just youthful optimism?

Knuth: I was thinking about Simula and trends in object-oriented

programming when I wrote that, clearly. I think what happens is that every

time a new language comes out it cleans up what’s understood about the

old languages and then adds something new, experimental and so on, and

nobody has ever come to the point where they have a new language and

then they want to stop at what’s understood. They’re always wanting to

push further.

Maybe someday somebody will say, “No, I’m not going to be innovative; I’m

just going to be clean and simple, and I’m going to stick to it.” Pascal was

started with that philosophy but then didn’t continue. Maybe we’ll get to a

time when somebody will say, “Let’s set our sights lower and really try to

make something that’s going to be stable.” It might be a good idea.

Seibel: Isn’t part of the problem that while there are misfeatures, there are

also missing features and if a thing is missing you’ve got to make up

something to fill that gap.

Knuth: Yeah, that’s right. It’s got to be extensible somehow. Java didn’t

make itself extensible in a good way.

Donald Knuth

597

Seibel: You’ve designed some languages yourself—probably the most

widely used of which is TeX.

Knuth: So TeX is a programming language but I had to put in those

features kicking and screaming. Guy Steele, Terry Winograd, Leslie

Lamport, and different people needed things when they were using TeX as a

front end for their material. I think Terry Winograd was writing a book on

the syntax of natural languages, so he had some really powerful macros that

he wanted to write in order to make the diagrams in his book. That pushed

TeX a lot towards becoming a programming language in the earliest days.

Seibel: Do you ever wish you had focused more on the design of the

language, as a language?

Knuth: I don’t know. I guess so. In a way I resent having every language be

universal because they’ll be universal in a different way. It’s a little bit like

Unix having 30 definitions of regular expressions under one roof—

depending on which part of Unix you’re using you’ve got a slightly different

flavor of regular expressions. If every tool that you have includes a Turing

machine inside, is this really the way to go? I was really thinking of TeX as

something that the more programming it had in it, the less it was doing its

real mission of typesetting.

When I put in the calculation of prime numbers into the TeX manual I was

not thinking of this as the way to use TeX. I was thinking, “Oh, by the way,

look at this: dogs can stand on their hind legs and TeX can calculate prime

numbers.”

Seibel: But people use the fact that it’s a Turing-complete programming

language to do typesetting-related computations. If it wasn’t Turing-

complete they would be unable to do those things.

Knuth: Yeah, that’s right. I wrote a programming language for simulation in

the ’60s that I had to work hard to kill because it had a lot of users, but

then when Simula came out I liked Simula better and I told people to stop

using my SOL language. Mostly I don’t consider that I have great talent for

language design.

Donald Knuth

598

With TeX I was interacting with hundreds of years of human history and I

didn’t want to throw out all of the things that book designers have learned

over centuries and start anew and say, “Well, forget that guys; you know,

we’re going to be logical now.” In this case, the name of the game was

mostly to take an enormously complicated problem and find a fairly small

set of primitives that would support it. Instead of having 1,000 primitives, I

have 100 primitives or something like that. But going down to 50 primitives,

10 primitives—which we would do if we wanted to be mathematically

clean—I believe wouldn’t work. The problem of making books goes too

much into the complexity of the world, which just doesn’t want to be

simplified.

Seibel: I haven’t really done a study, but it seems like the vast majority of

mathematical and scientific papers are typeset with TeX these days. There

must have been things you’ve seen typeset in TeX that made you think,

“Wow, my program played a part in this.”

Knuth: Well, the proof of Fermat’s Last Theorem was one of those. It’s

one of the most famous mathematical papers. And it happens all the time

that I see books that I know wouldn’t have been written if the authors had

had to go through channels the way they used to. It’s again a little bit of the

black-box thing.

It used to be, you would have to type something up and that would go into

a compositor and it would come back in galley proofs, and so on. You’re

going through all kinds of levels of people who aren’t mathematicians and

then coming out with the product at the end. So you don’t dare do anything

that would confuse any of the people in that line.

But if you can see yourself what it’s going to look like, and you can make up

a notation that isn’t in somebody’s style sheet because it just happens to be

the right one for your problem, then you’re encouraged to do a much

better job.

So this brings me great satisfaction all the time when I know that people

have been able to cut through this and their creativity goes directly to the

reader.

Donald Knuth

599

Seibel: Do you feel like programmers and computer scientists are aware

enough of the history of our field? It is, after all, a pretty short history.

Knuth: There aren’t too many that are scholars. Even when I started

writing my books in 1963, I didn’t think people knew what had happened in

1959. I was reading in American Scientist last week about people who had

rediscovered an algorithm that Boyer and Moore had discovered in 1980. It

happens all the time that people don’t realize the glorious history that we

have. The idea that people knew a thing or two in the ’70s is strange to a lot

of young programmers.

It’s inevitable that in such a complicated field that people will be missing

stuff. Hopefully with things like Wikipedia, achievements don’t get forgotten

the way they were before. But I wish I could also instill in more people the

love that I have for reading original sources. Not just knowing that so-and-

so gets credit for doing something, but looking back and seeing what that

person said in his own words. I think it’s a tremendous way to improve

your own skills.

It’s very important to be able to get inside of somebody else’s way of

thinking, to decode their vocabulary, their notation. If you can understand

something about the way they thought and the way they made a discovery,

then that helps you make your own discoveries. I often read source

materials of what brilliant people have said about this stuff in the past. It’ll be

expressed in unusual ways by today’s conventions, but it’s worth it to me to

penetrate their notation and to try to get into their idea.

For example I spent a good deal of time trying to look at Babylonian

manuscripts of how they described algorithms 4,000 years ago, and what did

they think about? Did they have while loops and stuff like this? How would

they describe it? And to me this was very worthwhile for understanding

about how the brain works, but also about how they discovered things.

A couple of years ago I found an old Sanskrit document from the 13th

century that was about combinatorial math. Almost nobody the author

knew would have had the foggiest idea what he was talking about. But I

found a translation of this document and it was speaking to me. I had done

similar kinds of thinking when I was beginning in computer programming.

Donald Knuth

600

And so to me reading source materials is great enrichment for my own life

and creativity.

I was unable to pass that on to any of my students. There are people alive

now in computer science who are doing this well—a few. But I could count

on the fingers of one hand the people who love source materials the way I

do.

I’ve got lots of collections of source code. I have compilers, the Digitek

compilers from the 1960s were written in a very interesting way. They had

their own language and they used identifiers that were 30 characters long

but very descriptive, and their compilers ran circles around the competition

at the time—this company made the state-of-the-art compilers of 1963 or

’64.

And I’ve got Dijkstra’s source code for the THE operating system. I haven’t

read that. I’ve just skimmed it so far but I collected it because I’m sure it

would be interesting to read if I had time.

One time I broke my arm—fell off a bike—and I had a month where I

couldn’t do anything much, so I read source code that I had heard had some

clever ideas in it that hadn’t been documented. I think those were all

extremely important experiences for me.

Seibel: How do you tackle reading source code? Even reading something in

a programming language you already know is a tricky problem.

Knuth: But it’s really worth it for what it builds in your brain. So how do I

do it? There was a machine called the Bunker Ramo 300 and somebody told

me that the Fortran compiler for this machine was really amazingly fast, but

nobody had any idea why it worked. I got a copy of the source-code listing

for it. I didn’t have a manual for the machine, so I wasn’t even sure what the

machine language was.

But I took it as an interesting challenge. I could figure out

BEGIN and then I

would start to decode. The operation codes had some two-letter

mnemonics and so I could start to figure out “This probably was a load

instruction, this probably was a branch.” And I knew it was a Fortran

Donald Knuth

601

compiler, so at some point it looked at column seven of a card, and that was

where it would tell if it was a comment or not.

After three hours I had figured out a little bit about the machine. Then I

found these big, branching tables. So it was a puzzle and I kept just making

little charts like I’m working at a security agency trying to decode a secret

code. But I knew it worked and I knew it was a Fortran compiler—it wasn’t

encrypted in the sense that it was intentionally obscure; it was only in code

because I hadn’t gotten the manual for the machine.

Eventually I was able to figure out why this compiler was so fast.

Unfortunately it wasn’t because the algorithms were brilliant; it was just

because they had used unstructured programming and hand optimized the

code to the hilt.

It was just basically the way you solve some kind of an unknown puzzle—

make tables and charts and get a little more information here and make a

hypothesis. In general when I’m reading a technical paper, it’s the same

challenge. I’m trying to get into the author’s mind, trying to figure out what

the concept is. The more you learn to read other people’s stuff, the more

able you are to invent your own in the future, it seems to me.

We ought to publish code. The Lions Book is available. And Bill Atkinson’s

programs are now publicly available thanks to Apple, and it won’t be too

long before we’ll be able to read that. That’s well-documented code with

lots of pioneering graphics algorithms in it.

Seibel: Certainly with open source there’s a lot more code out there to

read than there use to be.

Knuth: Yeah, that’s right. But the more varieties of different kinds of

notations are still useful—don’t only read the people who code like you.

APPENDIX

Bibliography

The Art of Computer Programming, Donaid Knuth (Addison-Wesley, 1997)

Beautiful Code: Leading Programmers Explain How They Think, Andy

Oram, Greg Wilson (eds.) (O’Reilly, 2007)

Byte, Vol. 6, No. 8, “Smalltalk issue,” August 1981

Code Complete, Steve McConnell (Microsoft Press, 1993)

Compiling with Continuations, Andrew W. Appel (Cambridge University

Press, 1992)

The Design and Analysis of Computer Algorithms, Alfred V. Aho, John E.

Hopcroft, and Jeffrey D. Ullman (Addison-Wesley, 1974)

Design Patterns: Elements of Reusable Object-Oriented Software, Eric

Gamma, Richard Helf, Ralph Johnson, and John M. Vlissides (Addison-

Wesley Professional, 1994)

A Discipline of Programming, Edsger W. Dijkstra (Prentice Hall, Inc., 1976)

Effective Java, Joshua Bloch (Prentice Hall, 2008)

The Elements of Programming Style, Brian Kernighan and P.J. Plauger

(Computing McGraw-Hill, 1978)

Elements of Style, William Strunk and E.B. White (Longman, 1999)

Bibliography

604

Expert C Programming, Peter van der Linden (Prentice Hall PTR, 1994)

Founders at Work, Jessica Livingston (Apress, 2007)

Hacker’s Delight, Hank Warren (Addison-Wesley, 2002)

Higher-Order Perl, Mark Jason Dominus (Morgan Kaufmann, 2005)

Java Concurrency in Practice, Brian Goetz, Tim Peierls, Joshua Bloch,

Joseph Bowbeer, David Holmes, and Doug Lea (Addison-Wesley, 2006)

Java Puzzlers: Traps, Pitfalls, and Corner Cases, Joshua Bloch and Neil

Gafter (Addison-Wesley, 2005)

The Lisp 1.5 Programmer's Manual, John McCarthy (MIT Press, 1962)

Literate Programming, Donald Knuth (Center for the Study of Language

and Information, 1992)

Machine Intelligence 1, N.L. Collins and Donald Michie (eds.) (Oliver and

Boyd, 1967)

Machine Intelligence 2, Ella Dale and Donald Michie (eds.) (Oliver and

Boyd, 1968)

Machine Intelligence 3, Donald Michie (ed.) (Edinburgh University Press,

1968)

Machine Intelligence 4, Bernard Meltzer and Donald Michie (eds.)

(Edinburgh University Press, 1969)

Magic House of Numbers, Irving Adler (HarperCollins, 1974)

“META II a Syntax-Oriented Compiler Writing Language,” D.V. Schorre in

Proceedings of the 1964 19th ACM national conference, (ACM, 1964)

Mindstorms: Children, Computers, and Powerful Ideas, Seymour A. Papert

(Basic Books, 1993)

The Mythical Man-Month: Essays on Software Engineering, Frederick P.

Brooks (Addison-Wesley Professional, 1995)

Principles of Compiler Design, Alfred Aho and Jeffrey Ullman (Addison-

Wesley, 1977)

“Proof of a Program: FIND”, C.A.R. Hoare in Communications of the ACM,

Vol. 14, Issue 1 (ACM, 1971)