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.