Levi's Lisp Log

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.