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

I said, “Wow, that seems really neat. Ah, so you need to log every side effect on memory. Every load and store instruction. Gosh, well there are a lot of those in Java.” But in Haskell there are practically none because they occur in this monadic setting. So loads and stores in Haskell are extremely explicit—programmers think of them as a big deal.

So I thought, “Oh, we should just try replicating this atomic memory stuff in Haskell because it would be a very cool feature to have.” And off we went—I talked to Tim about how to do this. Before long, because of the kind of framework that we had—this kind of pure, rather sparer framework that we had—we’d invented retryand orElse. Retryis this mechanism that allows you to do blocking within a transaction and orElseis the bit that allows you to do choice within a transaction. Neither of these are things that had occurred to him or his colleagues in developing transactional memory for Java because the rest of their context was rather more complicated.

So they hadn’t really thought much about blocking. Or maybe they just assumed that the way you do blocking was you say, atomically, “Only run this transaction when this predicate holds.” But that’s very noncompositional—supposing you wanted to get something out of one bank account and put it in another, well, what’s the condition that the transaction can run under? Answer: well, if there’s enough money in the first bank account and there’s enough space in the second—let’s say that they’re limited at both ends. So that’s a rather complicated condition to figure out. And it gets even more complicated if there’s a third bank account involved. It’s very noncompositional—you have to look inside the methods and pull all their preconditions out to the front.

That’s what he had and it kind of worked fine for small programs but clearly wasn’t very satisfactory. So in a Haskell context we came up with this retry, orElsething which we’ve since transplanted back into the mainstream imperative context and they’re busy doing retryand orElseas well. That’s great.

Seibel:So there’s nothing actually inherent about Haskell that enabled that concept? It was just that you were able to think of it?

Peyton Jones:That’s right. There was less crap, basically, so the cool idea stood out in higher relief. It became more disgusting that there was no way to do blocking without losing the abstraction. That’s what led us to retryand orElse. I think a really good place for functional programming to be, or a role for it to play, is as a kind of laboratory in which to examine the beast. And then ideas can feed back. And this STM was a particularly clear example because there was a transition in both directions. Here there was a loop that actually got closed, which I thought was lovely.

Seibel:What’s your desert-island list of books for programmers?

Peyton Jones:Well, you should definitely read Jon Bentley’s Programming Pearls . Speaking of pearls, Brian Hayes has a lovely chapter in this book Beautiful Code entitled, “Writing Programs for ‘The Book’” where I think by “The Book” he means a program that will have eternal beauty. You’ve got two points and a third point and you have to find which side of the line between the two points this third point is on. And several solutions don’t work very well. But then there’s a very simple solution that just does it right.

Of course, Don Knuth’s series, The Art of Computer Programming . I don’t think it was ever anything I read straight through; it’s not that kind of book. I certainly referred to it a lot at one stage. Chris Okasaki’s book Purely Functional Data Structures . Fantastic. It’s like Arthur Norman’s course only spread out to a whole book. It’s about how you can do queues and lookup tables and heaps without any side effects but with good complexity bounds. Really, really nice book. Everyone should read this. It’s also quite short and accessible as well. Structure and Interpretation of Computer Programs . Abelson and Sussman. I loved that. And Compiling with Continuations , Andrew Appel’s book about how to compile a functional program using continuation passing style. Also wonderful.

Books that were important to me but I haven’t read for a long time: A Discipline of Programming by Dijkstra. Dijkstra is very careful about writing beautiful programs. These ones are completely imperative but they have the “Hoare property” of rather than having no obvious bugs they obviously have no bugs. And it gives very nice, elegant reasoning to reason about it. That’s a book that introduced me for the first time to reasoning about programs in a pretty watertight way. Another book that at the time made a huge impression on me was Per Brinch Hansen’s book about writing concurrent operating systems. I read it lots of times.

Seibel:Do you still program a lot?

Peyton Jones:Oh yes. I write some code every day. It’s not actually every day, but that’s my mantra. I think there’s this horrible danger that people who are any good at anything get promoted or become more important until they don’t get to do the thing they’re any good at anymore. So one of the things I like about working here and working in research generally is that I can still work on the compiler that I’ve been working on since 1990.

It’s a big piece of code and there are large chunks of it that I’m really the person who knows most about it.

How much code do I write? Some days I spend the whole day programming, actually staring at code. Other days, none. So maybe, on average, a couple hours a day, certainly. Programming is such fun. Why would you ever want not to do it? Furthermore it keeps you honest—it’s a good reality check to use your own compiler and to use the language that you advocate as well.

Seibel:And you still enjoy programming just as much as when you started?

Peyton Jones:Oh, yes, yes. That’s the most fun thing. I think most programmers have the feeling that “there must be a good way to do this.” One of the nice things about working in research is that instead of some manager standing over me saying, “This has to be done this week—just get it done,” I can sit and look at something and say, “There must be a right way to do this.”

So I spend a lot of time refactoring and moving interfaces around and writing new types or even just rewriting a whole blob to try to make it right. GHC is pretty large—it’s not large by industrial standards; it’s large by functional programming standards—it’s about 80,000 lines of Haskell, maybe a bit more. And it’s long-lived—it’s 15 years old now. The fact that it’s still actively developed is indicative that chunks have got rewritten. There are no untouchable bits. So it’s both challenging and good fun to look at something and think, “What is the right way to do this?” And often I’ll hold off for weeks on something but I just can’t think of a nice way to do it. But that’s tantalizing. Because there has to be a nice way.

Seibel:In those weeks, what happens?

Peyton Jones:Oh, I’m thinking about it in the back of my mind. And sometimes I’ll have a go at it—I sort of run up the hill. And then I remember why it was so complicated and then usually some other displacement activity takes place. So sometimes I run up this hill several times. Sometimes I’m thinking about it in the background. And sometimes I think, “Well, time’s up—just got to do something now.” And maybe it’s not quite as beautiful as it could be.