§ Partial Evaluation, Chapter 1
out = [[p]](i, i'), then
p1 = [[mix]](p, i); out = [[p1]](i').
- Alternatively, can write as
[[p]](i, i') = [[ [[mix]](p, i) ]](i')
S be the source language (Early Rust). Let
T be the target language (assembly). Let
Lbe the language that the interpreter for
S is implemented in (OCaml).
- See that we have the equation
out = [source]_S (in), or
out = [interp]_L (source, in).
- That's the equation for the interpreter.
- a compiler produces a target program, so we have
target = [compiler]_L(source). Running the target and source programs should have the same effect, so
[target]_T(in) = [source]_S(in).
- Written differently, this is
[ [compiler]_L(source) ]_T(in) = [source]_S(in).
§ First futamura projection
out = [source]_S (in)
out = [int](source, in)
out = [[mix](int, source)](in)
- But by definition of
target, we have
out = target(in)
- Thus, we see that
target = [mix](int, source). We get the compiled output program/target program by partially applying the interpreter to the source program.
§ Second futamura projection
- Start with
target = [mix](int, source).
- Now partially apply,
target = [mix(mix, int)](source).
- But we know that
target = compiler(source). So we must have
[mix(mix, int)] = compiler.
- A compiler is obtained by partially applying the partial applier against the interpreter. Thus, when fed an input, it partially evaluates the interpreter against any input, giving us a compiler.
§ Third futamura projection
cogen = [mix(mix, mix)], applied to an interpreter.
comp = cogen(interp) = ([mix](mix, mix))(interp) = mix(mix, interp)
comp(source). This gives us
comp(source) = mix(mix, interp)(source) = mix(interp, source) = target.
- Thus, we have create a compiler generator, which takes an interpreter and produces a compiler.