This is the documentation for the software accompanying the textbook Programming Languages: Application and Interpretation (PLAI). The full book can be found on the Web at:
In DrScheme, under the Language menu, select Choose Language.... Under the section Programming Languages: Application and Interpretation, you will find the following languages:
1.1 Defining Types: define-type
|(define-type type-id variant ...)|
The value of each field is checked by its associated contract-expr. A contract-expr may be an arbitrary predicate or a contract.
In addition to the contructors, a define-type expression also defines:
for each field of each variant, an accessor variant-id-field-id that returns the value of the field, and
for each field of each variant, a mutator set-variant-id-field-id! that set the value of the field.
1.2 Deconstructing Data Structures: type-case
If a branch is not specified for each variant, you may use an else branch to create a catch-all branch. An else branch must be the last branch in the sequence of branches. type-case signals a compile-time error if all variants are not covered and the else branch is missing. Similarly, type-case signals a compile-time error if an else branch is unreachable because a branch exists for all variants.
PLAI Scheme provides the following syntactic forms for testing.
|(test result-expr expected-expr)|
(good result-expr result-value expected-value location).
If they do not evaluate to the same value, the test prints
(bad result-expr result-value expected-value location).
If evaluating result-expr signals an error, the test prints
(exception result-expr exception-message <no-expected-value> location)
If evaluating expected-expr signals an error, the test prints
(pred-exception result-expr exception-message <no-expected-value> location)
|(test/pred result-expr pred?)|
If evaluating pred? signals an error, the test prints
(pred-exception result-expr exception-message <no-expected-value> location)
The syntax of pred? is considered expected-value for the purposes of test reporting.
|(test/exn result-expr error-message)|
For example, the following test succeeds:
The error message is "/: division by zero", and "by zero" is a substring of the error message. However, the following test fails:
Although the expression raises an exception and the error string contains "by zero", since the error was not explicitly raised by user-written code, the test fails.
The evaluation of error-message is considered expected-value for the purposes of test reporting.
|(test/regexp result-expr error-message-regexp)|
The evaluation of error-message-regexp is considered expected-value for the purposes of test reporting.
GC Collector Scheme is based on PLAI Scheme. It provides additional procedures and syntax for writing garbage collectors.
The GC Collector Scheme language provides the following functions that provide access to the heap and root set:
|(get-root-set id ...)|
A garbage collector must define the following functions:
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.
|(gc:cons? loc) → boolean?|
|loc : location?|
Returns true if loc refers to a cons cell. This function should never signal an error.
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.
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 allocator-setup. In particular, many of the primitive forms, such as cons map directly to procedures such as gc:cons, written in the collector.
The GC Mutator Scheme language supports the following syntactic forms:
The language also defines the following procedures:
|add1 sub1 zero? + - * / even? odd? = < > <= >= cons first rest|
|set-first! set-rest! cons? symbol? number? boolean? empty? eq?|
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:
|(import-primitives id ...)|
For example, the GC Mutator Scheme language does not define modulo:
|(test/value=? (modulo 5 3) 2)|
GC Mutator Scheme provides two forms for testing mutators:
|(test/location=? mutator-expr1 mutator-expr2)|
|(test/value=? mutator-expr scheme-datum/quoted)|
|(printf format mutator-expr ...)|
The Web Application Scheme language allows you to write server-side Web applications for the PLT Web Server.
For more information about writing Web applications, see: Web: PLT Web Applications.
A Web application must define a procedure start:
|(start initial-request) → response?|
|initial-request : request?|
When you click on the Run button in DrScheme, your Web application is launched in the Web server.
The application is available at http://localhost:8000/servlets/standalone.ss.
The Web Application Scheme language will automatically load this URL in your Web browser.
|(require (planet plai/plai:1:18/random-mutator))|
This PLAI library provides a facility for generating random mutators, in order to test your garbage collection implementation.
|file : path-string?|
|collector-name : string?|
|iterations : exact-positive-integer? = 200|
|program-size : exact-positive-integer? = 10|
|heap-size : exact-positive-integer? = 100|
|string? : "1:18"|
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.
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.
The plai-version string determines which version of PLAI is put into the #lang line for the generated 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.