Problem 2: Handling introspection and causal connection

Introspection behaves very differently in 3-Lisp like reflective towers and lookup  apply ones. In 3-Lisp towers, reflective procedures should be written in the language of the level where they are applied ⁹ but their body will ultimately be executed at some higher-level, perhaps depending on the inputs to the program. In lookup  apply ones, the introspective code is directly inserted in their level of application and is therefore written in the language of this level.

Compilation implies that the data structures and the code of one level will be progressively transformed, in a multistage process, into data structures of the lowest (machine) level. For example, in a Scheme to C compiler, Scheme environments, a latent concept at the Scheme level (but it would be explicit in a reflective language) are first transformed into C data structures and then into machine language ones. Danvy and Malmkjaer [DM88] indirectly observe this when they show that a value at level n has to be represented by some value of the level n+1 processor, which in turn must be represented by a value of the level n+2 processor, and so on. This means that when introspective code written in Scheme or in C, respectively accessing reified versions of the internal data structures, i.e., data structures in Scheme and in C, is compiled in machine language, it must access the corresponding machine language data structures.

Compiling usually means a loss of information. When a program is compiled, variable names are mapped to locations in memory and the names themselves disappear. Hence, a reflective computation written at the Scheme level to access the reified environment, must be compiled into machine code that accesses the real environment. This leads us to the following observation about the relationship between reflection, reification and compilation:

Reflection = Compilation + Information
Reification = Information + Decompilation

For the same piece of data, reflection and reification are mediating between a higher-level representation accessible in terms of the higher-level language, and a lower-level one, which is accessible in the terms of the lower-level language. For example, the piece of data may be an environment represented as an a-list in Scheme but as an activation record in the lower-level representation. The a-list in Scheme maps variable names to values, while the activation record maps offsets to values. The first equation essentially says that when you reflect something, or install it in the lower-level, you must compile it but some information will be lost in the process. In the environment example, the variable names will be lost. The second equation essentially says that when you reify something, you must decompile a lower-level representation to create a higher-level one, but this process will need some information. Again in the environment example, you will need to supply the mapping between the variable names and the offsets in the activation record to return a complete a-list.

In fact, the need for this kind of information appears in several existing situations:

1.

This kind of information is needed for source level debugging (the symbol table). This is not surprising: in source level debuggers, we have requests made in the source level model of computation that must be mapped onto the low-level model in which the program is run. These requests are very similar to reflective expressions.

2.

It is also needed to manage Smalltalk reified activation records where a mapping between machine code addresses and the corresponding positions in the byte-codes must be kept for debugging purposes but also to transform them on demand from their native representation to an object one [DS84].

3.

It is even more apparent in the debugging of heavily optimized code where it is difficult to keep track of the infromation because of code movement or even code elimination, among other things [BHS92].

4.

Finally, it is also needed to decompile code on demand, a capability that exists in several systems like Smalltalk [DS84] and Self [HCU92].

In the static behavioral reflection case, the compiler would have this information at hand and would use it to compile the introspective code. In the dynamic behavioral reflection case, this information would have to be kept around at run-time to process the introspective code correctly.