An active area of research in Computer Science concerns the manipulation of programs by other programs, and investigates the use of automatic logical reasoning systems to reason about programs. It has come to the attention of many researchers that, if it is useful for a program to manipulate, and reason about, other programs, it may be even more useful for it to be able to manipulate and reason about itself---that is, to reflect on itself.
Reflection differs from one program working on another program in one important respect: changes made by the program to itself must affect the behaviour of the program, and, correspondingly, the behaviour of the program must affect what the program sees of itself. Thus, there is a causal link between the program as agent and the program as subject. A overview of the implications of this, with a survey of some seminal work in the area, is given in [Batali 83].
To be able to make sense of a running program as a subject, we must take it in the context of
Therefore, in this thesis, we include the language and the evaluating agent as part of the subject program. Once we make the language part of the subject, we are handling languages as data values, and so can also handle systems that allow each program to be written in a mixture of languages.
By including the evaluator (or interpreter) explicitly in our model of computation, we add another layer, or level, to the interpretation; as we look further into the model, we find that the evaluator itself must be interpreted likewise, and so on, and so we add an infinite number of levels of interpretation [Smith 82]. It has already been shown [Smith and des Rivières 84b] that it is possible to implement an interpretive system for a single language using this infinite number of levels of interpretation, with little less efficiency than a normal interpreter. In this thesis, we investigate the possibility of doing this for a system with explicit and variable languages; and at the same time, in investigating further the nature of interpretation itself, we change the infinite tower of levels of interpretation to an infinite tower of infinite towers ... of infinite towers of levels of interpretation.
Though a tower of interpretation is slightly more complicated to construct than a plain interpreter, it makes it simpler to modify the interpreter later, for example to add new language features. When used as a construction kit for building mutually compatible interpreters in a mixed-language environment, the slight extra complexity is adequately compensated for by the ease of adding features and even whole languages within the framework.
Just as the tower model simplifies the construction of individual components based on it, the meta-tower simplifies the construction of the tower in a very similar way, and, since the relationship of successive meta-towers is the same as the between a tower and its meta-tower, it can also be said to simplify its own construction, through the development of a regular model for towers and meta-towers.
The implementation of a system using this model turns out to be concise and elegant, and when refined as far as possible appears to be rather simpler than the ad-hoc systems of which it is a replacement and superset.
When we include the evaluator as part of the subject of the program, we give the program access to the thing which defines the meaning of the program--and through this, the program can manipulate its own meaning or interpretation.
Since this involves operations on the interpreter of the program, the meaning of the interpreter must be defined in some way. The interpreter is a program (hardware interpreters--computers--are outside the scope of this thesis) and so its meaning is determined by the interpreter of that program. Thus, we see an infinite tower of interpreters defining the meaning of a program. For a program to inspect and manipulate its interpreter meaningfully, it must also have access to the whole tower of levels of interpretation (which, for practical purposes, come into existence only as needed--a lazily generated tower).
Reflection is not simply a programming tool, but a general model for describing a wide range of things that perform processes in some intelligent manner. While this thesis is confined almost entirely to Computer Science, it is often helpful to see the field in the contexts of psychology and philosophy, harnessing the anthropomorphising tendencies of the human mind to make useful analogies regarding self and meaning.
Since the search for the definition of the meaning of an action (process,program, utterance, trace) leads toward our projection of meaning onto a free formula---something which does not have meaning until taken in a particular context---some philosophical digression from the mathematical logic is used in places to give a meaning to the mathematics uttered.
In constructing a system for handling programs and their environments, we must draw from several areas of Computer Science, as well as adding new material concerning the causal link between action and behaviour. While using techniques from these areas, we also contribute techniques that they can use.
A program must be written according to the grammar of the language in which it is written. To manipulate programs, we must have formal grammars of the languages in which they are written.
This area has been researched extensively, and the results of this research are in common use, not only for constructing programming language systems, but also in many other areas of information processing, as all computer-manipulable information must be in a form describable by a grammar.
In this work, the grammars we use (both formally and informally) are those describing programming languages---particularly procedural programming languages. To bring a language into the system developed here, a grammar for it must be provided, describing the lexical and syntactic aspects of the language, to enable some program, called a parser or lexical analyzer, (with which we are not concerned here) to convert (parse) the textual form of each program into a parse tree or abstract syntax tree. This conversion may be a bare transliteration of the program text, or it may include annotation---an augmented syntax tree---for example, global and local variable references may be distinguished explicitly in the parse tree. Some languages, notably non-procedural, non-functional ones, may require considerable processing at this stage; for example, prolog programs could be procedurized here.
Many tools for generating parsers are available. The best known are perhaps those provided on the Unix system: Lex (a lexical analyzer generator) and YACC (a syntactic parser generator, also sometimes used to generate the main framework of a compiler). These work across the boundary between textual data processing and symbolic data processing, and both are mixtures of an existing, general-purpose programming language, C, with specialized languages. Lex and Yacc (or similar tools) may be used to complement the work behind this thesis; and the work presented here helps, in turn, to formalize the language mixtures in which Lex and YACC grammar descriptions are written.
This thesis looks very little at the lexical and grammatical levels of language processing---it is treated as being largely a separate task. However, a full mixed-language system would have to be able to accept grammatical descriptions as well as the semantic descriptions that the present system uses.
Reflective program execution is both a form of interpretation, and a tool for studying interpretation. Some techniques from writing conventional interpreters apply here; more significantly, reflective programming is a new technique for constructing interpreters, and may be used as such either by itself, or in conjunction with other techniques. It also provides a framework in which to reason about interpreters.
The reflective model of interpretation has several advantages over ad-hoc interpreter architectures. Not only does it make it possible for an ordinary program to extend the interpreter, but it also makes the design and implementation of interpreters more systematic--perhaps making it less of an art and more of an exact science.
With a well-defined model of interpretation, constructing and debugging interpreters becomes easier, and it is possible to write tools to assist in writing and testing them.
Partial evaluation is an interpretation technique in which a program is run as far as possible on the data available to it at the time, reducing it to a residual program which accepts some or all of the remaining data to procede to another residual program or to the result. Whereas reflective interpretation tends to add new levels of interpretation to the execution of a program, partial evaluation can remove levels of interpretation by combining them with adjacent levels, which is done by evaluating the interpreter with the program that it interprets as input. Thus, partial evaluation and reflection may have complementary effects on the interpretation of a program. This effect is described and explored in [Danvy 87], which explains how partial evaluation and reflection may be used together, giving the advantages of reflection, while collapsing the extra layers that it can introduce.
Compilation, like partial evaluation, reduces a program, and so in some sense opposes reflection. It is sometimes possible to compile a reflective program into a non-reflective one, thus allowing systems developed under reflective interpretation to become more efficient compiled programs.
Mixing [Jones, Sestoft and Søndergaard 87] is a form of partial evaluation that allows for self-reference by the evaluator, and, through this, allows the evaluation to specialize interpreters to run particular programs. This is a form of compilation, as it reduces an interpreter I in a language Li and a program P in a language Lp to a combined program IP, with the same meaning as P, but in the language Li. It can also evaluate itself, M (the Mix program) with respect to any interpreter Ia in language La, leaving a residual program MI that accepts programs Pb in any language Lb and produces combined programs IPa---this residual program is a compiler. Mixing the mixer with itself produces a residual program that accepts interpreters Ia to produce residual programs MIa---this is a compiler-compiler. Although this self-reference is not causal, there are some strong similarities between mixing and reflection, as both relate program and interpreter [Danvy 87].
Handling data obtained from the state of a running program requires a suitable abstraction for program interpretation; such abstractions are discussed in [Smith 82] and [Wand and Friedman]. Such an abstraction also provides a tool for further abstraction in the field, as it describes causal self-reference abstractly.
The abstraction must describe not only programs in their static form, but also the active process of running them. As it turns out, a suitable abstraction for this is reflective interpretation itself---the very feature that required the abstraction in the first place. Such cycles of reference as this are natural in this work, as the systems described and implemented include descriptions and implementations of the abstractions used in their descriptions and implementations. This goes against the traditional form of semantic definition, of which the main aim is to describe the system in terms of things outside the system itself. Here, we prefer to include a description of the system within the system, and describe how something outside the system may project a meaning onto the system, and thereby may give it an external definition. We then show how a system may be constructed that includes within itself a description of how an outside system may project a meaning onto the system.
Reflection is useful both as a tool for abstract description and manipulation of programs and other active agents, and as a practical programming tool. Active agents here can mean anything that has defined behaviour and processes information, such as a computer, a program, an organization, or an animal. Reflection describes a causal link between abstract information handling and concrete behaviour. In mentalistic terms [Batali 83], it is the part of introspection that links the self as the subject of reasoning to the self as reasoner. This works in both directions: it links observation of the self to reasoning, and reasoning to action on the self---which is part of learning. A fully reflective agent can reflect upon reflection, and can thus can observe observation, reason about reasoning, and learn about learning.
The idea of reflection is useful for describing either reflective or non-reflective interpretation of programs. It can describe programs, languages and processing agents. It describes the meaning of any of these, and, as described in this thesis and other work [Danvy and Malmkjær 88] [Smith 82], relates the extensional meaning of something---that is, its description, or what the thing means---to the intensional meaning, that is, how it works, or its implementation. It does this by putting the intension into a frame of reference which binds it to the world outside the description, that is, the extension.
In mentalistic terms [Batali 83] we manipulate our surroundings (as we perceive them) in terms of abstract concepts, a form of manipulation that is widely accepted as being deeply connected with our linguistic faculties. For example, hammering a nail involves the concept of momentum; even if someone does not have a spoken name for it, they must have this specific (and hence nameable) concept in order to understand why hammering is more effective then steady pressure applied with the hammer. Earlier work on procedural reflection allowed programs to modify their language environments but did not have a specific model for languages as data values. Here, we make it possible to reflect on languages more formally and abstractly than before.
Reflection, in the form used here, links a program with its interpreter in such a way that the program can modify the interpreter [Smith 82]. By adding new features to the language, then removing the features of the original language, a program can construct an implementation of another language, and continue to run in that language instead of the original one.
This is a novel approach to language definition, and offers interesting prospects for programming in general. Not least among the possibilities is that of tailoring a application-oriented programming language for a particular program, as part of the application program and in terms of the application-oriented language rather than as part of a separate language processing program written in a language less suited to the application domain.
This form of language implementation also makes language development and debugging more like other application development. Debugging facilities provided within the language system can be used on the language system, and new debugging facilities (for example, printing messages at points in the code) for working on the language can be inserted just as they can be into an application.
Reflection provides some useful facilities for debugging programs, such as access to the program's state as data---this data can then be passed to an inspection tools, as is done in SmallTalk-80 [Goldberg and Robson 83]. Such data can then be modified, and installed back in the program to continue running it. The routines to display, manipulate and re-install the reified data may be written as part of the application program (and thus in the language of the application, not of the interpreter), and so the debugging facilities can be presented in terms of the application domain.
Reflection opens some new possibilities; one example that has been investigated (but not found to have any important practical use) is migration [Harpaz 87]: for a program to transmit its state and data to another host computer, and continue running on its new host. It has been demonstrated that such a facility can be made machine-independent, and so can be used to make programs that install themselves intelligently on new machines.
Another possible application of reflection is explanation in expert systems, where a program can go through the code and state of its own reasoning to explain why it reached a particular conclusion. An example of a system that does this is SHRDLU [Winograd 72], a system for manipulating solid block in response to natural-language commands. SHRDLU is capable of answering questions about why it had to make particular parts of a sequence of movements (for example, moving a block to be able to pick up one from beneath it).
Since reification takes a snapshot of a running program (or returns a handle into the running copy of the program), and reflection resumes the execution of the snapshot, it is possible to take checkpoints, either in case of the program or computer crashing later, or for holding versions of a program in various useful states: for example, a PostScript program could be frozen at the end of each page (thus collecting all the global state changes accumulated by running all the preceding pages) to make a collection of programs ready to run any specific page without working through all the preceding ones.
There are two approaches to reflective interpretation:
Of these two approaches, tower reflection is a better study of the general process of interpretation, as it requires a general definition of the link between a running program and its interpreter. It is also the more powerful, as it allows successive transformations on the interpretation process to be composed (for example, lazy evaluation and program tracing).
Writing programs in a mixture of languages has been possible for
some time now, and there have been many formal descriptions of
individual languages. However, little work has been done to describe
mixed-language programming, except in some specific cases such as the
Poplog system [Hardy
82], which combines Pop-11, Lisp and Prolog. Mixed language
programming has shown its usefulness in several ways; for example, in
creating new languages which draw on features of existing language
(make using sh on Unix is a common
example); and in accessing obscure features (such as asm
statements in C; FORTRAN-based arithmetic libraries called from a
variety of languages). Some problems have solutions in which
different areas of the problems are best tackled by different
languages, for example the pic | refer | eqn | tbl |
troff combination of text processors on the Unix system, where
each of the components is good at just its own proper task, but either
weak or completely incapable in the other areas (for example, making a
table with eqn or a mathematical display with
tbl or refer is difficult and generally
inappropriate).
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).
``I should see the garden far better,'' said Alice to herself, ``if I could get to the top of that hill: and here's a path that leads straight to it---at least, no, it doesn't do
that ---'' (after going a few yards along the path, and turning several sharp corners), ``but I suppose it will at last.''Alice Through The Looking Glass, Chapter 2