In the programming language area, we define reflection as ``the ability of a program to manipulate as data something representing the state of the program during its own execution'' [BGW93], the mechanism for encoding execution states as data being called reification. We further categorize reflective mechanisms in two major forms: structural and behavioral reflection. The chief interest of this distinction lies in the fact that structural reflection is considered easier to implement. Indeed, languages such as Lisp, Prolog, Smalltalk, and others have included structural reflection mechanisms for a long time.
Behavioral reflection has not been so clearly tackled yet, essentially because it touches aspects governing the semantics of programs. When confronted with behavioral reflection, most language implementors adopt interpretive techniques. Interpreters ease modifications and react to them as soon as they occur, a remarkable advantage in reflection. But to improve the applicability of reflective languages, there is no way around more efficient implementations. Unfortunately, the lack of a precise understanding of the issues involved in this evolution pushes implementors to limit the reflective models. In this tutorial, we resist this temptation. We first propose a comprehensive look at these issues. Next, we suggest new avenues towards more efficient implementation techniques for full behavioral reflection.
Our approach to this problem is based on the recognition that reflection is, in fact, pursuing a long tradition in computer science [Hal93, Binding]: ``Broadly speaking, the history of software development is the history of ever late binding time ...'' Reflection pushes this idea to its limit by postponing the binding time of at least part of the language syntax, semantics and implementation as well as the program itself, to the run-time. In the extreme case, this possibility challenges our capability to efficiently implement reflective languages (i.e., compile them). But if behavioral reflection indeed includes such an extreme possibility, we claim that most of the time, typical programs will behave in such a way that most of their code can be compiled using standard techniques, or at least techniques that are within the reach of the current research on the implementation of modern dynamic programming languages.
In this sense, we consider that reflective language designers must give as much freedom as possible to programmers in terms of late-binding, but their implementors must use appropriate techniques to extract static computations from programs in order to compile and optimize them prior to run-time. To this end, we introduce the distinction between static and dynamic behavioral reflection. Coarsely speaking, static behavioral reflection is a restricted form of reflection where we statically know enough information about the reflective computations in a program to compile it.
Our goal is to precisely characterize the static case in order to enable the development of new compiler tools and techniques to tackle static reflection, even in languages allowing dynamic behavioral reflection. Reflective language designers and implementors will then face two possible paths. Indeed, one of them is to provide highly efficient languages with only static behavioral reflection. But we also propose that dynamic behavioral reflection can be introduced, at the price of dynamic compilation and cache techniques similar to the ones already developed in Smalltalk [GR83] and Self [USC+91] for example. The essential motivation behind these techniques is that changes happen infrequently enough that we can compile the code under the assumption that everything is stable, and then pay the price of dynamically recompiling part of it each time a change occurs at run-time.
In the rest of this tutorial, we first recall the basics of reflection in programming languages. In Section 3, we explore the state of the art in the implementation of behavioral reflection. In Section 4, we move on to the issues related to binding time and behavioral reflection; we introduce a crucial distinction between static and dynamic behavioral reflection. In Section 5, we propose new avenues in the implementation of reflective languages based on this distinction. We look at four problems crucial to the current research: how to compilation reflective towers, how to handle introspection and causal connection, how to take into account modifications to the semantics of the language and how to tackle dynamic behavioral reflection. We then conclude and expound some perspectives.
