Welcome to vScheme!
What language shall we implement? The course will eventually enable you to implement a language you design yourself, but to learn the technology, you’ll start by implementing a simple language called vScheme. It’s a simple functional language based on Scheme, and more exactly, based on the μScheme language that is taught in COMP 105 and is described in my book, Programming Languages: Build, Prove, and Compare. To remind you about μScheme, I’ve cribbed a grammar.
If you already know μScheme, you might be interested in these ways that vScheme is different:
There are more values: in addition to symbols, Booleans, numbers, cons cells, and functions, there are also records, hash tables, and mutable sequences.
The initial environment contains a binding for every possible name. Each name is bound to a unique location which, if not otherwise specified, is initialized to
nil
.vScheme supports more primitives than μScheme.
Assigning to a primitive, as in
(set cons (lambda (x xs) ...))
, is an unchecked run-time error. (The ability to do such things is an odd quirk of Scheme, and I can’t figure out how to make it safe while keeping the implementation simple and efficient.)Primitives usefully appear only in function position, not as first-class values. A primitive that appears in another context is automatically eta-expanded so that in the eta-expansion, it appears in function position.
Primitives
print
andprintu
may be used only for their side effects. Attempting to use a value returned by primitiveprint
orprintu
is an unchecked run-time error. Such an attempt may make your compiler crash.Behavior of functions introduced with
define
is subtly different: in μScheme, a recursive call gets the function’s value out of a global variable, which can be mutated by code outside the function. In vScheme, that value comes out of a local variable, which can be mutated only from within the function.Numbers are IEEE floating-point numbers, not machine integers. Primitive
/
is floating-point division; truncating integer division isidiv
.vScheme does not support the
check-error
unit-test form.
In order to keep the project as simple as possible, we’ll spend the first part of the term working with a first-order subset of vScheme: something without lambda
.