3 GC Mutator Scheme

The GC Mutator Scheme language is used to test garbage collectors written with the GC Collector Scheme language. Since collectors support a subset of Scheme’s values, the GC Mutator Scheme language supports a subset of procedures and syntax. In addition, many procedures that can be written in the mutator are omitted as they make good test cases. Therefore, the mutator language provides only primitive procedures, such as +, cons, etc.

3.1 Building Mutators

The first expression of a mutator must be:

syntax
(allocator-setup collector-module
heap-size)

heap-size = exact-nonnegative-integer?

collector-module specifies the path to the garbage collector that the mutator should use. The collector must be written in the GC Collector Scheme language.

The rest of a mutator module is a sequence of definitions, expressions and test cases. The GC Mutator Scheme language transforms these definitions and statements to use the collector specified in allocator-setup. In particular, many of the primitive forms, such as cons map directly to procedures such as gc:cons, written in the collector.

3.2 Mutator API

The GC Mutator Scheme language supports the following procedures and syntactic forms:

syntax
if

Just like Racket’s if.

syntax
and

Just like Racket’s and.

syntax
or

Just like Racket’s or.

syntax
cond

Just like Racket’s cond.

syntax
case

Just like Racket’s case.

syntax
define-values

Just like Racket’s define-values.

syntax
let

Just like Racket’s let.

syntax
let-values

Just like Racket’s let-values.

syntax
let*

Just like Racket’s let*.

syntax
set!

Just like Racket’s set!.

syntax
quote

Just like Racket’s quote.

syntax
error

Just like Racket’s error.

syntax
begin

Just like Racket’s begin.

syntax
(define (id arg-id ...) body-expression ...+)

Just like Racket’s define, except restricted to the simpler form above.

syntax
(lambda (arg-id ...) body-expression ...+)
syntax
(λ (arg-id ...) body-expression ...+)

Just like Racket’s lambda and λ, except restricted to the simpler form above.

syntax
add1

Just like Racket’s add1.

syntax
sub1

Just like Racket’s sub1.

syntax
zero?

Just like Racket’s zero?.

syntax
+

Just like Racket’s +.

syntax
-

Just like Racket’s -.

syntax
*

Just like Racket’s *.

syntax
/

Just like Racket’s /.

syntax
even?

Just like Racket’s even?.

syntax
odd?

Just like Racket’s odd?.

syntax
=

Just like Racket’s =.

syntax
<

Just like Racket’s <.

syntax
>

Just like Racket’s >.

syntax
<=

Just like Racket’s <=.

syntax
>=

Just like Racket’s >=.

syntax
symbol?

Just like Racket’s symbol?.

syntax
symbol=?

Just like Racket’s symbol=?.

syntax
number?

Just like Racket’s number?.

syntax
boolean?

Just like Racket’s boolean?.

syntax
empty?

Just like Racket’s empty?.

syntax
eq?

Just like Racket’s eq?.

procedure
(cons hd tl) → cons?
hd : any/c
tl : any/c

Constructs a (mutable) pair.

procedure
(cons? v) → boolean?
v : any/c

Returns #t when given a value created by cons, #f otherwise.

procedure
(first c) → any/c
c : cons?

Extracts the first component of c.

procedure
(rest c) → any/c
c : cons?

Extracts the rest component of c.

procedure
(set-first! c v) → void
c : cons?
v : any/c

Sets the first of the cons cell c.

procedure
(set-rest! c v) → void
c : cons?
v : any/c

Sets the rest of the cons cell c.

syntax
empty

The identifier empty is defined to invoke (gc:alloc-flat empty) wherever it is used.

syntax
print-only-errors

Behaves like PLAI’s print-only-errors.

syntax
halt-on-errors

Behaves like PLAI’s halt-on-errors.

Other common procedures are left undefined as they can be defined in terms of the primitives and may be used to test collectors.

Additional procedures from scheme may be imported with:

syntax
(import-primitives id ...)

Imports the procedures id ... from scheme. Each procedure is transformed to correctly interface with the mutator. That is, its arguments are dereferenced from the mutator’s heap and the result is allocated on the mutator’s heap. The arguments and result must be heap-value?s, even if the imported procedure accepts or produces structured data.

For example, the GC Mutator Scheme language does not define modulo:

(import-primitives modulo)

(test/value=? (modulo 5 3) 2)

3.3 Testing Mutators

GC Mutator Scheme provides two forms for testing mutators:

syntax
(test/location=? mutator-expr1 mutator-expr2)

test/location=? succeeds if mutator-expr1 and mutator-expr2 reference the same location on the heap.

syntax
(test/value=? mutator-expr scheme-datum/quoted)

test/value=? succeeds if mutator-expr and scheme-datum/expr are structurally equal. scheme-datum/quoted is not allocated on the mutator’s heap. Futhermore, it must either be a quoted value or a literal value.

syntax
(printf format mutator-expr ...)

format = literal-string

In GC Mutator Scheme, printf is a syntactic form and not a procedure. The format string, format is not allocated on the mutator’s heap.

3.4 Generating Random Mutators

(require plai/random-mutator)

This PLAI library provides a facility for generating random mutators, in order to test your garbage collection implementation.

procedure
(save-random-mutator file
collector-name
[ #:heap-values heap-values
#:iterations iterations
#:program-size program-size
#:heap-size heap-size]) → void?
  file : path-string?
  collector-name : string?
   heap-values : (cons heap-value? (listof heap-value?))
= (list 0 1 -1 'x 'y #f #t '())
  iterations : exact-positive-integer? = 200
  program-size : exact-positive-integer? = 10
  heap-size : exact-positive-integer? = 100

Creates a random mutator that uses the collector collector-name and saves it in file.

The mutator is created by first making a random graph whose nodes either have no outgoing edges, two outgoing edges, or some random number of outgoing edges and then picking a random path in the graph that ends at one of the nodes with no edges.

This graph and path are then turned into a PLAI program by creating a let expression that binds one variable per node in the graph. If the node has no outgoing edges, it is bound to a heap-value?. If the node has two outgoing edges, it is bound to a pair and the two edges are put into the first and rest fields. Otherwise, the node is represented as a procedure that accepts an integer index and returns the destination node of the corresponding edge.

Once the let expression has been created, the program creates a bunch of garbage and then traverses the graph, according to the randomly created path. If the result of the path is the expected heap value, the program does this again, up to iterations times. If the result of the path is not the expected heap value, the program terminates with an error.

The keyword arguments control some aspects of the generation of random mutators:

Elements from the heap-values argument are used as the base values when creating nodes with no outgoing edges. See also find-heap-values.
The iterations argument controls how many times the graph is created (and traversed).
The program-size argument is a bound on how big the program it is; it limits the number of nodes, the maximum number of edges, and the length of the path in the graph.
The heap-size argument controls the size of the heap in the generated mutator.

procedure
(find-heap-values input) → (listof heap-value?)
input : (or/c path-string? input-port?)

Processes input looking for occurrences of heap-value?s in the source of the program and returns them. This makes a good start for the heap-values argument to save-random-mutator.

If input is a port, its contents are assumed to be a well-formed PLAI program. If input is a file, the contents of the file are used.

top← prev up next →

1	PLAI Scheme
2	GC Collector Scheme
3	GC Mutator Scheme
4	Web Application Scheme

3.1	Building Mutators
3.2	Mutator API
3.3	Testing Mutators
3.4	Generating Random Mutators