Programming Languages -- Spring '98

Homework 6 (honors part): Garbage collection

Due Tuesday March 3, 11:59pm.

In this assignment, you will implement a mark and sweep garbage collector for a language with the following features:

Recursive procedures implemented via letrecproc. Only one procedure can be defined in a single letrecproc expression.
List manipulation primitives: car, cdr, cons, set-car!, set-cdr!, null and the empty list constant emptylist.
No set!. Therefore, we don't need to bother with packaging procedure arguments in boxes or cells.
Explicit heap maintainance. Unlike previous interpreters that we wrote, this one does not use meta-language's heap for allocation of objects of the interpreted language.

This file, 6honors.ss, provides an implementation of the described language. Instead of passing the store in and out of the interpreter like we did in Assignment 4, we define a global variable, the-store, that contains the current image of the heap.

The interpreter takes a recordified expression and an environment (as before) and returns a pointer object. There are several kinds of pointers, and each one is implemented as a record whose tag starts with the letter "p" (for pointer). These are the kinds of pointers:

pnum pointer represents a number and contains the value of the number.
pnull pointer represents the empty list.
pprim pointer represents a primitive procedure and contains a Scheme procedure that performs the job.
ppair pointer refers to a pair. It contains the address in the heap where the first element of the pair is located. The second element of the pair resides in the next location.
pclosure pointer contains the address where the closure is allocated. The first location at that address contains the size of the closure's environment; the second location contains the list of formal parameters, and the third location contains the body of the closure in its record form. Starting from location 4, reside the environment cells.
penv-cell pointer is an internal pointer type that is never returned by the interpreter. It is used to store an environment association in the heap as a part of a closure. A pointer of this kind contains an env association which is a pair of a variable name and a pointer.

The heap is represented by a vector of size HEAP-SIZE. Each element of the vector can be either the symbol free or a record of type mcell (for memory cell). Each memory cell contains a mark bit and a pointer.

There are two operations that allocate heap space: closure creation and pair creation. During either of these operations, the system might run out of heap space. In such a case, it should call the garbage collector passing it the current environment. Currently, there is a stub function gc in place of the garbage collector that simply throws an error informing the user that there is not enough memory. You are to modify this function to perform mark and sweep garbage collection. Use heap ADT functions for marking, unmarking of memory cells; checking whether a cell is marked; freeing unused cells. Also, for scanning the heap, you might want to utilize the for function defined in the beginning of the file.

Consider the following two examples of heap layout. In the first example the pointer #(ppair 4) refers to the list '(1 2 3) assuming that the first 6 cells in the heap are as follows:

#(mcell #f #(pnum 3))              ; cell 0
#(mcell #f #(pnull))               ; cell 1
#(mcell #f #(pnum 2))              ; cell 2
#(mcell #f #(ppair 0))             ; cell 3
#(mcell #f #(pnum 1))              ; cell 4
#(mcell #f #(ppair 2))             ; cell 5

In the second example, the pointer #(pclosure 0) refers to the closure obtained by evaluating (lambda (x) x) in the initial envronment. As you can see the second and third heap locations contain the formal parameters and the body of the procedure; the remaining locations contain the environment in which the procedure was evaluated, and the very first location gives the size of the environment.

#(mcell #f 16)                                                ; cell 0
#(mcell #f (x))
#(mcell #f #(varref x))
#(mcell #f #(penv-cell (+ . #(pprim #<procedure plus>))))
#(mcell #f #(penv-cell (- . #(pprim #<procedure minus>))))
#(mcell #f #(penv-cell (* . #(pprim #<procedure times>))))
#(mcell #f #(penv-cell (add1 . #(pprim #<procedure addone>))))
#(mcell #f #(penv-cell (sub1 . #(pprim #<procedure subone>))))
#(mcell #f #(penv-cell (cons . #(pprim #<procedure make-pair>))))
#(mcell #f #(penv-cell (set-car! . #(pprim #<procedure setcar>))))
#(mcell #f #(penv-cell (zero . #(pprim #<procedure zero>))))
#(mcell #f #(penv-cell (less . #(pprim #<procedure less>))))
#(mcell #f #(penv-cell (greater . #(pprim #<procedure greater>))))
#(mcell #f #(penv-cell (car . #(pprim #<procedure fst>))))
#(mcell #f #(penv-cell (cdr . #(pprim #<procedure snd>))))
#(mcell #f #(penv-cell (null . #(pprim #<procedure null>))))
#(mcell #f #(penv-cell (equal . #(pprim #<procedure equal>))))
#(mcell #f #(penv-cell (set-cdr! . #(pprim #<procedure setcdr>))))
#(mcell #f #(penv-cell (emptylist . #(pnull))))

The following test case will not work in the given interpreter because of the lack of memory. Once you implement the garbage collector, it will enable this program to run.

> (decode-ptr
    (eval-exp
      (recordify
	'(letrecproc (r (ls acc)
		       (if (null ls)
			   acc
			   (r (cdr ls) (cons (car ls) acc))))
	   (r
	     (cons 1 (cons 2 (cons 3 (cons 4 (cons 5 emptylist)))))
	     emptylist)))
      init-env))
(5 4 3 2 1)

Submission

Subject line for this assignment is handin a6honors.

milevin@cs.indiana.edu