In computing, partial evaluation is a technique for program optimization by specialization. RAM (Random Access Memory) Look up computing in Wiktionary, the free dictionary. ... In computing, optimization is the process of modifying a system to make some aspect of it work more efficiently or use fewer resources. ... Specialization is an important way to generate propositional knowledge, by applying general knowledge, such as the theory of gravity, to specific instances, such as when I release this apple, it will fall to the floor. Specialization is the opposite of generalization. ...

A computer program is seen as a mapping prog of input data into output data: A computer program is a collection of instructions that describe a task, or set of tasks, to be carried out by a computer. ...

prog: {I_static, I_dynamic} 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} O becomes prog*: I_dynamic O which in general runs more efficiently.

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. The 1970s decade refers to the years from 1970 to 1979, also called The Seventies. ...

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:

1. Compiling by specializing an interpreter
2. Compiler generation by self-application
3. Compiler generator generation by double self-application

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

See also

• C++ Template metaprogramming
• Run-time algorithm specialisation

C++ (pronounced see plus plus, IPA: ) is a general-purpose, programming language with high-level and low-level capabilities. ... Template metaprogramming is a programming technique in which templates are used by a compiler to generate temporary source code, which is merged by the compiler with the rest of the source code and then compiled. ... In computer science, Run-time algorithm specialisation is a methodology for creating efficient algorithms for costly computation tasks of certain kinds. ...

External links

• Neil D. Jones, Carsten K. Gomard, and Peter Sestoft: Partial Evaluation and Automatic Program Generation (1993) Book, full text available online.
• partial-eval.org - a large "Online Bibliography of Partial Evaluation Research".
• 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
• C++ Templates as Partial Evaluation, 1999 ACM SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation (PEPM'99)
• C++ Templates as Partial Evaluation a different version including Catat (pdf)
• Applying Dynamic Partial Evaluation to dynamic, reflective programming languages