Partial evaluation

Partial evaluationMain

Community hub

Partial evaluation

7 pages, 0 posts

0 subscribers

Recent from talks

Be the first to start a discussion here.

Recent from talks

Be the first to start a discussion here.

Contribute something

About hubMembersContent overviewUpdatesRules

Main reference articles

Partial evaluation

View on Wikipedia

from Wikipedia

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
Eager evaluation Lazy evaluation Partial evaluation Remote evaluation Short-circuit evaluation
v t e

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 ${\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 ${\texttt {prog}}^{*}:I_{\text{dynamic}}\to O$ by precomputing all static input at compile time. ${\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" ${\texttt {prog}}$ to ${\texttt {prog}}^{*}$ .

Futamura projections

[edit]

A particularly interesting example of the use of partial evaluation, first described in the 1970s by Yoshihiko Futamura,^[1] is when ${\texttt {prog}}$ is an interpreter for a programming language.

If $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 ${\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 ${\texttt {prog}}^{*}$ is effectively a compiled version of $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.

References

[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

[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

[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. pp. 15–. arXiv:cs/9810010.
Applying Dynamic Partial Evaluation to dynamic, reflective programming languages

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

Revisions and contributors Edit on Wikipedia Read on Wikipedia

View on Grokipedia

from Grokipedia

Partial evaluation is a program transformation technique in computer science that specializes a given program with respect to known static inputs, producing a more efficient residual program tailored to the remaining dynamic (unknown) inputs by precomputing as much as possible at specialization time.^[1] This process decomposes the program's computation into static and dynamic components, often through binding-time analysis, enabling optimizations that eliminate interpretive overhead and reduce runtime complexity.^[1] The technique draws from theoretical foundations in recursion theory, such as Kleene's s-m-n theorem, which formalizes the parameterization of computable functions.^[1] The concept was formalized by Yoshihiko Futamura in his 1971 paper, where he proposed partial evaluation as a method to automatically derive a compiler from an interpreter by specializing the interpreter with respect to a source program, thus bridging formal semantics and practical compilation.^[2] Futamura's framework introduced the Futamura projections, a series of three self-applications of a partial evaluator: the first projection generates a compiler from an interpreter and source code; the second produces a compiler generator (cogen) by specializing the partial evaluator on itself; and the third yields a compiler generator generator through further self-application.^[1] These projections highlight partial evaluation's potential for automating program generation, with practical implementations emerging in the 1980s, including the first self-applicable partial evaluator for functional languages developed by Neil D. Jones, Peter Sestoft, and Harald Søndergaard in 1984.^[1] Partial evaluation serves as a unifying paradigm for various optimization strategies, encompassing compiling, interpretation, and the automatic creation of program generators, while differing from manual staging techniques by emphasizing full automation.^[3] Key challenges include ensuring termination of the specialization process and controlling the size of the residual program, particularly in non-oblivious settings where dynamic data influences control flow, often addressed through online (drive-time) or offline (analysis-driven) strategies.^[1] Applications span compiler construction, where it achieves speedups of up to 13.7 times in interpreter specialization; scientific computing and simulations, such as ray tracing with 8-12x performance gains; database query optimization; and domains like neural networks and string matching algorithms (e.g., Knuth-Morris-Pratt).^[1] Tools like Similix and Logimix have demonstrated its portability across languages, including Scheme and Prolog, underscoring its role in metaprogramming and higher-order function handling.^[1]

Fundamentals

Definition

Partial evaluation is a program transformation technique that specializes a program with respect to some known inputs, known as static inputs, to produce a residual program that efficiently handles the remaining unknown inputs, referred to as dynamic inputs.^[1] This process involves partially executing the program on the static inputs at specialization time, folding constants and simplifying computations where possible, while generating code for the dynamic parts to be evaluated at runtime.^[1] Unlike full evaluation, which requires all inputs to be available to compute a final result, partial evaluation operates with only a subset of inputs known, deferring the rest to avoid complete execution and instead producing an optimized executable tailored to the static context.^[1] To illustrate, consider a simple arithmetic expression evaluator defined as the lambda term

\lambda x \, y . x + y \times 2

. When partially evaluated with the static input

y = 3

, it specializes to the residual program

\lambda x . x + 6

, where the multiplication by 2 and addition of 3 are precomputed, eliminating redundant operations for any dynamic

x

.^[1] This specialization reduces computation time by avoiding repeated evaluations of static elements, results in smaller code size through constant folding and dead-code elimination, and enables optimizations such as loop unrolling or inlining that may not be feasible in the general-purpose program.^[1] Formally, given a program

P

that computes a function

f(s, d)

where

s

are static inputs and

d

are dynamic inputs, partial evaluation produces a residual program

P

such that

P[s](d) = P(s, d)

for any

d

, without re-evaluating the static parts during runtime execution of the residual program.^[1] This concept, originally proposed by Yoshihiko Futamura, underpins theoretical formalizations like the Futamura projections, which demonstrate practical applications such as automatic compiler generation.^[4]

Binding-time distinctions

In partial evaluation, binding time refers to the stage at which a value in a program becomes known or computed.^[1] This distinction is fundamental to classifying program components for specialization, ensuring that computations are performed either during the specialization phase or deferred to the execution of the resulting residual program.^[5] Values are categorized into three primary binding times: static, dynamic, and future. Static values are those known completely at specialization time, allowing immediate evaluation and optimization without generating residual code.^[1] For instance, in an expression like let x = 5 in x + 3, both operands are static, enabling full reduction to 8 during specialization. Dynamic values, in contrast, remain unknown until the runtime of the residual program and thus generate corresponding code fragments rather than computed results. An example is a function call where one argument is dynamic, such as add(x, y) with x static but y dynamic, which residuals as a call to the original function. Future values arise from mixtures of static and dynamic computations, often represented using constructs like "lift" to delay evaluation until needed, as in symbolic representations where a dynamic value is wrapped for later static treatment.^[1]^[5] Programs are annotated with binding-time information through two main techniques: manual annotation and automatic inference. Manual annotation involves explicitly marking variables and expressions as static or dynamic, often using two-level syntax to distinguish stages, which guides the partial evaluator in constructing an annotated program for processing.^[1] Automatic inference, typically via abstract interpretation over a lattice of binding times (e.g., {S, D} with S ⊆ D), propagates signatures through the program to compute classifications conservatively, ensuring safety by over-approximating dynamic behaviors.^[1]^[5] These methods enable the partial evaluator to apply program specialization by identifying opportunities for transformation. Binding-time errors occur when classifications are mismatched, leading to incorrect or inefficient specialization. For example, attempting to unfold a loop with a dynamic bound treats the iteration as static, potentially generating infinite code if the bound is unbounded at specialization time. Conversely, classifying a static loop as dynamic misses optimization, resulting in residual code that retains interpretive overhead. Such errors are mitigated by congruence rules in binding-time analysis, which enforce consistent treatment of subexpressions to avoid termination issues or dead code.^[1] These distinctions play a crucial role in enabling key transformations during specialization. Unfoldings expand static function calls inline, reducing call overhead; reductions simplify static arithmetic or conditional expressions to constants; and eliminations remove unreachable dynamic code or unused static computations, enhancing efficiency.^[1] Without accurate binding-time information, these optimizations cannot be applied selectively, limiting the benefits of partial evaluation.^[5] Specialization strategies further differentiate based on binding-time contexts: monovariant and polyvariant. Monovariant specialization generates a single residual version per program point, suitable for uniform static/dynamic patterns but potentially conservative for mixed cases. Polyvariant specialization, however, produces multiple residuals for the same code when encountered in differing contexts—such as varying static arguments—allowing aggressive optimizations like full loop unrolling for specific static bounds while preserving generality elsewhere. This approach improves accuracy but risks code bloat if not controlled.^[1]^[6]

Historical development

Origins in the 1970s

The concept of partial evaluation first took shape in the early 1970s through theoretical and practical explorations in programming language theory. A seminal contribution came from Yoshihiko Futamura in 1971, who proposed using partial evaluation of an interpreter with respect to a specific program to automatically generate a dedicated compiler, establishing a foundational link between interpretation and compilation.^[7] This idea, later known as the first Futamura projection, highlighted partial evaluation's potential for automatic program generation. Concurrently, Danish computer scientists at the University of Copenhagen's Department of Computer Science (DIKU), including Neil D. Jones, began investigating related concepts, drawing heavy influence from Lisp's homoiconicity—which treats code as data—and functional programming paradigms like lambda calculus and recursion schemes.^[8] These influences facilitated experiments in program transformation, where static knowledge about inputs could be folded into code at compile time to produce more efficient residuals. A key publication advancing these ideas appeared in 1976 with the work of L. Beckman, A. Haraldsson, Ö. Oskarsson, and E. Sandewall, who implemented a partial evaluator for a practical subset of Lisp, incorporating features like imperative constructs and property lists.^[9] Their system demonstrated partial evaluation's utility in meta-programming by specializing functions with partial inputs, enabling optimizations such as unfolding recursive calls and eliminating runtime checks, though limited by Lisp's side effects. At DIKU, early experiments by Jones and collaborators explored precursors like mixfix notation for flexible syntax in program generators and attribute grammars for analyzing binding times in flow-chart languages, laying groundwork for distinguishing static and dynamic computations.^[8] These efforts were driven by the era's challenges in interpreter design, particularly the "compilation problem"—the inefficiency of running high-level interpreters on specific programs without tailored optimizations. The primary motivations in the 1970s centered on automating the generation of efficient code from interpretive specifications, addressing the gap between high-level descriptions and machine-executable binaries. Researchers sought to leverage partial evaluation to specialize interpreters, reducing interpretive overhead by propagating static data through the computation. Parallel efforts, such as the CIP (Computer-Aided Intuition-Guided Programming) project in Germany, explored related transformational techniques for program synthesis during this period.^[8] At DIKU, this work marked the transition from theoretical schemata to practical systems, emphasizing functional languages' suitability for self-applicable transformations.

Key advancements and researchers

In the 1980s, significant progress was made in developing practical partial evaluators for functional languages, with Olivier Danvy advancing type-directed techniques that simplified the generation of residual programs from compiled code.^[10] Danvy's work, beginning with his 1986 dissertation on analytical approaches to programs as data, laid groundwork for automatic partial evaluation in languages like Scheme by integrating type information to guide specialization.^[11] Collaborating with Karoline Malmkjær in the early 1990s, Danvy extended these ideas to eta-expansion strategies that improved the efficiency of partial evaluators without requiring explicit continuation-passing style conversions, enabling more robust handling of higher-order functions in functional programs.^[12] The development of the Schism partial evaluator in the late 1980s and early 1990s represented a key milestone in self-applicable specializers, demonstrating how mixed computation could produce efficient compilers from interpreters for higher-order applicative languages like a subset of Scheme.^[13] Schism's polyvariant specialization and support for partially static data structures influenced subsequent systems by showing that self-application could yield practical compiler generators with minimal manual intervention.^[14] Building on Yoshihiko Futamura's foundational projections from the 1970s—which theoretically enabled compiler generation via self-specialization—Futamura himself implemented early partial evaluators in the 1980s, including a compact Lisp-based system that specialized programs by treating them as partially known inputs.^[15] During the 1990s and 2000s, researchers like Charles Consel and Julia Lawall integrated partial evaluation with type theory to enhance safety and expressiveness in program specialization, particularly for imperative languages.^[10] Consel's work on systems like Schism evolved into broader frameworks for offline partial evaluation, emphasizing modular techniques that separated binding-time analysis from code generation to support typed residuals. Lawall, collaborating with Consel, applied these principles to Java and C, developing tools that automated specialization while preserving type correctness, as seen in their 2000s efforts on generic component configuration.^[16] The Cmix system, an extension of earlier Mix work, further advanced partial evaluation for C by specializing ISO-compliant programs through loop unrolling and function inlining, achieving measurable speedups in numerical computations without altering source semantics.^[17] Neil D. Jones played a pivotal role in formalizing partial evaluation principles, co-authoring the seminal 1993 book Partial Evaluation and Automatic Program Generation that synthesized techniques for self-applicable evaluators like Mix, which demonstrated automatic compiler generation in the late 1980s.^[18] Jones's contributions extended to binding-time analysis, ensuring termination and optimality in specialization processes. Anders Bondorf complemented this by developing binding-time improvement algorithms in the early 1990s, introducing methods to refine annotations without explicit CPS conversion, which reduced residual code size and improved specialization efficiency in functional settings.^[19] Post-2010 advancements have leveraged partial evaluation in high-performance domains, particularly for GPU programming and machine learning code generation. Frameworks like Terra, introduced in 2012, employ multi-stage programming akin to partial evaluation to generate optimized low-level code for heterogeneous systems, enabling efficient GPU kernels through staged compilation that specializes abstract algorithms to hardware specifics.^[20] Similarly, Halide's scheduling system, while not purely partial evaluation, integrates specialization techniques to auto-tune image processing and deep learning pipelines, producing high-performance code for ML workloads by partially evaluating tensor operations against fixed parameters like kernel sizes. These developments, exemplified in systems like AnyDSL, extend partial evaluation to online modes for just-in-time GPU compilation, achieving competitive performance against hand-optimized libraries.^[21] More recently, as of 2025, partial evaluation techniques have been applied to whole-program compilation for dynamic languages, enabling efficient JIT compilation without extensive tracing, as demonstrated in research presented at PLDI 2025.^[22]

Core techniques

Binding-time analysis

Binding-time analysis (BTA) is a static analysis technique used in partial evaluation to classify program expressions, variables, and control structures according to their binding times, determining whether they can be evaluated statically at specialization time (known inputs) or dynamically at residual program runtime (unknown inputs). This classification typically assigns labels such as static (S), dynamic (D), or mixed to ensure that the partial evaluator can distinguish computable parts from those requiring residual code generation, while maintaining semantic equivalence between the original and specialized programs.^[1] The core algorithms for BTA rely on abstract interpretation over a simple lattice of binding-time information, such as {S, D}, where S denotes static and D denotes dynamic. Forward propagation computes binding times from inputs to outputs by iteratively annotating expressions based on their operands: for an operator * applied to expressions e1 and e2, the binding time bt(e1 * e2) is S if bt(e1) = S and bt(e2) = S, otherwise D. Backward propagation refines these annotations by propagating constraints from outputs back to inputs, ensuring congruence—meaning static computations depend only on static data—and uniformity across program points. These propagation steps are often implemented via fixpoint iterations in a dataflow framework, with abstract domains like the powerset of {S, D} to handle mixed cases in higher-order settings.^[1]^[23] Consider a simple function

f(x, y) = \if x > 0 \then y + 1 \else y - 1

, where x is static with value 5 and y is dynamic. BTA propagates the static binding time of x to the conditional test, inferring that the branch

x > 0

evaluates to true statically, allowing the then-branch

y + 1

to be specialized into residual code while residualizing the else-branch only if needed; however, since the condition is static, the entire function specializes to

f'(y) = y + 1

. This demonstrates how BTA enables branch elimination and unfolding for efficiency.^[1] Handling control flow in BTA involves analyzing conditionals and loops to decide safe unfoldings and avoid infinite specialization. For conditionals, the analysis checks if the guard expression is static; if so, the corresponding branch is evaluated and unfolded statically, with the other residualized. Loops are treated via abstract domains that model iteration counts (e.g., finite vs. unknown), using polyvariant analysis to generate multiple specialized versions based on static parameters, such as unfolding a loop a fixed static number of times. Continuation-passing style (CPS) transformations often linearize control flow, facilitating precise propagation in functional languages.^[1] Challenges in BTA include scalability for large programs, where fixpoint computations can be expensive due to wide lattices, and handling higher-order functions, which introduce dynamic closures and require closure analysis to track binding times of free variables. Solutions employ modular abstract domains, such as those combining binding times with control-flow approximations (e.g., k-limited unfolding), and type-directed inference to bound complexity while preserving completeness for first-order cases.^[1]

Program specialization process

The program specialization process in partial evaluation involves applying a specializer to a source program and a set of static input values, producing a residual program that incorporates the effects of those static computations while leaving dynamic parts as executable code.^[1] The pipeline typically begins with a binding-time analysis to classify program elements as static or dynamic, followed by annotation of the program, and culminates in the specialization phase where the specializer simulates execution on static inputs.^[1] This generates an optimized residual program tailored to the static values, enabling faster execution when the remaining dynamic inputs are provided.^[1] Specialization employs two primary strategies: driving and non-driving. In the driving strategy, also known as online partial evaluation, the specializer eagerly evaluates and reduces static parts during the computation, making decisions on unfolding and reduction based on the actual static values encountered, without prior annotations.^[1] This approach simulates the program's execution, driving forward only when static data is available, which allows for dynamic handling of control flow but risks incomplete specialization if values are insufficiently concrete.^[1] Conversely, the non-driving strategy, or offline partial evaluation, postpones eager evaluation by first performing a comprehensive binding-time analysis and annotating the program with static/dynamic distinctions upfront; the specializer then follows these annotations rigidly, reducing only pre-identified static computations and generating residual code for dynamic ones.^[1] Offline methods ensure completeness but may miss optimization opportunities that online driving could exploit through value-specific insights.^[1] Central to the process are unfolding rules, which determine when to inline and reduce computations. For instance, when a lambda abstraction receives a static argument, beta-reduction substitutes the argument into the body, eliminating the function call and computing any resulting static expressions immediately.^[1] Unfolding is applied selectively to static calls to avoid infinite loops, often limited by heuristics such as depth bounds or call graph analysis, while dynamic calls are preserved as residual invocations.^[1] These rules enable the specializer to propagate static information, simplifying control structures and arithmetic operations. Residual code generation occurs as the specializer traverses the annotated program, replacing static computations with their results and constructing code fragments for dynamic portions. Dynamic variables and unknown inputs are annotated as placeholders (e.g., new parameters), and dead code—unreachable due to static reductions—is optimized away through flow analysis.^[1] The output is a self-contained program, often with specialized functions or case statements reflecting static branches, ensuring type safety and efficiency.^[1] A representative workflow illustrates the process using an interpreter for a toy language, such as a simple arithmetic expression evaluator written in a functional style. Given the interpreter program and a static input program (e.g., the expression "2 + 3 * 4"), the specializer drives the interpretation loop with these static values, unfolding the evaluation steps to compute constants inline while generating residual code for any dynamic inputs like runtime variables. The result is a specialized evaluator equivalent to a compiled version of the static expression, directly yielding the value 14 without further interpretation overhead.^[1] In practice, successful specialization yields significant metrics: speedups ranging from 2.7-fold for simple arithmetic to 13.7-fold for complex tasks like ray tracing, alongside code size reductions of up to 50% through dead code elimination, though unchecked unfolding can occasionally increase size exponentially.^[1] These gains establish partial evaluation's impact on performance-critical systems, provided polyvariance and termination controls are applied.^[1]

Futamura projections

First projection

The first Futamura projection states that applying a partial evaluator to an interpreter

I

with respect to a static source program

P

produces a specialized compiler

C_P

such that for any dynamic input program

Q

C_P(Q) = I(P, Q)

.^[2] This transformation effectively compiles

P

by specializing the interpreter, eliminating interpretive overhead while preserving semantics.^[1] Yoshihiko Futamura first described this projection in a 1971 paper published in Japanese, which laid the theoretical foundation for using partial evaluation in compiler generation.^[7] The work remained influential but less accessible until an English translation was published in 1999, popularizing the concept among Western researchers and leading to practical implementations in the 1980s and 1990s.^[2] A proof of correctness follows from the fundamental mix equation of partial evaluation, which ensures semantic equivalence. Let

pe

denote the partial evaluator,

I

the interpreter,

P

the static program, and

Q

the dynamic input. Then:

pe(I, P)(Q) = [[P]]_S Q = [[I]] [P, Q],

where

[[ \cdot ]]

denotes the meaning of a program under static (

S

) or dynamic evaluation. The residual program produced by

pe(I, P)

simulates the execution of

I

P

for any

Q

, yielding

C_P(Q) = [[I(P, Q)]]

.^[1] This projection has significant practical implications, as it enables the automatic generation of compilers from high-level interpreter specifications, facilitating rapid prototyping of domain-specific languages and reducing development time for optimized executables.^[1] Early implementations demonstrated speedups of 3 to 200 times over pure interpretation, depending on the language and application.^[1] A representative example involves partial evaluation of a simple Lisp interpreter with respect to static Lisp source code, such as a power function

(\lambda (n) (if (= n 0) 1 (* n (power (- n 1)))))

. Specializing the interpreter eliminates the loop over Lisp instructions, producing a standalone executable that directly computes powers without interpretive overhead, achieving near-native performance.^[1]

Second and third projections

The second Futamura projection extends the idea of partial evaluation by applying the partial evaluator, denoted as

pe

, to itself as the static input, with an interpreter

I

for a given programming language

L

serving as the dynamic input. This self-application yields a compiler generator, or cogen, specifically tailored to

L

, which can then take any source program

P

L

and produce an efficient compiler for it by specializing

I

with respect to

P

. Formally,

pe[pe](I) = \text{cogen}_L

, where

\text{cogen}_L(P) = pe[I](P)

, resulting in a compiler that translates programs in

L

to executable code without requiring manual construction for each new source program. This projection, introduced by Yoshihiko Futamura in his seminal 1971 paper, enables automated generation of language-specific compilers from a universal partial evaluator, assuming

pe

is self-applicable.^[24] The third Futamura projection further abstracts this process by applying

pe

twice to itself, producing a universal compiler generator, often called cogent, that operates at a higher meta-level. Specifically,

pe[pe[pe]] = \text{cogent}

, which takes any interpreter

I

as input and outputs the corresponding

\text{cogen}_L

for the language

L

interpreted by

I

. This tool can thus generate compiler generators for arbitrary languages without prior specialization to a particular one, providing a foundational mechanism for meta-programming systems. While the first two projections appeared in Futamura's 1971 work, the third was detailed in a 1973 internal report and later formalized in his publications through the mid-1970s.^[25] Futamura's projections, originally published in Japanese, gained prominence in Western computer science literature through the 1993 book Partial Evaluation and Automatic Program Generation by Neil D. Jones, Carsten K. Gomard, and Peter Sestoft, which provided detailed analyses, proofs of correctness, and practical implications, sparking widespread research into self-applicable partial evaluators.^[1] Despite their theoretical elegance, the second and third projections face significant practical limitations, primarily the computational expense of self-applying a partial evaluator, which involves analyzing and specializing complex code for binding-time distinctions at multiple meta-levels, often leading to prohibitive runtimes and memory usage for non-trivial languages. Additionally, realizing these projections requires a self-applicable

pe

that can handle its own structure without divergence or incompleteness, a challenge that has historically limited implementations to toy languages or required extensive optimizations.^[26] As an illustrative application, the third projection can generate a domain-specific specializer for SQL query optimization: by inputting a partial evaluator designed for SQL interpretation into

\text{cogent}

, one obtains a compiler generator that produces optimized query executors tailored to particular database schemas or workloads, enhancing performance in relational systems without hand-coding each optimizer.^[27]

Applications

In compiler optimization

Partial evaluation plays a crucial role in compiler optimization by enabling the automatic specialization of programs with respect to known inputs, leading to more efficient code generation, particularly in just-in-time (JIT) compilation environments.^[28] In JIT compilers, partial evaluation specializes interpreters or bytecode at runtime, folding constants and propagating known values to produce optimized machine code tailored to specific execution paths.^[29] This approach aligns with the Futamura projections, where specializing an interpreter yields a compiler.^[1] In JIT compilers for dynamic languages, partial evaluation is employed to specialize bytecode interpreters based on static method inputs observed at runtime. For instance, the Truffle framework, integrated with the Graal compiler on the HotSpot JVM, uses partial evaluation to optimize languages like Ruby and JavaScript by inlining and specializing abstract syntax trees (ASTs) with runtime type information, resulting in high-performance execution.^[28] Similarly, LuaJIT's trace-based JIT compiler captures hot execution traces and specializes them akin to online partial evaluation, optimizing Lua bytecode for frequent paths in applications like game scripting.^[30] These techniques allow dynamic language virtual machines (VMs) to achieve near-native performance without duplicating semantics across interpreter, compiler, and runtime components.^[29] Staged compilers leverage partial evaluation in multi-stage programming paradigms to generate code for subsequent compilation stages. In systems like MetaOCaml, an extension of OCaml for multi-stage programming, partial evaluation enables the production of residual code from staged expressions, allowing developers to embed domain-specific optimizations early in the compilation pipeline.^[31] This facilitates efficient code generation where earlier stages specialize computations based on static knowledge, deferring dynamic parts to later stages.^[32] Key optimization techniques enabled by partial evaluation include loop unrolling and constant propagation. During specialization, loops with known iteration counts are unrolled into straight-line code, eliminating overhead from control flow and enabling further optimizations like instruction scheduling.^[33] Constant propagation evaluates expressions with static values at specialization time, replacing variables with computed constants to simplify code and expose additional optimizations.^[34] These transformations reduce interpretive overhead in JIT settings by producing tighter, more predictable code. A notable case study is the application of partial evaluation in JavaScript engines like V8, where inline caching mechanisms specialize property access code based on observed types, effectively performing partial evaluation to cache monomorphic assumptions and avoid repeated lookups.^[35] As of 2025, implementations exploring partial evaluation for JavaScript-to-WebAssembly compilation build on V8's caching to enable whole-program specialization, optimizing interpreters for specific bytecodes without tracing.^[35] Recent work, such as whole-program partial evaluation for JavaScript interpreters, derives compiled code directly from bytecode specialization, enhancing performance in web environments.^[35] Empirical performance gains from partial evaluation in dynamic language VMs are substantial, with studies showing speedups of up to 3.8x relative to traditional implementations like JRuby and 5x over GNU R interpreters, while remaining competitive with V8 (0.83x).^[29] These improvements stem from reduced abstraction penalties and aggressive inlining, often yielding 2-10x overall speedups in benchmark suites for languages like Ruby and R.^[36] Despite these benefits, partial evaluation introduces challenges, including the overhead of specialization time, which can increase compilation latency if specializations proliferate without reuse.^[29] This overhead is balanced by runtime savings, but requires techniques like speculation and deoptimization to manage code bloat and ensure profitability in JIT scenarios.^[28]

In domain-specific languages and program generation

Partial evaluation plays a pivotal role in the development of domain-specific languages (DSLs) by enabling the specialization of general-purpose language interpreters into efficient, tailored implementations for specific domains. This process involves partially evaluating an interpreter with respect to a fixed DSL specification, generating optimized code that incorporates domain-specific optimizations without manual intervention. For instance, partial evaluation can transform a general-purpose interpreter into a dedicated SQL query engine by specializing it for a particular database schema, resulting in residual programs that execute queries more efficiently than interpreted versions. Experimental evidence demonstrates that this approach can yield residual programs with performance comparable to hand-written code. In program generation tools, partial evaluation facilitates automated synthesis of customized software components, as exemplified by systems like Mix and Schism, which specialize programs to produce stand-alone generators for domain-specific tasks. These tools leverage partial evaluation to create efficient code from high-level descriptions, such as generating workflow automation scripts or embedded system controllers, by unfolding computations at specialization time. Furthermore, partial evaluation integrates with aspect-oriented programming (AOP) by specializing pointcuts—predicates that select join points in code—allowing aspects to be woven efficiently at compile time, reducing runtime overhead in modular extensions like logging or security checks. In languages supporting macro expansion, such as Lisp and Scala, partial evaluation enhances macro systems by enabling compile-time computation of macro expansions, akin to specializing fexprs in Lisp to replace traditional macros with performant, purely functional alternatives that eliminate interpretation overhead. This results in code that is over 70,000 times faster than naive interpretations in functional Lisp settings.^[18]^[37]^[38] Modern applications extend partial evaluation to AI-driven code generation, where it specializes high-level descriptions in frameworks for target hardware, incorporating optimizations such as vectorization and parallelism without explicit user coding. For example, systems like AnyDSL use partial evaluation to generate high-performance code for domain-specific libraries, enabling mappings of abstract algorithms to hardware efficiently. Benefits include automatic derivation of vectorized code paths, which can improve execution on GPUs while maintaining high-level expressiveness. A notable case study is the SPIRAL system, which generates specialized fast Fourier transform (FFT) kernels, producing code that outperforms vendor libraries like FFTW by up to 20% in certain configurations through tailored blocking and cache optimizations for specific transform sizes and architectures.^[39]^[40]

History

Partial evaluation

Recent from talks

Recent from talks

Contribute something

Contribute something

Media Pages

Timelines

Articles

Notes collections

Notes

Notes

Days in Chronicle

Partial evaluation

Futamura projections

See also

References

General references

External links