Partial evaluation

In computing, partial evaluation is a technique for program optimization by specialization.

A computer program, "prog", is seen as a mapping of input data into output data::$prog\; :\; I\_\{static\}\; imes\; I\_\{dynamic\}\; o\; O$

$I\_\{static\}$, the "static data", is the part of the input data known at compile time.

The partial evaluator transforms $langle\; prog,\; I\_\{static\}\; angle$ into $prog^*\; :\; I\_\{dynamic\}\; o\; O$ by precomputing all static input at compile time. $prog^*$ is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" $prog$ to $prog^*$.

Futamura projections

A particularly interesting example of this, first described in the 1970s by Yoshihiko Futamura, is when "prog" is an interpreter for a programming language.

If I_static is source code designed to run inside said interpreter, then partial evaluation of the interpreter with respect to this data/program produces "prog*", a version of the interpreter that only runs that source code, is written in the implementation language of the interpreter, does not require the source code to be resupplied, and runs faster than the original combination of the interpreter and the source. In this case prog* is effectively a compiled version of I_static.

This technique is known as the first Futamura projection, of which there are three:

#Compiling by specializing an interpreter
#Compiler generation by self-application
#Compiler generator generation by double self-application

References

* Reprinted in "Higher-Order and Symbolic Computation" 12 (4): 381–391, 1999, with a foreword.
*

ee also

* Run-time algorithm specialisation
* Smn theorem
* Template metaprogramming

External links

* [http://www.itu.dk/people/sestoft/pebook/ Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: "Partial Evaluation and Automatic Program Generation" (1993)] Book, full text available online.
* [http://partial-eval.org partial-eval.org] - a large "Online Bibliography of Partial Evaluation Research".
* [http://www.brics.dk/~pepm99/ 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)]
* [http://osl.iu.edu/~tveldhui/papers/pepm99/ C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)]
* [http://arxiv.org/pdf/cs.PL/9810010 C++ Templates as Partial Evaluation] a different version including Catat (pdf)
* [http://people.csail.mit.edu/gregs/dynamic-pe.html Applying Dynamic Partial Evaluation to dynamic, reflective programming languages]