Introduction

Broadly construed, reflection is the ability to reason and act upon oneself. For a programming language, this entails being able to reason about and change the semantics from within a program.

Imagine a language where you can change the meaning of any program, and the meaning of the meaning, and the meaning of the meaning of the meaning, ad infinitum — as the program is running. Reflective towers of interpreters provide that.

Initiated in the 80s by Brian Cantwell Smith (1982, 1984), reflective towers of interpreters are a semantic model of reflection, with a user level (level 0) interpreted by a meta level (level 1) interpreted by a meta meta level (level 2) interpreted by a meta meta meta level (level 3) and so on potentially for infinity. Each level comes with its own REPL and ‘program counter’, as each level can be thought of as a little interactive machine causally connected with the others. Each level (e.g. user level aka level 0) can reify its program into data at the level above (e.g. meta level aka level 1), and each level above can reflect data back into the program at the level below.

In this post, I hope to popularize reflective towers of interpreters. While their primary motivation is semantic, they illustrate key mechanisms and uses of reflection in programming languages.

Design Considerations

Reflective towers of interpreters capture the essence of reflection.
We consider the design choices mostly common to all reflective towers.

• reification / reflection: reification turns a running program into data that represents it (expression, environment, continuation) while reflection reinstates the data into a running program.
• up / down: a level is interpreted by the meta level above (so the user level is interpreted by the meta level, and the meta level is interpreted by the meta meta level, and so on…). In a reflective tower, reification goes up the tower while reflection goes down. A reflective tower always has a vantage point.
• the tower is conceptually infinite: each level has a meta level. However, the tower can be fully realized by dynamically defaulting above an unmodified level — that is, by using a default interpreter to evaluate the unmodified upper levels of the tower. A meta continuation is a stream of (environment, continuation) pairs representing the potentially infinite tower. The infinite tower clarifies the inherent infinite regress of evaluating evaluation.
• semantics and modified semantics: after a running program is reified, it can be inspected and manipulated and reflected back in many ways. One can write a custom evaluator, or one can transform the program text (expression) and use the default evaluator. In some towers, one can change the evaluator piece-wise (for example, only changing the evaluation of variables).
• interactivity: each level has a REPL, and one can go up and down the tower in the REPLs.
• causal connection: to explain the causally connected levels, Brian Cantwell Smith draws an analogy: “it is as if we were creating a magic kingdom, where from a cake you could automatically get a recipe, and from a recipe you could automatically get a cake.”

We will now look at three examples in Black, a reflective tower of interpreters due to Kenichi Asai et al. (1996). The code for the examples is available as a live playground.

Black Walkthrough: Debugging

First we’ll see how reflection can be used to support interactive debugging.

We start the Black REPL. The REPL starts at the user level. To evaluate a user-level expression, two new levels are loaded: the meta level (which evaluates the user level) and the meta meta level (in which meta level evaluation functions are looked up).

(black)
New level loaded.
New level loaded.
0-0: start

We define a function foo and create a thunk (a function with zero arguments) out of its application. Then, we invoke the thunk.
There is an error: the number 2 is passed in for f but foo expects f to be a function. Because of the error, the control passes to the meta level. The prompt changes from 0- (user level) to 1- (meta level), that is from 0-3> to 1-0> here.
A new level is loaded for the meta meta meta level.

0-1> (define foo (lambda (f) (lambda (x) (lambda () (f (+ x 1))))))
0-1: foo
0-2> (define thunk ((foo 2) 3))
0-2: thunk
0-3> (thunk)
New level loaded.
1-0: (Not a function: 2)

We can use the old continuation old-cont (set by Black when moving up the tower) to jump back to the level below (here the user level). Since the top-level application is at fault, and there are no pending computations, we can just return any value with the continuation.

1-1> (old-cont 'ok)
0-3: ok

Now what are our options to fix this error? One option is to fiddle with the thunk and change the value of f in its closure to be a function.
We load the file break.blk at the meta level, as indicated by the exec-at-metalevel form.
This break.blk file defines the inspect form — it’s nothing special; we will sketch its definition later.
When calling inspect on the thunk, we get a REPL below the user level to inspect and modify the thunk’s enclosing environment.
When we exit that REPL, we go back to the level above (here the user level).

0-4> (exec-at-metalevel (load "break.blk"))
0-4: done
0-5> (inspect thunk)
inspect-loop
inspect> f
2
inspect> (set! f (lambda (x) (* 2 x)))
f
inspect> (exit 'done)
inspect-end
0-5: done
0-6> (thunk)
0-6: 8
0-7> (thunk)
0-7: 8

Another option is defining application of numbers so that it multiplies all the numbers together instead of returning an error.
We load the file multn.blk (again nothing special as we will see) at the meta level to re-define the behavior of application where the operator is a number.

0-8> (define thunk2 ((foo 2) 3))
0-8: thunk2
0-9> (thunk2)
1-1: (Not a function: 2)
1-2> (old-cont 'ok)
0-9: ok
0-10> (exec-at-metalevel (load "examples/multn.blk"))
0-10: done
0-11> (thunk2)
0-11: 8
0-12: (1 2 3 4)
0-12: 24

What does the Black code to create those inspection and modification look like?
Let’s start with the code to re-define application of numbers defined in multn.blk.
This code is to be loaded from the meta level.
The Black meta level defines the interpreter piece-wise.
There is a base-apply function that handles applying an operator to an operand, where both have already been evaluated.
We re-define the base-apply function to handle an operator that is a number and delegate to the old base-apply function otherwise.

(let ((original-base-apply base-apply))
  (set! base-apply
    (lambda (operator operand env cont)
      (cond ((number? operator)
             (base-eval (cons '* (cons operator operand)) env cont))
            (else
             (original-base-apply operator operand env cont))))))

For the inspector defined in break.blk, we define a special form inspect by changing the eval-application meta function to handle the case.

(let ((original-eval-application eval-application))
  (set! eval-application
    (lambda (exp env cont)
       (cond
         ((eq? (car exp) 'inspect)
          (eval-inspect (car (cdr exp)) env cont))
         (else
          (original-eval-application exp env cont))))))

The evaluation of the inspect form starts a loop with the closure environment as the running environment. The loop does not need to explicitly exit, since that is handled by the meta continuation. The full code is given in the live playground.

Example: Instrumentation

We can modify the interpreter so that it instruments a program in custom ways.
For example, we can implement an instrumentation routine specific to There and Back Again (TABA) (O. Danvy & M. Goldberg, 2002; 2005) programs, to visualize the process as it pushes and pops the stack. TABA can solve problems which typically require some copy and reversal of the input in one “simple, first-order recursive descent that gets us there (i.e., to the base case) and back again (with the result)”. Here, we consider the convolution function cvn which takes two lists and zips the first list with the reverse of the second list.

We install the taba special form at the meta level by loading taba.blk. We show a sample execution: we define the convolution function cnv at the user level by loading cnv.scm (the function cnv delegates to the helper function walk); we then use taba to monitor cvn and walk as the expression (cnv '(1 2 3) '(a b c)) is being evaluated.

(black)
New level loaded.
New level loaded.
0-0: start
0-1> (exec-at-metalevel (load "examples/taba.blk"))
New level loaded.
0-1: done
0-2> (load "examples/cnv.scm")
0-2: done
0-3> (taba (cnv walk) (cnv '(1 2 3) '(a b c)))
(cnv (1 2 3) (a b c))     ((1 . c) (2 . b) (3 . a)) 
|                         ^                         
V                         |                         
(walk (1 2 3))            (((1 . c) (2 . b) (3 . a)))
|                         ^                         
V                         |                         
(walk (2 3))              (((2 . b) (3 . a)) c)     
|                         ^                         
V                         |                         
(walk (3))                (((3 . a)) b c)           
|                         ^                         
V                         |                         
(walk ())                 (() a b c)                
|                         ^                         
V                         |                         
---------------------------
0-3: ((1 . c) (2 . b) (3 . a))
0-4> 

From the output, we infer that 1, 2 and 3 get pushed onto the stack, and we pop them off while matching with a, b and c.

Example: Meta-Level Undo

All this mutation at the meta level to realize custom semantics is error prone.
We can implement a meta-level undo by changing the eval-set! function in the meta meta level — this function defines the semantics of set! (mutation) for the meta level.
To implement this functionality, we load undo.blk at the meta level, affecting the meta meta level as well.
We show a usage example: we re-define the evaluation of a variable to always return 0 if the variable is named n, and then we undo the meta level change.

(black)
New level loaded.
New level loaded.
0-0: start
0-1> (exec-at-metalevel (load "examples/undo.blk"))
0-1: done
0-2> (exec-at-metalevel (define old-eval-var eval-var))
0-2: old-eval-var
0-3> (exec-at-metalevel (set! eval-var (lambda (e r k) (if (eq? e 'n) (k 0) (old-eval-var e r k)))))
0-3: eval-var
0-4> (define n 1)
0-4: n
0-5> n
0-5: 0
0-6> (exec-at-metalevel (eq? old-eval-var eval-var))
0-6: #f
0-7> (exec-at-metalevel (undo!))
0-7: done
0-8> n
0-8: 1
0-9> (exec-at-metalevel (eq? old-eval-var eval-var))
0-9: #t
0-10> 

History

Reflective towers of interpreters include 3-Lisp (B.C. Smith, 1982; 1984; J. des Rivières and B.C. Smith, 1984), Brown (D.P. Friedman and M. Wand, 1984, M. Wand & D.P. Friedman, 1986), Blond (O. Danvy & K. Malmkjaer, 1988), Black (K. Asai et al., 1996) and Pink and Purple (N. Amin & T. Rompf, 2018). Based on denotational semantics, Brown features first-class reifiers, which are first-class special functions that are given the current unevaluated expression, environment and continuation when applied. Blond clarifies the denotational semantics of the tower and focuses on tower manipulation for example permuting two levels. In Black, as we have seen, the interpreter at each meta level can be mutated piece-wise, for example the evaluation of variables can be re-defined. Pink and Purple demonstrate that it is possible to “collapse” a tower, that is compile it without interpretive overhead with respect to the current semantics.

Implementations and examples of Brown, Blond and Black are available online, as well as those of Pink and Purple.

A reflective meta-level architecture organizes a system to facilitate reflection. We need more research to explore reflective meta-level architectures, such as reflective towers of interpreters, meta-object protocols (Smalltalk, Common Lisp Object System, …), proof by reflection (FOL, Coq, …), mirrors (Bracha & Ungar 2004), …

Parting thoughts

As a semantic thought experiment in reflection, reflective towers have limitations.

• How do we re-define meaning in a reflective tower? At one extreme, we can use a custom meaning function or transform the program and use the built-in meaning function. At the other extreme, in Black, we can mutate piece-wise functions that take part in meaning. Meta mutation provides a program the ability to modify its own meaning arbitrarily, without delimitation, which is powerful — perhaps too powerful, and error-prone. Meta-Object Protocols use object-orientation to provide a more delimited form of meaning manipulation.
• It’s not clear we need to tie reification/reflection to going up/down the tower. On the contrary, we may want more flexible points of view on a computation. Instead of a tower — a linear hierarchy — we may want causally connected meaning-defining points of view. Perhaps each agent in a multi-agent system can have a point of view on each other agent and itself.
• The malleability of reflective towers renders static analysis difficult. How can we reconcile reflection with abstraction boundaries, static analysis and verification? Combining reflection and static meta programming could be very fruitful for modifying a language from the outside.
• We want “reasonable” reflection, one that can adapt to unanticipated needs, while preserving static reasoning and guarantees.

Acknowledgements: Thanks to Kenichi Asai, Michael Ballantyne, Will Byrd, Steve Chong, Olivier Danvy, Michael Fogus, Dan Friedman, Anastasiya Kravchuk-Kirilyuk, Stefan Marr, Todd Millstein, François-René Rideau, Tiark Rompf, Felix Sosa, Joey Velez-Ginorio and Mitch Wand for discussions and/or feedback.

Bio: Nada Amin is an assistant professor at Harvard SEAS. She likes “software archaeology”, re-discovering artifacts of the past from a modern perspective.

Disclaimer: These posts are written by individual contributors to share their thoughts on the SIGPLAN blog for the benefit of the community. Any views or opinions represented in this blog are personal, belong solely to the blog author and do not represent those of ACM SIGPLAN or its parent organization, ACM.