[phylum]<3-LISP>DESRIVIERES>IMPL-PAPER>impl-paper-1.bravo!1

As described in [Smith 82a; Smith 84a], a procedurally reflective programming language is one in which all programs are executed not through the agency of a primitive and inaccessible "interpreter", but rather by the explicit running of a program that represents that interpreter. Since the latter program, which we call the reflective processor program (we use the term ‘processor’ in place of ‘interpreter’ in order to avoid semantic confusion) is written in the same reflective language as the user program, it too is executed by the explicit running of a copy of itself, and so on ad infinitum. In other words, in at least the virtual machine, no program is ever run directly by the actual implementation, but is run indirectly through the explicit action of the running of the reflective processor program. It follows that in the implementation of any reflective language there are (at least virtually) an infinite number of levels of processing, all simultaneously active (in exactly the same way that a program written in language L and the program implementing language L are simultaneously active). Each level has its own local state distinct from the state of neighbouring levels (i.e., there is one ‘‘control stack’’ per level).

The architecture resembles an infinite tower of continuation-passing meta-circular processors, except that (again as discussed in [Smith 84a]) there are crucial causal connections between the levels. A program running at one level can cause non-system code to be run at the next higher level — at that of the program’s processor — thereby gaining explicit access to the formerly implicit state of the computation. This enables the user to define new control contructs or implement debuggers without requiring special hooks into the actual implementation processor. In fact, all control constructs can be defined in the language in terms of a handful of primitive data-manipulation procedures.

Reflection is a powerful tool to add to any language designer’s toolbox. Even if one decides that reflection is too powerful a capability to make generally available to regular users, one may find that the task of producing a correct and complete implementation (e..g, including debugging facilities) is simplified by adopting a reflective architecture. Also, reflection has interesting (and unique) properties that are a direct effect of making it possible to view a computation from more than one vantage point at the same time. For example, a purely functional procedurally reflective language, entirely lacking primitive functions or special constructs with side effects, can nevertheless use reflection to define an assignment statement. {Note Denotational Accounts} In general, reflection is a technique whereby a theory of a language embedded within a language can convey remarkable and otherwise inobtainable power.

Given a virtual machine consisting of an infinite number of levels of processing, it is clear that one of the most important questions to ask about a reflective language is whether, and why, it is computationally tractable. This paper addresses that problem by considering the general question of producing an efficient implementation of a procedurally reflective language. After presenting principles and techniques in a rather general discussion — and in a way that should apply to reflective variants of any standard applicative or imperative programming languages — we describe an efficient implementation of a particular LISP dialect, 3-LISP.

Each level of processing is numbered, for convenience. Let the level at which the user’s program is running be 0; assign 1 to the level at which the processor program that runs the user’s program is running; and so on. In general, the structures at any given level represent the implicit state of the computation at one level below; thus level n+1 is one level ‘‘meta’’ to level n. This whole arrangement, which we call a tower, is depicted in FIGURE 1. Finite heterogeneous towers of processing (i.e., a finite number of different languages) are commonplace — a LISP program running at level 0, being run by the LISP processor (interpreter), which is a machine language program running at level 1, which, in turn might be run by the emulator, a microcode program running at level 2. {Note Hardware} In the case of procedurally reflective architectures, however, the tower is infinite and homogeneous. The user’s program (at level 0) is run by the reflective processor program (running at level 1), which is in turn run by another incarnation of that same reflective processor program (at level 2). And so on.

When we say that a user’s program runs at level 0, we are actually lying: procedurally reflective languages allow user code run at level 1 or higher, giving user programs explicit access to the data structures encoding their own state, and therefore power to direct the course of the computation. What we will call the real implementation (that process that mimics the virtual infinite tower) must therefore be able to make explicit those structures that normally encode the implicit state of the user’s program. It is this fact that makes procedurally reflective systems more difficult to implement than systems without introspective capabilities. Before showing how to do this, however, we need to discharge the threat of the infinite.

The key observation is that the activity at most levels — in fact at all but a finite number of the lowest levels — will be monotonous: the reflective processor program will primarily process the same old expressions, namely those that make up the reflective processor program itself. Identify as kernel those expressions in the reflective processor program that are used in the course of processing the reflective processor program one level below. {Note Kernel} Call a processing level boring if the only expressions it processes (in the course of a computation) are kernel expressions. Define the degree of introspection (D) of a program to be the least m such that when the program is run at level 0, all levels numbered higher than m are boring. All programs consisting entirely of kernel expression have D=0. Normal programs will have D=1, meaning that no out-of-the-ordinary processing is required at level 1; i.e., the processing of the level 0 program will not entail running non-kernel code at level 1. D=2 would be assigned to programs that involve running user code at levels 0 and 1, but not at the second meta level. And so on. Just as a correct implementation of recursion is not required to terminate when a procedure recurses indefinitely, a correct implementation of a procedurally reflective system need terminate only on computations having a finite degree of introspection, providing that a single computation step can increase the degree of introspection by only a finite amount (in 3-LISP it is by one).

It is now possible to formulate a general plan for implementing a procedurally reflective system. Suppose that one has a implementation processor G that engenders the behaviour of the processor for the language provided that the program it is given to run has D=1. The existence of G is not necessarily a big ‘‘if’’, since a procedurally reflective language minus the ability for the user to use the meta levels is likely to be quite conventional. For example, 3-LISP minus the ability to define reflective procedures is a simple SCHEME-like language that will succumb to standard implementation techniques [Allen 78, Steele 77a, Henderson 80]. The essential observation is that the overall degree of introspection of a reflective processor program that is running some D=n computation is D=n-1 (this follows directly from the definition of D). So, if instead of having the user program run directly by G it is run indirectly by the reflective processor program which itself is run directly by G, then any D<2 user program will be processed correctly. In general, any D<n program can be run correctly by G provided that n-1 levels of genuine reflective processor program are placed in between. This result is depicted in FIGURE 2.

Since it is unlikely that a program’s D can be determined without processing it, the insight employed above is more useful when incorporated into a slightly different implementation strategy. Assume initially that D=1, and give the program to G to run directly. If G detects that the program that it is running has D>1, start the whole computation over again, but this time run it indirectly with one more level of intervening reflective processor program. Repeat this last step until G does not protest. This procedure is guaranteed to terminate for any computation with a finite degree of introspection. It requires only that G be able to recognize, at some point during its processing, that a computation has a D>1, and that the computation be re-startable {Note Restartable computations}. Both of these assumptions are reasonable.

It would be far better, of course, if there were some computationally tractable way of inferring the instantaneous state of the level n+1 reflective processor program from the instantaneous state of the level n one. This suggestion is not as unlikely as it might first seem. The processing that goes on at adjacent levels is always strongly correlated (since, after all, level n+1 essentially implements level n). Adjacent levels are related by ‘‘meta’’-ness; it is not as if different levels had ‘‘minds of their own’’. If it were possible to make such a step, one could refine the implementation strategy so as not to restart the computation when an impasse was reached, but rather to manufacture the state that would have existed one level up had the implementation been explicitly running up there right from the beginning. In other words, the real implementation processor would be able to make a instantaneous shift up to where it would have been had an extra level of explicit reflective processor program been in effect since the start. Thus a D=n program would be run directly by the implementation processor G until it was discovered that n>1, at which time the internal state of G would be used to create the explicit state that would be passed to the explicit reflective processor program that would take over the running of the user program. After modifying its own internal state to reflect what would have been the state one level up, G would devote its attention to running the reflective processor program. This means that the original program will now be run indirectly. It will continue to be run that way until such time as it is revealed that n>2, at which time it will start being run double-indirectly. And so on. {Note Shift-points}

Invariably, each additional level of indirection can only degrade the system’s performance with respect to the user program. This is alarming, given that interpretive overhead is typically measured in orders of magnitude. What is really wanted is a implementation that will never run any higher that necessary. Not only should the implementation be able to shift up easily, but it should to be able to shift back down whenever it discovers that things have locally become boring (this requires local, rather than global, notions of boredom and introspective degree, but those are relatively straightforward extensions). That is, when it appears that the program that G is running directly has a local D=0, the implementation processor should compensate by absorbing the explicit state of the reflective processor program it was previously running directly, and proceed to take direct responsibility for running of the computation formerly two levels down. This ensures maximum utilization of the capability of G to directly run arbitrary D=1 computations. A real implementation will be called optimal if it never processes a kernel expression indirectly.

There are two subtleties here. First, it is not necessarily reasonable to expect that every reflective processor program will permit this determination of local boredom. Once the user has been able to run code at a meta level there is no telling what might have been done there. A time bomb may have been planted, in particular, that will detonate at some later point in time. The local notions of boredom just cited must be able to say that a portion of a program is boring, even if some of its embedding context is not. Then the implementation can depend on the fact that it is safe to turn its back on an arbitrary number of boring levels of processing as long as it can turn around and shift back up the moment any of them becomes interesting again. In general, it would seem to be very difficult to determine whether it is safe to shift down. On the other hand, as the 3-LISP example will show in some detail, there are some eminently reasonable assumptions and techniques that enable optimality at least to be approached.

In sum, a correct implementation is one that engenders the same computation as that specified by the limit of a tower of n reflective processor levels as n←#. The base case requires an independent specification of the capabilities of an implementation processor capable only of running D=1 programs. The induction step shows that adding an extra level of processing engenders exactly the same computation while increasing by one the maximum degree of introspection that can be handled. In order to produce a level-shifting implementation we also need computationally effective rules for determining when and how to shift up and back down.

In order to make this all a little more specific, we need a specific reflective language. 3-LISP [Smith 82a] is a reduction-based higher-order, lexically scoped dialect of LISP whose closest ancestor is SCHEME. Other that its reflective capabilities (described below), the most significant way in which 3-LISP differs from its ancestors is that the notion of evaluation was rejected in favour of a rationalized semantics based on the orthogonal notions of reference (what an expression designates, stands for, refers to) and simplification (how an expression is handled by the 3-LISP processor; what is returned). All 3-LISP expression are taken as designating something. $T designates truth and $F designates falsity. Expressions of the form [x1 x2 ... xn] designate the abstract sequence of length n consisting of the objects designated by the xi in the specified order. Expressions of the form (f . a) designate the result of applying the function designated by f to the argument object designated by a. The common case of applying a function to a sequence of n (>0) arguments (f . [x1 x2 ... xn]) is abbreviated (f x1 x2 ... xn). The standard sequence operations are named EMPTY, 1ST, REST, PREP, and SCONS (corresponding to LISP 1.5’s NULL, CAR, CDR, CONS, and LIST, respectively).

The expression ’x is used to designate the expression x. For each different form of x, there is a specially-named collection of designators. For example, ’100 designates the numeral 100; ’$T designates the boolean $T; ’[1 2] designates the rail [1 2]; ’FOO designates the atom FOO; ’(X . Y) designates the pair (X . Y). There are also normal form function designators called closures, which have no adequate printed representation. The expressions ’’FOO, ’’[1], and ’’’’$F designate the handles ’FOO, ’[1], and ’’’$F, respectively. The standard functions NUMERAL, BOOLEAN, RAIL, ATOM, PAIR, CLOSURE, and HANDLE are characteristic functions for the seven kinds of internal structures. The standard operations on sequences apply equally well to rails. The additional standard operation RCONS can used to construct new rails: (RCONS) designates the empty rail []. The standard operations on pairs are named PCONS, CAR, and CDR; (PCONS ’A ’B) designates the pair (A . B); (CAR ’(A . B)) designates the atom A; and (CDR ’(A . B)) designates the atom B. The standard operations on closures are named CCONS, ENVIRONMENT, REFLECTIVE, BODY, and PATTERN.

Despite the many minor differences between the languages, readers familiar with SCHEME should have little difficulty understanding 3-LISP programs. The reader is referred to [Smith 84a] for a more complete introduction to both the language and to the intuitions that guided its development. Very much like the meta-circular interpreters discussed in the ‘‘Lambda papers’’ [Sussman and Steele 1975, 76a, 76b, 77a, 77b, 78a, 78b, 80], we present the continuation-passing 3-LISP reflective processor program:

(define REDUCE
(lambda simple [proc args env cont]
(normalise proc env
(lambda simple [proc!]; PROC continuation
(if (reflective proc!)
(↑(de-reflect proc!) args env cont)
(normalise args env
(lambda simple [args!]; ARGS continuation
(if (primitive proc!)
(cont ↑(↑proc! . ↑args!))
(normalise (body proc!)
(bind (pattern proc!) args! (environment proc!))
cont)))))))))

All the procedures used in the above code, other than those explicitly defined, are straightforward, side-effect-free, data manipulation functions. None have any special control responsibilities (except COND, DEFINE, and BLOCK, which have been omitted only to shorten the presentation). PROMPT&READ and PROMPT&REPLY issue the system’s ‘level>’ and ‘level=’ prompts, and perform input and output, respectively, but are otherwise innocuous; ↑ and ↑ mediate between a sign and what is signified: (examples: ↑(+ 2 2) g ’4, ↑↑(+ 2 2) g ’’4, ↑’’4 g ’4, ↑’’(+ 2 2) g ’(+ 2 2), but ↑’(+ 2 2) is an error). There are no hidden procedures; user programs may use CCONS (the closure constructor), BODY, NORMALISE, etc. — even ↑ and ↑ — with impunity. In fact, by defining his own reflective procedures (using LAMBDA REFLECT), the user may augment this processor — these reflective procedures are handled by the (↑(de-reflect proc!) args env cont) line of REDUCE. When the level 1 processor encounters (foo e1 ... en) in the program it is running, the reflective procedure associated with the name foo is called at the same level as the processor with exactly three arguments: a designator of the unnormalised argument structure (from the level 0 redex) ’[e1 ... en], the variable binding environment, and the continuation. In this way, the user’s program may gain access to all of the state information maintained by the processor that is running his program. From this unique vantage point, it is easy to realize new control constructs, such as CATCH and THROW, or to implement a resident debugger. The infinite tower appears to the user exactly as if the system had been initialized in the following manner:

1> (define QUIT (lambda reflect [args env cont] ’DONE))
1= ’QUIT
1> (quit) ; QUIT is run as part of the level 1 processor, which it kills.
2= ’DONE
2> (+ 2 (quit)) ; This time QUIT terminates the level 2 processor.
3= ’DONE
3> (read-normalise-print 1 global) ; But levels can be re-created at will.
1> (read-normalise-print 2001 global) ; Level numbers are arbirtary.
2001> (quit)
1= ’DONE
1> (quit)
3= ’DONE

To some extent, a meta-circular or reflective processor program can be viewed as an account of a language (or at least of how it is processed) that is expressed within that language. As such, it "explains" various things about how the language is processed, but depending on the account, it can account for more or less of what is the case. In particular, it is important to realize what the above 3-LISP reflective processor program does and does not explain. This reflective processor was designed to be similar to standard Scott-Strachey continuation-based semantic accounts of l-calculus based languages (e.g., [Stoy 77, Muchnick 80]). Its primary purpose is to explain the variable binding mechanisms and the flow of control in the course of error-free computations. This account intentionally does not say anything about how errors are processed, nor does it shed any light on how data structures are implemented, nor on how I/O is carried out. These details are buried in the primitive procedures, and the reflective processor carefully avoids accounting for what they actually do. A different theory that did explain these aspects of the language could be written, yielding a different reflective processor program, and a different reflective dialect — all of which would require a different implementation. But the basic architecture and strategies we employ would generalize to such other circumstances.

One of the many things that SCHEME demonstrated was that lexical scoping and the treatment functions as first class citizens resulted in a cleaned-up LISP that no longer needed to quote its LAMBDA expressions or resort to using APPLY or FUNCALL. 3-LISP goes a step further by showing how to incorporate, in a semantically principled way, some of the other hallmarks of real LISPs, including: constructing programs on-the-fly; explicit use of EVAL and APPLY; FEXPRs and NLAMBDAs; and implementing a LISP debugger in LISP.