A-Normalization: Why and How

A-Normal Form is a sweet spot during program compilation.

In the first half of compilation, linguistic complexity rises:

Characters become a token stream.
Token streams become a parse tree.
A parse tree becomes an abstract syntax tree.
An abstract syntax tree becomes an annotated syntax tree.

In the second half of compilation, linguistic complexity falls.

Typically, the first drop is a desugaring phase which removes complex language features by transforming them into core language features.

In functional compilers, a transformation to A-Normal Form (ANF) [introduced in 1993 by Flanagan, Sabry, Duba and Felleisen] is often the next drop in complexity.

A-Normal Form syntactically sequentializes computations, and it partitions expressions into two classes: atomic expressions and complex expressions.

Because it (implicitly) simplifies the internal structure of continuations, it is easier to construct an interpreter for A-Normal Form.

For the same reason, it is easier to generate machine code or construct a static analyzer.

A later transformation to continuation-passing style (like that in Appel’s Compiling with Continuations) is also simplified if transforming from A-Normal Form.

In short, a-normalization saves a lot of programmer effort in compilation.

Read on for an overview of A-Normal Form and code for a-normalization.

A-Normal Form

Syntactically, A-Normal form partitions expressions into two forms: atomic expressions and complex expressions.

An expression is atomic if:

it is guaranteed to terminate;
it causes no side effects;
it causes no control effects; and
it never produces an error.

In A-Normal Form, all non-atomic (complex) expressions must be let-bound, or else appear in tail position.

The following grammar describes a minimal A-Normal form, adapted from Flanagan et al.’s The Essence of Compiling with Continuations:

    <aexp> ::= NUMBER | STRING | VAR | BOOLEAN | PRIMOP
            |  (lambda (VAR ...) <exp>)

    <cexp> ::= (<aexp> <aexp> ...)
            |  (if <aexp> <exp> <exp>)

    <exp>  ::= (let ([VAR <cexp>]) <exp>)
            |  <cexp>
            |  <aexp>

Examples

Neither the function terms nor the arguments can be applications themselves:

  ((f g) (h x) 3)

  =>

  (let ([t0 (f g))
   (let ([t1 (h x))
    (t0 t1 3)))

Factorial:

  (define (f n)
       (if (= n 0)
           1
           (* n (f (- n 1)))))

  (f 20)

  =>

  (define f
    (λ (n)
      (let ((g1478 (= n 0)))
        (if g1478
          1
          (let ((g1479 (- n 1)))
            (let ((g1480 (f g1479)))
              (* n g1480)))))))
  (f 20)

Connection to assembly code

Juxtaposing some assembly pseudocode with code in A-Normal form hints at the connection between the two:

(define (celsius F)       ; celsius: mov F, a0
 (let ((t1 (/ 5 9)))      ;          div t1, 5, 9
   (let ((t2 (- F 32)))   ;          sub t2, F, 32
    (* t1 t2))))          ;          mul rv, t1, t2
                          ;          ret rv

The normalization process imparts a clear order to code.

Transforming to A-Normal Form

In the original paper, Flanagan et al. provide an A-Normalization algorithm in Scheme.

Remarkably, the code in that paper still works!

Not only does it work, but the code produces efficient output, and its structure is readily extended to new language forms.

Here it is with only cosmetic embellishment in Racket:

(define (Value? M)
  (match M
    [`(quote ,_)         #t]
    [(? number?)         #t]
    [(? boolean?)        #t]
    [(? string?)         #t]
    [(? char?)           #t]
    [(? symbol?)         #t]
    [(or '+ '- '* '/ '=) #t]
    [else                #f]))


(define (normalize-term M) (normalize M (λ (x) x)))

(define (normalize M k)
  (match M
    [`(λ ,params ,body)
      (k `(λ ,params ,(normalize-term body)))]

    [`(let ([,x ,M1]) ,M2)
      (normalize M1 (λ (N1)
       `(let ([,x ,N1])
         ,(normalize M2 k))))]

    [`(if ,M1 ,M2 ,M3)
      (normalize-name M1 (λ (t)
       (k `(if ,t ,(normalize-term M2)
                  ,(normalize-term M3)))))]

    [`(,Fn . ,M*)
      (normalize-name Fn (λ (t)
       (normalize-name* M* (λ (t*)
        (k `(,t . ,t*))))))]

    [(? Value?)             (k M)]))

(define (normalize-name M k)
  (normalize M (λ (N)
    (if (Value? N) (k N)
        (let ([t (gensym)])
         `(let ([,t ,N]) ,(k t)))))))

(define (normalize-name* M* k)
  (if (null? M*)
      (k '())
      (normalize-name (car M*) (λ (t)
       (normalize-name* (cdr M*) (λ (t*)
        (k `(,t . ,t*))))))))

With side effects and a top-level

It’s not hard to extend the original Flanagan et al. normalizer to handle top-level defines and side effects:

;; Input language:

;; <prog> ::= <dec> ...

;; <dec> ::= (define (<var> <name> ...) <exp>)
;;        |  (define <var> <exp>)
;;        |  <exp>

;; <exp> ::= (let ([<var> <exp>] ...) <exp>)
;;        |  (if <exp> <exp> <exp>)
;;        |  (set! <var> <exp>)
;;        |  (λ (<name> ...) <exp>)
;;        |  <number>
;;        |  <boolean>
;;        |  <string>
;;        |  <var>

;; Output language:

;; <prog> ::= <dec> ...

;; <dec> ::= (define <var> <exp>)
;;        |  (begin <dec> ...)
;;        |  <exp>

;; <aexp> ::= (λ (<name> ...) <exp>)
;;         |  <number>
;;         |  <boolean>
;;         |  <string>
;;         |  <var>
;;         |  (void)

;; <cexp> ::= (<aexp> <aexp> ...)
;;         |  (if <aexp> <exp> <exp>)
;;         |  (set! <var> <exp>)

;; <exp> ::= (let ([<var> <cexp>]) <exp>)
;;        |  <aexp>
;;        |  <cexp>

(define (atomic? exp)
  (match exp
    [`(quote ,_)   #t]
    [(? number?)   #t]
    [(? boolean?)  #t]
    [(? string?)   #t]
    [(? char?)     #t]
    [(? symbol?)   #t]
    [(or '+ '- '* '/ '=) #t]
    [else          #f]))


;; Expression normalization:
(define (normalize-term exp) (normalize exp (λ (x) x)))

(define (normalize exp k)
  (match exp
    [`(λ ,params ,body)
      (k `(λ ,params ,(normalize-term body)))]

    [`(let () ,exp)
      (normalize exp k)]

    [`(let ([,x ,exp1] . ,clause) ,exp2)
      (normalize exp1 (λ (aexp1)
       `(let ([,x ,aexp1])
         ,(normalize `(let (,@clause) ,exp2) k))))]

    [`(if ,exp1 ,exp2 ,exp3)
      (normalize-name exp1 (λ (t)
       (k `(if ,t ,(normalize-term exp2)
                  ,(normalize-term exp3)))))]

    [`(set! ,v ,exp)
      (normalize-name exp (λ (t)
       `(let ([,(gensym '_) (set! ,v ,t)])
          ,(k '(void)))))]

    [`(,f . ,e*)
      (normalize-name f (λ (t)
       (normalize-name* e* (λ (t*)
        (k `(,t . ,t*))))))]

    [(? atomic?)
     (k exp)]))

(define (normalize-name exp k)
  (normalize exp (λ (aexp)
    (if (atomic? aexp) (k aexp)
        (let ([t (gensym)])
         `(let ([,t ,aexp]) ,(k t)))))))

(define (normalize-name* exp* k)
  (if (null? exp*)
      (k '())
      (normalize-name (car exp*) (λ (t)
       (normalize-name* (cdr exp*) (λ (t*)
        (k `(,t . ,t*))))))))


;; Top-level normalization:
(define (normalize-define def)
  (match def
    [`(define (,f . ,params) ,body)
     `(define ,f ,(normalize-term `(λ ,params ,body)))]

    [`(define ,v ,exp)
     `(begin ,@(flatten-top (normalize-term exp) v))]))


(define (flatten-top exp v)
  (match exp
    [`(let ([,x ,cexp]) ,exp)
     (cons `(define ,x ,cexp)
            (flatten-top exp v))]

    [else
     `((define ,v ,exp))]))


(define (normalize-program decs)
  (match decs
    ['()
     '()]

    [(cons `(define . ,_) rest)
     (cons (normalize-define (car decs))
           (normalize-program rest))]

    [(cons exp rest)
     (cons (normalize-term exp)
           (normalize-program rest))]))

Code

More resources

For more on the compilation of functional languages, I recommend:

Andrew Appel’s Compiling with Continuations; and
Christian Queinnec’s Lisp in Small Pieces.
My post on continuation-passing style.