Partial evaluation
Encyclopedia
In computing
, partial evaluation is a technique for several different types of program optimization
by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way. More advanced uses include compiling by partially evaluating an interpreter with the program to be compiled as its input; generating compilers by partially evaluating a partial evaluator with an interpreter for the source language concerned as its input; and finally generating a compiler-generator by partially evaluating a partial evaluator with itself as its input.
A computer program
, prog, is seen as a mapping of input data into output data:
, the static data, is the part of the input data known at compile time.
The partial evaluator transforms
into
by precomputing all static input at compile time. 
is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" 
to 
.
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:
Computing
Computing is usually defined as the activity of using and improving computer hardware and software. It is the computer-specific part of information technology...
, partial evaluation is a technique for several different types of program optimization
Optimization (computer science)
In computer science, program optimization or software optimization is the process of modifying a software system to make some aspect of it work more efficiently or use fewer resources...
by specialization. The most straightforward application is to produce new programs which run faster than the originals while being guaranteed to behave in the same way. More advanced uses include compiling by partially evaluating an interpreter with the program to be compiled as its input; generating compilers by partially evaluating a partial evaluator with an interpreter for the source language concerned as its input; and finally generating a compiler-generator by partially evaluating a partial evaluator with itself as its input.
A computer program
Computer program
A computer program is a sequence of instructions written to perform a specified task with a computer. A computer requires programs to function, typically executing the program's instructions in a central processor. The program has an executable form that the computer can use directly to execute...
, prog, is seen as a mapping of input data into output data:
, the static data, is the part of the input data known at compile time.The partial evaluator transforms
into
by precomputing all static input at compile time. is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" to .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 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:
- Specializing an interpreter for given source code, yielding an executable
- Specializing the specializer for the interpreter (as applied in #1), yielding a compiler
- Specializing the specializer for itself (as applied in #2), yielding a tool that can convert any interpreter to an equivalent compiler
See also
- Run-time algorithm specialisationRun-time algorithm specialisationIn computer science, run-time algorithm specialization is a methodology for creating efficient algorithms for costly computation tasks of certain kinds...
- MemoizationMemoizationIn computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...
- Strength reductionStrength reductionStrength reduction is a compiler optimization where expensive operations are replaced with equivalent but less expensive operations. The classic example of strength reduction converts "strong" multiplications inside a loop into "weaker" additions – something that frequently occurs in array...
- Smn theorem
- Template metaprogrammingTemplate metaprogrammingTemplate metaprogramming is a metaprogramming 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. The output of these templates include compile-time constants, data structures, and...
- PyPyPyPyPyPy is a Python interpreter and JIT compiler. PyPy focuses on speed, efficiency and 100% compatibility with the original CPython interpreter.- Details and motivation :...
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