A-normal form

ANF was introduced by Sabry and Felleisen in 1992 as a simpler alternative to continuation-passing style (CPS). Some of the advantages of using CPS as an intermediate representation are that optimizations are easier to perform on programs in CPS than in the source language, and that it is also easier for compilers to generate machine code for programs in CPS. Flanagan et al. showed how compilers could use ANF to achieve those same benefits with one source-level transformation; in contrast, for realistic compilers the CPS transformation typically involves additional phases, for example, to simplify CPS terms.

Grammar

Consider the pure λ-calculus with constants and let-expressions. The ANF restriction is enforced by

1. allowing only values (variables, constants, and λ-terms), to serve as operands of function applications, and
2. requiring that the result of a non-trivial expression (such as a function application) be immediately captured in a let-bound variable.

The following BNF grammars show how one would modify the syntax of λ-expressions to implement the constraints of ANF:

Variants of ANF used in compilers or in research often allow records, tuples, multiargument functions, primitive operations and conditional expressions as well.