Partial evaluation

Not to be confused with Partial application.

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 that run faster than the originals while being guaranteed to behave in the same way.

A computer program Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}} is seen as a mapping of input data into output data:

$${\texttt {prog}}:I_{\text{static}}\times I_{\text{dynamic}}\to O,$$

where $I_{\text{static}}$, the static data, is the part of the input data known at compile time.

The partial evaluator transforms $\langle {\texttt {prog}},I_{\text{static}}\rangle$ into Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}^* : I_\text{dynamic} \to O} by precomputing all static input at compile time. Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}^*} is called the "residual program" and should run more efficiently than the original program. The act of partial evaluation is said to "residualize" Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}} to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}^*} .

Futamura projections

A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura, is when Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}} is an interpreter for a programming language.

If Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_\text{static}} is source code designed to run inside that interpreter, then partial evaluation of the interpreter with respect to this data/program produces Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \texttt{prog}^*} is effectively a compiled version of Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_\text{static}} .

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

1. Specializing an interpreter for given source code, yielding an executable.
2. Specializing the specializer for the interpreter (as applied in #1), yielding a compiler.
3. Specializing the specializer for itself (as applied in #2), yielding a tool that can convert any interpreter to an equivalent compiler.

They were described by Futamura in Japanese in 1971 and in English in 1983.

PyPy's RPython and GraalVM's Truffle framework are examples of real-world JIT compilers that implement Futamura's first projection.

See also

• Compile-time function execution
• Memoization
• Meta-tracing
• Partial application
• Run-time algorithm specialisation
• smn theorem
• Strength reduction
• Template metaprogramming

References

General references

• Futamura, Y. (1999). "Partial Evaluation of Computation Process—An Approach to a Compiler-Compiler". Higher-Order and Symbolic Computation. 12 (4): 381–391. CiteSeerX 10.1.1.10.2747. doi:10.1023/A:1010095604496. S2CID 12673078.
• Consel, Charles; Danvy, Olivier (1993). "Tutorial Notes on Partial Evaluation". POPL '93: Proceedings of the 20th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. Association for Computing Machinery. pp. 493–501. CiteSeerX 10.1.1.114.7330. doi:10.1145/158511.158707. ISBN 0897915607. S2CID 698339.

External links

• Jones, Neil D.; Gomard, Carsten K.; Sestoft, Peter (1993). Partial Evaluation and Automatic Program Generation. Prentice Hall. ISBN 9780130202499.
• Danvy, O., ed. (1999). "Partial Evaluation and Semantics-Based Program Manipulation PEPM'99" (PDF). CiteSeerX 10.1.1.164.2284.
• Veldhuizen, Todd L. (1999). "C++ Templates as Partial Evaluation". PEPM'99. pp. 15–. arXiv:cs/9810010.
• Applying Dynamic Partial Evaluation to dynamic, reflective programming languages