Read EOPL Chapter 10 for background, and the lecture notes.
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.
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.
(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.
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!
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.