Third Futamura Projection

PartialEvaluation to the third order, with communications support.

See http://www.cubiclemuses.com/cm/blog/archives/000419.html

The 3rd projection is what you get when a partial evaluator (specializer) applies itself to itself. The output is a CompilerCompiler?, a program which takes as input an interpreter and produces as output a compiler.

See http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html

Currently they are not very efficient. A hand-written CompilerCompiler? is usually more efficient than one produced by specializing the specializer on the specializer, and hand-written compilers are usually more efficient than compilers output by a CompilerCompiler?, regardless of whether it was hand-written or generated.

A CompilerCompiler? is still very useful though, since it is usually easier to write an interpreter than a compiler, but interpeters are usually slower than compilers. With a CompilerCompiler?, you can have your cake and eat it too.

Additionally, you can chain languages together. For example, suppose you write an interpreter for a high level language in a low level language. Then you write an interpreter for a higher level language in the high level language. Normally the highest level language would be very very slow, due to multiple layers of interpretational overhead. But multiple applications of a CompilerCompiler? can remove most of that interpretational overhead, and so you get the expressiveness of a high level language but the performance of a low level language. Dybkjaer used this approach to write programs in the ultra high level language of category theory.

The language chaining technique is also extremely useful for domain specific languages, which are usually too special purpose to warrant the effort of creating a compiler for that language. Morgensen, for instance, used partial evaluation techniques to compile ray-tracing scenes, and got an 8-12x speedup.


CategoryTypeTheory

EditText of this page (last edited April 25, 2013) or FindPage with title or text search