Mon May 4 21:03:55 CEST 2009

Futamura Projections

sigfpe is talking [1] about the Futamura projection.  I find it a bit
hard to follow so let's try to explain it here again.

( or not? )

I'm actually more interested in determining why partial evaluation is
not a trivial problem.  If it is just about folding constants, it
really shouldn't be too hard.

The problem as I understand is recursion: you can't unfold general
recursion as it will lead to infinite code structures.  At some point,
run-time recursion needs to be introduced to break the loop.  This is
mentioned in Wadler's paper [2] on deforestation (blazed treeless

As far as I understand, doing this in general can be quite involved.
Using transformations of higher order functions instead of raw
recursion seems a better approach.

[1] http://blog.sigfpe.com/2009/05/three-projections-of-doctor-futamura.html
[2] http://homepages.inf.ed.ac.uk/wadler/topics/deforestation.html
[3] http://www.itu.dk/people/sestoft/pebook/