The ClojureScript Compilation Pipeline
this is the fifth entry in an n-part series explaining the compilation techniques of Clojure.
In honor of the upcoming Clojure’s Google Summer of Code projects I present some discussion of the ClojureScript compiler pipeline. I talked about this in my ClojureWest talk, but a little more discussion is welcomed. Much of what I say here also applies to Clojure’s pipeline except that the details around data structures and actual programmatic interfaces are different. I will attempt to stay at a high-level of abstraction.
The ClojureScript pipeline survey
This is the ClojureScript compiler pipeline:
You put Clojure code in one end and out comes JavaScript from the other end.
The compiler is made of numerous phases the first of which is devoted to reading strings and converting them into Clojure data structures.
You can see how the reading phase works by observing the following in a Clojure REPL:
(def E (read-string "(-> 42 (- 6) Math/sqrt)"))
(type E)
;=> clojure.lang.PersistentList
(type (last E))
;=> clojure.lang.Symbol
You can see E
is a data structure.
The next compilation phase is the macro expansion phase.
During this phase a form will be expanded until it reaches some fixed point, as shown below:
(-> E macroexpand-1)
;=> (clojure.core/-> (clojure.core/-> 42 (- 6)) Math/sqrt)
(-> E macroexpand-1 macroexpand-1)
;=> (Math/sqrt (clojure.core/-> 42 (- 6)))
(-> E macroexpand-1 macroexpand-1 macroexpand-1)
;=> (. Math sqrt (clojure.core/-> 42 (- 6)))
(-> E macroexpand-1 macroexpand-1 macroexpand-1 macroexpand-1)
;=> (. Math sqrt (clojure.core/-> 42 (- 6)))
In the illustrative case above at three levels of macro expansion the form reached a fixed point (does not change from one level to the next). Eventually the inner ->
macro will also expand, but that happens as the form is traversed during AST generation. You’ll notice that I made the macro expansion box a bit smaller. The meaning for this difference is that macro expansion is interleaved with AST generation. Apart from rote expansion of macros, this phase also shuffles arguments to the .
(dot) operator into a consistent (. target field/method args)
format.
The next phase is deemed the analysis phase and its primary purpose to generate the ClojureScript abstract syntax tree (AST).
If you’ve talked to me about ASTs you’ll probably had the unfortunate luck to hear all about my prejudice against the unfortunate phrase “Lisp syntax is the AST of the program itself” (or some such variation). This is junk. Actual ASTs are adorned with a boatload of additional information like local binding information, accessible bindings, arity information, and many other useful tidbits.
You’ve likely seen a diagram like this (and probably images similar to the pipeline also) in other blog posts, textbooks and papers. However, one advantage that the ClojureScript (and the Clojure compiler one day) provides is that between each compilation phase the interface consists solely of Clojure data! The product of the reader is a list, some other Clojure data type, or a nesting thereof. The product of the macro expansion is the same. The product of the analysis phase is an AST itself composed of nested Clojure maps. There is no product of the compilation phases that cannot be processed by the very tools that Clojure or ClojureScript themselves (and hundreds of libraries) handle directly. This is truly an amazing feature of Clojure and Lisps in general.
The final stage is the emission phase that takes an AST and generates JavaScript.
Emission is likely the most complicated part of the entire ClojureScript compiler – it’s about 700 lines of code.
Jacking into the ClojureScript pipeline
The first obvious point of extension is at the backend of the analysis phase.
This is effectively the approach that Ambrose Bonnaire-Sergeant takes in his typed-clojure. The big difference is that his analyze project provides a ClojureScript-like AST using Clojure’s analysis engine. It’s very cool. Graphically, you can envision typed-clojure situated like the following:
With the type checker adorning and vetting a tree generated by the analysis phase. Question: what is the greatest limitation of Haskell’s type system? Think about it. I answer this in my talk, but it’s not a central point to this post.
There is no reason to stop there however as conceptually one can imagine additional checking occurring on the AST in sequence.
Therefore, the model derived is one where an AST is gradually adorned through a pipeline. This is a pluggable1 compilation system; one that is fully in line with Clojure’s ideal of open extension.
This is a very powerful model, but potentially fraught with complexity.
However, while powerful, the sequential model is not terribly interesting nor desired. Instead, a better model would be one that allows branching or tap logic into the pipeline. For example, if a program is isolated and fully typed then a branch (beta) may be an appropriate action. However, if a program includes the use of untyped libraries then perhaps partial static typing ornamented with runtime constraint checks2 (alpha) may be the more appropriate branch path.3
Designing an interface to the analysis phase and a set of tools for processing its structures is fairly straightforward. The hard part comes in their use, tapping into the pipeline, and branch logic. Careful design is required here.
The next point of extension is at the point of input to the emission phase.
By extension of course I mean that one can plug in their own emitter.
This is likely the most straightforward way to target new platforms for ClojureScript and is indeed the one taken by clojure-scheme. That is, with clojure-scheme Nathan Sorenson generates Gambit Scheme at the backend. The generated Scheme can then be further compiled to C and then finally compiled to machine code.
There is a choke point in this approach, however. ClojureScript’s compiler is very straightforward in that it does very little in the way of code pruning, but instead farms that work off to the Google Closure compiler. If your target language does not have its own processing (e.g. tree-shaking) then you would need to build your own, or better yet, extend ClojureScript to do so.
The final obvious point of extension is to replace the entire pipeline up to the emission phase with your own parser.
This either a very large task (writing a language parser from scratch) or a moderately large task (modifying an existing parser).
The ClojureScript pipeline is extensible along various dimensions, but still needs some work around tooling and interfaces. Clojure’s compiler is less extensible, but certainly not impossibly so. More work is needed to provide the same experience to those wishing to tap into its pipeline. I haven’t even mentioned another approach, one taken by clojure-py. That is, you might also choose to implement the entire Clojure runtime in your target language of choice.
Regardless of the approach that you decide to take (if any), have fun, rock on, and create something amazing.
:F
thanks to Craig Andera, Bobby Calderwood and Rich Hickey for reading a draft of this post
-
Gilad Bracha talks eloquently about pluggable type systems in his paper “Pluggable Type Systems” at http://bracha.org/pluggableTypesPosition.pdf ↩
-
Gilad Bracha again with Types are anti-modular. ↩
-
Although I have the docs phase situated along a separate branch it may more appropriately serve as a tap into all branches. ↩
Categories: joyofclojure, programming
So what’s the greatest limitation of Haskell’s type system? I didn’t see you answer that question.
by configurator on Apr 25, 2012 at 19:42:12
@configurator I haven’t seen Fogus’ talk either, but I’m guessing the limitation of Haskell’s type system is that it’s not optional.
by Mike on Apr 30, 2012 at 08:35:42
@Mike it used to say “answer forthcoming”, so I thought I missed something…
by configurator on May 1, 2012 at 05:25:31
Just FYI, the Haskell type system is becoming slightly more optional in 7.6. I disagree with that being the biggest limitation of the type system. But if you feel that way, you can turn on deferred type errors. In many cases that will cause a Haskell program to fail “like” a strongly, dynamically typed language instead of like the strongly, statically typed language it is.
by Boyd Stephen Smith Jr. on Jun 1, 2012 at 12:35:42
I’ve not seen this mentioned anywhere lately, so… the Stalin compiler for Scheme is a whole-program optimizer. It creates its own types, including union types as needed.
Stalin also does very good lifetime analysis to reduce the amount of garbage needing collection. i.e. it will compute good places in the stack to create a heap, then objects that are determined to be born and die within that sub-stack are allocated from that heap. When the stack unwinds past that point, the entire local heap can be released in one fell swoop.
Clojurescript being whole-programmed into Javascript for a production deployment could benefit from all kinds of analyses like these.
by Patrick Logan on Jul 13, 2012 at 11:05:53
…oh, yeah. This would be a lot easier if the runtime were a JVM with ByteBuffers.
Is it me, or is computing seemingky taking multiple steps backward every year?
by Patrick Logan on Jul 13, 2012 at 11:15:53