The Standard Evaluator

The essential rôle of the evaluator is to evaluate the expression of a level in a context provided by the information in that level. To do this, it must

and then, if the expression is a compound expression (like a list in Lisp), it must

A very simple function proves to be all that is necessary both for interpretation of the level below it and for preservation of integrity up the tower. This presents and explains that function.

A general evaluator

The evaluator function is complicated slightly by being both an expression evaluator (like Lisp's apply) and a general evaluator (like Lisp's eval), used for example, for variable lookup. This was not the case in early stages of this work, but turned out to be the cleanest way of making control of evaluation easy to reflect into. Without this, certain changes (for example, between different forms of variable binding) would be much harder to reflect in to the system, and could even involve two levels of reflection instead of one (which potentially takes a considerable penalty from performance, as the interpreter's interpreter is interpreted by the meta-evaluator, instead of the program's interpreter). An alternative to making the evaluator be a general evaluator is to have several specific evaluators as fields of each closure; a tidy form of this is to have a map from types to evaluators---in effect a language whose operators are type names and whose operator implementations are type-specific evaluators. This map is the type-evaluators field of the closure structure, as mentioned in sections typeval1 and typeval2. It is onto this form which, after experimentation, the implementation in this thesis settled.

The structure of each level

Using the model of procedure calling described in section 3.4, we make towers in the following overall form:

where the meta-evaluator field is the procedure that makes the tower run, and the


shadow-map

s are used by the meta-evaluator as described in section 10.6, as is the standard-processor-closure. The base-level is the first level in the tower---the application level that the tower eventually interprets.

The tower component allows anything that has access to the level to access the meta-evaluator (and hence the meta-tower) of the level. This is one of several cycles of reference within the tower, that make it possible to go from one part of a reifier's result to another, as well as being used by the evaluator and meta-evaluator in evaluating the tower. The call-record-stack is the succession of saved procedure activations, which are saved as closures, and the


template-closure

is a closure which is copied when a new closure is to be made in that level, before filling in any of its slots with more specific values. For example, it has as its evaluator by default the standard evaluator of that tower.

In each level of the tower, the call stack is made up of closures, each of the following form:

The evaluator closure, the type-evaluators, language environments, the procedure- and continuation-expressions, and the


values

and lexical- and dynamic-


environment

s components of the closure are as already explained. The original is the closure of which this one is an instantiation. It is used by the meta-evaluator to find whether the closure is one that it can interpret directly, as explained in sections shiftmaplang and extintalgor. If the closure is changed by reflection, its


original

field is altered to point to the closure itself, so that, if the closure had been shadowed, it will no longer be recognized as being shadowed (since the shadow will no longer apply). The level is the level of which this closure is part. Not only does this give access to other parts of the level, but also through the level it gives access to the tower and thence to the meta-tower. The number is there to identify the closure, for the implementor's convenience. It is a reliable way of testing whether two closures are the same. The number is issued from a counter when the closure is created, and when a modified copy of the closure is made, the new one gets a different number.

The standard evaluator code

The standard evaluator is a procedure which embodies very little evaluation strategy and no language-specific features. Unlike a Lisp evaluator, it does not evaluate the arguments to the procedures that it interprets, as explained in section 7.5.

As mentioned in section 7.1, the standard evaluator is also the general evaluator. To combine the rôles of tower level evaluator and general evaluator, the evaluator switches on the type of its argument. Tower levels are processed, literals are returned unchanged, variable references are looked up in the environment, and expressions are evaluated by saving the old expression in the context level and recursing to evaluate the context level with the new expression temporarily in place of the old one. The switching is done by looking up the name of the type of the argument, in an environment (the level-type-evaluators of the


closure-level

of the closure) defining how to evaluate each type of object. The values bound in this environment are closures taking as their arguments the thing to evaluate and the level in which to evaluate it. This is very similar to languages, which bind operator names (effectively node sub-type names) to specific evaluator closures.

An earlier version of these routines did not have the type-evaluators environment, but used a single routine containing a Lisp typecase form, in which a fixed set of evaluand types were handled directly. This made it hard to change specific parts of the evaluation strategy through reflection; the new system is at a better granularity for manipulating parts of the interpreter, just as the ``environment of operators'' view of languages is easier to handle and extend than a single procedure for handling all types of expression or statement.

Here follows the code of the standard evaluator, written in the dialect of Lisp that is used as the base language of the system (see baselanguage) with the additional syntax of labels in square brackets for purposes of explanation (also referred to in a later ).

The standard evaluator itself

The standard evaluator is a simple procedure which selects other procedures to evaluate its argument according to their type. This means that it has very little evaluation strategy built into it; the strategy for each type of argument is defined in a separate procedure, and these procedures are accessed via the level-type-evaluators environment in the level---a form convenient for reifiers to change the evaluation of particular types of value.

Some of the accessor macros in the functions presented here appear to present as part of the level fields which the previous text has explained as belonging to closures. These accessor macros (such as level-language) refer to the corresponding part of the closure at the top of that level's call stack.

The defining form def-unclosure, which is explained in section 11.6, constructs a closure record, but does not close in all of the usual parts of a closure; those which are not defined at this time (such as the dynamic environment) are added to the active copy as the closure is instantiated.

The standard evaluator is called with two arguments, the thing to evaluate and the level which to use as the context for that evaluation.

It finds the type of the evaluand and looks it up in the level-type-evaluators environment of that level to produce the closure used to evaluate objects of that type. It then calls this closure. If the closure is not supplied, the evaluand evaluates to itself.

A more flexible alternative to this strategy, used in a further refinement of these routines presented at section 7.4, is for each environment to contain, as well as its set of bindings, a value to return for any unbound names. This allows the ifs and their else clauses be removed from the general evaluator and from the expression (list) evaluator, and also makes it easier to specify (and change reflectively) the default actions in these cases. Such flexibility, and fine granularity, are to be desired in reflective interpretation systems. Although the larger number of smaller procedures makes for more overhead in procedure calling, the potentially smaller amount that must be changed to implement evaluation features reflectively means that a larger amount will still be shadowed, so at a small cost to the speed of the fully shadowed system, the overall speed of reflective evaluation is likely to be better than that of the system with coarser granularity and fewer procedure calls.

The following functions are called to evaluate particular types of evaluand. They are bound to the type names by the level-type-evaluators environment of the level that uses them. Each one takes the evaluand as its first argument and the level in which to evaluate it as the second argument.

The symbol evaluator

As mentioned in section 6.3, local variables are represented not by symbols but by indices into the value list. Symbols are used for type and operator names, and to name non-local variables. It is the non-local variables that are implemented by the symbol evaluator.

The symbol evaluator handles both lexical and dynamic environments; if a symbol is bound dynamically, that binding is used, otherwise the lexical binding is used. (This is easily changed by use of a reflector to re-bind the symbol symbol in the


level-type-evaluators

environment of the tower.)

The symbol evaluator has some Lisp-specific code in it, although these features may be used from other languages, and indeed perhaps should, for compatibility. The symbol t is treated specially, as are keywords. These two special kinds of symbol always evaluate to themselves.

If the symbol is neither t nor a keyword, it is looked up in the dynamic environment, and, if that fails, in the lexical environment, which are stored in the active closure of the level. (The reference to

here is Lisp-specific, and is introduced for the implementor's convenience.)

The list evaluator

The list evaluator evaluates expressions consisting of an operator and its arguments (if present). Although its arguments are different, it is similar to Lisp's apply procedure. It also implements the implicit funcall used by Lisp and some other languages---a feature which a reifier could remove by rebinding the list entry in the level-type-evaluators environment of the level. It implements the implicit funcall by tagging funcall onto the front of the expression if the operator is not found. The current closure's language's definition of funcall will then be used to do the work of the procedure call.

List evaluation is central to the evaluator, as this is where operators and procedures are applied to their arguments.

As with symbols, a Lisp-specific feature appears: by an effect of the Lisp type system, nil appears as a list, and always evaluates to itself.

If the list is not nil, the operator name of the expression is extracted, at \coderef{operator}, and is looked up in the language of the level to produce a closure, which is evaluated to implement that operator.

Note that this is very similar to the action of the type lookup and evaluation in


standard-processor

above. The operator may be seen as being the type of the expression.

If the operator is not defined, the funcall operator is used to create a new stack level in which to try to run a function of that name. This is commonly useful, as most languages allow calls to be made without an explicit call operator; it is however to some extent a Lisp-specific feature.

The call to funcall is made by making a temporary modification to the current level with the name


funcall

prepended to the expression, at \coderef{funcall}. Such temporary changes are made using the construct with-changed-level which takes as arguments a level on which to work, a list of changes to make to components of that level, and a block of code to run having made those changes. After running the argument code, it undoes the changes made at the start, and returns the result of the argument code. It is an operator within the tower, and in the meta-evaluator, it is a Lisp macro, which is presented and explained in section 11.4. Using the existing level rather than a fresh copy has two advantages: it means that changes made by reflection within the argument code persist outside the dynamic extent of this construct; and superfluous levels are not created (they would add to the load on the garbage collector).

The string-char evaluator

For efficient access to the values list, we use string characters for the indices into it. (This is because in the underlying Lisp system this is the only distinctly tagged small integer type; we want ordinary integers to evaluate to themselves, as literal constants.)

The local variable references evaluator

String characters suffice for most variable references, but we provide a mechanism for using integers in general for this. The presence of two local variable mechanisms rather than one brings no overhead (apart from the behaviour of the environment mechanism, if that is slower for environments containing more bindings---see section 6.3), since it is just another binding in an environment.

Local variable references beyond the range of character numbers are referred to by the number stored in a local variable reference structure. This is very rarely used!

The level evaluator

This is present largely for historical reasons; various parts of the evaluator passed levels around (similar, in some ways, to continuation-passing style Haynes et al 84), but most of these are now work in other ways. The evaluator is retained as a way of splicing two levels together and evaluating the result. It is still used in calling external interpreters, where levels do meet in such a manner.

A level is split into two parts to make it appear in the appropriate form to pass back to the central evaluator routine.

The closure evaluator

The closure evaluator constructs a level using the expression and language of the argument closure (which should be kept together) and the other components from the level providing the context.

A closure is evaluated by splicing it into the current level, preserving the parts of the closure that must be kept together; the expression and the language must match because the expression is written in the language.

The essence of interpretation

The functions standard-evaluator and


eval-list

, roughly equivalent to Lisp's


eval

and apply, are very similar in structure, and a symbol evaluator (shown here for a slightly simpler system) can be constructed that is very similar to these two.

By extracting the common parts of the procedures, It is possible to construct a procedure which performs any of their functions, being passed as arguments suitable structure accessor procedure as well as the arguments for any of the procedures above.

standard-evaluator is the general evaluator, which selects an evaluator according to the type of its argument.

If called with an evaluand of a type for which there is no evaluator defined, the evaluand will typically evaluate to itself, the level-type-evaluators environments returning the identity function as the unbound value.

The in-line insides of the previous form of the evaluator have been replaced by a call to a function very similar to the old in-line code, but parameterized to allow them to be used in other ways in the evaluator. For reasons that may become clearer later, this function is called the boojum function:

The arguments thing and level are as for the evaluator presented earlier in this . The two extra arguments are structure or attribute accessor functions: selector selects an attribute of the thing to evaluate, which is used as the key for finding a more specific evaluator; and env-selector finds a part of the level in which to use that key for lookup.

Unlike the evaluator presented earlier, there is no explicit default case handling (for example, for types of evaluand for which no evaluator is defined). This is provided by having the


lookup

function return a suitable default value on being called with an argument that is not bound in that environment. This is a property of the environment used, and requires the environment system to allow the unbound value for an environment to be specified as part of the environment.

eval-list evaluates parse-tree nodes consisting of an operator with a (possibly empty) list of argument sub-expressions. The unbound value in level-language environments should be the funcall function---which can look much like eval-list above:

The symbol evaluator is defined without using


boojum

, although it could use it:

This only allows for one environment, rather than the dynamic and lexical arguments of the evaluator above. However, they could be provided by binding each name to a function that must be evaluated to return a value (functional representation of environments, mentioned in section 6.3, is sometimes used in experimental Lisp systems[Danvy And Malmkj&Aelig;R 8?]), and having a the unbound value in the first environment return a value that makes a call to the lookup in the second environment. These functions may, of course, be based on calls to boojum.

The rest of the functions do not have any need to call boojum, and are just as in the other version of the evaluator.

In all the evaluator code using boojum above, only the following functions are used:

Most of these are structure accessors, so if we regard those as being just two operators (type-of being distinct from normal structure accessors), this reduces it to

which is a total of six distinct operators, of which two (funcall and lookup) could be fairly complicated, and the rest are very simple.

It is my contention that the boojum function represents a refined principle of interpretation, going (in terms more from philosophy than from Lisp) from a value of some kind to a description of how to find the meaning of values of that kind, and applying that meaning function to the value, in context, to reach the meaning. It is, in fact, a form of the essence of sentence, which, on further reflection, may be also the sentence of essence.

Evaluation strategies

Because the evaluator is parameterized by the rest of the closure of which it is the evaluator, the code presented in section 7.3 is all that the structure of our reflective system requires of the evaluator (other evaluators may add features such as tracing, but the skeletal function is the same). The evaluator does not, by itself, do recursive descent of the expression tree. Sub-expressions are passed to the evaluator (generally, but not necessarily, the same evaluator) by the operator definitions when they need their arguments evaluated. Note that, unlike Lisp, we do not evaluate functions' arguments for them automatically. The evaluation is more like Lisp's special form evaluation. This is because, while for function definition it is normally desirable to have the arguments evaluated, here we are defining language constructs, and will usually require more control over evaluation. Conditionals are the classic example of a construct with such requirements. An alternative to this evaluation strategy is to quote argument sub-expressions, with quotes that are not stripped by evaluation---the handles of 3-Lisp [Smith 82]. These two strategies are equivalent, since the stripping of handles is done by explicit evaluation. For convenience, Lisp-like evaluation for defined functions may be introduced by a suitable function-defining macro (see section 11.6), which inserts the argument-evaluation code (see section 7.7) at the appropriate point.

The evaluator as a link between levels

The evaluator links the parts of a level, since it is the part that calls the other parts. The linking is as much a protocol between the components as an active part of the computational mechanism. Since the evaluator of one level runs at the level above, it also determines the protocol for communication of information and control up and down the tower.

It would be possible to have levels of a different form in a tower, so long as they support the same protocol. In this case, the only requirement on each interpreter level is that it must provide an evaluator that can be called to interpret the level. For consistent support of reification and reflection, each tower level should use the standard format of closure in full.

Relaxing the rules to require only the maintainance of interpretability along the tower allows greater diversity. For example, a level written in a language difficult to represent with a parse tree and an environment of operators could use some other form of closure, as long as that closure has an evaluator, and can process the level below.

Since such non-standard closures do not allow the level above them to provide reification data of the commonly expected type (that is, a normal closure), they spoil any assumptions about the universal applicability of the operations we provide for the handling of closures. The usual form of closure appears to be flexible enough, and we will refer to that form only from here on.

How lisp-like operators evaluate their arguments

The operators that always evaluate all their arguments (just as Lisp functions do) may do so by calling a general expression evaluator provided in the system, that evaluates all the argument sub-expressions of a given expression---that is, all those other than the operator.

To evaluate each argument, the evaluator of the current level is called. This is done through the form evaluate-by-evaluator-of-level, which in practice allows a short cut to be taken in common cases of the evaluation. This form is presented at section 11.4.

The argument expression evaluatoris provided as an operator in the base language in Platypus. For efficient execution, it is shadowed by a corresponding procedure in the meta-evaluator. Its code is as follows:

This may be called by operators which require all of their arguments evaluated in left-to-right or unspecified order. For example, arithmetic operators typically will do this. The actual evaluation of each expression occurs at [eval], which evaluates a sub-expression in the context of the current level, using the standard evaluator, which is assumed to be available as an operator (or a function substituting for an operator) in the level. The results of the evaluation are pushed onto a consed stack, and this is reversed to make the overall result, which is a list, leftmost sub-expression's result first, suitable for use as the last argument to a Lisp apply call.

Operators requiring explicit control of sub-expression evaluation may call the same function used by [eval] directly:

Summary of the standard evaluator

The evaluator is the kingpin of a level. It links the parts of the level to each other by using them to evaluate the level, and links adjacent tower levels by making it possible to shift data from one level to another. Its form is tied to the form of the tower level type.

Each evaluable infinite tower (in the scope of this thesis) eventually reaches a repetitive stage (termed the boring stage by [Smith and des Rivières 84a]), the procedure running in each of these identical levels being known as the standard evaluator level.

The standard evaluator is a fairly small and skeletal procedure, needing, in its most refined form, only six operators in its definition, most of those being for structure handling. The rest of the evaluator is defined separately, partly in individual operator definitions, and partly in some general evaluator procedures that may be called by operator definitions. These general procedures are used for evaluating arguments to operators. To do this, they invoke the evaluator and language mechanism to do the evaluation in the appropriate context.

The concise form of the standard evaluator may be seen as a distillation of the essential matter of a programming language interpreter (independently of any particular language). This may be refined further to a procedure which implements several of the main parts of the evaluator. This procedure consists of three procedure calls and one environment lookup.