Scheme−: a small dialect of the Scheme LISP language

The following grammar summarizes Scheme−, as described in the PhD dissertation by Jonathan Allen Rees of MIT, February 1995, "A Security Kernel Based on the Lambda-Calculus." E stands for an expression.

The meaning of most of the constructs is as in full Scheme. The first group of three constructs in Scheme−’s λ-calculus core: variable reference, procedure abstraction (lambda), and application. Each of the next group of five constructs (if, etc.) has a special evaluation rule.

The rest of the constructs are a set of primitive operators. In every case all of the operand expressions are evaluated before the operator is applied. Most of these are familiar, but a few require explanation:

The cell is a mutable object with a single outgoing access link (field). (new-cell) creates a new, uninitialized cell, (cell-ref cell ) returns the object to which cell currently has a link, and (cell-set! cell obj ) redirects cell’s outgoing link to obj.

The enclose operator takes a program and a specification of a successor set and converts them to a procedure. enclose might be called on the output of a Scheme− or Algol compiler.

The control operator controls hardware devices. For example,

might read a character from a particular keboard. Its arguments are interpreted differently for different kinds of devices.

The reduce the complexity of the exposition, pairs will be assumed to be immutable, and eq? will be assumed to be applicable only to symbols and cells.

I’ll use the term value to describe integers, booleans, symbols, and other entities that carry only information, not privileges. Whether or not values are considered to be objects is unimportant.