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.
   Comments: (0) Categories: Programming