## Monday, April 12, 2010

### Thrush in Clojure

Quite some time back I wrote a blog post on the Thrush Combinator implementation in Scala. Just for those who missed reading it, Thrush is one of the permuting combinators from Raymond Smullyan's To Mock a Mockingbird. The book is a fascinating read where the author teaches combinatorial logic using examples of birds from an enchanted forest. In case you've not yet read it, please do yourself a favor and get it from your favorite book store.

A Thrush is defined by the following condition: Txy = yx. Thrush reverses the order of evaluation. In our context, it's not really an essential programming tool. But if you're someone who takes special care to make your code readable to the human interface, the technique sometimes comes in quite handy.

Recently I came across Thrush in Clojure. You don't have to implement anything - it's there for you in the Clojure library implemented as a macro ..

Conside this simple example of bank accounts where we represent an account as a Map in Clojure ..

(def acc-1 {:no 101 :name "debasish" :type 'savings :balance 100}) (def acc-2 {:no 102 :name "john p." :type 'checking :balance 200}) 
We have a list of accounts and we need to find all savings accounts and compute the sum of their current balances .. well not too difficult in Clojure ..

(defn savings-balance   [& accounts]   (apply +     (map :balance       (filter #(= (:type %) 'savings)          (seq accounts))))) 
To a programmer familiar with the concepts of functional programming, it's quite clear what the above function does. Let's read it out for all of us .. From a list of accounts, filter the ones with type as savings, get their balances and report the sum of them. That was easy .. but did you notice that we read it inside out from the implementation, which btw is a 4 level nested function ?

Enter Thrush ..

Being a permuting combinator, Thrush enables us to position the functions outside in, in the exact sequence that the human mind interprets the problem. In our Scala version we had to implement something custom .. with Clojure, it comes with the standard library .. have a look ..

(defn savings-balance   [& accounts]   (->> (seq accounts)        (filter #(= (:type %) 'savings))        (map :balance)        (apply +))) 
->> is implemented as a macro in Clojure that does the following :

1. threads the first form (seq accounts) as the last argument of the second form (the filter), which makes (seq accounts) the last argument of filter
2. then makes the entire filter form, including the newly added argument the last argument of the map
.. and so on for all the forms present in the argument list. Effectively the resulting form that we see during runtime is our previous version using nested functions. The Thrush combinator only dresses it up nicely for the human eyes synchronizing the thought process with the visual implementation of the logic. And all this at no extra runtime cost! Macros FTW :)

->> has a related cousin ->, which is same as ->>, but only threads the forms as the second argument of the next form instead of the last. These macros implement Thrush in Clojure. Idiomatic Clojure code is concise and readable and using a proper ubiquitous language of the domain, makes a very good DSL. Think about using Thrush when you feel that reordering the forms will make your API look more intuitive to the user.

Thrush also helps you implement the Decorator pattern in a very cool and concise way. In my upcoming book, DSLs In Action I discuss these techniques in the context of designing DSLs in Clojure.

Jonas Elfström said...

I find the Thrush combinator interesting but also kind of questioned the need or use for it in some languages (Ruby, C#). Seeing it being used the way it is in Clojure was enlightening as it made the code so much easier to read.

> makes a very good DSL

For programmers, maybe. I suspect that you will see eyes glazing over if you show anyone else
(filter #(= (:type %) 'savings))

Debasish said...

Jonas -

I do *not* subscribe to the view that non-programmers will start writing Clojure code given a proper DSL. At max they can understand the basic semantics on browsing the code. The main intent is to make the code domain centric with clear API design so that the programmer who is familiar with the domain should be able to use it and maintain it.

Jonas Elfström said...

I also do not subscribe to the idea of non-programmers writing code. Not in Clojure DSLs or in any other DSLs. At most some configurability could be hoped for.
It was the reading part I was worried about. Partly because five non alphanumeric characters in a row makes people cringe.

The making it easier for programmers part I totally agree with.

Thanks for a great post!

Tom said...

Aren't you looping many times where if you used an imperative language you would only need to loop once: ie. for (e in object) if savings, get balance and add to another list

Daniel said...

I take an issue with this: "in the exact sequence that the human mind interprets the problem". You could rewrite it as "the exact sequence that programmers used to imperative programming style thinks of the problem". Here's how the "human mind" interprets the problem:

Sum the balance of all saving accounts.

That's it. One word for each line of the code, minus boilerplate lines and words, in the exact order of the code. Instead, you are suggesting the "human mind" interprets it as follow:

From a list of all accounts, get those that are saving accounts, then get the balance for each one, and finally add all them.

I don't think so, really.

Debasish said...

Tom -

Well, I guess it's a whole different way of thinking about optimization. Imperative loops, will, in many cases be faster than the pure functional code. However, the fact is, you don't need raw metal performance every time. For those where you need it, you can use imperative loops. Even you can code the same balance computation using loop/recur in Clojure. But then, you miss out the fun part of it.

Here I look at it from a different perspective. Immutability based code structures offer you a world of goodness. Besides, it's always recommended to use the sequence functions in Clojure whenever possible. You get laziness by default (that helps you handle infinite sequences) without having to construct lazy-seqs by hand and also all the optimization of chunked sequences for performance. In most cases all these advantages plus the added readability outweigh the incremental performance benefit that u get from imperative programming. But of course, there's the ubiquitous fallback of an imperative for-loop, in case you need to meet your benchmark figures.

Daniel said...

@Tom That's a good question. If this sequence is strict, then, yes, it is looping multiple times, and creating intermediary results. On the other hand, if the sequence is non-strict, it's looping only once.

Bill Allen said...

Tom - not necessarily and in the example not at all. That's the beauty of lazy evaluation - computations aren't actually being done until they are required. What's actually being passed to each new evaluation is not the result of the evaluation, but the instruction to do it when needed.

Baishampayan said...

Good post. Minor nit-picks -

The (seq accounts) is redundant, and I think it's better to denote the account types as ::checking & ::savings than vanilla symbols (none does that in real Clojure code). The :: namespace-qualifies the keyword and avoids any kind of clashes.

My version of the code --

(def acc-1 {:no 101 :name "debasish" :type ::savings :balance 100})
(def acc-2 {:no 102 :name "john p." :type ::checking :balance 200})

(defn savings-balance
[& accounts]
(->> accounts
(filter #(= (:type %) ::savings))
(map :balance)
(apply +)))

Have fun!

Debasish said...

Baishampayan -

Thanks for the tips .. I never meant it to be production quality code. I was working at the REPL and pasted it right from there. But I should have been careful.
The main purpose was to demonstrate how ->> can act as the Thrush combinator. I have started some serious learning of Clojure idioms and felt that this can be a powerful tool in DSL design.

Anonymous said...

@Jonas

> made the code so much easier to

Only if you're not accustomed to lisp. Clojure is a lisp, so one might as well learn how to read lisp.

Peter said...

Nice.

Just a side note. This particular example doesn't need the Thrush combinator for Scala. The usual chaining works fine.

case class Account(number: Int, name: String, atype: Symbol, balance: Int)

val acc1 = Account(101, "debasish", 'savings, 100)
val acc2 = Account(102, "john p.", 'checking, 200)

def savingsBalance(accounts: Account*) = {
accounts.filter(_.atype == 'savings)
.map(_.balance)
.sum
}

Ant... said...

Does Clojure not have a list comprehension macro? In python for example the map/filter can be acheived in a very readable way as follows:

sum(x['balance'] for x in accs if x['type'] == 'savings')

Jonas Elfström said...

@Ant
(print (->> (range 1 101) (filter odd?) (reduce +)))

Bob Shock said...

For comprehension usage:

(def acc-1 {:no 101 :name "debasish" :type 'savings :balance 100})
(def acc-2 {:no 102 :name "john p." :type 'checking :balance 200})
(def accounts [acc-1 acc-2])
(def total (apply + (for [account accounts :when (= (:type account) 'savings)] (:balance account))))

(println total)

Keith Brown said...

Just came across this and wanted to point out that this does not loop multiple times in Clojure - map and filter both produce lazy sequences, so you're in essence creating a pipeline that isn't evaluated until it hits (apply +), at which point the loop runs one time, and each account is filtered, mapped to its balance, and then summed.