A-Normal Form is a sweet spot during program compilation.

In the first half of compilation, linguistic complexity rises:

• Characters become a token stream.
• Token streams become a parse tree.
• A parse tree becomes an abstract syntax tree.
• An abstract syntax tree becomes an annotated syntax tree.

In the second half of compilation, linguistic complexity falls.

Typically, the first drop is a desugaring phase which removes complex language features by transforming them into core language features.

In functional compilers, a transformation to A-Normal Form (ANF) [introduced in 1993 by Flanagan, Sabry, Duba and Felleisen] is often the next drop in complexity.

A-Normal Form syntactically sequentializes computations, and it partitions expressions into two classes: atomic expressions and complex expressions.

Because it (implicitly) simplifies the internal structure of continuations, it is easier to construct an interpreter for A-Normal Form.

For the same reason, it is easier to generate machine code or construct a static analyzer.

A later transformation to continuation-passing style (like that in Appel's book) is also simplified if transforming from A-Normal Form.

In short, a-normalization saves a lot of programmer effort in compilation.

Read on for an overview of A-Normal Form and code for a-normalization.

A-Normal Form

Syntactically, A-Normal form partitions expressions into two forms: atomic expressions and complex expressions.

An expression is atomic if:

• it is guaranteed to terminate;