◄ WORLD V · SONNY 5DART 146 · a helldive at the net

FUTAMURA specialize an interpreter and you have a compiler

Partial evaluation folded on itself. Specialize an interpreter to one fixed source program and you get that program compiled (1st projection). Specialize the specializer to the interpreter and you get a compiler (2nd). Specialize the specializer to itself and you get a compiler-generator (3rd). One operation — partial evaluation — applied three times.

THE TECHNIQUE fold the static input away

A generic power(base, exp) loops exp times — it must test and decrement the exponent every call. Specialize it with exp = 3 fixed: the loop unrolls away, leaving straight-line base*base*base with no exponent parameter and no loop test. The interpreter + the fixed program = the compiled program. live demo







  
HISTORY & CREDIT stated 1971, realised 1984

  
“Futamura built a compiler by self-application in 1971” — he stated the projections; no self-applicable partial evaluator existed until 1984–85. cited

  

    1938 / 1952 · Kleene’s s-m-n theorem — a specializer exists, but its trivial construction just staples the input on and adds overhead.

    1971 · Yoshihiko Futamura — states the three projections (interpreter+program = compiled; specialize the specializer = compiler; again = compiler-generator). Stated, not implemented.

    1977 · Andrei Ershov (USSR) — mixed computation independently; the DIKU group later named their partial evaluator “mix” after Ershov’s term (neither is Futamura’s).

    1984–93 · Jones, Sestoft & Søndergaard (Copenhagen) — the first self-applicable mix (binding-time analysis makes self-application work); the 1993 book fixes the canonical statement. Modern form: PyPy’s meta-tracing, Truffle/Graal.
  

  
Self-application is not required — you can write the compiler-generator (cogen) by hand; and specialization does not always speed things up (over-unrolling bloats code). Futamura, 1971






  
RECOMMEND FOR I-13 the generic loop vs the unrolled code

  
The generic interpreter and its specialization both run — the specialized one does fewer operations:

  
$ i13 run futa.i13   # power(base, exp) generic vs pow3 specialized (exp=3)
generic power(2, 3) = 8   (3 multiplies + a loop test each step)
specialized pow3(5) = 125 (base*base*base, exponent + loop folded away)

  

    Recommend: nothing new — the generic power(base, exp, acc, mults) recurses over the exponent, threading a multiply-count; the specialized pow3(base) = base*base*base has no exponent parameter and no loop test (verified generic 2³=8 in 3 multiplies; pow3(5)=125). The specialization is the 1st projection: interpreter + fixed program = compiled program.

    Note: it is the corpus’s own shape at the meta-level — the campaign grounds each dart by specializing a general algorithm to one concrete input and running it. Full self-applicable mix wants a program representation to specialize (a term/AST arena, PS-015).