Intensions and extensions in a reflective tower

ABSTRACT

This article presents a model of the reflective tower based on the formal semantics of its levels. They are related extensionally by their mutual interpretation and intensionally by reification and reflection. The key points obtained here are: a formal relation between the semantic domains of each level; a formal identification of reification and reflection; the visualisation of intensional snapshots of a tower of interpreters; a formal justification and a generalization of Brown's meta-continuation; a (structural) denotational semantics for a compositional subset of the model; the distinction between making continuations jumpy and pushy; the discovery of the tail-reflection property; and a Scheme implementation of a properly tail-reflective and single-threaded reflective tower. Section 1 presents the new approach taken here: rather than implementing reification and reflection leading to a tower, we consider an infinite tower described by the semantics of each level and relate these by reification and reflection. Meta-circularity then gives sufficient conditions for implementing it. Section 2 investigates some aspects of the environments and control in a reflective tower. An analog of the funarg problem is pointed out, in relation with the correct environment at reification time. Jumpy and pushy continuations are contrasted, and the notions of ephemeral level and proper tail-reflection are introduced. Our approach is compared with related work and after a conclusion, some issues are proposed.

REFERENCES

• Danvy 87: Olivier Danvy: A ccross the Bridge between Reflection and Partial Evaluation, Proceedings of the Workshop on Partial Evaluation and Mixed Computation, Dines Bj0rner, Andrei P. Ershov and Neil D. Jones (eds.), North-Holland (to appear), GI. Avernms, Denmark (October 1987)
• Danvy & Malmkjaer 88: Olivier Danvy, Karoline Malmkj~r: A Blond Primer, draft, DIKU, University of Copenhagen, Copenhagen, Denmark (February 1988)
• des Rivières & Smith 84: Jim des Rivières , Brian Cantwell Smith, The implementation of procedurally reflective languages, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.331-347, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802050]
• des Rivières 88: Jim des Rivi~res: Control-Re&ted Meta-Levei Facilities in LISP, from Meta-Level Architectures and Reflection, Patti Maes & Daniele Nardi (ed~.), North-Holland (1988)
• Felleisen et al. 87: Matthias Felleisen, Daniel P. Friedman, Bruce F. Duba, John Merrill: Beyond Continuations, Technical Report No 216, Computer Science Department, Indiana University, Bloomington, Indiana (February 1987)
• Friedman & Wand 84: Daniel P. Friedman , Mitchell Wand, Reification: Reflection without metaphysics, Proceedings of the 1984 ACM Symposium on LISP and functional programming, p.348-355, August 06-08, 1984, Austin, Texas, United States [doi>10.1145/800055.802051]
• Jones et al. 88: Neil D. Jones, Peter Sestoft, Harald S0ndergaard: MIX: a Self-Applicable Partial Evalttator for Experiments in Compiler Generation, to appear in the International Journal LISP and Symbolic Computation, (1988)
• Moses 70: Joel Moses, The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem, Massachusetts Institute of Technology, Cambridge, MA, 1970
• Muchnick & Pleban 80: 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]
• Rees & Clinger 86: J Rees , W Clinger, Revised report on the algorithmic language scheme, ACM SIGPLAN Notices, v.21 n.12, p.37-79, Dec. 1986 [doi>10.1145/15042.15043]
• Schmidt 86: David A. Schmidt, Denotational semantics: a methodology for language development, William C. Brown Publishers, Dubuque, IA, 1986
• Smith 82: Brian C. Smith: Reflection and Semantics in a Procedural Language, Ph.D. thesis, MIT/- LCS/TR-272, Cambridge, Massachusetts (January 1982)
• Smith 84: 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]
• Steele & Sussman 78: Guy L. Steele Jr., Gerald J. Sussman: The Revised Report on SCHEME, a Dialect of LISP, MIT-AIL, AI Memo No 452, Cambridge, Massachusetts (January 1978)
• Sturdy 88: John C. G. Sturdy: Ph.D. thesis (forthcoming), University of Bath, School of Mathematical Sciences, Bath, England (1988)
• Talcott 85: Carolyn L. Talcott, The essence of rum: a theory of the intensional and extensional aspects of lisp-type computation (program transformation, closure, continuation structure, comparison-relation), 1985
• Wand & Friedman 86: Mitchell Wand , Daniel P. Friedman, The mystery of the tower revealed: a non-reflective description of the reflective tower, Proceedings of the 1986 ACM conference on LISP and functional programming, p.298-307, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319871]
• Wand, Friedman & Duba 86: Mitchell Wand, Daniel P. Friedman, Bruce F. Duba: Getting the Levels Right (Preliminary Report), Preprints of the Workshop on Meta-Level Architectures and Reflection, Patti Maes & Daniele Nardi (eds.), Alghero, Sardinia (October 1986)
• Wand & Friedman 88: Mitchell Wand, Daniel P. Friedman: The Mystery of the Tower Revealed: a Non-Reflective Description of the Reflective Tower, to appear in the International Journal LISP and Symbolic Computation (1988)

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.3 LOGICS AND MEANINGS OF PROGRAMS

General Terms:
Algorithms, Languages, Theory