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

Seibel:Yet lots of people have tried to come up with languages or programming systems that will allow “nonprogrammers” to program. I take it you think that might be a doomed enterprise—the problem about programming is not that we haven’t found the right syntax for it but that people have to learn this unnatural act.

Steele:Yeah. And I think that the other problem is that people like to focus on the main thing they have in mind and not worry about the edge cases or the screw cases or things that are unlikely to happen. And yet it is precisely in those cases where people are most likely to disagree what the right thing to do is.

Sometimes I’ll quiz a student, “What should happen in this case?” “Well, obviously it should do this.” And immediately someone else will jump in and say, “No, no, it should do that.” And those are exactly the things that you need to nail down in a programming specification of some process.

I think it’s not an accident that we often use the imagery of magic to describe programming. We speak of computing wizards and we think of things happening by magic or automagically. And I think that’s because being able to get a machine to do what you want is the closest thing we’ve got in technology to adolescent wish-fulfillment.

And if you look at the fairy tales, people want to be able to just think in their minds what they want, wave their hands, and it happens. And of course the fairy tales are full of cautionary tales where you forgot to cover the edge case and then something bad happens.

Seibel: Fantasia and the perils of recursion, for instance.

Steele: Fantasia and recursion, yes. Or, “I wish I was the richest man in the country”—well, that makes everybody else extremely poor and you’re the same as you were before. That kind of thing happens in fairy tales because people forget that there’s more than one way to do something. And if you just think about your main wish and don’t think about the details, that leaves a lot not tied down.

Seibel:So the lesson from fairy tales is that the Gandalfs of the world got there by hard labor, learning the incantations, and there’s no shortcut to that?

Steele:Yeah. I’ll give you another example—suppose I were to tell my smart computer, “OK, I’ve got this address book and I want the addresses to always be in sorted order,” and it responds by throwing away everything but the first entry. Now the address book is sorted. But that’s not what you wanted. It turns out that just specifying something as simple as “a list is in sorted order and I haven’t lost any of the data and nothing has been duplicated” is actually a fairly tricky specification to write.

Seibel:So are there language features that make programmers—folks who have mastered this unnatural act—more productive? You’re designing a language right now so you’ve obviously got some opinions about this.

Steele:I said earlier that I think you can’t afford to neglect correctness. On the other hand, I think we can design tools to make it easier to achieve that. We can’t make it trivial, but I think we can make it easier to avoid mistakes of various kinds. A good example is overflow detection on arithmetic, or providing bignums instead of just letting 32-bit integers wrap around. Now, implementing those is more expensive but I believe that providing full-blown bignums is a little less error-prone for some kinds of programming.

A trap that I find systems programmers and designers of operating-systems algorithms constantly falling into is they say, “Well, we need to synchronize some phases here so we’re going to use a take-a-number strategy. Every time we enter a new phase of the computation we’ll increment some variable and that’ll be the new number and then the different participants will make sure they’re all working on the same phase number before a certain operation happens.” And that works pretty well in practice, but if you use a 32-bit integer it doesn’t take that long to count to four billion anymore. What happens if that number wraps around? Will you still be OK or not? It turns out that a lot of such algorithms in the literature have that lurking bug. What if some thread stalls for 2 to the 32nd iterations? That’s highly unlikely in practice, but it’s a possibility. And one should either mitigate that correctness problem or else do the calculation to show that, yeah, it’s sufficiently unlikely that I don’t want to worry about it. Or maybe you’re willing to accept one glitch every day. But the point is you should do the analysis rather than simply ignoring the issue. And the fact that counters can wrap around is a lurking pitfall that doesn’t hurt most programmers but for a very few it lays traps in their algorithms.

Seibel:Speaking of glitches, what was the worst bug you’ve ever had to track down?

Steele:I’m not sure I can dig up a worst one, but I can tell you a few stories. Certainly, dealing with parallel processes has produced the most difficult-to-deal-with bugs.

When I was a teenager programming on the IBM 1130 was the one time in my life when the solution to a bug came to me in a dream. Or as I woke up. I had been puzzling over a bug for a couple days, couldn’t figure it out. And then suddenly sat bolt upright in the middle of the night and realized I knew what the problem was. And it was because I had overlooked something in an interface specification.

It had to do with concurrent processes. I was writing a decompiler so that I could study the IBM disk operating system by decompiling it. And to this end it would take binary data on the disk and print it in a variety of formats including as instructions, as character codes, as numbers, and so on. And in order to convert the characters, I was feeding the data to various character–conversion routines, one of which was designed for use after reading card codes from a card reader. And I had overlooked the tiny footnote in the specification that said, “We assume that before you call the procedure, the buffer in which the card data will be read has all over the low order bits cleared.” Or maybe had them set.

Anyway, the 12 bits from the card-code column were going into the high 12 bits of the 16-bit word and they were using the low bit for a clever trick whereby you could call the card-reader routine asynchronously and it would asynchronously load the buffer and the conversion routine would follow behind, using that low bit to determine whether the next card column had been read in or not. And if it had been read it would then convert that character. Thereby, as soon as the card was read, very shortly thereafter the conversion would finish—they were overlapping the cost of the card conversion with the time it took to read the card. And I was feeding it raw binary data that wasn’t obeying this constraint. And I had just overlooked this—I thought it was yet another card-conversion routine but it turned out this one had something special about its interface—it was relying on those low-order bits, which ordinarily you wouldn’t think about. It was interpreting what was in the buffer as saying, “Oh, the data has not yet arrived from the card reader.” In principle I knew this, but it wasn’t occurring to me. And then, as I say, it came to me while I was asleep. So that was an odd case.

The other really interesting story I can think of was while I was the maintainer of the Maclisp system and Maclisp supported bignums—integers of arbitrary precision. They’d been around for several years and were considered pretty well debugged and shaken out. They’d been used for all kinds of stuff in Macsyma, and Macsyma users were using them all the time. And yet a report came in from Bill Gosper saying, “The quotient of these two integers is wrong.” And he could tell because the quotient was supposed to be very near a decimal multiple of pi.