Monday, May 11, 2015

Clojure and Metacircularity

I feel lucky to have found myself as a full time lisp programmer again, in great company with the Lonocloud team. Emphasis on small l lisp, because I'm writing clojure. While a fine lisp, it still feels like an incomplete thought. I don't want this to be another Common-Lisp-vs-Clojure post, though it is unavoidable that some thoughts along those lines will creep in.

tl;dr I have thus far enjoyed working with Clojure, but suspect I would be far happier had its implementation been metacircular.

Let's start with a couple of quotes from the top of clojure.org:

Clojure is a dynamic programming language that targets the Java Virtual Machine (and the CLR, and JavaScript).

A bit further along...

Clojure is a dialect of Lisp, and shares with Lisp the code-as-data philosophy and a powerful macro system. Clojure is predominantly a functional programming language, and features a rich set of immutable, persistent data structures.

However, the JVM host version of Clojure receives far more love and attention than the other hosts. The JavaScript host doesn't have true support for macros. They must instead be defined in Clojure, and applied on ClojureScript code. ClojureScript cannot be written without Clojure on the JVM, it is not a stand-alone language. So the first claim is only partially true, most charitably an aspirational comment.

The second quote is really telling about the relationship between Clojure and other lisps. Clojure is a dialect of lisp in so far as it shares the homoiconicity property of lisps. It is at least as much a functional language in its rejection of a traditional object system and embrace of immutability. Being functional, rather than being a weakness, is a great source of strength. It has allowed clojure to deal with state and asynchronicity in very interesting ways.

Let's return to Clojure as a lisp though. In my first scheme class, based on the classic SICP, we didn't touch macros at all. We did functional programming, and learned about interpreter and compiler implementation, all with scheme acting as both the target and the host language. This is not possible in Clojure, as far as I can tell. At least not without a great deal of effort.

The difference between classical lisps and Clojure on this front is that the core of every Lisp is quite precisely defined in the lisp itself. There is an eval function that is capable of taking any expression in the language, and executing the expression. That eval function is defined in the language itself. So it is not that the language is (partially) homoiconic to the extent that one can write macros, it is homoiconic all the way down. The language is metacircular.

I'm not the first one to make this assertion, I'm sure, but I'll try to explore a bit on my own the proximal and distal reasons for the lack of metacircularity and its impact.

The proximal reason is found in the definition clojure.core.Compiler.eval. Note what happens if the form is a non-trivial type where a function may be defined: you run the whole analyzer, which is also implemented in java. So in order to produce a metacircular Clojure, you have to implement this entire procedure as a Clojure function, and require a Clojure implementation capable of supporting the execution of this eval function. This is a non-trivial undertaking. My experience with other lisps is that you first construct a bootstrapping implementation: one that is able to produce an eval over a small subset of the language. Then in that subset language you implement a small compiler that is able to express this core language as machine executable code. Then you repeat, and in doing so you now have a core language that is implemented entirely in terms of itself. This idea is not limited to lisps, mind you, this is also basically how gcc is built. But metacircularity in conjunction with homoiconicity makes the language easy to describe and manipulate within the language itself. Macros at that point become trivial.

Then in that distilled core language you proceed to define the rest of the functionality that makes the language useful and interesting.

Clojure has no such core language. It has no bootstrap procedure. It cannot run without the host Java environment.

The distal reason for the lack of metacircularity is there seems to be a lack of interest in the idea in a lot of the community. Most Clojure development focuses on the JVM, and Clojure runs well enough there. So there isn't a strong need. Clojure has successfully appealed to a large contingent of programmers with a functional rather than lisp background, so there could also be a certain lack of awareness. Clojure has also been an eminently practical and conservative language, and I get the feeling that parts of the community view metacircularity as a nice-to-have rather than an essential, which has left some lispers feeling that Clojure is an inferior lisp. I don't have a long enough history with Clojure to speculate on the nature of the distal causes.

The impact though is felt by every user of the language, for some in small ways, and for some in profound ways. Clojure as a language doesn't really have a specification. Specifications for lisps have always been relatively straightforward: the eval function is the specification. As a result, it is not straightforward to port Clojure to a new host, such as JavaScript. I suspect moving from one Clojure host to another would be a fairly jarring affair, where the language behaves substantially differently as you change hosts, because "being hosted" is not a well defined idea.

A smaller impact is in the stack traces you get when you have an error. You get a Java stack trace, which you can sometimes relate to the clojure program, and sometimes not. Debugging programs is more challenging. In particular I suspect an interactive debugger in the spirit of Common Lisp will be impossible to have in Clojure.

It's encouraging that there are so many projects underway (or experimented with) to try and address these issues:

But these experiments do not amount to a sustained effort in this direction. I can only hope Clojure goes down this path in the near future.

Edit: Updated description of clojurescript macro support.