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?

Saltwater

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 
      | 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.

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.

Multure

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.

Dulse

the link you've shared is broken, could you share the title or doi of the paper? thanks – Square

Sorry. It's Types Are Calling Conventions, by Bolingbroke and Peyton Jones. – Dulse