Partial evaluation
|
|
Partial Evaluation is a program optimization by specialization technique.
A computer program is seen as a mapping prog: {Istatic, Idynamic} <math>\rightarrow<math> O of input data into output data. Istatic is the part of the input data known at compile time.
The partial evaluator transforms {prog, Istatic} into prog* i.e. precomputes all static input at compile time. prog* is called the residual program.
prog: {Istatic, Idynamic} <math>\rightarrow<math> O becomes prog*: Idynamic <math>\rightarrow<math> O which in general runs more efficiently.
A particularly interesting example of this is when prog is an interpreter for a programming language. If Istatic 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 Istatic. 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
See also C++ Template metaprogramming
- C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99) (http://osl.iu.edu/~tveldhui/papers/pepm99/)
- NEIL D. JONES, An Introduction to Partial Evaluation, ACM Computing Surveys, Vol. 28, No. 3, September 1996 (http://www.futamura.info.waseda.ac.jp/~futamura/PapersToRead/jones.pdf)
- partial-eval.org - a large "Online Bibliography of Partial Evaluation Research".