Partial evaluation - Wikipedia
Jump to content
Search
Search
Donate
Create account
Log in
Personal tools
Donate
Create account
Log in
Partial evaluation
4 languages
Français<br>Italiano<br>日本語<br>Русский
Edit links
From Wikipedia, the free encyclopedia
Technique for program optimization
Not to be confused with Partial application.
This article includes a list of general references, but it lacks sufficient corresponding inline citations . Please help to improve this article by introducing more precise citations. (May 2013) (Learn how and when to remove this message)
Evaluation strategies<br>Eager evaluation
Lazy evaluation
Partial evaluation
Remote evaluation
Short-circuit evaluation
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
prog
{\displaystyle {\texttt {prog}}}
is seen as a mapping of input data into output data:
prog
static
dynamic
{\displaystyle {\texttt {prog}}:I_{\text{static}}\times I_{\text{dynamic}}\to O,}
where
static
{\displaystyle I_{\text{static}}}
, the static data, is the part of the input data known at compile time.
The partial evaluator transforms
prog
static
{\displaystyle \langle {\texttt {prog}},I_{\text{static}}\rangle }
into
prog
dynamic
{\displaystyle {\texttt {prog}}^{*}:I_{\text{dynamic}}\to O}
by precomputing all static input at compile time.
prog
{\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"
prog
{\displaystyle {\texttt {prog}}}
to
prog
{\displaystyle {\texttt {prog}}^{*}}
Futamura projections<br>[edit]
A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura,[1] is when
prog
{\displaystyle {\texttt {prog}}}
is an interpreter for a programming language.
If
static
{\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
prog
{\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
prog
{\displaystyle {\texttt {prog}}^{*}}
is effectively a compiled version of
static
{\displaystyle I_{\text{static}}}
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.
They were described by Futamura in Japanese in 1971[2] and in English in 1983.[3]
PyPy's RPython and GraalVM's Truffle framework are examples of real-world JIT compilers that implement Futamura's first projection.
See also<br>[edit]
Compile-time function execution
Memoization
Meta-tracing
Partial application
Run-time algorithm specialisation
smn theorem
Strength reduction
Template metaprogramming
References<br>[edit]
^ "Professor Yoshihiko Futamura". fi.ftmr.info. Retrieved 2026-01-28.
^ "Partial Evaluation of Computation Process --- An approach to a Compiler-Compiler", Transactions of the Institute of Electronics and Communications Engineers of Japan, 54-C : 721–728, 1971
^ Futamura, Y. (1983). "Partial computation of programs". RIMS Symposia on Software Science and Engineering. Lecture Notes in Computer Science. Vol. 147. Springer. pp. 1–35. doi:10.1007/3-540-11980-9_13. hdl:2433/103401. ISBN 3-540-11980-9.
General references<br>[edit]
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<br>[edit]
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....