Assignment #3
Orignally Due Thursday, 20 October, 11:59 p.m. (10 point bonus)
Revised Due Date Saturday, 22 October, 11:59 p.m.

General Instructions

All homework and programming exercises must be prepared in accordance with the instructions given in the Syllabus. Each assignment must be submitted to Blackboard by its stated deadline.

AST Simplification

The goal of this assignment is to restructure the abstract syntax tree for an expression in the Imperative Core Language so that the resulting tree can be evaluated more efficiently (or can be used to generate more efficient code).

A simplified abstract syntax tree must be the same semantically as the input expression, but it may have a different structure. To be equivalent semantically, the evaluation of the tree must yield the same result and have the same sequence of side effects.

The := (Set constructor) and write (Write constructor) expressions have side-effects as well as values. They cannot be removed, but their subexpressions can be simplified.

The Imperative Core Language interpreter encodes the abstract syntax trees for expressions as Lua tables. These tables are created by the constructor functions in the Abstract Syntax module.

For example, consider the input expression in the prefix syntax:

    (if  1  (+ (* x 1) (+ (* 3 0) (- y 0)))  (neg (neg z)))

The abstract syntax tree corresponding to the above expression is defined by the following nested construtor calls from the Abstract Syntax module:

    If( Int(1),
        Add( Mul( Var("x"), Int(1) ),
             Add( Mul(Int(3), Int(0)),
                  Sub(Var("y"), Int(0)))),
        Neg(Neg(Var("z"))) )

This results in the following nested Lua table structure:

    {"If", {"Int", 1},
         {"Add", {"Mul", {"Var", "x"}, {"Int", 1}}, 
               {"Add", {"Mul", {"Int", 3}, {"Int", 0}},
                     {"Sub", {"Var", "y"}, {"Int", 0}}}},
         {"Neg", {"Neg", {"Var", "z"}}}}

Of course, programs can use query functions such as isInt, isVar, isIf, and isAdd to test for the various kinds of nodes in the abstract syntax tree.

We can draw the tree pictorially something like the following:

Abstract Syntax Tree

Abstract Syntax Tree

But this tree has many unnecessary nodes. For example, {"Mul", {"Int", 3}, {"Int", 0}} can be simplified to just {"Int", 0} and {"Sub", {"Var", "y"}, {"Int", 0}} simplified to just {"Var", "y"}. The node above those can be simplified from {"Add", {"Int", 0}, {"Var", "y"}} to just {"Var", y}. And so forth up the tree.

For arbitrary expressions e, we can simplify ImpCore expressions by applying mathematical identities (stated in our usual infix notation) such as

    0 + e = e + 0 = e
    1 * e = e * 1 = e
    0 * e = e * 0 = 0 
    e - 0 = e
    0 - e = -e
    e/1 = e
    0/e = 0
    --e = e

Similarly, for constants j and k, we can also go ahead and carry out the operations such as j + k, j - k, j * k, j / k, j == k, j < k, etc. and replace the operation and operands by the constant value.

We can also simplify if with constant conditions. The expression if 1 e1 e2 is the same as e1 and if 0 e1 e2 is the same as e2.

Thus the above expression can be simplified to:

    {"Add", {"Var", "x"}, {"Var", "y"}}

For while, we can check whether the condition for is always false and we can otherwise simplify the body. For block, we can remove any expressions in the sequence that do not have side effects, except for the last expression.

Note: There are likely other simplifications that can be done, for example, using the commutativity and associativity of arithmetic operations to reorder expressions to allow other simplifications.

Tasks

  1. Add a new public function simplify to the Abstract Syntax module of the ImpCore interpreter. This function takes an ImpCore expression and returns a possibly simpler ImpCore expression that returns the same value and has the same side effects. Of course, if no simplification are possible, it should return the input expression.

    You may work from the base ImpCore interpreter on the course website; it is not neccessary to simplify the extensions you did for Assignment #2. You will need to modify the Abstract Syntax module and use the Utilities and Values modules. The project does not require use of the other module, nor of any Lua module not in the standard libraries.

  2. The simplifications supported should include those needed for the example above -- using addition and multiplication identities, multiplication by 0, subtraction of 0 or from 0, double negation, arithmetic on constants, if with a constant condition, and simplification of while, block, write, and := appropriately.

  3. To aid in your testing you may use the test script

    simplify_test.lua

    as a beginning point for your testing.

  4. If you add any other simplifications, please document those and include aprpopriate tests in your test script.

  5. Turn in your modified and other needed ImpCore modules and your test script to Blackboard by the due date.