Peter Seibel - Coders at Work - Reflections on the craft of programming

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

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 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 4x n 3steps instead of n 3steps. If the real case takes a certain time, t , then the complex case takes time 4 t . 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.