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), vectors (these actually are in other Scheme implementations), a debugger, 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. The Python-based project and staff interpreter will output booleans as True and False while the Dart-based web interpreter will use 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.

The staff and web levels also contain 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 vectors, which are data structures containing a fixed number of fields, similar to arrays in languages like Java or C, and JS objects, which simply wrap real JavaScript objects received through interop. More information about these is available in the web primitives and JS interop documents, respectively.

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 params 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 expressions 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 clauses, the return value is undefined.

and

(and [test] ...)

Evaluate the tests in order, returning the first false value. If no test is false and there are no more tests left, return #t.

or

(or [test] ...)

Evaluate the tests in order, returning the first true value. If no test is true and there are no more tests 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 params 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 params 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>)).

Staff Level

The staff level includes all of the special forms above, plus these.

define-macro

(define-macro (<name> [param] ...) <body> ...)

Constructs a new macro procedure with params 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.

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.

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.

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.