Seibel Peter. Coders at Work
Подождите немного. Документ загружается.
C H A P T E R
15
Donald Knuth
Of all the subjects of this book, Donald Knuth perhaps least needs an introduction.
For the past four decades he has been at work on his multivolume masterwork
The Art of Computer Programming, the bible of fundamental algorithms and data
structures, which American Scientist included on its list of the top 12 physical-
sciences monographs of the century, in the company of works by Russell and
Whitehead, Einstein, Dirac, Feynman, and von Neumann. He popularized the use
of asymptotic (a.k.a. Big-O) notation in analyzing algorithms, invented LR parsing,
and defended goto statements from Dijkstra’s criticism.
But he is not simply a theorist. After finishing Volume III of The Art of Computer
Programming in 1976, Knuth took what was supposed to be a year off to write
the typesetting software TeX and METAFONT so he could see his books typeset
to his own satisfaction. Ten years later he was done, having along the way
invented a new style of programming, “literate programming,” and an algorithm
for breaking paragraphs of text into lines for typesetting that is still pretty much
the state of the art.
His numerous awards have included the first Association for Computing Machinery
Grace Murray Hopper Award (1971), the Turing Award (1974), and the National
Medal of Science (1979). In 1990 he stopped using email, explaining that his job
was not “to be on top of things” but “to be on the bottom of things” deeply
understanding and explaining large areas of computer science so he could explain
them in his books.
Donald Knuth
566
In this interview we talked about Knuth’s enthusiasm for literate programming, his
ambivalence about black boxes, and what he sees as a regrettable “overemphasis
on reusable software.”
Seibel: When did you learn to program?
Knuth: I was a freshman at Case Institute of Technology. This was the fall
of 1956 and during that quarter or semester they got a computer.
Seibel: This was the IBM 650?
Knuth: It was the 650, yeah. That was the first computer that they made
more than a hundred of. I think they had thousands of them but maybe not
ten thousand. But it was the first mass-produced computer, so even Case
got one.
I was employed in the statistics lab sorting cards. I would tabulate data for
the statisticians and that helped supplement my scholarship. There was this
room on the first floor with a window in it and you could see this machine
behind the window with lights flashing. It looked pretty fascinating.
One afternoon a guy from the lab went to the blackboard and was
explaining to the three of us freshmen what this machine did. I found a
manual for the machine and they had example ten-line programs. It seemed
to me they were kind of stupid—it looked like there was a way to improve
even those little programs.
And it turned out it was possible to go at night and touch the machine. This
was unusual. I think Dartmouth and Case were the only universities that let
undergraduates touch machines. Other places they had professionals and
you submitted decks of cards and got your answers the next day. But at
Case it was hands-on. They just said, “Oh, yeah, watch out for this; you
don’t want to do that; it’ll mess up the machine,” so we had a really nice
chance to play with it.
Anyway, I got to see if one of my little changes to the program would also
work, and it did. So I said, “My goodness, this is pretty amazing. I’m only a
Donald Knuth
567
freshman and I can do better than what was in this book—this might be
something I have talent for.” Well, it turned out I did have a talent for it but
not in the way I thought, because almost anybody in the world could have
done better than that program in that particular manual.
The machine was a decimal machine, so it wasn’t quite as strange as if I had
to learn binary arithmetic, although I played with binary arithmetic a little bit
when I was in high school. But the fact that it was decimal made it somehow
more human or something—comfortable. I can still remember the machine
language—sixty-five is reset-add-lower—it helps me making up passwords and
things now.
Seibel: Uh-oh; you just revealed your secret there.
Knuth: Yeah, right. Then I decided I would write a little program to
calculate the prime factors of a number. It was about 100 lines long. I would
come at night when nobody else was using the machine, and debug it. And I
found more than 100 bugs in my 100-line program. But 2 weeks later I had a
program that would find prime factors of any 10-digit number that you
dialed into the console switches.
That was how I learned programming—basically taking one program that I
made up myself and sitting at a machine over a period of some weeks, and
kept getting it to work a little better and a little better.
My second program was converting between binary and decimal. But my
third program was a program to play tic-tac-toe and that was what really
made me a programmer.
I had to use data structures for that. I made three versions of tic-tac-toe,
one of which was self-learning so that it would start out knowing nothing
about the game and then it would remember every time it lost a game that
the moves it made were suspicious and the moves that the opponent made
were good, and it would upgrade the quality of certain positions and
downgrade the quality of other positions, and then after you played 400
games it would do a fairly decent job of tic-tac-toe.
Seibel: It seems a lot of the people I’ve talked to had direct access to a
machine when they were starting out. Yet Dijkstra has a paper I’m sure
Donald Knuth
568
you’re familiar with, where he basically says we shouldn’t let computer-
science students touch a machine for the first few years of their training;
they should spend all their time manipulating symbols.
Knuth: But that’s not the way he learned either. He said a lot of really
great things and inspirational things, but he’s not always right. Neither am I,
but my take on it is this: Take a scientist in any field. The scientist gets older
and says, “Oh, yes, some of the things that I’ve been doing have a really
great payoff and other things, I’m not using anymore. I’m not going to have
my students waste time on the stuff that doesn’t make giant steps. I’m not
going to talk about low-level stuff at all. These theoretical concepts are
really so powerful—that’s the whole story. Forget about how I got to this
point.”
I think that’s a fundamental error made by scientists in every field. They
don’t realize that when you’re learning something you’ve got to see
something at all levels. You’ve got to see the floor before you build the
ceiling. That all goes into the brain and gets shoved down to the point
where the older people forget that they needed it.
Seibel: I’ve asked the people I’ve talked to for this book about how much
they’ve read The Art of Computer Programming. Most have used it as a
reference but a few said they’ve read it cover to cover. Should every
programmer be able to read your books? It’s pretty mathematically intense
stuff.
Knuth: I sometimes wonder if I can read them. I’m trying to organize a lot
of wisdom that surrounds the topic that I’m discussing and I gather it from
all these places where it appeared in parts and put it into some unity that
can be carried forward, and gets the history right, and corrects bugs and
obscurities in the original sources.
Like in the parts that I’m writing now, I’m starting out with stuff that’s in
math journals that is written in jargon that I wouldn’t expect very many
programmers to ever learn, and I’m trying to dejargonize it to the point
where I can at least understand it. I try to give the key ideas and I try to
simplify them the best I can, but then what happens is every five pages of my
book is somebody’s career.
Donald Knuth
569
In other words, there’s still so much more beyond any five pages of my
book that you can make a lifetime’s worth of study, because there’s just that
much in computer science. Computer science doesn’t all boil down to a
bunch of simple things. If it turned out that computer science was very
simple, that all you needed to do was find the right 50 things and then learn
them really well, then I would say, “OK, everybody in the world should
know those 50 things and know them thoroughly.”
But it isn’t that way. I’ve got thousands of pages and exercises, and I write it
down and put it in the book so that I don’t have to have it all in my head. I
have to come back to it and learn it again. And I have the answers to the
exercises because I know that ten years from now I won’t remember how
to do the darn thing and it will take me a long time to reconstruct it. So I
give myself at least the clues to how to reconstruct stuff.
I’m constantly torn between saying, “Well, this is too complicated; you’d
better not talk about it at all,” and the other feeling that people are saying,
“But all you’ve put in your book is just so trivial; there’s nothing good.” I can
argue at any particular time that I should cut everything out or that I have
way too little.
What it really boils down to is, all of the really cool things that can be
explained in a half a page have to be in my book, on some half a page. And
all the things I’ve seen that are just too good to be left out. So I find out that
the section I just wrote about binary decision diagrams, it turned out that I
had more than 260 exercises because there just was more and more stuff
that seemed to me there would be more than a trivial audience for. But I’m
not saying everybody is the audience for all 260 of these things. Still, I know
there are a large number, for each of these, that are going to appreciate it.
I consider it amazing that some people do go cover to cover in my books. In
most cases I know that people are going to pick and choose the parts that
they like. But they know that if they dig further then they’ll get something
that has only one subset of jargon describing it instead of all different kinds
of notations and terminology—if I didn’t write the books it would be much
harder for people to find stuff out. That’s what turns me on.
Also, I try to explore the territory in a way that is most relevant to a
practical programmer rather than the most academic cachet for getting
Donald Knuth
570
something published that’s theoretically interesting but wouldn’t really be
used in a real program.
The things that I leave out are where somebody has a data structure that
saves a factor of log log n only when n gets bigger than two to the million.
And there are lots and lots of papers that are doing that. They’re playing
games where in principal, if computers were godlike, then we could have
algorithms that are faster. But even an algorithm like a balanced tree or AVL
tree, I don’t use in my own programs unless I know that it’s going to be a
really big tree.
Seibel: What do you use?
Knuth: I use an ordinary binary search tree with a little trick for
randomizing it that I just put in.
Seibel: Speaking of practical work, in the middle of working on The Art of
Computer Programming you took what turned into a ten-year break to write
your typesetting system TeX. I understand you wrote the first version of
TeX completely away from the computer.
Knuth: When I wrote TeX originally in 1977 and ’78, of course I didn’t
have literate programming but I did have structured programming. I wrote it
in a big notebook in longhand, in pencil.
Six months later, after I had gone through the whole project, I started typing
into the computer. And did the debugging in March of ’78 while I had
started writing the program in October of ’77. The code for that is in the
Stanford archives—it’s all in pencil—and of course I would come back and
change a subroutine as I learned what it should be.
This was a first-generation system, so lots of different architectures were
possible and had to be discarded until I’d lived with it for a while and knew
what was there. And it was a chicken-and-egg problem—you couldn’t
typeset until you had fonts but then you couldn’t have fonts until you could
typeset.
But structured programming gave me the idea of invariants and knowing
how to make black boxes that I could understand. So I had the confidence
Donald Knuth
571
that the code would work when I finally would debug it. I felt that I would
be saving a lot of time if I waited six months before testing anything. I had
enough confidence that the code was approximately right.
Seibel: And the time savings would be because you wouldn’t spend time
building scaffolding and stubs to test incomplete code?
Knuth: Right.
Seibel: Other than the fact that they’re so nicely typeset now, do you think
your books would be very different if you hadn’t spent ten years writing
TeX?
Knuth: Good question. The experience of using structured programming in
a not purely academic way—in other words, I’m not just thinking about
invariants in toy programs, but in real programs—probably had a fair
influence on how I’m describing algorithms in the new stuff I write now. Or
if it hasn’t, it should.
I wouldn’t have known about caching and trends in the way computers
change and things like that if I was just going on in the same mold of going
from the literature to writing my books. While I was writing Volumes I, II,
and III, I wasn’t writing programs like TeX that that would be more typical
of a large programming practice. They would be toy programs. So it gave
me more of a perspective on numbers and quantity.
It’s really amazing, though, when you’re writing a book, the influences that
will make you choose different words. It’s mysterious how it gets in there.
That’s the most important influence of writing TeX—that it gave me a
different kind of a mental take on things so that my sentences come out
different. They’ll be a little bit less hedgy. There is a tone that comes out in
the whole thing, of confidence or something.
Seibel: Do you think you were a dramatically better programmer when
you finished TeX than when you started?
Knuth: Well, yes, because of literate programming.
Seibel: So you had better tools, but had you actually improved your skills?
Donald Knuth
572
Knuth: I learned a terrific amount while I was doing it. One of the things I
learned was how much software occupies the brain. It was a much more
difficult task than I expected. I couldn’t teach classes full-time and write
software full-time. I could teach classes full-time and write a book full-time
but software required so much attention to detail. It filled that much of my
brain to the exclusion of other stuff. So it gave me a special admiration for
people who do large software projects—I would never have guessed it
without having been faced with that myself.
Seibel: So programming is harder than writing books, and somewhere I
read something where you said that it’s impossible to estimate how long it
will take to write books. Does that then mean that it’s even harder to
estimate how long programming will take?
Knuth: Yeah, right. That’s a very good corollary.
This year I’ve written probably three major programs which are pushing one
hundred pages of code—literate code, with 8.5✕11 pages. Two of them are
related to each other, so it’s more like two and a half major programs. And
about 150 small programs. Probably more than I did the previous year. So I
programmed galore this year on small programs but also, a couple of them
were things that took a month or more to do.
Seibel: And did you expect them to take a month?
Knuth: Well, I expected one of them to take a month. I knew that it wasn’t
going to be easy but I didn’t know how much richness there was going to
be, so I added more features as I got to using them. I think it is always going
to be true that a person who manages programmers should not expect it to
be predictable.
Seibel: In addition to writing The Art of Computer Programming and TeX,
you’re also the inventor of—and advocate for—literate programming, a way
of writing code so it can be more easily read by people. And you wrote
WEB
and CWEB, tools that implement literate programming languages based on
Pascal and C.
Knuth: So you say advocate—it’s sort of my shtick to say that this is good.
But I also am the kind of guy that’s uncomfortable preaching or trying to
Donald Knuth
573
convert someone. I think programming is a lot like religion; people have
their beliefs. Some people like to force their beliefs on others. Others say,
you know, here’s what I think; I can’t prove that this is the best thing, but it
sure works for me. Then you hope that other people will try it and come to
the same conclusion. But I don’t like going out and telling people what they
ought to believe.
Seibel: Well, maybe you can explain why you like it so much and how it
differs from illiterate programming.
Knuth: The first rule of writing is to understand your audience—the better
you know your reader the better you can write, of course. The second rule,
for technical writing, is say everything twice in complementary ways so that
the person who’s reading it has a chance to put the ideas into his or her
brain in ways that reinforce each other.
So in technical writing usually there’s redundancy. Things are said both
formally and informally. Or you give a definition and then you say,
“Therefore, such and such is true,” which you can only understand if you’ve
understood the definition.
Or you’ll say, “We define a equals the such-and-such to be the set of all
leading elements.” So this informal term, the set of all leading elements, is
complemented by the mathematical description of how we constructed the
set a.
So literate programming is based on this idea that the best way to
communicate is to say things both informally and formally that are related.
And it just provides a natural framework for switching between the natural
language, English, and the formal language, C or Lisp or whatever is your
formal language, and putting this together. So that, to me, has to be a win
for documentation.
Now, the other thing is, as I write the program, I don’t have to present it in
the form that the compiler wants to see it. I present it in the form that I
think is easiest for a reader to understand.
You can write your code bottom-up and make subroutines that give you
bigger and bigger things and your confidence builds because now you can do
Donald Knuth
574
more things. Other people write top-down; they start out and say, “Well, I
have this problem to solve, so first I’ll do this and then I’ll do this.”
When I write a literate program I can choose between these as I like. And
almost always the way my final program comes out is in the order in which I
actually thought of the things myself. So I’ll start out and I’ll say, “I have this
problem to solve, so first I’m going to have to solve this and then I’m going
to have to solve that.”
But then I say, “Now let’s start building some tools bottom-up.” We have
the goal in mind but we build a few bottom-up tools and then we’ll go back
and do a little top-down. But in what order we do this is, first I write about
what I thought about the first day I had to work on this problem. And then,
the next chapter would be the thing I decided to tackle next.
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.