Paper: Partial Computation of Programs (Futamura, 1983)

Partial Computation of Programs (Futamura, 1983)

This is a fascinating paper, for several reasons.

  • First of all, the paper is very accessible, even though it’s technical, because it does not dive in too deeply in theory; it’s actually quite practical.
  • Moreover, Futamura Projections are one of theoretical basis for Truffle (so-called first Futamura Projection)
  • Finally the key idea can be explained in just a few words

Here’s the gist of it: if there is an operator (the partial evaluator) that you can apply to a program to “fix” part of its input, then you get very interesting results by applying it to a language interpreter (a program itself), and to the partial evaluator itself (which is assumed to exist as a program too).

  • an interpreter fixed on a program for that interpreter, is a compiled program (first projection)
  • the second projection yields a compiler
  • the third projection yelds a compiler-compiler i.e. a compiler generator

There is an excellent presentation and blog post by Tom Stuart at RubyCon where the idea is explained in layman terms, but I found that the paper is pretty readable too.

I have presented it at our local Papers We Love meetup. You’ll see that I took quite a few hints from Tom’s presentation in mine.