Futamura Projections

Last update: Fri Jun 19 18:22:26 EEST 2026

Imagine that we have the following function:

const add = (a, b) => a + b;

There is a technique called currying where you turn a function of many inputs into functions of one input by chaining and nesting.

const adder = a => b => a + b;

const add2 = adder(2);

add(2, 3) == add2(3)

Imagine that instead have a partial evaluator function called ρ(α, β) which takes a function α and a value β and then partially evaluates α by fixing the first argument of α to the value of β thus returning that as a new function γ. Doing the above with this:

const add2 = p(add, 2);

add(2, 3) == add2(3)

So the general form of what we’re talking about is:

const p = (a : (a, b) => c, b) => b => c // partial evaluator
// where argument a of function a is fixed to a value

Which somehow lands us with the Futamura projections:

exe = p(interpreter, program)

compiler = p(p, interpreter)

cogen : interpreter => compiler = p(p, p) // compiler generator

In the first ρ creates an executable from an interpreter and a program.

In the second ρ creates a compiler from the partial evaluator and an interpreter.

In the third ρ creates a compiler generator to turn interpreters into compilers. Well… to be more exact it only works for certain kind of interpreters, but the amazing part is that it can be done in the first place.