Skip navigation

Clojure is a new Lisp on the block.  It runs on the JVM, giving it full access to any Java library (and its complement), but it leans more towards the functional paradigm, so data structures are immutable (a big boon for concurrent programming, as locks become obsolete).

In addition to supporting the usual data types of Lisp, Clojure has added syntactic support for vectors, maps and sets.  Some sacrifices have been made for performance; in order to have immutable data structures, it returns a new data structure for each mutation.  However, because the parent data structure is immutable, much of the structure can be shared. Performance-wise, Rich Hickey has stated that “I’ve tried to keep [operations] all within 1 to 4 times [the equivalent] Java data structure, [but lookup times are frequently faster]”.

For example, copying a normal hash map would be quite expensive, but by using a modified version of Phil Bagwell’s Hash Array Mapped Trie (HAMT) (a hash table with near optimal performance characteristics), near-constant time operations are possible.  The key is that the tree is quite wide; for optimal performance, the number of branches should be equal to the number of bits in the architecture.  That means that for a 32 bit machine, a trie of 10^12 entries would have a depth of 8 (log(10^12)/log(32) = 7.97) (this may not be exactly true, due to the sparse nature of hash trees, but it gives an idea).  This is obviously quite small. Because the tree is so shallow, most lookups are near constant.

Modifying a hash map would involve copying each node in the path to the modification and returning the new root node.  All unchanged nodes would not require any special treatment, but they are now part of multiple hash maps.  This seems expensive, but it is much better than copying the entire structure.  If many changes are occurring, I suspect that most extra nodes would rapidly be garbage collected, so space shouldn’t be as much of an issue, so the only possible issue is the copying overhead.  Not surprisingly, modifying hash maps is probably going to be a bit slower than modifying the structure directly, and so is probably one of the operations that Rich was referring to above, but tradeoffs must be made.

It should be noted that Clojure is not finished; breaking changes are made and development tools are not yet fully featured.

For example, if you use Clojure with slime, useful error messages are left in the inferior lisp buffer, and a simple “Evaluation aborted” message is printed in the repl, and the minibuffer simply says “error in process filter: Wrong number of arguments: nil, 3”.  This should be fixed with newer versions of swank-clojure or clojure, whichever is the source of problems.  In the meantime, running slime-redirect-inferior-output, or adding (add-hook ‘slime-connected-hook ‘slime-redirect-inferior-output) to your .emacs file will fix the problem.

Clojure also supports lazy evaluation, and infinite sequences as a result.

I’m quite excited by this new lisp, and can’t wait to try it out on some larger projects.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: