▼Programming Languages:   Application and Interpretation
►2 GC Collector Scheme
On this page:
2.1 Garbage Collector Interface
heap-size
location?
root?
heap-value?
heap-set!
heap-ref
get-root-set
read-root
set-root!
procedure-roots
with-heap
current-heap
with-roots
2.2 Garbage Collector Exports
init-allocator
gc:  deref
gc:  alloc-flat
gc:  cons
gc:  first
gc:  rest
gc:  set-first!
gc:  set-rest!
gc:  cons?
gc:  flat?
  top  ← prev  up  next → 

2 GC Collector Scheme

 #lang plai/collector package: plai-lib

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:

procedure

(heap-size) → exact-nonnegative-integer?

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.

procedure

(location? v) → boolean?

  v : any/c
Determines if v is an integer between 0 and (- (heap-size) 1) inclusive.

procedure

(root? v) → boolean?

  v : any/c
Determines if v is a root.

procedure

(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?).

procedure

(heap-set! loc val) → void?

  loc : location?
  val : heap-value?
Sets the value at loc to val.

procedure

(heap-ref loc) → heap-value?

  loc : location?
Returns the value at loc.

syntax

(get-root-set id ...)

Returns the current roots as a list. Local roots are created for the identifiers id as well.

procedure

(read-root root) → location?

  root : root?
Returns the location of root.

procedure

(set-root! root loc) → void?

  root : root?
  loc : location?
Updates the root to reference the given location.

procedure

(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.

syntax

(with-heap heap-expr body-expr ...)

 
  heap-expr : (vectorof heap-value?)
Evaluates each of the body-exprs in a context where the value of heap-expr is used as the heap. Useful in tests:
(test (with-heap (make-vector 20)
        (init-allocator)
        (gc:deref (gc:alloc-flat 2)))
      2)

value

current-heap : (parameter/c (vectorof heap-value?))

Bound to the current heap inside of with-heap.

syntax

(with-roots roots-expr expr1 expr2 ...)

 
  roots-expr : (listof location?)
Evaluates each of expr1 and the expr2s in in a context with the result of roots-expr as additional roots.

This function is intended to be used in test suites for collectors. Since your test suites are not running in the

#lang plai/mutator

language, get-root-set returns a list consisting only of the roots it created, not all of the other roots it normally would return. Use this function to note specific locations as roots and set up better tests for your GC.

(test (with-heap (make-vector 4)
                 (define f1 (gc:alloc-flat 1))
                 (define c1 (gc:cons f1 f1))
                 (with-roots (list c1)
                             (gc:deref
                              (gc:first
                               (gc:cons f1 f1)))))
      1)

2.2 Garbage Collector Exports

A garbage collector must define the following functions:

procedure

(init-allocator) → void?

init-allocator is called before all other procedures by a mutator. Place any requisite initialization code here.

procedure

(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.

procedure

(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.

procedure

(gc:cons first rest) → location?

  first : location?
  rest : location?
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.

procedure

(gc:first cons-cell) → location?

  cons-cell : location?
If the given location refers to a cons cell, this should return the first field. Otherwise, it should signal an error.

procedure

(gc:rest cons-cell) → location?

  cons-cell : location?
If the given location refers to a cons cell, this should return the rest field. Otherwise, it should signal an error.

procedure

(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.

procedure

(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.

procedure

(gc:cons? loc) → boolean?

  loc : location?

Returns true if loc refers to a cons cell. This function should never signal an error.

procedure

(gc:flat? loc) → boolean?

  loc : location?
Returns true if loc refers to a flat value. This function should never signal an error.

  top  ← prev  up  next →