Levi's Lisp Log

Software and Concurrency

As I was doing research for a paper, I hunted down Herb Sutter's article The Free Lunch Is Over: A Fundamental Turn Towards Concurrency in Software to find some passages that supported my thesis. There was quite a buzz about this article when it appeared in Dr. Dobb's Journal and C/C++ Users Journal earlier this year, as it seemed to capture and clearly explain the feeling so many people had been getting while watching what the CPU manufacturers have been doing lately. Everything's going multi-core, even video game processors.

Following a few links, I found that Sutter has written (with James Larus) another article on the subject, this time with a greater focus on software. It's Software and the Concurrency Revolution at the ACM Queue, and it's a broad look at the deficiencies of current programming languages and practices in the face of concurrency, and what sort of changes need to be made to face the future he sees, in which individual processor cores don't get much faster than they are today.

I'm convinced that Sutter's take on the future is at least mostly right, and these articles ought to be required reading for anyone who wants to take up or continue writing software.

Futamura Projection

Every once in a while you come across something that just blows your mind. Having been reading textbooks and research papers on programming languages for a while, I thought I had already had most of the mind-blowing experiences to be had in that domain, but I couldn't have been more wrong.

Partial evaluation is an optimization technique in which the compiler analyzes the program to find any static portions of code and pre-evaluate them. In the 1970s, Yoshihiko Futamura described what is now known as Futamura Projection. There are three levels of Futamura Projection. The first takes an interpreter and a program as input and returns what is essentially a compiled version of the program. The second applies an interpreter to itself and creates a compiler for that languages. The third, and most mind-bending, takes itself twice as input and creates a compiler generator, which is a program that takes an interpreter as input and returns a compiler.

I have no idea yet what sort of practical use the Futamura Projection has, but it is at least a theoretically fascinating concept.

Fundamental Idea of Programming

According to Hal Abelson in his foreword to the book Essentials of Programming Languages, the most fundamental idea in computer programming is this:

The interpreter for a computer language is just another program.

On the face of it, this seems not to apply to compiled languages, or programs written in machine code. But, upon reflection, it does. The interpreter for these languages is the microcode on the CPU, and the interpreter for the microcode is a logic program expressed in physical transistors.

In any case, the concept of an interpreter program is a powerful one, and is certainly worth study and mastery. As Sussman says, you will become "a designer of languages rather than only a user of languages, [ . . . ] a person who chooses the rules by which languages are put together, rather than only a follower of rules that other people have chosen."

Sussman at OOPSLA

Gerald Sussman is one of the contemporary luminaries of the field of computing, so I'm always interested to hear what he has to say. His most recent talk, delivered in San Diego last week at OOPSLA, defended the idea that programming is a good medium for expressing ideas that we don't yet fully understand. It forces us to translate from theory to practice in a methodical fashion.

The abstract for his talk can be found at the OOPSLA site, and a great summary and response to it was written up by Eugene Wallingford at his blog, Knowing and Doing.

Analytical Engine Emulator

In 1837, Charles Babbage wrote a memoir entitled On the Mathematical Powers of the Calculating Engine. In this paper, he described a machine, steam powered and made of brass, that would be able to store and run general-purpose programs. While it was never fully constructed, Babbage's Analytical Engine was the first computer to ever be designed.

Usually computer emulators are designed to mimic computers that actually existed, but fortunately for the curious, someone has put together a Java-based Analytical Engine Emulator for the really-retro computing enthusiasts to play with. I haven't got the time nor inclination to write programs for it myself, but I think Babbage would appreciate his idea being brought to virtual fruition.

Speaking of programming the thing—although it was never built, it did have programs written for it. In fact, the very first was written by Ada Lovelace, who thus has the distinction of being the first computer programmer. It is sadly ironic that a field pioneered by women such as Ada and Grace Hopper, inventor of the first compiler, now finds itself with very few women practicing its arts.