Partial 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 $𝚙𝚛𝚘𝚐$ is seen as a mapping of input data into output data:

$𝚙𝚛𝚘𝚐 : I_{static} \times I_{dynamic} \to O,$

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

The partial evaluator transforms $⟨ 𝚙𝚛𝚘𝚐, I_{static} ⟩$ into ${𝚙𝚛𝚘𝚐}^{*} : I_{dynamic} \to O$ 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 the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura, is when $𝚙𝚛𝚘𝚐$ is an interpreter for a programming language.

If $I_{static}$ is source code designed to run inside that interpreter, then partial evaluation of the interpreter with respect to this data/program produces ${𝚙𝚛𝚘𝚐}^{*}$ , 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 ${𝚙𝚛𝚘𝚐}^{*}$ is effectively a compiled version of $I_{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 and in English in 1983. Glück (2009) proposed extending the Futamura projections to a fourth projection and beyond.

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

References

↑ "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.
↑ Robert Glück (11 January 2009), "Is there a fourth Futamura projection?", PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, doi:10.1145/1480945.1480954

External links

Applying Dynamic Partial Evaluation to dynamic, reflective programming languages

[1] "Professor Yoshihiko Futamura". fi.ftmr.info. Retrieved 2026-01-28.

[2] "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

[3] 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.

[4] Robert Glück (11 January 2009), "Is there a fourth Futamura projection?", PEPM '09: Proceedings of the 2009 ACM SIGPLAN workshop on Partial evaluation and program manipulation, doi:10.1145/1480945.1480954

v t e Compiler optimizations
Basic block	Peephole optimization Local value numbering
Loop	Automatic parallelization Automatic vectorization Induction variable Loop fusion Loop-invariant code motion Loop inversion Loop interchange Loop nest optimization Loop splitting Loop unrolling Loop unswitching Software pipelining Strength reduction
Data-flow analysis	Available expression Common subexpression elimination Constant folding Dead store elimination Induction variable recognition and elimination Live-variable analysis Upwards exposed uses Use-define chain Reaching definitions
SSA-based	Global value numbering Sparse conditional constant propagation
Code generation	Instruction scheduling Instruction selection Register allocation Rematerialization
Functional	Deforestation Tail-call elimination
Global	Interprocedural optimization
Other	Bounds-checking elimination Compile-time function execution Dead-code elimination Expression templates Inline expansion Jump threading Partial evaluation Profile-guided optimization
Static analysis	Alias analysis Array-access analysis Control-flow analysis Data-flow analysis Dependence analysis Escape analysis Pointer analysis Shape analysis Value range analysis

Partial evaluation

Futamura projections

See also

References

Further reading

External links