A-normal form: Difference between revisions
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]], ''' |
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
- allowing only constants, λ-terms, and variables, to serve as arguments of function applications, and
- 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
- ^ 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)