LISP and Symbolic Computation, 1(1)11-37

The Mystery of the Tower Revealed: A Nonreflective Description of the Reflective Tower

Mitchell Wand, College of Computer Science, Northeastern University, Boston, MA 02115
Daniel P. Friedman, Computer Science Department, Indiana University, Bloomington, IN 47405

Abstract: In an important series of papers [8, 9], Brian Smith has discussed the nature of programs that know about their text and the context in which they are executed. He called this kind of knowledge reflection. Smith proposed a programming language, called 3-LISP, which embodied such self-knowledge in the domain of metacircular interpreters. Every 3-LISP program is interpreted by a metacircular interpreter, also written in 3-LISP. This gives rise to a picture of an infinite tower of metacircular interpreters, each being interpreted by the one above it. Such a metaphor poses a serious challenge for conventional modes of understanding of programming languages. In our earlier work on reflection [4], we showed how a useful species of reflection could be modeled without the use of towers. In this paper, we give a semantic account of the reflective tower. This account is self-contained in the sense that it does not employ reflection to explain reflection.

[local copy]
Steel gray color with the Angel Gabriel's horn

May 2004 - hosc@brics.dk