Typing the futamura projections in haskell

Futamura.lhs

> module Futamura where

Partial evaluation transforms the source code of a general program into a more specialized program.

For example, given the following general program:

function repeatedlyPrint(count, message):
  for i from 1 to count:
    print(message)

We can partially evaluate this, setting count = 3, and get the more specialized program:

function repeatedlyPrint(message):
  print(message)
  print(message)
  print(message)

We can represent partial evaluation with the following types:

> data Src a
> data Pgm a

`Src a` is the source code of a program that outputs `a`. Note that `a` can itself be a function,
e.g. `Src (b -> c)` is the source code of a program that inputs `b` and outputs `c`.

`Pgm a` is a compiled version of a program that outputs `a`. Again, `a` can be a function, so
`Pgm (b -> c)` is a compiled program that inputs `b` and outputs `c`.

Pgm can be a binary executable format, source code in a different language, or source code in the
original language. Most implementations of partial evaluation target the original language, i.e.
Src = Pgm. Here I leave them distinct for the sake of generality.

Partial evaluation can be typed as

> mix' :: Src (staticInput -> dynamicInput -> output) -> staticInput -> Pgm (dynamicInput -> output)
> mix' = undefined

i.e. it inputs the source code of a program with two inputs, a value for one of those inputs, and
outputs a program that takes in the remaining missing input. In the first example, this instantiates
to

> mixRepeatedlyPrint :: Src (Int -> String -> IO ()) -> Int -> Pgm (String -> IO ())
> mixRepeatedlyPrint = undefined

However, I will use the following more general type:

> mix :: Src (staticInput -> a) -> staticInput -> Pgm a
> mix = undefined

because `a` can just be instantiated to `dynamicInput -> output`. The source code of mix is

> srcMix :: Src (Src (staticInput -> a) -> staticInput -> Pgm a)
> srcMix = undefined

An interpreter is simply

> interpret :: Src a -> a
> interpret = undefined

and the source code of an interpreter is

> srcInterpreter :: Src (Src a -> a)
> srcInterpreter = undefined

We can represent an arbitrary program as

> program :: i -> o
> program = undefined

and its source code as

> srcProgram :: Src (i -> o)
> srcProgram = undefined

We now have everything set up. Time to experiment.

What happens if we give the source code of an interpreter to our partial evaluator?

ghci> :t mix srcInterpreter srcProgram
mix srcInterpreter srcProgram :: Pgm (i -> o)

We get a compiled version of srcProgram. This is the first Futamura projection. `mix srcInterpreter`
is a compiler! But it's bloated and not very fast. We have to keep the partial evaluator AND the
interpreter around every time we want to compile something. Or do we?

What if we combine mix with itself and the interpreter?

ghci> :t mix srcMix srcInterpreter
mix srcMix srcInterpreter :: Pgm (Src a -> Pgm a)

NOW we have a true compiler. This is the second Futamura projection.

Just for kicks, what if we combine mix with itself and only itself?

ghci> :t mix srcMix srcMix
mix srcMix srcMix
  :: Pgm (Src (staticInput -> a) -> Pgm (staticInput -> Pgm a))

This is pretty general. `staticInput` can be anything. But what if we instantiate it to `Src a`?

mix srcMix srcMix
  :: Pgm (Src (Src a -> a) -> Pgm (Src a -> Pgm a))

We saw before that `interpret :: Src a -> a`. It's also clear that a compiler is
`compile :: Src a -> Pgm a`. So we can think of that signature as

type Interpreter a = Src a -> a
type Compiler a = Src a -> Pgm a
mix srcMix srcMix
  :: Pgm (Src (Interpeter a) -> Pgm (Compiler a))

i.e. it inputs interpreters, and outputs compilers. This is the third Futamura projection.