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. 1 Backus, J. Can programming be liberated from the von Neumarm style? A functional style and its algebra of programs. Comm. ACM 21, 8 (Aug. 1978), 613-641.]]
2. 2 Baker, H. B., Jr. List processing in real time on a serial computer. Comm. ACM 21, 4 (April 1978), 280-294.]]
3. 3 Berkeley, E. C., and Bobrow, D. G., Ed. The Programming Language LISP: Its Operation and Applications. Inform. Internat., Inc., Cambridge, Mass. 1964.]]
4. 4 Bobrow, D. G., and Wegbreit, B. A model and stack implementation of multiple environments. Comm. A CM 16, 10 (Oct. 1973), 591-603.]]
5. 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. 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. 7 Deutsch, L. P., and Bobrow, D.G. An efficient, incremental, automatic garbage collector. Comm. A CM 19, 9 (Sept. 1976), 522- 526.]]
8. 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. 9 Greenblatt, R. The LISP machine. Working Paper 79, MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1974.]]
10. 10 Gries, D. An exercise in proving parallel programs correct. Comm. ACM 20, 12 (Dec. 1977), 921-930.]]
11. 11 Hansen, W.J. Compact list representation: Definition, garbage collection, and system implementation. Comm. ACM 12, 9 (Sept. 1969), 499-507.]]
12. 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. 13 Hewitt, C. Viewing control structures as patterns of passing messages. Artif. Intell. J. 8, 3 (June 1977), 323-364.]]
14. 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. 15 Hon, R., and Sequin, C. A Guide to LSI Implementation. Xerox PARC, Palo Alto, Calif., Sept. 1978.]]
16. 16 Knight, T. The CONS microprocessor. Working Paper 80, MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1974.]]
17. 17 Knuth, D.E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, Reading, Mass., 1968.]]
18. 18 Levin, M. Mathematical logic for computer scientists. TR-131, Project MAC, MIT, Cambridge, Mass., June 1974.]]
19. 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. 20 McCarthy, J., et al. LISP 1.5 Programmer's Manual. MIT Press, Cambridge, Mass., 1962.]]
21. 21 McDermott, D.V., and Sussman, G.J. The CONNIVER reference manual. Memo 295a, MIT Artif. Intell. Lab., Cambridge, Mass., Jan. 1974.]]
22. 22 Mead, C., and Conway, L. Introduction to VLSI Systems. Addison-Wesley, Reading, Mass., 1980.]]
23. 23 Minsky, M.U A LISP garbage collector using serial secondary storage. Memo 58 (revised), MIT Artif. Intell. Lab., Cambridge, Mass., Dec. 1963.]]
24. 24 Minsky, M.L. Computation: Fmite and Infinite Machines. Prentice-Hall, Englewood Cliffs, N.J., 1967.]]
25. 25 Moon, D.A. MacLISP reference manual, revision 0. Project MAC, MIT, Cambridge, Mass,, April 1974.]]
26. 26 Morris, F.L. A time- and space-efficient garbage compaction algorithm. Comm. ACM 21, 8 (Aug. 1978), 662-665.]]
27. 27 Moses, J. The function of FUNCTION in LISP. Memo 199, MIT Artif. Intell. Lab., Cambridge, Mass., June 1970.]]
28. 28 Reynolds, J.C. Definitional interpreters for higher order programming languages. Proc. ACM Nat. Conf., Boston, Mass., 1972, pp. 717-740.]]
29. 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. 30 Schorr, H., and Waite, W.M. An efficient machine-independent procedure for garbage collection in various list structures. Comm. ACM 10, 8 (Aug. 1967), 501-506.]]
31. 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.]]
32. 31 Steele, G.L., Jr. Compiler optimization based on viewing LAMBDA as Rename plus Goto. S.M. Th., MIT, Cambridge, Mass., May 1977.]]
33. 32 Steele, G.L., Jr. Debunking the "expensive procedure call" myth. Proc. ACM Nat. Conf. Seattle, Wash., Oct. 1977, pp. 153-162, revised as Memo 443, MIT Artif. Intell. Cambridge, Mass., Oct. 1977.]]
34. 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.]]
35. 34 Steele, G.L. Jr., and Sussman, G.J. The art of the interpreter; or, the modularity complex (parts zero, one, and two). Memo 453, MIT Artif. Intell. Lab., Cambridge, Mass., Jan. 1978.]]
36. 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.]]
37. 36 Steele, G.L., Jr., and Sussman, G.J. Design of LISP-based processors; or, SCHEME: A dielectric LISP; or, finite memories considered harmful; or, LAMBDA: The ultimate opcode. Memo 514, MIT Artif. Intell. Lab, Cambridge, Mass., March 1979.]]
38. 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.]]
39. 38 Sussman, G.J., and Steele, G.U Jr. SCHEME: An interpreter for extended lambda calculus. Memo 349, MIT Artif. Intell. Lab, Cambridge, Mass., Dec. 1975.]]
40. 39 Wand, M. Continuation-based program transformation strategies. Tech. Rep. 61, Comp. Sci. Dept., Indiana Univ. Bloomington, Indiana, March 1977; J. ACM 27, 1 (Jan. 1980), 164-180.]]
41. 40 Wegbreit, B., et al. ECL programmer's manual. Ctr. for Res. in Comptng. Technology, Harvard Univ., Cambridge, Mass., Dec. 1974.]]
42. 41 Weinreb, D., and Moon, D. LISP machine manual (preliminary version). MIT Artif. Intell. Lab., Cambridge, Mass., Nov. 1978.]]

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language types