Mon May 26 19:00:32 CEST 2008

What is Partial Evaluation?

Some clarification of terminology:

   * Currying
   * Partial Application
   * Partial Evaluation
   * Staging

These are all very related:

* Curry: move a parameter out of a function's parameter list to create
  a higher order function. I.e. for Scheme's multiple argument lambda:

     (lambda (a b) (+ a b)) -> (lambda (a) (lambda (b) (+ a b))).

  In a language like ML or Haskell the default representation is
  curried (all functions are unary).

* Partial Application: given a higher order (curried) function, obtain
  function of a lower order by applying one or more arguments.

* Staging: moving computations between compilation stages (i.e. from
  run-time to compile-time). A stage converts source code of a higher
  level form to a lower level form.

* Partial evaluation: Automatic staging based on input data available
  at compile time.

Partial application and staging are somewhat related (in a functional
setting, they are both about beta-reductions), but differ mainly in
the way the result of the reduction is represented.  Staging performs
substitution on expression _syntax_ while partial application
typically creates an abstract closure object comprised of a
representation of the original un-reduced expression and an
environment of name->value bindings, where final reduction (execution
of base-machine code) only happens when _all_ variables are available.

Partial evaluation makes most sense for functional languages, where
evaluation order can be easily manipulated.  To apply it to imperative
languages requires the identification of a functional subset.

In a language based on function composition, partial evaluation is a
trivial operation based only on associativity of function composition.
This the main idea behind Staapl's code representation.

In the face of unrestricted recursion, the main problem of automatic
staging is to decide what NOT to evaluate, to avoid infinite expansion
size.  Therefore it is useful to restrict the language a bit, the main
idea being that full turing-completeness is not always necessary, and
can make automatic specialization simpler.