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
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
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.
' 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. --------------------------------------