A-normal form

In computer science, A-normal form (abbreviated ANF, sometimes expanded as administrative normal form) is an intermediate representation of programs in functional programming language compilers. In ANF, all arguments to a function must be trivial (constants or variables). That is, evaluation of each argument must halt immediately.

ANF was introduced by Sabry and Felleisen in 1992[1] as a simpler alternative to continuation-passing style (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 for programs in CPS. Flanagan et al.[2] 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 with weak reduction and let-expressions. The ANF 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.

The following BNF grammar describes the syntax of λ-expressions 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)

By imagining the sort of assembly this function call would produce:

;; let v0 = g(x)
move x into args[0]
call g
move result into temp[0]
;; let v1 = h(y)
move y into args[0]
call h
move result into temp[1]
;; f(v0, v1)
move temp[0] into args[0]
move temp[1] into args[1]
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

References
  1. Sabry, Amr; Felleisen, Matthias. "Reasoning about Programs in Continuation-Passing Style". Proceedings of the 1992 ACM Conference on LISP and Functional Programming, LFP'92. San Francisco, CA, USA. CiteSeerX 10.1.1.22.7509. Sabry92.
  2. Flanagan, Cormac; Sabry, Amr; Duba, Bruce F.; Felleisen, Matthias. "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 2012-11-16.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.