Type Theory Forall - #37 Compilers, Staging, Futamura Projections
www.typetheoryforall.com
An accessible podcast about Type Theory, Programming Languages Research and related topics.

It’s just one part, but the Futamura Projections] are techniques to “compile” interpreted programs using partial evaluation:

partialEval : (a : Function) -> a -- Specializes a partially-applied function: returns something with the same arity and semantics but faster
interpret prog inp -- Runs the interpreter on a program with input
  • The first futamura projection turns an interpreted program into a compiled one by “partially evaluating” (AKA “specializing”) the interpreter on the source code (e.g. hard-coding things that would remain constant during the code’s execution). partialEval (interpret prog) inp
  • The second futamura projection turns an interpreter into a compiler by partially-evaluating the partial evaluator on the interpreter. partialEval (partialEval interpret) prog inp
  • The third futamura projection partially-evaluates the partial-evaluator on itself, creating a “compiler compiler”: a function which takes an interpreter and returns a compiler, or more precisely, takes an interpreter and returns something that takes a program and returns a compiled program, or more precisely, takes an interpreter and returns something that takes a program and returns something that takes an input and produces the same output the original program would, but faster: partialEval (partialEval partialEval) interpret prog inp

More detailed explanation. An example of this in practice is Truffle in GrallVM.

  • CorbinEnglish
    4·
    10 months ago

    Good summary. A couple notes before I listen:

    • There is a book that everybody needs to read if they want to implement compilers using Futamura’s projections, known as The Book. There’s an important meme from The Book – “if the specializer is any good, then so is its output” – and also “the trick”, which involves carefully promoting variables to constants.
    • The partial evaluator is traditionally called mix, particularly in The Book and also a few important papers like Glück 2009. This also extends to project nomenclature; “Logimix” for Prolog or “Similix” for Scheme are both based on mix.
    • That paper by Glück is wild, by the way. There are three more Futamura projections, although they don’t offer any power beyond the third projection.
    • We can think of the first projection as also turning an interpreter to a compiler, although it requires the presence of the partial-evaluator runtime to invoke the compiler.
    • Truffle is one of the two important frameworks to mention; the other is RPython, as used to implement PyPy. RPython uses the first projection to transform interpreters into JIT compilers; technically, it’s the second projection, since inside each JIT compiler there is a mechanically-generated transformation from a custom bytecode to machine code.
    • The third projection has never been shown to be practical. Maybe the reader can be the first to do it! It’s partially because implementing even the first projection is difficult and the only two efficient examples of the second projection are Truffle and RPython, and partially because Glück’s paper shows that a specializer has to be able to rewrite all of its guts without losing any of its behavior, acting as a compiler torture test.