A partial history of partial evaluation
summary
The 1984–85 work realizes non‑trivial self‑application of a partial evaluator, achieving the second and third Futamura projections by turning a specializer into a compiler and a compiler-generator. Key techniques are binding‑time annotations and automated binding‑time analysis that produce a two‑level program the specializer actually processes, implemented over simple first‑order functional languages with S‑expression data. The result is a working mix that generates compilers from interpreters and a compiler‑generator that survives self‑application, with papers, generated compilers and an active workshop community to show it worked.
AI-written summary · about
chapters (9)
- 0:00Start
- 0:10Peter Sestoff
- 1:10Overview
- 7:05What Is Non-Trivial Self-Application
- 18:29Binding Time Analysis
- 41:26Architecture of the Machine
- 44:32Translation of Euclid's Algorithm
- 45:42The Loader Program
- 46:48Compiler's Flow Graph
related talks
09mCompilers for nothing, executables for free!
31mThe Genesis of Mix: Early Days of Self-Applicable Partial Evaluation (Invited Co...
46mDr. Futamura and the Projection Machine: From Interpreters to Compilers
07mFutamura Projections
27mTowards Type Debugging using Partial Evaluation
09mRetargeting an Abstract Interpreter for a New Language by Partial Evaluation (Short Paper)
20mPartial Evaluation, Whole-Program Compilation
15mMonadic Compiler Calculation (Functional Pearl)