THE A-NORMAL FORM name every intermediate result — the functional IR
A-normal form (ANF) is three-address code for functional languages: every intermediate result is let-bound to a name, and function arguments must be trivial (a variable or constant, never a nested call). f(g(x)) becomes let t = g(x) in f(t). It makes evaluation order explicit and every subcomputation nameable — the same clarity TAC gives imperative code, in a form that respects functions and scope. Flanagan, Sabry, Duba & Felleisen showed it captures “the essence of compiling with continuations” without the full CPS transform: the good part of CPS, in direct style.
THE TECHNIQUE let-bind every intermediate; arguments are trivial
A nested expression converted to ANF, one let per intermediate. The demo names each step and counts the bindings: live demo
HISTORY & CREDIT Flanagan, Sabry, Duba & Felleisen, 1993
“To compile functional code you must go through CPS.” — ANF captures the same sequencing and naming CPS gives you, in readable direct style. You get the essence of compiling with continuations without turning the whole program inside out. cited
1993 · Flanagan, Sabry, Duba & Felleisen — “The Essence of Compiling with Continuations” (PLDI): ANF as the direct-style equivalent of CPS. lineage · the functional cousin of three-address code (dart 265). now · the IR of choice for many functional compilers (GHC's Core is close; Scheme/ML backends).
Name every intermediate and fix the evaluation order, and a functional program reads like a linear sequence of simple steps — CPS's benefit without CPS's inversion. Flanagan et al. 1993
RECOMMEND FOR I-13 ANF let-bindings, computed
On the canonical compiler, converting (2+3)*4 to ANF introduces 2 let-bindings and reaches 20:
$ i13 run m_anf.i13 # let x1 = 2+3 in let x2 = x1*4 in x2
RUN OK . 12 step(s) . peak stack 2 . call depth 0
x1 = 5
x2 = 20
lets = 2
Recommend: i13's syntax is essentially ANF already. Its bindings I x1 <- 2+3 name every intermediate, its function arguments are simple values, and it has no nested-call-as-argument surprise — exactly ANF's two rules (let-bind intermediates, trivial arguments). That is why i13's single-assignment globals gave it near-SSA for free (dart 232): ANF and SSA are close kin. i13 didn't adopt ANF; its grammar landed there by insisting every value be named once — the same austerity that runs through its whole design.