Tuesday 4 August 2009

Arc's Accum Macro and Transient

Arc is Paul Graham's shot at writing a new Lisp. Recently there was a comment on Y Combinator about how Clojure's transients would enable writing an efficient version of Arc's accum macro. Original comment here.

Having never used Arc, I looked up the definition in the latest release of the source.

The code is very readable and it's clear to see that this creates an accumulator (with a unique symbol) and names the symbol the user provides as an function that pushes onto the accumulator. This means that you can write simple functions that iterate over data and just keep accumulating results. For example, the functions to get the keys and the maps of map are defined as iteration over the key value pairs and pushing the values into the accumulator.

So, how do we translate this into Clojure, and how do transients help?

The first version I did had a subtle bug in it; relying on the fact that the accumulators identity is persistent. This is an implementation detail and shouldn't be relied on. This unfortunately results in the messy with-local-vars. This is definitely very verbose compared to the Arc code! Is there a better way to do it?

The definition is (obviously) very similar to Arc's code (they have common ancestry). The reader macro for unique symbol definition (trailing #) feels more concise than the w/uniq of Arc (but perhaps I'm missing something?).

Once you've seen this code it becomes clear why transient data structures help. Without them, it'd be inefficient otherwise, creating additional copies of the structure. This way around we're making minimal changes to the data and creating less garbage.

Even from reading a tiny bit of Arc it's clear there's lots to learn from the source and ideas of structuring code / macros. Time to do learn some more Arc me thinks!