gnu.expr

Class ANormalize

java.lang.Object

gnu.expr.ExpVisitor<Expression,D>

gnu.expr.ExpExpVisitor<gnu.expr.ANormalize.Context>

gnu.expr.ANormalize

All Implemented Interfaces:

javax.xml.transform.SourceLocator, org.xml.sax.Locator

public class ANormalize
extends ExpExpVisitor<gnu.expr.ANormalize.Context>

A visitor that performs transformation to Administrative Normal Form. This is an adaptation and extension of the A-normalization algoritm described in the paper "The Essence of Compiling with Continuations" by Flanagan et al. and in "A-Normalization: Why and How" by Matt Might (http://matt.might.net/articles/a-normalization/). The algoritm performs a monadic transformation combining three steps:

1. Monadic conversion:

  (+ 1 (if (>= x 0) (f x) 0))
 

becomes:

  (bind (if (>= x 0)  (f x)  (return 0)) (lambda (t) (+ 1 t)))
 

2. The result is interpreted in the Identity monad:

                 (return a)  becomes:  a
 
    (bind a (lambda (x) b))  becomes:  (let ((x a)) b)
 

   (bind (if  (>= x 0)
             (f x)
             (return 0))
         (lambda (t) (+ 1 t)))
 

becomes:

   (let ((t (if  (>= x 0)
                (f x)
                (return 0))))
        (+ 1 t))
 

3. Nested let are flattened:

 
    (let ((x (let ((y a))               (let ((y a))
               b)))        becomes:          (let ((x b))
      c)                                    c))
 
 

In the actual Java code "return" operation is called "identity", while the "bind" operation is called "normalizeName" as in the Flanagan et al. paper. The ExpVisitor type matching mechanism replaces the role of the "match" in the paper, while the Context class replaces the "k" parameter. Lambdas are simulated with classes for backward compatibility with Java version 7 and lower. Each visit[...]Exp method is called with two parameters, an expression and a context (the very first context is the identity function that returns its argument). If the visit method is called with a non-atomic expression a new context is created and the passed context is called only inside the new one. The new-context is then passed to "normalizeName" that has two purposes: 1. to create a context, that generates a "let" expression to let-bind the expression next to come in the "visiting" process; 2. to call visit() on the passed expression, to continue the syntax tree traversing. This chain will finish when a leaf (an atomic expression) is encountered in the tree, in this case the passed context is invoked (which in turn will invoke the previous context and so on). At this point the chain of context invocations starts to wrap each expression in a "let" binding, processing the expressions backward, and enclosing them step by step in nested "let" expressions. This backward traversing stops when the context called is the identity function. When the expression to normalize is a conditional, "normalizeTerm" is used on each branch expression. Instead of creating a let binding for each branch, as they cannot be evaluated before the test outcome, "normalizeTerm" calls the visit method with the identity context, restarting the normalization in each branch.

Nested Class Summary

Nested classes/interfaces inherited from interface gnu.text.SourceLocator

SourceLocator.Simple

Field Summary

Fields inherited from class gnu.expr.ExpVisitor

currentLambda, exitValue, messages

Constructor Summary

Constructors

Constructor and Description
ANormalize()

Method Summary

Modifier and Type	Method and Description
static void	aNormalize(Expression exp, Compilation comp)
protected static boolean	isAtomic(Expression exp) Determines if an Expression is atomic, that is if it needs to be normalized or not.
protected Expression	normalizeName(Expression exp, gnu.expr.ANormalize.Context context) Performs the bind operation, introducing a new let expression to capture the result of non-trivial expressions, which is bound to a new let variable.
protected Expression	normalizeNames(Expression[] exps, int index, gnu.expr.ANormalize.MultiContext context) Deals with the normalization of multiple expressions.
protected Expression	normalizeTerm(Expression exp) Starts the normalization of expression exp.
protected CatchClause	toCatchClause(LetExp exp, CatchClause next)
protected Expression	visitApplyExp(ApplyExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitBeginExp(BeginExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitBlockExp(BlockExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitCaseExp(CaseExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitClassExp(ClassExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitExitExp(ExitExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitIfExp(IfExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitLambdaExp(LambdaExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitLetExp(LetExp exp, gnu.expr.ANormalize.Context context) Besides handling "let" and "fluidlet" normalization, it flattens the nesting of let expressions.
protected Expression	visitModuleExp(ModuleExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitQuoteExp(QuoteExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitReferenceExp(ReferenceExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitSetExp(SetExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitSynchronizedExp(SynchronizedExp exp, gnu.expr.ANormalize.Context context)
protected Expression	visitTryExp(TryExp exp, gnu.expr.ANormalize.Context context)

Methods inherited from class gnu.expr.ExpExpVisitor

defaultValue, error, error, update

Methods inherited from class gnu.expr.ExpVisitor

error, getColumnNumber, getCompilation, getCurrentLambda, getEndColumn, getEndLine, getExitValue, getFileName, getLanguage, getLineNumber, getMessages, getPublicId, getStartColumn, getStartLine, getSystemId, isStableSourceLocation, noteError, setColumn, setContext, setFile, setLine, setLine, visit, visit, visitAndUpdate, visitDeclarationType, visitDeclarationTypes, visitDefaultArgs, visitExpression, visitExps, visitExps, visitFluidLetExp, visitLangExp, visitObjectExp, visitScopeExp, visitThisExp

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

ANormalize

public ANormalize()

Method Detail

aNormalize

public static void aNormalize(Expression exp,
                              Compilation comp)

normalizeTerm

protected Expression normalizeTerm(Expression exp)

Starts the normalization of expression exp. It has the effect of monadic conversion plus interpreting it in the Identity monad.

isAtomic

protected static boolean isAtomic(Expression exp)

Determines if an Expression is atomic, that is if it needs to be normalized or not.

normalizeName

protected Expression normalizeName(Expression exp,
                                   gnu.expr.ANormalize.Context context)

Performs the bind operation, introducing a new let expression to capture the result of non-trivial expressions, which is bound to a new let variable.

normalizeNames

protected Expression normalizeNames(Expression[] exps,
                                    int index,
                                    gnu.expr.ANormalize.MultiContext context)

Deals with the normalization of multiple expressions. It is actually used to normalize the arguments of a function application. The array is updated inplace with references to the introduced let-bound variables.

visitQuoteExp

protected Expression visitQuoteExp(QuoteExp exp,
                                   gnu.expr.ANormalize.Context context)

Overrides:

visitQuoteExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitReferenceExp

protected Expression visitReferenceExp(ReferenceExp exp,
                                       gnu.expr.ANormalize.Context context)

Overrides:

visitReferenceExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitApplyExp

protected Expression visitApplyExp(ApplyExp exp,
                                   gnu.expr.ANormalize.Context context)

Overrides:

visitApplyExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitBeginExp

protected Expression visitBeginExp(BeginExp exp,
                                   gnu.expr.ANormalize.Context context)

Overrides:

visitBeginExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitLetExp

protected Expression visitLetExp(LetExp exp,
                                 gnu.expr.ANormalize.Context context)

Besides handling "let" and "fluidlet" normalization, it flattens the nesting of let expressions.

Overrides:

visitLetExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitIfExp

protected Expression visitIfExp(IfExp exp,
                                gnu.expr.ANormalize.Context context)

Overrides:

visitIfExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitCaseExp

protected Expression visitCaseExp(CaseExp exp,
                                  gnu.expr.ANormalize.Context context)

Overrides:

visitCaseExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitLambdaExp

protected Expression visitLambdaExp(LambdaExp exp,
                                    gnu.expr.ANormalize.Context context)

Overrides:

visitLambdaExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitSetExp

protected Expression visitSetExp(SetExp exp,
                                 gnu.expr.ANormalize.Context context)

Overrides:

visitSetExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitModuleExp

protected Expression visitModuleExp(ModuleExp exp,
                                    gnu.expr.ANormalize.Context context)

Overrides:

visitModuleExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitTryExp

protected Expression visitTryExp(TryExp exp,
                                 gnu.expr.ANormalize.Context context)

Overrides:

visitTryExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

toCatchClause

protected CatchClause toCatchClause(LetExp exp,
                                    CatchClause next)

visitSynchronizedExp

protected Expression visitSynchronizedExp(SynchronizedExp exp,
                                          gnu.expr.ANormalize.Context context)

Overrides:

visitSynchronizedExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitBlockExp

protected Expression visitBlockExp(BlockExp exp,
                                   gnu.expr.ANormalize.Context context)

Overrides:

visitBlockExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitExitExp

protected Expression visitExitExp(ExitExp exp,
                                  gnu.expr.ANormalize.Context context)

Overrides:

visitExitExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>

visitClassExp

protected Expression visitClassExp(ClassExp exp,
                                   gnu.expr.ANormalize.Context context)

Overrides:

visitClassExp in class ExpVisitor<Expression,gnu.expr.ANormalize.Context>