History and future; related work; observations

Reflective systems have grown in part from a desire to make a tidy but practical model for the meaning of interpretation, and in part from the need for powerful language and program development and debugging tools. Systems such as SmallTalk [Goldberg and Robson 83] have demonstrated the usefulness and flexibility of reflective interpretation, as well as its practicality, while systems such as 3-Lisp [Smith and des Rivières 84a] have shown their power and expressiveness.

As the results of this thesis, and other work on reflective interpreters, have shown, implementation of reflective interpreters is now established as feasible and reasonably efficient.

Other recent developments in interpretation

Reflection is one of a group of computational techniques that have been explored recently. Others include partial evaluation (mixing) [Jones, Sestoft and Søndergaard 87] and abstract interpretation [Mycroft 81]. All these techniques are to some extent applicable to a variety of language styles (algorithmic, functional, logical).

Possible further work

Tower implementation

Many variations are possible on the theme of Platypus-like reflective language implementations. Some of these concern implementation details, in particular the mechanism by which an object in one tower is connected to any shadow that it may have in the next meta-level. The possibilities here include

Meta-towers

Platypus89 implements one dimension of meta-towers, but does not go beyond the omega^2+1 tower. This would be a simple experiment, but should probably be done in conjunction with making Platypus89 more efficient. Work with such a system might well await the development of a better user/programmer interface to reflection, perhaps with graphical output to draw towers.

Better integration with the substrate language

Full implementation of meta-towers would fall out naturally if towers could be called as if they seemed to be ordinary Lisp functions to the substrate Lisp system. It might be possible to represent them as Lisp closures for the substrate system, so that they would become callable.

It would be possible for a tower reflective system based on a substrate language such as Lisp (with incremental compilation) to make new primitives by compiling functions defined within the tower by calling a primitive operator that calls the native system compiler to make the shadow definition, and installing in the language and the shadow map to make it accessible as a real primitive. (The usual rules for when it is run as primitive and when it is interpreted will apply.)

Further applications of reflection: reflection with mixing

It is in principle possible to use the architecture described here to build an interpreter mixing system using some of the ideas from [Jones, Sestoft and Søndergaard]. With our simple and regular program and language architecture, we can make this much simpler than the partial evaluator presented by [Jones, Sestoft and Søndergaard]. This results not in a full mixer function, but in a compilation system; for each node of the expression tree, we expand the node out using the operator definition closure for that node---an inlining of the operators. There are two notable restrictions on this operation: the procedure being compiled must not change its expression reflectively; and all the operator definitions must be in the same language as each other, since the resulting closure will be in the language used to define the operators, and each closure is allowed only one language. (This second restriction may be relaxed at the cost of having to merge several languages, with automatic renaming of operators where necessary.)

If operators are provided to escape entirely from the meta-tower system down to the real substrate system (in Platypus, this is Common Lisp), it should be possible to generate real compiled code from any executable procedure (that is, one using only grounded definitions) that does not reflect into its expression or interpreter, by repeated substitution of operators as described above, until operators shadowed by the real substrate are reached. At this point, code in the real substrate language may be substituted (possibly from the shadow definitions, but it may be necessary, or at least better, to have other code for this), and the results passed to the substrate's native compiler. The result of this compilation may then be put into the appropriate shadow maps, if it was generated from a closure used as a type-evaluator or as an operator.

Using these techniques, a program-tuning system could be written, that runs a program (possibly its caller) on an interpreter that does time- or call-counting- profiling, then arranges for new primitives to be installed, if possible, to make that program run faster.

Register-based implementation

It is possible to compile reflective programs to an abstract machine code, or to real machine code using a model of execution suited to reification. A register model that might be suitable; it could have a group of working registers similar to those of the SECD machine [Landin 63], and reification would read from those registers, and reflection write to them. A possible set of registers is:

This model allows reflection to take place as in Platypus, but can potentially run faster. It may be possible to compile the standard evaluator down to real machine code, using real machine registers for the abstract registers listed above. Many modern computers have enough CPU registers for this to be possible, and I propose to follow this line of research further.

Another use of compilation with reflection is for producing more efficient versions of programs that were developed using reflective interpretation.

Object-oriented programming

I have deliberately avoided the object-oriented style in developing Platypus, particularly for Platypus89. This was to emphasize the point that reflection and objects are completely separable---Platypus works in terms of values rather than objects. This point having been made, it would be interesting to use an object-based style in implementing such towers. On a Lisp substrate, such as Common Lisp with CLOS (the Common Lisp Object System) this would provide a simple way of integrating the tower with the substrate Lisp, as towers could simply be a kind of self-evaluating object.

Efficient use of heap

Platypus generates all stack frames on the heap, which results in a high turnover of heap storage. This problem is to some extent in all reflective interpreters, as any function may have its stack frame returned as a result. It has been solved in practice in some SmallTalk implementations [Moss 87], which try to use real stack frames whenever possible, and convert them to heap objects as needed. Platypus could be modified to handle stack frame generation more efficiently.

A more thorough theoretical framework

The complexity theory describing meta-tower evaluation could be developed further, and could be extended to include the complexity of the shadowing mechanisms, thus describing the evaluation time for whole meta-towers.

Lexical and syntactics aspects of languages

As presented here, Platypus requires programs to be presented in the form of parse trees, represented as Lisp expressions (although it does include a modification of the Lisp parser, to read PostScript). A natural extension would be to include a facility for defining the lexical and syntactic aspects of a language to a flexible parsing mechanism, which would be able to read programs in the conventional syntax for their language, into the internal parse-tree form. The techniques for this are already well-developed [Lesk and Schmidt 75] [Johnson78] but are not usually fitted into a Lisp-type framework.

Ideally, the parser control system should allow the listing of programs from the internal representations into the usual textual format, for debugging. In some cases it may be possible to print out in one language a program that was originally read in another, which, in a mixed-language system, allows programmers to read routines listed in a backtrace, for example, in the language with which they are most familiar. The ability to do this depends on the rôles of particular operators being recognized---which, as longs as the procedures preparing the parse trees try to use base language operators where possible, may be quite straightforward.

A systematic framework for syntactic analysis could be provided, perhaps using a mechanism like the ``source code transformations'' used by some compilers, including some Lisp compilers. These might also be used to effect partial compilation, and be linked closely to operator definition bodies for interpreted operators.

Higher-level tools

Reflection has been used in conjunction with inspection tools, such as the SmallTalk browser system. This is suitable for flat reflective systems, but tools working at a more abstract level may prove necessary for working with full towers and meta-towers. In particular, the amount of information available can be overwhelming, and some means of focussing interaction on particular parts of a meta-towering system may be necessary, and, with that, means for navigating around the meta-tower.

Further applications

Reflection has so far been used largely within the field of programming language research, and has not been applied significantly to other areas of Computer Science. Fields in which it could prove useful include:

Summary of history and future

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:


The thing that hath been, it is that which shall be; and that which is done is that which shall be done; and there is no new thing under the sun.

Is there any thing whereof it may be said, See, this is new? it hath been already of old time, which was before us.

There is no remembrance of former things; neither shall there be any remembrance of things that are to come with those that shall come after.

Ecclesiastes 1:9-11



Submitted, Examined And Accepted: 1991
Contact me