A-normal form

This article relies too much on references to primary sources. Please improve this by adding secondary or tertiary sources. (October 2011) (Learn how and when to remove this template message)

In computer science, A-normal form (abbreviated ANF) is an intermediate representation of programs in . In ANF, all arguments to a function must be trivial (constants or variables). That is, evaluation of each argument must halt immediately.

ANF is introduced by Sabry and Felleisen in 1992^[1] 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.^[2] 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.

This article deals with the basic definition expressed in terms of the λ-calculus with weak reduction and let-expressions, where the restriction is enforced by

1. allowing only constants, λ-terms, and variables, to serve as arguments of function applications, and
2. requiring that the result of a non-trivial expression be captured by a let-bound variable or returned from a function.

Grammar[]

The following BNF grammar describes the pure λ-calculus modified to support the constraints of ANF:

EXP ::= VAL 
      | let VAR = VAL in EXP
      | let VAR = VAL VAL in EXP

VAL ::= VAR
      | λ VAR . EXP

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

Examples[]

The expression:

f(g(x),h(y))

is written in ANF as:

let v0 = g(x) in
    let v1 = h(y) in
        f(v0,v1)

See also[]

• Continuation-passing style
• Static single assignment form

References[]

This programming-language-related article is a stub. You can help Wikipedia by .

• v
• t