In
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, A-normal form (abbreviated ANF, sometimes expanded as administrative normal form or as atomic normal form) 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 (American English; also Commonwealth English in terms of computer programming and related activities) or programme (Commonwealth English in all other meanings), programmer, or programming may refer to:
Business and management
* Program m ...
s in
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
language
compiler
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
s.
In ANF, all
argument
An argument is a series of sentences, statements, or propositions some of which are called premises and one is the conclusion. The purpose of an argument is to give reasons for one's conclusion via justification, explanation, and/or persu ...
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-orie ...
must be trivial (constants or variables). That is, evaluation of each argument must halt immediately.
ANF was 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 S ...
(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 computer code consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). For conventional binary computers, machine code is the binaryOn nonb ...
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.
Grammar
Consider the pure
λ-calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computation based on function abstraction and application using variable binding and substitution. Untyped lambda calculus, the topic ...
with constants and
let-expressions. The ANF restriction is enforced by
# allowing only ''values'' (variables, constants, and λ-terms), to serve as operands of function applications, and
# requiring that the result of a non-trivial expression (such as a function application) be immediately captured in a
let-bound variable.
The following
BNF grammars show how one would modify the syntax of λ-expressions to implement the constraints of ANF:
Variants of ANF used in compilers or in research often allow 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)
By imagining the sort of assembly this function call would produce:
;; let v0 = g(x)
move x into args
call g
move result into temp
;; let v1 = h(y)
move y into args
call h
move result into temp
;; f(v0, v1)
move temp
into args
move temp
into args
call f
One can see the immediate similarities between ANF and the compiled form of a function; this property is a part of what makes ANF a good intermediate representation for optimisations in compilers.
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 S ...
*
Static single assignment form
In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of intermediate representation (IR) where each variable is assigned exactly once. SSA is used in most high-quality optimizing compilers for ...
References
Functional programming
Implementation of functional programming languages
{{prog-lang-stub