Note that you have longer to do this problem set than you did on previous problem sets. This is not an accident; this problem set is significantly more work. So get started early!
You may do this problem set alone or in pairs. You will submit the files you changed through CMS.
The problem set has 7 parts, all of them concerning optimizing ML programs. The earlier problems are intended to be relatively simple; this is not true of the last problems.
Note that this problem set does not rely upon the Mini-ML interpreter that you used in PS#3. However, it will use the parser and the AST data-structure from that problem set.
In this problem set you will write a program that takes an ML program and returns a new ML program. The new ML program will have exactly the same behavior as the old program; only it will be faster and (probably) use less memory.
Note that this is not the same as the evaluator (PS#3), which took an ML expression and gave its value. Instead, we will return a new expression which computes the same thing, only faster. So for example suppose that we start off with:
val try = let val double = fn(x) => x+x in fn(x) => double(x) + double(x) end
We might end up with the new program:
val try = fn(x) => 4*x
This clearly is the same program in all respects save efficiency. Such an optimization is sometimes called a source to source transformation, and is a subset of what a compiler does.
In order to simplify your life, we will limit the programs we will consider to a small subset of ML, which is the same subset we dealt with in PS#3. To refresh your memory, there is no pattern matching or use of recursive functions. The following is a representative list of what is still in the language:
+ - * mod div = > < >= <= :: @ andalso orelse~ not234 true () foo if/then/else let/in/endfn (x) => xhd tl null
Also, the input to be optimized will be a single expression (i.e. it does not support val statements at top level). We will assume that all the programs we deal with are properly typed. This set of assumptions will make our lives much simpler!
The goal of this problem set is to turn one ML program into another one. In order to do this we need an internal representation for ML programs. We will use Abstract Syntax Trees (AST’s), just as we did in PS#3. Just as with before, we will provide you with the definition of an AST (see: abstractSyntax.sml) and a function Parser.parseString, which takes a string and returns the corresponding AST.
You have been provided (in prettyprinter.sml) with a pretty-printer. Given an AST, this prints out the corresponding program in a somewhat human-readable fashion (this function is the inverse of parse). Note that if the input AST includes unsupported features (such as fun declarations) this will not work. For debugging purposes we have provided you with function that prints out an AST, contained in printAST.sml.
Throughout this problem set, you will be creating optimizations that take an AST as input and produce a modified AST as output. In order to make this easier to read, you will use a main loop, somewhat like you used in PS#2 and PS#3. This loop will read a line of text and call parse on the output. It will then call Transformations.optimize to produce a better AST, which is then returned and printed out via the pretty printer.
Currently, there is one optimization implemented, Transformations.optimize0, which replaces e+e with 2*e for any expression e. This illustrates the structure of the code you will write. Notice that the code for optimize0 only handles a limited set of expressions; this is OK, because we are willing to restrict the input language to make this problem set (somewhat) tractable. You should study this code carefully, since your solutions should look fairly similar to it.
The Read-Optimize-Print Loop is contained in optimizer.sml, and is invoked by Optimizer.run(). The optimizer has various levels, which you will be required to implement. At any point in time, the optimizer is running at a certain level. You can change the level to n with the :o command (if you give it no arguments, it will display the current optimization level).
Here is an example of the Read-Optimize-Print Loop in operation, doing the single optimization we provided you:
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :p let val ford = f(x) + f(x) in ford+30 endLet_e(Val_d(ford,Binop_e(Apply_e(Id_e(f),Id_e(x)),Plus,Apply_e(Id_e(f),Id_e(x)))),Binop_e(Id_e(ford),Plus,Int_c(30))) Optimize >> f(x)+f(x);Optimized at level 0 to:(2*f(x)) Optimize >> let val ford = f(x) + f(x) in ford+30 endOptimized at level 0 to: let val ford = (2*f(x)) in (ford+30) end Optimize >> (let val x = y+y in ford(x) end)+ (let val x = y+y in ford(x) end)Optimized at level 0 to:2 * let val x = 2 * y in ford x end
Note that the optimization is done recursively, as can be seen from the last example.
Your task is to add 7 different optimizations. The basic code is included in transformations.sml, although the optimizations are (of course) not yet provided. This is the only file you should modify!
Each optimization you add is designed to be independent (although, of course, running them all can result in even better code). For each optimization, we will provide you with an English description of its effect, as well as some examples. We will not in general assume that any previous optimizations have been done; your code should work correctly on code that has not been otherwise optimized.
In an AST, we want to shift
constants to the right. More
precisely, a binary operator expression whose operator is commutative, and
whose left hand argument is a constant and whose right hand argument is not, should
have its arguments swapped. The following examples show how your code should
behave.
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 1Optimization level = 1Optimize >> 10 + aOptimized at level 1 to:a + 10 Optimize >> 9 * c + bOptimized at level 1 to:c * 9 + b
What to hand in: your version of Transformations.optimize1
Many arithmetic expressions can be computed during compile time. Consider:
let val x = 2 * 5 in f(x) end
The expression that x is bound to is represented by Binop_e(Int_c(2),Times,Int_c(5)). Since this is an arithmetic computation where we know the values during compile time, we can compute the value straight away and then bind x to it. Therefore we can replace it by the expression Int_c(10)
Of course we cannot always compute the value of an expression during compile time as shown above. If y = (a + (4 * 10)), we do not know what the value of a is during compile time. However, we can still simplify the arithmetic computation in y to get y = (a + 40). This kind of an optimization which is done in the early stages of compilation by folding constants is known as constant folding. This is a spatial (i.e. space saving) optimization; to see this, consider:
let val x = 2 * 5….in …. end
If the above expression is called a million times then each time, when we call evaluate on x, we have to compute 2 * 5 and then bind it to x and this optimization performs this computation fairly early on during compilation and this saves us space (in terms of ASTs) as well as time.
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 2Optimization level = 2Optimize >> let val x = 2*5 in f(x) endOptimized at level 2 to:let val x = 10 in f x end Optimize >> let val x = 2*5+32 in f(x) endOptimized at level 2 to:let val x = 42 in f x end
Note: In order to make this last example work correctly,
you will need to walk the AST in the appropriate order.
What to hand in: your version of Transformations.optimize2
This optimization is a
general form a constant folding wherein we make use of simple arithmetic and
boolean rules to simplify expressions. Implement the following rules:
x * 1 è x y orelse true è true
x div 1 è x y orelse false è y
x + 0 è x y andalso false è false
x * 0 è 0 y andalso true è y
x - 0 è x
x - x è 0
Note that in this problem
you are only required to do the optimizations that can be immediately done on
the input code. This is in contrast to optimization 4.
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 3Optimization level = 3Optimize >> let val x = y+0 in f(x, z andalso false) endOptimized at level 3 to:let val x = y in f (x, false) end Optimize >> let val x = y+0 in f(x, z andalso (w andalso false)) endOptimized at level 3 to:let val x = y in f (x, z andalso false) end Optimize >> let val x = y*0 in f(x) endOptimized at level 3 to:let val x = 0 in f x end Optimize >> let val x = y*(z*0) in f(x) endOptimized at level 3 to:let val x = y * 0 in f x end
What to hand in: your version of Transformations.optimize3
In this optimization, we
apply the previously defined optimization repeatedly to an expression. For
example:
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 4Optimization level = 4Optimize >> let val x = y+0 in f(x, z andalso false) endOptimized at level 4 to:let val x = y in f (x, false) end Optimize >> let val x = y+0 in f(x, z andalso (w andalso false)) endOptimized at level 4 to:let val x = y in f (x, false) end Optimize >> let val M = (x div 1 + (y - x * 0)) + (y * 1 + x * 0) * ((x div (1 + 0)) - x) in f(M) endOptimized at level 4 to:let val M = x + y in f M end
Note: Your
solution to this problem must call Transformations.optimize3.
What to hand in: your version of Transformations.optimize4
If the value of a variable
is known to be a constant, then an expression containing the variable can
replaced by the constant. Consider:
let val x = (20 + 45 * 100 div 5) val y = x + 42 val z = x * yin f(z)end
When evaluating the
expression x + 42, we know from earlier that x evaluates to a constant value
i.e. 920 and therefore we can replace x by 920. So the code above is equivalent
to:
let val x = 920 val y = 962 val z = x * yin f(z)
end
We are essentially
‘propagating’ the value of the constant in other expression. This propagation leads
us to an even faster (yet equivalent) piece of code, namely:
let val x = 920 val y = 962 val z = 885040in f(z)end
This optimization saves us
space as well as a speeding up on execution time.
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 5Optimization level = 5Optimize >> let val x = (20 + 45 * 100 div 5) val y = x + 42 val z = x * y in f(z) endOptimized at level 5 to: let val x = 920 val y = 962 val z = 885040 in f 885040 end
Note: We’ve
only provided you with a sample of where this optimization can be performed. Be
sure to apply it everywhere you can.
What to hand in: your version of Transformations.optimize5
Note: two minor typographical errors in this problem were fixed on 10/25.
The overhead associated with
calling and returning from a function can be eliminated by expanding the body
of the function inline. Since our subset of ML does not include fun there
is no way to do recursion, so this is not a problem.
For example, consider this
code:
let val add = fn(x,y) => x + y val addTwice = fn(a,b) => add(add(a,b),add(a,b))in addTwice(m,n)end
By inlining the value of add
we get:
let
val add = fn(x,y) => x + y (* Note that this is not deleted! *) val addTwice = fn(a,b) => (a+b)+(a+b)in addTwice(m,n)end
Your code should perform this optimization for any function that the input expression defines.
What to hand in: your version of Transformations.optimize6
Alpha-renaming is powerful
mostly to enable other optimizations, though it is powerful in its own right.
Alpha-renaming ensures that all bound variables have distinct names; as a
consequence, after alpha-renaming two variables with the same name are in fact
the same variable.
- Optimizer.run();--- CS312 Optimizer ---Optimize >> :o 7Optimization level = 7Optimize >> let val x = y val x = x+1 in f(x) endOptimized at level 7 to: let val _v0 = y val _v1 = _v0+1 in f _v1 end
The variable names that are
introduced by alpha-renaming must always start with the prefix “_v” (no
quotes), followed by an ordinal number. The parser that we are using does not
accept the underscore character as the first character of a variable name, so
this method guarantees that the newly introduced variables are not in conflict
with any pre-existing variables.
What to hand in: your version of Transformations.optimize7