CS 61A Scheme Specification
Overview
The version of Scheme used in this course is not perfectly true to any official specification of the language, though it is perhaps closest to R5RS. We deviate from R5RS for several reasons, including ease of implementation (both for the staff in reference implementations and for students in completing the Scheme project), ease of instruction, and quirks of Python that our version is built around.
This document and the linked primitive procedure references are very long and are an attempt to formalize the variant of Scheme used in 61A. If you are a student, you should not find it necessary to read this entire document (though a staff member may link to a section of it to answer a question you ask about Scheme) unless you have a personal interest in it.
There are three levels of this specification: student, staff, and web. A completed and fully correct Scheme project serves as a reference implementation of the student level. Students are only expected to know this level on assignments and exams. The additional features of the other levels are purely for those who are interested in them.
The staff interpreter released in Scheme labs and homeworks is the reference implementation of the staff level. This level includes all aspects of the student level, with the addition of variable-argument procedure, macros, error tracing, and quasiquoting. It also contains promises and streams, which have been in the staff interpreter since Fall 2015, but were only added to the project starting in Summer 2016.
The web interpreter is the reference implementation of the web level. It should largely match the staff interpreter's implementation, although, since it is written in Dart instead of Python, some differences may arise due to differences in the two host languages. Known differences which are too difficult to work around will be listed in this document. Please report any other differences as bugs. The web level also includes several additional features, few of which exist in any other Scheme implementation, including a diagrammer and execution visualizer (similar to Python Tutor), built-in libraries and demos, event listeners, comprehensive JS interop, and more.
Data Types
Numbers
Numbers are built on top of Python's number types and can thus support a combination of arbitrarily-large integers and double-precision floating points. The web level should also support the same, though may deviate from Python-based versions due to the different host language and the necessity to work-around the quirks of JavaScript when running in a browser. Any valid number literal in the interpreter's host language should be properly read. You should not count on consistent results when floating point numbers are involved in any calculation or on any numbers with true division.
Booleans
Booleans are built on the host language's boolean type. In Scheme, the boolean
#f
is the only false value. All other values, including the boolean #t
are considered true. Scheme booleans may be inputted either as their
canonical #t
or #f
representations or as any capitalization of the words
"true" or "false". To ease implementation, an interpreter may output booleans
as any representation that is valid as input. All interpreters used in Fall
2017 should output them as True
and False
.
Symbols
Symbols are used as identifiers in Scheme. Valid symbols consist of only the following characters:
ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789!$%&*/:<=>?@^_~+-.
All symbols are case-insensitive and should be internally stored with lowercase letters. Symbols must not form a valid integer or floating-point number.
Strings
Unlike other implementations, 61A Scheme has no concept of characters. Strings are considered primitive data types in their own right. Strings can be entered into the intepreter as a sequence of characters inside double quotes, with certain characters, such as line breaks and double quotes escaped. As a general rule, if a piece of text would be valid as a JSON key, it should work as a string in Scheme. Because the student and staff interpreters have little use for strings, they lack proper support for their manipulation. The web interpreter, which requires strings for JS interop (among other things), has more extensive support, which is described in the web primitives document.
Pairs and Lists
Pairs are a built-in data structure consisting of two fields, a car
and a
cdr
. Each of these two fields can contain any Scheme data type, including
another pair. Pairs can be constructed by passing the values for the two fields
as arguments to cons
.
nil
is a special value in Scheme which represents the empty list. It can be
inputted by typing nil
into the interpreter.
A list is defined as either nil
or a pair whose cdr
is another list. This
may also be referred to as a well-formed list.
Pairs are displayed in the form (a . b)
where a
is the car
and b
is the
cdr
. If b
is nil
, it will be omitted along with the preceding dot, so a
pair constructed as (cons 1 nil)
would be displayed as (1)
. If b
is
another pair, the dot preceding b
and the parentheses wrapping around it are
omitted, so a list constructed as (cons 1 (cons 2 nil))
would be displayed as
(1 2)
.
Procedures
Procedures represent some subroutine within a Scheme program. Procedures are first-class in Scheme, meaning that they can be bound to names and passed around just like any other Scheme value.
Procedures can be called on some number of arguments, performing some number of actions and then returning some Scheme value.
A procedure call can be performed with the syntax (<operator> <operand> ...)
,
where <operator>
is some expression that evaluates to a procedure and each
<operand>
(of which there can be any number, including 0) evaluates to one of
the procedure's arguments.
There are several types of procedures. Primitive procedures (or just primitives) are built-in to the interpreter and already bound to names when it is started (though it is still possible for you to rebind these names). The web interpreter includes a few primitives that act more like special forms, as they do not evaluate the argument expressions. A list of the primitives available in each interpreter is available in the Scheme primitives document.
Lambda procedures are defined using the lambda
special form (see below) and
create a new frame whose parent is the frame in which the lambda was defined in
when called. The expressions in the lambda's body are than evaluated in this
new environment. Mu procedures are similar, but the new frame's parent is the
frame in which the mu
is called, not the frame in which it was created.
61A Scheme also has macro procedures, which must be defined with the
define-macro
special form. Macros work similarly to lambdas, except that they
pass the argument expressions in the call expression into the macro instead of
the evaluated arguments and they then evaluate the expression the macro returns
in the calling environment afterwards.
The web level also contains JS procedures, which appear like primitives in Scheme, but actually wrap a JavaScript function. Any time a JS function is returned through JS interop, it will be wrapped as a JS procedure so it can be called like any normal Scheme primitive.
Promises and Streams
Promises represent the delayed evaluation of an expression in an enviornment.
They can be constructed by passing an expression into the delay
special form.
The evaluation of a promise can be forced by passing it into the force
primitive. The expression of a promise will only ever be evaluated once. The
first call of force
will store the result, which will be immediately returned
on subsequent calls of force
on the same promise.
Promises are used to define streams, which are to lists what promises are to
regular values. A stream is defined as a pair where the cdr is a promise that
evaluates to another stream or nil
. The cons-stream
special form and the
cdr-stream
primitive are provided make the construction and manipulation of
streams easier. (cons-stream a b)
is equivalent to (cons a (delay b))
while (cdr-stream x)
is equivalent to (force (cdr x))
.
Other Types
The web level also contains various other data types. More information about these is available in the web primitives and JS interop documents.
Special Forms
In all of the syntax definitions below, <x>
refers to a required element x
that can vary, while [x]
refers to an optional element x
. Ellipses
indicate that there can be more than one of the preceding element.
Student Level
The following special forms are included in all versions of 61A Scheme.
define
(define <name> <expression>)
Evaluates <expression>
and binds the value to <name>
in the current
environment. <name>
must be a valid Scheme symbol.
(define (<name> [param] ...) <body> ...)
Constructs a new lambda procedure with param
s as its parameters and the body
expressions as its body and binds it to name
in the current environment.
name
must be a valid Scheme symbol. Each param
must be a unique valid Scheme
symbol. At the staff level and above, (<name> [param] ...)
can be dotted, with
a variable number of excess arguments bound as a list to the symbol after the
dot. This shortcut is equivalent to:
(define <name> (lambda ([param] ...) <body> ...))
However, some interpreters may give lambdas created using the shortcut an
intrinsic name of name
for the purpose of visualization or debugging.
if
(if <predicate> <consequent> [alternative])
Evaluates predicate
. If true, the consequent
is evaluated and returned.
Otherwise, the alternative
, if it exists, is evaluated and returned (if no
alternative
is present in this case, the return value is undefined).
cond
(cond <clause> ...)
Each clause
may be of the following form:
(<test> [expression] ...)
The last clause
may instead be of the form (else [expression] ...)
, which
is equivalent to (#t [expression] ...)
.
Starts with the first clause
. Evaluates test
. If true, evaluate the
expression
s in order, returning the last one. If there are none, return what
test
evaluated to instead. If test
is false, proceed to the next clause
.
If there are no more clause
s, the return value is undefined.
and
(and [test] ...)
Evaluate the test
s in order, returning the first false value. If no test
is false, return the last test
. If no arguments are provided, return #t
.
or
(or [test] ...)
Evaluate the test
s in order, returning the first true value. If no test
is true and there are no more test
s left, return #f
.
let
(let ([binding] ...) <body> ...)
Each binding
is of the following form:
(<name> <expression>)
First, the expression
of each binding
is evaluated in the current frame.
Next, a new frame that extends the current environment is created and each
name
is bound to its corresponding evaluated expression
in it.
Finally the body
expressions are evaluated in order, returning the evaluated
last one.
begin
(begin <expression> ...)
Evaluates each expression
in order in the current environment, returning the
evaluated last one.
lambda
(lambda ([param] ...) <body> ...)
Creates a new lambda with param
s as its parameters and the body
expressions
as its body. When the procedure this form creates is called, the call frame
will extend the environment this lambda was defined in.
mu
(mu ([param] ...) <body> ...)
Creates a new mu procedure with param
s as its parameters and the body
expressions as its body. When the procedure this form creates is called, the
call frame will extend the environment the mu is called in.
quote
(quote <expression>)
Returns the literal expression
without evaluating it.
'<expression>
is equivalent to the above form.
delay
(delay <expression>)
Returns a promise of expression
to be evaluated in the current environment.
cons-stream
(cons-stream <first> <rest>)
Shorthand for (cons <first> (delay <rest>))
.
define-macro
(define-macro (<name> [param] ...) <body> ...)
Note: This special form is implemented as part of an extra credit problem.
Constructs a new macro procedure with param
s as its parameters and the body
expressions as its body and binds it to name
in the current environment.
name
must be a valid Scheme symbol. Each param
must be a unique valid Scheme
symbol. (<name> [param] ...)
can be dotted, with a variable number of excess
arguments bound as a list to the symbol after the dot.
In this official implementations of 61A Scheme we release, the body of the macro
is evaluated in a child of the frame that the macro was defined in (that is, it
is lexically scoped). However, in this specification, we treat any use of
define-macro
outside of the global frame as unspecified behavior, so other
implementations need not worry about this distinction.
quasiquote
(quasiquote <expression>)
Returns the literal expression
without evaluating it, unless a subexpression
of expression
is of the form:
(unquote <expr2>)
in which case that expr2
is evaluated and replaces the above form in the
otherwise unevaluated expression
.
<expression>
is equivalent to the above form.
unquote
See above. ,<expr2>
is equivalent to the form mentioned above.
unquote-splicing
(unquote-splicing <expr2>)
Similar to unquote
, except that expr2
must evaluate to a list, which is
then spliced into the structure containing it in expression
.
,@<expr2>
is equivalent to the above form.
Staff Level
The staff level includes all of the special forms above, plus this:
set!
(set! <name> <expression>)
Evaluates expression
and binds the result to name
in the first frame it can
be found in from the current environment. If name
is not bound in the current
environment, this causes an error.
Web Level
The web level does not contain any special forms beyond what is in the staff level, though certain primitives do not evaluate their arguments and thus behave like special forms.
Additional Reading
- Scheme Primitives - covers the primitive procedures at the staff and student levels
- R5RS Specification - the full Scheme specificaton that 61A Scheme most closely resembles.
- Web Interpreter Help - a broad overview of the features of the web interpreter
- Web Primitives - covers the primitive procedures at the web level but not the staff or student levels
- JS Interop - a detailed description of the web interpreter's support for JavaScript interop.