The Secret Art of Futamura Projection

Consider a database. You may query the database more often than you make changes, and you may use certain queries more often than others. Some queries might be so useful that you use them over and over again on different kinds of data. Another example, consider programs with configurable options and user preferences. Once set, your preferences will change less often than the documents and data that your program uses. Third example, suppose you are making an animation. The characters in the animation will move move than the scenery. The background is statically fixed. The characters are fluid and dynamic.

We can leverage the fact that static input changes less often than dynamic input. Partial evaluation makes the most of the static input when the dynamic input is subject to change: go ahead and evaluate, but only use the static part. A partial evaluator takes a program paired with part of its input and returns a new program which will finish the job when the rest of the input becomes available.

Partial evaluation is dark magic. Darkest of all is Futamura projection. Its most potent form, the third Futamura projection, allows the creation of a compiler generator from the partial evaluator alone. A compiler generator is a program which given an interpreter as input, produces a compiler as output. It is similar to a parser generator (a program which given a grammar as input, produces a parser as output). The difference, of course, is that the compiler generator manages whole languages where the parser generator only handles grammars. With a compiler generator in hand, you can freely write specialized, domain specific languages without the runtime overhead of having layer upon layer of abstraction. Partial evaluation squashes the layers often resulting in order an magnitude improvements in performance.

In what follows, I will attempt to unravel the mystery of Futamura Projection.

Partial Evaluation Preliminaries

The journey to the dark side begins with the desire for power. In our case the power function:

power base exponent =
  1 if exponent is 0 else
  base * power base (exponent - 1)<br/>
power 2 8 => 256
power 3 5 => 243
power 6 3 => 216

Of all possible exponents, two are so familiar they they have their own names:

square x = power x 2
cube   x = power x 3

power is a function of two numbers; square and cube differ from power by fixing the value of the exponent. The desire for different kinds of power leads to the dark side, leads to partial evaluation. A partial evaluator mixes one part program with one part input yielding new specialized program for the remaining input. Thus, the partial evaluator is known as mix.

reverse-arguments f = x y -> f y x
rpower = reverse-arguments power
square = mix rpower 2
cube   = mix rpower 3

Lines “a partial evaluator mixes one part program with one part input yielding new specialized program for the remaining input” will prove tedious later on. Better to suffer some notation up front:

-- maps a pair of numbers to a number.
power :: Number Number -> Number<br/>
-- maps a number to a number.
square :: Number -> Number<br/>
-- given a program of two arguments and one of the arguments
    returns a new program which given the other argument returns
    the same result as the original program.
mix :: (static dynamic -> result) static -> dynamic -> result

Any sentence, like the one above, describing what mix does will be equally long winded. To be precise, let’s give a formal specification once and for all:

a PartialEvaluator is a Function where
  for-all program static dynamic
    result = program static dynamic
    mixed  = this program static
    result is mixed dynamic

Not all partial evaluators are created equal. A trivial partial evaluator, one that implements the spec but doesn’t do any partial evaluating, is this one liner:

trivial-mix program static = dynamic -> program static dynamic
=> trivial-mix is a PartialEvaluator

See the following derivation for verification of the above assertion. If you don’t want to deal with the math, just skip it. I don’t want to deal with explaining the notation, so I skipped that.

proof that trivial-mix is a PartialEvaluator
  fix program static dynamic
  result = program static dynamic
  mixed  = trivial-mix program static
  result => program static dynamic =>
            (dynamic -> program static dynamic) dynamic =>
            (trivial-mix program static) dynamic =>
            mixed dynamic

trivial-mix is a perfectly good partial evaluator and a perfectly bad example of a useful one. I won’t show a real partial evaluator today because I’d never get to talking about Futamura projection. Just suppose that we already have a good mix. What an outrageous claim! I won’t let myself get off that easy. Instead of defining mix, I’ll settle for an example of a mix in action:

reverse-arguments f = x y -> f y x
rpower = reverse-arguments power
square = mix rpower 2<br/>
square =>
mix rpower 2 =>
-- enter the mixed up world
  rpower 2 m =>
  (reverse-arguments power) 2 m =>
  ((f -> x y -> f y x) power) 2 m =>
  (x y -> power y x) 2 m =>
  power m 2 =>
  (base exponent ->
    1 if exponent is 0 else
    base * power base (exponent - 1)) m 2 =>
  1 if 2 is 0 else
  m * power m (2 - 1)) =>
  m * power m 1 =>
  m * (base exponent ->
    1 if exponent is 0 else
    base * power base (exponent - 1)) m 1 =>
  m *
    1 if 1 is 0 else
    m * power m (1 - 1) =>
  m * m * power m 0 =>
  m * m * (base exponent ->
    1 if exponent is 0 else
    base * power base (exponent - 1)) m 0 =>
  m * m *
    1 if 0 is 0 else
    m * power m (0 - 1) =>
  m * m * 1 =>
-- that was mixed up
m -> m * m * 1

Even though mix doesn’t know the value of m that doesn’t keep it from evaluating everything else which is the point of having a partial evaluator.

First Futamura Projection

What’s an interpreter? Ruby is an interpreter. What does Ruby do? First you write a little code. Here’s a simple program. Let’s call it quine.rb:

puts gets

Then you invoke the Ruby interpreter with the source file and list of input files. Since we just wrote quine.rb, let’s see what it does when given itself as input:

~> ruby quine.rb quine.rb
puts gets
~>

So quine.rb is a program that prints itself when given itself as input. It’s not a proper quine but we aren’t talking about quines, we’re talking about interpreters. An interpreter is function of two arguments:

interpreter :: source input -> output

Function of two arguments, that mean we can mix it. Let’s see what happens:

mix interpreter source ::
  (static dynamic -> result) static -> dynamic -> result @
    source input -> output
    source
-- Let's simplify the type:
-- We know
  static dynamic -> result = source input -> output
  mix interpreter source :: dynamic -> result
-- Therefore
  dynamic = input
  result  = output
  dynamic -> result = input -> output
-- Hence
mix interpreter source :: input -> output

In other words, mixing an interpreter with some source results in a program that takes some input and returns some output. Since mix is a partial evaluator, the resulting program does the same thing with its input as the interpreter would given both the source and the input. Applied to our Ruby example, the operation (shall we say projection) would look something like this:

~> mix ruby quine.rb >mixed_quine
~> mixed_quine quine.rb
puts gets
~>

What just happened? With the Ruby interpreter and quine.rb as input, the partial evaluator returned a new binary executable that does the same thing as quine.rb. Mix compiled quine.rb! This is the first of three Futamura projections.

Second Futamura Projection

Using mix to compile ruby programs is pretty nifty, but wouldn’t it be great if we had a dedicated Ruby compiler? A compiler takes some source code as input and produces a executable program. When you run the program, it takes some input and produces some output. Schematically:

program  :: input  -> output
compiler :: source -> program

How are we supposed to get a compiler just using mix and interpreter? For the first projection, we used mix in the following way:

interpreter :: source input -> output
mix :: interpreter source -> program

Notice that mix itself is s function of two arguments in which one, the interpreter, changes more slowly than the other, the source program. This means that we can mix mix with an interpreter to get a compiler? Check the typing:

mix mix interpreter ::
  (static dynamic -> result) static -> dynamic -> result @
    interpreter source -> program
    interpreter
-- Let's simplify the type:
-- We know
  static dynamic -> result = interpreter source -> program
  mix mix interpreter :: dynamic -> result
  compiler :: source -> program
-- Therefore
  dynamic = source
  result  = program
  dynamic -> result = source -> program
  dynamic -> result = compiler
-- Hence
mix interpreter source :: input -> output

Sure enough, mixing mix with an interpreter to gives you a compiler. This is the second Futamura projection. How good is the compiler? Depends on the partial evaluator. Realistic partial evaluators provide order of magnitude performance gains. Mathematically speaking, interpretation has an order of magnitude overhead due to indirection. A good partial evaluator simply removes the indirection and reaps the performance benefit.

Third Futamura Projection

A compiler generator is a program which given an specification (interpreter) as its input produces a compiler as its output. The type is simple enough:

generator :: interpreter -> compiler

In the introduction, I claimed that mix was the only program necessary to create a generator. If so, that would mean? Yes, you guessed it:

mix mix mix :: generator

Don’t believe me? I wouldn’t either. The second projection uses mix to return a compiler from mix and an interpreter. In other words:

mix :: mix interpreter -> compiler

With that tidbit in mind, the rest of the argument goes through as before:

mix mix mix ::
  (static dynamic -> result) static -> dynamic -> result @
    mix interpreter -> compiler
    mix
-- Let's simplify the type:
-- We know
  static dynamic -> result = mix interpreter -> compiler
  mix mix mix :: dynamic -> result
  generator :: interpreter -> compiler
-- Therefore
  dynamic = interpreter
  result  = compiler
  dynamic -> result = interpreter -> compiler
  dynamic -> result = generator
-- Hence
mix interpreter source :: generator

To mix the mixer with itself: this is the third Futamura Projection.