What is the A-Normal Form?

Question

I was reading about various intermediate forms but I cant get information about A-normal forms besides the wiki-like entries. Does anyone here know about this or has good resources about it?

Answer 1

See Administrative normal form.

In computer science, administrative normal form (abbreviated ANF) is a canonical form of programs, which was introduced by Flanagan et al 1993 to serve as an intermediate representation in functional compilers to make subsequent transformations to machine code more direct.

In ANF, all arguments to a function must be trivial. That is, evaluation of each argument must halt immediately.

Grammar

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

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

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

Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.;Felleisen, Matthias. "The Essence of Compiling with Continuations" likely is the definitive source.

Also found some notes on cs252r : Advanced Functional Programming.

Answer 2

In essence, a lambda term in administrative normal form can be read as a procedure for evaluating itself, since all arguments to applications must already be in 'evaluated' and thus the order in which arguments should be evaluated must necessarily be made explicit.

There's an interesting overview in this independently interesting paper on a strict intermediate language for compiling lazy functional languages. Section 3.1 et seq, and especially figure 7 which gives a small-step operational semantics for a strict language in administrative normal form.