The implementation of procedurally reflective languages

ABSTRACT

In a procedurally reflective programming language, all programs are executed not through the agency of a primitive and inaccessible interpreter, but rather by the explicit running of a program that represents that interpreter. In the corresponding virtual machine, therefore, there are an infinite number of levels at which programs are processed, all simultaneously active. It is therefore a substantial question to show whether, and why, a reflective language is computationally tractable. We answer this question by showing how to produce an efficient implementation of a procedurally reflective language, based on the notion of a level-shifting processor. A series of general techniques, which should be applicable to reflective variants of any standard applicative or imperative programming languages, are illustrated in a complete implementation for a particular reflective LISP dialect called 3-LISP.

REFERENCES

• 1: John Allen, Anatomy of LISP, McGraw-Hill, Inc., New York, NY, 1978
• 2: Peter Henderson, Functional Programming, Prentice Hall PTR, Upper Saddle River, NJ, 1980
• 3: John McCarthy, LISP 1.5 Programmer's Manual, The MIT Press, 1962
• 4: Steven S. Muchnick , Uwe F. Pleban, A semantic comparison of LISP and SCHEME, Proceedings of the 1980 ACM conference on LISP and functional programming, p.56-64, August 25-27, 1980, Stanford University, California, United States [doi>10.1145/800087.802790]
• 5: Smith, B. Reflection and Semantics in a Procedural Language, M.I.T. Laboratory for Computer Science Report MIT-TR-272 (1982a).
• 6: Smith, B. "The Computational Metaphor", available from the author (1982b).
• 7: Brian Cantwell Smith, Reflection and semantics in LISP, Proceedings of the 11th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.23-35, January 15-18, 1984, Salt Lake City, Utah, United States [doi>10.1145/800017.800513]
• 8: Smith, B., and des Rivières, J. "Interim 3-LISP Reference Manual", Xerox PARC ISL Report ISL-1, Palo Alto (1984, forthcoming).
• 9: Joseph E. Stoy, Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, MIT Press, Cambridge, MA, 1977
• 10: Gerald J. Sussman , Guy L. Steele, Jr., An Interpreter for Extended Lambda Calculus, Massachusetts Institute of Technology, Cambridge, MA, 1975
• 11: Sussman, G, Holloway, J., Steele, G., and Bell, A. "SCHEME-79 - LISP on a Chip", IEEE Computer, pp. 10-21 (July 1981).
• 12: Guy L Steele , Gerald J Sussman, Lambda: The Ultimate Imperative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 13: Guy L Steele, LAMBDA: The Ultimate Declarative, Massachusetts Institute of Technology, Cambridge, MA, 1976
• 14: Guy L. Steele, Jr., Rabbit: A Compiler for Scheme, Massachusetts Institute of Technology, Cambridge, MA, 1978
• 15: Guy L Steele, Debunking the ``Expensive Procedure Call'''' Myth or, Procedure Call Implementations Considered Harmful or, LAMDBA: The Ultimate GOTO, Massachusetts Institute of Technology, Cambridge, MA, 1977
• 16: Steele, G., and Sussman, G., "The Revised Report on SCHEME, A Dialect of LISP", M.I.T Artificial Intelligence Laboratory Memo AIM-452 (1978a).
• 17: 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
• 18: Guy Lewis Steele, Jr. , Gerald Jay Sussman, Design of a LISP-based microprocessor, Communications of the ACM, v.23 n.11, p.628-645, Nov. 1980 [doi>10.1145/359024.359031]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Applicative (functional) languages

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Interpreters

General Terms:
Languages, Performance