Seibel: Many people will agree with you that, yes, it’s more fun to writethe code yourself. But other than the fun—

Knuth: It’s not only fun. The job of a mathematician is to make proofs butalmost never, when you’re solving a mathematical problem, do you find atheorem for which the hypotheses are exactly what you need for theproblem you’re solving. Almost always you’ve got something that’s sort oflike the theorem that’s in the book. So what you do is you look at the proofof that theorem and you say, “Oh, here’s how I have to change that proof inorder to prove the hypothesis that I really have.” So mathematical booksare packed with theorems, but you never plug in exactly the theorem—youwant to see that proof because it’s one time in a hundred when you’ll findjust the theorem that you wanted. I think it’s exactly the same withsoftware.

Seibel: Yet isn’t software—I think you’ve said it yourself—about the mostcomplex thing human beings have ever made?

Knuth: It was Dijkstra, I think, first, but yeah. It’s because the complexity ofputting something together is so nonuniform. Pure mathematics tends tohave a few rules that are applied universally—three or four axioms thatdescribe a system. Computer programs have many parts—step one isdifferent from step two is different from step three. It brings together allthese things and they have to fit in an intricate way.

Seibel: So given that complexity, it seems like at some point you have totake some black boxes and say, “OK, we know how this thing works, andwe can use it.” If we were forced to look inside every black box, we’d neverfinish.

Knuth: I’m not saying black boxes are useless. I’m saying that if I’m notallowed to open ’em up—if I have to do everything with a library orsomething like this, I would come up with much, much worse results andmuch slower.

Seibel: Slower-running or slower-developing?

Knuth: Both. Well, OK, I can get programs to work in a hurry, so I can’tclaim that. It’s just taking me longer because I have to search through morereference manuals and find the right parts, so it’s more of a search problemthan a creative problem.

Seibel: A while back the guy who wrote the standard Java collectionlibraries wrote an article about how there had been a bug in theirimplementation of binary search for nine years. Basically they took the minand the max and added them together and divided by two. But, of course, ifthat addition overflows, that’s a bug. So, it’s bad the standard library had abug in it, but they found it eventually and fixed it. If everyone wrote binarysearch themselves, the percentage of binary searches that would be wrongwould 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 programmingclasses in the ’70s. The first day of class everyone writes a program forbinary search and we collect them and the TAs take a look. And you findthat fewer than ten percent are correct. And there are four or six differentbugs. But not with respect to the overflow that you mentioned, which is anew one—it didn’t occur in my classes that we thought adding these twonumbers 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 matrixmultiply black box and then you change the data type from real to complexand so then you’ve got a complex matrix multiply box and it takes 4xn³steps instead of n³ steps. If the real case takes a certain time, t, then thecomplex case takes time 4t. But if you’re allowed to open the box, thenyou’ll only need three real matrix multiplications instead of four becausethere’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; whateverit is—binary search—I’ll have a good source for the algorithm but it won’tquite fit what I want, so I’ll adapt it every time. And I think I’ll be better off. Iknow I’m going against a lot of people who think their job is to write thingsthat 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’munhappy with that kind of world. I like to see their program.

When I wrote Volume I of The Art of Computer Programming people didn’trealize that they could use linked lists in their own programs, that theycould use pointers for data structures.

If you had a problem that had something beyond arrays, you would go tosomebody’s package, or an interpreted language like IPL-V or Lisp. Therewere also Fortran versions and you could get these subroutines and thenyou would learn how to use that package and you would do your programin that. It was completely preposterous for somebody to teach an ordinaryprogrammer how to include linked lists in their program. Everything wassupposed to be done by these canned routines.

But general packages have got to have all of this extra machinery in order tohandle cases that only come up for a small number of the users. So my booksort of opened people’s eyes: “Oh my gosh, I can understand this and adaptit so I can have elements that are in two lists at once. I can change the datastructure.” It became something that could be mainstream instead of justenclosed in these packages.

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 workwith BDDs but the thrust of what I’m writing now for The Art of ComputerProgramming is that you too can program simple versions of BDDs for lotsof applications and it’ll go very far. You can use them for lots of differentkinds of problems where you don’t need all the bells and whistles of theseother packages and these things you can do are easy to understand and easyto put into programs you’re writing yourself.

Earlier this year I finished my section on bitwise tricks and techniques andthese are things that have been a black art in the hacker community foryears. I decided it’s time to say that there’s a theory of these things that youcan understand the ideas, how they fit together. You can use them yourselfwith confidence. And you can build on things and do amazing things that lastyear you didn’t know how to do well at all. It went through theunderground until now; it’s something that we might as well teach topeople—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 Iget a lot of them working for a large variety of things and I would find itharder if I had to spend all my time learning how to use somebody else’sroutines. It’s much easier for me to learn a few basic concepts and thenreuse code by text-editing the code that previously worked.

Seibel: How has the way you think about programming changed from thoseearliest days to now?

Knuth: We already talked about literate programming—that’s a radicaldeparture, that I’m viewing myself as an expositor rather than trying to justput together the right instructions. Dijkstra came out with that sameevolution. In the end his programs were even more literate than mine in thesense that they didn’t even go into the machine. They were only literate.

And he was one of the people largely responsible for structuredprogramming, where we saw patterns that we could use to scale up ourprogram so that we could make larger programs and still keep our headstraight. You write a program that’s ten times as big but you don’t have tolose ten times as much sleep over it because you have tools that allow youto put things together reliably in a larger system. That was definitelydifferent.