Partial Evaluation
Partial evaluation is a program optimization technique where a program is specialized with respect to some of its input data, producing a residual program that runs faster when given the remaining inputs. It is related to concepts like function currying and can be applied automatically using a partial evaluator or specializer.
Background
Partial evaluation is a program optimization technique where a computer program is specialized by pre-computing parts of it using known input data, producing a faster "residual" program. It's most famously applied through the Futamura projections (named after Yoshihiko Futamura, 1971): by partially evaluating an interpreter with respect to a program, you can compile that program; by partially evaluating a compiler with itself, you can generate a compiler generator. These ideas underpin much work in programming languages (e.g., specialization in just-in-time compilers, binding-time analysis, and metaprogramming). The concept connects to language theory (Kleene's s-m-n theorem), practical systems like DyC and Tempo, and the history of computing since the 1970s. It matters because it formalizes how to automatically derive compilers from interpreters, a deep theoretical result with real impact on compiler design and program optimization.