Tue May 5 09:25:25 CEST 2009


Now, the question is: is this a specializer that can take itself as
input?  Do the works of mister Futamura have any significance here?
Can the theory of partial evaluation be used to shed some light here?

The following is from [1] page 43.  PE is a partial evaluator, prog is
a program, const is its static data and data is its dynamic data:

  PE(prog,const)(data) = prog(const,data)

Here PE(prog,const) = prog' is a specialized program.

The 3 Futamura projections are then about prog being an interpreter
int, with the static data const = prog.  The first projection combines
the interpreter and the program into a compiled program.

  PE(int,prog)(data) = int(prog,data)
  +----------+ compiled program

When this specialization happens a lot with int = constant, the PE
itself can be specialized to the interpreter resulting in a compiler.

  PE(PE,int)(prog)(data) = int(prog,data)
  +--------+       compiler
  +--------------+ compiled program

Now, if we have to do this for a lot of different interpreters, we can
specialize the PE(PE,int) invokation to the static PE giving a
compiler generator PE(PE,PE)

  PE(PE,PE)(int)(prog)(data) = int(prog,data)
  +-------+            compiler generator
  +------------+       compiler
  +------------------+ compiled program

Anyways, I'd like to read some more of this [2].  It seems to contain
some answers about why partial evaluation isn't trivial.  On page 42
in [1] there is some simple answer to the non-triviality: partial
evaluators need to be conservative to ensure termination.

[1] http://thyer.name/phd-thesis/
[2] http://www.itu.dk/people/sestoft/pebook/