A-normal form (ANF)

Purpose

Most functional compilers use CPS as IR. Benefits are easier optimizations and generation of machine code.

However CPS transformation typically involves additional phases, to simplify CPS terms.

ANF IR of programs in functional compilers as a simpler alternative to CPS.

Definition

All arguments to functions are trivial. I.e. the evaluation of each argument immediately halts.

Implementation

  1. Only constants, lambda-terms, variables can be function application arguments.
  2. result of Non-trivial expression MUST be captured by let-bound variable / returned from function.

Counter examples

Complex arguments:

f(g(x), h(y))

Must be rewritten:

let v0 = g(x) in
  let v1 = h(y) in
    f(v0, v1)
logo