Reflection and reification

Reification is the making available of program code and state to the program itself, by the interpreter of the program.

Reflection is the incorporation of data from a program into the code or state of that program, through the action of the interpreter of the program.

Sometimes, ``reflection'' is used as a term for both of these.

Reification is also sometimes called ``introspection''.

Basics of implementation

An interpreted program can only do things provided by the operators that the interpreter makes available. To make a language reflective, the interpreter must include operators that give access to the data structures of the interpreter itself; in particular, the data structures representing the code and state of the program being interpreted.

Flat reflection and tower reflection

In flat reflection, the evaluator gives the program access only to its own code and state.

[Reflective tower being unrolled]
Tower being unrolled

In tower reflection, as well as having access to its own code and state, the program has access to its evaluator's code and state, and the code and state of the evaluator running that evaluator (in the metacircular model of interpretation), and so on. Because there are infinitely many levels, they have to be instantiated only when referenced.

Since they are all the same (or there is a repeating cycle of them), they can be instantiated as copies of one standard evaluator.

[Tower and meta-evaluator]
Tower with meta-evaluator

This requires another evaluator, outside the tower of metacircular interpretation, to make it all work, and to create the levels of interpretation as needed for inspection and modification by the reflective operators.

This external evaluator can be called a meta-evaluator or an ultimate machine. This was originally researched by Brian Cantwell Smith in his PhD work.

The meta-evaluator both manages the tower from outside the tower, and mimics the effect of the standard evaluator running within the tower.

Fractal tower reflection

[The meta-evaluator's tower]
The meta-evaluator's tower

Of course, the meta-evaluator itself is a program, which could be interpreted, and its interpreter could have an interpreter, and so on, and hence there is another tower, the meta-evaluator tower of the first tower.

[The beginnings of the fractal tower]
The beginnings of the fractal tower

That tower, in turn, will have its own meta-evaluator, which is a program being evaluated by an evaluator.... and so will start another tower, and so on.

[The full fractal tower]
The full fractal tower

These form a meta-tower, which needs a meta-meta-evaluator, and so on.

It is possible to give programs access to the meta-evaluator, its evaluator, its evaluator's evaluator, and so on. (This is what I did in my PhD thesis work.)

Making the whole thing work

All these levels have to spring into existence as needed. Of course, eventually there really is an ``ultimate machine'' but it always keeps hiding itself away -- as you approach it by following data structures, it (since it really implements the way that you follow the data structures) keeps handing you newly-created substitutes for itself.

This is echoed beautifully by the following quote:

The shop seemed to be full of all manner of curious things---but the oddest part of it all was that, whenever she looked hard at any shelf, to make out exactly what it had on it, that particular shelf was always quite empty, though the others round it were crowded as full as they could hold.

``Things flow about so here!'' she said at last in a plaintive tone, after she had spent a minute or so in vainly pursuing a large bright thing, that looked sometimes like a doll and sometimes like a work-box, and was always in the shelf next above the one she was looking at. ``And this one is the most provoking of all---but I'll tell you what---'' she added, as a sudden thought struck her. ``I'll follow it up to the very top shelf of all. It'll puzzle it to go through the ceiling, I expect!''

But even this plan failed: the ``thing'' went through the ceiling as quietly as possible, as if it were quite used to it.

Alice Through the Looking Glass, Chapter 5

John C. G. Sturdy
[John's home] Last modified: Sun Jun 10 22:00:02 GMT Daylight Time 2007