In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, A-normal form (abbreviated ANF) is an
intermediate representation
An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive to further processing, such as optimization and translation. A "good" ...
of
program
Program, programme, programmer, or programming may refer to:
Business and management
* Program management, the process of managing several related projects
* Time management
* Program, a part of planning
Arts and entertainment Audio
* Progra ...
s in
functional compilers.
In ANF, all
argument
An argument is a statement or group of statements called premises intended to determine the degree of truth or acceptability of another statement called conclusion. Arguments can be studied from three main perspectives: the logical, the dialectic ...
s to a
function
Function or functionality may refer to:
Computing
* Function key, a type of key on computer keyboards
* Function model, a structured representation of processes in a system
* Function object or functor or functionoid, a concept of object-oriente ...
must be trivial (constants or variables). That is, evaluation of each argument must halt immediately.
ANF is introduced by Sabry and
Felleisen in 1992 as a simpler alternative to
continuation-passing style In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
(CPS). Some of the advantages of using CPS as an intermediate representation are that optimizations are easier to perform on programs in CPS than in the source language, and that it is also easier for compilers to generate
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
for programs in CPS. Flanagan et al.
showed how compilers could use ANF to achieve those same benefits with one source-level transformation; in contrast, for realistic compilers the CPS transformation typically involves additional phases, for example, to simplify CPS terms.
This article deals with the basic definition expressed in terms of the
λ-calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...
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
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...
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.
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
*
Continuation-passing style In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. This is contrasted with direct style, which is the usual style of programming. Gerald Jay Suss ...
*
Static single assignment form In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing var ...
References
Functional programming
Implementation of functional programming languages
{{prog-lang-stub