A semantic comparison of LISP and SCHEME

ABSTRACT

We review the features of some of the major dialects of LISP, show how they are reflected in denotational treatments of their semantics and draw a series of conclusions concerning semantic design of languages, program proving and optimization. We concentrate our attention on four dialects: (1) LISP 1.0 - approximating McCarthy's original design, (2) Modern LISP - approximating the major features of most current systems, (3) Funarg LISP - Modern LISP with upward and downward functional arguments, and (4) SCHEME - Steele and Sussman's lexically scoped dialect. LISP 1.0 and SCHEME are semantically tractable. In both cases it is possible to write a denotational semantics which exactly specifies the types of semantic objects being manipulated and the meaning of each valid syntactic construct. For modern LISP and Funarg LISP, on the other hand, we show that it is not possible to give a semantics which fully specifies the language and satisfies all the tenets of denotational semantics. However, we give a definition which rests on the foundational underpinnings of denotational semantics, thus guaranteeing that our semantic objects exist, and violates only the structural definition principle: that the meaning of a construct be defined in terms of the meanings of its parts. This has far-reaching significance for program proving, optimization and comprehensibility of programs.

REFERENCES

• 1: Robert S. Boyer , J. Strother Moore, Proving Theorems about LISP Functions, Journal of the ACM (JACM), v.22 n.1, p.129-144, Jan. 1975 [doi>10.1145/321864.321875]
• 2: Johan de Kleer , Jon Doyle , Guy L. Steele, Jr. , Gerald Jay Sussman, AMORD explicit control of reasoning, Proceedings of the 1977 symposium on Artificial intelligence and programming languages, p.116-125, August 15-17, 1977
• 3: Michael J. C. Gordon, Operational reasoning and denotational semantics., Stanford University, Stanford, CA, 1975
• 4: Michael J. C. Gordon, The Denotational Description of Programming Languages: An Introduction, Springer-Verlag New York, Inc., Secaucus, NJ, 1979
• 5: Neil D. Jones , Steven S. Muchnick, Binding time optimization in programming languages: Some thoughts toward the design of an ideal language, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.77-94, January 19-21, 1976, Atlanta, Georgia [doi>10.1145/800168.811542]
• 6: Neil D. Jones , Steven S. Muchnick, Flow analysis and optimization of LISP-like structures, Proceedings of the 6th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.244-256, January 29-31, 1979, San Antonio, Texas [doi>10.1145/567752.567776]
• 7: Jones, Neil D., Steven S. Muchnick & David A. Schmidt, A Universal Compiler: Towards a Compiler Generator Based on Denotational Semantics, Technical Report IR-17, University of Aarhus, Aarhus, Denmark, December 1979.
• 8: John McCarthy, Recursive functions of symbolic expressions and their computation by machine, Part I, Communications of the ACM, v.3 n.4, p.184-195, April 1960 [doi>10.1145/367177.367199]
• 9: McCarthy, John, Paul W. Abrahams, David J. Edwards, Timothy P. Hunt & Michael I. Levin, LISP 1.5 Programmer's Manual, 2nd ed., M.I.T. Press, Cambridge, Massachusetts, 1965.
• 10: John McCarthy, History of LISP, ACM SIGPLAN Notices, v.13 n.8, p.217-223, August 1978 [doi>10.1145/960118.808387]
• 11: Moon, David A., MACLISP Reference Manual, Revision 0, Project MAC, M.I.T., Cambridge, Massachusetts, April 1974.
• 12: Moore, J. Strother, Introducing Iteration into the Pure LISP Theorem Prover, IEEE Trans. on Software Eng., vol. SE-1, no. 3, September 1975, pp. 328-338.
• 13: Mosses, Peter D., Mathematical Semantics and Compiler Generation, Ph.D. Dissertation, University of Oxford, 1975.
• 14: Pleban, Uwe F., The Standard Semantics of a Subset of SCHEME, a Dialect of LISP, Technical Report TR-79-3, Computer Science Department, University of Kansas, Lawrence, Kansas, July 1979.
• 15: Pleban, Uwe F., A Denotational Approach to Flow Analysis and Optimization of SCHEME, a Dialect of LISP, Ph.D. Dissertation, University of Kansas, Lawrence, Kansas, to appear in 1980.
• 16: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 17: Steele, Guy L., Jr. & Gerald J. Sussman, Revised Report on SCHEME, a Dialect of LISP, Memo 452, Artificial Intelligence Laboratory, M.I.T., January 1978.
• 18: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 19: 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
• 20: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 21: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 22: Teitelman, Warren, InterLISP Reference Manual, Revised edition, Xerox Palo Alto Research Center, Palo Alto, California, 1975.
• 23: R. D. Tennent, The denotational semantics of programming languages, Communications of the ACM, v.19 n.8, p.437-453, Aug. 1976 [doi>10.1145/360303.360308]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS
      F.3.2 Semantics of Programming Languages
          Subjects: Denotational semantics

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Correctness proofs
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications

          Nouns: LISP; SCHEME

General Terms:
Languages, Verification