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

[Weasel words required here!
* Related ideas of section 2 to the implementation of 3-LISP.
* Want to explain what’s happening before presenting code.
* The resulting implementation is remarkably familiar.
* Want to show you how we analyze the rpp in order to build ppp.
* Explain why we say "compiling" the ppps.
* Why it’s possible to shift up; how’s it done.
* Why it’s possible to shift back down; how it’s done.
* How we decided on what part of the kernel to "compile".
* How you should grok the code in the next section (or how we do so).
* COde in next section is subtle if you are not tuned in to what’s happening.]

Although procedurally reflective architectures are new, the idea of level shifting certainly isn’t. Consider your favourite implementation of LISP that supports both ‘‘interpreted’’ and ‘‘compiled’’ procedures definitions; i.e., to the LISP system, some procedures will be defined by LISP source code — normally a LAMBDA expression represented as a list structure — while others will be represented by a block of instructions acceptable to the machine on which the LISP system is implemented. There are some interesting wrinkles in the procedure call mechanism that the implementation smoothes so well that many users never realize the complexities. In the simplest case where both procedures have compiled code, the compiled-to-compiled linkage is usually achieved directly using a machine language branch instruction to transfer control from the calling procedure to the first instruction of the destination procedure (after arguments and the return address are loaded into registers or perhaps pushed on a stack). On the other hand, when a compiled procedure calls one that has no compiled code associated with it, a transfer of control must be made to the block of machine language code that implements the explicit LISP processor that can grovel over the list-encoded LAMBDA expression representation of a procedure. Once the LISP processor is in control, the situation is somewhat reversed. As long as the procedures called by the user’s program are not compiled, everything is straightforward, with the machine language level locus of control remaining within the LISP processor’s code; control will leave it only when a compiled procedure is called. As depicted in FIGURE 3, this can be described as simple level shifting between a level of implicit LISP processing (lower level, where compiled procedures run) and one of explicit LISP processing (where non-compiled procedures get run). Shifting up and down both occur at times corresponding to procedure-to-procedure calls (and returns).

The analogy can be pushed even further by considering how matters are complicated when explicit calls to EVAL are included in the story. Suppose that the expression (EVAL ’(FOO 10)) is found within the body of a (non-compiled) procedure named FEE. When the explicit LISP processor encounters this expression while processing a call to FEE, control within the user’s program must pass to the EVAL procedure, which, we will assume for the moment, will be defined via LISP source code; i.e., EVAL is a meta-circular processor program for LISP. The net effect will be to explicitly process the procedure for FOO indirectly; instead of being processed by the LISP processor, the LISP processor will processes the source definition for EVAL, which in turn will carry out the explicit processing of the source for FOO. It is a relatively simple change to the LISP processor to have it recognize calls to EVAL and treat them in a special way that avoids this extra level of explicit processing — and that is just what most implementations of LISP do. (see FIGURE 4) But notice that this, too, is a form of level shift, this time not between compiled code and the LISP processor but between two different LISP expressions: (EVAL ’(FOO 10)) and (FOO 10).

The strong similarities between these forms of level shifting are more than mere coincidence. The machine code for the LISP processor is the compiled code for EVAL; the downward shift to avoid a extra level of explicit processing on calls to EVAL is also the downward shift to run the compiled code for EVAL. In both cases, the relationship between adjacent levels is the same: the computation that happens implicitly at one level is being carried out explicitly one level above it.

While the simple level shifting techniques described above might suffice to handle a non-reflective language with explicit access to the processor, the task of implementing 3-LISP has an additional complexity; viz., reflective procedures give the user a way of running arbitrary procedures at the level of the program’s processor. In effect, the user can get his hooks into the middle of NORMALISE (3-LISP’s EVAL), making the job of ‘‘compiling’’ NORMALISE much more difficult. Moreover, several of the standard control constructs, such as LAMBDA and IF, look as if they are defined in a circular fashion, being both defined as reflective procedures and used in the account of how the processor works. Thus we turn to a careful analysis of the processing activities that must go on, with an eye to implementing some of them directly while allowing others to be carried out in virtue of one or more levels of explicit processing.

The processing activity engendered by the processing of the expression (SECOND [10 20]) can be broken down into a series of simpler processing activities using the definition of the procedure SECOND, namely (LAMBDA SIMPLE [X] (FIRST (REST X))). Roughly, the subactivities correspond to the processing of (REST [10 20]) and (FIRST [20]). We will call this a horizontal decomposition of processing activity so as to be consonant with the way we have been depicting levels of processing. In a languages with some form of procedure, procedure call boundaries usually serve as most convenient dividing lines. In general, a lengthy computation is carried out in virtue of its horizontal decomposition into a series of simple steps, each of which can be achieved directly by the implementing mechanism.

As we have already seen, having a meta-circular processor program gives one an additional degree of freedom when it comes to decomposing a processing activity. It becomes possible to vertically decompose a processing activity; e.g., to shift from the processing of (SECOND [10 20]) to the finer-grained processing activity involved in the processing of (NORMALISE ’(SECOND [10 20])), whose lengthy horizontal decomposition through NORMALISE and REDUCE begins (roughly):

The tiling game example of FIGURE 5 illustrates several points; only odd-numbered tiles may be stepped on. Given the particular way each tile is related to the tiles above it (e.g., directly above a 2-tile there is always a 3-tile and a 4-tile), it will always be possible to find a path no matter what the bottom layer of tiles is chosen to be. Moreover, no path ever need go higher than three rows from the bottom (in order to get over a 2-tile), and the strategy of choosing the lowest possible path will always be optimal and will never lead to a dead end. If the rules were made more restrictive by forbidding one to step on 3-tiles, the game would still be beatable; however, the same can’t be said of either the 1-tile or the 5-tile, both of which are absolutely unavoidable (notice the insurmountable ‘‘spike’’ of 1-tiles).

As defined in an earlier section, the kernel consists of those parts of the reflective processor program that are used in the course of processing the reflective processor program one level below. For 3-LISP, this includes the closures and all of the body code for the primary processor procedures: NORMALISE, REDUCE, NORMALISE-RAIL, LAMBDA, IF, READ-NORMALISE-PRINT, and their embedded continuations (which we call the PROC, ARGS, FIRST, REST, IF, and REPLY continuations), the utilities like BINDING, BIND, and NORMAL, and the primitives such as CAR, CDR, ↑, ↑, and RCONS. If the implementation had ‘‘compiled’’ versions of all of the kernel procedures, it would be guaranteed that any D=n (n finite) expression could be normalised (the analogous situation in the tiling game would be one where any tile could be stepped on). The implementation that we will show is slightly simpler; only the primary processor procedures are ‘‘compiled’’ since the ARGS continuation handles all of the primitive procedures. {Note Minimal Compiled Kernel} As with the tiling game, the choice of basis cannot be made independently of the strategy for shifting up and down. The particular basis chosen will only work in conjunction with the particular choice of shift points discussed below.

The next important problem is to determine the criteria by which the implementation processor will decide that it is necessary to shift up and the mechanisms for achieving this transition. Begin by observing that the state explicitly maintained at each level of processing by the reflective processor consists of the expressions, environments, and continuations that are passed as arguments among the primary processor procedures. Not captured at any particular level are the global state of I/O streams and the structural field itself; however, the reflective processor does not use side effecting primitives to remember state information except when the program that it is running forces it to. {Note No RPLACA} As a result, when a shift up occurs, only an expression, an environment, and a continuation will have to be ‘‘pulled out of thin air’’.

Shifting up will have to occur when control would leave the implementation code corresponding to the compiled kernel. This can happen only at a handful of places in the reflective processor program: one of the continuation calls, (cont ...), and where a reflective procedure is called, (↑(de-reflect proc!) ...). The real question is where in the implementation processor should the shift up take us? It is all very well to note where one needs to leave the level below and shift up; it is much less clear where, in the level above, we should arrive. For example, if we assume that exp and cont normalise to exp and the simple closure cont, respectively, the implemetation processor could shift from ‘‘doing’’ (cont exp) to doing any of

Since the higher level will always be finer-grained that the lower level, there will always be this kind of decision to make. Given that our particular choice of primary processor procedures, it turns out that all of these are acceptable. In fact, a more natural seam at which to dissect computations occurs in the ARGS continuation the instant NORMALISE is about to be called on the body of the (simple) closure:

Why is this the case? There are two critical things to realise about the reflective processor program. First, it implements a ‘‘tail-recursive’’ dialect of LISP (e.g., SCHEME); i.e., it is not procedure calls per se that cause the processor to accumulate state, but rather only embedded procedure calls. For example, with respect to a call to the procedure given by (lambda simple [x] (f (g x))), the call (g x) is embedded in the first argument position of (f (g x)), and therefore requires the processor to save state until (g x) returns, just as in a conventional implementation of procedure calls; on the other hand, the call to f is not embedded with respect to the initial call (rather, it substitutes for it), and can be implemented much like a GO TO statement, except that arguments must be passed as well. The fact that 3-LISP has a tail-recursive processor can been seen by inspecting the reflective processor program and observing that a) the number of bindings in an environment is a (more-or-less) linear function of the static nesting depth of programs, and b) when a call to a simple procedure is reduced, the continuation in effect upon entry to REDUCE is the one passed to NORMALISE for the body of the called procedures’s closure. The key implication is that when one procedure calls another from a non-embedded context, the continuation carried by the processor upon entry to the called procedure is the same as what it was upon entry to the calling procedure.

The second crucial property is that the primary processor procedures always call one another in non-embedded ways. Together with the other observation, it implies the following property of the reflective processor processing the reflective processor program itself: the continuation carried by the processor upon entry to any primary processor procedure is always the same. This assertion can be phrased more precisely: the (level 2) reflective processor processing the (level 1) reflective processor program processing a (level 0) D<1 structure always carries the same level 2 continuation at every trip through level 2 REDUCE when the level 2 PROC is bound to ’NORMALISE. In other words, if one were to ‘‘watch’’ the level 2 state upon entry to REDUCE, one would find that CONT was always bound to the same closure whenever PROC is bound to the atom ’NORMALISE (or ’REDUCE, or ’CONT, etc.).

Since the points where the up-shift are to take place logically corresponds to a non-embedded call within the reflective processor program (specifically, either to (↑(de-reflect proc!) ...) or to one of the six (cont ...) expressions), the continuation that must be reified is not a function of the current level of processing. Instead, it is the original REPLY continuation at the next higher level, assuming that user-defined code has never been run at that level before.

Deciding when to shift down is similarly straightforward. The implementation processor should shift down whenever it is processing one of the primary processor procedures. In practice, it is not necessary to shift down as soon as possible (i.e., full optimality need not be achieved); it suffices to recognize only the situation where the implementation processor is processing a call to NORMALISE, since all paths through the reflective processor program will pass through this procedure. The situation can be detected in the code corresponding to the ARGS continuation (i.e., is PROC! bound to the closure for NORMALISE?). It is also essential that the arguments passed to NORMALISE be scrutinized, to ensure that they are ‘‘reasonable’’ (of proper type and so forth). If they are, the implementation processor can make the transition from

The continuation in effect prior to shifting down must be recorded in the absorbed state. It will usually be the same REPLY continuation — the original one for that level of processing, born within the call to READ-NORMALISE-PRINT that created that level at system genesis. However, since it is possible for the user to call NORMALISE from an embedded context, it is essential to save the continuation each time a downward shift occurs so that it may be brought back into play the next time the processor shifts up to this level. What allows a non-primary processor continuation to be absorbed? The answer is simply that the continuation cannot come into play until such time as the computation at the lower level returns a result. Since each primary processor procedure ends in a tail-recursive call, this chain can break down only if some non-primary processor procedure is called which returns a result instead of calling the continuation passed to it. But it is precisely these calls that always cause a shift up; hence, the implementation processor will automatically find its way back to the appropriate level whenever a non-primary processor continuation would be called at a higher level.