CS 441 Assignment 6: Registerization and Garbage Collection

This assignment is a larger assignment, so it is due Thursday April 11 (in 2 weeks) at 10:30am by electronic submission. Don't leave it till the last minute! Also, being a larger assignment, it will count double.

Read EOPL Chapter 10 for background, and the lecture notes.

Part 1: Registerization

Working from your CPS interpreter from assignment 5 (or the model solution), perform a first-order transformation to make closures (the procedures constructed by lambdas), environments, and continuations be records. Use an apply-k function to avoid duplicating the code that applies the various kinds of continuations. Consider dealing with let and let* by expanding them into lambdas and applications. The environment functions do not have to be in CPS. You do not need to include dynamic-let.

At the same time, change the cons, car, cdr, and pair? primitives of your interpreter to construct values using a record like:

    (define-record Pear (a b))
Ensure also that any lists in fields of continuation records use these pears, rather than Scheme pairs. This does not mean that you have to use Pears throughout. By doing this, all fields of closures, environments, continuations, boxes, and Pears should be only simple values, abstract syntax tree records, or closures, environments, continuations, boxes, or Pears. (Note that the parser constructs Scheme pairs for '(a b), so you will have to use (cons 'a (cons 'b ())) instead. Accordingly, I have modified the parser you get by cs441-load to reject '(a b).)

Test your code thoroughly before continuing.

Finally, registerize your interpreter so that the interpreter function and apply-k take no arguments. You do not need to registerize any other procedures.

Test your code thoroughly before continuing.

If you have trouble getting this far, or are suffering a bug you can't track down, you may give up one point of four and ask me for working code from which to continue.

Part 2: Explicit Heap Allocation

Change the representation of continuation records, closure records, environment records, boxes, and pears to allocate space from a large vector of fixed size (the heap). Include the size of the record in slot 0 of the record, and a tag in slot 1. The macro define-heap-record which you can get by
    (cs441-load "heap-record.scm")
will help you make minimal changes to your code. All you should have to do is write heap-alloc, heap-ref, heap-set!, and pointer? (set-box! needs slightly special treatment, and is the only procedure that uses heap-set!). Note that define-heap-record calls heap-alloc without the size field, so heap-alloc must add it.

For example, if a continuation record has 3 fields, allocate 5 slots from the heap to hold the size (5), a tag (symbol) indicating the type of the record and the field values. Continuations, closures, environments, boxes and Pears will now be small integers that are indices into this heap vector. Ensure that all allocation comes from the heap; ie., that the the heap vector contains only simple constants (#t, #f, (), numbers) and heap pointers. At this point, you do not need to distinguish heap pointers from ordinary numbers. Also, note that you only need to place Pears in the heap, not Scheme pairs used in intermediate data structures.

If this step is done right, you won't have to touch the code for the interpreter at all.

Test your code thoroughly before continuing.

Part 3: Identifying Pointers

Using a record like:
    (define-record pointer (contents))
wrap all the small integers that are heap pointers in a pointer structure. This should require changing heap-alloc, heap-ref, and heap-set! only. Now you should be able to distinguish heap pointers from numbers when inspecting the heap.

Test your code VERY thoroughly before continuing.

Part 4: Garbage Collection

Write a copying garbage collector for your heap. Test it first with some data allocated by hand (eg. call make-Pear). When you have it working, place checks at the top of the interpreter and apply-k that invoke the collector if the heap is low on space. (Ideally, determine the maximum amount of space a single interpreter call or apply-k call can allocate, and ensure there is enough space for that allocation. But a rough approximation will do.) Have the collector print out how many heap slots it reclaims each time it is run.

It is not necessary to start with a fresh heap every time eval is called. Junk left in the heap by the last evaluation will be collected at the next garbage collection point. But, you must be careful with the initial continuation and initial environment, as garbage collection may have moved them. Either eval must construct a new initial environment and continuation each time it is called, or the initial environment and continuation must be placed in a register and treated as roots by the garbage collector.

Try your interpreter with a tail recursive infinite loop, but finite heap. It should run forever!

What to turn in

Turn in only a single interpreter. Your assignment should define a function eval that takes one argument, an s-expression, parses it, and evaluates it with the garbage-collected interpreter. Have your garbage collector print messages as indicated above when it runs. Please test that your submission is self contained by starting a fresh Scheme process and sending it:

    (load "your-file")
    (eval '(+ 1 2))
Many earlier assignments have required me to make minor fixes to get them to run, and I am getting tired of doing this.