[phylum]<3-LISP>documentation>old-3-interim-manual-02c.bravo!1

We say that a programming language is procedurally reflective if it supports programs that are able to manipulate in a causally effective way structural descriptions of their own operations and structures. To do this, one must encode an explicit theory of such a system within the structures of the system, and then connect that theory to the fundamental operations of the system in such a way as to satisfy three essential properties. First, at any point in the course of a computation fully articulated descriptions of the state of the reasoning process must be available for inspection and modification. Second, it must be possible at any point to resume an arbitrary computation in accord with such (possibly modified) theory-relative descriptions. Third, procedures that reason with descriptions of the processor state must themselves be subject to description and review, to arbitrary depth. Such reflective abilities allow a process to shift smoothly between dealing with a given subject matter, and dealing with its own reasoning processes over that domain.

In any computational formalism in which programs are accessible as first class structural fragments, it is possible to construct what are commonly known as meta-circular interpreters: "meta" because they operate on (and therefore terms within them designate) other formal structures, and "circular" because they do not constitute a definition of the processor, for two reasons: they have to be run by that processor in order to yield any sort of behaviour (since they are programs, not processors, strictly), and the behaviour they would thereby engender can be known only if one knows beforehand what the processor does. Nonetheless, such processors are often pedagogically illuminating, and they play a critical role in the development of a reflective model. In line with our general strategy of reserving the word "interpret" for the semantical interpretation function, we will call such processors meta-circular processors (or MCP’s, for short).

The basic idea is that if the code for an MCP were processed by the primitive processor, the process that would thereby be engendered would be behaviourally equivalent to that of the primitive processor itself. If, in other words, we were to assume mathematically that processes are functions from structure onto behaviour, and if we call the meta-circular processor by the name MCP, and called the primitive processor P, then we would presumably be able to prove the following result, where by "e" we mean behaviourally equivalent (in some appropriate sense):

It should be recognised that the equivalence of which we speak here is a global equivalence; by and large the primitive processor, and the processor resulting from the explicit running of the MCP, cannot be arbitrarily mixed. For example, if a variable is bound by the underlying processor P, it will not be able to be looked up by the meta-circular code. Similarly, if the meta-circular processor encounters a control structure primitive, such as a THROW or a QUIT, it will not cause the meta-circular processor itself to exit prematurely, or to terminate. The point, rather, is that if an entire computation is mediated by the explicit processing of the MCP, then the results will be the same as if that entire computation had been carried out directly.

Given any particular MCP (we will shortly constrain this choice), we define a reflective tower based on that MCP by simply positing that the primitive processor is engendered by an infinite number of recursive instances of that MCP, each running a version one level below (and started in some initial configuration). In recognition of the special status of the MCP on which a reflective tower is based, we will call it a reflective processor. A very rough idea of the levels of reflective processors is given in the following diagram. The intent of this picture is to show how each level is processed by an active reflective processor that interacts with it (locally and serially, as usual), but how each processor is in turn composed of a structural field fragment in turn processed by a reflective processor interacting with it.

The implied infinite regress is not problematic, since only a finite amount of information is encoded in it (all but a finite number of the bottom levels each reflective processor is merely running a copy of the reflective processor). Because we (the language designers) know exactly how the language runs, and know as well what the reflective processor is like, we can provide this infinite number of levels, to use the current jargon, only virtually. As Appendix B will explain, such a simulation is in fact perfectly well-defined.

As mentioned above, not just any MCP can serve as a reflective processor. It is crucial that the MCP provide a mechanism by which the user’s program can gain access to the fully arcticulated descriptions of that program’s operations and structures. In 3-LISP, this support comes in the form of what we call reflective procedures — procedures that, when invoked, are run not at the level at which the invocation occured, but one level higher, at the level of the reflective processor running the program, being given as arguments those expressions that would have been passed around in the reflective processor.

The reader will note that there are two ways in which we can characterise this form of reflection. On the one hand we can think of there being a primitive and noticeable reflective act, which causes the processor to shift levels rather markedly (this is the explanation that best coheres with some of the pre-theoretic intuitions about reflective thinking in the sense of contemplation). On the other hand, we have also just spoken of an infinite number of levels of reflective processors, each essentially implementing the one below, so that it is not coherent either to ask at which level the tower is running, or to ask how many reflective levels are running: in some sense they are all running at once, in exactly the same sense that both the LISP processor inside your editor, and your editor, are both running when you use that editor. In the editor case it is not, of course, as if LISP and editor were both running together, in the sense of side-by-side or independently, rather, the one, being interior to the other, in fact supplies the anima or agency of the outer one. It is just this sense in which the higher levels in our reflective hierarchy are always running: each of them is in some sense within the processor at the level below, so that it can thereby engender it.

We will not take a principled view on which account — a single locus of agency stepping between levels, or an infinite hierarchy of simultaneous processors — is correct: they turn out, rather curiously, to be behaviourally equivalent. For certain purposes one is simpler, for others the other.

To illustrate the "shifting levels" account (which is more complex than the infinite number of levels story), we present the following account of what is involved in constructing a reflective dialect, in part by way of review, and in part to suggest to the reader how it is that a reflective dialect could in fact be finitely constructed. In particular, you have to provide a complete theory of the given calculus expressed within its own language (the reflective processor — this is required on both accounts, obviously). Second, you have to arrange it so that, when the process reflects, all of the structures used by the reflective processor (the formal structures designating the theoretical entities posited by the theory) are available for inspection and manipulation, and correctly encode the state that the interpreter was in prior to the reflective jump. Third, you have to make sure that when the process decides to "drop down again", the original base-level interpretation process is resumed in accordance with the facts encoded in those structures. In the minimal case, upon reflection the processor would merely interpret the reflective processor explicitly, then at some further point would drop down and resume running non-reflectively. Such a situation, in fact, is so simple that it could not be distinguished (except perhaps in terms of elapsed time) from pure non-reflective interpretation.

The situation, however, would get more complex as soon as the user is given any power. Two provisions in particular are crucial. First, the entire purpose of a reflective dialect is to allow the user to have his or her own programs run along with, or in place of, or between the steps of, the reflective processor. We need in other words to provide an abstract machine with the ability for the programmer to insert code — in convenient ways and at convenient times — at any level of the reflective hierarchy. For example, suppose that we wish to have a l-expression closed only in the dynamic environment of its use, rather than in the lexical environment of its definition. The reflective model will of course contain code that performs the default lexical closure. The programmer can assume that the reflective code is being explicitly interpreted, and can provide, for the lambda expression in question, an alternate piece of code in which different action is taken. By simply inserting this code into the correct level, (s)he can use variables bound by the reflective model in order to fit gracefully into the overall regime. Appropriate hooks and protocols for such insertion, of course, have to be provided, but they have to be provided only once. Furthermore, the reflective processor will contain code showing how this hook is normally treated.

As well as providing for the arbitrary interpretation of special programs, at the reflective level, we need in addition to enable the user to modify the explicitly available structures that were provided by the reflective model. Though this ability is easier to design than the former, its correct implementation is considerably trickier. An example will make this clear. The 3-LISP reflective processor we will exhibit will be shown to deal explicitly with both environment and continuation structures. Upon reflecting, programs can at will access these structures that, at the base level, are purely implicit. Suppose that the user’s reflective code actually modifies the environment structure (say to change the binding of a variable in some procedure somewhere up the stack, in the way that a debugging package might support), and also changes the continuation structure (designator of the continuation function) so as to cause some function return to bypass its caller. When this reflective code "returns", so to speak, and drops back down, the interpretation process that must then take effect must be the one mandated by these modified structures, not the one that would have been resumed prior to the reflection. These modifications, in other words, must be noticed. This is the causal connection aspect of self-reference that is so crucial to true reflection.