Jump to content

A-normal form: Difference between revisions

From Wikipedia, the free encyclopedia
Content deleted Content added
a-normal form
m The A is just "A" as in "set of Axioms"; it doesn't stand for "Administrative".
Line 1: Line 1:
{{primary sources|date=October 2011}}
{{primary sources|date=October 2011}}
In [[computer science]], '''administrative normal form''' (abbreviated '''A-normal form''' or '''ANF''') is a form of [[program (computer science)|program]]s introduced by Flanagan et al. in 1993<ref>{{cite conference
In [[computer science]], '''A-normal form''' (abbreviated '''ANF''') is a form of [[program (computer science)|program]]s introduced by Flanagan et al. in 1993<ref>{{cite conference
| id = Flanagan93
| id = Flanagan93
| first = Cormac
| first = Cormac

Revision as of 00:09, 16 November 2012

In computer science, A-normal form (abbreviated ANF) is a form of programs introduced by Flanagan et al. in 1993[1] 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.

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

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

References

  1. ^ Flanagan, Cormac. "The Essence of Compiling with Continuations" (PDF). Proceedings ACM SIGPLAN 1993 Conf. on Programming Language Design and Implementation, PLDI'93. Albuquerque, NM, USA. Flanagan93. Retrieved 2007-06-05. {{cite conference}}: Unknown parameter |booktitle= ignored (|book-title= suggested) (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)