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

DEFUNCTIONALIZATION every closure becomes a tag; higher-order vanishes

A whole program has only finitely many lambdas, so tag each with an integer, replace every first-class function value with a plain data record (the tag + its captured variables), and replace every call with one first-order apply(tag, arg) that switches on the tag. Higher-order functions disappear — the exact transformation a language with no first-class functions needs.

THE TECHNIQUE tag the lambdas; one apply dispatches

A higher-order map(f, [1,2,3]) with f = λn.n+10 uses a first-class function. Defunctionalize: represent each lambda by a tag — tag 0 for λn.n+10, tag 1 for λn.n*2 — and dispatch with one apply(tag, n). Now it runs with no closures at all. live demo







  
HISTORY & CREDIT coined 1972, revived 2001

  
“Defunctionalization = closure conversion” — no. Closure conversion keeps functions first-class (a code-pointer + environment, called indirectly); defunctionalization is first-order (a tag + a switch). cited

  

    1960 / 1964 · McCarthy’s global apply; Landin’s closure already represents a function as a data structure — Reynolds did not invent functions-as-data.

    1972 · John Reynolds — “Definitional Interpreters for Higher-Order Programming Languages”: coins defunctionalization — finitely many lambdas, so tag them and switch.

    2001 · Danvy & Nielsen — “Defunctionalization at Work”: revives the term (unused for ~30 years) and gives the modern analysis.

    2003 / 2004 · Ager-Biernacki-Danvy-Midtgaard derive SECD/CEK/Krivine by CPS + defunctionalize the continuation; Pottier & Gauthier show it is type-preserving via GADTs.
  

  
The inverse (refunctionalization) is Danvy (2006), only a left inverse. Whole-program compilers (MLton) defunctionalise to tagged records. Reynolds, 1972






  
RECOMMEND FOR I-13 the technique the corpus already lives by

  
I-13 has no first-class functions — so defunctionalization is not a demo, it is how the whole corpus runs:

  
$ i13 run defun.i13   # no closures; apply(tag, x) dispatches on an integer tag
apply(0, 5) = 15   apply(1, 5) = 10
map(tag 0, [1,2,3]) = [11, 12, 13]   -- higher-order map, running with NO closures

  

    Recommend: the technique is LIT and load-bearing — a “function value” is an integer tag, and apply(tag, x) is an if-chain that dispatches (verified apply(0,5)=15, apply(1,5)=10, and map over [1,2,3] with tag 0 → [11,12,13]). Because I-13 has no closures, this is exactly how every higher-order pattern (map, fold, callbacks) is expressed on the corpus — Reynolds’ 1972 transformation is the corpus’s native idiom.

    Note: it is the deep tie of the whole batch — SECD (142), Krivine (143), SKI (144), and CPS (149) all become runnable on a closureless language precisely by defunctionalizing their higher-order parts (the closure, the continuation). Captured free variables want a record (PS-015); here the lambdas are closed, so a bare tag suffices.