Came across Futamura projections while read the wiki for Partial evaluation.

  1. Specializing an interpreter for given source code, yielding an executable.
  2. Specializing the specializer for the interpreter (as applied in #1), yielding a compiler.
  3. Specializing the specializer for itself (as applied in #2), yielding a tool that can convert any interpreter to an equivalent compiler.

I had to admit that it’s mind-flowing to me. The text description in the wiki is quite mouthful, so here’s an attempt to express it using Haskell type systems.

1
2
3
4
5
6
7
8
data Source
data Value

type Excutable = () -> Value
type Interpreter = Source -> Value

partial :: Interpreter -> Source -> Excutable
partial eval source = \() -> eval source

partial does the first projection, that given the Interpreter and Source, we could obtain the final Excutable. Not so difficult.

The second projections says that we could construct one compiler out of a interpreter. Realizing that compiler is no more than the following:

1
type Compiler = Source -> Excutable

partial does the second projection as well with no modification at all. Maybe we are just lucky.

The third projection says that we could construct a tool that converts any interpreter to an equivalent compiler. Isn’t partial itself?

1
partial :: Interpreter -> Compiler

It turns out that the partial we constructed above covers all three projections, which, to some extent, surprised me, and illustrates the powerful insight from function currying.