How to Make an SQL From Clojure or My Macros Kata: Part 2

In a recent post I showed some strange things that one can do with macros to be able to write SQL-like queries right in Clojure. Several weeks ago we enabled selecting fields from records as well as filtering them with where clause. In the end of the first post I promised you that we will soon add sorting capabilities to our query language and enable joining “tables” together. Not that I am going to totally break this promise, but I will deliver on it only partially: this time we will do sorting and the sweetest part, joins, we leave for the final post.

Before proceeding, let me remind once more that the code obtained through this exercise is not something that can be used in any real application – it sucks from both performance and feature-richness perspectives and is hardly idiomatic, nice or readable. Furthermore, while doing the exercise I gradually came across the idea that what I show here is by no means a good way to utilize the power of macros. Still, I am sure that implementing a query language like this is a good exercise and can really help one understand what macros are about, how to handle them and, at least, where one should not use them. This way of learning is hard but it pays back a lot once you put enough effort into it.

Let’s recap where did we stop last time. First of all, we mastered picking fields from records and can write simple queries like this one:

(def table [
  {:a 1 :b 100 :c "100" :d 4}
  {:a 2 :b 200 :c "200" :d 3}
  {:a 3 :b 300 :c "300" :d 2}
  {:a 4 :b 400 :c "400" :d 1}])

(select :c from table)
;=> ({:c "100"} {:c "200"} {:c "300"} {:c "400"})

However, since this is hardly an impressing achievement and can be done in a much more concise way, we have gone further and allowed for filtering – starting from very simple conditions and proceeding to quite long and complex ones:

(select :a :b from table where :a < :d)
;=> ({:a 1, :b 100} {:a 2, :b 200})

(select :a :b from table where :a = 2 or (:d < 3 and :b > 300))
;=> ({:a 2, :b 200} {:a 4, :b 400})

Our key goals were to make the syntax as close to SQL as possible and I think we succeeded at it – at the cost of introducing a lot of complex stuff, whose main purpose is to deal with symbols like from, where and others. Now let’s take a look at our macros and see what we can do to make ordering possible. The key player in our team is select:

(defmacro select [& what]
  (let [fields (set 
          (take-while #(not= 'from %) what))
      source (fnext 
          (drop-while #(not= 'from %) what))
      conditions (next (drop-while #(not= 'where %) what))]
      `(map (fn [record#]
            (into {} (filter #(~fields (first %)) record#)))
          (filter #(condition % ~@conditions) ~source))))

For now, select is aware of from and where clauses, which it uses to find the desired fields, the source table and the filtering conditions in a query. To enable sorting we have to pay attention to the order by clause as well and here I am going to cheat. For the sake of making code a tiny bit simpler I will use a single orderby word without a whitespace – this will save us a couple keystrokes. The only place in our code where we have to pay attention to this symbol is in the select macro, where we have to retrieve the actual ordering conditions from the original query. For this we use the same approach as with where – basically skip everything up to the orderby symbol and the symbol itself. At the same time, we should remember that the new clause at the end of the query might introduce a problem: we don’t want this stuff to get into the condition macro, because upon meeting orderings it will immediately spit an “Unable to resolve symbol: orderby” error. Thus, we also restrict the conditions list on both sides:

(defmacro select [& what]
  (let [fields (set 
          (take-while #(not= 'from %) what))
      source (fnext 
          (drop-while #(not= 'from %) what))
      conditions (take-while #(not= 'orderby %) 

             (next (drop-while #(not= 'where %) what)))
      orderings (next (drop-while #(not= 'orderby %) what))]
      `(map (fn [record#]
            (into {} (filter #(~fields (first %)) record#)))
          (filter #(condition % ~@conditions) ~source))))

Now, once we have the orderings list extracted from the query, we can use it in some way. Because the select macro doesn’t look pretty straightforward already, it is a good idea to implement the sorting stuff elsewhere and just use it in select. For this purpose we are going to introduce another macro - order. To start with, let us make it distinguish between 2 situations: when no ordering is requested and when there is actually some stuff in the ordering conditions list. For now we can simply return nil in the latter case. The place to plug ordering in select seems quite obvious: sorting should be done after filtering so we will just wrap the existing body of select (the syntax-quoted part) in a call to the new macro:

(defmacro order [orderings what]
  (if (empty? orderings)
    what
    nil))

(defmacro select [& what]
  (let [fields (set 
          (take-while #(not= 'from %) what))
      source (fnext 
          (drop-while #(not= 'from %) what))
      conditions (take-while #(not= 'orderby %) 
             (next (drop-while #(not= 'where %) what)))
      orderings (next (drop-while #(not= 'orderby %) what))]
      `(order ~orderings
        (map (fn [record#]
            (into {} (filter #(~fields (first %)) record#)))
          (filter #(condition % ~@conditions) ~source)))))

If you execute any query with the updated macro you will see that the only thing that has changed is that now we get nil when there is a non-empty orderby clause:

(select :c from table where :a > 1)
;=> ({:c "200"} {:c "300"} {:c "400"})

(select :b :c from table where :a > 1 orderby :b)
;=> nil

Let’s take this as an evidence that we didn’t break anything and proceed with sorting. First, what are we expecting to get in the list of ordering conditions? Definitely, it should contain keywords denoting the fields to order by. Besides, each of these keywords may have an optional asc or desc symbol after it, standing for ascending and descending order, respectively. When the keyword is not followed by such a symbol, we will assume ascending order, similarly to what SQL dialects do. Now, this is not a completely trivial thing to implement, so let us first do something simple – for example, handle the case when there are only keywords in the orderings list. For this we only need to use the built-in sort-by and juxt functions in the order macro:

(defmacro order [orderings what]
  (if (empty? orderings)
    what
    `(sort-by (juxt ~@orderings) ~what)))

(def table [
  {:a 1 :b 400 :c "200" :d 4}
  {:a 2 :b 300 :c "100" :d 3}
  {:a 3 :b 200 :c "400" :d 2}
  {:a 4 :b 100 :c "300" :d 1}])

(select :b :c from table where :a > 1 orderby :b)
;=> ({:c "300", :b 100} {:c "400", :b 200} {:c "100", :b 300})

(pprint (select :a :b :c :d from table orderby :d))
;=> ({:a 4, :c "300", :b 100, :d 1}
;=> {:a 3, :c "400", :b 200, :d 2}
;=> {:a 2, :c "100", :b 300, :d 3}
;=> {:a 1, :c "200", :b 400, :d 4})

The examples show us that filtering and the simplest sorting facilities both work nicely. Still, if we chose to ask for ascending or descending order explicitly, the compiler will award us with something like “Unable to resolve symbol: asc”. Let us allow for these symbols and get closer to our goal. Here I want to start with something that I have been avoiding since the beginning of our strange exercise – we will get rid of the asc and desc symbols in the order macro well before doing anything else. Even though while implementing select and condition I got used to handling symbols in macros, they still bother me a lot and I want to force them out as fast as possible. We will replace asc with 1 and desc with -1 – this feels pretty logical and saves us from comparing everything to asc and desc as well as from the attempts to prevent Clojure from evaluating these symbols.

(defmacro order [orderings what]
  (if (empty? orderings)
    what
    (let [orderings-desym
        (vec (map (fn [s]
        (cond (= 'desc s) -1
            (= 'asc s) 1
            (keyword? s) s))))]
    `(sort-by (juxt ~@orderings) ~what))))

Next, we need a way to understand which keywords should go with which order. This would be very simple should we not allow to skip the asc symbol, but with this extra convenience feature we have to find a way to handle this without falling into some non-trivial loop-recur construct. Fortunately, this can be done in a not very elegant but satisfactory manner:

(defmacro order [orderings what]
  (if (empty? orderings)
    what
    (let [orderings-desym 
        (vec (map (fn [s]
        (cond (= 'desc s) -1
            (= 'asc s) 1
            (keyword? s) s))))
          orderings-separated 
          (->> orderings-desym
              (partition-by keyword?)
              (map (partial interpose 1))
              flatten
              (partition-all 2))]
    `(sort-by (juxt ~@orderings) ~what))))

This seemingly strange sequence of functions transforms the incoming list of ordering conditions into a sequence of pairs of the form (:key 1) or (:key -1). To achieve this result we first separate the list into sublists of keywords without ordering markers and those of ordering markers themselves. Then we use interpose, which will add missing 1‘s, and flatten the resulting list to finally split it into pairs. To make this easier to understand let’s take a look at the example – here are the stages of this transformation for a particular list of ordering conditions:

;0. [:a :b :c 1 :d :e -1 :f] ;initial orderings
;1. ((:a :b :c) (1) (:d :e) (-1) (:f)) ;partition-by keyword?
;2. ((:a 1 :b 1 :c) (1) (:d 1 :e) (-1) (:f)) ;map (partial interpose 1)
;3. (:a 1 :b 1 :c 1 :d 1 :e -1 :f) ;flatten
;4. ((:a 1) (:b 1) (:c 1) (:d 1) (:e -1) (:f)) ;partition-all 2

As you see, each keyword apart from the last one gets its 1 or -1. – missing tail is, in fact, not a big problem and we will deal with it shortly. Now we have set up everything except for the actual sorting part – we need to transform the new sequence of conditions into a list of functions suitable for sort-by. For this purpose, we can introduce an auxiliary function and consume it in the order macro:

(defn order-fn
  ([k]
    k)
  ([k ord]
    (if (neg? ord)
      `(fn [r#] (- (~k r#)))
      k)))

(defmacro order [orderings what]
  (if (empty? orderings)
    what
    (let [orderings-desym 
        (map (fn [s]
        (cond (= 'desc s) -1
            (= 'asc s) 1
            (keyword? s) s)) orderings)
          orderings-separated 
          (->> orderings-desym
        (partition-by keyword?)
        (map (partial interpose 1))
        flatten
        (partition-all 2))
          order-funcs 
          (map #(apply order-fn %) orderings-separated)]
    `(sort-by (juxt ~@order-funcs) ~what))))

(pprint (select :a :b :c :d from table orderby :a desc))

;=> ({:a 4, :c "300", :b 100, :d 1}
;=> {:a 3, :c "400", :b 200, :d 2}
;=> {:a 2, :c "100", :b 300, :d 3}
;=> {:a 1, :c "200", :b 400, :d 4})

It works! Let’s try to understand why. The key piece is the order-fn, which generates sorting functions for us. The one-argument version is trivial – it takes a single key and returns it to the caller. Why do we need something this stupid? Well, that’s simply our way to handle the last keyword in the orderings sequence when it comes without explicit asc or desc. As seen in the example above in this case it won’t have an ordering marker (1 or -1) in the orderings-separated list, but with the help of order-fn defined as above we can just ignore this and everything will work fine. 

The two-arguments version of order-fn is a bit less trivial but still manageable: it will either return the keyword if we want ascending order, or wrap it into a function that will "invert" the numeric value retrieved with the keyword otherwise.  At the same time, here we have one nasty feature: it returns a syntax-quoted fn form instead of a mere function. This might seem weird – and it is – but at the same time that’s the only way it is going to work. The problem here is that we use order-fn in a macro to produce another function – a closure around the k argument. This combination of macro, function and closure somehow makes compiler vomit “No matching ctor found for class user$order_fn$fn__*” errors. I must admit that I failed to understand this problem – if you can explain it I would be grateful. Still, for now we, at least, can go on with quoting.

The way we use order-fn is very simple – we map it onto the list of (key, sorting order) pairs and then pass the resulting functions to juxt. The latter produces a single function, which extracts all the values used for ordering from a record. Finally, in combination with sort-by this gives us a properly ordered results set.

Now, you might have spotted several problems with our solution. The most severe one (apart from the approach in general) is that we allow sorting only by the numeric fields – strings won’t do. This is because to produce an ordering function for desc we use simple numeric negation, which isn’t compatible with strings, sequences or anything else. I have tried to come up with a more generic solution, but the time and brainpower that I had put into it were not enough. Fortunately, my goal of understanding macros better and learning to be not afraid of quoting and unquoting allows me to live with this. However, if you come up with a more generic implementation of order-fn it will be a great pleasure for me to see it – please share it in comments!

On the other side, the use of quoting in the order-fn makes me think that something is definitely wrong with our approach to the problem. The degree of complexity of our macros also strengthens this feeling – I still can manage them, but it ceased to be an easy task long before we produced a working implementation of orderby. I have already stated that this way of implementing SQL-ish queries doesn’t look like an idiomatic way to use Clojure macros and all these concerns only reassure me in this idea. Still, the audible tension that I had in my brains when fighting this stuff confirms that the exercise is a damn good kata.

Here are some of my takeaways from this iteration:

• Maybe the most frequent error that I faced here was the “Wrong number of arguments passed to a keyword” one. The reason for this was always that Clojure tried to evaluate a list starting from a keyword when I didn’t mean it to be evaluated. This same problem manifested itself in some other ways and I find it the most important thing to tackle: you should always pay close attention to what and when you are evaluating.
• I have expected to face some difficulties with sorting over several fields – until I remembered that there is juxt in Clojure. So one of the lessons from each and every exercise in programming is actually that there is likely a function to solve your problem. That's actually one of the reasons why it is good to do these exercises – you discover and remember a lot of useful stuff.
• One sign of using a wrong approach to a problem is that you have a lot of bindings or variables and find it difficult to come up with proper names for them (order, order-fn, orderings-separated, etc simply don’t sound very good). Maybe the most appropriate thing to do under such conditions is to step back and try to rethink the way you reason about the problem.

I will add joins to the mess in the next post – as promised. For now, feel free to play with what we already have – here is the code. By the way, there is a problem with our new select macro, which limits sorting capabilities, but is very easy to fix. Did you spot it? Let me know in the comments!

In addition to showing me where I messed up, please tell whether you find this exercise a good way to accustom oneself with macros or do you think it is as useless as it is long and complex? Maybe you have your favorite Clojure kata, which helps to explore and understand macros better? I will be glad to hear about it!

CodeProject