Higher-Order and Symbolic Computation, 11(4)405-439
Scheme: A Interpreter for Extended Lambda CalculusGerald Jay Sussman, Massachusetts Institute of Technology, 545 Tech Square, Room 428, Cambridge, MA 02139, USA
Guy L. Steele Jr., Sun Microsystems Labs, 2 Elizabeth Drive, MS UCHL03-207, Chelmsford, MA 01824, USA
|
Abstract: Inspired by ACTORS [7, 17], we have implemented an
interpreter for a LISP-like language, SCHEME, based on the lambda
calculus [2], but extended for side effects, multiprocessing, and
process synchronization. The purpose of this implementation is
tutorial. We wish to: 1.alleviate the confusion caused by
Micro-PLANNER, CONNIVER, etc., by clarifying the embedding of
non-recursive control structures in a recursive host language like
LISP. 2.explain how to use these control structures, independent of
such issues as pattern matching and data base manipulation. 3.have a
simple concrete experimental domain for certain issues of programming
semantics and style. This paper is organized into sections. The first
section is a short "reference manual" containing specifications for
all the unusual features of SCHEME. Next, we present a sequence of
programming examples which illustrate various programming styles, and
how to use them. This will raise certain issues of semantics which we
will try to clarify with lambda calculus in the third section. In the
fourth section we will give a general discussion of the issues facing
an implementor of an interpreter for a language based on lambda
calculus. Finally, we will present a completely annotated interpreter
for SCHEME, written in MacLISP [13], to acquaint programmers with the
tricks of the trade of implementing non-recursive control structures
in a recursive language like LISP. This report describes research done at the Artificial Intelligence Laboratory of the Massachusetts Institute of Technology. Support for the laboratory?s artificial intelligence research is provided in part by the Advanced Research Projects Agency of the Department of Defense under Office of Naval Research contract N00014-75-C-0643. |
This article can be downloaded [here] or locally [here].
![[picture of journal cover]](../LISP.JPG)