Page Numbers: Yes X: 306 Y: 1.0" First Page: 22
Margins: Top: 1.0" Bottom: 1.3"
Heading:
des Rivìeres & SmithThe Implementation of Procedurally Reflective Languages Draft
6.Conclusions
[More weasel words needed here.
Real implementation — how does it differ from this one.]
The level-shifting implementation processor for 3-LISP that we derive is a rational reconstruction of certain mysterious aspects of several existing language implementations, providing an explanation for such assorted questions as a) a LISP system’s treatment of calls between compiled and interpreted code, b) spaghetti stacks, c) the ‘‘microcode punts’’ of INTERLISP-D, and d) SMALLTALK-80’s explicit use of the compiled code interpreter during debugging.
Acknowledgements
The authors would like to thank Austin Henderson, Mike Dixon, Greg Nuyens, and Hector Levesque for their helpful comments on an early draft. This reasearch was conducted in the Intelligent Systems Laboratory at Xerox PARC, as part of the Situated Language Program of Stanford’s Center for the Study of Language and Information.
Notes
{Note Denotational Accounts}.Exactly the same principle is employed when giving a denotational semantic account of a programming language that has assignment statements: the state of the computation that was implicit at the level of the program is made explicit at the level of the mathematical metalanguage in which the account of the language is formulated.
{Note Hardware}.In a finite tower, there is one level which is run "by the hardware", at which point there is no further program, and therefore no question of who runs it. See [Smith 82b].
{Note Kernel}.There are three classes of expressions that one might think of as the relevant base for the induction: those that are primitive, those that are simple (i.e., do not involve reflection), and those that are kernel. In 3-LISP the three classes are distinct. It is the kernel ones that are key to a correct implementation.
{Note Restartable computations}. The re-startability of a computation does not imply that external world side effects (e.g., I/O) are out of the question for a procedurally reflective system. All that would be required is for all interactions with the external world to be remembered by G. Since the restarted computation will merely retrace the steps up to the point that G detected the problem, the computation up to that point could be replayed without having to interact with the external world. (Moreover, the performance degradation would be likely to go unnoticed.)
{Note Minimal Compiled Kernel}. It is possible to design an implementation based on the absolutely minimal collection of compiled kernel procedures having precisely eight members: NORMALISE, REDUCE, and NORMALISE-RAIL and their four embedded continuations: PROC, ARGS, FIRST, and REST. (Hint: READ-NORMALISE-PRINT, LAMBDA, and IF are like the 3-tiles.)
{Note No RPLACA}.Although 3-LISP has primitive procedures that ‘‘smash’’ structures, in this paper we will pretend that there aren’t any. Without this simplifying assumption, bothersome technicalities would tend to obscure the otherwise straightforward solution. The interested reader is referred to the Interim 3-LISP Reference Manual [Smith & des Rivìeres 84] which contains a correct implementation for the unabridged language.
{Note Shift-points}.We are assuming (not unreasonably) that the point at which it is determined that D>1 is a point at which all upper levels would have been boring so far, even if they had been run explicitly. A more formal treatment would make this explicit.
References
Allen, J. Anatomy of LISP. New York: McGraw-Hill (1978).
Henderson, P. Functional Programming, Application and Implementation. Prentice-Hall, Englewood Cliffs, N.J. (1980).
McCarthy, J., et al., LISP 1.5 Programmer’s Manual. Cambridge, Mass.: The MIT Press (1965).
Muchnick, S., and Pleban, U. ‘‘A Semantic Comparison of LISP and SCHEME’’, 1980 LISP Conference, Stanford, pp. 56-64 (1980).
Smith. B. Reflection and Semantics in a Procedural Language, M.I.T. Laboratory for Computer Science Report MIT-TR-272 (1982a).
Smith, B. "The Computational Metaphor", available from the author (1982b).
Smith. B. ‘‘Reflection and Semantics in Lisp’’, 1984 ACM POPL Conference, Salt Lake City, Utah, pp. 23-35 (January 1984a).
Smith. B., and des Rivìeres, J. ‘‘Interim 3-LISP Reference Manual’’, Xerox PARC ISL Report, Palo Alto (1984, forthcoming).
Stoy, J. E., Denotational Semantics: The Scott-Strachey Approach to Programming Language Theory, Cambridge: MIT Press (1977).
Sussman, G, and Steele, G. ‘‘SCHEME: An Interpreter for Extended Lambda Calculus’’, M.I.T. Artificial Intelligence Laboratory Memo AIM-349 (1975).
Sussman, G, Holloway, J., Steele, G., and Bell, A. ‘‘SCHEME-79 − LISP on a Chip’’, IEEE Computer, pp. 10-21 (July 1981).
Steele, G., and Sussman, G. ‘‘LAMBDA: The Ultimate Imperative’’, M.I.T Artificial Intelligence Laboratory Memo AIM-353 (1976a).
Steele, G. ‘‘LAMBDA: The Ultimate Declarative’’, M.I.T. Artificial Intelligence Laboratory Memo AIM-379 (1976b).
Steele, G. ‘‘RABBIT: A Compiler for SCHEME (A Study in Compiler Optimization)’’, M.I.T. Artificial Intelligence Laboratory Technical Report AI-TR-474 (1977a).
Steele, G. ‘‘Debunking the ‘‘Expensive Procedure Call’’ Myth’’, M.I.T. Artificial Intelligence Laboratory Memo AIM-443 (1977b).
Steele, G., and Sussman, G., ‘‘The Revised Report on SCHEME, A Dialect of LISP’’, M.I.T Artificial Intelligence Laboratory Memo AIM-452 (1978a).
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).
Steele, G., and Sussman, G., ‘‘Design of a LISP-Based Microprocessor’’, CACM 23, 11, pp. 628-645 (November 1980).
9
9
9
——————————————————————————————
Reflective processor program running at level 3.
——————————————————————————————
Reflective processor program running at level 2.
——————————————————————————————
Reflective processor program running at level 1.
——————————————————————————————
User program running at level 0.
——————————————————————————————
FIGURE 1. The numbering of processing level in a reflective tower.
——————————————————————————————
Implementation processor G running at level n.
——————————————————————————————
Reflective processor program with D=1 running at level n-1.
——————————————————————————————
9
9
9
——————————————————————————————
Reflective processor program with D=n-3 running at level 3.
——————————————————————————————
Reflective processor program with D=n-2 running at level 2.
——————————————————————————————
Reflective processor program with D=n-1 running at level 1.
——————————————————————————————
User program with D=n running at level 0.
——————————————————————————————
FIGURE 2. How to run a D=n program with a black-box
processor that can only handle D=1 programs.