A LISP Machine with Very Compact Programs

L. Peter Deutsch Xerox corporation, Palo Alto Research center (PARC) Palo Alto, California 94304 Abstract This paper presents a machine designed for compact representation and rapid execution of LISP programs. The machine language is a factor of 2 to 5 more compact than S-expressions or conventional compiled code, and the.compiler is extremely simple. The encoding scheme is potentially applicable to data as well as program. The machine also provides for user-defined data structures. Introduction Pew existing computers permit convenient or efficient implementation of dynamic storage allocation, recursive procedures, or operations on data whose type is represented explicitly at run time rather than determined at compile time. This mismatch between machine and language design plagues every implementor of languages designed for manipulation of structured information.