Type Theory Forall - #37 Compilers, Staging, Futamura Projections (podcast) (www.typetheoryforall.com)
from armchair_progamer@programming.dev to programming_languages@programming.dev on 12 Mar 2024 19:29

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

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


threaded - newest

Corbin@programming.dev on 13 Mar 2024 06:28 collapse

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.