Levi's Lisp Log

Thoughts and links relating to Lisp and computer theory

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.

# Posted by: Levi at 12:00 AM on Tuesday, November 15, 2005
   Comments: (0) Categories: Programming

Post a Comment

Name:
Email:
URL:
What is the square root of 4?:
Comment: