This chapter is composed from the summaries that appear at the end of each chapter.
The mechanisms of program interpretation may be analyzed into several areas, some of which are currently active research areas. These include program transformation, partial evaluation, reflection, and mixed-language programming. This thesis concentrates on the latter two.
Reflection---the causal link between actions of a program and its state, text, behaviour and environment---combines ideas from interpretation theory, logic, mathematical philosophy, linguistics, compilation, abstraction and other fields of Computer Science. It also contributes new techniques which may be used in these, and other, fields.
Mixed-language working is already common practice, but has not been formalized. Its existing use argues strongly for its usefulness, and the limitations on its present use, and its current haphazardness argue for further development of the ideas underlying it.
In common between these fields is the systematic definition of programming language interpreters, and the idea of provision of meaning for a value in terms of the context surrounding it (including its interpreter).
Reflective techniques are based on two facilities: reification, by which a program may examine its own code, state and interpreter; and reflection, by which it may modify any of these. The connection that reflection makes between a programs actions and its behaviour is causal in nature: modifications that a program makes to its interpreter may cause changes in the way that the program is interpreted.
Some programming languages, not normally regarded as reflective, provide a limited range of reflective operations, such as access to the parameter list of a procedure call. However, in a fully reflective program interpretation system, all the features of any programming language can be implemented through reflective programming in the program, thus removing the distinguished status from the interpreter of a language, and making it equivalent to any other program in the system.
There are two kinds of reflection: simple reflection and tower reflection. Simple reflection provides a program with access to its own code and state and interpreter. Tower reflection also provides it with access to its means of interpretation---that is, the mechanism by which a program is related to its interpreter, and thence to its interpreter's interpreter, and so forth. Tower reflection is more general, and, not having an arbitrary stop after the first level, is a more regular conceptual structure. Thus it is a more powerful tool for reasoning about intensional reflection and about interpretation.
Although tower reflection deals with infinite structures, it is possible to implement it with finite constructions. This thesis explores the infinite towers and their finite implementations, and investigates whether an interpretive programming system built this way can be made reasonably efficient, compared with conventional, non-reflective interpreters.
In this thesis, we develop a reflective tower implementation, called Platypus, and use it to demonstrate many of the points discussed.
At each level in our infinite tower, there are one or more procedures, of which at any one time one will be active, and some (possibly none) will be on a list of saved procedure evaluations to be returned to.
In common with many other language systems, we represent procedures by closures, each containing the code of the procedure and any context that must be carried with that code to interpret it.
To make explicit the interpreter of a procedure, we close over the interpreter when constructing the closure of the procedure, and thence the rest of the tower of which that evaluator is the lower end, thus making it contain the whole of the context in which the procedure is interpreted.
A closure constructed this way we call an interpretive closure, since it encloses all the information needed for interpreting a procedure.
We use interpretive closures as the building block for constructing reflective interpretive towers. Each level of a tower contains a closure (actually, a stack (or list) of closures). The interpreter of an interpretive closure is also an interpretive closure, as are the operator definitions. Closures are also used to represent procedures available for calling. When a procedure is called, its closure is instantiated by copying in onto the top of the stack, and filling in fields that come from other parts of the level and the tower (such as the dynamic environment within which it was called.)
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.
As well as being a reflective system, our system is a mixed-language one, making reified languages into part of the evaluation data that is available for manipulation by application programs running on the system.
To make the language a variable part of the context of a closure, we divide the interpreter into two parts, the evaluator, which is language-independent, and the language.
To do this, we need an abstraction for languages.
The abstraction must be general enough to handle
most languages reasonably well, and to handle all
languages to some extent. Such an abstraction can
be devised only in conjunction with an abstraction
for the programs in the languages. For the
programs, we choose to use parse trees, with each
node being identified by its operator such
as if or +, and for the languages, we
use environments binding operator names to
operator definitions.
This abstraction makes it easy to add new operators to a language, and also keeps separate the general evaluator, thus making it possible to redefine the evaluator independently from the language.
By making the language (the environment
binding operator names to operators) of each tower
level an explicit part of that level, we extend
tower reflection from being a tool for reasoning
about interpretation of programs to also being one
for reasoning about languages and their
interpretation.
The ideas behind the towers' type system are important in understanding tower reflection. Types are an essential part of the way we represent values, and the mapping from one tower level to the next is a representation of a value in one system by a value in another. The basis for representing values in a computer is Gödelization, in which digits in numbers denote words in a language.
The type system we use must allow the representation of procedures and of procedural evaluation, as well as the representation of the application's problem domain. It must also be possible to represent the infinite towers and meta-towers used in reflective evaluation.
The system must provide operations on types concerned with reflection (that is, types for objects representing parts of the tower) as well as for the types of objects normally handled by an interpreter. We divide types into two kinds: simple and compound.
A few types are of particular importance in a reflective tower. Closures are the central type. Other important types include expressions, environments and value lists.
As information is moved between levels, its representation may be changed, although in Platypus it is not changed. The meaning of the same information may be different at different levels even when the representation is the same.
Although the meaning and representation of information does not normally change between levels of a normal tower, it may well have to change in going between the tower and the meta-evaluator that implements the tower.
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.
Our mixed-language interpretation is designed to allow many languages to be built on top of it. Languages which can be converted readily to a procedural form are most suitable for this: procedural and functional languages are easiest, declarative and rule-based languages are harder.
We assume handling of such types as numbers to be made available underneath the implementation of reflection. Reflection does not help to describe these, anyway, so nothing would be gained were it possible to include them in the reflective system.
Most conventional language features map readily onto a reflective mixed-language architecture. Occasionally there is a mismatch, such as it being natural to try to make all calls reflective (which builds a tower level for each procedure call).
Using jumpy reflectors (that assign to parts of the state, without saving the old values on a stack) to change specific parts of a tower allows very natural implementation of many common language features such as jumps, calls and assignments.
Reflective features may be used to group together parts of a system, such as all the operators of a language, for interpretation in a particular way.
As well as any languages implemented on top of the reflective system, there is a base language which provides reflective facilities and some simple flow control and calling operators. This is sufficient for running the rest of the system, so long as all parts of the system are connected with integrity to the base language.
Reflection allows new features to be added to conventional languages, including extreme examples such as a non-local exit that goes right out of several levels of interpretation.
Procedure calls are to some extent built into the evaluator, but other features are not so much so. Our procedure calling is naturally call-by-name, but call-by-value may be implemented easily on top of this; such a facility is provided in a form that is useful to many language implementations.
A language for use with the standard interpreter in the boring section of the tower must be powerful enough to support both the standard interpreter and the procedures that will run on it, which will typically be operators for other languages.
The implementation of the base language has two parts: the operators themselves, and their shadows, which are run at the next meta-level in the tower. (The last meta-tower is run in the substrate language on which the whole reflective system is built, and it is there that all operator definitions are eventually evaluated.)
The language should provide operations typically needed by interpreters, and those needed for reification and reflection. It is also desirable that the base language be reasonably expressive.
As well as the fundamental reifiers and reflectors, it is convenient to provide some jumpy reflectors that assign only part of the state; these are not only more efficient, but also more expressive of many common language features that they may be used to model.
In practice, we provide many more operators in the base language than are strictly necessary. ([Smith and des Rivières] explains how to work out which operators are necessary.)
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.
Platypus is a trial implementation of a reflective tower-based evaluation system in which data representations inside and outside the tower are the same. It has been through two broadly similar implementation generations, one in C and one in Common Lisp.
Dynamic typing is used throughout the system, both inside and outside the tower. All objects in the tower are kept in a storage heap; in the C implementation this is scavenged by a stop-and-copy garbage collector, which must pay attention to updating variables of the meta-evaluator as it moves the things to which they point.
While several meta-evaluator variables point into the heap, it is not possible for a program in the tower to find from an object in the heap what it corresponds to in the meta-evaluator (although a meta-evaluator that makes this information available could be written).
The meta-interpreter must contain:
The meta-evaluator may be reduced to a very concise form built around one function, which is appropriately very similar to the corresponding function for the concise form of the standard internal evaluator for a tower. This function consists of four procedure calls and two environment lookups.
The code for all the shadow operator definitions has much in common; in particular, all operators that must evaluate all their arguments independently share an argument evaluator mechanism. Such operators are built around primitive procedures in the implementation language, by a macro-preprocessor, that takes functions in the implementation language, and produces wrapper functions for use as the shadow operators.
Platypus has proved to be a practical interpretive system for Lisp-like languages, and promises to be able to run at speeds comparable to other, non-reflective, interpreted Lisp systems---it is already well within the factor of ten that I chose initially as a suitable limit for regarding this new interpretation technique as practical. There is certainly promise of being able to improve the performance, and I would expect to reach speeds similar to those of non-reflective, single-language interpreters. The usefulness of dynamic typing is clearly evident, and the appropriateness of implementing reflective interpretation by shadowing has been demonstrated.
Working with mixtures of two type systems, one for the substrate language and one for the tower, was particularly confusing, and this should either be avoided, or handled with careful planning, in future work in this area.
The amount of garbage generated is a potential problem, as all stack frames are, in principle, built on the heap. The problem is reduced by using the stack frames of the substrate system to store some of the data that might have otherwise needed more frames to be built for very short-term use.
Initializing the system is complicated by the number of cross-references and self-references that must be set up. It would be useful to have some program tools for generating (or gathering) the initialization code automatically from the rest of the source code.
It is possible to produce very compact versions of both
the evaluator and the meta-evaluator, these being based
on a pair of functions, boojum and snark,
that appear to encapsulate the essence of evaluation
and meta-evaluation respectively.
Reflection is a young field of Computer Science and formal logic (and an older field of philosophy) and there is much yet to be explored in it. Enough is now understood to make an intuitive grasp possible, and, although always touching on the meta-physical, it is possible to explain it formally, although formalisms in common use today do not express reflective concepts very well.
In three main areas of research on the topic, two present considerable scope for further research, and the other presents scope for development and enhancement of ideas that are now established:
reflection is a large and very open field. Some forms of reflection have now been described and analyzed extensively, particularly those concerning procedural languages, but there is much more to be done, particularly on declarative languages.
The mathematical description of infinite reflective towers, using transfinite numbers, is an intriguing field which could be developed much further, particularly with reference to the type system needed to represent such towers.
Implementing reflective systems has been researched, to the extent that it is possible to build fully tower-reflective interpreters of similar speed to their nearest non-reflective equivalents [Smith and des Rivières 84b]. This could be developed further, and applied more widely.
Application of reflection to real logical, computational and scientific problems has scarcely begun. To date, it has been used within the area of language research, but little further.
A reasonably efficient reflective evaluation system can emulate an infinite meta-tower of evaluation, in remarkably few lines of Lisp. The most central of these lines may be regarded as a refined form of generalized or parameterized evaluator.
Perhaps somewhat fancifully, parallels may be drawn with non-computational procedural activities, such as deliberation, and learning, in people.
The reflective approach to language definition avoids the conventional route of definition in terms of something outside the the system, after the acknowledgement that no system---neither computational nor mathematical---nor for that matter those based on any other linguistic notation---can describe itself completely. An outside reference---visible to the same observer---must always be present, and we allow such a reference to be arbitrary, rather than from some denotational framework from mathematics, for which in turn the same problem of an outside reference also occurs.
Reflection and reification let programs access themselves and their interpreters as data. This access is causal in nature: modifications a program makes to its interpreter changes how the program runs.
Simple Reflection lets a program access its code and state and interpreter. Tower Reflection also lets it access its means of interpretation---that is, the mechanism by which a program is related to its interpreter, and thence to its interpreter's interpreter, etcetera.
We close over the interpreter when constructing the closure of the procedure, and thence the tower of interpreters starting there, making it contain the whole context in which the procedure is interpreted.
By making the language of each tower level an explicit part of that level---a new contribution to this field --- we extend reflection from being a tool for reasoning about interpretation of programs to being one for reasoning about language interpretation.
The meta-evaluator implementing a tower has two rôles: it implements finitely the infinite tower, and stands in for any number of levels.
To do this, it must absorb level shifts, by realizing new levels, and abandoning old ones, on demand.
We use a shadow map from shadowed operators in the tower to shadowing operators in the meta-evaluator.
The meta-evaluator can itself be a program executed by a tower of interpreters, starting a meta-tower---an original development.
Platypus is an implementation of a reflective tower in which data representations inside and outside the tower are identical. It has two similar implementations, in C and in Lisp.
Platypus has proved to be a practical interpreter for Lisp-like languages, and promises to be able to run at speeds comparable to non-reflective interpreted systems. The appropriateness of implementing reflective interpretation by shadowing has been demonstrated.
Scheme, now,
feels like Algol-60 (the world's sweetest version of Fortran), and I'd say that feel is more important than look.
Reuben_Bert_Mayo@Cup.Portal.Com