|
MASSACHUSETTS INSTITUTE OF TECHNOLOGY
| |
| AI Memo No. 349 | December 1975 |
| SCHEME | |
| AN INTERPRETER FOR EXTENDED LAMBDA CALCULUS | |
| by | |
| Gerald Jay Sussman and Guy Lewis Steele Jr. | |
Abstract
Inspired by ACTORS [Greif and Hewitt][1] [Smith and Hewitt][2], we have implemented an interpreter for a LISP-like language, SCHEME, based on the lambda calculus [Church][3], but extended for side effects, multiprocessing, and process synchronization. The purpose of this implementation is tutorial. We wish to:
- 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.
- explain how to use these control structures, independent of such issues as pattern matching and data base manipulation.
- 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 [Moon][4], 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.
- ↑ [Greif and Hewitt]
Greif, Irene and Hewitt, Carl. Actor Semantics of Planner-73. Working Paper 81, MIT AI Lab (Cambridge, 1975). - ↑ [Smith and Hewitt]
Smith, Brian C. and Hewitt, Carl. A PLASMA Primer (draft). MIT AI Lab (Cambridge, October 1975). - ↑ [Church]
Church, Alonzo. The Calculi of Lambda Conversion. Annals of Mathematics Studies Number 6. Princeton University Press (Princeton, 1941). Reprinted by Klaus Reprint Corp. (New York, 1965). - ↑ [Moon]
Moon, David A. MACLISP Reference Manual, Revision 0. Project MAC, MIT (Cambridge, April 1974).
