牛: How static is enough?

Ox has been and will continue to be a long-haul project in part because it’s a dumping ground of ideas for me, and in part because I don’t desperately need it. There’s plenty of bad in the software industry, but I’m able to swing the hammers that already exist. Ox isn’t so much a hammer as it is an exercise in the ongoing search for what a better hammer would be.

Part of this search comes from my judgments of the tools I use on the daily and their failures. The most significant part however is how the decisions I’ve made in what prototypes I have built have shaken out.

It would have been easy enough to crank out an RⁿRS interpreter and call it Ox. It just wouldn’t have added anything to the software ecosystem or solved any problems I actually had. In fact most of the problems I’ve tried in one way or another to approach in Ox are directed by my programming experience.

So lets start with the motivation and what I was trying to get at in the last cut I took at Ox.

Clojure is a nice language which does a good job at trying to provide sane defaults. Its data structures are immutable by default, it features destructuring - macro sugar for binding values in structures to locals, it interoperates nicely with the JVM and it has a namespace system which makes code organization fairly predictable.

Because Clojure uses a singe pass compiler and its compilation unit is a single form rather than a file/module or group thereof, it can be difficult to Clojure whose module structure reflects its logical structure. Cyclic dependencies between modules/namespaces are difficult to achieve and have poor ergonomics. In fact, cyclic dependencies within a single namespace are - if not difficult to achieve - then at least requires an effort which tends to prohibit their use.

This has a couple of consequences, well exemplified by the language implementation itself. The namespace clojure.core is a huge namespace containing many groups of related functions which would do just as well if not better in their own namespaces. Big namespaces which don’t have a unifying concept are difficult to approach as a new user and difficult to document. Furthermore, they create artificial contention over the “good” names, and tend to lead to the use of prefixes.

Perhaps most interesting is the consequences the lack of circular dependency support has for the language’s own implementation. The first several thousand lines of clojure.core serve to bootstrap the language using mainly JVM inter-operation to Java interfaces and the Java implementation of Clojure’s various built-ins. Some of this bootstrap code is unavoidable, but parts of it could be avoided if the implementation was able to make forward use of symbols which weren’t defined yet.

With explicit forward declarations in some cases this could be made possible today within a single namespace such as clojure.core. The most interesting use cases of circular dependencies however require circular dependencies across module boundaries. For instance what if we could have a clojure.core.seqs namespace containing all the operations related to the sequence abstraction, and so-forth. A large number of small namespaces would be more modular, easier to break out of the standard library into library packages where possible.

And after all, Ox is a pie in the sky project so what would it take?

Well - circular dependencies on functions are pretty easy. They don’t have a data dependency on each-other at compile time; okay they do but letrec is easy to write and rewriting modules as letrec to support mutual function recursion is well understood and a traditional Scheme trick.

For instance if I had the nonsensical module

(define (f a b)
  (c a))

(define (g a b)
  (c b))

(define (c x)
  (+ x 1))

This could be implemented instead by re-writing it to the letrec form

(letrec ((f (lambda (a b) (c a)))
         (g (lambda (a b) (c b)))
         (c (lambda (x) (+ x 1))))
  ...)

Implementing circular dependencies Scheme style via letrec works because the top level special forms (define etc.) are well understood and can be re-written into letrec bindings as above.

The idea I had at the time was that REALLY the core problem here is that the evaluator can’t figure out the dependency graph between functions and macros because we have an indeterminable number of un-expanded macros. A solution to this problem is to simply make the dependency graph statically visible.

In scheme, the above letrec conversion is trivial because the top level form define is well understood by the implementation and so can be rewritten into a form where circular references will function as desired. The take on this in #29 is to do so by restricting top level forms to a small set of forms which explicitly state what definitions they provide. For instance def, defn, deftype and soforth all explicitly name the definitions they create.

(ns example)

;; This provides the definition example/foo. `def` is well know, so
;; this form can be understood as a definition at read time without
;; any effort to evaluate the body or docstring just like `define`.
(def foo
  "Some docs"
  1)

;; Same as above, `defn` is well known and can be statically parsed
;; at least to the degree we need to understand that this defines
;; the symbol example/qux for dependency analysis
(defn qux
  "Some docs"
  ([x] "arity 1")
  ([x y] "arity 2")
  ([x y z & more] "arity 3+"))

;; `defmacro` is just `defn` with the macro flag and some tweaks to
;; accept implicit arguments like `&form` and `&env`.
(defmacro deftype
  ;; ...
  )

;; deftype, definterface and friends all nicely fit this pattern to
;; the extent one may choose to implement them as special forms.

This all works pretty well. The problem is what happens when a macro occurs at the top level? Doing macros this way doesn’t work, especially when there are sequential dependencies between the macros and the functions in the module. While the macros can be re-written as letrec bindings, the semantics of macro expansion don’t fit that way because the macros have to be expanded before the functions or (or the other macros!) using them become executable.

Consider something like this…

(deftype Foo "A foo record." [a b c])
;; We now have the functions `->Foo`, `Foo?` and some friends

(defn foo-or-bar [a]
  (or (Foo? a)   ;; Where does `Foo?` come from? Nothing at the top
                 ;; level trivially provides `Foo?`, but we have to
                 ;; find it in order to compile `foo-or-bar`.
      (Bar? a)))

I thought about this for a long time because I think there’s a clear case for supporting mutually recursive definitions with the most generality possible. And the first solution I came up with is the one implemented in ox-lang/ox#29.

By defining a new top-level special form providing, users can just annotate their top level macros with the symbols they’re expected to produce! Problem solved! This lets Ox determine what top level forms need to be evaluated to see of they provide macros and perform lazy loading by doing functionally free dependency analysis before any evaluation.

So for instance

(providing [->Foo, Foo?]
  (deftype Foo "A foo record." [a b c]))

(defn foo-or-bar [a]
  (or (Foo? a) ;; The reader understands `providing` and can determine
               ;; that to get the needed `Foo?` definition the
               ;; previous form needs to be evaluated.
      (Bar? a)))

The problem with this approach - and the reason I call it a mistake - is that it greatly complicates load time and neuters definition writing macros. As noted earlier, there’s plenty of good reason to want to write macros that write definitions. However a good bit of the syntactic power of such macros is lost if you have to provide a list by hand of definitions the macros will create for you.

Frankly this made implementing code loading so complicated that what with trying to bootstrap Ox in Java I couldn’t do it. This decision proved absolutely fatal to that particular run at the Ox project.

There are, now that I’ve seen the failures of this approach and had some hammock time, other ways to achieve this same end. For instance if you don’t allow macros to write macros, you can play games where macro definitions are letrec rewritten as above, and the definitions of “normal” functions or expressions are delayed until forced by a macro expansion. This lets you play games whereby functions and macros may mutually recur so long as you can ground out a macroexpansion to some concrete form or function of forms that can be evaluated without unbounded mutual recursion between functions and macros. Which, honestly, is the best I think you can do.

The advantage of Clojure’s single pass approach here is a huge complexity win which avoids all these considerations, and the fact that the Clojure read/evaluate/print loop has exactly the same structure as code loading.

Anyway. Languages are hard. That’s what makes them fun.

More when I’ve got better ideas.

^d