3 GC Mutator Scheme
#lang plai/mutator 
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:
 

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 allocatorsetup. 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 syntactic forms:
if and or cond case define definevalues let letvalues let* set! lambda λ quote error begin
The syntax of define is restricted to: (define (id argid ...) body ...+). The syntax of lambda and λ are restricted to: (lambda (argid ...) body ...+).
The language also defines the following procedures:
add1 sub1 zero? +  * / even? odd? = < > <= >= cons first rest 
setfirst! setrest! cons? symbol? symbol=? number? boolean? empty? eq? 
(setfirst! c v) → void 
c : cons? 
v : any/c 
The identifier empty is defined to invoke (gc:allocflat empty) wherever it is used.
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:
(importprimitives id ...) 
For example, the GC Mutator Scheme language does not define modulo:
(importprimitives modulo) 
(test/value=? (modulo 5 3) 2) 
3.3 Testing Mutators
GC Mutator Scheme provides two forms for testing mutators:
(test/location=? mutatorexpr1 mutatorexpr2) 
(test/value=? mutatorexpr schemedatum/quoted) 
(printf format mutatorexpr ...)  

3.4 Generating Random Mutators
(require plai/randommutator) 
This PLAI library provides a facility for generating random mutators, in order to test your garbage collection implementation.
 
file : pathstring?  
collectorname : string?  
 
iterations : exactpositiveinteger? = 200  
programsize : exactpositiveinteger? = 10  
heapsize : exactpositiveinteger? = 100 
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 heapvalue?. 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.
Elements from the heapvalues argument are used as the base values when creating nodes with no outgoing edges. See also findheapvalues.
The iterations argument controls how many times the graph is created (and traversed).
The programsize 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 heapsize argument controls the size of the heap in the generated mutator.
(findheapvalues input) → (listof heapvalue?) 
input : (or/c pathstring? inputport?) 
If input is a port, its contents are assumed to be a wellformed PLAI program. If input is a file, the contents of the file are used.