Lisp in Small Pieces of Clojure - part 2

L.I.S.P. cover

Continuing a translation of various parts of Lisp in Small Pieces into Clojure. For Chapter 1 see Lisp in Small Pieces of Clojure - part 1.

Chapter 2

Chapter two of LiSP covers the concept of namespaces, the distinction between Lisp-1s and Lisp-2s, dynamic binding and how recursion can work in different binding schemes (including a section on the Y combinator - see here for the combinator in Clojure.)

A number of variations on the interpreter are suggested and explored. The implementation I’ve provided in this gist is more or less the “Lisp-3” (!) that is defined by separating out the namespaces for variables, functions and dynamic variables.

Notes on the translation

For no good reason I’ve used an entirely different implementation of mutable cons cells this time round, using Java arrays rather than mutable deftypes.

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

(deftype ArrayCons [ar]
  MutableCons
  (mcar [_] (aget ar 0))
  (mcdr [_] (aget ar 1))
  (mset-car! [_ val] (aset ar 0 val))
  (mset-cdr! [_ val] (aset ar 1 val)))

(defn mcons [a b]
  (ArrayCons. (into-array Object [a b])))

I’ve also split part of the evaluator out into a multimethod evaluate-sexp.

Special forms can then be added by adding the appropriate defmethods (although the new features of this evaluator depend on all the separate environments being passed through all calls so it’s clearly not the case that such features can be added without invasive changes to the evaluator).

The mutable environments are still based on a-lists (or the clojure equivalent, seqs of vectors) in atoms but accessed through protocols. This has meant some switching around of parameters so they no longer match the book but the result is cleaner.

funcall - Lisp-2s

In Lisp-2s like Common Lisp, only symbols in function position are looked up in the function environment; symbols elsewhere are looked up in the normal variable environment.

Or equivalently if binding is handled using cells on the symbol itself, the function cell of the symbol is only used when the symbol is in function position - otherwise the variable cell is used. (Any of us more familiar with elisp than CL will probably be familiar with the “symbol’s definition as variable is void” error message.)

To access functions from the function environment in any other position, the function special form must be used.

Relatedly, as the function application approach expects to evaluate a symbol in function position in order to acquire the function to apply, calling a function that is already stored as a value in the normal value environment needs special handling. This is the role of the funcall special form.

In order to populate the function environment we also provide flet (and labels - see later).

This function / funcall protocol is one of the awkwardnesses of Lisp-2s in comparison to Lisp-1s like Scheme and Clojure.

Our daughter lisp has the following namespace characterstics for the function environment.

Use Syntax
Reference (f ... )
Value (function d)
Modification not possible
Extension (flet (... (f ...) ) )
Definition not provided
(defmethod evaluate-sexp 'function [[_ f] env fenv denv]
  (if (symbol? f)
    (lookup fenv f)
    (wrong "Incorrect function " f)))

(defmethod evaluate-sexp 'flet [[_ bindings & body] env fenv denv]
  (eprogn
   body
   env
   (extend fenv
     (map first bindings)
     (map (fn [[name args & fbody]] (make-function args fbody env fenv)) bindings))
   denv))

funcall is provided as a primitive.

Dynamic variables

The representation of functions has changed in order to accept a dynamic environment at call time.

Therefore:

In contrast to Common Lisp and Clojure which streamline access to dynamic variables at the expense of extra decoration at the definition site (cf. ^:dynamic), our lisp makes the dynamic nature explicit at the access site.

So we have a dynamic special form which is equivalent to function but accesses the dynamic environment instead of the function environment. And a dynamic-let which is equivalent to flet for extending the dynamic environement instead of the function environment.

So note that Common Lisp has an invisible access protocol for the dynamic namespace but an explicit, visible access protocol for the function environment. Clojure has an invisible access protocol for both. Our Lisp-3 has an explicit, visible access protocol for both.

Neither CL nor Clojure allows dynamic (‘special’) variables to share a name with non-dynamic variables so in reality it’s just one namespace - the variables are distinguished at definition time using defparameter or similar (CL) or ^:dynamic (Clojure).

Our daughter lisp has the following namespace characterstics for the dynamic environment.

Use Syntax
Reference cannot be captured
Value (dynamic d)
Modification (dynamic-set! d ...)
Extension (dynamic-let (.. (d ...) ) )
Definition not provided
(defmethod evaluate-sexp 'dynamic [[_ n] env fenv denv]
  (lookup denv n))

(defmethod evaluate-sexp 'dynamic-set! [[_ n v] env fenv denv]
  (update! denv n (evaluate v env fenv denv)))

(defmethod evaluate-sexp 'dynamic-let [[_ bindings & body] env fenv denv]
  (eprogn body
          env
          fenv
          (extend denv
            (map first bindings)
            (map (fn [[k v]] (evaluate v env fenv denv)) bindings))))

Recursion

I’ve used the simple labels special form approach to providing for mutual recursion which works by mutating the environment under the covers so there’s a small period of time where the function environment contains :unititialised values. This is invisible to the daughter lisp though as no code can be executed during this period. (We’re still single threaded only here.)

At the REPL

Demonstrating the protocols for using dynamic and function environments:

;; lambdas in function position and car / cdr / cons still work
(dynamic-let ((x (quote dyn)))
  (car (cdr ((lambda (x) (cons x (cons (dynamic x) nul)))
             (quote param)))))
;; => dyn

;; labels provides for mutual recursion
(labels ((odd? (x) (if (eq? 0 x) |f| (even? (- x 1))))
         (even? (x) (if (eq? 0 x) |t| (odd? (- x 1)))))
  (even? 4))
;; => true

;; dynamic vars are accessible outside their lexical scope
(flet ((f (x) (+ x (dynamic y))))
  (dynamic-let ((y 2)) (f 3)))
;; => 5

;; the funcall / function protocol works for passing functions
(flet ((invoke (f x) (funcall f x))
       (g (x) 'hello))
  (invoke (function g) 'ignored))
;; => hello

Comments