The Clojure macro binding is frequently handy for mocking out functionality during testing, but this sometimes does not behave as desired in multi-threaded context. Fortunately, there's a solution...

For example, at work we have unit tests on functions that may attempt to talk to network services, which we'd rather they not do:

(defn send-request [request server]
  '(...do real RPC stuff here...))

(defn average-timestamp [time-servers]
  (/ (apply + (map #(send-request :get-timestamp %)
                   time-servers))
     (count time-servers)))

In order to test average-timestamp, we need a "mock" function that will stand in for send-request. This must be a function that takes a request and a server and returns a timestamp, just like the real send-request. For this example, it can take the timestamp itself as the "server" and simply return that timestamp. For bonus points we can make sure the request parameter is what we expect:

(defn mock-send-request [request server]
  (assert (= request :get-timestamp))
  server)  ; assume "server" is actually the timestamp

(mock-send-request :get-timestamp 5)
;=> 5

Using binding we can temporarily replace send-request with mock-send-request:

(binding [send-request mock-send-request]
  (send-request :get-timestamp 5))
;=> 5

(binding [send-request mock-send-request]
  (average-timestamp [5 15]))
;=> 10

So there's the background: a pretty normal way to mock out stuff in Clojure. What this doesn't address is when some clever co-worker (hi, Nathan!) realizes that average-timestamp would work better if it talked to multiple time-servers in parallel, and that this could be easily accomplished by replacing the use of map with pmap:

(defn average-timestamp [time-servers]
  (/ (apply + (pmap #(send-request :get-timestamp %) time-servers))
     (count time-servers)))

This is an easy single-letter change that indeed works quite well with the real send-request. But when we try to use binding to mock it out, we run into problems:

(binding [send-request mock-send-request]
  (average-timestamp [5 15]))
; java.lang.ClassCastException:
;   clojure.lang.PersistentList cannot be cast to java.lang.Number

It's not obvious from the error message, but what's happening is our original un-mocked send-request is getting called. This is because binding only has an effect on the current thread, but pmap causes send-request to be called in other threads.

The solution is simple enough in Clojure 1.0 -- you simply mock out pmap as well, and since the API is identical to map, it's quite easy to do. But as you can see, this does us no good at all in recent versions of Clojure:

(binding [send-request mock-send-request
          pmap map]
  (average-timestamp [5 15]))
; java.lang.ClassCastException:
;   clojure.lang.PersistentList cannot be cast to java.lang.Number

The reason is that starting with Clojure 1.1, most clojure.core Vars are linked directly into code that uses them. This means that our definition of average-timestamp above links directly to the actual definition of clojure.core/pmap, not just the Var that points to it, thus attempts to rebind the Var with binding are futile.

But do not despair, there is a solution even for this. All you need to do is tell Clojure not to directly link pmap when it compiles average-timestamp. This is done by adjusting pmap's metadata before average-timestamp is compiled, like so:

; Set pmap to be dynamically linked
(alter-meta! #'pmap assoc :dynamic true)

; Must now re-define the function that uses pmap
(defn average-timestamp [time-servers]
  (/ (apply + (pmap #(send-request :get-timestamp %)
                    time-servers))
     (count time-servers)))

; Finally, our mocking out of pmap works
(binding [send-request mock-send-request
          pmap map]
  (average-timestamp [5 15]))
;=> 10

The best place to put the alter-meta! depends on your particular use case. You might want to figure out how to do the alter-meta! only when in testing and not in production. Remember that the metadata on pmap is global -- you're changing the only metadata that clojure.core/pmap has, so the namespace you're in when you do it makes no difference at all.

In our case at work however, the performance impact of leaving pmap dynamic all the time was not enough to worry about. Dynamic linking is still pretty fast and is fine even for our production uses of pmap in this particular code base. So we simply put the alter-meta! at the top of the file that used pmap and got on with our unit testing.

The Joy of Clojure

Thinking the Clojure Way

by Michael Fogus and Chris Houser

A normal Clojure REPL (or prompt) in a terminal window is by default a bit touchy about infinite seqs, deeply nested structures, and long-running operations. Any of these can cause your REPL to wander off into the weeds, busy spinning, perhaps printing pages of useless data, with the only apparent remedy being to press CTRL-C, which generally kills the entire JVM, Clojure and all, and dumps you back at your operating system prompt.

It's unfortunate that this is the default, but Clojure's youth shows particularly when it come to tools and settings like this. Happily it's sufficiently mature to provide several solutions that are not difficult to apply.

(set! *print-length* 103)

(iterate inc 0)
;=> (0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
    24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
    45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
    66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
    87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 ...)

(set! *print-level* 15)

(let [x (atom 0)] (reset! x {:deeper x}))
;=> {:deeper #<Atom@4cb533b8: {:deeper #<Atom@4cb533b8:
    {:deeper #<Atom@4cb533b8: {:deeper #<Atom@4cb533b8:
    {:deeper #<Atom@4cb533b8: {:deeper #<Atom@4cb533b8:
    {:deeper #<Atom@4cb533b8: {:deeper #}>}>}>}>}>}>}>}

Run-away exercise bikes

But these settings only help take control of run-away printing. Sometimes the REPL gets hung up doing something other than printing, sitting there spinning away like a stationary bike, and neither of these settings will help you. My final advice is to use repl-utils to register your REPL thread as killable by CTRL-C:

(require 'clojure.contrib.repl-utils)
(clojure.contrib.repl-utils/add-break-thread!)

Now when you press CTRL-C, instead of shutting down the whole JVM, an exception will be thrown within the REPL thread, which is usually exactly what you need to halt run-away computation. Note that repl-utils does this using a deprecated Java API that is described as unsafe. And yet it remains useful for just such circumstances. For example:

(deref (promise))

Look at that -- instant deadlock! Now press CTRL-C, and you get:

java.lang.Exception: SIGINT (NO_SOURCE_FILE:0)

...and you're back to REPL prompt. But now you've violated Java, so I'd recommend saving what you need to save and then restart your JVM anyway. If you don't, weird things can happen. For example if you run the above deref-promise example again immediately, it may fail with a slightly different exception, even before you press CTRL-C. Similar strangeness can occur if you press CTRL-C at the REPL when no operation is running, though in that case it usually just kills your next expression, whatever it is.

Hopefully by setting your *print-length*, *print-level*, and break-thread, you can feel more comfortable at the REPL with less fear of getting stuck.

The Joy of Clojure

Thinking the Clojure Way

by Michael Fogus and Chris Houser

There are a few books about Clojure in the works now. But despite the variety in authorship and publisher, they all seem to be primarily in the vein of a language tutorial, starting from a basis of "common knowledge" among most programmers and taking the reader to a level of basic familiarity with Clojure.

Michael Fogus and I think there is more to Clojure that has yet to be addressed by any of the books currently being written. So we've started writing "The Joy of Clojure". Our vision for this book is to impart not just what Clojure is, but why it's the way it is; not just how to use it, but how to choose well from among the wide variety of options Clojure provides. And along the way we hope you'll experience the wonder, amazement, and, yes joy that Clojure can bring to programming tasks that often feel like nothing more than chores in other environments.

I also wanted to take this opportunity to brag a little on Fogus. He's been a fantastic partner throughout this process -- I wouldn't even be involved if it weren't for him. He has put into our book many references to papers and books that I've never heard of, but that illuminate much of Clojure's design -- clearly he has read a good deal more than I have. Once we're done writing, I intend to use the Bibliography as a reading list -- I'm sure it will be enlightening. He is dedicated to producing the best book we can, and he's the only reason we're meeting any of our deadlines. I'm looking forward to the next few months as we finish this book together.

The Joy of Clojure

Thinking the Clojure Way

by Michael Fogus and Chris Houser

The code making up Clojure's current implementation can be divided into 3 main groups:

1. The compiler -- used at the REPL and for AOT compilation, the compiler translates Clojure expressions into JVM bytecode. For this discussion, the reader lives in this group.

2. The data structures -- persistent maps, sets, and vectors, sorted and unsorted. For this discussion we'll also include here the reference types (ref, agent, var, atom) and the STM implementation.

3. clojure.core -- Destructuring, most of syntax quote, the Clojure functions for manipulating seqs (filter, map, for, doseq, etc.) and all the other programmer-facing functions we know and love.

Today, Clojure is written mostly in Java. Of the groups above, only the core library is written almost entirely in Clojure. This is no small thing, mind you -- the language that is defined by just the first two is an awkward, tiny little language that is rather painful to use. (You can see this demonstrated near the top of clojure/core.clj.) However, there is still quite a bit of code in the compiler and data structures, and they're almost entirely implemented in .java files.

Clojure-in-Clojure is the effort to re-write the compiler and built-in data structures in Clojure. Note that the primary compiler implementation would still run on the JVM and still produce JVM bytecode. This is not about getting rid of the JVM or implementing any new runtime or virtual machine.

The author of Clojure, Rich Hickey, has been contemplating changing the behavior of one of Clojure's core features, the seq abstraction. He's been working on a few different alternatives for a couple months now.

First, a quick review of how things stand now. Currently a lazy seq can be produced by using lazy-cons:

(defn my-range [from to]
  (when (< from to)
    (lazy-cons from (my-range (inc from) to))))

Calling my-range returns a lazy seq of the integers between from and to. This seq can be used by any of the functions that consume seqs:

user=> (reduce + (my-range 5 10))
35

Reduce takes the first two numbers in the seq (5 and 6) and passes them as parameters to the addition function. This result and the next value from the seq (11 and 7) are passed to the addition function again. This continues until the end of the seq is reached, and the result (35) is returned.

The first alternative I heard about is the Left Fold Enumerator (LFE). LFEs are about inversion of control, where the function passed to reduce would be in charge of the looping and could choose to stop before the end of the seq and signal to the seq to free any resources it was holding.

This was was explored in much more detail by Christophe Grand.

However after some consideration, Rich appears to have abandoned the idea of replacing Clojure's current seq abstraction with LFEs.

The next alternative is something called "streams". These are stateful iterators, carefully protected to help prevent the problems of state that Clojure sets out to solve. Their main benefits over the existing seq model are better performance and more complete laziness. Clojure's existing seq abstraction could be built on top of streams such that both the extra laziness and most of the performance would be available to user-level code that remains almost entirely unchanged

One user-visible change would be the loss of a feature called nil punning. Currently, something that returns a seq actually promises to return either an instance of ISeq (which is guaranteed to have at least one item in it), or nil. Since nil acts like false, you can write code like:

(if (filter odd? coll)          ; nil pun
  (println "coll is a bit odd")
  (println "no odds in coll"))

If there are no odd numbers in coll, filter promises to return nil, otherwise it will return a lazy seq containing all the odd numbers.

With streams, though, the behavior changes: filter could return a non-nil object representing an empty stream. This provides the extra laziness that's desirable, but the example above would no longer be correct. If you want to find out if the stream is empty, you must force it to do some traversal, the idiom for which is to get a seq of the stream:

(if (seq (filter odd? coll))
  (println "coll is a bit odd")
  (println "no odds in coll"))

The only way to save nil punning would be to provide a whole separate set of seq-library-like functions for dealing with streams: filter-stream, map-stream, concat-stream, etc. These would not allow nil punning, but the regular seq functions would continue to behave as they always had.

Despite the potential loss of nil punning, Rich thought this approach had enough promise that he forked a streams branch of Clojure and wrote some docs:

(defn my-range [from to]
  (let [a (atom (dec from))]
    (stream
      (fn [eos]
        (swap! a inc)
        (if (< @a to)
          @a
          eos)))))

But the stateful and imperative nature of the streams code were apparently unpleasant enough that he began looking at another alternative. This new lazy branch does not have quite the performance benefits of streams, but does keep the immutable nature of Clojure and adds the extra laziness demonstrated by streams.

The lazy-cons macro is gone, and instead there is a lazy-seq macro:

(defn my-range [from to]
  (lazy-seq
    (when (< from to)
      (cons from (my-range (inc from) to)))))

This has the same loss of nil punning as streams, but perhaps the extra laziness is worth it.

But what happened to the resource management touted by LFEs? It appears likely that a new macro (currently named 'scope' in the streams branch) will be introduced to help with that problem, regardless of whether the lazy or streams branch is finally adopted.

So there you have it -- two forks representing possible futures for Clojure. Which will be the chosen path? Well, I can't say for sure, but the only drawback of the lazy branch compared to today's Clojure is the loss of nil punning, and Rich seemed pleased by how little code in clojure.core was actually making that assumption. There's even a compile-time flag that can be turned on to help users track down their nil puns, which I'll blog about later.

Besides, I think Rich pushed streams as far as he could toward simplicity and protection against mutation, and still didn't like the results. I doubt the streams branch has much future, but Rich has been asking for feedback so now's the time to explore the options and make your opinion know.

In my next blog post I'll show my setup for easily switching between Clojure branches.

Update: My next blog post will not be about switching Clojure branches. As of Tue Feb 17 2009, the lazy branch was merged into trunk.

for( var i = 0; i < foo.length; ++i ) { ... }

That pattern is used very often in JavaScript to do something with each item in the array foo, setting aside for the moment that it's often not quite correct (if the var i is declared anywhere else in the same function).

You'd think they would have provided a more succinct way to walk
through an array. And actually they tried:

for( var i in foo ) { ... }

but they screwed it up, because in this case i is set not to each
value in foo, but to each index, 0 through whatever. ...as a string.

So the first time through, i is the string "0". Fortunately (I suppose) this still works as a parameter to your array, because you can say foo["0"] to get the initial item in the array.

But the knowledge of the amount of work being done to convert the integer range 0 through length into a series of strings, back to ints, and then look them up again in the array just pains me too much. It's not that the performance has actually ever hurt me in such cases, it's just that I can't stand to do it.

So I type for( var i = 0; i < foo.length; ++i ) one more time, and glance around to make sure i isn't being used for anything else nearby...

Someone asked me about the path that lead me to Clojure. On the off chance that he's not the only one curious, I thought I'd post the answer here.

Sometime after college I started hunting for the "best language", not with any formal definition but as a personal quest for what I liked the best. A primary criteria was something I called "expressiveness". I don't know if I can define that accurately, but it has something to do with being able to provide APIs that concisely model whatever specific domain you're dealing with. A common example is how much easier it is to work with text in perl (because of strongly integrated regex support) than it is in C.

My "best language" before Clojure was Ruby, because of its clean object system and iterators, but I hadn't experienced any functional or immutable languages yet.

I had heard a lot about how amazing LISP was, but I didn't get it. I couldn't figure out why anyone liked LISP's annoying syntax, or why anyone (who wasn't deeply into Artificial Intellegence) would want to write programs that write programs. So one big turning point was reading "On Lisp" by Paul Graham (free download). By the time I was done with that book, I was convinced that any "best language" had to support macros.

So I tried to use Common Lisp, but just couldn't make it "stick". I had learned plenty of other languages, and usually enjoyed the process, but Common Lisp's lack of libraries really drove me nuts. I could do network, file or text stuff in 4 or 5 lines of ruby that took a page of code in Common Lisp. So I shelved Common Lisp for a while.

I do a lot of C++ and JavaScript at work, and was learning to really like JavaScript -- clean syntax, closures, direct support for hash-maps and regex, a builtin "gui" system. So it was easy for Yegge to lure me into trying JavaScript on the JVM, especially with the promise of optional static typing, which I was pretty sure I wanted.

Around the same time I learned about Project Euler, and thought it would be a great way to get used to using JavaScript for general purpose programming rather than just browser stuff. I did the first five PE problems in JavaScript before giving up. It was terrible. Not only was there no static typing yet, but things that had been minor annoyances in the browser now seemed to be giant obstacles to solving the problem at hand. Re-reading some of Yegge's cheerleading brought me to the conclusion that he's actually endorsing some private language based roughly on JavaScript. None of the other languages that Google lets him use are as malleable, and Rhino lets him code up whatever new features he wants in Java and morph the language to his will. This is great for him, I'm sure, but was lousy for me.

I hadn't used Java in any capacity for years, but now thanks to Yegge I had it installed and ready to go. This made me more willing to try Scala. I don't remember how I heard about it, but I picked it up to work on the rest of the PE problems, and this is when I started to learn about immutability. Scala encourages the use of immutable locals, and has a few immutable collections. I expended a lot of energy bending my problem-solving thought processes to this new context. Scala also has lazy streams, which was another big hurdle. Both of these were challenging to learn, but once I got it, they were very rewarding tools to have at my fingertips. Project Euler was my primary teaching tool, forcing me to learn new concepts a little at a time. The folks on the IRC channel helped me when I got stuck, though in exchange, I frequently had to endure condescension from some of them.

So this was going along okay, until I thought I had enough Scala under my belt to take a crack at a tricky little API I'd had on my mind. I'd been wanting a way of picking data out of HTML documents, something with the expressive power of XPath, but that embedded cleanly in the host language. I wanted to be able to provide new functions, filters, etc. (have you tried to work with dates in XPath and XSLT??), and for the return values to be host language data structures, not more XML documents. I'd actually built a beastly little project using xlstproc and ruby, but that's another story altogether.

Anyway, I began sculpting this API in Scala. I spent a day or two experimenting with syntax, the right combinations of traits, implicits, etc. to create the kind of XPath-like expressions I wanted. I finally got the beginnings of something that I thought would work, and compiled a minimal test. Well, tried to compile it, but the types weren't quite right. I then spent the another day or two trying to get the type declarations correct enough to even compile, and finally gave up in frustration. I'm sure it would have been possible to make it work, but I wanted to spend my time solving actual problems, not solving problems the compiler was making up for me. Maybe I didn't want static typing after all.

This is when I started learning Clojure. Paul Graham had convinced me I wanted a LISP. Yegge's hype about JavaScript had prepared me for the JVM. Scala had introduced me to immutability and lazy streams. Clojure let me use the best properties of each of these, so it was a very natural fit right from the beginning. I've since learned more -- how to use more immutable collections, software transaction memory, etc., and the discussion group and IRC channel have always been friendly and encouraging.

That's how I got to where I am. I don't think I'd recommend the JavaScript or Scala tangents to anyone else, but "On Lisp" may still be worth reading, at least until Programming Clojure comes out. Since bailing on Scala, I've done another 25 or so Project Euler problems in Clojure, and had so much fun I even went back and did the first 14 all over again. I also took another stab at XPath-inspired document querying, resulting in a zip-filter lib that I'll write about some other time.

Clojure's definitely closer to the "best language" than any other I've tried. If you haven't tried it yet, you should!

In the beginning was the Word, and the Word was with God, and the Word was fully God. The Word was with God in the beginning. All things were created by him, and apart from him not one thing was created that has been created. In him was life, and the life was the light of mankind. And the light shines on in the darkness, but the darkness has not mastered it.

A man came, sent from God, whose name was John. He came as a witness to testify about the light, so that everyone might believe through him. He himself was not the light, but he came to testify about the light. The true light, who gives light to everyone, was coming into the world. He was in the world, and the world was created by him, but the world did not recognize him. He came to what was his own, but his own people did not receive him. But to all who have received him – those who believe in his name – he has given the right to become God’s children

-- John 1:1-12a, NET

The program to draw the tree is 30 lines of Clojure

Below is a walk-though of solving a problem using side-effect free functions, then agents, and finally agents and watchers. It's a very slightly edited copy of a post I made to the Clojure Google Group a week or two ago. I'm including it here because the audience for this blog is a bit different from the Google group

Spoiler warning -- this is about a Project Euler problem. If you don't follow the links, I think you'll be able to understand what I'm talking about without learning anything specific enough to ruin any particular puzzle. If you want to know which specific puzzle I'm discussing (to see if you've already done it, for example) you can go to the problem description. The problem number isn't mentioned in the full solution code.

For this puzzle, I had a grid of cells, each of which had a value that depends on the values of its neighbors in a way that guaranteed a stable solution. The value of one cell was given.

My initial solution [single-threaded.clj] represented the grid as a vector of vectors of Integers, and maintained a PersistentQueue of cells that needed to be updated, with a single loop to work through the queue. For each iteration of the loop, a cell would be popped off the queue, and a new value for that cell computed. If the new value was different from the old value, the 'recur' then updated the cell in the vector and pushed the neighboring cells onto the work queue. When the queue was empty, a stable state had been reached and the answer value could be read.

This ran fairly fast, used no mutable state, and the implementation seemed relatively clean to me. I was quite pleased with myself.

But my friend Aaron Brooks who had already solved the problem was encouraging me to created a multi-threaded solution. Note the solution I had was already thread-safe, but only used one of my two processor cores.

My second solution [using-agents.clj] represented the grid as a vector of vectors of agents. The action function computed a new value for a given agent, and then used 'send' to queue up the same action for neighboring agents. It also maintained other shared state to keep track of how many cell agents were running so that it could detect when a stable state for the whole grid had been reached.

Despite the complexity one might expect from all that, the agent solution was only 3 lines longer than the single-threaded solution. It also ran about 30% faster.

But it had a bug -- often returning the right answer, but sometimes returning an incorrect number. It also seemed more imperative than the first solution, because of the 'send' calls, updating shared counters, etc. When I mentioned this on IRC, it was recommended I try watchers.

So I added a watcher to every agent before kicking off the computation process. The watcher did no computation as such, but it was the perfect place to 'send' to neighboring agents, update the running count, etc. Moving this code to the watcher also meant the action function was now pure, with no side-effects.

It was during the process of separating the stateless and state-management code that I discovered my bug -- the code to manage global state had obscured an error in the computation logic. With them completely separate, it was easier to think about the specific responsibilities of each.

It was also now easy to see that the pure computation function was almost exactly the same whether I was using agents or just a simple loop. I finished factoring out this duplication and ended up with code that could use either mechanism to solve the same problem. [with-watchers.clj]