How The Tower Levels Are Linked Together

The relationships between adjacent levels of a tower are as important as the contents of each level. Having examined the closures that are used to make up each tower level, we now look at how they fit together to make a tower, and how that infinite tower is linked to a meta-evaluator so that it may be interpreted in finite time.

Levels, Strings Of Levels, And Towers

A tower is made up of a sequence of levels, but not every sequence of levels is a tower. We will call a sequence of levels a string of levels, and here explain some of the properties of these strings.

A tower is a string of levels that has an application (bottom end) that is not an interpreter---that is, does not take another program as its subject and evaluate the result of that program. A grounded interpreter (one whose computation is known to take a finite number of steps, as explained on here) at the top is not necessary for it to be a tower.

A string is at the bottom of the tower if its lower end interprets an application. Since this application may be another interpreter, the same string could be in a longer tower, not at the bottom of it. The lower limit of the tower is defined by what we consider to be an interpreter: at a more abstract level than computer science, we may in some cases consider the application program to be the interpreter of something in the world outside the computer; indeed, one possible view is that the observer of the system may be seen as a tower of meaning, in a morphic mirror image of the reflective tower. (This is one of the possibilities available through co-tower relations, as described in section 4.5.)

A string interprets the closure applied to its lower end. In turn a string must be interpreted by a closure to which its upper end is applied. Thus, a string of interpreter levels is equivalent to an interpreter level: it interprets something, and is itself interpreted by something. The interpreters in the string are functionally composed, making what is intensionally a string of interpreters into what is extensionally a single interpreter.

We say that a string (or a level) is grounded if it interprets a terminating application applied to its lower end in finite time. In the formulae below, levels which are known to be grounded are written suffixed thus:

Reification and reflection are complementary operations, reflection moving information up the tower from LG1 to LG2 into the level interpreting the level providing the data, and reification moving data down the tower, from LG1 to LG0, from interpreter to interpreted. This implies that both interpreter and interpreted can access each other. Formulae (given in section tower-formulae-1) explain the relationship between levels in terms of this knowledge of neighbouring levels. To use these paths to move up and down the tower, links must be present in both directions:

These two links form a protocol that is observed throughout the tower. This is important not only dynamically, in the execution of a tower, but also statically or structurally, for inspecting and modifying the tower, allowing any level to perform the same operations on all the levels to which it has access.

Links Always Occurring Together

Since both links are set up by parts of the calling mechanism, they always occur in pairs:

The application level is the only level that has no level below it for it to interpret; whilst the tower stretches up infinitely from the application level.

These links make a two-way chain throughout the tower, so any interpreter in the tower can access the application, although normally only the last interpreter should do this, and the application can access any interpreter in the tower, although it will usually only need to access the nearer ones, and (provided it terminates) will never access those infinitely far from it, as explained in section finitereify.

Rolling Up The Infinite String For Storage

Although the tower is infinite, it may be represented finitely, because its infinitely long upper initial string consists of identical successive levels (or identical strings of levels). In Smith's work, such levels are termed boring [Smith 82]. This repetitive string may be stored as a circular structure, in which those levels are not only equivalent but actually the very same level. A hidden mechanism, to be explained in section unroll-circular-tower, separates off copies of this level (or these levels) when they have to be changed, rather like printing off copies of a pattern from an inked roller:

As the levels produced this way are copies of the original, any of them can be changed without affecting either each other or the original.

The Umbrella Of The Tower.

Since a tower is an infinite structure, any computation involving all levels of it cannot terminate. In particular, as each level is interpreted by the level above it, we can never find a level that can be executed non-reflectively. So, from a traditional computability viewpoint, a program represented as the base of an infinite tower could not be executed were it not for that we can rely on the application terminating. If it terminates, it can have reified only a finite amount of the tower. If it does not terminate, we cannot tell whether it requires infinite amounts of reified tower, and so it only matters that we can realize (that is, convert into a form that really occupies storage, as described in section unroll-circular-tower) an arbitrary but finite number of levels.

A special interpreter can be constructed using this fact. It takes the place of an infinite amount of the tower (the boring part), and is always just above the highest level that has been touched by reification or reflection. Because it is always at the top of the tower, we call this interpreter an Umbrella. Umbrella interpreters are explained further in section umbrellainterpreters.

Tower Computability; Propagation; Integrity

This section shows how a tower that is apparently infinite can be evaluated in a finite number of steps. We look at the complexity of each action at different levels that it involves, and then procede to remove factors from the complexity by introducing interpreters that absorb (or collapse) level shifts. Since adding a level of interpretation multiplies the complexity of an action, absorbing a level removes the multiplying factor that that level introduced.

From this, we see that the ability to absorb an infinite number of unwanted multiplying factors (by collapsing the levels at the top of the tower) allows us to prevent the infinite prolongation of calculation caused by tower interpretation.

Relative Computability

We have shown that a terminating application in an infinite tower in one sense can be computed, because the infinite part of the computation must be collapsable into a finite computation for any terminating application, and in another sense cannot terminate, because the computation happens at an infinite number of levels. We wish to resolve this paradoxical situation, and so we develop a theory of computability for interpretive towers.

The conventional idea of computability, in the sense of what can be computed by a universal machine such as a Turing Machine, is not sufficient to describe this, as it works only in terms of absolute computability. We must use relative computability to describe what the lower end of a string of levels can interpret if its upper end is given an interpretation. In terms of Turing's work [Turing 37], this is called oracular computability, because something can be computed if the information on which that computation depends is given by some oracle. In a reflective system this information includes the computation process itself as a data value.

Using relative computability, we can describe what effects a string of levels may have on computability when it is inserted between an interpreter and a procedure that is interpreted.

Relative Computability---Quantitatively

What rules for computability hold in a infinite interpretive tower? Let us take an interpreter LGx which if used to interpret a terminating application ax thus:

will calculate it in a finite number of steps of a grounded interpreter LGx. LGx is itself represented as a closure, and so tells us what interpreter to use to interpret it, which we will callLG(x+1). This lets us use it as the application of another interpreter in a meta-circular interpretation chain:

where LGx

LG(x+1) This is now also calculable in a finite number of steps, since, if, z terminates, LGx(z) terminates.

But since LG(x+1) is a closure, it must be interpreted, by some grounded interpreter (either meta-circularly or by some other one):

Can we force this computation to become absolutely finite? Using the notation introduced in section 2.1, we can calculate how many steps are involved in working a calculation through two levels of interpretation:

If we have an interpreter LGz capable of interpreting two tower levels at once, we can do

Now let the application ay in the first of the pair of formulae above be an interpreter LGv which interprets the second application az in g steps:

In LGz we have a kind of closure which, through running two levels at once, absorbs and generates level shifts within itself. Since it is the level shifting that prolongs a terminating computation at one level into a non-terminating computation at an infinite number of levels, we can use this interpreter that performs level shifts within itself in finite time to provide full grounding for an infinite tower.

This makes it possible to evaluate a tower that has at the top an interpreter that can handle level shifts within itself, while still providing the illusion of an infinite number of levels of interpretation, as described in section 4.3.

We call this kind of interpreter an umbrella since it appears to occur at the top of the tower, and caps the tower.

Shadowing Interpreters

We cannot take this solution as it stands because each level can have only one closure running in it at once---it contains a list of closures, as a call stack---and each closure can represent the state of just one level. (The way that several closures are running at once is at separate levels of interpretation, as explained in the clock analogy of section 2.3) Because of this relationship between closures and the representation of tower levels, this shift-absorbing closure must, by the rules, be outside the tower, shadowing an infinite string of ordinary levels that are within the tower. This is as explained in section 2.7:

A closure in the tower is shadowed by a closure outside the tower if the one outside the tower implements the one inside the tower and all those above it in the tower that take part in its interpretation. The closure outside the tower is called the shadow of the corresponding closure within the tower. As the meta-evaluator of a tower begins the evaluation of each closure, it first checks whether the closure is in a table of shadowed closures---the shadow map. If the closure does have a shadow listed in the shadow map, the meta-evaluator calls the shadow directly, that is, as a procedure within the meta-evaluator. If there is no shadow, the closure is interpreted stepwise by the meta-evaluator---that is, as a regular interpreter does.

The idea of shadowing is central to this thesis. In later s, we develop the details of a mechanism for shadowing the upper initial string of a tower, which makes it possible to implement the interpretation of an infinite tower in finite time.

The shadowing interpreter of a tower, in performing some number of steps, makes each of the levels that it interprets---that is, those below the one that it shadows---take some smaller number of steps in each of their actions. In this way, it is like the infinite string of levels which it shadows, since their progression through their procedures would also cause the same effect on the lower parts of the tower.

Let us return to the digital clock analogy of section 2.3, in which we examined how the minutes digits affect the hours digits, and so forth. Starting at the seconds digit, and setting off in the other direction, we can posit the existence of further digits, which are usually invisible: a deciseconds digit, a centiseconds digit, and so on. In a typical clock, some of these digits will exist, but there will not be infinitely many of them. While our model of how a clock works may continue to produce more and more digit devices, each counting faster than the last, in practice we eventually reach some device that ticks without the aid of a previous ticker---or rather, one in which the ticks are of a very different kind, such as the resonance of a quartz crystal. The shadowing interpreter of the tower takes the place of the crystal in the clock. Although there could be more counting devices, a non-counting ticking device (with the same interface at its slow end as a counting one) rounds off the chain of counters, and shadows an infinite number of even faster counters.

It is worth noting that the shadowing interpreter has not taken control away from the string of interpreters that it shadows. It exists beside that non-existent string, just as the quartz crystal in the clock exists beside the non-existent extra counters. It does not displace them! They are still there as a concept.

From the abstract, extensional point of view, the last counter sees something equivalent to a string of counters. From an implementational, intensional viewpoint, the crystal is there. They are views in two worlds of the one thing performing its function.

The extensional view is what you see if you look at the counter chain from any one of the counters. If you look at it from the quartz crystal, you are viewing it from the intensional viewpoint.

Since reflection is a means for abstraction, it is natural to view it reflectively, using its own abstraction. This always involves taking the extensional view of the system---looking upwards in a tower, or outwards in a meta-tower. This is not useful for creating and starting a (meta-)tower; the tower's creator must work from the outside in (like Smith's lightning bolt), as the tower cannot start itself from nothing. This necessity for an outsider follows the same logic as that of section 3.3. From the outsider's point of view, the system within the (meta-)tower is flat; it is all processed at one level, as the application of the outsider; in the clock analogy above, the crystal puts its output into what may be seen as a single counting device; whether that counting device is infinite or finite is irrelevant.

Rules For Groundedness

In the discussion above, we have assumed that we work with grounded towers only---as indeed we must for the practical evaluation of a tower. However, the same rules hold for non-grounded towers, which cannot be evaluated, but can still be manipulated in the same way. A non-grounded tower is ungrounded because it has no grounded interpreter anywhere in it. A non-grounded tower can be made into a grounded tower by connecting to it a grounded tower, which will interpret it in a finite number of steps. (The connection will be at the bottom of the boring part of the tower.) These grounded towers ground the towers to which they are appended by acting as oracles [Turing 37] for the interpretation of their highest levels.

Integrity Of Strings

If an interpreter level evaluates its application finitely for a finite application, then we say the interpreter has integrity. A finite string of adjacent levels also can have integrity (as a relative property; this is integrity with respect to an oracle), if its highest level of interpreter terminates evaluation for a terminating application run at the lowest level. These are both the same concept of integrity. As explained above, an interpreter which evaluates more than one level is an exact substitute for a string of interpreters (an infinite string, if the upper end is boring).

Since an infinite tower can be evaluated by an interpreter that absorbs level shifts, and is thus, effectively, an extensible finite tower, it may also have integrity, but only if its higher end is accessed via its umbrella interpreter. This is because it is the umbrella that provides the computability. If we look at the infinite upper string of interpreters that the umbrella stands in for, instead of looking at the umbrella, the tower then appears not to be grounded.

The integrity of a string of levels is broken by it having any level without integrity. A level is grounded[1] if it is linked with integrity to a level that is grounded, such as an umbrella, or a string that is known to be possible to link to an umbrella.

Unlike conventional semantic definition systems, reflective interpretation allows us to reason about non-computable programs, and constructs which cannot be computed, just as easily as computable ones. This may not seem very useful in its own right, except for pure theoretical linguistics, but since computability is undecidable for most programs (and so all programs must be treated as potentially non-computable) this is not necessarily a problem, and so this approach is very generally applicable.

The solution to the problem of grounding towers is mentioned at the start of this : at some level on our way up the tower, we find a meta-circular interpreter (let us say Ln) whose interpreter, Ln+1, is the same as the interpreter Ln itself, that is, Ln Equiv

LN+1. Since this level is a meta-circular interpreter, this relationship holds for the next level too, and for all subsequent pairs of levels Lm, Lm+1. Closing this transitively, we have

Since we wish to use reflection in real computations, for practical purposes we can make the tower above that level into a circular structure, such that not only is

Shift-Absorbing Levels

The real interpreter outside the tower, called the meta-evaluator, mimics this closure Ln, and all the closures past it in the tower. This imposes a constraint on towers in the system: any which are to be evaluated must have Ln as their upper initial string, which, given that the meta-evaluator mimics them, implies that they are grounded. A tower which has a repeating chain of anything other than Ln as its initial string cannot be evaluated by the meta-evaluator, which keeps on realizing new levels until it gets to one running Ln.

The operators that we provide for reflection help to maintain this, in that by default all new closures are created with Ln as their interpreter. It is possible to enforce this rule absolutely, by insisting that any closure that becomes the interpreter of another closure must be grounded through the standard interpreter. This can always be determined, since the route up from a closure can be determined statically from its contents.

The Standard Evaluator And The Meta-Evaluator

Since the standard evaluator is an invariant part of the system, mimicked by code outside the tower, it must not be mutable by reflection operations. The meta-evaluator employs a technique for maintaining this integrity while still allowing reflection at any level of the tower, without requiring infinite storage or time. This technique is described in detail in section 9.4.

If the reflection system tries to access or modify Lm (where Ln is the lowest level mimicked by the meta-evaluator, and m>n--- that is, any level representing the standard interpreter), new levels, all running copies of the standard evaluator, are created in memory for levels Ln ... Lm. The `evaluator' link of Ln-1 points to the new Ln, and the `evaluator' link of Lm points to the standard evaluator. Then Lm is modified as specified by the call to the reflection operator, and the meta-evaluator continues execution as before, but now shadowing levels Lm+1 ... L infty

instead of Ln+1 ... L infty

. Note that level Ln has not been changed by any of this activity.

This activity has made into real levels some levels that previously were not stored anywhere, although they were accessible for inspection. We say it has realized them.

This realization is part of the process of level-shifting, that is, the transfer of information or control between levels of the tower. It takes place only as needed, so not all level shifts will realize any levels; they may simply move between levels that have already been realized. The realization is performed by the meta-evaluator, which is explained in detail in section 11.1.

Reifying The Meta-Evaluator

The meta-evaluator implements reflection through non-reflective means, and so can be an ordinary program, written in a language without explicit reflective features (such as C, or Common Lisp). But, since reflective interpreters provide a superset of the facilities of other program evaluators, the meta-evaluator could itself be the application run by another reflective tower. To extend the reflective facilities provided by a tower, we can provide a connection between a tower and the tower of its meta-evaluator.

In doing so, we make the whole system more regular, and we bring reflective techniques, and meta-circular interpretation---already accepted as a standard and powerful means of describing interpretation in the Lisp world---to bear on the problems of how the meta-evaluator is connected to the tower. We later find a similarity between this connection and the connection between operator names and operator definitions in a language.

The Dimensions Of The Tower

When we provide a means of reaching this second tower (for reifying and reflecting it) from the first one, we have a new form of reflective system, which has a two-dimensional tower rather than the one-dimensional tower already described. The second dimension, like the first, may continue either for one level, as a non-towering second dimension:

However, since the point of a tower-reflective system is to make the interpretation mechanism visible and manipulable, such a meta-evaluator stands out as an oddity---although it is a running procedure, it is not decomposable in the same terms as are the other running procedures in the system.

A more consistent model for reifying interpreters demands that we include the meta-evaluator within the reifiable part of the system, on the same basis as the other reifiable parts of the system. This can be done by providing a type tower, and including in each level a field pointing to the tower of which that level is part. (The definitions of the level and tower types are given in section 7.2.)

It would be possible to make the meta-evaluator, which is attached to (or part of) this tower structure, be simply a procedure in the language of the substrate system. However, for consistency, to allow the same reasoning to be applied to the meta-evaluator as to the other interpreters, we model it as the application of a new tower---the meta-tower of the first one:

Note that this second tower is reached not from the end of the first one, since that has no end, but to the side from any closure on the first tower. In other words, the meta-evaluator is a property of the tower, rather than of a particular level.

The structure of this second tower is just like that of the first; each of its levels is represented by same kind of structure used to represent levels in the first tower. Thus, the same operations for manipulating reified data may also be used. The reifier and reflector operations themselves may also be the same as in a single-dimensional tower; it is simply that there is another field, the meta-evaluator (or meta-tower), in the data structure used to represent towers, and the content of that field is a tower level running an interpreter. The difference is not in the form of reification, but in the data that is provided by reification.

To the second tower, the entire first tower is a value within its problem domain. So, for example, while for the second tower the problem is a program to execute, for the first tower the problem might be a representation of some problem outside the world of computers, such as weather prediction. Or, of course, it could be another tower to interpret.

The Dimensions Of The Dimensions Of The Tower

Continuing this idea, we can provide third and subsequent meta-towers, continuing in an infinite meta-tower (which we draw as a spiral, to fit it better onto the page; we draw the successive meta-levels not quite orthogonally to each other, so that they do not altogether hide those drawn behind them). Note that for each successive meta-level link, all the levels of one meta-level are accessible to the lowest level of the next meta-level.

These ideas may be continued to any number of towers of levels, as the structure provided through reification becomes more and more extensive. However, however many towers are provided, the relationship between adjacent towers remains the same.

Just as a tower is implemented by its meta-evaluator running in the tower's meta-tower, we can explain the spiral of towers as being evaluated by an evaluator external to the spiral. We draw this as a rod (as if seen in section) running up the middle of the spiral. This interpreter is, of course, similar in form to any of the meta-evaluators within the spiral of towers. Just as a meta-evaluator of a tower shadows the boring part of the tower, the meta-evaluator of a spiral of towers shadows the boring part of the spiral.

In turn, this program may be the application of another tower... and a form of reflection could be provided that allows access to this tower. It is noteworthy that all these multi-dimensional forms of reflection differ from the first form we saw only in the structure provided by reification. The form of reflection and reification is still the same. The tower type has a field for the meta-evaluator, which is itself a level or tower, and also through the meta-evaluator`s tower, a field for the next dimension of meta-towers. However, this is only one of the directions that may be pursued; to implement this direction of provision of meaning, there must be an orthogonal direction also; and another to implement that... and so we have an infinite list of meta-towers to describe each meta-tower. Having established this, we can see that, we now settle down to a fixed-point, in which the structure is the same: from each tower, we have access not only to the meta-tower that interprets it, but also to the meta-tower that provides the link between these two. This is similar to the first form of tower reflection that we have looked at, and obeys the rules explored in sections flatplustower and relationships. In the terms already presented, this can be represented by the following diagram:

These diagrams show how the same idea of the reflective tower may be pursued to any number of levels.

Pursuing this reflection to higher meta-levels leads to examination of the ideas of what gives an interpretation its interpretation, or meaning, or grounding (as in the symbol grounding problem). Starting at the highest level, and constructing lower levels, by implementing them, leads to an understanding of meta-towers as a real programming device. As mentioned in more abstract terms in section 2.3, it is easier to think in terms of running an meta-evaluator on a system that happens to be in a tower, than to think of using one tower to implement another.

The idea of shadowing is equally applicable to any of these towers and meta-towers. The relationships between them are equivalent, and can be extended to any number of meta-levels---a meta-tower is a fractal structure, where the detail of each meta-level is similar in form to the detail of any other meta-level. Any dimensionality of meta-tower may be implemented, although the generalized meta-tower has its own dimensionality, which is fractal. The known practical advantages of doing this are swamped by the computational complexity of such a system, but the ideas have proved worth pondering to further understanding of simpler forms of reflection.

The important point here is not that any number of levels and meta-levels may be returned by the reifier, but that each new plane of meta-levels is introduced in the same way as all the preceding ones: the deeper information about a level is provided by the level implementing that level. If one level does not provide its subject level (interpretee) with some particular information about itself, there is no way in which the subject can derive that information. This is explained, in terms of a single tower, in section 3.3.

It is natural to think of reflection from within; as information about the self is reified, it is brought from outer reaches of the meta-tower in the application. Likewise, in mental introspection, it is normal to think from objective-world views out to deeper abstractions about self. However, an infinite regression along an inner route outwards will never get outside self; whereas other can observe self from the outside, without any regression whatsoever.

Reflection involving such an outsider is an interesting extension to the idea of meta-towers. One possibility is to have two meta-towers, each examining (and possibly interpreting, with the help of a suitable outsider) the other, on a co-routine-like basis---let us call these co-towers. Further (in the sense of more encompassing) related forms of reflection involve reflecting on the observer of the co-towering relationship (which is what allows each of the co-towers to interpret parts of the other). However, one thing is common to all these forms of inspection: introspection at any level is only possible when a higher (outer/other) level provides it as a form of extraspection and makes it available to the introspecting level.

Multidimensional Ideas In Single-Dimensional Towers

The full meta-tower system described above may seem far more complicated than is necessary to describe interpretation. So what is its relevance here? It first comes into the system as a way of making the meta-evaluator accessible just as the rest of the system is; but having been introduced, it finds further use in explaining the nature of ordinary reflection, and for explaining the meaning of types in a tower of meta-circular reflection (as explained in typechap).

The two-(or higher-)dimensional tower is not just an interesting complication of the tower, but is a useful concept for designing meta-evaluators for reflective towers of one or more dimensions. Higher-dimensional towers are hard to explain without first looking at the type theory behind reflective towers, and the type theory cannot be explained without first looking further at the towers. Because of this, the following text makes some forward references to typechap, and might well be re-read after reading that .

The benefits of treating even a flat meta-evaluator as though having a tower level itself include a similarity to the standard evaluator that it mimics, and a better match of the type systems, as the requirements for the evaluator and the meta-evaluator are very similar, and may even be identical (see section 6.5). The use of reflective techniques in this research helped to design a clean, concise standard interpreter, and the same conciseness has shown through in the meta-evaluator.

In particular, the tower's model of each level, and of the links between levels, has helped to define the meta-evaluator's view of each tower level and of its access points to the tower. This is a first shift of a new orthogonal level (see section 6.5) and non-identity mappings of intensional values in and out of the first tower are useful here. These are kept to a minimum, as they involve computation instead of just copying, and so are slower than identity mappings. The mappings are really part of the meta-evaluator, and not visible to the procedures within the tower unless made available by the meta-evaluator. This strictly one-sided mapping ensures that while the tower can inspect itself absolutely completely, it has no access to the meta-evaluator, other than that which the meta-evaluator specifically provides. Thus, the appearance of the tower to itself as infinite and enclosed is utterly maintained. Here, use of the reflective model of level-shifting evaluation has been made explicitly, to prevent reification from occurring at a particular point.

This way of designing the meta-evaluator leads to the meta-evaluator being very similar to the normal evaluator, but extended to handle the level shifting. It is a significant, and pleasing, discovery that the difference between the standard evaluator and the meta-evaluator is remarkably similar to the standard evaluator itself (or rather, to the difference between the standard evaluator and the identity function)---there is a correspondence, perhaps even an isomorphism, between interpretation itself and level-shifting, as both implement the injection (or extraction) of meaning at one level by the level above.

Unidirectional visibility is provided automatically, as an evaluator always sees its structural field. The other side of intervisibility---the structural field seeing the evaluator (and therefore the evaluator being within the structural field of the evaluator's structural field)---is only possible if given by something that already has that evaluator within its structural field. This something may be the evaluator's evaluator, or the tower's meta-evaluator---or it could simply be any single operator at such a level.

This point is re-iterated several times in this thesis, at several levels of meaning; it is central to understanding the meaning of reflection, and also to the implementation of reflection. What matters is not the infinite regression, nor even the shadowing (see section 4.4) but that reflection in level n can be provided only by level n+1 (for flat reflection) and tower reflection of level n+1 into level n can be provided only by level n+2.

What Does This Architecture Allow Us To Do?

Using this model of interpretation, we can change the way that a program is interpreted, in accordance with a simple, consistent model---very distinct from the traditional type of self-modifying program. These changes may be composed systematically through the order in which the changed interpreters are installed in the tower.

The reflective nature of the interpreter makes it possible to implement such language features as variable length argument lists through an orderly model of access to the state and code of the program and its interpreter.

It also provides, through giving procedures access to the program, a generalized form of Lisp's fexpr mechanism---procedures which do not evaluate their arguments automatically---and thus may be used to define language constructs (``special forms'' in Lisp terminology). This makes possible the addition of language constructs by procedures at the same level of interpretation as the program in which they are to be used.

The fexpr-like facility is one way in which reflective interpretation can be used to define language features. Another facility is that for changing the underlying method of interpretation, independently of changing individual constructs; for example, tracing might be added, or the implementation of variable lookup changed. How this is separated from the definition of individual constructs is described in mixlangchap.

One way in which systems based on such reflective meta-towers differ from many languages and their implementations is that everything in the system is a first-class value---even such things as languages may be passed around and manipulated just as, for example, number may in many languages. This removes (or allows languages to allow programs to remove) many of the restrictions that many languages impose. In effect, it allows each language to be its own meta-language.

The multi-dimensional form of reflective interpretation allows the same things to be done to the tower implementation mechanism (meta-evaluator) that reflective interpretation allows for the interpreter implementation (evaluator). While perhaps not adding as much useful functionality as the first dimension, this does enable further control over the system; but possibly more significantly, it explains how reflection in the tower works by relating it to something more general and more powerful, and also and also clarifies that it is neither the number of levels nor the number of dimensions that matters, but whether a particular transfer of information or control is moving inwards or outwards in the towering system.

This gives us a new tool for looking at the symbol grounding problem in the context of procedural language interpretation. Accepting that no system can ground itself (an interpretation of Gödel's incompleteness theorem) it provides not only a model for moving towards and away from the ground of the system, but it also describes grounding of one tower in terms of another tower, which we treat as being grounded itself---an expression of Turing's ``oracular computability'' [Turing 37], in which, for each tower, the tower of its meta-evaluator is the oracle. With this description of groundedness as being only the concern of two adjacent level (or strings of levels, see diagram on here), we can describe it in terms of the first meta-level that can describe the relationship between the two levels concerned.

Summary of Links Between Levels

The tower of interpreters is made up from links between adjacent levels of interpretation. Reification and reflection are complementary operations, and they use complementary links between tower levels. Since both links are set up by parts of the calling mechanism, they always occur in pairs. These links make a bidirectional chain throughout the tower.

Since a tower is an infinite structure, any computation involving all levels of it cannot terminate. An application that uses reflection and does terminate must therefore make reference to only a finite part of the tower.

Therefore, the infinite tower may be represented finitely, and it is possible to reason about how many steps of interpretation are needed at one level to implement each step of interpretation at a lower level.

To make the finite representation of an infinite string of identical levels, we make the highest part of the tower into a circle, in which the same level occurs again and again. Whenever an interpreter tries to reify the level that makes up this circle, a hidden meta-evaluator makes a copy of the level in the circle, and passes that copy out as the reification of the level in the circle. The application can then modify the level it has been given, without upsetting the level that is still in the circle.

Thus, the infinite part of the tower is stored compactly as a circle, which is unrolled on demand to produce an infinite supply of identical levels. To the application, this is indistinguishable from there being a real infinite chain of levels at the top of the tower, instead of the circle and the unrolling mechanism.

The idea of the reflective tower and the means of reflection may also be applied to towers of towers---that is, meta-towers. Meta-towers might at first seem complicated to reason about, but an understanding of them brings a readier understanding of ordinary towers.

The design of the meta-evaluator, and particularly the mechanisms for detecting the need to unroll a new level from the circle and for unrolling the levels, are a major new development of this thesis.

N.B. the ground is at the top, and so can be used to grow computer science trees which have their roots at the top.

How The Tower Levels Are Linked Together.