A Simplifier

Create another module, src/simplify.c (and src/simplify.h) that contains a function that simplifies a tree. It should perform transformations on a tree with the idea of reducing it to a form that does not require further simplification.

The simplifier should not change the tree. It should return the simplified tree. So its heading is

  AST simplify(AST t)

The rules for simplifying trees should be fairly obvious. (Okay, they look obvious to me.) Mainly use call-by-value. That is, evaluate the parameter of a function before you pass it to the function. Here are some hints.

1. An identifier node always stands for something that was defined using def. To simplify identifierNode(x), look up x in the symbol table and return the tree that is stored there for x.

2. To simplify a constant node, such as an integer constant, just return it unchanged.

3. To simplify expression A:B,

   1. Simplify A (call the result a)
   2. Simplify B (call the result b)
   3. Return a new CONS node for a:b

   Treat a CONS node like a constant; just return it unchanged.

4. To simplify an operator node opNode(op, A, B), first simplify A, then simplify B, then perform operator op on the results.

5. To simplify a standard function node funNode(fun, A), first simplify A, then apply function fun to the result.

6. To simplify a conditional node ifNode(A, B, C):

   1. Simplify A.

   2. If A simplifies to constant true, then return the result of simplifying B.

   3. If A simplifies to constant false, then return the result of simplifying C.

   4. If simplifying A yields any other kind of result, it is an error.

7. To simplify applyNode(A, B):

   1. Simplify A.

   2. If the simpified value of A is not a FUNCTION node, it is an error.

   3. Simplify B.

   4. Suppose that A has simplified to A', which has the form functionNode(E). Let's call a PARAMETER node in tree E that points back to the root of A' an active PARAMETER node.

      1. Set the mark of each node in E to 0.

      2. Scan E again, setting the mark to 1 in each node that contains an active PARAMETER node in any of its subtrees.

      3. Build a copy E' of E in which each active PARAMETER node has been replaced by the simplified value of B. Note that any subtree whose root has a mark of 0 does not need to be copied.

         See below for a discussion on copying.

      You can change marks in-place, since they are only used temporarily. But do not try to replace PARAMETER nodes in-place. It is crucial that you not modify the structure of E.

   5. Simplify E', and return that simplified result.

8. To simplify functionNode(E), just return it as is. Do not make any changes. Do not try to simplify the body, E.

9. To simplify a readChar or readInt node, just return the node unchanged.

10. To simplify print(A) or printList(A) or produce(A) node, return it as is. Do not simplify A.

11. To simplify A ~> B, return it as is. Do not simplify A or B.

Copying trees

You will need to copy a tree when you simplify a function application. Mainly, the issue here is that you need to change the pointers in PARAMETER nodes to point to the function node in the copy.

To copy a tree, pass an extra parameter that is a table holding (old identity, new identity) pairs for all FUNCTION nodes that the copy is inside.

If the copy function sees a PARAMETER node that refers to an old identity in the table, then the copy is a PARAMETER node that refers to the corresponding new identity.

To copy a FUNCTION node with identity I, make a new FUNCTION node with a new identity J and add pair (I, J) to the table, and copy the body of the function with this new table. Then install the copy of the function body into the new FUNCTION node.

You can represent the table any way that you like. Think about it.

Testing the simplifier

Create a tester to test the simplifier. You will want to build some trees directly using constructors and simplify them. Try storing some trees into the symbol table too, and test simplifying trees that use names from the symbol table.