CS 536 (F02) Homework 5: Compiling Programs via CPS

Assignment Goals

• To manually compile a small program using CPS, register transformations, and vectors.

Exercise: Performing Compilation

Using the techniques presented in class (and in the posted notes), manually compile this program over family trees. Turn in at least three separate, self-contained files:

1. One containing the CPSed version of the program.
2. One containing the program after you've introduced stack records.
3. The final compiled version of the program (for full credit, your final version should include a heap and should manipulate family trees on the heap rather than as structures. As in the filter-pos example in the notes, leave the stack records in Scheme's define-datatype).

If you don't get the final version working, you may also turn in the last working version you had. Please don't turn in every version you wrote -- I do need to read all of these!

NOTE: I expect that you have actually run and tested the programs you submit for this assignment. I won't grade files that you clearly have not run and tested (for example, a program with syntax errors clearly hasn't been run). Obviously, if you dind't get the final compiler fully working, turn in what you have, but what you have should at least run in Scheme, even if it doesn't produce the correct answer. (I'm surprised to be saying this in a grad class, but it's clear that some of you don't run your programs before turning in homework, which rather defeats the point of having you implement concepts as a way of experimenting with and understanding them.)

Some hints and guidelines:

1. This assignment looks deceptively short. It could still take you a few hours.
2. You may define as many registers as you need.
3. Keep the structure of the original program. Do not modify the source program before starting (i.e., don't inline the helper function, rewrite the body of have-eye-color, etc).
4. When you CPS, be sure to CPS both have-eye-color and eye-match?.
5. Your final program can store booleans, symbols, and numbers (data or addresses) in the heap.
6. If you get to the heap version, make sure your file includes a simple function to run that initializes the heap with a non-trivial example (as we did with filter-pos in class).
7. Go step by step as we did in the notes; make sure each version is working before you start the next transformation. Save a copy of your last working version(s) at all times. It's easy to make small mistakes in this process that would take you hours to find (which is why we all rely on compilers in the first place!). Don't try to write the final program right off the bat.

Exericses: More Advanced Options

1. The given family tree program fixes the function with which we will filter the tree. Compile a version that takes in a tree, a predicate on people, and a function on people and returns a list. The list contains the result of running the function (3rd arg) on each person who satisfied the predicate (2nd arg). This version lets you experiment with compiling functions as arguments.

2. (This one would take you a while) For a more substantial challenge, implement the compiler (or at least the first couple of stages). Pick one of our languages (with at least basic arithmetic, vars and let statements) and write a program that compiles programs in that language. You'll need to define a datatype for the language you are compiling into.