January 11, 2015 - Tagged as: en, partial evaluation.
Here’s a way to understand Futamura projections1:
(Quick note: “Partial evaluator” == “specializer”. As far as I can see these words are also used interchangeably in the literature)
We call our specializer specialize. We specify languages using capital letters, S, T, L etc. We use Haskell syntax for applications. (e.g. f a1 a2 a3 is a function application of f to three arguments, applications are left-associative in the case of currying)
specialize takes two arguments, first argument is the program(function) to specialize, second argument is the input to specialize the program(function) on.
Note that our specializers are “correct”: For all specializer s, program f and program arguments a and b, (s f a) b is semantically same as f a b.
We show a specializer written in L which operates on programs written in T as specialize_L_T.
Now there are three interesting “Futamura projections”. Let’s say we have an interpreter for a language L, called int, which is written in T. We use * as a wildcard for languages. (e.g. it can be substituted with any language)
specialize_*_T int int_pgm: We specialized the interpreter on a program int_pgm, resulting program is in T. We now have a program in T which just gets arguments of the interpreted program and produces output. This gives us a compiled version of int_pgm to T.
specialize_T_T specialize_T_T int: We specialized the specializer on an interpreter. Generated program will be in T, and it’ll be expecting interpreter programs as input. The output will be specialized version of int for the given interpreter program. So we got a compiler for the interpreter int!
Note that specializers now need to be written in the language that they operate on. Alternatively, we could use two different specializers: One for specialize the interpreter, and one for specializing the interpreter specializer. (e.g. in most general form, we can have specialize_A_B specialize_B_C int where int is written in C)
specialize_T_T specialize_T_T specialize T_T: This one is tricky. Let’s try to think what will be the generated program. We know from (2) is that specialize_T_T specialize_T_T int is a compiler for the language that int interprets. Now, we know from the note above that specializing doesn’t change meaning of the program, so our term from (2) specialize_T_T specialize_T_T int should be same with (specialize_T_T specialize_T_T specialize_T_T) int. What happens if we don’t apply the last int? Then we got a program that takes an interpreter and specializes it, resulting with a program in T that doesn’t expect interpreter argument. This is a compiler-compiler. Given an interpreter in T, it gives us a compiled version.
Futamura projections are originally introduced in Futamura’s “Partial Evaluation of Computation Process – An Approach to a Compiler-Compiler” and also described in “Partial Evaluation and Automatic Program Generation”.
Thinking about languages and interpreters are good way to have an intuition about how partial evaluation, specializing specializers etc. work, and “writing interpreters on problem domain” may be a good and general approach to solving problems2, but I’m wondering what interesting programs and results we would get if we apply the these to different domains. Any ideas and pointers would be appreciated.
Implementing ideas are generally a good way to learn, but in this case it’s a bit tricky. If we want to specialize specializers(like in projection (2) and (3)) we need to write one specializer in the language that it specializes, so we need a specialize_T_T for a T.
To be more concrete, if we want to write the specializer in Haskell, then it has to be operating on Haskell so that we could specialize it on itself. Now this is no trivial work, Haskell is a big and complicated language.
On the other hand, if we want to roll our own language just to try this idea, then we’ll have to write the specializer in our language. This is also not trivial, because we need implement a language that is expressive enough to write a specializer for itself.
Designing a minimal language that is expressive enough to implement the idea may be a good challenge.
Futamura projections are what you get when you apply partial evaluators to interpreters and to themselves. Have a look at related Wikipedia page and see bottom of the post for more resources.↩︎
I recently stumbled upon this SO answer to a question about functional design patterns. It’s interesting how forcing yourself to a particular paradigm leads to different approaches and ways to solving problems. This is one of the reasons why I’m trying to learn a new paradigm using a language that is specifically crafted for that paradigm(e.g. Haskell for functional programming instead of Lisps, Scala etc.).↩︎