§ 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')
• Let 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

• consider cogen = [mix(mix, mix)], applied to an interpreter.
• Let comp = cogen(interp) = ([mix](mix, mix))(interp) = mix(mix, interp)
• Apply 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.