The Scheme Environment
William Clinger Tektronix, Inc.
I can think of no better way to introduce this department than to quote the first two paragraphs
of the introduction
to the new Scheme standard, the Revised3 Report on the Algorithmic Language Scheme [4], which I will refer to
as R3RS. The first paragraph conveys a sense of the Scheme philosophy, while the second paragraph lists technical
features that distinguish Scheme from other programming languages. One of my goals for future articles will be
to explain and illustrate those features, as well as some other features that were considered too experimental to be
included in R3RS.
Programming languages should be designed not by piling feature on top of feature, but by removing the
weaknesses and restrictions that make additional features appear necessary. Scheme demonstrates that
a very small number of rules for forming expressions, with no restrictions on how they are composed,
suffice to form a practical and efficient prograrmning language that is flexible enough to support most
of the major programming paradigms in use today.
Scheme has influenced the evolution of Lisp. Scheme was one of the first programming languages to
incorporate first class procedures as in the lambda calculus, thereby proving the usefulness of static
scope rules and block structure in a dynamically typed language. Scheme was the first major dialect of
Lisp to distinguish procedures from lambda expressions and symbols, to use a single lexical environment
for all variables, and to evaluate the operator position of a procedure call in the same way as an operand
position. By relying entirely on procedure calls to express iteration, Scheme emphasized the fact that
tail-recursive procedure calls are essentially goto's that pass arguments. Scheme was the first widely
used programming language to embrace first class escape procedures, from which all known sequential
control structures can be synthesized. A few of these innovations have recently been incorporated into
Common Lisp, while others remain to be adopted.
The two features of Scheme that have been adopted by Common Lisp are first class procedures and static scope
rules. These are the key features that make Common Lisp superior to most older dialects of Lisp. It can also
be argued that Common Lisp has adopted a third feature: the distinction between procedures, lambda expressions
and symbols. Given the technical meaning of "function" on page 32 of [6] and
the acceptability of symbols and
lambda expressions as arguments to procedures like funcall, apply, and mapcar, it's probably more accurate to
say that Common Lisp has gone part of the way toward adopting this important feature of Scheme but is constrained
by a desire to maintain compatibility with the past.
Several books that use Scheme have been published recently, and more are on the way. Much academic interest in
Scheme was sparked by Structure and Interpretation of Computer Programs by Hal Abelson and Gerry Sussman
with Julie Sussman [1]. This introductory computer science textbook is unusual
in its emphasis upon serious
intellectual concepts rather than details of a particular programming language. Scheme helped to make this approach
work by being simple enough for anyone to learn and powerful enough for everyone to use. Dan Friedman and
Matthias Felleisen also used Scheme when they wrote the second edition of Friedman's The Little Lisper [3]. Oddly
enough, neither the introduction nor the preface to this book mentions Scheme, so their readers have to study the
footnotes to find out which dialect of Lisp they're learning. Other books are keyed to particular implementations.
The SCHEME Programming Language by Kent Dybvig [2] places
particular emphasis on Chez Scheme, while The T
Programming Language by Stephen Slade [5] describes Yale's implementation.
The Scheme development team at the MIT AI Lab maintains a list of available Scheme implementations, primarily
as an aid to people using the Abelson and Sussman textbook. The table below was adapted from their release note
#1 and from information solicited from implementors by Jonathan Rees. It is my hope that implementors of Scheme
will take part in the more detailed survey of Lisp implementations being conducted by Walter van Roggen, so I
|