Seibel Peter. Coders at Work
Подождите немного. Документ загружается.
Donald Knuth
575
I tried it only a limited amount at Stanford. I worked with a group of
undergraduates. They would write their programs on a summer project and
I introduced them to this idea of literate programming. There were only
seven of them working with me that summer. And six of them loved it to
the point that they’re still using it today. The seventh one hated it. His idea
of writing a literate program was to take an ordinary program and put a
wrapper around it and say, “This is module one,” and so on. Of course,
Stanford admits people who are good writers, so this isn’t a random sample.
Seibel: Have you ever written a literate program where you dramatically
reorganized it into a different order for explication? It’s hard for me to
imagine that stream of consciousness is always the best organizing principle.
Knuth: It just hardly ever happened. I can’t remember going back and really
changing the order of the chapters. It just always seemed like there was
almost only one choice what to attack next. I can’t explain it exactly, but it
just seemed that one would segue into the next.
Seibel: Do you write literate code for programs that no one but you will
ever see?
Knuth: Exactly. This is what literate programming is so great for—I can talk
to myself. I can read my program a year later and know exactly what I was
thinking.
Seibel: Does that always work?
Knuth: Well, it’s often a lot harder to understand a year later than before.
But compare that to what I had without it. It doesn’t make the complicated
thing trivial ,but it’s just way better than any other method I know.
I just printed out a small subset of a large collections of subroutines that are
all written in C that are pretty much state of the art for manipulating
BDDs—Boolean decision diagrams. This is the opposite of
CWEB—this is
what almost everyone in the world does when they’re developing packages
now. They do it by means of fairly disciplined commenting conventions that
are understood by a large community. And the code is not real difficult to
understand because it’s separated out into a logical form and you’ve got
these header files and I can see the data structures and there are comments
Donald Knuth
576
on each part of the data structure explaining what it’s doing. So this is
another style of programming that works.
Yet I can’t help but think that it’s considerably below what can be achieved
with literate programming. Because of lots of intangible things that I can’t
prove. The most convincing to me was that I believe that I’ve written some
programs that I could not have written at all without literate programming.
For example, the
MMIX simulator would have been such an intellectual
challenge that if I had to do it in the conventional style, I don’t think I ever
would have finished it. Just separating it out into subroutines wasn’t enough
to simplify it to make it intellectually manageable.
This is a simulator that takes an extremely general specification of a
computer: what functional units it has, how many instructions can execute
at a time, the caching strategies, how the bus works, how the output works,
how are you doing branch prediction, and how you maintain the pipeline.
So you can imagine a computer that would have six division units and a
pipeline of certain stages and this will simulate it. Would you be able to
calculate prime numbers faster if you had this machine? You don’t have to
build the machine.
I’m not saying it’s impossible to take that program and put it into
subroutines, but I would never have finished it that way. And also it’s only
170 pages and it is possible to understand it—I’m not the only person in the
world who understands it.
Seibel: I read your literate reimplementation of the game Adventure and
noticed that it seemed somewhat monolithic. It seemed like the literate
style, because it lets you interpolate things, draws you away from breaking
things down into subroutines.
Knuth: This is true. Instead of calling a subroutine, it’s like inline
subroutines all the way through. The idea of a subroutine is there but it’s
not in your final program as a subroutine. It’s more like a macro in some
ways. But the thing is, at the conceptual level, the subroutine-calling
mechanism isn’t necessary if you have some other way to do it in the
language you’re using.
Donald Knuth
577
In Adventure I don’t think I actually removed subroutines from Don Woods’s
Fortran program—I was taking his Fortran program and putting it into
English and C. But it’s true that when you look at my code for TeX, the
number of subroutines that you’re in, on the subroutine stack, might be 4
or 5 whereas a program written by somebody else, without literate
programming, it might be 50 or 100.
What I try to work on is units that correspond to the way I have it in my
head, rather than the way a logician might want it to be in some formal
system. My programs are supposed to match my intuition more than
somebody else’s rigid framework.
Of course, eventually it has to go into a computer, which is rigid, which has
its precise rules of understanding. But to me the idea of the right kind of a
program is something that matches the way I think as closely as possible
rather than something that matches the machine as closely as possible. I
have to find the way to do the conversion, but my source text tries to stay
closer to my brain than to the machine.
I also believe that literate programming is a powerful style of documentation
that can be used to communicate across groups of people. I had many
people who understood the code for TeX well enough to construct
scenarios where it would fail. I think more people, at one point in their life,
understood that program than any other program of its size,
Seibel: Did you ever find, even with that, that you still had people who had
read the thing and then sent you questions that made you think, “Wow,
they really missed something here”?
Knuth: Of course. That always happens, but it’s a mistake in my exposition.
Let me give you a simple example. In The Art of Computer Programming I’m
talking about the early history of bit-oriented operations and I have the
following sentence: “The Manchester Mark 1 computer, built about the
same time as the EDSAC, included not only bitwise and but also or and
exclusive or. When Alan Turing wrote its first programming manual in 1950
he remarked that bitwise not can be obtained by using exclusive or in
combination with a row of ones.”
Donald Knuth
578
Now, in my sentence I’m saying, “Alan Turing wrote its first programming
manual,” meaning the first programming manual for the Manchester Mark 1.
But four or five readers independently said, I must have meant “his:” “When
Alan Turing wrote his first programming manual in 1950”.
Well, actually, he had written other programming manuals, so what I said
was correct but it was misinterpreted by people. So now I say, “When Alan
Turing wrote the first programming manual for the Mark I, in 1950. . . .”
Mathematical things; similarly I’ll get people who miss it. So then I’ll say, you
know, I actually said it correctly, but I know I still have to change it and
make it better.
Seibel: When you publish a literate program, it’s the final form of the
program, typically. And you are often credited with saying, “Premature
optimization is the root of all evil.” But by the time you get to the final form
it’s not premature—you may have optimized some parts to be very clever.
But doesn’t that make it hard to read?
Knuth: No. A good literate program will show its history. A good literate
program will say, “Here’s the obvious way to do it and then why we don’t
follow that road?”
When you put subtle stuff in your program, literate programming shines
because you don’t just have the code that does it but also your
documentation. You say, “This is a dirty trick here, it work’s because—”
and then you state very carefully the reasons and the assumptions.
I’ll use dirty tricks for two reasons. One is, if it’s really going to give me a
performance improvement and my application is one that the performance
improvement is going to be appreciated. Or sometimes I’ll say, “This is
tricky; I couldn’t resist being tricky today because it’s so cute.” So just for
pure pleasure. In any case, I document it; I don’t just put it in there.
Seibel: Would that be more in the prose?
Knuth: It’s in the prose part. I don’t show the code that I’ve taken out. I
could.
Donald Knuth
579
Seibel: Is there any facility in CWEB for actually including code that isn’t part
of the application, so rather than just document it in the prose, you can say,
“Here’s a really dirt-simple version of this function.”
Knuth: You just have the code but you never use it. It comes out in the
documentation saying this code is never used.
Seibel: So it would just be a fragment that you would never reference?
Knuth: Yeah. Also, I have code in there that I can then invoke from the
debugger. I can say, “Call such-and-such with such-and-such parameters.”
The subroutine is never actually called in the program itself, but it’s there in
the documentation. So I can stop a program in the middle and I can call this
subroutine and it’ll take a look and see how it’s doing, see how big things
have gotten.
Seibel: So by the same token you could write, “Section one—here’s a naive
implementation of this algorithm; section two—here’s a slightly souped-up
version of section one; and section three, here’s the one we actually use
which you would never understand if you hadn’t read the first two
sections.”
Knuth: Exactly. I have some programs on the Web that solve the 15 puzzle.
And I go through 3 different versions. And I say, “Read version one or you’ll
never understand version two. And read version two or you’ll never
understand version three.”
I write a whole variety of different kinds of programs. Sometimes I’ll write a
program where I couldn’t care less about efficiency—I just want to get the
answer. I’ll use brute force, something that I’m guaranteed I won’t have to
think—there’ll be no subtlety at all so I won’t be outsmarting myself. There
I’m not doing any premature optimization.
Then I can change that into something else and see if I get something that
agrees with my brute-force way. Then I can scale up the program and go to
larger cases. Most programs stop at that stage because you’re not going to
execute the code a trillion times. When I’m doing an illustration for The Art
of Computer Programming I may change that illustration several times and the
people who translate my book might have to redo the program, but it
Donald Knuth
580
doesn’t matter that I drew the illustration by a very slow method because
I’ve only got to generate that file once and then it goes off to the publisher
and gets printed in a book.
But right now I’m working on combinatorial algorithms, which are, by
definition, humongous-size problems. So in order to have interesting
examples in my book I’ve got to write programs that solve problems that
readers will say, “Oh, yeah, I couldn’t have done that just by simple
methods, so I need to learn something about the art of programming or it’ll
take 100 years to solve this problem by the brute-force method.”
Combinatorial algorithms are fascinating because one good idea can save
you ten orders of magnitude in running time. But I don’t sneer at ideas that
save you twenty percent when you’re doing it a trillion times. Because if you
can save a hundred nanoseconds in a loop that’s being done a trillion times,
I think you’re saving a day. If the code is going to be used a lot it can really
pay off so you’ve got to go to subtle tricks that aren’t easy to understand.
About a year ago I saw a review in Computing Reviews—the guy was
reviewing a book; the title was Programming Tricks or something like this.
And the thrust of the review was, “If I ever caught any of the programmers
working for me using any of these tricks, I would fire them.” And so
naturally I went out and looked at the book because I thought, “This is a
book I want to see and learn from. Unfortunately, the tricks weren’t actually
that good.”
Seibel: Were they really firing offenses?
Knuth: They were very weak, actually. It wasn’t presented systematically
and everything, but I thought they were pretty obvious. It was a different
culture entirely. But the guy who said he was going to fire people, he wants
programming to be something where everything is done in an inefficient way
because it’s supposed to fit into his idea of orderliness. He doesn’t care if
the program is good or not—as far as its speed and performance—he cares
about that it satisfies other criteria, like any bloke can be able to maintain it.
Well, people have lots of other funny ideas.
People have this strange idea that we want to write our programs as worlds
unto themselves so that everybody else can just set up a few parameters
Donald Knuth
581
and our program will do it for them. So there’ll be a few programmers in
the world who write the libraries, and then there are people who write the
user manuals for these libraries, and then there are people who apply these
libraries and that’s it.
The problem is that coding isn’t fun if all you can do is call things out of a
library, if you can’t write the library yourself. If the job of coding is just to be
finding the right combination of parameters, that does fairly obvious things,
then who’d want to go into that as a career?
There’s this overemphasis on reusable software where you never get to
open up the box and see what’s inside the box. It’s nice to have these black
boxes but, almost always, if you can look inside the box you can improve it
and make it work better once you know what’s inside the box. Instead
people make these closed wrappers around everything and present the
closure to the programmers of the world, and the programmers of the
world aren’t allowed to diddle with that. All they’re able to do is assemble
the parts. And so you remember that when you call this subroutine you put
x0, y0, x1, y1 but when you call this subroutine it’s x0, x1, y0, y1. You get
that right, and that’s your job.
Seibel: Many people will agree with you that, yes, it’s more fun to write
the code yourself. But other than the fun—
Knuth: It’s not only fun. The job of a mathematician is to make proofs but
almost never, when you’re solving a mathematical problem, do you find a
theorem for which the hypotheses are exactly what you need for the
problem you’re solving. Almost always you’ve got something that’s sort of
like the theorem that’s in the book. So what you do is you look at the proof
of that theorem and you say, “Oh, here’s how I have to change that proof in
order to prove the hypothesis that I really have.” So mathematical books
are packed with theorems, but you never plug in exactly the theorem—you
want to see that proof because it’s one time in a hundred when you’ll find
just the theorem that you wanted. I think it’s exactly the same with
software.
Seibel: Yet isn’t software—I think you’ve said it yourself—about the most
complex thing human beings have ever made?
Donald Knuth
582
Knuth: It was Dijkstra, I think, first, but yeah. It’s because the complexity of
putting something together is so nonuniform. Pure mathematics tends to
have a few rules that are applied universally—three or four axioms that
describe a system. Computer programs have many parts—step one is
different from step two is different from step three. It brings together all
these things and they have to fit in an intricate way.
Seibel: So given that complexity, it seems like at some point you have to
take some black boxes and say, “OK, we know how this thing works, and
we can use it.” If we were forced to look inside every black box, we’d never
finish.
Knuth: I’m not saying black boxes are useless. I’m saying that if I’m not
allowed to open ’em up—if I have to do everything with a library or
something like this, I would come up with much, much worse results and
much slower.
Seibel: Slower-running or slower-developing?
Knuth: Both. Well, OK, I can get programs to work in a hurry, so I can’t
claim that. It’s just taking me longer because I have to search through more
reference manuals and find the right parts, so it’s more of a search problem
than a creative problem.
Seibel: A while back the guy who wrote the standard Java collection
libraries wrote an article about how there had been a bug in their
implementation of binary search for nine years. Basically they took the min
and the max and added them together and divided by two. But, of course, if
that addition overflows, that’s a bug. So, it’s bad the standard library had a
bug in it, but they found it eventually and fixed it. If everyone wrote binary
search themselves, the percentage of binary searches that would be wrong
would probably be quite high.
Knuth: That’s true. And that’s just one of a huge number of examples.
Binary search is a particular example that we started out our programming
classes in the ’70s. The first day of class everyone writes a program for
binary search and we collect them and the TAs take a look. And you find
that fewer than ten percent are correct. And there are four or six different
bugs. But not with respect to the overflow that you mentioned, which is a
Donald Knuth
583
new one—it didn’t occur in my classes that we thought adding these two
numbers might be a problem.
But this black-box idea—why do I hate it so much? We’re talking arithmetic,
so say you have a program for matrix multiplication. You have a matrix
multiply black box and then you change the data type from real to complex
and so then you’ve got a complex matrix multiply box and it takes 4✕n
3
steps instead of n
3
steps. If the real case takes a certain time, t, then the
complex case takes time 4t. But if you’re allowed to open the box, then
you’ll only need three real matrix multiplications instead of four because
there’s an identity that will describe the product of two complex matrices.
That’s just one small example—it just goes on and on.
I’ll have a priority queue or I’ll have some kind of a heap structure; whatever
it is—binary search—I’ll have a good source for the algorithm but it won’t
quite fit what I want, so I’ll adapt it every time. And I think I’ll be better off. I
know I’m going against a lot of people who think their job is to write things
that everybody is going to use, so if there are any bugs in it, they get to fix
’em and everybody else’s program will start working better now. OK. I’m
unhappy with that kind of world. I like to see their program.
When I wrote Volume I of The Art of Computer Programming people didn’t
realize that they could use linked lists in their own programs, that they
could use pointers for data structures.
If you had a problem that had something beyond arrays, you would go to
somebody’s package, or an interpreted language like IPL-V or Lisp. There
were also Fortran versions and you could get these subroutines and then
you would learn how to use that package and you would do your program
in that. It was completely preposterous for somebody to teach an ordinary
programmer how to include linked lists in their program. Everything was
supposed to be done by these canned routines.
But general packages have got to have all of this extra machinery in order to
handle cases that only come up for a small number of the users. So my book
sort of opened people’s eyes: “Oh my gosh, I can understand this and adapt
it so I can have elements that are in two lists at once. I can change the data
structure.” It became something that could be mainstream instead of just
enclosed in these packages.
Donald Knuth
584
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