I was recently play­ing around with D3 and ClojureScript and I ended up cre­at­ing this silly exhaustive sort sim­u­la­tor for the TSP. I ended up learn­ing a cou­ple of things:

Lazy Sequences are useful even outside of a pure Clojure context.

I actu­ally came across a good use case for lazy sequences putting this togeth­er. The trav­el­ing sales­man prob­lem is an NP-hard prob­lem and an exhaus­tive solu­tion to it is an O(n!) algo­rithm, which makes it ridicu­lously slow for any­thing but a triv­ial num­ber of nodes. Now, the goal of my sim­u­la­tor was not to actu­ally cal­cu­late solu­tions to the TSP, but just to show the exhaus­tive sort in action. You can see what it does by look­ing at the simulator, but in short, it shows each per­mu­ta­tion in sequence as it searches for the best one.

The intu­itive way of doing this would be to write code which com­putes each stage of the sort and then mod­i­fies the SVG ele­ments accord­ing­ly. The prob­lem with this approach is that it merges the sort­ing code with the visu­al­iza­tion code, which would make it more dif­fi­cult to sim­u­late dif­fer­ent sorts if I wanted to, or to adjust the visu­al­iza­tions. In addi­tion, D3 is asyn­chro­nous which means this approach won’t work any­way as suc­ces­sive calls to D3 will not actu­ally ani­mate them in sequence. In the­ory what I would have had to do was cre­ate a queue which D3 con­sumed from and which the sort­ing algo­rithm wrote to, but this would require both unnec­es­sary state and thread­ing, which Javascript does­n’t really do.

The real solu­tion was to have D3 make suc­ces­sive calls to the exhaus­tive algo­rithm in a call­back. This could be an unwieldy thing to do, try­ing to pass the entry cur­rent state of the algo­rithm in a map between D3 and get-next-permutation but using a lazy sequence actu­ally made it sim­ple. Gen­er­at­ing a lazy sequence of per­mu­ta­tions and pass­ing that sequence to my D3 func­tion means that each state will be com­puted when need­ed, but not soon­er. This means that we can treat an exhaus­tive set of per­mu­ta­tions for a hun­dred nodes ¹ as if it where an ordi­nary sequence and not worry about the mem­ory usage or wait­ing. It also means that the sort­ing code can be strictly divorced from the visu­al­iza­tion code, which makes it sim­ple to write new sorts or visu­al­iza­tions with­out hav­ing to redo other parts of the pro­gram. It also makes the code more DRY. You’ll notice that the result­ing sim­u­la­tion runs very smooth­ly.

Macros in ClojureScript are annoying.

My sim­u­la­tor used a cou­ple of macros which were prob­a­bly unnec­es­sary but I chose to use any­way for the exer­cise so to speak. Clo­jure­Script, it turns out does not include eval and as such does not natively sup­port macros either.² Macros in Clo­jure­Script are actu­ally Clo­jure macros which are included using the :require-macros con­struct. This is annoy­ing mainly because they are defined in a sep­a­rate namespace from the rest of the Clo­jure­Script code. This means that not only do you have to define the Clo­jure­Script macros in a sep­a­rate file, prob­a­bly in a sep­a­rate part of the appli­ca­tion, but you also have to use hacks to pre­vent the code from expand­ing into namespaces which don’t exist in the Clo­jure­Script envi­ron­ment.

For exam­ple, sup­pose you want to use the Math.pow() func­tion in your Clo­jure­Script macro? You might attempt some­thing like this:

(defmacro foo [a b c ...]
  `(Math/pow (+ ~a ~b ~a ...)))

This looks like it will work, but because this code will be expanded in Clo­jure, and Math is both a Java and Javascript object, Math/pow will expand to the Java name, java.lang.Math.pow rather than the Javascript func­tion Math.pow(), and the result­ing code will result in an unde­fined func­tion error. The solu­tion is to use a sym­bol capture:

(defmacro foo [a b c ...]
  `(~'Math/pow (+ ~a ~b ~a ...)))

but this is a hack and is frowned upon in Clo­jure exactly because it can lead to sym­bols being mis­in­ter­pret­ed. The mak­ers want to solve this by writ­ing a native Clo­jure­Script macro system(Apparently not :)) but it seems to me that just writ­ing a new macro form which expands its argu­ments dif­fer­ent­ly, you could do away with a lot of the annoy­ance.

D3 is not as hard as it’s made out to be.

For some rea­son D3 is often described as hav­ing a large learn­ing curve but I haven’t found that to be so. The only real issue in my expe­ri­ence is oin under­stand­ing that it is rather strictly declar­a­tive and work­ing within the result­ing lim­i­ta­tions. You don’t tell D3 what to do or how to do it but instead tell it what you want accom­plished and then let it do it’s job. When you get the hang of this, it’s actu­ally very sim­ple.

It’s a lit­tle mis­lead­ing that D3 makes such heavy use of method chain­ing, because typ­i­cally when you chain meth­ods, the actions they sig­nify occur one after anoth­er, sequen­tial­ly. How­ev­er, D3 uses method chain­ing to define dif­fer­ent aspects of a data bind­ing/­trans­for­ma­tion/an­i­ma­tion. Val­ues that in other libraries or lan­guages would be set in one huge com­pli­cated func­tion are instead set with chained meth­ods and the action they define isn’t launched until the func­tion chain is run. So:

d3.selectAll("p").data(some_data)
  .style(function(d) {d.style})
  .text(function(d) {d.text});

tells D3 that it should change the style and text of p ele­ments in an HTML doc­u­ment but it does­n’t actu­ally run the oper­a­tions direct­ly. Instead, it builds the oper­a­tion and d3 per­forms it asyn­chro­nously after this code has been eval­u­at­ed. So, you can’t do things like this:

d3.selectAll("p").data(some_data)
  .style(function(d) {d.style})
  .text(function(d) {d.text})
  .data(some_more_data)
  .style(function(d) {d.style})
  .text(function(d) {d.text});

or like this:

d3.selectAll("p").data(some_data)
  .transition()
  .style(function(d) {d.style})
  .text(function(d) {d.text});
d3.selectAll("p").data(some_more_data)
  .transition()
  .style(function(d) {d.style})
  .text(function(d) {d.text});

It won’t work. You have to use call­backs for suc­ces­sive tran­si­tions. D3 is meant to be called when data changes to bind HTML or SVG to data and not really as a gen­eral pur­pose SVG trans­for­ma­tion library.

1. 100! => 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000 ↩
2. Also, this means that ClojureScript, unlike Clojure, is not a true Lisp because the entire language is not present at all times. This is an understandable but disappointing trade-off. The better solution IMHO, would have been to make dead-code elimination an optional feature, but incompatible with eval. Meaning that the majority of application which do not need eval, could be made much more efficient, but those that do need it would have it available. Actually, this is a feature I would like in JVM Clojure because it would make it possible to write fast-loading Clojure programs just by avoiding eval use. Clojure on Android might actually be feasible in that case. ↩