Dr. Futamura and the Projection Machine: From Interpreters to Compilers
summary
Futamura projections let a partial evaluator turn a high‑level interpreter into a compiled program by specializing the interpreter on a fixed source program; applying it twice yields a compiler, and a third time yields a compiler generator (paper from 1983). Truffle on GraalVM implements this: AST interpreters get speculatively partially evaluated to optimized machine code, deoptimized and recompiled on misprediction, and produce Ruby/JavaScript runtimes competitive with V8 rather than slower prototypes.
AI-written summary · about
chapters (15)
- 0:00Introduction
- 3:37About me
- 5:18Programs
- 6:02Program Evaluation
- 10:52Partial Evaluation
- 12:06Partial Application vs Partial Evaluation
- 14:32Rewriting
- 16:46Projection
- 19:32Applying Partial Evaluation
- 20:02Compile Program
- 26:56Alpha
- 28:45Truffle
- 32:21What is Alpha
- 34:35Tabulation
- 38:47First Projection
related talks
07mFutamura Projections
59mSupercompilation, Partial Evaluation, Futamura Projections and How GraalVM Will Save the World
01h 01mA partial history of partial evaluation
09mCompilers for nothing, executables for free!
45mInvited Talk: A decade of Self-Optimizing Interpreters in GraalVM
01h 19mTowards the tower of Babel: a Polyglot Language VM in Java
28mTruffle
53mUnveiling the Mysteries of GraalVM's Least Understood Component