5 A-Normal Form

8.3

5 A-Normal Form

(require rackpropagator/anf)
	package: rackpropagator-lib

This module provides some utilities for transforming code into Administrative Normal Form, as introduced by Flanagan et al. (1993). See also this excellent guide.

Routines are provided to transform into two related normal forms. The first is close to ANF as described in the reference above, the second is a variant consumed by the reverse transformation (to perform reverse-mode AD).

The input syntax must match the grammar given in Supported Language.

5.1 A-Normal Form (first kind)

anf1-val	=	literal
	\|	id
	\|	(#%plain-lambda formals anf1-expr)

anf1-cexpr	=	anf1-val
	\|	(#%plain-app anf1-val anf1-val ...)
	\|	(if anf1-val anf1-expr anf1-expr)
	\|	(set! id anf1-val)

anf1-expr	=	anf1-cexpr
	\|	(let-values (((id) anf1-cexpr)) anf1-expr)

literal	=	(quote datum)
	\|	(quote-syntax datum)
	\|	(quote-syntax datum #:local)

formals	=	(id ...)
	\|	id
	\|	(id ...+ . id)

5.2 A-Normal Form (second kind)

anf2-val	=	literal
	\|	id
	\|	(#%plain-lambda formals anf2-expr)

anf2-cexpr	=	anf2-val
	\|	(#%plain-app id id ...)
	\|	(if id (#%plain-app id) (#%plain-app id))
	\|	(set! id anf2-val)

anf2-expr	=	id
	\|	(let-values (((id) anf2-cexpr)) anf2-expr)

literal and formals are the same as in ANF1.

ANF2 has a more restricted grammar than ANF1:

The body of a let-values can only be an identifier or another let-values
All function applications are made in a let-values binding (no explicit tail calls)
Function application and if only use identifiers (wrapped in thunks in the branches of an if)

5.3 Functions for converting to ANF

procedure
(anf1-normalize stx [k]) → anf1?
stx : syntax?
k : procedure? = identity

Convert stx, which must be fully-expanded syntax, to first A-normal form. An explicit continuation k may be passed.

procedure
(anf1? stx) → boolean?
stx : syntax?

Is stx in first A-normal form?

procedure
(anf1->2 stx) → anf2?
stx : anf1?

Convert stx, which must be in first A-normal form, to second A-normal form.

procedure
(anf2-normalize stx) → anf2?
stx : syntax?

Convert stx, which must be fully-expanded syntax, to second A-normal form. Equivalent to (anf1->2 (anf1-normalize stx)).

procedure
(anf2? stx) → boolean?
stx : syntax?

Is stx in second A-normal form?

procedure
(anf-normalize stx) → anf2?
stx : syntax?

The same as anf2-normalize.

procedure
(anf? stx) → boolean?
stx : syntax?

The same as anf2?.

5.4 Box mutated bindings

procedure
(set!->set-box! stx) → anf2?
stx : anf2?

Convert all bindings that are mutated with set!, to boxed values, and all uses of set! to corresponding uses of set-box!. The resulting syntax is in second A-normal form, but with no uses of set!.

5.5 Utilities

procedure
(anf-expand-expression expr) → anf2?
expr : syntax?

Fully-expand expr, convert to ANF2 and convert all uses of set! to set-box!. This procedure must be called during the dynamic extent of a syntax transformer application (see syntax-transforming?).

procedure
(anf-free-vars stx) → free-id-set?
stx : anf2?

Returns a set of identifiers that are free within stx.

Similar to free-vars with a true value passed as module-bound?, except this procedure does not depend on the enriched lexical context from expansion.

procedure
(anf-outer-binding expr) → syntax?
expr : anf2?

Given an expression in ANF2, extract and return the outermost let-bound expression.

contents ← prev up next →

1	Supported Language
2	Automatic differentiation
3	Linear generic interface
4	Registering primitives
5	A-Normal Form
6	Limitations
	Bibliography

5.1	A-Normal Form (first kind)
5.2	A-Normal Form (second kind)
5.3	Functions for converting to ANF
5.4	Box mutated bindings
5.5	Utilities