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. 1.Allen, J. Anatomy of LISP. New York: McGraw-Hill (1978).
2. 2.Henderson, P. Functional Programming, Application and Implementation. Prentice-Hall, Englewood Cliffs, N.J. (1980).
3. 3.McCarthy, J., et al. LISP 1.5 Programmer's Manual. Cambridge, Mass.: The MIT Press (1965).
4. 4.Muchnick, S., and Pleban, U. "A Semantic Comparison of LISP and SCHEME", 1980 LISP Conference, Stanford, pp. 56-64 (1980).
5. 5.Smith, B. Reflection and Semantics in a Procedural Language, M.I.T. Laboratory for Computer Science Report MIT-TR-272 (1982a).
6. 6.Smith, B. "The Computational Metaphor", available from the author (1982b).
7. 7.Smith, B. "Reflection and Semantics in Lisp", 1984 ACM POPL Conference, Salt Lake City, Utah, pp. 23-35 (January 1984a).
8. 8.Smith, B., and des Rivières, J. "Interim 3-LISP Reference Manual", Xerox PARC ISL Report ISL-1, Palo Alto (1984, forthcoming).
9. 9.Stoy, J. E., Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, Cambridge: MIT Press (1977).
10. 10.Sussman, G, and Steele, G. "SCHEME: An Interpreter for Extended Lambda Calculus", M.I.T. Artificial Intelligence Laboratory Memo AIM-349 (1975).
11. 11.Sussman, G, Holloway, J., Steele, G., and Bell, A. "SCHEME-79 - LISP on a Chip", IEEE Computer, pp. 10-21 (July 1981).
12. 12.Steele, G., and Sussman, G. "LAMBDA: The Ultimate Imperative", M.I.T Artificial Intelligence Laboratory Memo AIM-353 (1976a).
13. 13.Steele, G. "LAMBDA: The Ultimate Declarative", M.I.T. Artificial Intelligence Laboratory Memo AIM-379 (1976b).
14. 14.Steele, G. "RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization)", M.I.T. Artificial Intelligence Laboratory Technical Report AI-TR-474 (1977a).
15. 15.Steele, G. "Debunking the "Expensive Procedure Call" Myth", M.I.T. Artificial Intelligence Laboratory Memo AIM-443 (1977b).
16. 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. 17.Steele, G., and Sussman, G., "The Art of the Interpreter, or, The Modularity Complex (Parts Zero, One, and Two)", M.I.T Artificial Intelligence Laboratory Memo AIM-453 (1978b).
18. 18.Steele, G., and Sussman, G., "Design of a LISP-Based Microprocessor", CACM 23, 11, pp. 628-645 (November 1980).

Index Terms

• Software and its engineering

  • Software notations and tools

    • Compilers

      • Interpreters

    • General programming languages

      • Language types

        • Functional languages