Design of a LISP-based microprocessor

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, and so is a suitable basis for 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 of various sizes, rather than an ordered, indexable vector of integers or bit fields of fixed size. An instruction set can be designed for programs expressed as trees of record structures. A processor can interpret these program trees in a recursive fashion and provide automatic storage management for the record structures. We discuss a small-scale prototype VLSI microprocessor which has been designed and fabricated, containing a sufficiently complete instruction interpreter to execute small programs and a rudimentary storage allocator.

REFERENCES

• 1: John Backus, Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs, Communications of the ACM, v.21 n.8, p.613-641, Aug. 1978 [doi>10.1145/359576.359579]
• 2: Henry G. Baker, Jr., List processing in real time on a serial computer, Communications of the ACM, v.21 n.4, p.280-294, April 1978 [doi>10.1145/359460.359470]
• 3: Berkeley, E. C., and Bobrow, D. G., Ed. The Programming Language LISP: Its Operation and Applications. Inform. Internat., Inc., Cambridge, Mass. 1964.
• 4: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 5: Church, A. The Calculi of Lambda Conversion. In Annals of Mathematics Studies, Number 6, Princeton Univ. Press, Princeton, N.J., 1941 (reprinted by Klaus Reprint Corp., N.Y., 1965).
• 6: Conrad, W. R. A compactifying garbage collector for ECL's nonhomogeneous heap. Tech. Rep. 2-74, Ctr. for Res. in Comptng. Technology, Harvard Univ. Cambridge, Mass., Feb. 1974.
• 7: L. Peter Deutsch , Daniel G. Bobrow, An efficient, incremental, automatic garbage collector, Communications of the ACM, v.19 n.9, p.522-526, Sept. 1976 [doi>10.1145/360336.360345]
• 8: Galley, S.W., and Pfister, G. The MDL language. Programming Technology Division Document SYS, 11.01, Project MAC, MIT, Cambridge, Mass., Nov. 1975.
• 9: Greenblatt, R. The LISP machine. Working Paper 79, MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1974.
• 10: David Gries, An exercise in proving parallel programs correct, Communications of the ACM, v.20 n.12, p.921-930, Dec. 1977 [doi>10.1145/359897.359903]
• 11: Wilfred J. Hansen, Compact list representation: definition, garbage collection, and system implementation, Communications of the ACM, v.12 n.9, p.499-507, Sept. 1969 [doi>10.1145/363219.363225]
• 12: Hart, TP., and Evans, T.G. Notes on implementing LISP for the M-460 computer. In The Programming Language LISP: Its Operation and Applications, E.C. Berkeley and D.G. Bobrow, Eds. Inform. Internat., Inc., Cambridge, Mass., 1964, pp. 191-203.
• 13: Hewitt, C. Viewing control structures as patterns of passing messages. Artif. Intell. J. 8, 3 (June 1977), 323-364.
• 14: Holloway, J., Steele, G.L., Jr., Sussman, G.J., and Bell, A. The SCHEME-79 chip. Memo 559, MIT Artif. Intell. Lab. Cambridge, Mass., Jan. 1980.
• 15: Hon, R., and Sequin, C. A Guide to LSI Implementation. Xerox PARC, Palo Alto, Calif., Sept. 1978.
• 16: Knight, T. The CONS microprocessor. Working Paper 80, MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1974.
• 17: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 18: M. Levin, MATHEMATICAL LOGIC FOR COMPUTER SCIENTISTS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 19: The LISP Machine Group: Bawden, A., Greenblatt, R., Holloway, J., Knight, T., Moon, D., and Weinreb, D. LISP machine progress report. Memo 444, MIT Artif. Intell., Lab, Cambridge, Mass., Aug. 1977.
• 20: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 21: McDermott, D.V., and Sussman, G.J. The CONNIVER reference manual. Memo 295a, MIT Artif. Intell. Lab., Cambridge, Mass., Jan. 1974.
• 22: Carver Mead , Lynn Conway, Introduction to VLSI Systems, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1979
• 23: Marvin Minsky, A LISP Garbage Collector Algorithm Using Serial Secondary Storage, Massachusetts Institute of Technology, Cambridge, MA, 1963
• 24: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 25: Moon, D.A. MacLISP reference manual, revision 0. Project MAC, MIT, Cambridge, Mass,, April 1974.
• 26: F. Lockwood Morris, A time- and space-efficient garbage compaction algorithm, Communications of the ACM, v.21 n.8, p.662-665, Aug. 1978 [doi>10.1145/359576.359583]
• 27: Moses, J. The function of FUNCTION in LISP. Memo 199, MIT Artif. Intell. Lab., Cambridge, Mass., June 1970.
• 28: John C. Reynolds, Definitional interpreters for higher-order programming languages, Proceedings of the ACM annual conference, p.717-740, August 01-01, 1972, Boston, Massachusetts, United States [doi>10.1145/800194.805852]
• 29: Saunders, R.A. The LISP system for the Q-32 computer. In The Programming Language LISP: Its Operation and Applications, E.C. Berkeley and D.G. Bobrow, Eds., Inform. Internat., Inc., Cambridge, Mass., 1964, pp. 220-231.
• 30: H. Schorr , W. M. Waite, An efficient machine-independent procedure for garbage collection in various list structures, Communications of the ACM, v.10 n.8, p.501-506, Aug. 1967 [doi>10.1145/363534.363554]
• 30a: Stallman, R.M. Phantom Stacks: If you look too hard, they aren't there. MIT Artif. Intell. Lab. Memo. No. 556, Cambridge, Mass., July 1980.
• 31: Steele, G.L., Jr. Compiler optimization based on viewing LAMBDA as Rename plus Goto. S.M. Th., MIT, Cambridge, Mass., May 1977.
• 32: Guy Lewis Steele, Jr., Debunking the “expensive procedure call” myth or, procedure call implementations considered harmful or, LAMBDA: The Ultimate GOTO, Proceedings of the 1977 annual conference, p.153-162, January 1977 [doi>10.1145/800179.810196]
• 33: Steele, G.L. Jr., and Sussman, G.J. The revised report on SCHEME: A dialect of LISP. Memo 452, MIT Artif. Intell. Lab., Cambridge, Mass., 1978.
• 34: Guy L Steele , Gerald J Sussman, The Art of the Interpreter or, The Modularity Complex (Parts Zero, One, and Two), Massachusetts Institute of Technology, Cambridge, MA, 1978
• 35: Steele, G.L., Jr., and Sussman, G.J. Storage management in a LISP-based processor. Proc. Caltech Conf. on Very Large-Scale Integration, Pasadena, Calif., Jan. 1979, 227-241.
• 36: Guy L Steele , Gerald J Sussman, Design of LISP-based Processors, or SCHEME: A Dielectric LISP, or Finite Memories Considered Harmful, or LAMBDA: The Ultimate Opcode, Massachusetts Institute of Technology, Cambridge, MA, 1979
• 37: Steele, G.L., Jr., and Sussman, G:J. The dream of a lifetime: A lazy scoping mechanism. Memo 527, MIT Artif. Intetl. Lab., Cambridge, Mass., Nov. 1979.
• 38: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 39: Mitchell Wand, Continuation-Based Program Transformation Strategies, Journal of the ACM (JACM), v.27 n.1, p.164-180, Jan. 1980 [doi>10.1145/322169.322183]
• 40: Wegbreit, B., et al. ECL programmer's manual. Ctr. for Res. in Comptng. Technology, Harvard Univ., Cambridge, Mass., Dec. 1974.
• 41: Weinreb, D., and Moon, D. LISP machine manual (preliminary version). MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1978.

INDEX TERMS

Keywords:
LISP, SCHEME, VLSI, direct execution, garbage collection, high-level language architectures, integrated circuits, interpreters, large-scale integration, linked lists, list structure, microprocessors, storage management, tail recursion