To explore metacircularity for Clojure, let's start with a minimal eval
,
implementing a lisp-in-lisp. We shall call our lisp mcircl, abbreviated
as mc
. Making it metacircular is a substantially larger
project, and we'll take that up in the future. I have been referring
heavily to Lisp
In Small Pieces, and this is covered (mostly) in the first
chapter. I have chosen Common Lisp as the host language, because I'm
more familiar with it than Scheme, and it has a clearly spelled out
specification. So the semantics of anything I define on top of it will
have a prayer of being specifiable.
Minimal eval
(mc:eval '(mc:quote x) '()) => x (mc:eval 'x '((x . y))) => y
This isn't a language yet, just a simple program. mc
:eval
is eval
defined in the host lisp. And the data structures
and types are also borrowed from the host. The second argument to eval
is the lexical environment, represented as an association list. We also
see our first special form: mc:quote
.Which is distinct from
quote
in the host lisp. We can already see how different this
lisp will turn out to be from clojure. The treatment of symbols and
namespaces is Common Lisp style, and to work towards clojure we will have
to define a new reader.Function Defining eval
(mc:eval '(mc:fn () (mc:quote x)) '()) => <unreadable-function-value> (mc:eval '((mc:fn () (mc:quote x))) '()) => x (mc:eval '((mc:fn (x) x) (mc:quote y)) '()) => y
Now we're doing something a bit more interesting: writing a function that returns a value. The first defines a function and returns it. The function is not a readable value, and is implemented as data in the host language. The second evaluates the function. The third defines and evaluates a function that takes an argument. To support this we need a more interesting definition of environments that can be extended during function execution.
Let's return to the value of a function. It is an unreadable value in
the host environment. But if the host environment is the lisp itself,
which happens with a metacircular eval
, then that function
value could be readable. We shall explore this idea further below.
Like clojure we're using fn
and not lambda
as the function signifier. And like clojure this is a Lisp-1. Unlike
clojure we are using parentheses ()
and not brackets []
for argument lists. That's because we're relying on the host lisp for
our reader, which will not understand []
without some
work.
Function Naming eval
We don't have recursive functions yet, and without recursive functions
we can't define a metacircular eval
. letfn
bindings can be implemented in a manner that supports recursive
execution. So we can write:
(mc:eval '(mc:letfn ((rf (mc:fn (x) (mc:if x (mc:cons x (rf mc:nil)) (mc:list))))) (rf (mc:quote y))) '()) => (y)
This is a huge step in the power of the language and requires a number of constructs to be added. A recursive function must have a base case, which requires conditionals or pattern matching. Conditionals are simpler. Function calling another function requires a stack, which we again borrow from the host lisp. This will likely never change. As clojure is hosted, we will try and make use of the host language stack to support seamless calls and callbacks with the host language. This comes at a cost though, we will never have good native debugging tools. While not strictly necessary, we have added functions for manipulating lists, so that we have something to compute. Lists and not numbers because lists are required for representing programs.
The Implementation of eval
mc:eval
is a fairly simple function, and deliberately so.
It means we have a hope of defining mc:eval
in mc
rather than Common Lisp. Doing so requires additional functionality that
we have yet to implement, such as def
.
(defun mc:eval (exp env) (if (atom exp) (if (symbolp exp) (lookup exp env) exp) (case (car exp) (mc:quote (cadr exp)) (mc:if (if (mc:eval (cadr exp) env) (mc:eval (caddr exp) env) (mc:eval (cadddr exp) env))) (mc:fn (make-function (cadr exp) (cddr exp) env)) (mc:let (eval-let (cadr exp) (cddr exp) env)) (mc:letfn (eval-letfn (cadr exp) (cddr exp) env)) (t (invoke (mc:eval (car exp) env) (eval-list (cdr exp) env))))))
Even with most implementation details put away in helper functions, we can get a sense for how the language works. We know how symbols are treated, what the fundamental building blocks of the language are, and that this is a Lisp-1. Even when this Lisp is implemented in a metacircular fashion, many of these helper functions will continue to be implemented in the host language. We can adjust the extent to which we rely on the host, for instance, whether we choose to rely on the host for memory management and function calling, or if we choose to implement our own. Our lisp will be hosted, so we will in fact try to build as much as possible on top of the host environment.
The most interesting parts of this function are the implementation of mc:fn
and mc:letfn
.
(defun make-function (params body env) (make-function-definition :parameters params :body body :environment env))
make-function
creates a function object and captures the
definition environment. We get lexical capture from this. The
implementation should otherwise be self-explanatory.
(defun eval-letfn (bind-forms body-forms env) (let ((env-with-letfn-bindings (letfn-env-with-empty-bindings bind-forms env))) (update-env-with-letfn-bodies bind-forms env-with-letfn-bindings) (eval-progn body-forms env-with-letfn-bindings)))
eval-letfn
seems to require mutability in the environment
data structure. Making the functions defined via mc:letfn
requires the functions to be aware of the environment in which they are
defined. Otherwise recursive calls are not possible. So, first we create
empty bindings for the function symbols, create functions with that
environment, and finally update the environment with those function
definitions.
Next Steps
The question of greatest immediate interest to me is whether this lisp can be made metacircular, and what else we need from our lisp in order to make this metacircular. Implementing the full syntax of clojure requires a custom reader, and implementing that in a metacircular fashion will be a larger project. I don't yet know how to start on that.