Programming Languages: Application and Interpretation
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 PLAI Scheme
#lang planet plai/plai:1:6
PLAI Scheme is derived from the scheme langauge. In addition, it includes
the define-type and type-case forms and testing
|(define-type type-id variant ...)|
|variant|| ||=|| ||(variant-id (field-id contract-expr) ...)|
Defines the datatype type-id. A constructor variant-id is defined for each variant.
Each constructor takes an argument for each field of its 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:
a predicate type-id? that returns true for instances of the
datatype, and false for any other value,
for each variant, a predicate variant-id? that returns true when applied to a value of the
same variant and false for any other value,
for each field of each variant, an accessor variant-id-field-id that returns the value of the
for each field of each variant, a mutator set-variant-id-field-id! that set the value of the
1.2 Deconstructing Data Structures: type-case
|branch|| ||=|| ||(variant-id (field-id ...) result-expr ...)|
| || ||||| ||(else result-expr ...)|
Branches on the datatype instance produced by expr
, which must be an instance of datatype-id
(previously defined with define-type
) Each branch
extracts the values of the fields, and binds them
to field-id ...
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.
1.3 Testing Infrastructure
PLAI Scheme provides the following syntactic forms for testing.
|(test result-expr expected-expr)|
If result-expr and expected-expr evaluate to the same value, result-value, the test prints
(good result-expr result-value expected-expr location).
If they do not evaluate to the same value, the test prints
(bad result-expr result-value expected-expr location).
If evaluating result-expr signals an error, the test prints
(exception result-expr exception-message expected-expr location)
Similar to test
, but instead of supplying an expected value, the predicate pred?
is applied to
If evaluating pred? signals an error, the test prints
(pred-exception result-expr exception-message expected-expr location)
pred? is considered expected-expr for the purposes of test reporting.
This test succeeds if the expression evaluates to a call to error
. Moreover, the error message contained in the
exception must contain the string error-message
. Note that test/exn
only suceeds if the exception was
explicitly raised by the user.
For example, the following test succeeds:
(test/exn (error "/: division by zero") "by zero")
The error message is "/: division by zero", and "by zero" is a substring of the error message. However,
the following test fails:
(test/exn (/ 25 0) "by zero")
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.
error-message is considered expected-expr for the purposes of test reporting.
This test is similar to test/exn
,but the error message is matched against a regular expression instead.
error-message-regexp is considered expected-expr for the purposes of test reporting.
1.3.1 Test Flags
When this flag is set to true
, the test forms never prints result-expr
This flag determines whether the program immediately halts when a test fails. By default, programs do not halt on
When this flag is set to true
, only tests that fail will be printed.
By default, the results of all tests are printed.
When testing inexact values for equality, test
permits them to differ by epsilon
default value of epsilon
If this flag is set to true
, when testing for exceptions with test/exn
the message of the exception is ignored. By default, test/exn
only succeed when the
message of the exception matches the supplied string or regular expression.
This variable is the list of all tests that have been run so far, with the most recent test at the head.
2 GC Collector Scheme
#lang planet plai/plai:1:6/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.
for more information.
Determines if v
is an integer between 0
and (- (heap-size) 1)
Determines if v is a root.
A value that may be stored on the heap.
Sets the value at loc to val.
Returns the value at loc.
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.
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.
2.2 Garbage Collector Exports
A garbage collector must define the following functions:
is called before all other procedures by a mutator. Place any requisite initialization code
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.
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.
If cons-cell refers to a cons cell, set the head of the cons cell to
first-value. Otherwise, signal an error.
If cons-cell refers to a cons cell, set the tail of the cons cell to
rest-value. Otherwise, signal an error.
Returns true if loc refers to a cons cell. This function should never signal an error.
refers to a flat value. This function should never signal an error.
3 GC Mutator Scheme
#lang planet plai/plai:1:6/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:
|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
3.2 Mutator API
The GC Mutator Scheme language supports the following syntactic forms:
if and or cond case define let let* set! lambda quote error begin
The language also defines the following procedures:
Sets the first
of the cons cell c
Sets the rest
of the cons cell c
The identifier empty is defined to invoke (gc:alloc-flat 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:
Imports the procedures id ...
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?
even if the imported procedure accepts or produces structured data.
For example, the GC Mutator Scheme language does not define modulo:
Imports the procedures id ...
from the collector module. Each
procedure must be explicited exported from the collector (e.g. (provide id ...)
should be in the collector). The procedures are not transformed to
cooperate with the mutator. That is, they receive location?
primitive procedures, and are expected to produce valid location?
3.3 Testing Mutators
GC Mutator Scheme provides two forms for testing mutators:
succeeds if mutator-expr1
reference the same location
on the heap.
succeeds if mutator-expr
are structurally equal.
is not allocated on the mutator’s heap. Futhermore, it must either be a quoted value or a
|(printf format mutator-expr ...)|
In GC Mutator Scheme, printf
is a syntactic form and not a procedure. The format string,
is not allocated on the mutator’s heap.
4 Web Application Scheme
#lang planet plai/plai:1:6/web
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?|
The initial request to a Web application is serviced by this procedure.
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.
You may use no-web-browser to prevent the browser from being launched and static-files-path
to serve additional static files.