Partial evaluation

From Wikipedia, the free encyclopedia

Programming evaluation
Eager Function Lazy Minimal Partial Remote Strategy

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

A computer program is seen as a mapping prog of input data into output data:

prog: {I_static, I_dynamic} $\rightarrow$ O

I_static, the static data, is the part of the input data known at compile time.

The partial evaluator transforms {prog, I_static} into prog* i.e. precomputes all static input at compile time. prog* is called the "residual program", and the act of partial evaluation is said to "residualize" prog to prog*.

prog: {I_static, I_dynamic} $\rightarrow$ O becomes prog*: I_dynamic $\rightarrow$ O which in general runs more efficiently.

1 Futamura projections
2 References
3 See also
4 External links

[edit] 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

[edit] References

Yoshihiko Futamura. Partial Evaluation of Computation Process -- An Approach to a Compiler-Compiler Systems . Computers . Controls 2(5):45-50, 1971. Reprinted in Higher-Order and Symbolic Computation 12(4):381-391, 1999, with a foreword
Charles Consel and Olivier Danvy. Tutorial Notes on Partial Evaluation Proceedings of the Twentieth Annual ACM Symposium on Principles of Programming Languages pp. 493-501, 1993