Wednesday, June 10, 2015

A Function Evaluating eval

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.