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 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
(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
Special forms can then be added by adding the appropriate
(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
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
labels - see later).
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.
(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.
The representation of functions has changed in order to accept a dynamic environment at call time.
make-functionaccepts only env and fenv but returns a fn requiring a denv
defprimitiveneeds to provide functions that accept the dynamic environment so we provide a simple
with-envwrapper to adapt the call protocol of the native clojure functions
In contrast to Common Lisp and Clojure which streamline access to
dynamic variables at the expense of extra decoration at the definition
^:dynamic), our lisp makes the dynamic nature explicit at
the access site.
So we have a
dynamic special form which is equivalent to
but accesses the dynamic environment instead of the function
environment. And a
dynamic-let which is equivalent to
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
Our daughter lisp has the following namespace characterstics for the dynamic environment.
|Reference||cannot be captured|
(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))))
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
: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