The stack of meta-interpreters in a reflective tower suggests a direct implementation using interpretive techniques. With a loss of an order of magnitude in performance for each level of meta-interpretation, such a naive implementation is totally useless. Early in the development of behavioral reflection, researchers have proposed ways to avoid the levels of meta-interpretation. In fact, two main efforts have succeeded: an operational approach, with Smith's and des Rivières' level-shifting processor (LSP) [dRS84] and a formal approach, with Friedman's and Wand's meta-continuation semantics [WF88].
Both of them apply to the discrete approach and are based on the single-threadedness assumption [DM88]. This assumption says that at any time during the execution, only one of the meta-interpreters needs to be executing, namely the lowest level which runs user's code, either in the program at level 0 (i.e., the meta-interpreter of level 1) or reflective code at some level i in the tower (i.e., the meta-interpreter of level i+1). The single-threadedness assumption relies on the fact that the meta-interpreters above this lowest level need not be executed because they perform an easily predictable computation (the code is known and there is no side-effects).
We now look at 3-Lisp level-shifting processor (LSP), but similar observations can be inferred from the meta-continuation semantics. Using the single-threadedness assumption, a 3-Lisp program p is executed by starting the LSP at level 1 on p, as illustrated in Figure 3. In this figure, the horizontal axis represents the run-time while the vertical axis represents levels in the tower; solid thick lines represent the locus of the computation. The LSP at level 1 is executed by a non-reflective version of itself (the ultimate machine) at level 2 (represented by the locus of the solid narrow line). Starting in this configuration is pure speculation. We conjecture that no reflective procedure calls will be made during this run.
When a reflective procedure is invoked at time 2, this conjecture appears to be false and we must conclude that we should have started with at least two levels in the tower running the LSP. This is the case because the body of the reflective must be executed by the level 2. But notice that until this point, the level 2 is the non-reflective version of the LSP, the ultimate machine, which cannot run reflective code. To process the reflective procedure body correctly, the level 2 must be the LSP.
We face two solutions: restart the program from the beginning with a three-level tower with the LSP at level 2 or try to create on the fly the same state of the LSP at level 2 if it had run since the beginning of the program, and to resume the computation from this state. The 3-Lisp LSP adopts the second solution. But, this warm start of level 2 imposes the creation of the values of the level 2 processor registers, namely its current expression, environment and continuation, without having to replay the program. If another reflective procedure is called at time 3, the level 3 LSP must now be created in the expected state we would obtain if it would have been run since time 0, and so on. Notice that when a reflective procedure is run at level n, no code is run at any level below n.
The ingenuity of the 3-Lisp LSP appears in the way it has been written that allows the creation of levels on the fly to be performed. How is this achieved? First notice that code can move up in the tower only when a (reflective) procedure call is made. Hence, this appears at a handful of places in the LSP program. Notice also that the LSP does not explicitly represent the state of I/O streams. In fact, the LSP makes no side-effect, as mentioned before. Hence, the state only contains an expression, an environment and a continuation. When shifting up, these three pieces of state can be ``pulled out of thin air'' because they are independent of the past computation at this level. The LSP does not accumulate state (its primitive procedures always call each others in tail position, so it is effectively a finite state machine) and it always carries the same continuation upon entry to its primitive procedures [dRS84] (in fact, the continuation of the next level up in the tower, which is the initial continuation unless some reflective code has been run at this level earlier in the computation). And this is true regardless of the level of computation, since all levels run the same LSP.
In conclusion, the 3-Lisp LSP gets rid of the levels of meta-interpretation. Des Rivières and Smith even report on an implementation where the 3-Lisp code is incrementally compiled at run-time into byte-codes of the underlying SECD machine, which provides a first compiled implementation of behavioral reflection. However, the above restrictions can hardly be applied to the lookup apply case. In this latter model, interpreters (or processors) in the towers are written by the end users for specific purposes, hence flatness (or boredom) 7 of levels doesn't make sense. All the levels are needed to execute methods correctly. It also appears difficult to prevent users from inserting side-effects in their apply methods. Tracing, for example, is one of the well-known applications of reflection that needs side-effects.
