A Metacircular Interpreter

Pink is an interpreter for λ↑↓ written in λ↑↓. On its own that is a standard construction — the metacircular interpreter of every Lisp textbook. What Part III shows is what staging does to the construction: because the interpreter is written in a language with lift, the interpreter can be made to compile the programs it interprets, and then to compile itself. This chapter reads the interpreter; the next two stage it.

The chapters in this part use the Purple session (narju at the shell, the default REPL). The session’s own mechanics — define, load, the tower it runs on — are Part IV’s subject; for now it is just the place where the Pink bindings live.

Programs as data, environments as functions

Pink’s programs are quoted s-expressions and its environments are functions from symbol to value. pink-eval takes both:

((pink-eval '(+ 1 2)) nil-env)
;=> 3
((pink-eval '(let x 5 (+ x 1))) nil-env)
;=> 6
((pink-eval '(cons 1 2)) nil-env)
;=> (1 . 2)
((pink-eval '(quote (a b))) nil-env)
;=> ('a 'b)

nil-env is the session’s name for the empty environment, (lambda _ y 0) — every lookup answers 0. The reference implementation uses the same silent zero, which makes an unbound variable indistinguishable from a bound zero:

((pink-eval 'x) nil-env)
;=> 0

Binding forms extend the environment functionally: eval-let wraps the incoming env in a new function that answers the binder’s name and defers everything else. There is no environment data structure to inspect, only a chain of closures.

The interpreted language is the staged core of λ↑↓ — the forms of Parts I and II except cells, throw/catch, and I/O other than log. Recursion needs no special treatment; a recursive function runs as written —

((pink-eval '((lambda f n (if (eq? n 0) 1 (* n (f (- n 1))))) 5)) nil-env)
;=> 120

The shape of the source

The interpreter is one closed expression in lib/pink-forms.naj: a let-chain of named handlers ending in a small dispatch function. Each handler has the same curried signature — it receives tie and eval (explained below), the stage parameter l (next chapter), the expression, and the environment. A representative pair:

(let eval-plus
  (lambda _ tie (lambda _ eval (lambda _ l (lambda _ exp (lambda _ env
    (+ (((eval l) (cadr exp)) env)
       (((eval l) (caddr exp)) env)))))))

(let eval-if
  (lambda _ tie (lambda _ eval (lambda _ l (lambda _ exp (lambda _ env
    (if (((eval l) (cadr exp)) env)
        (((eval l) (caddr exp)) env)
        (((eval l) (cadddr exp)) env)))))))

Each form of the object language is interpreted by the same form of the meta language: Pink’s + is the floor’s +, Pink’s if is the floor’s if. This is the metacircular bargain — the interpreter is short because it inherits the semantics it implements — and it is also, in Part II’s terms, exactly what makes the interpreter stageable: handlers written against ordinary values work unchanged when the values are code.

base-eval is the dispatch: numbers are constants, symbols are variable lookups, and a pair dispatches on its head through a chain of eq? tests to the matching handler. After the special forms comes application. The final expression of the chain ties the knot:

(lambda tie eval
  (lambda _ l
    (lambda _ exp
      (lambda _ env
        (((((base-eval tie) eval) l) exp) env)))))

The self-name tie is the interpreter’s own recursion — every handler’s eval is this function — and it is also the seam at which the interpreter can be replaced (below).

Booting from data

The session gets pink-eval by reading lib/pink-forms.naj as data and animating it with the floor’s trans/evalms primitives (the floor reference lists both): read-file produces the expression as a list, trans translates it to a code value, evalms evaluates that under an empty environment. The interpreter’s source exists exactly once, in that file; the session also keeps it as plain data:

(car pink-poly-src)
;=> 'let

Programs, interpreters, and the sources of interpreters are all the same kind of value — quoted lists — which is the precondition for everything in the Futamura chapter.

Extending the evaluator

delta-eval is a Pink form that runs a subprogram under a modified interpreter. Its first operand evaluates to an extension: a function that receives tie — the unmodified dispatch — and returns a replacement evaluator, deferring to tie for whatever it does not change. An extension that logs every variable lookup:

((pink-eval '(delta-eval (lambda _ tie (lambda _ eval (lambda ev l (lambda _ exp (lambda _ env (if (symbol? exp) (log 0 (((eval l) exp) env)) ((((tie ev) l) exp) env))))))) (let x 3 (+ x x)))) nil-env)
;=> [log] 3
;=> [log] 3
;=> 6

The two [log] lines are the two lookups of x; the sum still comes out. Nothing about the interpreter was anticipated for this — the extension point is just the tie argument every handler already threads. The matcher chapter’s reference implementation uses the same mechanism to build a tracing matcher.