The evolution of Lisp

ABSTRACT

Lisp is the world's greatest programming language---or so its proponents think. The structure of Lisp makes it easy to extend the language or even to implement entirely new dialects without starting from scratch. Overall, the evolution of Lisp has been guided more by institutional rivalry, one-upsmanship, and the glee born of technical cleverness that is characteristic of the "hacker culture" than by sober assessments of technical requirements. Nevertheless, this process has eventually produced both an industrial-strength programming languages, messy but powerful, and a technically pure dialect, small but powerful, that is suitable for use by programming-language theoreticians.We pick up where McCarthy's paper in the first HOPL conference left off. We trace the development chronologically from the era of the PDP-6, through the heyday of Interlisp and MacLisp, past the ascension and decline of special purpose Lisp machines, to the present era of standardization activities. We then examine the technical evolution of a few representative language features, including some notable successes and failures that illuminate design issues that distinguish Lisp from other programming languages. We also discuss the use of Lisp as a laboratory for designing other programming languages. We conclude with some reflections on the forces that have driven the evolution of Lisp.

References

1. {Abelson, 1985} Abelson, Harold and Sussman, Gerald Jay, with Sussman, Julie. Structure and Interpretation of Computer Programs. Cambridge, MA: MIT Press, 1985.
2. {Abrahams, 1966} Abrahams, Paul W., Barnett, Jeffrey A., Book, Erwin, Firth, Donna, Kemeny, Stanley L., Weissman, Clark, Hawkinson, Lowell, Levin, Michael I., and Saunders, Robert A. The LISP 2 programming language and system. In Proceedings of the 1966 AFIPS Fall Joint Computer Conference, vol. 29, San Francisco, CA, Nov. 1966, pp. 661--676. American Federation of Information Processing Societies. Washington, D. C.: Spartan Books, 1966.
3. {ACM AIPL, 1977} Association for Computing Machinery. Proceedings of the Artificial Intelligence and Programming Languages Conference, Rochester, NY, Aug. 1977. ACM SIGPLAN Notices, 12:8, Aug. 1977. ACM SIGART Newsletter, 64, Aug. 1977.
4. {ACM LFP, 1982} Association for Computing Machinery. Proceedings of the 1982 ACM Symposium on Lisp and Functional Programming, Pittsburgh, PA, Aug. 1982.
5. {ACM LFP, 1984} Association for Computing Machinery. Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming, Austin, Texas, Aug. 1984.
6. {ACM LFP, 1986} Association for Computing Machinery. Proceedings of the 1986 ACM Conference on Lisp and Functional Programming, Cambridge, MA, Aug. 1986.
7. {ACM LFP, 1988} Association for Computing Machinery. Proceedings of the 1988 ACM Conference on Lisp and Functional Programming, Snowbird, Utah, July 1988.
8. {ACM OOPSLA, 1986} Association for Computing Machinery. Proceedings of the ACM Conference on Objected-Oriented Programming, Systems, Languages, and Applications (OOPSLA '86), Portland, OR, Oct. 1986. ACM SIGPLAN Notices, 21:11, Nov. 1986.
9. {ACM PLDI, 1990} Association for Computing Machinery. Proceedings of the 1990 ACM SIGPLAN '90 Conference on Programming Language Design and Implementation, White Plains, NY, June 1990. ACM SIGPLAN Notices 25:6, June 1990.
10. {ACM PSDE, 1984} Association for Computing Machinery. Proceedings of the ACM SIGSOFT/SIGPLAN Symposium on Practical Software Development Environments, Pittsburgh, PA, Apr. 1984. ACM SIGPLAN Notices, 19:5, May 1984; also ACM Software Engineering Notes, 9:3, May 1984.
11. {Backus, 1978} Backus, John. Can programming be liberated from the von Neumann style? A functional style and its algebra of programs. Communications of the ACM, 21:8, Aug. 1978, pp. 613--641, 1977 ACM Turing Award Lecture.
12. {Baker, 1978} Baker, Jr., Henry B. List processing in real time on a serial computer. Communications of the ACM, 21:4, Apr. 1978, pp. 280--294.
13. {Bartley, 1986} Bartley, David H. and Jensen, John C. The implementation of PC Scheme. In {ACM LFP, 1986}, pp. 86--93.
14. {Bawden, 1988} Bawden, Alan and Rees, Jonathan. Syntactic closures. In {ACM LFP, 1988}, pp. 86--95.
15. {Berkeley, 1964} Berkeley, Edmund C., and Bobrow, Daniel G., Eds. The Programming Language LISP: Its Operation and Applications. Information International, Inc., and Cambridge, MA: MIT Press, 1964.
16. {Black, 1964} Black, Fischer. Styles of programming in LISP. In {Berkeley, 1964}, pp. 96--107.
17. {Bobrow, 1964} Bobrow, Daniel G. METEOR: A LISP interpreter for string transformations. In {Berkeley, 1964}, pp. 161--190.
18. {Bobrow, 1972} Bobrow, Robert J., Burton, Richard R., and Lewis, Daryle. 1972 Manual (An Extended Stanford LISP 1.6 System). Information and Computer Science Technical Report 21, University of California, Irvine, Irvine, CA, Oct. 1972.
19. {Bobrow, 1973} Bobrow, Daniel G. and Wegbreit, Ben. A model and stack implementation of multiple environments. Communications of the ACM, 16:10, Oct. 1973, pp. 591--603.
20. {Bobrow, 1986} Bobrow, Daniel G., Kahn, Kenneth, Kiczales, Gregor, Masinter, Larry, Stefik, Mark, and Zdybel, Frank. CommonLoops: Merging Lisp and object-oriented programming. In {ACM OOPSLA, 1986}, pp. 17--29.
21. {Boehm, 1986} Boehm, Hans-J., Cartwright, Robert, Riggle, Mark, and O'Donnell, Michael J. Exact real arithmetic: A case study in higher order programming. In {ACM LFP, 1986}, pp. 162--173.
22. {Brooks, 1982a} Brooks, Rodney A., Gabriel, Richard P., and Steele, Jr., Guy L. S-1 Common Lisp implementation. In {ACM LFP, 1982}, pp. 108--113.
23. {Brooks, 1982b} Brooks, Rodney A., Gabriel, Richard P., and Steele, Guy L., Jr. An optimizing compiler for lexically scoped LISP. In Proceedings of the 1982 Symposium on Compiler Construction, Boston, June 1982, pp. 261--275. Association for Computing Machinery. ACM SIGPLAN Notices, 17:6, June 1982.
24. {Brooks, 1984} Brooks, Rodney A. and Gabriel, Richard P. A critique of Common Lisp. In {ACM LFP, 1984}, pp. 1--8.
25. {Burke, 1983} Burke, G. S., Carrette, G. J., and Eliot, C. R. NIL Reference Manual. Report MIT/LCS/TR-311, MIT Laboratory for Computer Science, Cambridge, Massachusetts, 1983.
26. {Burstall, 1971} Burstall, R. M., Collins, J. S., and Popplestone, R. J., Eds. Programming in POP-2. Edinburgh University Press, 1971.
27. {Campbell, 1984} Campbell, J. A., Ed. Implementations of Prolog. Chichester: Ellis Horwood Limited, 1984. Also published by John Wiley & Sons, New York.
28. {Church, 1941} Church, Alonzo. The Calculi of Lambda Conversion. Annals of Mathematics Studies 6. Princeton, NJ: Princeton University Press, 1941. Reprinted by Klaus Reprint Corp., New York, 1965.
29. {Clark, 1982} Clark, K. L. and Tärnlund, S.-Å., Eds. Logic Programming. New York: Academic Press, 1982.
30. {Clinger, 1984} Clinger, William. The Scheme 311 compiler: An exercise in denotational semantics. In {ACM LFP, 1984}, pp. 356--364.
31. {Clinger, 1985a} Clinger, William, Ed. The Revised Revised Report on Scheme; or, An Uncommon Lisp. AI Memo 848, MIT Artificial Intelligence Laboratory, Cambridge, MA, Aug. 1985.
32. {Clinger, 1985b} Clinger, William, Ed. The Revised Revised Report on Scheme; or, An Uncommon Lisp. Computer Science Department Tech. Rep. 174, Indiana University, Bloomington, June 1985.
33. {Clinger, 1988} Clinger, William D., Hartheimer, Anne H., and Ost, Eric M. Implementation strategies for continuations. In {ACM LFP, 1988}, pp. 124--131.
34. {Clinger, 1990} Clinger, William D. How to read floating point numbers accurately. In {ACM PLDI, 1990}, pp. 92--101.
35. {Clinger, 1991} Clinger, William, and Rees, Jonathan. Macros that work. In Proceedings of the Eighteenth Annual ACM Symposium on Principles of Programming Languages, Orlando, Florida, January 1991, pp. 155--162. Association for Computing Machinery.
36. {CLTL1, 1984} Common Lisp: The Language. By Guy L. Steele, Jr., Scott E. Fahlman, Richard P. Gabriel, David A. Moon, and Daniel L. Weinreb. Burlington, MA: Digital Press, 1984.
37. {CLTL2, 1990} Common Lisp: The Language (Second Edition). By Guy L. Steele, Jr., Scott E. Fahlman, Richard P. Gabriel, David A. Moon, Daniel L. Weinreb, Daniel G. Bobrow, Linda G. DeMichiel, Sonya E. Keene, Gregor Kiczales, Crispin Perdue, Kent M. Pitman, Richard C. Waters, and Jon L White. Bedford, MA: Digital Press, 1990.
38. {Cohen, 1981} Cohen, Jacques. Garbage collection of linked data structures. ACM Computing Surveys, 13:3, Sept. 1981, pp. 341--367.
39. {Correll, 1979} Correll, Steven. S-1 uniprocessor architecture (SMA-4). In The S-1 Project 1979 Annual Report, Vol. I, Chap. 4. Lawrence Livermore Laboratory, Livermore, CA, 1979.
40. {Davies, 1984} Davies, J. POPLER: Implementation of a POP-2-based PLANNER. In {Campbell, 1984}, pp. 28--49.
41. {DEC, 1964} Digital Equipment Corporation, Maynard, MA. Programmed Data Processor-6 Handbook, 1964.
42. {DEC, 1969} Digital Equipment Corporation, Maynard, MA. PDP-10 Reference Handbook, 1969.
43. {DEC, 1981} Digital Equipment Corporation, Maynard, MA. VAX Architecture Handbook, 1981.
44. {de Kleer, 1978a} de Kleer, Johan, Doyle, Jon, Rich, Charles, Steele, Guy L., Jr., and Sussman, Gerald Jay. AMORD: A Deductive Procedure System. AI Memo 435, MIT Artificial Intelligence Laboratory, Cambridge, MA, Jan. 1978.
45. {de Kleer, 1978b} de Kleer, Johan, and Sussman, Gerald Jay. Propagation of Constraints Applied to Circuit Synthesis. AI Memo 485, MIT Artificial Intelligence Laboratory, Cambridge, MA, September 1978. Also in Circuit Theory and Applications, 8, 1980, pp. 127--144.
46. {Deutsch, 1964} Deutsch, L. Peter, and Berkeley, Edmund C. The LISP implementation for the PDP-1 computer. In {Berkeley, 1964}, pp. 326--375.
47. {Deutsch, 1973} Deutsch, L. Peter. A LISP machine with very compact programs. In {IJCAI, 1973}, pp. 697--703.
48. {Deutsch, 1976} Deutsch, L. Peter, and Bobrow, Daniel G. An efficient, incremental, automatic garbage collector. Communications of the ACM, 19:9, Sept. 1976, pp. 522--526.
49. {Drescher, 1987} Drescher, Gary. ObjectLISP User Manual. LMI (LISP Machine, Inc.), Cambridge, Massachusetts, 1987.
50. {Dybvig, 1986} Dybvig, R. Kent, Friedman, Daniel P., and Haynes, Christopher T. Expansion-passing style: Beyond conventional macros. In {ACM LFP, 1986}, pp. 143--150.
51. {Eastlake, 1968} Eastlake, D., Greenblatt, R., Holloway, J., Knight, T., and Nelson, S. ITS 1.5 Reference Manual. AI Memo 161, MIT Artificial Intelligence Laboratory, Cambridge, MA, June 1968. Revised as AI Memo 161A, July 1969.
52. {Eastlake, 1972} Eastlake, Donald E. ITS Status Report. AI Memo 238, MIT Artificial Intelligence Laboratory, Cambridge, MA, Apr. 1972.
53. {Fateman, 1973} Fateman, Richard J. Reply to an editorial. ACM SIGSAM Bulletin, 25, March 1973, pp. 9--11. This reports the results of a test in which a compiled MacLisp floating-point program was faster than equivalent FORTRAN code. The numerical portion of the code was identical and MacLisp used a faster subroutine-call protocol.
54. {Feldman, 1972} Feldman, J. A., Low, J. R., Swinehart, D. C., and Taylor, R. H. Recent developments in SAIL. In Proceedings of the 1972 AFIPS Fall Joint Computer Conference 41, Stanford, CA, Nov. 1972, pp. 1193--1202. American Federation of Information Processing Societies.
55. {Fessenden, 1983} Fessenden, Carol, Clinger, William, Friedman, Daniel P., and Haynes, Christopher. Scheme 311 Version 4 Reference Manual. Tech. Rep. 137, Indiana University, Feb. 1983.
56. {Foderaro, 1982} Foderaro, J. K., and Sklower, K. L. The FRANZ Lisp Manual. University of California, Berkeley, CA, Apr. 1982.
57. {Forgy, 1977} Forgy, C., and McDermott, J. OPS, a domain-independent production system language. In Proceedings of the Fifth International Joint Conference on Artificial Intelligence (IJCAI-77), Cambridge, MA, 1977, pp. 933--935. International Joint Council on Artificial Intelligence.
58. {Friedman, 1975} Friedman, Daniel P., and Wise, David S. CONS Should Not Evaluate Its Arguments. Tech. Rep. 44, Indiana University, Nov. 1975.
59. {Friedman, 1987} Friedman, Daniel P., and Felleisen, Matthias. The Little LISPer. Trade edition. Cambridge, MA: MIT Press, 1987. Also published by Science Research Associates, Chicago, 3rd ed., 1989.
60. {Gabriel, 1982} Gabriel, Richard P. and Masinter, Larry M. Performance of Lisp systems. In {ACM LFP, 1982}, pp. 123--142.
61. {Gabriel, 1984a} Gabriel, Richard P. and Frost, Martin E. A programming environment for a timeshared system. In {ACM PSDE, 1984}, pp. 185--192.
62. {Gabriel, 1984b} Gabriel, Richard P. and McCarthy, John. Queue-based multiprocessing Lisp. In {ACM LFP, 1984}, pp. 25--44.
63. {Gabriel, 1985} Gabriel, Richard P. Performance and Evaluation of Lisp Systems. Cambridge, MA: MIT Press, 1985.
64. {Gabriel, 1988} Gabriel, Richard P. and Pitman, Kent M. Technical issues of separation in function cells and value cells. Lisp and Symbolic Computation, 1:1, June 1988, pp. 81--101.
65. {Gabriel, 1992} Gabriel, Richard P. Personal communication to Guy L. Steele, Jr., Nov. 30, 1992 (two hours before handing off this manuscript to Federal Express).
66. {Galley, 1975} Galley, S. W. and Pfister, Greg. The MDL Language. Programming Technology Division Document SYS.11.01, MIT Project MAC, Cambridge, MA, Nov. 1975.
67. {Geschke, 1977} Geschke, Charles M., Morris, Jr., James H., and Satterthwaite, Edwin H. Early experience with Mesa. Communications of the ACM, 20:8, Aug. 1977, pp. 540--553.
68. {Golden, 1970} Golden, Jeffrey P. A User's Guide to the A. I. Group LISCOM Lisp Compiler: Interim Report. AI Memo 210, MIT Project MAC, Cambridge, MA, Dec. 1970.
69. {Goldman, 1988} Goldman, Ron and Gabriel, Richard P. Preliminary results with the initial implementation of Qlisp. In {ACM LFP, 1988}, pp. 143--152.
70. {Greenblatt, 1974} Greenblatt, Richard. The LISP Machine. Working Paper 79, MIT Artificial Intelligence Laboratory, Cambridge, MA, Nov. 1974.
71. {Greussay, 1977} Greussay, P. Contribution à la définition interprétive et à l'implémentation des lambda-langages. Thèse d' Etat, Université de Paris VI, Nov. 1977.
72. {Gries, 1977} Gries, David. An exercise in proving parallel programs correct. Communications of the ACM, 20:12, Dec. 1977, pp. 921--930.
73. {Griss, 1981} Griss, Martin L. and Hearn, Anthony C. A portable LISP compiler. Software Practice and Experience, 11, 1981, pp. 541--605.
74. {Griss, 1982} Griss, Martin L., Benson, Eric, and Maguire, Gerald Q., Jr. PSL: A portable LISP system. In {ACM LFP, 1982}, pp. 88--97.
75. {Guzman, 1966} Guzman, Adolfo and McIntosh, Harold V. CONVERT. AI Memo 99, MIT Project MAC, Cambridge, MA, June 1966.
76. {Hailpern, 1979} Hailpern, Brent T. and Hitson, Bruce L. S-1 Architecture Manual. Tech. Rep. 161 (STAN-CS-79-715), Department of Electrical Engineering, Stanford University, Stanford, California, Jan. 1979.
77. {Halstead, 1984} Halstead, Robert H., Jr., Implementation of Halstead, 1985: Lisp on a multiprocessor. In {ACM LFP, 1984}, pp. 9--17.
78. {Halstead, 1985} Halstead, Robert H., Jr., Multilisp: A language for concurrent symbolic computation. ACM Transactions on Programming Languages and Systems, 7:4, Oct. 1985, pp. 501--538.
79. {Harbison, 1991} Harbison, Samuel P. and Steele, Jr., Guy L. C: A Reference Manual. 3rd ed., Englewood Cliffs, NJ: Prentice-Hall, 1991.
80. {Hart, 1963} Hart, Timothy P. MACRO Definitions for LISP. AI Memo 57. MIT Artificial Intelligence Project---RLE and MIT Computation Center, Cambridge, MA, Oct. 1963.
81. {Hart, 1964} Hart, Timothy P. and Evans, Thomas G. Notes on implementing LISP for the M-460 computer In {Berkeley, 1964}, pp. 191--203.
82. {Hearn, 1971} Hearn, A. C. REDUCE 2: A system and language for algebraic manipulation. In Proceedings of the Second Symposium on Symbolic and Algebraic Manipulation, Los Angeles, Mar. 1971, pp. 128--133.
83. {Henneman, 1964} Henneman, William. An auxiliary language for more natural expression---The A-language. In {Berkeley, 1964}, pp. 239--248.
84. {Hewitt, 1969} Hewitt, Carl. PLANNER: A language for proving theorems in robots. In Proceedings of the {First} International Joint Conference on Artificial Intelligence (IJCAI), Washington, DC, May 1969, pp. 295--301. International Joint Council on Artificial Intelligence.
85. {Hewitt, 1972} Hewitt, Carl. Description and Theoretical Analysis (Using Schemata) of PLANNER: A Language for Proving Theorems and Manipulating Models in a Robot. MIT, Cambridge, MA, Apr. 1972. MIT Artificial Intelligence Laboratory TR-258. Ph.D. thesis.
86. {Hewitt, 1975} Hewitt, Carl. How to use what you know. In Proceedings of the Fourth International Joint Conference on Artificial Intelligence, vol. 1, pp. 189--198, Tbilisi, Georgia, USSR, Sept. 1975. International Joint Council on Artificial Intelligence. Originally circulated as Working Paper 93, MIT Artificial Intelligence Laboratory, Cambridge, MA, May 1975.
87. {Hewitt, 1991} Hewitt, Carl and Inman, Jeff. DAI betwixt and between: From "intelligent agents" to open systems science. IEEE Transactions on Systems, Man, and Cybernetics, 21:6, Nov./Dec. 1991, pp. 1409--1419.
88. {Hieb, 1990} Hieb, Robert, R., Dybvig, Kent, and Bruggeman, Carl. Representing control in the presence of first-class continuations. In {ACM PLDI, 1990}, pp. 66--77.
89. {IEEE, 1985} IEEE, New York. IEEE Standard for Binary Floating-Point Arithmetic, ANSI/IEEE STD 754--1985, 1985. An American National Standard.
90. {IEEE, 1991} IEEE Computer Society, New York. IEEE Standard for the Scheme Programming Language, IEEE STD 1178--1990, 1991.
91. {IJCAI, 1973} International Joint Council on Artificial Intelligence. Proceedings of the Third International Joint Conference on Artificial Intelligence (IJCAI3), Stanford, CA, Aug. 1973.
92. {Iverson, 1962} Iverson, Kenneth E. A Programming Language. New York: Wiley, 1962.
93. {Jensen, 1974} Jensen, Kathleen, and Wirth, Niklaus. Pascal User Manual and Report. New York: Springer-Verlag, 1974.
94. {Kahn, 1984} Kahn, K. M., and Carlsson, M. How to implement Prolog on a LISP machine. In {Campbell, 1984}, pp. 117--134.
95. {Kempf, 1987} Kempf, James, Harris, Warren, D'Souza, Roy, and Snyder, Alan. Experience with CommonLoops. In Proceedings of the ACM Conference on Objected-Oriented Programming Systems, Languages, and Applications (OOPSLA '87), Orlando, FL, Oct. 1987, pp. 214--226. Association for Computing Machinery. ACM SIGPLAN Notices, 22:12, Dec. 1987.
96. {Kernighan, 1978} Kernighan, Brian W. and Ritchie, Dennis. The C Programming Language. Englewood Cliffs, NJ: Prentice-Hall, 1978.
97. {Knuth, 1969} Knuth, Donald E. Seminumerical Algorithms, Vol. 2 of The Art of Computer Programming. Reading, MA: Addison-Wesley, 1969.
98. {Knuth, 1974} Knuth, Donald E. Structured programming with GO TO statements. Computing Surveys, 6:4, Dec. 1974, pp. 261--301.
99. {Knuth, 1981} Knuth, Donald E. Seminumerical Algorithms (Second ed.), Vol. 2 of The Art of Computer Programming. Reading, MA: Addison-Wesley, 1981.
100. {Knuth, 1986} Knuth, Donald E. The METAFONT Book, volume C of Computers and Typesetting. Reading, MA: Addison-Wesley, 1986.
101. {Kohlbecker, 1986a} Kohlbecker, Eugene, Friedman, Daniel P., Felleisen, Matthias, and Duba, Bruce. Hygienic macro expansion. In {ACM LFP, 1986}, pp. 151--161.
102. {Kohlbecker, 1986b} Kohlbecker, Eugene E., Jr., Syntactic Extensions in the Programming Language Lisp. Tech. Rep. 109, Indiana University, Aug. 1986. Ph.D. thesis.
103. {Komorowski, 1982} Komorowski, H. J. QLOG: The programming environment for PROLOG in LISP. In {Clark, 1982}, pp. 315--322.
104. {Kranz, 1986} Kranz, David, Richard Kelsey, Rees, Jonathan, Hudak, Paul, Philbin, James, and Adams, Norman. ORBIT: An optimizing compiler for Scheme. In Proceedings of the 1986 ACM SIGPLAN '86 Symposium on Compiler Construction, Palo Alto, CA, June 1986. Association for Computing Machinery. ACM SIGPLAN Notices, 21:7, July 1986, pp. 219--233.
105. {Landin, 1964} Landin, Peter J. The mechanical evaluation of expressions. Computer Journal, 6:4, 1964.
106. {Landin, 1965} Landin, Peter J. A correspondence between ALGOL 60 and Church's lambda-notation. Communications of the ACM, 8:2--3, Feb.--Mar. 1965.
107. {Lisp Archive} LISP ARCHIV. On-line archive of MacLisp release notes, 1969--1981, with entries by Jon L White, Guy L. Steele Jr., Howard I. Cannon, Richard P. Gabriel, Richard M. Stallman, Eric C. Rosen, Richard Greenblatt, and Robert W. Kerns.
108. {Lisp Conference, 1980} Conference Record of the 1980 LISP Conference, Stanford, CA, Aug. 1980. Republished by Association for Computing Machinery.
109. {Malachi, 1984} Malachi, Yonathan, Manna, Zohar, and Waldinger, Richard. TABLOG: The deductive-tableau programming language. In {ACM LFP, 1984}, pp. 323--330.
110. {Marti, 1979} Marti, J., A. C. Hearn, Griss, M. L., and Griss, C. Standard Lisp report. ACM SIGPLAN Notices, 14:10, Oct. 1979, pp. 48--68.
111. {Mathlab Group, 1977} Mathlab Group, The. MACSYMA Reference Manual (Version Nine). MIT Laboratory for Computer Science, Cambridge, MA, 1977.
112. {McAllester, 1978} McAllester, David A. A Three Valued Truth Maintenance System. AI Memo 473, MIT Artificial Intelligence Laboratory, Cambridge, MA, May 1978.
113. {McCarthy, 1962} McCarthy, John, Abrahams, Paul W., Edwards, Daniel J., Hart, Timothy P., and Levin, Michael I. LISP 1.5 Programmer's Manual. Cambridge, MA: MIT Press, 1962.
114. {McCarthy, 1980} McCarthy, John. Lisp: Notes on its past and future. In {Lisp Conference, 1980}, pp. v--viii.
115. {McCarthy, 1981} McCarthy, John. History of LISP. In Wexelblat, Richard L., Ed., History of Programming Languages, ACM Monograph Series, Chapter IV, pp. 173--197. New York: Academic Press, 1981. (Final published version of the Proceedings of the ACM SIGPLAN History of Programming Languages Conference, Los Angeles, CA, June 1978.)
116. {McDermott, 1974} McDermott, Drew V., and Sussman, Gerald Jay. The CONNIVER Reference Manual. AI Memo 295a, MIT Artificial Intelligence Laboratory, Cambridge, MA, Jan. 1974.
117. {McDermott, 1977} McDermott, Drew V. Oral remark at the ACM Symposium on Artificial Intelligence and Programming Languages, Rochester, NY, Aug. 1977, as recollected by Guy L. Steele, Jr.
118. {McDermott, 1980} McDermott, Drew. An efficient environment allocation scheme in an interpreter for a lexically-scoped LISP. In {Lisp Conference, 1980}, pp. 154--162.
119. {Mellish, 1984} Mellish, C. and Hardy, S. Integrating Prolog in the POPLOG environment. In {Campbell, 1984}, pp. 147--162.
120. {Miller, 1987} Miller, James Slocum. MultiScheme: A Parallel Processing System Mased on MIT Scheme. Ph.D. thesis, MIT, Cambridge, MA, Aug. 1987.
121. {MIT RLE, 1962a} MIT Research Laboratory of Electronics. Cambridge, MA: MIT Press. COMIT Programmers Reference Manual, June 1962.
122. {MIT RLE, 1962b} MIT Research Laboratory of Electronics. Cambridge, MA: MIT Press. An Introduction to COMIT Programming, June 1962.
123. {Moon, 1974} Moon, David A. MacLISP Reference Manual. MIT Project MAC, Cambridge, MA, Apr. 1974.
124. {Moon, 1984} Moon, David A. Garbage collection in a large Lisp system. In {ACM LFP, 1984}, pp. 235--246.
125. {Moon, 1986} Moon, David A. Object-oriented programming with flavors. In {ACM OOPSLA, 1986}, pp. 1--8.
126. {Moore, 1976} Moore, J. Strother, II. The InterLISP Virtual Machine Specification. Tech. Rep. CSL 76-5, Xerox Palo Alto Research Center, Palo Alto, California, Sept. 1976.
127. {Moses, 1970} Moses, Joel. The Function of FUNCTION in LISP. AI Memo 199, MIT Artificial Intelligence Laboratory, Cambridge, MA, June 1970.
128. {Moses, 1978?} Moses, Joel, as recalled (and probably paraphrased) by Guy L. Steele, Jr. There has been a persistent confusion in the literature about this remark. Some have reported that Moses said it while on a panel at the ACM APL 79 Conference. Moses denies having ever made that particular remark, however, and indeed Steele has heard him deny it. Steele, however, is equally certain that Moses did make such a remark---not at the APL conference, but while standing in the doorway of Steele and White's office, MIT room number NE43-834, circa 1978. Jon L White {personal communication to Steele, November 30, 1992} independently recalls having heard Moses comparing APL to a diamond and Lisp to a ball of mud on at least three separate occasions in that office building, once in NE43-834. The confusion will undoubtedly persist.
129. {Naur, 1963} Naur, Peter, Ed., et al. Revised report on the algorithmic language ALGOL 60. Communications of the ACM, 6:1, Jan. 1963, pp. 1--20.
130. {Okuno, 1984} Okuno, Hiroshi G., Takeuchi, Ikuo, Osato, Nobuyasu, Hibino, Yasushi, and Watanabe, Kazufumi. TAO: A fast interpreter-centered Lisp system on Lisp machine ELIS. In {ACM LFP, 1984}, pp. 140--149.
131. {Organick, 1972} Organick, Elliot I. The Multics System: An Examination of Its Structure. Cambridge, MA: MIT Press, 1972.
132. {Padget, 1986} Padget, Julian, et al. Desiderata for the standardisation of Lisp. In {ACM LFP, 1986}, pp. 54--66.
133. {PDP-6 Lisp, 1967} PDP-6 LISP (LISP 1.6). AI Memo 116, MIT Project MAC, Cambridge, MA, Jan. 1967. Revised as Memo 116A, April 1967. The report does not bear the author's name, but Jeffrey P. Golden {Golden, 1970} attributes it to Jon L White.
134. {Pitman, 1980} Pitman, Kent M. Special forms in Lisp. In {Lisp Conference, 1980}, pp. 179--187.
135. {Pitman, 1983} Pitman, Kent M. The Revised MacLISP Manual. MIT/LCS/TR 295, MIT Laboratory for Computer Science, Cambridge, MA, May 1983.
136. {Pratt, 1973} Pratt, Vaughan R. Top down operator precedence. In Proceedings of the ACM Symposium on Principles of Programming Languages, Boston, Oct. 1973, pp. 41--51. Association for Computing Machinery.
137. {Pratt, 1976} Pratt, Vaughan R. CGOL: An Alternative External Representation for LISP Users. AI Working Paper 121, MIT Artificial Intelligence Laboratory, Cambridge, MA, Mar. 1976.
138. {Quam, 1972} Quam, Lynn H., and Diffie, Whitfield. Stanford LISP 1.6 Manual. SAIL Operating Note 28.6, Stanford Artificial Intelligence Laboratory, Stanford, CA, 1972.
139. {Raymond, 1991} Raymond, Eric, Ed. The New Hacker's Dictionary. Cambridge, MA: MIT Press, 1991.
140. {Rees, 1982} Rees, Jonathan A. and Adams, Norman I., IV, T: A dialect of Lisp; or, LAMBDA: The ultimate software tool. In {ACM LFP, 1982}, pp. 114--122.
141. {Rees, 1986} Rees, Jonathan, Clinger, William, et al. The revised3 report on the algorithmic language Scheme. ACM SIGPLAN Notices, 21:12, Dec. 1986, pp. 37--79.
142. {Reynolds, 1972} Reynolds, John C. Definitional interpreters for higher order programming languages. In Proceedings of the ACM National Conference, Boston, Aug. 1972, pp. 717--740. Association for Computing Machinery.
143. {Robinson, 1982} Robinson, J. A. and Sibert, E. E. LOGLISP: Motivation, design, and implementation. In {Clark, 1982}, pp. 299--313.
144. {Roylance, 1988} Roylance, Gerald. Expressing mathematical subroutines constructively. In {ACM LFP, 1988}, pp. 8--13.
145. {Rudloe, 1962} Rudloe, H. Tape Editor. Program Write-up BBN-101, Cambridge, MA: Bolt Beranek and Newman Inc., Jan. 1962.
146. {Sabot, 1988} Sabot, Gary W. The Paralation Model: Architecture-Independent Parallel Programming. Cambridge, MA: MIT Press, 1988.
147. {Sammet, 1969} Jean E. Sammet. Programming Languages: History and Fundamentals. Englewood Cliffs, NJ: Prentice-Hall, 1969.
148. {Saunders, 1964a} Saunders, Robert A. The LISP listing for the Q-32 compiler, and some samples. In {Berkeley, 1964}, pp. 290--317.
149. {Saunders, 1964b} Saunders, Robert A. The LISP system for the Q-32 computer. In {Berkeley, 1964}, pp. 220--238.
150. {Shaw, 1981} Shaw, Mary, Wulf, William A., and London, Ralph L. Abstraction and verification in Alphard: Iteration and generators. In Mary Shaw, Ed., ALPHARD: Form and Content, Chapter 3, pp. 73--116. New York: Springer-Verlag, 1981.
151. {Smith, 1970} Smith, David Canfield. MLISP. Technical Report AIM-135, Stanford Artificial Intelligence Project, Oct. 1970.
152. {Smith, 1973} Smith, David Canfield and Enea, Horace J. Backtracking in MLISP2: An efficient backtracking method for LISP. In {IJCAI, 1973}, pp. 677--685.
153. {Smith, 1975} Smith, Brian C. and Hewitt, Carl. A PLASMA Primer. Working Paper 92, MIT Artificial Intelligence Laboratory, Cambridge, MA, Oct. 1975.
154. {Sobalvarro, 1988} Sobalvarro, Patrick G. A Lifetime-based Garbage Collector for LISP Systems on General-Purpose Computers. Bachelor's Thesis, MIT, Cambridge, MA, Sept. 1988.
155. {Stallman, 1976} Stallman, Richard M. and Sussman, Gerald Jay. Forward Reasoning and Dependency-Directed Backtracking in a System for Computer-Aided Circuit Analysis. AI Memo 380, MIT Artificial Intelligence Laboratory, Cambridge, MA, Sept. 1976. Also in Artificial Intelligence, 9, 1977, pp. 135--196.
156. {Steele, 1975} Steele, Guy Lewis, Jr. Multiprocessing compactifying garbage collection. Communications of the ACM, 18:9, Sept. 1975, pp. 495--508.
157. {Steele, 1976a} Steele, Guy Lewis, Jr., and Sussman, Gerald Jay. LAMBDA: The Ultimate Imperative. AI Memo 353, MIT Artificial Intelligence Laboratory, Cambridge, MA, Mar. 1976.
158. {Steele, 1976b} Steele, Guy Lewis, Jr. LAMBDA: The Ultimate Declarative. AI Memo 379. MIT Artificial Intelligence Laboratory, Cambridge, MA, Nov. 1976.
159. {Steele, 1977a} Steele, Guy Lewis, Jr. Compiler Optimization Based on Viewing LAMBDA as Rename plus Goto. Master's thesis, MIT, May 1977. Published as {Steele, 1978a}.
160. {Steele, 1977b} Steele, Guy Lewis, Jr. Data representations in PDP-10 MacLISP. In Proceedings of the 1977 MACSYMA Users' Conference, Washington, DC, July 1977, pp. 203--214. NASA Scientific and Technical Information Office. Also published as AI Memo 420, MIT Artificial Intelligence Laboratory, Cambridge, MA, Sept. 1977.
161. {Steele, 1977c} Steele, Guy Lewis, Jr. Fast arithmetic in Maclisp. In Proceedings of the 1977 MACSYMA Users' Conference, Washington, DC, July 1977, pp. 215--224. NASA Scientific and Technical Information Office. Also published as AI Memo 421, MIT Artificial Intelligence Laboratory, Cambridge, MA, Sept. 1977.
162. {Steele, 1977d} Steele, Guy L., Jr. Macaroni is better than spaghetti. In {ACM AIPL, 1977}, pp. 60--66.
163. {Steele, 1977c} Steele, Guy Lewis, Jr. Debunking the 'expensive procedure call' myth; or, Procedure call implementations considered harmful; or, LAMBDA: The ultimate GOTO. In Proceedings of the ACM National Conference, Seattle, Oct. 1977, pp. 153--162. Association for Computing Machinery. Revised version published as AI Memo 443, MIT Artificial Intelligence Laboratory, Cambridge, MA, Oct. 1977.
164. {Steele, 1978a} Steele, Guy Lewis, Jr. A Compiler for SCHEME (A Study in Compiler Optimization). Tech. Rep. 474, MIT Artificial Intelligence Laboratory, May 1978. This is a revised version of the author's master's thesis {Steele, 1977a}.
165. {Steele, 1978b} Steele, Guy Lewis, Jr., and Sussman, Gerald Jay. The Art of the Interpreter; or, The Modularity Complex (Parts Zero, One, and Two). AI Memo 453, MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, May 1978.
166. {Steele, 1978c} Steele, Guy Lewis, Jr. and Sussman, Gerald Jay. The Revised Report on SCHEME: A Dialect of LISP. AI Memo 452, MIT Artificial Intelligence Laboratory, Cambridge, MA, Jan. 1978.
167. {Steele, 1979} Steele, Guy Lewis, Jr. and Sussman, Gerald Jay. Constraints. In Proceedings of the APL 79 Conference, Rochester, NY, June 1979, pp. 208--225. Association for Computing Machinery. APL Quote Quad, 9:4, June 1979. Also published as AI Memo 502, MIT Artificial Intelligence Laboratory, Cambridge, MA, Nov. 1978.
168. {Steele, 1980} Steele, Guy Lewis, Jr. and Sussman, Gerald Jay. The dream of a lifetime: A lazy variable extent mechanism. In {Lisp Conference, 1980}, pp. 163--172.
169. {Steele, 1982} Steele, Guy L., Jr. An overview of Common Lisp. In {ACM LFP, 1982}, pp. 98--107.
170. {Steele, 1986} Steele, Guy L., Jr. and Hillis, W. Daniel. Connection Machine Lisp: Fine-grained parallel symbolic processing. In {ACM LFP, 1986}, pp. 279--297.
171. {Steele, 1990a} Steele, Guy L., Jr. Making asynchronous parallelism safe for the world. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, San Francisco, Jan. 1990, pp. 218--231. Association for Computing Machinery.
172. {Steele, 1990b} Steele, Guy L., Jr. and White, Jon L. How to print floating-point numbers accurately. In {ACM PLDI, 1990}, pp. 112--126.
173. {Sussman, 1971} Sussman, Gerald Jay, Winograd, Terry, and Charniak, Eugene. Micro-PLANNER Reference Manual. AI Memo 203A, MIT Artificial Intelligence Laboratory, Cambridge, MA, Dec. 1971.
174. {Sussman, 1972a} Sussman, Gerald Jay and McDermott, Drew Vincent. From PLANNER to McDermott, 1974---A genetic approach. In Proceedings of the 1972 Fall Joint Computer Conference, Montvale, NJ, Aug. 1972, pp. 1171--1179. AFIPS Press. This is the published version of {Sussman, 1972b}.
175. {Sussman, 1972b} Sussman, Gerald Jay and McDermott, Drew Vincent. Why Conniving is Better than Planning. AI Memo 255A, MIT Artificial Intelligence Laboratory, Cambridge, MA, April 1972.
176. {Sussman, 1975a} Sussman, Gerald Jay and Stallman, Richard M. Heuristic Techniques in Computer-Aided Circuit Analysis. AI Memo 328, MIT Artificial Intelligence Laboratory, Cambridge, MA, Mar. 1975.
177. {Sussman, 1975b} Sussman, Gerald Jay and Steele, Guy Lewis, Jr., SCHEME: An Interpreter for Extended Lambda Calculus. AI Memo 349, MIT Artificial Intelligence Laboratory, Cambridge, MA, Dec. 1975.
178. {Sussman, 1988} Sussman, Gerald Jay and Halfant, Matthew. Abstraction in numerical methods. In {ACM LFP, 1988}, pp. 1--7.
179. {Swanson, 1988} Swanson, Mark R., Kessler, Robert R., and Lindstrom, Gary. An implementation of Portable Standard Lisp on the BBN Butterfly. In {ACM LFP, 1988}, pp. 132--142.
180. {Swinehart, 1972} Swinehart, D. C. and Sproull, R. F. SAIL. SAIL Operating Note 57.2, Stanford Artificial Intelligence Laboratory, Stanford, CA, 1972.
181. {Symbolics, 1985} Symbolics, Inc., Cambridge, MA. Reference Guide to Symbolics-Lisp, Mar. 1985.
182. {Takeuchi, 1983} Takeuchi, Ikuo, Okuno, Hirochi, and Ohsato, Nobuyasu. TAO: A harmonic mean of Lisp, Prolog, and Smalltalk. ACM SIGPLAN Notices, 18:7, July 1983, pp. 65--74.
183. {Teitelman, 1966} Teitelman, Warren. PILOT: A Step toward Man-Computer Symbiosis. Tech. Rep. MAC-TR-32, MIT Project MAC, Sept. 1966. Ph.D. thesis.
184. {Teitelman, 1971} Teitelman, W., Bobrow, D. G., Hartley, A. K., and Murphy, D. L. BBN-LISP: TENEX Reference Manual. Cambridge, MA: Bolt Beranek and Newman Inc., 1971.
185. {Teitelman, 1973} Teitelman, Warren. CLISP: Conversational LISP. In {IJCAI, 1973}, pp. 686--690.
186. {Teitelman, 1974} Teitelman, Warren. et al. InterLISP Reference Manual. Xerox Palo Alto Research Center, Palo Alto, CA, 1974. First revision.
187. {Teitelman, 1978} Teitelman, Warren, et al. InterLISP Reference Manual. Xerox Palo Alto Research Center, Palo Alto, CA, Oct. 1978. Third revision.
188. {Tesler, 1973} Tesler, Lawrence G., Enea, Horace J., and Smith, David C. The LISP70 pattern matching system. In {IJCAI, 1973}, pp. 671--676.
189. {Thacker, 1982} Thacker, C. P., McCreight, E. M., Lampson, B. W., Sproull, R. F., and Boggs, D. R. Alto: A personal computer. In Siewiorek, Daniel P., C. Gordon Bell, and Allen Newell, Eds., Computer Structures: Principles and Examples, Computer Science Series, Chap. 33, pp. 549--572. New York: McGraw-Hill, 1982.
190. {Travis, 1977} Travis, Larry, Honda, Masahiro, LeBlanc, Richard, and Zeigler, Stephen. Design rationale for TELOS, a Jensen, 1974-based AI language. In {ACM AIPL, 1977}, pp. 67--76.
191. {Ungar, 1984} David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In {ACM PSDE, 1984}, pp. 157--167.
192. {Utah, 1982} Utah Symbolic Computation Group. The Portable Standard LISP Users Manual. Tech. Rep. TR-10, Department of Computer Science, University of Utah, Salt Lake City, Jan. 1982.
193. {Vuillemin, 1988} Vuillemin, Jean. Exact real computer arithmetic with continued fractions. In {ACM LFP, 1988}, pp. 14--27.
194. {Wand, 1977} Wand, Mitchell and Friedman, Daniel P. Compiling Lambda Expressions Using Continuations and Factorization. Tech. Rep. 55, Indiana University, July 1977.
195. {Waters, 1984} Waters, Richard C. Expressional loops. In Proceedings of the Eleventh Annual ACM Symposium on Principles of Programming Languages, Salt Lake City, Utah, Jan. 1984, pp. 1--10. Association for Computing Machinery.
196. {Waters, 1989a} Waters, Richard C. Optimization of Series Expressions, Part I: User's Manual for the Series Macro Package. AI Memo 1082, MIT Artificial Intelligence Laboratory, Cambridge, MA, Jan. 1989.
197. {Waters, 1989b} Waters, Richard C. Optimization of Series Expressions, Part II: Overview of the Theory and Implementation. AI Memo 1083, MIT Artificial Intelligence Laboratory, Cambridge, MA, Jan. 1989.
198. {Wegbreit, 1970} Wegbreit, Ben. Studies in Extensible Programming Languages. Ph.D. thesis, Harvard University, Cambridge, MA, 1970.
199. {Wegbreit, 1971} Wegbreit, Ben. The Wegbreit, 1974 programming system. In Proceedings of the 1971 Fall Joint Computer Conference, pp. 253--262, Montvale, NJ: AFIPS Press, Aug. 1971.
200. {Wegbreit, 1972} Wegbreit, Ben, Brosgol, Ben, Holloway, Glenn, Prenner, Charles, and Spitzen, Jay. ECL Programmer's Manual. Tech. Rep. 21--72, Harvard University Center for Research in Computing Technology, Cambridge, MA, Sept. 1972.
201. {Wegbreit, 1974} Wegbreit, Ben, Holloway, Glenn, Spitzen, Jay, and Townley, Judy. ECL Programmer's Manual. Tech. Rep. 23--74, Harvard University Center for Research in Computing Technology, Cambridge, MA, Dec. 1974.
202. {Weinreb, 1978} Weinreb, Daniel, and Moon, David. LISP Machine Manual, Preliminary Version. MIT Artificial Intelligence Laboratory, Cambridge, Massachusetts, Nov. 1978.
203. {Weinreb, 1981} Weinreb, Daniel and Moon, David. LISP Machine Manual, Third ed. MIT Artificial Intelligence Laboratory, Cambridge, MA, Mar. 1981.
204. {White, 1980} White, Jon L. Address/memory management for a gigantic LISP environment; or, GC considered harmful. In {Lisp Conference, 1980}, pp. 119--127.
205. {White, 1986} White, Jon L. Reconfigurable, retargetable bignums: A case study in efficient, portable Lisp system building. In {ACM LFP, 1986}, pp. 174--191.
206. {Wulf, 1971} Wulf, W. A., Russell, D. B., and Habermann, A. N. Bliss: A language for systems programming. Communications of the ACM, 14:12, Dec. 1971, pp. 780--790.
207. {Wulf, 1975} Wulf, William, Johnsson, Richard K., Weinstock, Charles B., Hobbs, Steven O., and Geschke, Charles M. The Design of an Optimizing Compiler, Vol. 2 of Programming Language Series. New York: American Elsevier, 1975.
208. {Yngve, 1972} Yngve, Victor H. Computer Programming with COMIT II. Cambridge, MA: MIT Press, 1972.

Index Terms

• Computer systems organization

  • Architectures

    • Other architectures

      • High-level language architectures

• Social and professional topics

  • Professional topics

    • History of computing

      • History of hardware

• Software and its engineering

  • Software notations and tools

    • Formal language definitions

      • Syntax

    • General programming languages

      • Language features

        • Procedures, functions and subroutines

      • Language types