Package gnu.expr
Class ANormalize
java.lang.Object
gnu.expr.ExpVisitor<Expression,gnu.expr.ANormalize.Context>
gnu.expr.ExpExpVisitor<gnu.expr.ANormalize.Context>
gnu.expr.ANormalize
- All Implemented Interfaces:
SourceLocator
,SourceLocator
,Locator
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: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.becomes:(+ 1 (if (>= x 0) (f x) 0))
2. The result is interpreted in the Identity monad:(bind (if (>= x 0) (f x) (return 0)) (lambda (t) (+ 1 t)))
(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))
-
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 -
Method Summary
Modifier and TypeMethodDescriptionstatic 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
-
Constructor Details
-
ANormalize
public ANormalize()
-
-
Method Details
-
aNormalize
-
normalizeTerm
Starts the normalization of expression exp. It has the effect of monadic conversion plus interpreting it in the Identity monad. -
isAtomic
Determines if an Expression is atomic, that is if it needs to be normalized or not. -
normalizeName
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
- Overrides:
visitQuoteExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitReferenceExp
- Overrides:
visitReferenceExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitApplyExp
- Overrides:
visitApplyExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitBeginExp
- Overrides:
visitBeginExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitLetExp
Besides handling "let" and "fluidlet" normalization, it flattens the nesting of let expressions.- Overrides:
visitLetExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitIfExp
- Overrides:
visitIfExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitCaseExp
- Overrides:
visitCaseExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitLambdaExp
- Overrides:
visitLambdaExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitSetExp
- Overrides:
visitSetExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitModuleExp
- Overrides:
visitModuleExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitTryExp
- Overrides:
visitTryExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
toCatchClause
-
visitSynchronizedExp
- Overrides:
visitSynchronizedExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitBlockExp
- Overrides:
visitBlockExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitExitExp
- Overrides:
visitExitExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-
visitClassExp
- Overrides:
visitClassExp
in classExpVisitor<Expression,
gnu.expr.ANormalize.Context>
-