Sun Sep 13 12:00:19 CEST 2009

Staging vs. Partial Evaluation

Explain the practical difference between the techniques of Staging and
Partial Evaluation, beyond the hand-waving ``PE is automated

A partial evaluator can be defined as a program that consumes a
general program and a fixed set of inputs, and produces a specific
program specialized to the fixed set.

Staging can be defined as performing this specialization manually, by
writing an explicit parameterized code generator that takes the fixed
set and produces the specialized program.

  - A staged program can express design (implementation) decisions
    that a partial evaluator cannot resolve due to 1. undecidability
    or 2. practical computational cost.

  - A staged program can give you extra guarantees about the
    specialized form of the program.  I.e. it can express the
    condition ``failure to implement as required''.

  - A (limited) partial evaluator (one that avoids recursion) can be
    used to augment staged programming.

TODO: give some explicit examples to support these vague claims.

What I'm really trying to work out is the use of staging for
control-flow guarantees (real-time programs, reduction to state
machines) combined with limited data-flow partial evaluation (= mostly
constant folding).

Glossing over a million details, there are essentially two forms of
PE: those that simplify expressions at compile time, and those that
modify arbitrary control structures.  The former are quite
straightforward to handle, but the latter (because they involve
unbounded recursion) are in general undecidable.  It is my thesis that
moving control flow into the expression domain (avoiding
non-termination in the form of _finite_ combinators) is the way to go.