Page:AIM-514.djvu/1

Massachusetts Institute of Technology Artificial Intelligence Laboratory
AI Memo No. 514	March 1979
Design of LISP-Based Processors or, SCHEME: A Dielectric LISP or, Finite Memories Considered Harmful or, LAMBDA: The Ultimate Opcode
by
Guy Lewis Steele Jr.* and Gerald Jay Sussman**

Abstract:

We present a design for a class of computers whose instruction sets are based on LISP. LISP, like traditional stored-program machine languages and unlike most high-level languages, conceptually stores programs and data in the same way and explicitly allows programs to be manipulated as data. LISP is therefore a suitable language around which to design a stored-program computer architecture. LISP differs from traditional machine languages in that the program/data storage is conceptually an unordered set of linked record structures or various sizes, rather than an ordered, indexabie vector of integers or bit fields of fixed size. The record structures can be organized into trees or graphs. An instruction set can be designed for programs expressed as such trees. A processor can interpret these trees in a recursive fashion, and provide automatic storage management for the record structures.

We describe here the basic ideas behind the architecture, and for concreteness give a specific instruction set (on which variations are certainly possible). We also discuss the similarities and differences between these ideas and those of traditional architectures.

A prototype VLSI microprocessor has been designed and fabricated far testing. It is a small-scale version of the ideas presented here, containing a sufficiently complete instruction interpreter to execute small programs, and a rudimentary storage a1locator. We intend to design and fabricate a full-scale VLSI version of this architecture in 1979.

Keywords: microprocessors, LISP, SCHEME, large scale integration, integrated circuits, VLSI, list structure, garbage collection, storage management

This report describes research done at the Artificial Intelligence Laboratory of the Massacntlsetts Institute of Technology. This work was supported in part by the National Science Foundation under Grant MCS77-04828, and in part by Air Force Office of Scientific Research Grant AFOSR-78-3593.

* Fannie and John Hertz Fellow

** Esther and Harold E. Edgerton Associate Professor of Electrical Engineering