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

Seibel:So you made this standard set of key-bindings. How did that go over? Were people happy with it?

Steele:Well, people worked through it. Then I then sat down and proceeded to begin an implementation of it. And we had another idea that came into the mix at the same time and it was the idea that you could make TECO macros run a lot faster if you squeezed out the spaces and deleted all the comments. The way the TECO interpreter worked, interpreting one character at a time, when you encountered a comment it had to spend the time skipping over that comment. So we had this idea of this very primitive TECO compiler that was mostly just squeezing out the white space and the comments and doing a few other minor things to put it in a form that would run a little bit faster.

So I began in an initial way to try to construct a version of this macro compressor, which I think was actually based on an earlier idea that Moon had had. I don’t think I originated that idea. I began to think about how to organize the initial dispatch and organize some of the first few routines borrowing on the existing implementations of other macro packages—I was trying to synthesize them. And about that point Stallman came along and said, “What are you doing? This looks interesting.” He immediately jumped in and he could implement ten times as fast as I could, partly because he knew TECO inside out.

So I worked seriously on the implementation of Emacs probably for only about four or six weeks. At which point it became clear that Stallman understood what the program was. I wanted to get back to doing graduate student things. So Stallman did the other 99.999 percent of the work. But I played a role in catalyzing it and beginning the implementation.

Seibel:On a different subject, academic computer science is very mathematical these days. How important is it for working programmers to be able to understand, say, the math in Knuth? Versus saying, “I need to sort things; I’m going to flip through Knuth and skip to where he says, ‘This is the best algorithm’ and implement that”?

Steele:I don’t know. There are parts of Knuth that I don’t understand because I don’t have the mathematical training. Particularly if it involves higher or continuous math. I’m a little weaker on that. I think my strengths are in things like combinatorics and permutations, group theory, things like that. And I find myself using that over and over and over again. Maybe that’s because that’s the particular hammer I have at hand. I don’t think that every programmer needs that. But I think that mathematics formalizes concepts that programmers do need to work with every day.

I’ll give you an example from my recent programming-language work on parallel languages, this Fortress project that I’ve got going. Suppose you want to add up a bunch of numbers. Well, one thing you can do is you can initialize a register to zero and add in the numbers one at a time—a classic sequential technique.

Notice that this depends on the addition operation having an identity. You needed to start with zero. Trivial little observation, but it’s there.

Now here’s another strategy—you can lay out all the numbers in a row and then add them up pairwise, giving you a bunch of sums, and keep adding pairwise until you’ve only got one number left. And of course if at any point you’ve got an odd number of them you just leave that one over extra and let it go to the next stage and so forth. Well, that works fine, too. And if you’re using floating-point numbers it may actually give you a little bit better accuracy, although with the bookkeeping overhead it’s sometimes not worth it.

Notice that this will give you the same answer, at least if you’re working with integers, as starting with zero and adding them one at a time. This depends on the fact that addition is associative. In other words, it doesn’t matter in what way you group the numbers.

And then there’s a third strategy. Suppose you’ve got a bunch of processors. You could parcel out the pairs to the processors and distribute that work. The “start with zero and add them one at a time” algorithm is hard to parallelize, but with the bunching in pairs, you’ve in effect made a tree and you can assign processors different parts of the tree, and they can do their parts independently, and only at the end do they need to interact and you get the sum.

OK, so that’s cool. Here’s another parallel strategy that’s more like the first one: pick some register and initialize it to zero, and then let processors compete for grabbing numbers and adding them into that common place. This involves questions of synchronization, but you will still get the same answer. But this depends on addition being both associative and commutative. That is, not only does it not matter how you group the numbers, it also doesn’t matter in what order you process the numbers.

Mathematicians have big, scary words like “identity” and “associativity” and “commutativity” to talk about this stuff—it’s their shorthand. But programmers need to know about ideas like, it doesn’t matter in what order you do it. And they need to know about ideas like, it’s OK if you regroup things. So to that extent I claim that mathematical ideas are important at some level to programmers.

Seibel:Obviously that’s a good example to give because anyone who understands arithmetic can understand it. But do you find that there are kind of higher-level concepts that come back into programming in the same way?

Steele:Now suppose I’m generating a report. The typical thing is you make a bunch of print statements and you depend on doing them in order and things get printed out in the order you said. Well, in this multicore world maybe I would like to break up the generation of the report and parcel it out to processors. Well, how about concatenating strings? Can I use the same techniques I used for adding up numbers? Turns out it is associative but not commutative—that tells me exactly which tricks will work for the strings and which ones won’t. As a language designer worrying about designing parallel programming languages, I find these concepts and a vocabulary for them very useful.

Seibel:Speaking of being a language designer, how have your ideas about language design changed over time?

Steele:I think that the biggest change in my thinking is what I set down in that talk “Growing a Language” at OOPSLA almost ten years ago, in 1998. Back in the ’70s people would invent languages and make a complete design and implement it and you’d be done. Or you wouldn’t be done, but you had this idea that there is this complete thing.

So Pascal was an invention. Things were in it for a reason and things were left out for a reason but it was a complete design. And if it turned out that it wasn’t complete—if it turned out that string processing wasn’t that great, well, too bad: Wirth had designed the language. And PL/I got designed and Ada got designed. And maybe Ada and C++ were close to the last of that generation. And C++ not so much, because it did sort of evolve over time.

I realized as languages got more complicated they were really too big to design all at once and that languages would necessarily from now on undergo evolution because they were too big to design all at once or to implement all at once. And that caused a change in how I approached programming-language design and thinking about it.

Seibel:So you think Java was not designed that way?

Steele:I think maybe Java was not and should have been. Java has evolved through the Java Community Process. That has addressed more API than core language issues. And while features have been added to the language over the last 12 or 13 years, I think the team that designed Java in the early ’90s thought they were designing a complete language for a specific selfcontained purpose. You know, they were aiming at set-top boxes.