Administrative normal form
Encyclopedia
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 compiler
s 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
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.
f(g(x),h(y))
is written in ANF as:
let v0 = g(x) in
let v1 = h(y) in
f(v0,v1)
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, administrative normal form (abbreviated ANF) is a canonical
Canonical
Canonical is an adjective derived from canon. Canon comes from the greek word κανών kanon, "rule" or "measuring stick" , and is used in various meanings....
form of programs, which was introduced by Flanagan et al. 1993 to serve as an intermediate representation in functional compiler
Functional compiler
A functional compiler is a compiler for a functional programming language. Functional compilers perform such transformation on source code which transform it to continuation-passing style or administrative normal form and need to handle tail calls correctly....
s to make subsequent transformations to machine code
Machine code
Machine code or machine language is a system of impartible instructions executed directly by a computer's central processing unit. Each instruction performs a very specific task, typically either an operation on a unit of data Machine code or machine language is a system of impartible instructions...
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
- require that the result of a non-trivial expression are captured by a let-bound variable or returned from a function.
Grammar
The following BNFBackus–Naur form
In computer science, BNF is a notation technique for context-free grammars, often used to describe the syntax of languages used in computing, such as computer programming languages, document formats, instruction sets and communication protocols.It is applied wherever exact descriptions of...
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)