How Specter works

Specter is a Clojure library which defined a DSL to query and manipulate composite data structure in a declarative way. Its a small library but its a great example to showcase how LISP increases productivity by defining DSL and working at a higher level of abstraction.

Anyone who needs to work with complex Clojure composite data structures should take a look at this library and very likely to benefit from it.

The wonderful thing here is you get a new domain specific language without leaving Clojure, it acts and looks just like normal Clojure code. Compare this to something like LINQ, LINQ has a very different syntax from its host language, you actually need to learn a new syntax. In Clojure you only need to learn the new semantics. The syntax is nothing but normal symbols and nested parenthesis. And its merely a library, you can even extend it by adding new navigators and use them in the DSL immediately.

The problem this library solves quite like what SQL do to relational databases. It provides a declarative way to manipulate data so you don't have to write tedious code to do the same thing.

The core concept of the library is navigator. A navigator is anything that satisfy the navigator protocol which simply contains two methods: select and transform. Internally, there is an AST(Abstract Syntax Tree) is built for each query, the AST node are navigators. Of course, the AST is polymorphic, each node comforms the navigator protocol but has different implementation with reify macro.

The query process is just a traversal to the AST, the traversal logic has no idea about the concrete implementaion of the nodes, it only visit the node by the protocol. The traversal logic is separated from the node visit logic.

The interesting part of the code is how the AST was built, it takes me quite a lot of time to figure out how it works. To see the details, look at private function combine-same-types. Notice that this function not only build the AST, it also determines how the traversal will proceed.

 
(defn- combine-same-types [[n & _ :as all]]
  (let [combiner
        (if (satisfies? RichNavigator n)
          (fn [curr next]
            (reify RichNavigator
              (rich-select* [this params params-idx vals structure next-fn]
                (exec-rich-select* curr params params-idx vals structure
                  (fn [params-next params-idx-next vals-next structure-next]
                    (exec-rich-select* next params-next params-idx-next
                      vals-next structure-next next-fn))))
 
              (rich-transform* [this params params-idx vals structure next-fn]
                (exec-rich-transform* curr params params-idx vals structure
                  (fn [params-next params-idx-next vals-next structure-next]
                    (exec-rich-transform* next params-next params-idx-next
                      vals-next structure-next next-fn))))))
 
          (fn [curr next]
            (reify Navigator
              (select* [this structure next-fn]
                (exec-select* curr structure
                  (fn [structure-next]
                    (exec-select* next structure-next next-fn))))
              (transform* [this structure next-fn]
                (exec-transform* curr structure
                  (fn [structure-next]
                    (exec-transform* next structure-next next-fn)))))))]
    (reduce combiner all)))
 

The AST nodes are connected by nested closures, its an unusual way to build an AST but works perfectly in this case. For example there is a query contains three navigators

 
[A B C]
 

The AST will looks like this

 
       N
     /   \
    N     C
   /  \
  A    B
 

The traversal order will be [N N A B C]. Start from the bottom left node(A here), the traversal can be affected by the implementation of the node, how the node use the next-fn parameter, if the node don't call the function, the traversal will stop. Because from the code that build AST, the next-fn will visit the node's right node in traversal order, node B's right node is C, A's right node is B.