Sun Jun 19 10:42:04 CEST 2011

Partial Evaluation

This book[1] is from 1993.  We're almost 20 years later and I don't
really see any obvious solution.  I.e. there's no GNU PE.  It seems
that the recent (+- 5 years) literature on staging is fueled by the
impracticality of PE.  In the book[1] there are 3 significant
remaining problems mentioned:

1. Need for annotation to _not_ unfold loops/recursions to prevent
   large or infinite programs.

2. Need for the user to understand the output program.

3. Need for the user to understand the working of the PE.

Looking specifically at compilers generated from interpreters, the
following attributes have not yet been automated (in the book[1] from

1. Changing language style, i.e. expressions -> sequential machine code

2. Sequentializing naturally non-sequential processes, i.e. using a
   stack for evaluation.

3. Lowering the level of abstraction (embedding?)

4. Devising low-level data structures for implementing high-level

5. Value management.

This list seems a bit too arbitrarily detailed to me.  What it seems
to say is that a PE can't "invent stuff".  I.e. it can't create extra
concreteness to embed non-implementable features into different,
concrete code and data structures.

In other words, to draw the analogy with manually solving algebraic
equations: it can't insert an operation and its inverse "at the right
spot".  There is still some un-ecodable (un-encoded) human
intelligence necessary to dream up effective structures.

[1] http://www.dina.kvl.dk/~sestoft/pebook/