A model meta-evaluator

Having already described the standard interpreter we now look at a model for the meta-evaluator. The meta-evaluator stands in for an infinite string of meta-circular standard interpreter levels, and in so doing implements the entire first dimension of the tower. To do so, whenever it is about to call a procedure---whether that is the evaluator, a type-evaluator or an operator---which is shadowed, it must call the shadow procedure (which runs in the meta-evaluator's own level, but performs actions as though it were in the meta-evaluatee's level) instead of the original procedure.

Requirements for the meta-evaluator

There are two major requirements for the meta-evaluator:

Since we are not requiring it to conform to the structure of a tower level itself, we can observe that

Most of the operations of the meta-evaluator will be directly equivalent to those of the standard interpreter, and the forms of the two will be similar. Reflective operations do not translate so directly into operations of the meta-evaluator because they do level-shifting, which is not possible when there is only one level. The operations which cause level-shifts in the standard interpreter must translate to non-reflective actions in the meta-evaluator.

Thus, we have the mappings:

All these actions affect variables of the meta-evaluator, which represent the state of the tower. The meta-evaluator has one important variable, let us call it *tower*, whose value is the tower which it interprets. This is the argument with which the meta-evaluator was called.

A non-reflective operation in the tower works on the contents of the base of the tower. For example, arithmetic operators handle values in the values element of the current closure at the lowest level of the tower, and flow control operators affect the stack of sub-functions (sub-expressions) implicit in the expressions elements of the stack of closures at that level.

Reflective operations may change the contents of the tower more significantly. For example, the grand-jumpy-reflector operation sets *tower* to a fresh value that has been produced from somewhere within the (old) contents of *tower*. Likewise, grand-jumpy-reifier assigns to a location (such as the value part of a variable binding) stored within the current value of *tower*. These may be used, in conjunction with a stack in the meta-evaluator, to implement pushy reflection.

This description would suffice were the meta-evaluator to be positioned at the end of the tower. A lightning bolt [Smith 82] is needed to reach from the top of the tower (where the ground is) toward the base of the tower. This must cut through the infinite repetitive (boring) section of the tower:

meta-evaluator at end of tower

However, as well as being at the infinitely remote upper end of the tower, the meta-evaluator has to be alongside the whole tower, so that it can reach through the infinite section of the tower, to shadow things at the lowest level at which it is possible:

meta-evaluator alongside tower

The lightning here travels along the tower through the meta-evaluator, which can conduct it from one level to another as needed. As already discussed, it strikes the highest point on the tower that is not mimicked by the meta-evaluator; before this, it is just travelling through open space, and does not touch anything.

Because of the meta-evaluator being beside the tower, its connection to the tower is more complicated. Indeed the tower is more complicated than that, as it has a castle of towers arising from the operator closures in the language of each level, thus:

Branching Tower
where, at any one time, exactly one of the towers drawn small on the diagram---the one starting at the closure for the current operator---is active.

The following diagram shows that the meta-evaluator is alongside everything, and that it contacts (shadows) any tower in the castle wherever a tower in that tree reaches meta-circular standard interpretation:

Branching Tower And Meta-Evaluator
Here, the meta-evaluator brings the lightning's power to any part of the tower, whether in the main tower or in a side tower.

An introduction to platypus

Platypus is a non-reflective, single-language implementation of a reflective, mixed-language interpreter. (Its name originally stood for Practical Language Algebra with TYpes, Procedures, Unification and Sending, although the latter two features are not implemented in this version of it.)

There are now three implementations of Platypus: an early prototype written in Cambridge Lisp, a version in C written for speed, and a more readable and concise version in Common Lisp. Both of the latter two are referred to below. Example code throughout the thesis is drawn largely from the Common Lisp implementation, Platypus89.

Platypus is a shadowing interpreter, as described in sections shadowidea and shadowint, and has to implement:

The pull of efficiency

My thesis is that the reflective facilities described can be implemented efficiently enough (compared against a conventional system) that a programming system using them is useable in practice, at least for prototyping. Hence the intensively used parts of Platypus are written with efficiency in mind. It is also essential that everything required in the reflective system is provided correctly---correctness cannot be compromised to gain speed. Therefore, there is a division of Platypus' internals into two parts:

This division is particularly noticeable in the C version. In Platypus89, the equivalent procedures inside and outside the tower could be produced from the same source, with one branch being held as a lambda-expression inside the tower, and the other compiled to machine code by the substrate Lisp system. (In practice, the sources are similar but not identical for most of the code, for historical reasons. Some of the compiled code is generated mechanically from the non-compiled code definitions, particularly for Lisp-like functions that evaluate all of their arguments.)

Representation strategies

There are two ways in which we could store tower components:

In all versions of Platypus, to be sure of the correct representation of reified state to the application, we use the former approach: everything is pre-reified---only ever kept in its reified form---rather than reified on demand. This means we that have to write the meta-evaluator to handle all the reifiable structures in their reified form throughout. The only values which are not always kept in a reified form are those that have no reified form, such as the internals of file stream descriptors.

In practice, it turns out that this works well; representations suitable for use with reified data are also suitable for use by the evaluator and meta-evaluator, and there are no points at which some other representation would have been obviously more suitable.

However, were translation at reification and reflection to be used, it would occur at very specific points (the reifiers and reflectors). Much of it would be simple, although there are possibilities for complicated reifiers and reflectors, ranging from building of reified stack frames to de-compilation at reification and compilation at reflection [Watson And Tillotson 89]. Because of the translation occuring at such well-defined places, the possibilities for errors introduced by this feature are restricted, and the possible effects on the rest of the system are reduced.


Objects in the tower world that have special meaning to the meta-evaluator, such as the closures representing functions which the meta-evaluator evaluates directly itself, must be mapped onto the corresponding objects in the meta-evaluator. In the C implementation of Platypus, this mapping is done by a pair of hash tables, using a perfect hashing scheme---that is, hash table lookups take a constant time. This is made possible by special allocation of memory while initializing the system (see section 11.7), such that there is something special about the addresses of the heap objects that have special meanings to the meta-evaluator.

The more significant of the two hash tables in the C implementation, as far as reflective interpretation is concerned, is the operator map. This maps from objects inside the tower to functions in the meta-evaluator. If the object is a closure representing a primitive operator, that is, one which is shadowed by the meta-evaluator, and is being called from the standard evaluator, this mapping succeeds and returns the meta-evaluator function. If the object is not a primitive operator closure, it is mapped to a distinguished null value.

The other hash table, called the location map, is concerned with garbage collection. It is used to update C variables pointing to distinguished heap objects (such as nil) as the garbage collector moves things around.

In the Common Lisp implementation, Platypus89, the hashing for the operator map is done by normal Lisp hash-tables. There is no location map in this implementation, as we use Lisp's garbage collector, and all levels share one conceptual undivided address space (and type space!), and so our meta-evaluator variables pointing into the tower are updated automatically as part of the normal action of Lisp's garbage collector.

The meaning of the map

As mentioned in section 10.6, the operator map is in some ways analagous to a language. Just as a language maps operator names (which are symbols, or tokens) to operator closures, the operator map maps operator closures at one meta-level to those at another.

Now, since the meaning of a name is not inherent in the name, but only in the context (environment) in which the name is de-referenced, any kind of value (such as an operator closure) may be used as a name. Thus, both operator maps and languages translate operator names (operator extensions) of some kind to operator closures (operator intensions) so that the intension of the operator may be used to fulfil, in that context, the extension of the operator.

How the meta-evaluator works

Meta-circular calls to the standard interpreter are recognized with a single comparison operation. When the meta-evaluator begins to evaluate a level, it compares the evaluator of that level with the standard evaluator.

When the meta-evaluator is interpreting a level directly, each time it tries to apply an operator or type-evaluator, on behalf of a standard interpreter level which it is shadowing, it first looks it up in the appropriate map.

This is almost identical to the action of the standard interpreter within the tower, except that there is a conditional level-shift in a one-level-deep second tower dimension, and when this level shift is taken, the operator or type-evaluator shadowing map is used much like a language.

The actions of the C and Lisp implementations are very similar. As far as the ideas of reflective interpretation are concerned, they are equivalent. In the implementations, the main difference between the evaluators is in the mapping mechanism---and this is a small difference, and in either implementation, it could be done some other way. The most notable difference between the substrate systems is that Lisp provides a lot of useful things (such as memory management) that had to be written into the C version directly.

Summary of the model meta-evaluator

The boring part of each tower is not really evaluated, but its evaluation is mimicked by the meta-evaluator of that tower. The meta-evaluator has two rôles: it implements finitely the infinite tower, and it stands in for any number of levels.

To do this, it has to be able to absorb level shifts, to stop them going any further along the tower. It does this by realizing new levels, (and abandoning old ones), on demand, when it must extend the non-boring part of the tower, and shadowing things itself when still on the boring section.

The code of the meta-evaluator can be similar to that of the standard evaluator, with the addition of some level-shifting code that would not, within the tower, be allowed to exist within a single level, because it is capable of generating (realizing) levels[1].

The meta-evaluator is alongside the tower (from the tower's point of view) and both alongside and above the tower (from the meta-evaluator's point of view).

The meta-evaluator runs beside the lowest tower level that it can, that is, one level above the highest one that is not mimicked by the meta-evaluator. It follows this boundary by climbing up to new levels as it realizes them, and climbing back off them when they are no longer needed.

There are two approaches to how the meta-evaluator should view data within the tower, in terms of how each type of data is represented, and whether each type appears as the same type inside and outside the tower, or as distinct types. In this thesis, we hold the data in the same form in both, and hence, for example, stack frames do not have to be re-encoded when reified or reflected.

The meta-evaluator must have a map from shadowed operators in the tower to shadowing operators in the meta-evaluator. In a system with only one dimension to the tower, this map must be visible to the meta-evaluator but not to the tower.

If the meta-evaluator implements the storage system of the tower, it must also have a map from distinguished objects within the tower to variables in the meta-evaluator. If the meta-evaluator and the tower share a storage system, such a map is not needed.

``And part of the roof came off, and ever so much thunder got in---and it went rolling round the room in great lumps---and knocking over the tables and things---till I was so frightened, I couldn't remember my own name!''

The White Queen, Alice Through the Looking Glass, Chapter 9


  1. Within the tower, each procedure may be in only one level at a time.

Submitted, Examined And Accepted: 1991
Contact me