The Three Projections of Doctor Futamura
The Futamura projections describe three transformations in program compilation: deriving a compiler from an interpreter via partial evaluation, generating a compiler generator, and bootstrapping that generator. They illustrate how self-application of a specializer can automatically turn interpreters into compilers.
Background
- The Futamura Projections are three fundamental relationships between interpreters, compilers, and partial evaluators, described by Japanese computer scientist Yoshihiko Futamura in 1971.
- Partial evaluation is a program transformation technique: given a program and some of its inputs (known as "static" inputs), a partial evaluator produces a specialized version of the program that runs faster because it pre-computes everything that depends only on those known inputs.
- The three projections show a deep connection in programming language theory: (1) running an interpreter on a program with partial evaluation produces a compiled version of that program; (2) running the partial evaluator on the interpreter produces a compiler from the interpreted language to the host language; (3) applying the partial evaluator to itself produces a tool that can generate compilers automatically.
- This is a landmark result in the theory of computation and programming languages, studied by researchers in partial evaluation, compiler construction, and program transformation.