Futamura Projections in a Nutshell

Futamura Projections are usually described with a lot of words, but they are much simpler to understand in types.

There are Interpreters, Compilers, and Specializers:

a -> b                           -- Specialized Machine
(a -> b)' -> a -> b              -- Interpreter
(a -> b)' -> (a -> b)            -- Compiler
(a -> b -> c)' -> a -> (b -> c)  -- Specializer

Futamura 1: Specializing an Interpreter at a Program results in an Executable

((a -> b)' -> a -> b)' -> (a -> b)' -> (a -> b)

Futamura 2: Specializing a Specializer at an Interpreter results in a Compiler

(((a -> b)' -> a -> b)' -> (a -> b)' -> (a -> b))' ->
  ((a -> b)' -> a -> b)' -> ((a -> b)' -> (a -> b))

Futamura 3: Specializing a Specializer at a Specializer results in an Interpreter -> Compiler Compiler

(((a -> b -> c)' -> a -> (b -> c))' ->
  (a -> b -> c)' -> a -> (b -> c))' ->
((a -> b -> c)' -> a -> (b -> c))' ->
((a -> b -> c)' -> a -> (b -> c))