Therapon Skotiniotis - On Reflection

The idea of reflection was first formalized in 1962 and dates back to Goedel. In the context of programming languages it appeared in Lisp with the ' operator, and with Fexp.

The first paper by Brian Smith, Reflection and Semantics in LISP published in 1982 defines computational reflection as the ability to observe own behavior and modify it. In order to understand and explain reflection, Smith split the evaluation into two components. These will be explained, once we have a more formal definition of what is a reflective language.

Definition: Reflective language has the following three properties:
(1) The system can reason about itself (about the embedded account of itself)
(2) Causual connection: this means that the 'account' is linked to its behavior
(3) Vantage point: this means the ability of the system to 'see itself from afar'

The paper presents a recipe on how to get there. Smith argues that it should be included in all languages and it should be used as well.

To implement and explain reflection, Smith develops two new variants of Lisp.

The first one, called 2Lisp is a new dialect that is the foundation on which the reflective language is built later.

He introduces the following functions:

'o' that maps the syntactic structure to the internal representation,
'psi', that maps internal structure into another internal structure,
phi', which denotes something in the real world.

There is a restriction on 'psi' that it be side-effects free, stable and context independent.

For example. (eval '2) will always give you '2.

eval and apply in regular Lisp are renamed to normalize and reduce.
The first one creates a normalized form of an internal structure, the second one produces a denotation from a structure.

Meta-structural interpretation:

' is a handle to normal form for any object. For example, we can talk about '(+ 1 2)

There are three kinds of structures/metastructures that the interpreter understands and can look at:

function -- (LAMBDA (x) x) rail -- '(LAMBDA (x) x)
closure -- ^(LAMBDA (x) x)

The meta-structural interpretation is a recipe to go from a language that does not support reflection to one that does.

3Lisp: is an infinite tower of meta-circular evaluators

At the bottom of the tower is the syntax, each next level is an MCP - a meta circular processor that looks at the level below and can move to level above through reflective procedures, remembering the current state and environment.

The code of the reflective procedure will run as a part of your interpreter - here is the casual connection. That is, the body of a reflective procedure is executed as if it was defined in the interpreter.

Macros are compile time reflections. Though the tower is seemingly infinite, there is a bound. ---------------------------------

Friedman and Wand (84)

They developed interpreter for Brown programming language.

Their goal was to flatten the tower.

They do this by defining two functions reify and reflect:

reify takes code and makes it into a structure (the up-arrow)
reflect takes a structure and makes it into code (the down-arrow)

The dispatches are on text, all in continuation-passing style. They cover all the functions in the Smith paper using only two levels.

There were some questions whether they indeed succeeded. A follow-up paper in (86) gave a definitive proof that their construction indeed is equivalent to Smith's infinite tower.

The solution is as follows:

The goal : given (env cont expr) reify it the solution uses meta-continuation - a stack of continuations, and one pushes/pops these, instead of going up and down the tower.

There was some question about how should callcc work
-------------------------------------

Davny and his wife (named Malmkjaer) in a later paper present the language Blonde to resolve the problem that there is something in the Brown language that cannot be reified, namely the meta-continuations. So they propose meta-meta-continuations as a future work. The motivation behind Blonde was to provide more insight into reflection and fix a bug that the authors of Blonde found in the mechanism of Brown. Specifically with which environment should a reified procedure be evaluated and why?

They desing a new environments E-sub-m and (E^-1)-sub-m that uses the environment and continuation from above (rho-sub-n and kappa-sub-n)

it comes with reifiers: -delta and _gamma that give us dynamic and static scoping between layers

Wand & Friedman used (make-reify (lambda (x) 'x))

But Danvy says that this is more "correct"

 (make-reify (lambda (x) rho 'x)) in Brown.

And this is what the delta abstraction does in Blonde. --------------------------------------