Clojure is almost as big as Common Lisp

How big is Clojure's standard library? Never mind the Java library, or even clojure.contrib; how much is built in to clojure.jar?

One way to answer this is to count definitions, in the form of public Vars:

(defn ns-size "How many public Vars does this namespace have?" [name]
  (require name)
  (count (ns-publics (find-ns name))))

(def builtins '(clojure.core clojure.core.protocols clojure.data
                clojure.inspector clojure.java.browse clojure.java.browse-ui
                clojure.java.io clojure.java.javadoc clojure.java.shell
                clojure.main clojure.pprint ;clojure.parallel ;deprecated
                clojure.reflect clojure.repl clojure.set clojure.stacktrace
                clojure.string clojure.template clojure.test clojure.test.junit
                clojure.test.tap clojure.walk clojure.xml clojure.zip))

In Clojure 1.3.0a6:

user=> (ns-size 'clojure.core)
563
user=> (reduce + (map ns-size builtins))
826

So Clojure is already approaching Common Lisp's 1064 definitions¹. This measure probably overstates Clojure's size relative to CL, because it compares all of Clojure to only the standard parts of Common Lisp, but every CL implementation includes other libraries in addition to the standard. CL also tends to pack more features into each definition, through keyword arguments and complex embedded languages like format and loop, so counting definitions understates its size. On the other hand, many CL features are of dubious value, so Clojure may already have surpassed it in useful library.

If it hasn't, it will soon, because Clojure's library is still growing. The Var count has increased by 50% in the last two years:

Version	Date	clojure.core	clojure.*
1.0.0	May 2009	458	543
1.1.0	Dec 2009	502	576
1.2.0	Aug 2010	546	782
1.3.0a6	Mar 2011	563	826

At this rate, Clojure 1.6 will have a bigger standard library than Common Lisp. (The timing depends on how quickly parts of clojure.contrib get assimilated into clojure.core.) I suppose when that happens, Common Lisp will still be perceived as huge and bloated, and Clojure as relatively small and clean. Any perceived complexity in Clojure will be blamed on Java, even though Java interoperation accounts for only a tiny part of Clojure's library. Scheme will still be considered small and elegant, no matter how big its libraries (or its core semantics) get. (R5RS Scheme has 196 definitions, and R6RS about 170, or 680 with its standard libraries. Racket is much bigger.) Traditional beliefs about language sizes are not very sensitive to data.

Update: riffraff on HN counts Python's definitions: len(__builtins__.__dict__.values()) ⇒ 143 definitions in the default namespace, plus len(set(chain( *[dir(o) for o in __builtins__.__dict__.values()]))) ⇒ 250 method names, so about 400 built-in definitions. There are also over 200 other modules in the standard distribution, so its full standard library is much bigger — the first 24 modules have sum([len(dir(__import__(n))) - 4 for n in "string re struct difflib StringIO cStringIO textwrap codecs unicodedata stringprep fpformat datetime calendar collections heapq bisect array sets sched mutex weakref UserDict UserList UserString".split()]) ⇒ 476 definitions, so the total is something like 5000. “Batteries included” indeed.

However, standard library size is less important than it used to be. When every language has an automatic library fetcher like Leiningen or Quicklisp or PLaneT, built-in libraries aren't much more readily available than other well-known libraries. The main obstacle to library use is no longer finding suitable libraries, or downloading them, but learning to use them.

¹ Common Lisp has 978 symbols, but symbols ≠ definitions: some symbols have definitions in more than one namespace, and some have no definition. Common Lisp has 752 definitions in the function namespace (636 functions, 91 macros, and 25 special forms), 116 variables, 85 classes, 66 setf functions, and 45(?) type specifiers, for a total of 1064 definitions. There are about 30 symbols without definitions: declare and its declarations and optimization qualities, a few locally bound symbols like call-next-method, and eight lambda-list keywords. There's also plenty of room for disagreement about what counts as a definition.

min-key and max-key should take lists

Clojure's min-key and max-key operators are variants of min and max that minimize or maximize some function of their arguments:

user=> (max-key count "Find" "the" "longest" "word")
"longest"

I used min-key a few times recently, and found it awkward every time, because the input arrived in a list, not in several separate expressions. Converting from one to the other is a simple matter of apply, but the resulting expression is not as clear as it ought to be:

user=> (apply min-key count
         (clojure.string/split "Find the shortest word" #" "))
"the"

It seems to me that while min and max are almost always used on separate arguments, min-key and max-key are much more likely to be used on lists. (In general, I think high-order functions are much more likely to be used on lists than their first-order relatives.) Googling clojure min-key supports this: almost all uses are (apply min-key ...), not (min-key ...) — and all of the latter seem to be either artificial examples or mistakes. Even the spelling corrector which was the original motivation for adding max-key uses it with apply. So these functions should really be provided in list form (like Arc's most) rather than separate-argument form.

This is a general problem, though. Any operator that takes an arbitrary number of arguments will probably be used sometimes on lists and sometimes on a few explicit arguments. apply or reduce are the obvious ways to transform one into the other, but they're rather disappointing when you're expecting a clear, convenient list function.

(Functions that aren't useful with only one argument (like min-key) can be overloaded to provide both: (min-key f xs) could operate on the elements of xs, while (min-key f a b) operates on a and b. This is what Python does. This is a potentially susprising irregularity, though ((min-key f a) no longer does what you expect), and it doesn't work for functions that can usefully take one argument. So I don't think it's a good idea.)

Clojure's unconventional symbols

If you asked me what a symbol is, I'd probably say something like “a canonicalized string”. I might explain why this is useful, or mention that some languages (e.g. Common Lisp) include top-level bindings and plists and packages as part of their symbols, even though those are really a different concept. But I'd take for granted that canonical identity is the central idea. You can't have symbols without intern, can you?

Clojure does. It creates a new symbol for each occurrence it reads, with no attempt to canonicalize them. Despite its name, clojure.lang.Symbol/intern always makes a new symbol. It does intern the strings that are their names, to make comparisons faster, but not the symbols themselves. (There's also clojure.core/intern, but that creates Vars — top-level definitions — not Symbols.) Observe:

user=> (identical? 'a 'a)
false
user=> (= 'a 'a)
true
user=> (identical? (clojure.lang.Symbol/intern "a") (clojure.lang.Symbol/intern "a"))
false

(identical? is Java ==, and = is Java .equals. The lengths of their names hint at their relative frequency in Clojure.)

Because symbols aren't interned, any code doing symbolic processing must compare them by name rather than identity. This looks at first glance like sloppiness, or a missing feature. Indeed, it does have one harmful effect: gensym can't quite guarantee that the symbols it creates won't collide with anything (although this risk is largely theoretical, and could be essentially eliminated by putting gensyms in their own namespace). But for the most part, it's harmless. Interning symbols sounds like a basic semantic feature, but it's not. It's only an optimization.

Digression: namespaces, and references vs. names

Symbol comparisons are actually more complicated than =, because Clojure symbols also optionally include a namespace. user/a and a are thus two different symbols — one with a namespace, one without — but they name the same variable:

user=> (= 'user/a 'a)
false
user=> (def a 1)
#'user/a
user=> user/a
1
user=> (def user/a 2)  ;redefinition!
#'user/a
user=> a
2

This appears to make symbol comparison impossible, since determining what definition a name refers to requires looking at the environment, not just at the symbol. But this is true in any language with lexical scope; including a namespace in the symbol doesn't make it harder. It's only a potential problem for plain old symbol processing, and you probably wouldn't use qualified symbols for that anyway.

What's really going on here is that symbols in Clojure have two roles. In addition to being names, they're also used as references to names, relative to the current namespace. Clojure uses the same class for both concepts: references may or may not specify a namespace, but names always(?) do. References are resolved to names (by clojure.lang.Compiler/resolveSymbol), so the first def above defines a variable called user/a, not a. This means names can be compared by = without worrying further about namespaces or collisions between them (although local bindings can still collide). In a language which resolved references directly to their definitions rather than via names, it would not be necessary to include the namespace in names, and SymbolRef could be distinct from Symbol.

Belated impressions of Clojure

Clojure is over two years old, and only last week did I finally get round to writing something in it. Some reactions after writing a few hundred lines:

• Error reporting is often a bane of new languages, but Clojure's is pretty good — usually you get a Java stack trace. However, I did get a number of NullPointerExceptions without stack traces.
• I often made what must be a standard newbie mistake: using parentheses in place of square brackets. Some forms, like when-first, handle that well:

  user=> (when-first (x nil) 3)
  java.lang.IllegalArgumentException: when-first requires a vector for its
  binding (NO_SOURCE_FILE:0)

  But fn gives a singularly confusing error:

  user=> (fn (x) 2)
  java.lang.RuntimeException: java.lang.IllegalArgumentException: Don't know
  how to create ISeq from: clojure.lang.Symbol (NO_SOURCE_FILE:136)

  This could be easily fixed by checking the type in psig in fn's expander:

  (if (not (vector? params))
    (throw (java.lang.IllegalArgumentException.
            "fn requires a vector for its parameter list")))

• Accessing nonexistent fields of struct-maps gives nil instead of an exception. This is consistent with other dictionaries, but it means this error isn't detected reliably, even dynamically.
• doc is the first thing on the cheatsheet, but I didn't notice it until after I'd spent much of a day manually looking things up. :/
• The documentation for proxy says it “expands to code which creates a instance of a proxy class that implements the named class/interface(s) by calling the supplied fns”, which sounds complicated and potentially inefficient. So I was very suspicious of it until I realized it's just inner classes.
• Something like half of my total difficulties were about the Java libraries, not Clojure.
• Java's GUI libraries are not entirely easy to use, but it's still wonderful to be able to take GUI support for granted. I'm used to GUI being possible in theory but not in practice.
• for, doseq and range did exactly what I wanted, with no mental effort.
• dosync took some getting used to. ref, deref and alter aren't unfamiliar, but having to announce in advance that you're doing state is a little unnerving. I didn't have any problems with code that might or might not be called in a transaction, but I was afraid I might. I'm not used to keeping track of this.
• The inability to nest #(... % ...) is annoying. In about 200 nonblank noncomment lines, I used it five times. It would have been seven, but two of those would have been nested (immediately, in both cases) inside others. On the other hand, there were several other 1-argument fns that could have been written with #(... % ...), had I thought of it — which I didn't, because my pet language's equivalent only does partial application.
• (alter r f x) is equivalent to (alter r #(f % x)). This saves a little typing, but it's such an arbitrary convenience that I found myself worrying about whether it worked with each function's argument order.
• Clojure structures are dictionaries, but this isn't important; so far I've only used them like ordinary user-defined classes whose accessors happen to have names beginning with colons. It does mean they appear in a strange place in the documentation, though.
• assoc is obvious in retrospect. I have wanted such an operator for structures, and I'd probably want it for dictionaries too, if I ever used nondestructive dictionaries.
• Some functions I missed: abs, expt, union and intersection (they exist in clojure.set but not in the default namespace, and they don't work on lists), member? (on values, not keys), for-each (yeah, I know, I'm not supposed to want it), and a function that returns the first element of a list that satisfies a predicate.

Array mapped hash tries and the nature of data structures

Clojure provides several immutable collection types: ordinary lists, associative arrays, and "a hash map and vector both based upon array mapped hash tries". Array mapped hash tries? What are those?

The short answer is that they're hashtables whose bodies are tries (prefix trees) made of bitmapped sparse arrays. ("Array mapped" refers, rather confusingly, to the last part.) The long answer can be found in two of Phil Bagwell's papers: Fast and Space Efficient Trie Searches and Ideal Hash Trees.

Nowadays most programmers are used to thinking of hashtables as a primitive data structure, but they're not as simple as they look. Ordinary hashtables combine three ideas in their implementation: arrays, hashing, and reprobing. Arrays are the most space-efficient collection type, so naturally you want to use them for everything, but they have the limitation that they can only be indexed with (a contiguous range of) integers. Hashing fixes this - it turns anything into an integer, suitable for indexing arrays or whatever data structure you please, at the cost of introducing collisions. Reprobing deals with those collisions, without the inefficiency of chaining. The combination has the coveted trait of fast constant-time lookup, so almost everyone uses it, but it's not the only way to build a hashtable.

Each of those three concepts can be used independently of the others. In particular, hashes can be used to index other structures than arrays. This is what Clojure does. Rather than backing its hashtables with (reprobed) arrays, it backs them with tries, treating the hashcode as a sequence of 5-bit integers. Tries are less efficient than arrays, of course, but they have the advantage of nondestructive update in log time. Clojure's collections are immutable, so efficient nondestructive update is a must.

(Mini-rant: I refuse to call it "persistence". There are plenty of other words for this - "nondestructive", "functional", "incremental". Do we have to appropriate a term with a well-established meaning that is both important and likely to be used in the same context?)

Tries have a singularly confusing name, which may explain how little attention they get. But they also have a space problem: each node may have a significant number of children, which must be accessed quickly, so an array is the obvious choice. But most nodes have only a few children, so arrays would waste a lot of space. Bagwell's (and Clojure's) solution is to use bitmapped sparse arrays. Each node of the tree has a bitmap showing which children are present - and then a small array containing only those entries. For example, in a base-32 trie, a node with children 1, 5, and 11 would be represented by a bitmap 100000100010 and a 3-element array containing pointers to the children. This represents a 32-element sparse array in only 4 words! It's not even inefficient to index into, as you can determine the index of an entry by counting the 1 bits below it in the bitmap. This is supported in hardware on most architectures - but not, alas, on x86.

But even with hardware support, these tries are considerably slower than ordinary hashtables - they're fast log time, not fast constant time. There is an unavoidable price to nondestructive updates: they require keeping more information around than destructive ones. We functional programmers are used to thinking of state as a valuable (if hazardous) optimization tool, but we often mistake the reason. The main performance benefit of side effects isn't from the obvious operations like nconc, that use state to recycle old objects and slightly reduce allocation. Much more important is the freedom they give us, to use different data structures and different algorithms, and to express our programs in different ways.

Clojure

While I'm talking about new Lisps, I should mention Clojure, a new Lisp with close JVM integration and fancy concurrency support. I've been meaning to write something in it and post about the experience, but it may be a while before I get around to that. So here's the quick summary:

Clojure has the usual features of modern Lisps: lisp-1-ness, case-sensitivity (because it's hard to do case-insensitivity right), distinguishing () from nil from |nil|, pure symbols, shorter names, modules. It's quite clean, although Lispers should watch out for the renamings (familiar names like cons and do aren't what you expect). There is destructuring in binding constructs, and lambda is really case-lambda. Its Lispy core looks quite good (although as I said, I haven't used it much yet), and it closely resembles the orthodox modern Lisp.

Except for one thing: most data is immutable. Clojure aims at the most popular open problem in languages today: safe concurrency. Like Erlang, it tries to provide state only in forms that are easier to use safely in concurrent programs. Clojure has three: mutable special variables (since their bindings are per-thread), software transactional memory, and reactive message-passing. (See those pages for explanations and examples. There's also a wiki with more examples.) What it doesn't have is the ordinary mutation we take for granted in other Lisps. There's no setf, no mutable arrays or hashtables, no push.

Fortunately there's a lot of careful support for immutable collections, including syntax for [vectors] and {maps}, and generic iteration (even on Java collections!). It includes some useful functions that are often forgotten, such as mapcat and range. Clojure may not have state, but it tries to do the alternatives well enough that you don't feel the lack.

The ultimate alternative to language limitations is an FFI. Clojure is implemented in Java and runs on the JVM, so its FFI takes the form of extensive Java integration: nil is Java null, some interfaces are supported (in both directions!), and it's very easy to call Java code. There are some downsides to staying so close to Java: there's no tail-call optimization, and since threads are Java threads, their number is limited (potentially annoying, in a concurrent language). The upside is that it inherits all sorts of functionality from Java - the VM, massive libraries, even mutable data if you need it. This goes a long way toward explaining the completeness and high quality of the implementation.

There's something I'm wondering about, though. How do you pronounce Clojure? Same as "closure"? Or with /ʤ/ as in "Java"?