Reflective programming languages have existed since the seminal work of Smith in the early eighties, yet the area lacks a widely accepted account of what is reflection and what are reflective languages. Some confusion arises because reflective properties already appear in several existing languages. In this section, we establish our terminolgy for the basic concepts used throughout this paper. Because we are particularly interested in the efficient implementation of reflective programming languages in the large, our definitions are biased towards a better understanding of implementation issues (a companion paper [DM95] provides an historical and comparative overview of reflective concepts and languages), beginning with the following basics about programming languages.
The effective computation is obtained by translating the program to a suitable low-level sequence of actions to be executed on a computer in conjunction with the language run-time system. When the translation is done on-line, expression by expression, and interleaved with the actual computation, the implementation is said to be an interpreter for the language; when it is done off-line, all at once, usually prior to the execution, the implementation is said to be a compiler for the language.
Given these basics, an effective or operational definition of reflection in the context of programming languages might well be the following:
The word integral in the above definition is very important. We insist on it to promote the idea that true reflection imposes no limit on what the program may observe or modify. This is clearly a long term goal. There are even theoretical limits (Gödel incompleteness theorem, paradoxical situations, etc.). But for the time being, we will stick to this definition to avoid including everything in reflection, and considering all languages as reflective. We will come back to this issue shortly.
In order to observe or change something, this thing must be represented in a such a way that the user program can manipulate it. This paves the way to the notion of reification.
Reification, at least partially, has been experienced in many languages to date: in early Lisps and in current Prologs, programs have been treated as data, although the causal connection has often been left to the responsability of the programmer. In Smalltalk-80, the compiler from the source text to bytecode has been part of the run-time system since the very first implementations of the language. Several other examples exist.
Notice the importance of the capability for the program to handle the reification data. This is in contrast with higher order languages for example, in which entities that were implicit are given a first-class status. First-class entites need only be denotable and used as any other primitive data types of the language: they may be passed as parameters, returned as results, assigned to variables. This is the case of functions and continuations in Scheme for example. But they need not be represented by data structures that can be inspected.
Most of the difficulties in giving a precise definition of what is reflection and what it is not stems from the fact that several existing languages exhibit some reflective behavior or provide reflective mechanisms, a notion that we define as follows:
It is difficult to draw a precise and tight frontier between what is considered as a few appearances of reflective mechanisms and full reflection. Indeed, the above definition is very general. It aims at gathering all expressions of reflective behavior or reflective properties in existing languages and systems. Our goal in introducing these distinctions is both to contrast selective expression of reflective properties from true (fully) reflective languages. On the other hand, we want to reuse the know-how developed around these mechanisms in existing languages and systems. For example, reification of program code has been done in several languages, but this does not mean that these languages were reflective. On the other hand, because reflection needs reified programs, the technology developed in Lisp, Prolog, Smalltalk and other languages is readily available for reflective languages.
Some reflective mechanisms are now pretty well-understood and their efficient implementation is also well-documented: the aforementioned programs reified as data 3, representation of program entities at run-time, for example using classes and metaclasses as first-class entites in object-oriented programming, etc. We will see later on that a lot of existing techniques provide a very helpful basis for the efficient implementation of reflective languages. In fact, the observation that the well-mastered cases lie much more in the static representation of programs side of reflection lead naturally to a distinction between structural and behavioral reflection.
Pionnered by Smith [Smi82,Smi84], behavioral reflection has proved, as we noted before, to be much more difficult to implement efficiently than structural reflection. This is essentially because it raises crucial issues related to the execution of programs. First of all, behavioral reflection complicates the run-time model of the language by introducing reflective towers, as we will see shortly. When efficiency, and therefore compiling, come into play, the following questions are raised: