From 24f3ce54983348e1aa0229d5c08b3fe99d739d40 Mon Sep 17 00:00:00 2001 From: bculkin2442 Date: Mon, 18 Apr 2016 13:04:01 -0400 Subject: Added operation condensing --- .../java/bjc/dicelang/DiceExpressionParser.java | 2 +- .../java/bjc/dicelang/ast/DiceASTEvaluator.java | 34 ++++++- .../java/bjc/dicelang/ast/DiceASTOptimizer.java | 20 ++-- .../dicelang/ast/DiceASTReferenceSanitizer.java | 2 + .../bjc/dicelang/ast/nodes/OperatorDiceNode.java | 26 +++-- .../ast/optimization/ConstantCollapser.java | 1 + .../ast/optimization/OperationCondenser.java | 105 +++++++++++++++++++++ 7 files changed, 168 insertions(+), 22 deletions(-) create mode 100644 dice-lang/src/main/java/bjc/dicelang/ast/optimization/OperationCondenser.java (limited to 'dice-lang/src/main/java') diff --git a/dice-lang/src/main/java/bjc/dicelang/DiceExpressionParser.java b/dice-lang/src/main/java/bjc/dicelang/DiceExpressionParser.java index 76ccdd4..d0e013a 100644 --- a/dice-lang/src/main/java/bjc/dicelang/DiceExpressionParser.java +++ b/dice-lang/src/main/java/bjc/dicelang/DiceExpressionParser.java @@ -36,7 +36,7 @@ public class DiceExpressionParser { /* * Create a shunter to rewrite the expression */ - ShuntingYard yard = new ShuntingYard<>(); + ShuntingYard yard = new ShuntingYard<>(true); /* * Add our custom operators to the yard diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java index 411212e..aeecb38 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTEvaluator.java @@ -67,9 +67,38 @@ public class DiceASTEvaluator { operatorCollapsers.put(OperatorDiceNode.GROUP, DiceASTEvaluator::parseGroup); + operatorCollapsers.put(OperatorDiceNode.LET, (nodes) -> { + return parseLet(enviroment, nodes); + }); + return operatorCollapsers; } + private static IPair> parseLet( + IFunctionalMap> enviroment, + IFunctionalList>> nodes) { + if (nodes.getSize() != 2) { + throw new UnsupportedOperationException( + "Can only use let with two expressions."); + } + + ITree bindTree = nodes.getByIndex(0).getRight(); + ITree expressionTree = + nodes.getByIndex(1).getRight(); + + IFunctionalMap> letEnviroment = + enviroment.extend(); + + evaluateAST(bindTree, letEnviroment); + int exprResult = evaluateAST(expressionTree, letEnviroment); + + IFunctionalList> childrn = + nodes.map((pair) -> pair.getRight()); + + return new Pair<>(exprResult, + new Tree<>(OperatorDiceNode.LET, childrn)); + } + /** * Evaluate the provided AST to a numeric value * @@ -121,8 +150,9 @@ public class DiceASTEvaluator { return result; } - // Value to allow for assignments - return 0; + throw new UnsupportedOperationException( + "Attempted to dereference unbound variable " + + variableName); } private static int evaluateLiteral(IDiceASTNode leafNode) { diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java index 00ac871..7676fac 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTOptimizer.java @@ -44,14 +44,16 @@ public class DiceASTOptimizer { */ public ITree optimizeTree(ITree ast, IFunctionalMap> enviroment) { - return passes.reduceAux(ast, (currentPass, currentTree) -> { - return currentTree.collapse(currentPass::optimizeLeaf, - (operator) -> { - return (nodes) -> { - return currentPass.optimizeOperator(operator, - nodes); - }; - }, (tree) -> tree); - }, (tree) -> tree); + ITree optimizedTree = + passes.reduceAux(ast, (currentPass, currentTree) -> { + return currentTree.collapse(currentPass::optimizeLeaf, + (operator) -> { + return (nodes) -> { + return currentPass.optimizeOperator( + operator, nodes); + }; + }, (tree) -> tree); + }, (tree) -> tree); + return optimizedTree; } } diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java index 08f84e3..05fddf6 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/DiceASTReferenceSanitizer.java @@ -41,6 +41,8 @@ public class DiceASTReferenceSanitizer { switch (((OperatorDiceNode) node)) { case ASSIGN: return TopDownTransformResult.TRANSFORM; + case LET: + return TopDownTransformResult.PASSTHROUGH; case ADD: case COMPOUND: case DIVIDE: diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java index ab47b56..c0f7bd3 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/nodes/OperatorDiceNode.java @@ -14,29 +14,33 @@ public enum OperatorDiceNode implements IDiceASTNode { */ ADD(MATH), /** - * Represents assigning one node to another + * Represents dividing two nodes */ - ASSIGN(EXPRESSION), + DIVIDE(MATH), /** - * Representings combining two node values together + * Represents multiplying two nodes */ - COMPOUND(DICE), + MULTIPLY(MATH), /** - * Represents dividing two nodes + * Represents subtracting two nodes */ - DIVIDE(MATH), + SUBTRACT(MATH), + /** + * Representings combining two node values together + */ + COMPOUND(DICE), /** * Represents using one node a variable number of times */ GROUP(DICE), /** - * Represents multiplying two nodes + * Represents assigning one node to another */ - MULTIPLY(MATH), + ASSIGN(EXPRESSION), /** - * Represents subtracting two nodes + * Represents evaluating one expression in the context of another */ - SUBTRACT(MATH); + LET(EXPRESSION); /** * Represents the group of operator this operator is sorted into. @@ -73,6 +77,8 @@ public enum OperatorDiceNode implements IDiceASTNode { case "c": case "compound": return COMPOUND; + case "=>": + return LET; default: throw new IllegalArgumentException( s + " is not a valid operator node"); diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java index 5062170..e476d74 100644 --- a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/ConstantCollapser.java @@ -78,6 +78,7 @@ public class ConstantCollapser implements IOptimizationPass { return new Tree<>(operator, children); case ASSIGN: + case LET: default: // We don't optimize these operators return new Tree<>(operator, children); diff --git a/dice-lang/src/main/java/bjc/dicelang/ast/optimization/OperationCondenser.java b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/OperationCondenser.java new file mode 100644 index 0000000..f41a3ef --- /dev/null +++ b/dice-lang/src/main/java/bjc/dicelang/ast/optimization/OperationCondenser.java @@ -0,0 +1,105 @@ +package bjc.dicelang.ast.optimization; + +import bjc.dicelang.ast.nodes.DiceASTType; +import bjc.dicelang.ast.nodes.IDiceASTNode; +import bjc.dicelang.ast.nodes.OperatorDiceNode; +import bjc.utils.data.IHolder; +import bjc.utils.data.Identity; +import bjc.utils.funcdata.ITree; +import bjc.utils.funcdata.TopDownTransformResult; +import bjc.utils.funcdata.Tree; + +/** + * Condenses chained operations into a single level + * + * @author ben + * + */ +public class OperationCondenser { + /** + * Condense chained similiar operations into a single level + * + * @param ast + * The AST to condense + * @return The condensed AST + */ + public static ITree condense(ITree ast) { + return ast.topDownTransform(OperationCondenser::pickNode, + OperationCondenser::doCondense); + } + + private static TopDownTransformResult pickNode(IDiceASTNode node) { + switch (node.getType()) { + case LITERAL: + return TopDownTransformResult.SKIP; + case OPERATOR: + return pickOperator((OperatorDiceNode) node); + case VARIABLE: + return TopDownTransformResult.SKIP; + default: + throw new UnsupportedOperationException( + "Attempted to traverse unknown node type " + node); + } + } + + private static TopDownTransformResult + pickOperator(OperatorDiceNode node) { + switch (node) { + case ADD: + case MULTIPLY: + case SUBTRACT: + case DIVIDE: + case COMPOUND: + return TopDownTransformResult.PUSHDOWN; + case ASSIGN: + case GROUP: + case LET: + return TopDownTransformResult.PASSTHROUGH; + default: + throw new UnsupportedOperationException( + "Attempted to traverse unknown operator " + node); + } + } + + private static ITree + doCondense(ITree ast) { + OperatorDiceNode operation = + ast.transformHead((node) -> (OperatorDiceNode) node); + + IHolder canCondense = new Identity<>(true); + + ast.doForChildren((child) -> { + if (canCondense.getValue()) { + canCondense.replace(child.transformHead((node) -> { + if (node.getType() == DiceASTType.OPERATOR) { + if (operation.equals(node)) { + return true; + } + + return false; + } + + return true; + })); + } + }); + + if (!canCondense.getValue()) { + return ast; + } + + ITree condensedAST = new Tree<>(operation); + + ast.doForChildren((child) -> { + if (child.getHead().getType() == DiceASTType.OPERATOR) { + child.doForChildren((subChild) -> { + condensedAST.addChild(subChild); + }); + } else { + condensedAST.addChild(child); + } + }); + + return condensedAST; + } +} -- cgit v1.2.3