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

Seibel:And is the only way out to say, “OK, this thing has lived long enough, start over”?

Peyton Jones:I think that eventually you have to reengineer chunks of it. And if you can afford to reengineer a bit as you go along, then—if you don’t do anything for ten years then the result may just be so daunting that you think, “I just have to throw it away and start again.” If you can afford to reengineer a bit as you go along, like the human cells regenerating themselves—that’s what I hope is happening to GHC.

The most depressing thing about life as a programmer, I think, is if you’re faced with a chunk of code that either someone else wrote or, worse still, you wrote yourself but you no longer dare to modify. That’s depressing.

Peter Norvig is a broad thinker and a hacker at heart. He once wrote a program to find in Google’s search logs series of three consecutive searches by the same user that, when put together, made a haiku (one of the most memorable: “java ECC / java elliptical curve / playboy faq”).

On his web site Norvig has links to the usual stuff: books and papers he’s written, slides from talks he’s given, and various bits of his code. But there are also links to items he’s had published in McSweeney’s Quarterly Concern, his witty recounting of writing a program to generate the world’s longest palindromic sentence, and his “Gettysburg Powerpoint Presentation,” a send-up of Microsoft’s PowerPoint software, which has been cited by Edward Tufte and which appears on the first page of results if you Google “PowerPoint.”

He is now the Director of Research at Google, after having been the Director of Search Quality. Prior to that he had been the head of the Computational Sciences Division at NASA Ames Research Center and before that, an early employee at the late-’90s Internet startup Junglee. He won the NASA Exceptional Achievement Award in 2001 and is a Fellow of the American Association for Artificial Intelligence and the Association for Computing Machinery.

Between Google, NASA, and Junglee, Norvig has experience with both the “hacker” and “engineer” approaches to building software and talks in this interview about the advantages and disadvantages of each. As a former computer science professor and now an insider at one of the biggest industrial software shops in the world, he also has an interesting perspective on the relation between academic computer science and industrial practice.

Other topics in our conversation included how programming has changed in recent years, why no design technique can make up for not knowing what you’re doing, and why NASA might be better off with less-reliable but cheaper software.

Seibel:When did you start programming?

Norvig:In high school. We had a PDP-8, I think it was, at my high school, and there was a class I took—we started in BASIC programming and I went from there.

Seibel:What year would that have been?

Norvig:I graduated high school in ’74, so it must have been ’72 or ’73. I remember a couple of things, going back to those early days. I remember the teacher trying to teach shuffling of a deck of cards. Her algorithm was, use a random-number generator to pick two locations and then swap them and keep a bit vector that said, these were swapped, and keep going until they’re all swapped. I remember my reaction being, “That’s stupid. That’s gotta be the stupidest thing in the world. It could take forever because there could be one pair that you never happen to choose.” I didn’t know enough then to say it’s n squared when it could have been order n . But I knew that that was just wrong. Then I was able to come up with, I think, the Knuth algorithm of swapping from 0 to 52 and then from 0 to 51 and so on—an order n algorithm. And I remember the teacher defending her approach. That helped me think, “Well, maybe I have an aptitude for this programming stuff.” It also helped me say, “Maybe teachers don’t really know everything.”

Seibel:Was it as soon as she described it that you just said, “Wow, this is wrong”? Or did you play with it for a while and then say, “Gosh it seems like we’re doing a lot of work here”?

Norvig:I think I noticed right away. It’s hard to know what I was really thinking back then but I think right away I noticed there’s a finite possibility that this might not terminate. I’m not sure I knew as much about the expected runtime.

I also remember finding my father’s back issues of Scientific American in the attic and going through them. There was this article by Christopher Strachey on software engineering in which he said that people are going to use these higher-order languages. And he had invented this language that there was never a compiler for—it was a paper language. And he said, “I’m going to write a checkers program using this language.” I remember reading that—it was the first nontrivial program I had ever read because in school we were just learning how to shuffle and so on. I read it again recently and the first thing I noticed was that there’s a bug in it. And it was great because you figure this is Christopher Strachey, he should know what he’s doing, and it’s Scientific American , they’ve got editors and so on—they should probably get those bugs out. But in the prose it says there’s a function makemovewhich takes a board position and returns a move and then you look in the code and there’s make-moveand it takes a board position and an extra parameter. Apparently they wrote the prose first and then they wrote the implementation. And they found out you can’t search infinitely deep so they added an extra parameter which was depth of search and you recurse down to a certain level and then you stop. They had added that in afterwards and hadn’t gone back and fixed the documentation.

Seibel:So that was the first interesting code you read; what was the first interesting program you wrote?

Norvig:I guess it was probably the Game of Life. It was actually an assignment for the class. I quickly did the assignment, and of course then we didn’t have the nice display screens. I didn’t have my 30-inch monitor—I had the teletype with the yellow paper. I said, “This is a waste, printing out one small field”—they probably wanted us to do a ten-by-ten field—“and then printing out the next one and the next one.” So I said, “Let’s print out five generations in a row.” And I remember that you couldn’t have threedimensional arrays in BASIC, and for some reason I couldn’t even have a bunch of two-dimensional arrays. It’s like they ran out of memory or something. So I had to figure out how am I going to have five or six across of these two-dimensional arrays, and that’s when I discovered bit fields.

Seibel:So given the constraints on memory, you rolled your own storage for that much data. Had you been taught about bit arrays and figured out how to apply them, or did you go digging through the manual and discovered, “Oh, look, here’s this PEEK and POKE” or whatever it was?

Norvig:Well, I was storing a zero or one in each of these locations, and I needed to store more stuff somewhere, and I said, “Oh, store other numbers there.” In fact, I don’t even remember if I did bit store. I might’ve done digits—decimal rather than binary—because the binary stuff hadn’t really been exposed to us in an interesting way. And then I got to add in things, like, is it repeating and if so, with what cycle. You couldn’t do that when you were just keeping one previous generation.