2 GC Collector Scheme
| #lang plai/collector |
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. See allocator-setup for more
information.
Determines if v is a root.
(heap-value? v) → boolean? v : any/c
A value that may be stored on the heap. Roughly corresponds to the contract
(or/c boolean? number? procedure? symbol? empty?).
(heap-set! loc val) → void? loc : location? val : heap-value?
Sets the value at loc to val.
(heap-ref loc) → heap-value? loc : location?
Returns the value at loc.
(get-root-set id ...)
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.
(procedure-roots proc) → (listof root?) proc : procedure?
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.
(with-heap heap expr ...)
heap : (vectorof heap-value?)
(test (with-heap (make-vector 20) (init-allocator) (gc:deref (gc:alloc-flat 2))) 2)
2.2 Garbage Collector Exports
A garbage collector must define the following functions:
(init-allocator) → void?
init-allocator is called before all other procedures by a
mutator. Place any requisite initialization code here.
(gc:deref loc) → heap-value? loc : location?
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.
(gc:alloc-flat val) → location? val : heap-value?
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.
(gc:set-first! cons-cell first-value) → void? cons-cell : location? first-value : location?
If cons-cell refers to a cons cell, set the head of the cons cell to
first-value. Otherwise, signal an error.
(gc:set-rest! cons-cell rest-value) → void? cons-cell : location? rest-value : location?
If cons-cell refers to a cons cell, set the tail of the cons cell to
rest-value. Otherwise, signal an error.
(gc:cons? loc) → boolean? loc : location?
Returns true if loc refers to a cons cell. This function should never signal an error.
Returns true if loc refers to a flat value. This function
should never signal an error.