Assignment 11
Functional Languages
Due April 20th, 9:30 a.m.
(Must be done with your group)

Goals of the assignment

The goals of this project are to give you experience programming in a functional language (SML).  More specifically, you will get experience with the following language features:

Introduction

The goal of compiler optimizations is to improve the performance of the code without changing the meaning of the code.  In this project we we consider a simple optimization, arithmetic simplification of expressions made up of constants, variables, addition, subtraction, and negation.  Here are some examples of expressions:

x + 7 + y
a + -7 - 3
a + b - -c

The expressions are represented as a tree, each internal node of which is a operator (addition, subtraction, or negation) and each leaf is either a constant or a string (which represents a variable with that name).   Here is the representation that I provide:

datatype node = Constant of int
                | Symbol of string
                | Negate of node
                | Add of node*node
                | Subtract of node*node;

Your goal is to transform the tree so that it contains fewer calculations.  In the next four sections I'll give you some examples and describe the two components of the project: transformations and simplifications.

 

Examples

  1. Consider "a  + (5 + 3)":
    A simple analysis can find that the inner add operates on two constants and can thus be simplified to yield: " a + 8"
  2. Consider   "(a + -5) + 3":
    To simplify this, we first use antiassociate to get: "a + (-5 + 3)"
    We can now simplify this easily to get: "a + -2"

Transformations

  • There are a small number of transformations that we routinely use in order to get the expression tree in a form that we can simplify it using the simplifications.  Here they are:

    Simplifications

    Here are some useful simplifications:
  • There are many other simplifications that we can imagine.  For this assignment, we will stick with the ones above.

    What you need to do

    Put the file setup.sml in your directory.  setup.sml contains the datatype declaration which I've already given above and a tostring function that takes a tree and returns a string that contains a flattened infix representation of the tree.  The file test.sml contains test cases that you can use to test your code.

    You need to write one routine for each transformation and simplification described above.  Each of the routine takes a node in the tree and returns a node that is the result of performing the transformation or simplification.  If the transformation or simplification does not apply to the node, then it returns the node itself. 

    For example, simplifyAddZero(Add(Subtract(x,1), 0) should return Subtract(x,1).  Note that these routines only transform the current node: they do not look at opportunities for the transformation in the children of the node.  For example, simplifyAddZero(Add(Add(x,0), 0)) returns Add(x,0), and not x (we would have to apply simplifyAddZero again to get "x").

    You also need to write a routine maptree that takes two arguments, a node, n, and a function, f, of type node->node.  It applies the function f to each node in the tree rooted at n in a bottom-up fashion and builds a new tree in the process using the value returned by f.  For example consider the following tree:
    Add(Constant(10), Symbol("x"))
    maptree will perform the following steps:
    val t = f(Constant(10));
    val u = f(Symbol("x"));
    val k = f(Add(t, u))

    Note how maptree applies its argument function in a bottom-up fashion (i.e., children before parent).
     

    You should put all your routines in program.sml and submit it electronically using our usual submission mechanism.  My solution for this is less than 40 lines of code (including blank lines and formatting). 

    Grading

    You will be graded on this assignment based solely on how well your solution works.  The file test.sml contains 4 tests and their outputs.  If you get all of these right, then you will get 80% of the points.  In addition, we will have a fifth test which we will not reveal to you.  If your program produces the correct answer for that, you will get 20% (in other words, to get 100% your program needs to produce the correct answer for all five tests).  There will be no partial credit on the individual tests.  So for example, if your code does not produce the right answer on any of the tests, you will get 0%.

    Using the system

    If you are using the CSEL machines,  add the following directory to your path:
    /tools/cs/smlnj/bin
    The above path works at least on the Linux machines in the CSEL lab.

    To invoke the compiler type "sml".  This will give you an interpreter prompt in which you can type in SML code.  If you now do:

    use "test.sml";

    It will run all your tests (test.sml includes "setup.sml" and "program.sml" so you do not need to do a "use setup.sml" or "use program.sml").  While writing the code, you may want to use a stripped down version of test.sml.

    If you prefer to install SML on your own machine, it is easy to do.  Download it from http://www.smlnj.org/software.html