Lisp in Small Pieces of Clojure - part 1

L.I.S.P. cover

Lisp in Small Pieces is a deep exploration of some of the fundamentals of programming that proceeds by describing a series of lisp evaluators and compilers over the course of 400 pages or so.

Personally I find the text pretty baffling at times and the English is often rather curious. Also the Kindle version I have garbles and shrinks some of the code which adds a certain challenge to the reading. Nevertheless the depth and detail of the content are awe-inspiring.

It appears in Rich Hickey’s list of “books that influenced Clojure, in no particular order”. It’s mentioned a few times in Lambda the Ultimate’s “Getting Started” page which is a great resource for PL texts. And Peter Norvig no less describes it as “The best book available on Lisp implementation”.

…of Clojure

There have probably been a few gestures towards porting examples from the book to Clojure already (I know of a gist by Fogus at least).

I don’t intend to produce a complete port of the code from LiSP (like these). I’m probably not interested enough.

However I have the book and have worked through some of the implementations. And, my implementation language of choice is for the most part Clojure. So it’s at least possible a few gists will appear.

In the following, I’ll have no hesitation in commiting crimes against idiomatic Clojure in the name of faithfulness to the book and crimes against the book in the name of idiomatic Clojure. Just a warning.

Chapter 1

The gist for chapter one is here.

Chapter one delivers a simple interpreter that is heavily parasitic on the underlying lisp. As the implementation language in the book is assumed to be Scheme we need to build a little bit of a compatibility shim in Clojure in order to stay close to the implementation in the book.

In particular, we need:

Mutable Environments

The interpreted language provides a set! special form for mutating variables. The environment data structures used in chapter one are simple A-lists that support set! by mutating the cdr of the cons cells.

At this stage I decided to stick with a similar structure in my Clojure implementation (atom wrapped round seq of seqs) and provided lookup, update! and extend operations as per the book.

Fogus chose a more idiomatic map implementation which I think is equivalent except for pathological cases like:

((lambda (x x x) (+ x x)) 1 2 3))

…and in that it provides for set! adding new bindings automatically.

A large part of the exploration of the book regards the behaviour of the environment and the global environment in particular so I decided to stick with the book on this. At this stage there is no dynamic creation of global variables so the implementation creates some initial variables in the environment (foo, bar, fib, fact) for use by programs.

The Evaluator

The evaluator itself is a straight translation from the book differing only in language specifics like atom?.

Mutable Cons Cells

Just as in the scheme implementation, functionality is exposed to the child lisp using definitial and defprimitive macros (substituting Clojure’s defmacro for the Scheme “hygienic” macro approach).

However Clojure is very different from Scheme. If we want to provide similar facilities to the child language (and mutability is essential to many of the problems discussed in the book) there’s some work to do. In particular we need to provide mutable cons cells, which means the cons we need to expose to the child lisp is most certainly not the cons of Clojure.

We could work around this by putting atoms around pairs (and lists would contain nested atoms in their cdr positions) but I chose instead to brute-force my way out:

(defprotocol MutableCons
  (mcar [self])
  (mcdr [self])
  (mset-car! [self val])
  (mset-cdr! [self val]))

(deftype Cell [^{:unsynchronized-mutable true} a ^{:unsynchronized-mutable true} b]
  (mcar [self] a)
  (mcdr [self] b)
  (mset-car! [self val] (set! a val))
  (mset-cdr! [self val] (set! b val))

  (toString [self] (str "(" a " . " b ")")))

(defn mcons [a b]
  (Cell. a b))

(defprimitive cons mcons 2)
(defprimitive car mcar 1)
(defprimitive cdr mcdr 1)
(defprimitive set-car! mset-car! 2)
(defprimitive set-cdr! mset-cdr! 2)

At the REPL

It works.

;; we have mutable cons cells, but printing leaves much to be desired
(set! foo (cons 1 2))
;; => #<Cell (1 . 2)>
(set-cdr! foo (cons 2 nil))
;; => #<Cell (2 . )>
;; => #<Cell (1 . (2 . ))>

;; truthiness is parasitic on the underlying lisp, in clojure 0 is truthy
(if 0 (quote truthy) (quote falsey))
;; => truthy

(begin (set! bar 1) (set! bar 2) bar)
;; => 2

((lambda (x) (+ x 1)) 12)
;; => 13

(set! fib (lambda (x) (if (< x 2) 1 (+ (fib (- x 1)) (fib (- x 2))))))
;; => #<eval$make_function$fn__576 lisp.chapter1.eval$make_function$fn__576@5702cbd3>
(fib 8)
;; => 34

Further Discussion

Chapter one contains some discussion of lexical closure. The lisp we have create works as expected:

((lambda (a) ((lambda (b) (cons a b)) (+ 2 a))) 1)
;; => #<Cell (1 . 3)>

Note also that our lisp is a lexical lisp in that the y in bar’s environment below is not visible from within foo.

(set! foo (lambda (x) (cons x y)))
;; => #<eval$make_function$fn__576 lisp.chapter1.eval$make_function$fn__576@42367c17>
(set! bar (lambda (y) (foo 1991)))
;; => #<eval$make_function$fn__576 lisp.chapter1.eval$make_function$fn__576@70cebf7>
(set! y 0)
;; => 0
(bar 100)
;; => #<Cell (1991 . 0)>
(foo 3)
;; => #<Cell (3 . 0)>

As the gist illustrates, providing cross-cutting enhancements like tracing, or enhancing any of the component parts (like the environment) is currently difficult because of the inflexible design.

There are numerous ways in which the design might be improved: