{"size": 4131, "ext": "scrbl", "max_stars_repo_path": "rackpropagator-doc/rackpropagator/scribblings/anf.scrbl", "max_stars_repo_name": "ots22/rackpropagator", "max_stars_repo_stars_event_min_datetime": "2020-02-14T03:37:57.000Z", "max_stars_repo_stars_event_max_datetime": "2022-01-31T11:20:59.000Z", "max_issues_repo_path": "rackpropagator-doc/rackpropagator/scribblings/anf.scrbl", "max_issues_repo_name": "ots22/rackpropagator", "max_issues_repo_issues_event_min_datetime": "2022-01-03T14:01:10.000Z", "max_issues_repo_issues_event_max_datetime": "2022-01-03T22:05:51.000Z", "max_forks_repo_path": "rackpropagator-doc/rackpropagator/scribblings/anf.scrbl", "max_forks_repo_name": "ots22/rackpropagator", "max_forks_repo_forks_event_min_datetime": "2022-01-03T13:34:07.000Z", "max_forks_repo_forks_event_max_datetime": "2022-01-03T13:34:07.000Z"}
{"max_stars_count": 11, "max_issues_count": 1, "max_forks_count": 1, "avg_line_length": 27.357615894, "max_line_length": 84, "alphanum_fraction": 0.6966836117}
#lang scribble/manual

@(require "common.rkt")

@title{A-Normal Form}

@defmodule[rackpropagator/anf]

This module provides some utilities for transforming code into
Administrative Normal Form, as introduced by @citet[flanagan1993].
See also this excellent
@hyperlink["https://matt.might.net/articles/a-normalization/"]{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
@secref{Supported_Language}.

@section{A-Normal Form (first kind)}

@racketgrammar*[
#:literals (#%plain-lambda #%plain-app if set! let-values quote quote-syntax)

[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 (@#,racket[quote] datum)
         (quote-syntax datum)
         (quote-syntax datum #:local)]

[formals (id ...)
         id
         (id ...+ . id)]

]

@section{A-Normal Form (second kind)}

@racketgrammar*[
#:literals (#%plain-lambda #%plain-app if set! let-values quote quote-syntax)

[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)]

]

@racket[literal] and @racket[formals] are the same as in ANF1.

ANF2 has a more restricted grammar than ANF1:
@itemlist[

@item{The body of a @racket[let-values] can only be an identifier or
another @racket[let-values]}

@item{All function applications are made in a @racket[let-values]
binding (no explicit tail calls)}

@item{Function application and @racket[if] only use identifiers
(wrapped in thunks in the branches of an @racket[if])}

]


@section{Functions for converting to ANF}

@defproc[(anf1-normalize [stx syntax?] [k procedure? identity]) anf1?]{

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

@defproc[(anf1? [stx syntax?]) boolean?]{
Is @racket[stx] in first A-normal form?
}

@defproc[(anf1->2 [stx anf1?]) anf2?]{
Convert @racket[stx], which must be in first A-normal form, to second A-normal form.
}

@defproc[(anf2-normalize [stx syntax?]) anf2?]{

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

@defproc[(anf2? [stx syntax?]) boolean?]{
Is @racket[stx] in second A-normal form?
}

@defproc[(anf-normalize [stx syntax?]) anf2?]{
The same as @racket[anf2-normalize].
}

@defproc[(anf? [stx syntax?]) boolean?]{
The same as @racket[anf2?].
}

@section{Box mutated bindings}

@defproc[(set!->set-box! [stx anf2?]) anf2?]{

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

@section{Utilities}

@defproc[(anf-expand-expression [expr syntax?]) anf2?]{
Fully-expand @racket[expr], convert to ANF2 and convert all uses of
@racket[set!] to @racket[set-box!].  This procedure must be called
during the dynamic extent of a syntax transformer application (see
@racket[syntax-transforming?]).
}

@(require (for-label syntax/id-set syntax/free-vars))
@defproc[(anf-free-vars [stx anf2?]) free-id-set?]{
Returns a set of identifiers that are free within @racket[stx].

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

@defproc[(anf-outer-binding [expr anf2?]) syntax?]{
Given an expression in ANF2, extract and return the outermost let-bound
expression.
}
