5 Homework 6🔗

This assignment is due Thursday, 2/13 by MIDNIGHT

What to Download:

hw6.rkt

Please start with this file, filling in where appropriate, and submit your homework to the HW6 assignment on Gradescope. This page has additional information, and allows us to format things nicely.

5.1 Superoptimization🔗

Superoptimization is the idea of replacing a given loop-free sequence of instructions with an equivalent sequence of instructions that is somehow better (usually, shorter and as a result, faster). It’s used in compilers at the very lowest level, to optimize numeric operations into often counter-intuitive sequences of instructions that can be baffling at first. It was invented by computer scientist Alexia Massalin in 1987: her idea was to find the shortest sequence of instructions, given a particular instruction set, to compute a given function. This is in contrast to most compiler optimization, which merely aim to improve performance, rather than finding truly optimal solutions.

The resulting programs often rely somewhat complex interactions between different instructions, and sometimes "startling" programs that rely on strange overlap between representations of different values: often times, code with branches is replaced with equivalent code that doesn’t use branches, for example.

5.2 Problem 1🔗

While superoptimization is an interesting problem, in this homework, we will tackle a simpler one: checking ordinary optimizations. In particular, showing that a program before and after an optimization are equivalent.

Our optimizations will use a simple, stack-based language: each instruction operates on the stack of numbers, either pushing a new number or adding/multiplying/subtracting the top two (and pushing the result). For example, the program:

(list (make-push 10)

(make-push 20)

(make-push 2)

(make-mul)

(make-add))

Would start with an empty stack, after the first instruction, would have 10 on top of the stack, and nothing beneath. After the second instruction, 20 would be on top. After the third, 2 would be on top, 20 beneath, 10 at the bottom. Now to run "mul", it would pop the top two numbers (20 & 2), multiply them (yielding 40), and push that back on top of the stack (so it would be 40 above 10). Then the last instruction would do a similar thing with addition, yielding 50 as the final value on the stack, with no instructions left to run.

We provide you with both the language definition and a function to run programs, simple-eval:

Your task is to first implement a function that verifies that two programs written in this language are equivalent, where equivalent means runs to the same thing (This will be relevant and useful once you reach the 3rd problem of this assignment):

5.3 Problem 2🔗

The next problem is to implement a simple optimization. In this case, we want you to implement a simple form of constant folding. Constant folding is the idea of replacing a series of operations that are all on constants with the result of running those operations at optimization time. By doing it at optimization time, it won’t have to be done when the program is actually running.

In this case, we want your optimization to replace the sequence (make-push n) (make-push m) (make-add) with (make-push o) where o is m plus n. You do not need to (and should not) replace sequences that only appear after the initial constant folding has been done. i.e., the sequence (make-push l) (make-push n) (make-push m) (make-add) (make-add) should turn into (make-push l) (make-push o) (make-add), where o is the result of adding n and m, but should not be further optimized into a single (make-push p), where p is the result of adding l and o. Similarly, the sequence (make-push l) (make-push n) (make-add) (make-push m) (make-add) should be optimized to (make-push o) (make-push m) (make-add) where o is the result of adding l and n, but should not be further optimized into a single (make-push p) where p is the result of adding o and m.

5.4 Problem 3🔗

To check that your constant folding works, define a property that shows that given a list of instructions, running the constant folding operation results in a program that is equivalent to the original program.

5.5 Problem 4🔗

In this problem, we’ll extend the stack calculator to include variables, which represent input from the user (as they will be substituted when running the program) so that there are real limits to what even the best constant folding could do (constant folding happens before running the program, so variables represent unknowns at that time). We represent variable names with strings, to make things easier, and now eval takes a set of variable bindings that give values for each variable.

Your first task is to make an updated version of your verify function, to check that two programs are equivalent. Now, you take in a set of variable bindings that both programs will use.

Your next task is to define a more general version of constant folding. This time, look for any sequence of (make-push n) (make-push m) (make-op) where op is one of add, sub, or mul. You still shouldn’t replace sequences that only appear after the initial constant folding has been done.

So you can do similar validation of your constant folding:

5.6 Problem 5🔗

Give a polymorphic signature (using All) to the following function tree-map, which is the list abstraction map abstracted to work over trees that have values (of arbitrary type) at their leaves.

5.7 Problem 6🔗

The identity function has signature (All (X) (-> X X)), a signature that actually ensures that the function has to behave as the identity. The reason is, since the function must return an X, the only thing it can do is return its argument, unchanged, as there are no other places it could find an X.

In this problem, we want you to write the four possible functions that have signature (All (X) (-> Boolean X X X)). i.e., the function takes a Boolean and two values of type X, and returns one of them. Like the signature of the identity function above ensures that there is only one function (there might be many ways of writing the function in code, but they will all behave the same), this signature ensures that there are only four possible functions. We want you to write them all as p6a, p6b, p6c, and p6d. It’s not important which is which, they just all have to behave differently.

NOTE: Do not use random in this assignment, including via contract-generate (or mutable state, if you’ve found that).