2 GC Collector Scheme
GC Collector Scheme is based on PLAI Scheme. It provides additional procedures and
syntax for writing garbage collectors.
2.1 Garbage Collector Interface
The GC Collector Scheme language provides the following functions that provide access to the heap and root set:
Returns the size of the heap. The size of the heap is specified by the mutator that uses the garbage collector.
for more information.
Determines if v
is an integer between 0
and (- (heap-size) 1)
Determines if v is a root.
Sets the value at loc to val.
Returns the value at loc.
Returns the current roots as a list. Local roots are created for the identifiers id as well.
Returns the location of root.
Updates the root to reference the given location.
Given a closure stored on the heap, returns a list of the roots reachable from the closure’s environment. If
proc is not reachable, the empty list is returned.
Evaluates (begin expr ...)
in the context of heap
. Useful in tests:
2.2 Garbage Collector Exports
A garbage collector must define the following functions:
is called before all other procedures by a mutator. Place any requisite initialization code
Given the location of a flat Scheme value, this procedure should return that value. If the location does not hold
a flat value, this function should signal an error.
This procedure should allocate a flat Scheme value (number, symbol, boolean, closure or empty list) on the heap,
returning its location (a number). The value should occupy a single heap cell, though you may use additional space to
store a tag, etc. You are also welcome to pre-allocate common constants (e.g., the empty list). This procedure may need
to perform a garbage-collection. If there is still insufficient space, it should signal an error.
Note that closures are flat values. The environment of a closure is internally managed, but contains
references to values on the heap. Therefore, during garbage collection, the environment of reachable closures must be
updated. The language exposes the environment via the procedure-roots function.
Given the location of the first and rest values, this procedure must allocate a cons cell on the
heap. If there is insufficient space to allocate the cons cell, it should signal an error.
If the given location refers to a cons cell, this should return the first field. Otherwise, it should signal an error.
If the given location refers to a cons cell, this should return the rest field. Otherwise, it should signal an error.
If cons-cell refers to a cons cell, set the head of the cons cell to
first-value. Otherwise, signal an error.
If cons-cell refers to a cons cell, set the tail of the cons cell to
rest-value. Otherwise, signal an error.
Returns true if loc refers to a cons cell. This function should never signal an error.
refers to a flat value. This function should never signal an error.