^2+1As 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.
Another implementation technique is to replace the boring section of the tower directy with its shadow (as used in Platypus for meta-tower reflection), and have the procedures that move along the tower recognize this and hide it by returning instead copies of the repeating element of the boring section. This is not very different from the present system, but should allow slightly more efficient evaluation.
^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.
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.)
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.
code: a series of instructions. This corresponds
to the Control register of the SECD machine, and
the procedure-expression of Platypus' closures.
code_index: the current index into the
code. With the code register, it is equivalent
to the continuation-expression of the current
closure in Platypus.
evaluator: a procedure to call to implement
the current closure. Shadowing can be implemented
by letting each shadowed closure be its own
shadow. For such closures, the evaluator's closure
is the closure's code itself, and that code is the
same as the underlying machine code. This is
equivalent to the evaluator of Platypus'
closures.
type-evaluators: an environment binding type
names to the closures implementing the evaluation of
those types.
values: a series of values, used for
procedure arguments and results, and for local
workspace. This is equivalent to the Stack
register of the SECD machine, and to the
values of Platypus' closures, and, as in those
closures, if a closure represents an interpreter,
the closure it interprets is passed to it as its
first argument.
language: a map from instructions to
instruction definitions. This is used to
interpret each instruction in the code. For
procedures that are their own shadows, the
language is ignored, since self-processing
procedures are implicitly written in the
underlying machine language. This is equivalent to
the language of Platypus' closures.
environment: the environment in which
non-local variables are to be found. This is
equivalent to the Environment register of
the SECD machine, and the environment of
Platypus' closures.
dump: the chain of saved register sets at this
level of interpretation. This is equivalent to the
Dump register of the SECD machine, and to the list of
saved closures in Platypus.
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.
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.
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.
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.
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 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.
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