A Recursive Walk on a String

Sometimes you don't pay attention to some details and this lead you right into the wrong direction. That's exactly what happened to me the other day. I had a specific problem I intended to solve for a while, nothing particularly difficult, but an interesting one. After hacking around for an hour, the situation was getting weird and I decided to ask for help on the Clojure Google Group. This post is an account of how that situation arose and what have been done to solve it.

Walking Recursively

The task is nearly as simple as explaining it. I needed a way to apply a function to each strings contained in a tree of nested data structures in Clojure. Not that easy to explain as you see, well you didn't really saw me rewrite the previous sentence a thousand times but you can probably picture it. My first attempt is really naive and leverages the clojure.walk library written by Stuart Sierra. It's a small library that provides functions to perform non-recursive walking of generic Clojure data structures. Lets first have a look at the walk function documentation.

user> (doc clojure.walk/walk)
-------------------------
clojure.walk/walk
([inner outer form])
  Traverses form, an arbitrary data structure.  inner and outer are
  functions.  Applies inner to each element of form, building up a
  data structure of the same type, then applies outer to the result.
  Recognizes all Clojure data structures except sorted-map-by.
  Consumes seqs as with doall. 
nil

It isn't hard to take this function and use it in a recursive one to do the job. Our function to transform strings could go in the inner argument, it's also where we'll add the recursive call. We don't need the outer one, so we will just use the identity function.

(use 'clojure.walk)

(defn recursive-string-walk [f form]
  (walk #(if (string? %) (f %) (recursive-string-walk f %))
    identity form))

It works well but there's an issue with this way of doing things, recursion will end up filling up the stack which will ultimately overflow. For the use I intend to make of this function, it isn't really a big problem, but I always like to take these kind of challenges.

A Buggy Test

The first thing that came to my mind to test the above issue was to create a nested list of arbitrary depth. We can take the iterate function to create an infinite sequence of nested function calls to list, then take and last to fetch the pit we want to test with.

user> (def pit (iterate list "bottom!"))
#'user/pit
user> (take 6 pit)
("bottom!" ("bottom!") (("bottom!")) ((("bottom!"))) (((("bottom!")))) ((((("bottom!"))))))
user> (last (take 6 pit))
((((("bottom!")))))
user> (recursive-string-walk identity (last (take 6 pit)))
((((("bottom!")))))
user> (recursive-string-walk #(str "reached " %) (last (take 6 pit)))
((((("reached bottom!")))))
user> (recursive-string-walk #(str "reached " %) (last (take 1000 pit)))
; Evaluation aborted.
user> (recursive-string-walk #(str "reached " %) (last (take 100 pit)))
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((("reached bottom!")))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))

Work great! Now lets create an informal test function. This function should take a range and a recursive walk function then will test it using pits starting with the shallowest. This way we can find exactly at which point the overflow happen.

(defn test-walk [walker shallowest deepest]
  (doseq [depth (range shallowest deepest)]
    (println (walker #(str depth " reached " %)
               (last (take depth pit))))))

We'll use it to make sure it works and see which depth our recursive-string-walk can reach.

user> (test-walk recursive-string-walk 400 500)
...
((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((((("486 reached bottom!")))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))))
(...(; Evaluation aborted.

On my computer, this function cannot go deeper than 486 (I wonder how it would fare on a 486?) which isn't that much. It shouldn't be all that difficult to make a lazy version of that function. It boils down to look for sequences and wrap their recursive calls with lazy-seq.

(defn lazy-recursive-string-walk [f form]
  (walk #(cond
           (string? %) (f %)
           (seq? %)    (lazy-seq (lazy-recursive-string-walk f %))
           :default    (lazy-recursive-string-walk f %))
    identity form))

From my understanding of lazy data structures and the walk library, this version should be able to handle data structures of infinite depth given infinite resources. However the test function didn't seems to be in agreement with me as it was crashing at 828. That's about the time I asked for help and stopped thinking about this problem for a while.

Lazy Zippers

A week-end passed by and in the meantime, some people from the group tried to help me, yet nobody found what was the real problem. That would have been miraculous given the actual source of the bug. Furthermore, I was now more convinced than before than there was no bug in the lazy version. Tom Hicks provided a lazy version of walk, which was behaving in the same way. Laurent Petit also suggested that I try to write a version using zippers.

It was an intriguing suggestion, I never used zippers but heard often about them. Additionally, that day, MarkCC from Good Math, Bad Math just posted an article about them. So I learned what they are and how to use them. I must say this is a very neat functional programming technique, really worth the time to learn. It's not that hard, Mark has done a great job explaining it. I won't go into the details, but this version is quite easy to understand when you know that the next function do a depth-first traversal automatically.

(require '[clojure.zip :as z])

(defn lazy-recursive-string-walk-with-zipper [f form]
  (loop [loc (z/seq-zip form)]
    (if (z/end? loc)
      (z/root loc)
      (recur (z/next
               (if (string? (z/node loc))
                 (z/replace loc (f (z/node loc)))
                 loc))))))

To my surprise, the test function still overflowed the stack using this version. And it could simply not throw the StackOverflowError as it executes in a loop. Maybe the error wasn't coming from the lazy walk function after all.

So Where's The Bug?

I've been negligent about one thing, I didn't look closely enough at the stack traces. The one thrown by recursive-string-walk happen to be completely different than the one thrown by lazy-recursive-string-walk. Here's both of them one after the other.

No message.
  [Thrown class java.lang.StackOverflowError]

Restarts:
 0: [ABORT] Return to SLIME's top level.

Backtrace:
  0: clojure.lang.RT.boundedLength(RT.java:1128)
  1: clojure.lang.RestFn.applyTo(RestFn.java:135)
  2: clojure.core$apply__4370.invoke(core.clj:436)
  3: clojure.walk$walk__7942.invoke(walk.clj:43)
  4: recursive_string_walk$recursive_string_walk__4137.invoke(NO_SOURCE_FILE:1)
  5: recursive_string_walk$recursive_string_walk__4137$fn__4139.invoke(NO_SOURCE_FILE:1)
---
No message.
  [Thrown class java.lang.StackOverflowError]

Restarts:
 0: [ABORT] Return to SLIME's top level.

Backtrace:
  0: clojure.lang.RT.assoc(RT.java:666)
  1: clojure.core$assoc__4259.invoke(core.clj:146)
  2: clojure.lang.AFn.applyToHelper(AFn.java:179)
  3: clojure.lang.RestFn.applyTo(RestFn.java:137)
  4: clojure.lang.Ref.alter(Ref.java:174)
  5: clojure.core$alter__4907.doInvoke(core.clj:1542)

The actual source of the exception is the print function that is recursive on nested sequences. This make sense, why would someone want to print such monsters. Because of that inattention I lost time searching for an imaginary bug. Only a small modification is needed to make our test function working.

(defn get-bottom [p]
  (loop [p (first p)]
    (if (seq? p) (recur (first p)) p)))

(defn test-walk [walker shallowest deepest]
  (doseq [depth (range shallowest deepest)]
    (println (get-bottom
               (walker #(str depth " reached " %)
                 (lazy-seq (last (take depth pit))))))))

We simply search for the bottom item and print it, this will also make the test output clearer. We can now see what our original walk function can handle.

user> (test-walk lazy-recursive-string-walk 100000 100001)
...
; Evaluation aborted.
---
Java heap space
  [Thrown class java.lang.OutOfMemoryError]

Well, the heap too has its limit! We would need to augment the JVM heap memory size to be able to run the previous example. Lets reduce our ambitions and do some benchmarking instead.

user> (time (test-walk lazy-recursive-string-walk 10000 10001))
10000 reached bottom!
"Elapsed time: 25.138697 msecs"
nil
user> (time (test-walk lazy-recursive-string-walk-with-zipper 10000 10001))
10000 reached bottom!
"Elapsed time: 122.691972 msecs"
nil

As you see, the version using clojure.walk is much faster. That's perfectly understandable considering the more complex concept of zippers which have multiple uses aside walking trees. As both versions are fully lazy, the first one is the clear winner here.

What Can We Use This For

After all these trials and tribulations, you may wonder what use I may have for such a function. It's to help create functions or macros that perform string replacement on all strings in a Clojure form. This can be useful with Compojure while deploying your application to a different root path than "/" for example. The idea come from my experience with ASP.NET in which URLs can contain a character (~) to denote the web site root path.

(use 'clojure.contrib.str-utils)

(defn expand* [expansions string]
  (reduce (fn [s [regex replacement]]
            (re-gsub regex replacement s))
    string (partition 2 expansions)))

(defn expand-form [url form]
  (recursive-string-walk (partial expand* [#"^~" url]) form))

Having the same functionality in a macro would be nice too.

(defmacro with-expansions [expansions & body]
  `(do ~@(recursive-string-walk (partial expand* expansions) body)))

(defmacro expand [url & body]
  `(with-expansions [#"^~" ~(str url)] ~@body))

To put this to use I've taken a function written by James Reeves a few months ago during a discussion on the Compojure group. A function with the same name (with-context) already exists in Compojure though, so we'll rename it to with-root-path. The way it work is by binding the given context to a var and then we can use a function called url to add the context so that internal links still work once the application is deployed elsewhere. Using the expand-form function on html's arguments can reduce repetition and make the code less cluttered if there's a lot of such URLs.

(use 'compojure)

(declare *context*)

(defn with-root-path
  [ctx & route-seq]
  (let [handler (apply routes route-seq)
         pattern (re-pattern (str "^" ctx "(/.*)?"))]
    (fn [request]
      (if-let [[_ uri] (re-matches pattern (:uri request))]
        (binding [*context* ctx]
          (handler (assoc request :uri uri)))))))

(defn url [path]
  (str *context* path))

(defn html-expand [& trees]
  (apply html (expand-form *context* trees)))

(defroutes test-routes
  (with-root-path "/foo"
    (GET "/"    (html-expand [:h1 "test"] [:p "~/"]))
    (GET "/bar" (html [:h1 "test"] [:p (url "/bar")]))
    (ANY "*" (page-not-found))))

(defn start-test-server []
  (run-server {:port 8000} "/*" (servlet test-routes)))

The first route use a special version of the html function, it's only a slight improvement but I really like that way of doing things. There's plenty of other possible use cases though, but that should be enough for this post.

P.S.: I know the title isn't correct, but it sounds way better than A Recursive Walk on Strings Contained in Arbitrary Nested Data Structures.

Debugging ClojureQL

Since last week, I embarked on a new endeavor, contributing to ClojureQL. My future projects involving Clojure will need to access some databases, some of which doesn't behave in the same way. Sure, there is already clojure.contrib.sql that give you a wrapper around JDBC, but there are two problems with this approach. First, JDBC is quite good at what it does, yet is not a very sophisticated tool. It gives you access to a portable subset of SQL, that mainly support querying and updating data. This leaves a lot of advanced features out of the deal, these are still available, but in a non-portable way. The other way around, if a database system doesn't support a common feature, JDBC cannot do anything about it, the driver can though. Second, the clojure.contrib sql API has a very procedural feeling to it, it doesn't even let you play with an intermediary form as it executes statement directly. That's enough for basic database interactions, but not for serious database agnostic development.

Lets put off advocacy and talk about something concrete. While contributing to ClojureQL, I realized there was some issues with debugging. It was working well for Postgres (which I had an instance running), I simply had to use the compile-sql method. A problem arise when you're testing changes that affect all backends. In this case, to verify the SQL generated, you need a server for each DBMS you want to test. After looking at the code for some time, I found an easy way of compiling statements without a connection. We can create mock objects using Clojure's proxy macro and use them instead of live connections. For now, it's really simple as no backend implementations are actually using the connector. To put this idea into practice, I wrote a macro to debug multiple databases.

(defmacro debug [db ast]
  (let [connector (.getName (db *connectors*))]
    `(compile-sql ~ast (proxy [~(symbol connector)] []))))

It uses a map containing the interfaces used by all backends with keywords as keys.

(def *connectors* {
  :postgres org.postgresql.PGConnection
  :mysql    com.mysql.jdbc.Connection
  :derby    org.apache.derby.iapi.jdbc.EngineConnection
  :generic  Object})

With this code you can easily debug statements for every databases ClojureQL support. We can add a final touch to be able to see the SQL output for all backends with a single command.

(defmacro debug-and-print-all [ast]
  (let [longest (reduce max (map (comp count str) (keys *connectors*)))
        debug-and-print (fn [db] `(println (format (str "%1$-" ~longest "s : %2$s")
                                           ~(subs (str db) 1)
                                           (debug ~db ~ast))))]
    `(do ~@(map debug-and-print (keys *connectors*)))))

Finally, you can see an example output of the debug-and-show-all macro at the REPL using my ClojureQL clone.

clojureql-test> (debug-and-print-all (create-table test [id int title text date date] :non-nulls * :primary-key id :auto-inc id :unique title))
postgres  : CREATE TABLE test (id SERIAL,title text NOT NULL,date date NOT NULL,PRIMARY KEY ("id"),UNIQUE ("title"))
mysql     : CREATE TABLE test (id int NOT NULL  AUTO_INCREMENT ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY (`id`),UNIQUE (`title`)) 
derby     : CREATE TABLE test (id int NOT NULL  GENERATED ALWAYS AS IDENTITY ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY ("id"),UNIQUE ("title"))
generic   : CREATE TABLE test (id int NOT NULL ,title text NOT NULL ,date date NOT NULL ,PRIMARY KEY ("id"),UNIQUE ("title"))

This code is not working properly on the main repository for the moment, as there's some issues with Derby and the generic backend. It's enough for this post, I'll go back hacking my way through ClojureQL code to find other useful tricks and speed up version 1.0 release.