home blog lisp (new!) favorites

Writing a Lisp, Part 12: Metacircular Evaluator

March 1, 2017

The term “metacircular evaluator” is a rather opaque way of saying “Lisp written in the Lisp you just wrote”, which is what we’re going to test out right now.

It’s a fun demonstration that you’ve build enough of an interpreter in OCaml (we’ll call it Lisp0) that you can build a shorter version of that same language, and extend it from there (we’ll call that Lisp1).

Paul Graham’s Lisp

I’ve taken Paul Graham’s (henceforth written as “pg”) implementation of the metacircular evaluator and modified it slightly for our use case. It’s easy to read, and short enough to be understood fully in a sitting. I’ll walk through it function by function.

(define null. (x)
  (eq x '()))

This seems to be a reasonable way to check if a thing is nil — check equality using the built-in eq.

(define and. (x y)
  (cond (x (cond (y #t)
                 (#t #f)))
        (#t #f)))

pg’s Lisp uses cond to write and., but we ended up building that into Lisp0 as a special form.

(define not. (x)
  (cond (x #f)
        (#t #t)))

pg’s Lisp uses cond to invert the truthiness of x.

(val cons pair)

(define append. (x y)
  (cond ((null. x) y)
        (#t (cons (car x)
                  (append. (cdr x) y)))))

In order to give list access to pair, we have to make an alias and call it cons. This is the simple non-tail-recursive version of append.

(define list. (x y)
  (cons x (cons y '())))

We could also just dispatch to the built-in list function instead of using cons.

(define pair. (x y)
  (cond ((and. (null. x) (null. y)) '())
        ((and. (not. (atom? x)) (not. (atom? y)))
         (cons (list. (car x) (car y))
               (pair. (cdr x) (cdr y))))))

Confusingly enough, pg’s Lisp defines a function named pair. that zips two lists together, like so:

> (pair. '(1 2 3) '(a b c))
((1 a) (2 b) (3 c))

Note that the elements of the parent list are themselves lists, not just pairs.

I think it’ll be easier if we rename pair. to zip..

(define o (f g) (lambda (x) (f (g x))))
(val caar (o car car))
(val cadar (o car (o cdr car)))

pg’s Lisp requires some functions like caar and caddr, that are defined to be (car (car x)) and (car (cdr (cdr x))), respectively. I’ve added in a function called o that does function composition, so that we can support those easily.

(define lookup. (key alist)
  (cond ((eq (caar alist) key) (cadar alist))
        (#t (lookup. key (cdr alist)))))

lookup. looks up a variable in an environment. pg calls it assoc., but we might as well call it lookup., since that’s what we use internally (in OCaml). His environment uses a list of lists instead of a list of pairs and (due to our implementation of lookup.) returns error if key is not found in alist.

eval

The key to the interpreter is the eval function. It’s definitely rather long for a Lisp function, so I’m going to walk through it in comments. The only thing, though, is that our Lisp reader does not understand comments — so you can’t just copy and paste it into the Lisp0 shell.

; eval takes two parameters: an expression and an environment. It's like our
; evalexp.
(define eval. (e env)
  ; There are a lot of cases to consider. This is like our large match
  ; expression.
  (cond
    ; If it's a symbol, look it up. This is different from pg's Lisp in that
    ; he *only* has symbols to work with.
    ((sym? e) (lookup. e env))
    ; If it's some other type of atom, just leave it be. Let it self-evaluate.
    ((atom? e) e)
    ; If it's a list (the only alternative to being an atom), check if the
    ; first item is an atom.
    ((atom? (car e))
     ; What kind of form is it?
     (cond
       ; Quote accepts one argument, so just return that argument as an
       ; unevaluated expression (note the lack of a recursive call to eval.).
       ((eq (car e) 'quote) (cadr e))
       ; For atom?, eq, car, cdr, and cons, just evaluate the expression then
       ; pass it through to the built-in form.
       ((eq (car e) 'atom?) (atom? (eval. (cadr e)  env)))
       ((eq (car e) 'eq)    (eq    (eval. (cadr e)  env)
                                   (eval. (caddr e) env)))
       ((eq (car e) 'car)   (car   (eval. (cadr e)  env)))
       ((eq (car e) 'cdr)   (cdr   (eval. (cadr e)  env)))
       ((eq (car e) 'cons)  (cons  (eval. (cadr e)  env)
                                   (eval. (caddr e) env)))
       ; For cond, it's a wee bit tricker. We get to this function a bit later.
       ((eq (car e) 'cond)  (eval-cond. (cdr e) env))
       ; ...else, try and evaluate the function as a user-defined function,
       ; applying it to the arguments.
       (#t (eval. (cons (lookup. (car e) env)
                        (cdr e))
                  env))))
    ; If it's a compound expression in which the first element is a
    ; label-expression,
    ((eq (caar e) 'label)
     ; ...evaluate the expression in environment with a new recursive binding.
     (eval. (cons (caddar e) (cdr e))
            (cons (list. (cadar e) (car e)) env)))
    ; If it's a compound expression in which the first element is a
    ; lambda-expresison,
    ((eq (caar e) 'lambda)
     ; ...evaluate the application of the lambda to the given arguments,
     ; evaluating them.
     (eval. (caddar e)
            (append. (zip. (cadar e)
                           (map-eval. (cdr e) env))
                     env)))))

; Some helpers...

; cond works by evaluating each of the conditions in order until it encounters
; a truthy one.
(define eval-cond. (c env)
  ; If we have no more conditions left, there's an error.
  (cond ((null. c) 'error)
         ; If the current condition is true, evaluate that branch.
         (eval. (caar c) env)   (eval. (cadar c) env))
         ; Otherwise, keep going.
         (#t (eval-cond. (cdr c) env))))

; This is a manually curried form of map. It runs eval over every element in a
; list using the given environment.
(define map-eval. (exps env)
  (cond ((null. exps) '())
        (#t (cons (eval.  (car exps) env)
                  (map-eval. (cdr exps) env)))))

And there we have it! Now, it took me a bit to understand exactly how to use this so-called “metacircular evaluator”. It’s not obviously well-documented. However, there is an excellent pdf that helped me understand the finer points of label.

label is used much like our built-in define, except that it requires manual use of lambda. Here’s what I mean:

; Our Lisp
(define fact (x)
  (cond ((< x 2) 1)
         (#t (* x (fact (- x 1))))))

; pg's Lisp
(label fact
  (lambda (x)
    (cond ((< x 2) 1)
           (#t (* x (fact (- x 1)))))))

While we could build in the nice syntactic transform that adds the lambda for us, effectively turning label into define, that’s apparently too much effort. Oh well!

In any case, let’s try running this thing. A couple of notes:

So I’ve added the pass-throughs for +, *, -, and < so we can write factorial. Here’s what it looks like:

$ cat 12_metacircular.lsp
[...]
(eval. '((label fact
                (lambda (x)
                  (cond ((< x 2) 1)
                        (#t (* x (fact (- x 1)))))))
         5)
       '())
$ ocaml 12_metacircular.ml < 12_metacircular.lsp
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<primitive:pair>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> #<closure>
> 120
> Exception: End_of_file.
$

Yeah, that looks weird. Turns out eval. can only evaluate one expression at a time. Understandable. So label is less of a define and more of a “recursive lambda”. It needs to be applied immediately — there’s no val, there’s no define, and it can’t stand alone and evaluate into a closure.

Adding a begin statement that allows for imperative programs would be another feature, but we’ve chosen not to include it for simplicity’s sake.

Download the code here (ml) and here (lisp) if you want to mess with it.

And there you have it — reasonable proof that our Lisp implemementation can be considered feature complete. Now we can move on to features that make the language easier to use, like let.