Leonardo Borges

Functional Programmers Unite! LambdaJam down under

2013-04-11T11:37:00+10:00

I hinted at LambdaJam Australia back in my 2012 Highlights post and the dates are fast approaching so I thought appropriate to blog about it once more.

YOW! LambdaJam is a conference targeted at intermediate and advanced functional programmers and is organised in talks, jams and workshops.

Talks are the traditional format and are 30 minutes long;
Workshops aim to introduce a specific subjects to attendees in great detail and are up to two hours long;
Jams are hands-on sessions. Participants will be guided through pre-defined problems around a given subject/technology and encouraged to work through the solutions either by themselves or ideally as small groups. Jams are also 2 hours long;

Sounds pretty amazing, doesn’t it?

If you’re still not convinced, check out the program.

The conference will run for 2 days, May 16-17, in Brisbane. Tickets are on sale.

Clojure

Besides the conference itself, Clojure/core will be giving an Intro to Clojure workshop in Sydney, Melbourne and Brisbane. It’s a great opportunity to learn from the language maintainers.

If you’re attending the conference already, you’re in luck because there is a 20% off discount on the link above if you attend both the conference and the workshop.

In case you’d like to attend the workshops only, you can buy individual tickets for Sydney, Melbourne and Brisbane.

Scala

Tony Morris will also be delivering a Functional Programming in Scala workshop in Brisbane and 20% off combo tickets can be bought from the EventBrite page for LambdaJam.

See you there

Got tickets yet? No? What are you waiting for?

Clojure and 'Why calculating is better than scheming'

2013-03-25T11:00:00+11:00

Last week while attending Clojure/West in Portland I came across a paper called Why calculating is better than scheming. In a nutshell, this paper is a critique to Abelson and Sussman’s classic textbook SICP - Structure and Interpretation of Computer Programs, used by MIT for many years to teach their introductory programming course.

If you haven’t read SICP, you should. It’s an amazing book. It uses Scheme, a dialect of Lisp, as the vehicle to present fundamental programming concepts.

Philip Wadler - the author of this particular paper - contrasts teaching in Scheme to teaching using KRC and Miranda, pointing out four major features he considers important and lacking in Scheme. They are:

Pattern matching
A syntax close to traditional mathematical notation
A static type discipline and user-defined types
Lazy Evaluation

Note: KRC influenced Miranda which in turn influenced Haskell. Their syntax is similiar, so where Wadler used Miranda code snippets in the paper, I’ll be using Haskell in this post.

As an aside, although the paper talks specifically of Scheme, the term Lisp is used quite loosely and could lead the not-so-careful reader to be misled regarding a whole family of languages. Lisps have come a long way and modern dialects - of which I’ll be focusing on Clojure - address many of the concerns raised by Wadler.

Let us begin.

Pattern Matching

Here Clojure, and most - all? - Lisps, are out of luck.

The example used in the paper is that of summing all integers in a list. First in Haskell:

sum []   = 0
sum x:xs = x + sum xs

Now in Clojure:

(defn sum [coll]
  (if (empty? coll)
      0
      (+ (first coll) (sum (rest coll)))))

The question here is this: Which snippet is easier to read/reason about? the Haskell code!

I must confess that I, too, miss pattern matching sometimes. However we can still improve our Clojure version to read nicer on the eyes by using destructuring:

(defn sum [[first & rest :as coll]]
  (if (empty? coll)
      0
      (+ first (sum rest))))

And that’s pretty much it. Without proper pattern matching, we can’t get much better than that.

In addition to the Haskell snippet being easier to read, it’s also easier to prove correct by structural induction, as demonstrated in Wadler’s paper.

Note: core.match adds support to pattern matching in Clojure. At the time of this writing, it’s considered “alpha quality”

Data structures

The paper continues to discuss exercise 2-27 from the SICP, where the reader has to write code to represent a binary mobile, which consists of a left and right branch with each branch being a rod of certain length, from which hangs either a weight or another binary mobile.

Translating the Scheme example to Clojure, such a structure is represented using lists, like so:

(defn make-mobile [left right]
  (list left right))
  
(defn make-branch [length structure]
  (list length structure))

Wadler then contrasts this with the equivalent Miranda code, translated below to Haskell, taking advantage of algebraic data types:

data Structure = Weight Int | Mobile Branch Branch
data Branch = Branch Int Structure

The first claim is that the Haskell/Miranda data type declaration makes it clearer what the data structure looks like, which is fair.

Also, the compiler can catch errors early on.

However, when writing idiomatic Clojure code, here’s how I’d actually create this structure:

(defn make-mobile [left right]
  {:left left :right right})
  
(defn make-branch [length structure]
  {:length length :structure structure})

Granted, it’s still not as clear and the compiler can’t validate the shape of our data structure.

This is however cleaner than the previous version and drives home the point that Clojure isn’t limited to lists, having literals for other data types such as the hash maps used in this example.

The second part of this claim is that through custom data types and pattern mathing, extracting values from those structures becomes simpler:

totalWeight (Weight w) = w
totalWeight (Mobile l r) = totalWeightBranch l + totalWeightBranch r

totalWeightBranch(Branch d s) = totalWeight s

Once again Clojure can improve things by taking advantage of its builtin data structures and destructuring:

(defn total-weight [{:keys [left right] :as structure}]
  (if (number? structure)
      structure
      (+ (total-weight-branch left)
         (total-weight-branch right))))
      
(defn total-weight-branch [{structure :structure}]
  (total-weight structure))     

For a language with no pattern matching nor algebraic data types, this snippet is clear, concise and elegant - and a real improvement over the Scheme version discussed in the paper - which was essentially handicapped by the use of lists to simulate ‘structs’.

As far as Clojure goes, this claim ends here: the next point in the paper, about changing from using list to using cons, is rendered moot since we’re using hash maps to represent our mobiles.

Lisp lists are not self-escaping

Creating lists in Clojure goes like this:

(list (list 1 2) nil) ;; ((1 2) nil)

'((1 2) nil) ;; ((1 2) nil)

Both statements above are equivalent, with the second one being clearly more concise.

The claim here is that the fact that you need to either use the list function or quote the form is cumbersome and can be confusing to beginners.

Clojure solves this by providing literals to another data structure - vectors:

[[1 2] nil]

Simple and concise - in fact, in idiomatic Clojure code, you’ll rarely see quoted lists where a vector will do.

This is possible because both lists and vectors conform to a higher level abstraction called a Seq, in terms of which most list operations are defined.

This eliminates the two following points mentioned in the paper as it allows a beginner to defer his/her understanding of quoted forms to more advanced lessons/usages.

Programs that Manipulate Programs - the interpreter example

Here Wadler shows a simple grammar for an interpreter in both Miranda and Scheme.

He claims that since Haskell/Miranda have free data types, representing such grammar becomes simpler:

data Term = Var [Char]
          | Lambda Var Term
          | Apply Term Term
          | Closure Env Var Term
type Env = [(Var, Term)]
type Var = [Char]

This is true in that one can easily scan the snippet above and deduce quickly what Term looks like.

Then, by using pattern matching, eval could be implemented like so:

eval e (Var v) = lookup e v
eval e (Lambda v t) = Closure e v t
eval e (Apply t0 t1) = apply (eval e t0) (eval e t1)

...

I do believe this makes Haskell an excellent choice for writing interpreters and compilers.

However, the flip side is that entering such terms in Haskell is cumbersome. Consider the term below:

(λx.(x x)) (λx.(x x))

This is how to represent this term using the grammar defined above:

(apply (Lambda "x" (apply (Var "x") (Var "x")))
       (Lambda "x" (apply (Var "x") (Var "x"))))

The strength in Lisp lies elsewhere. Since we have quoted forms, entering a similar term is a lot less verbose and closer to its intended representation:

'((lambda [x] (x x)) (lambda [x] (x x)))

This is, of course, at the expense of making eval a more complicated function:

(defn eval [e t]
  (cond (variable? t)
        (lookup e (variable-name t))
        (lambda? t)
        (make-closure e (lambda-var t) (lambda-body t))
        (apply? t)
        (apply (eval e (apply-operator t))
               (eval e (apply-operand t)))))

...

The paper leaves out an important advantage of Lisps though:

Because we can write code for our made up language directly in its (almost)abstract syntax tree form, Lisps are the ideal choice when writing Internal Domain Specific Languages.

Lazy Evaluation

Lists

Haskell and Miranda are lazy languages and that yields a lot of power. This claim is more specific to the use of lazy lists - or sequences, streams - and starts off with a snippet that calculates the sum of squares of all odd numbers from 1 up to 100:

sum [ i*i | i <- [1..100], odd i ]

What follows in the paper is a not-so-clear snippet of equivalent functionality using Scheme streams.

Clojure features lazy sequences and list comprehensions, making the above Haskell example trivial to write:

(sum (for [i (range 100) :when (odd? i)] (* i i)))

If you’re following at home with the original paper you’ll see this is more readable and elegant than the equivalent Scheme example.

Another - also idiomatic - way to write the same expression is by using a combination of map/filter:

(sum (map #(* % %) (filter odd? (range 100))))

Deciding which one is clearer is left as an exercise to the reader.

Special forms and lazy evaluation

In this section, Wadler brings another example from SICP where the reader wishes to implement his/her own if form.

As we know, in order to implement our own version of if, we need to use macros. That is because in Lisps arguments to functions are eagerly evaluated.

One might implement it like this:

(defmacro my-if [pred then else]
  `(cond ~pred ~then
          :else ~else))

In Lazy languages, such as Haskell and Miranda, this problem doesn’t occur allowing such functions to be defined without the need for special and/or quoted forms:

myIf True  t e = t
myIf False t e = e

However this completely dismisses the power of macros which allow you to extend the language in ways no other language allows - as is extensively demonstrated in books such as On Lisp and Let Over Lambda.

As Guy Steele once put it: ”[…] If you give someone Lisp, he has any language he pleases”

Conclusion

Hopefully this post doesn’t come off as trying to invalidate Wadler’s paper - that is not my intention.

While I do think a few of the points discussed are only applicable to the domain in which his paper was written - teaching - they are still valid and worth understanding.

I do however expect to have given you a different perspective on it, showing the strengths of modern Lisps such as Clojure and how it approaches these issues - such as by using its rich set of data structures, literals and techniques such as destructuring.

Purely functional data structures in Clojure: Leftist Heaps

2013-02-03T12:41:00+11:00

Last year I started reading a book called Purely Functional Data Structures. It’s a fascinating book and if you’ve ever wondered how Clojure’s persistent data structures work, it’s mandatory reading.

However, all code samples in the book are written in ML - with Haskell versions in the end of the book. This means I got stuck in Chapter 3, where the ML snippets start.

I had no clue about Haskell’s - much less ML’s! - syntax and I was finding it very difficult to follow along. What I did notice is that their syntaxes are not so different from each other.

So I put the book down and read Learn You a Haskell For Great Good! with the hopes that learning more about haskell’s syntax - in particular, learning how to read its type signatures - would help me get going with Puretly Functional Data Structures.

Luckily, I was right - and I recommend you do the same if you’re not familiar with either of those languages. Learn You a Haskell For Great Good! is a great book and I got a lot out of it. My series on Monads is a product of reading it.

Enough background though.

The purpose of this post is two-fold: One is to share the github repository I created and that will contain the Clojure versions of the data structures in the book as well as most solutions to the exercises - or at least as many as my time-poor life allows me to implement.

The other is to walk you through some of the code and get a discussion going. Hopefully we will all learn something - as I certainly have when implementing these. Today, we’ll start with Leftist Heaps.

Leftist Heaps

Leftist Heaps - or trees - are a variant of binary heaps that can be used as priority queues. On top of the standard invariants of binary heaps, it obeys the leftist property:

Every node has a rank, which is the distance from its right spine to the nearest leaf
A node’s left child has a rank at least as large as its right child

In a nutshell, these are the operations we need to be able to perform on a leftist heap:

insert a value into an existing heap
merge two heaps
find the minimum value in a heap
delete the minimum value, returning a new heap

Since the book uses ML/Haskell, it starts with a data type definition for Heaps that exposes these and a couple of other auxiliary functions. I decided to take a stab at writing the solution using Clojure’s protocols and records:

(defprotocol Heap
  (is-empty?   [this])
  (insert      [this v])
  (merge       [this other])
  (rank        [this])
  (find-min    [this])
  (delete-min  [this]))

(defrecord LeftistHeap [rank value left right])

When implementing the algorithms the base case for the recursive solutions will involve dealing with nil values which at first seems like it wouldn’t be a problem. However, protocol functions dispatch on the type of its first argument so what happens if I call the function is-empty? on nil?

Luckily, Clojure allows us to extend a protocol to core types:

(extend-protocol Heap
  nil
  (rank [_] 0)
  (merge [_ other] other)
  (is-empty? [_] true)

  LeftistHeap
  (is-empty? [this]
    (nil? this))

  (rank [this]
    (:rank this))

  (merge [{val-this :value left-this :left right-this :right :as this}
          {val-other :value left-other :left right-other :right :as other}]
    (cond
     (is-empty? other) this
     (<= val-this val-other) (ensure-leftist left-this
                                             (merge right-this other)
                                             val-this)
     :else (ensure-leftist left-other
                           (merge this right-other)
                           val-other)))

  (insert [this v]
    (merge (->LeftistHeap 1 v nil nil)
           this))

  (find-min [{v :value}] v)

  (delete-min [{left :left right :right}]
    (merge right left)))

Note how I extended a few of the protocol functions to the nil data type, allowing me to continue with this implementation with no nasty hacks.

There’s one last bit missing: a function that will ensure each heap retains the leftist property:

(defn ensure-leftist
 [this other v]
 (let [rank-this (rank this)
       rank-other (rank other)]
   (if (>= rank-this rank-other)
     (->LeftistHeap (inc rank-other) v this other)
     (->LeftistHeap (inc rank-this) v other this))))

The reason this function is isolated is that the Heap protocol defined above is fairly generic and could be used for defining other types of heaps - and I didn’t feel it warranted its own interface.

We can now play with it and create a new leftist heap:

(-> (->LeftistHeap 1 3 nil nil)
                   (insert 2)
                   (insert 7)
                   (insert 4)
                   (insert 10)
                   (insert 1)
                   (insert 20))

While I quite like this approach, I thought I’d also implement this solution using Clojure’s core data types - maps in this case - and no protocols. The code is shown below:

(defn mk-heap [rank value left right]
  {:rank rank :value value :left left :right right})

(defn heap-rank [heap]
  (if (nil? heap)
    0
    (:rank heap)))

(defn ensure-leftist-heap [value heap-a heap-b]
  (let [rank-a (heap-rank heap-a)
        rank-b (heap-rank heap-b)]
    (if (>= rank-a rank-b)
      (mk-heap (inc rank-b) value heap-a heap-b)
      (mk-heap (inc rank-a) value heap-b heap-a))))

(defn merge-heaps [{val-a :value left-a :left right-a :right :as heap-a}
                   {val-b :value left-b :left right-b :right :as heap-b}]
  (cond
   (nil? heap-a) heap-b
   (nil? heap-b) heap-a
   (<= val-a val-b) (ensure-leftist-heap val-a
                                         left-a
                                         (merge-heaps right-a heap-b))
   :else (ensure-leftist-heap val-b
                              left-b
                              (merge-heaps heap-a right-b))))

(defn heap-insert [value heap]
  (merge-heaps (mk-heap 1 value nil nil)
               heap))

(defn heap-find-min [{v :value}] v)

(defn heap-delete-min [{left :left right :right}]
  (merge-heaps right left))

Using it is equally simple:

(->> (mk-heap 1 3 nil nil)
                    (heap-insert 2)
                    (heap-insert 7)
                    (heap-insert 4)
                    (heap-insert 10)
                    (heap-insert 1)
                    (heap-insert 20))

That’s it for now.

As I implement more of the book’s code and exercises I’ll add them to the github repo - it also includes tests for all implementations.

Enjoy :)

Announcing bouncer, a validation library for Clojure Apps

2013-01-04T17:39:00+11:00

Today I’m releasing bouncer, which was extracted from a project I’ve been working on.

It’s a validation library for Clojure apps and it lets you write code like this:

(def person {:name "Leo"})

(validate person
    :name required
    :age  [required number])

If you’d like to see more examples and a detailed guide check out the github repository. The README should get you started.

This post however isn’t only about announcing bouncer. It’s also about the motivation and implementation details behind it.

There are a couple of Clojure validation libraries already out there so why would I write a new one? Well…

Writing Clojure is fun! (who knew? :P)
Because I believe this problem can be solved more elegantly with the use of Monads

If you’ve been following me for a while, you’ll know that I spent most of 2012 deepening my knowledge about functional programming.

In that journey, the unavoidable subject of monads came about - and it was both interesting and enlightening enough that made me write a whole series of posts about it.

After learning what they are and then thinking about the validation problem for a while, I couldn’t help but notice that the problem had a lot in common with the State Monad.

In order to explain how the two relate, I’ll have to digress for a moment. It’ll all make sense in the end - or so I hope

Purity

In pure functional languages, such as Haskell, functions can’t have side effects. These include performing IO, changing global variables or launching missiles.

Because of that, functions in Haskell are pure: if you repeatedly call a function f with the same argument x over time you will always get the same result back.

Pure functions are not a feature of Haskell though. We, too, can write pure functions if we wish:

(defn double [x]
    (+ x x))

The function double above is pure. If we call it with 10, we can be sure the result will always be 20.

This leaves us with a question though: If we were to write our programs with pure functions only, how would we perform computations that need to carry state - state that needs to change over time - around?

A good example of such computation is generating random numbers.

Most programming languages provide generators capable of creating random numbers on demand. Using them is usually trivial. Here’s an example in Java:

Random gen = new Random();

gen.nextDouble(); // 0.0037635726242281065
gen.nextDouble(); // 0.15821091918430885

Impurity alert!

The function nextDouble above is obviously not pure. Multiple invocations of it with the same argument - in this case, none - returns different results.

nextDouble is keeping some sort of global state between function calls.

This is where the State Monad comes in. It allows such functions to remain pure.

The State Monad

The State Monad provides a way to abstract state from the function that needs to operate on it.

Sounds confusing? Hopefully an example will clear things up.

Let’s have a look at the clojure function rand:

(rand)
;; 0.04388682005715605
(rand)
;; 0.43057496371080517

rand suffers from the same problem as nextDouble we saw above. It keeps it’s own state that is shared across calls, therefore being an impure function.

Now let’s write a pure version of rand. We’ll call it pure-rand:

(def gen (java.util.Random.))

(defn pure-rand [g]
    [(.nextDouble g) g])

(pure-rand gen)
;; [0.5783608063218478 #<Random java.util.Random@7f30ab6>]

(pure-rand gen)
;; [0.9251968987499839 #<Random java.util.Random@7f30ab6>]

This is interesting. pure-rand now takes a generator as an argument and returns a two-element vector containing the random number itself - the result we’re actually interested in - and the generator that was passed in.

Recall however that the generator returned, albeit the same object, is in a new sate.

By re-writing the function like this, we’ve regained purity, as demonstrated below:

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

(pure-rand (java.util.Random. 100))
;; [0.7220096548596434 #<Random java.util.Random@bb14fe1>]

As you can see, as long as we provide the same generator - the same argument - we get the same result back.

If you’re wondering why I’m returning a two element vector from our little function, the answer lies in the State Monad implementation as found in the algo.monads library.

From its docstring:

State Monad: Monad describing stateful computations. The monadic values have the structure:
(fn [old-state] [result new-state]).

It expects a function that receives its old state and returns the result and the new state - these are called monadic values.

By designing the function to follow this contract, we can leverage the domonad macro - think of it as syntactic sugar for working with monads:

(require '[clojure.algo.monads :as m])

((m/domonad m/state-m
    [a pure-rand
     b pure-rand
     c pure-rand]
     [a b c])
     (java.util.Random. 100))

;; [[0.7220096548596434 0.19497605734770518 0.6671595726539502] 
;; #<Random java.util.Random@358ddfd6>]

In the example above, we’re using our pure-rand function in the context of the State Monad to generate 3 random numbers - based on some initial state - and returning them as a vector.

As we’ve seen before the result is itself in a vector alongside the new state.

This is where the State Monad and the validation problem meet:

In bouncer, each validation function is designed to be compatible with the State Monad, just like pure-rand above:

It receives an initial state - at first, the map to be validated - and returns a vector with the map of errors and the new state: the original map augmented with any errors from previous validators.

The end result, should one or more validations fail, is a map with all errors that might have happened, plus our new state.

Now if you head to the github repository and read the examples by keeping the State Monad and the above explanation in mind, the similarities should be obvious.

Wrapping up

As I mentioned in the beginning of the article, there are other validation libraries for Clojure and at the time of this writing they have more features than bouncer - by all means have a look at them.

However I will keep maintaining bouncer for a couple of reasons:

That’s what I’m using in my current side project
It takes a fundamentally different implementation approach that is in itself worthy of exploration
If nothing else, this is yet another example of where Monads can be useful.

Acknowledgments

Thanks to Steve and Julian for reviewing early drafts of this post as well as Nick for being such a PITA :) - our discussions led to a considerably nicer design.

As usual, let me know your thoughts.

So long 2012: Year highlights

2013-01-02T13:05:00+11:00

Keeping the tradition of end-of-year blog posts, here are my year highlights for 2012:

Clojure

I started clj-syd - the Sydney Clojure User Group - back in January and it has seen a major uptake. We consistently get an average of 25 people each month and there’s no shortage of talks and topics to discuss. It’s a great crowd and I’m proud to have started it and of being part of it.

Speaking

I spent most of the year studying functional programming and I tried to make my talks reflect that. Even the javascript talk I gave in April had a FP focus. Anyway, you can find some of the slides online:

The many facets of code reuse in JavaScript - this was given at a ThoughtWorks technical event in April
Continuation Passing Style and Macros in Clojure - this is the talk I gave at our first Clojure meetup in Sydney
Clojure Reducers - Another preso I gave at the clojure user group, in August.

Books

As usual I read a number of books this year and these are my favourites:

The Little Schemer

As they say, an oldie but a goodie. This is mandatory reading for anyone who consider themselves a serious programmer. The insights and techniques found here are invaluable. Do yourself a favor and buy it now.

For a Clojure take on it, check Julian Gamble’s series on The Little Schemer in Clojure

The Joy of Clojure

This is pretty much how I learned Clojure. I actually started reading it in November 2011 but felt I needed to put it down from time to time to go and code on my own to solidify what I learned. That’s why I only finished it in 2012.

This book packs a great deal of info and is a great way to get into both functional programming and Clojure.

Learn you a Haskell for Great Good

This is the best intro to Haskell ever. Hands down. ‘nuff said.

Clojure Programming

I like reading different books about the same subject to get to see it from various perspectives. Clojure Programming takes a different approach to The Joy of Clojure in that, as it progresses through topics and code examples, it contrasts it with languages likely to be familiar to the reader, such as Java, Ruby and Python. Another great alternative if you’ve been thinking of getting into Clojure but didn’t know where to start.

Content

Here’s just a few of the posts visitors found most interesting this year:

Monads in Small Bites Parts I, II, III & IV - Even though I only published this series in December, it quickly became one of the most read posts that month. And it’s also a personal favorite.
Build Automation With XCode 4.3, KIF and Jenkins - This turned out to be very popular - build automation and testing are not among the top priorities within the iOS community so I’m glad this helped some people out. It’s getting way better now.
Hiring Good People Is Really Simple - Another one high up in my analytics, and it still stands true.
JRuby on Rails and Legacy Java Apps: Managing Dependencies - The JRuby enterprise world seems to be hotter than ever before. I wouldn’t think this post from 2009 would still get this many visits. I haven’t been involved much with JRuby as of late so I wonder if this is still the way to go?

LambdaJam

LambdaJam is a conference for functional programmers and although it’s set to happen in May 2013 the wheels have already started turning - thus I had to list it as a highlight.

I’m fortunate enough to be involved with the organization alongside very bright people from the Australian functional programming community as well as Dave Thomas from the YOW! Conference who’s leading the effort. We’re all really excited about it.

Stay tuned, lots more info to come!

Goals

No resolutions. Goals. And I wanna achieve them. They’re simple and I hope this post will keep me in check

Better utilize my free time

This is a bit abstract but will help me achieve the goals below. The output of this goal is a calendar with time slots assigned to each one of the next goals - I’ve just done this now actually so this is a good start. No more procrastinating.

Books

I got a big pile of books I wanted to have read in 2012 so I’ll be updating my good reads profile with them and make sure I just do it - with the help of my new calendar from the goal above.

Side projects

In 2012 I worked on two side project which are not ready yet, so I can’t comment a whole lot on them apart from saying that one is being developed in Clojure and the other in Ruby - in 2013, these two will see the light of day.

Here’s to a new year

I hope you all had a great 2012 and are as excited as I am for the new year.

Happy holidays, safe driving and awesome parties! :)

Monads in small bites - Part IV - Monads

2012-12-08T17:36:00+11:00

This is Part IV of my Monads tutorial. Make sure you read the previous parts:

A quick recap

In Part I we learned about Functors, which are things that can be mapped over using a normal function - fmap is used for that.

Part II tought us that when our Functors themselves contain functions and we want them applied to the values contained in other Functors, Applicatives come to the rescue - and bring theirs friends pure and <*>.

Part III introduced Monoids which model a special type of relationship involving binary functions and their identity values.

Now it’s time for what I hope is the post you have all been waiting for :)

Monads

A word on context

So far I’ve said things such as wrapping stuff in Functors, unwrapping functions from Applicatives and putting results into minimal Functors. All this really means is that [Applicative]Functors - and Monads - have associated contexts that model some sort of computation.

For lists, for example, this means they represent computations that can have several results - non-determinism.

These computations can have much greater implications though - they can represent failure (or not!), do IO and even launch nuclear missiles. The point is: when we combine Functors/Applicatives/Monads, we carry their context with us to the end - they are essentially sequenced together.

This will become clearer with an example. For once I won’t start with lists - w00t! - so get ready for it!

The Maybe Monad

The Maybe monad models computations that can fail. Let’s have a look at an example.

Say you have an e-commerce system. When placing an order, a few things need to get done:

gather information about the order;
calculate shipping rates;
apply discount codes, if any, and;
finally place the order.

The code below shows the supporting functions that will be orchestrated in order to achieve this:

(defn calculate-shipping-rate [address]
    (if (= (:country address) "Australia")
        10.0
        nil))

(defn apply-shipping-costs [order shipping-rate]
    (assoc order :total (+ (:total order) shipping-rate)))

(defn lookup-discount-code [code]
    (if (= code "XMAS2012")
        5.0
        nil))

(defn apply-discount-code [order discount]
    (assoc order :total (- (:total order) discount)))

(defn place [order]
    (prn (str "Off you go! Order total: $" (:total order))))

Note that based on the code above, we can only ship to Australia and there is only one active discount code. Keep this in mind - you’ll see why later on.

Now let’s place an order for some Jalapeño sauce:

(def order {
    :items [{:name "Jalapeño sauce" :price 20.0}]
    :address {:country "Australia"}
    :discount-code "XMAS2012"
    :total 20.0
})

(def shipping-rate (calculate-shipping-rate (:address order)))
(def discount (lookup-discount-code (:discount-code order)))

(-> order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; "Off you go! Order total: $25.0"

Great! Soon I’ll be receiving some hot sauce to go with my burritos!

But wait, what if I had mistakenly set my address to somewhere other than Australia? How would this code behave?

(def another-order {
    :items [{:name "Jalapeño sauce" :price 20.0}]
    :address {:country "Brazil"}
    :discount-code "HACKERZ"
    :total 20.0
})


(def shipping-rate (calculate-shipping-rate (:address another-order)))
(def discount (lookup-discount-code (:discount-code another-order)))

(-> another-order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; NullPointerException   [trace missing]

Oops! Your e-commerce system just crashed! Not cool. But hey, this is easy to fix, right? We could just change our apply-shipping-costs function to something like this:

(defn apply-shipping-costs [order shipping-rate]
    (if shipping-rate
        (assoc order :total (+ (:total order) shipping-rate))
        order))


;;Remember we only support one discount code so the same problem could happen again
;;We need to change the apply-discount-code function as well

(defn apply-discount-code [order discount]
    (if discount
        (assoc order :total (- (:total order) discount))
        order))

Now let’s see what happens:

(def shipping-rate (calculate-shipping-rate (:address another-order)))
(def discount (lookup-discount-code (:discount-code another-order)))

(-> another-order
    (apply-shipping-costs shipping-rate)
    (apply-discount-code discount)
    (place))
;; "Off you go! Order total: $15.0"

Well, it doesn’t crash but we can’t ship to Brazil anyway! So the code is still incorrect! What we really want is a way to halt the whole computation - placing an order - if any of those steps fail.

Of course we could fix it with a couple more if forms before trying to call the place function but you see where this is going.

Essentially our nice little functions became burdened with context: each of them is now aware that they can fail and need to cater for it.

Enter the Monad

I’ll jump straight to how the code could look like if we had monads - it won’t work now because we haven’t actually implemented the monad yet, but this should whet your appetite.

Also, assume we reversed the changes from before - the functions don’t have the if forms checking its arguments any longer, just like in the original version. Here’s the code:

(domonad maybe-monad
    [order order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;;"Off you go! Order total: $25.0"

(domonad maybe-monad
    [order another-order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;; nil

domonad receives the monad you want to operate on, a vector of bindings and an expression that’s the final result of the whole thing.

Is your mind blown yet? :) Somehow the whole operation fails and yields nil in the second call to domonad above - without any if forms and without crashing! To see why that is, I’ll now explain the monad type class from Haskell.

The Monad Type Class

Here’s the Haskell definition of the Monad type class (I left the fail function out so we can focus on the core of it):

class Monad m where
    return :: a -> m a

    (>>=) :: m a -> (a -> m b) -> m b

    (>>) :: m a -> m b -> m b
    x >> y = x >>= \_ -> y

Let’s distill those bad ass type signatures:

return - much like pure from Applicative Functors, return is responsible for wrapping a value of type a into a minimum context Monad that yields a value of type a - referred to as a monadic value.

(>>=) - often called bind - is a function of two arguments. The first is a monadic value of type a and the second is a function that receives a value of type a and returns a monadic value of type m b which is also the overall result of the function.

In other words: bind runs the monad m a, feeding the yielded a value into the function it received as an argument - any context carried by that monad will be taken into account.

(>>) - often called then - This function receives two monads, m a and m b, and returns a monad of type m b. It is generally used when you’re interested in the side effects - the context - carried out by the monad m a but doesn’t care about the value a it yields. It’s rarely implemented in specific monads because the type class provides a default implementation:

It applies bind to the monad x and a function that ignores its argument (\_ -> y) - which by convention is represented by an underscore - and simply yields the monad y: that’s the final result of the computation.

I won’t be implementing then in Clojure though - I’ll focus on return and bind, since then is essentially a helper function you could write yourself.

The Maybe Monad - Clojure edition

With definitions out of the way, let’s implement the Clojure version of the Maybe monad.

(def maybe-monad {
    :return (fn [v] v)
    :bind (fn [mv f]
            (if mv
                (f mv)
                nil))})

Yup. That’s it.

For the maybe monad, all its context needs to represent is a single value or the absence of value. We do this inside bind by checking if the monadic value mv is nil. If it isn’t, we apply f to it, which will yield another monadic value. If, on the other hand, mv IS nil, we just return nil, bypassing the function application entirely.

return, as we saw, wraps a value into a minimal monad. In this case this is the value itself, so we just return it untouched.

This is how one may go about using it:

(-> another-order
    ((:bind maybe-monad)
     (fn [order]
       (-> (calculate-shipping-rate (:address order))
           ((:bind maybe-monad)
            (fn [shipping-rate]
              (-> (lookup-discount-code (:discount-code order))
                  ((:bind maybe-monad)
                   (fn [discount]
                     ((:return maybe-monad)
                      (-> order
                        (apply-shipping-costs shipping-rate) (
                        apply-discount-code discount)
                        (place))))))))))))
;; nil

WOW! That is awful! And I won’t blame you for not wanting to read through this aberration. But trust me, it does the job.

However, you’re probably thinking: that looks nothing like the nice little domonad notation we saw earlier!

Well, you’re right. That’s because domonad is a macro - it gives us some syntactic sugar that expands into the real code shown above. In order to be able to use the domonad notation, paste the following into your REPL:

(defn monad-steps
    ([monad steps expr]
        (if (seq steps)
            (let [fst (first steps)
                  snd (second steps)]
                  `((:bind ~monad)
                    (fn [~(symbol fst)]
                        (->  ~snd ~(monad-steps monad (subvec steps 2) expr)))))
            expr)))


(defmacro domonad [monad steps expr]
    (let [args (map first (partition 2 steps))
          forms (map second (partition 2 steps))
          new-steps (subvec (vec (interleave (cons nil args) forms)) 2)]
          `(let [m# ~monad]
            (-> ~(second steps)
                ~(monad-steps monad new-steps
                    `((:bind ~monad) (fn [~(symbol (last args))] ((:return ~monad) ~expr))))))))

All set! Now you should be able to run the examples that use domonad without any hiccups. Give it a shot:

(domonad maybe-monad
    [order another-order
     shipping-rate (calculate-shipping-rate (:address order))
     discount (lookup-discount-code (:discount-code order))]
     (-> order
        (apply-shipping-costs shipping-rate)
        (apply-discount-code discount)
        (place)))
;; nil

Note: macros can be daunting at times so don’t worry too much about its implementation. It’s way more important to me that you understand the end result than it is to be able to implement the macro yourself - but by all means dissect this implementation if you feel inclined to do so :)

Now that’s way better. The maybe monad abstracted away the logic behind computations that can fail so you don’t have to worry about it in your functions - you can just focus on writing them.

In the end I also believe it aids readability once you get used to it.

Don’t break the law

Monads have laws of their own too! Let’s have a look at them.

Right unit

Binding a monadic value m to return should be equal to m itself

In Haskell speak:

m >>= return =  m

The proof in Clojure:

(def m 10)
(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))

;; given the above, this...
(>>= m return) ;; 10

;;is the same as
m ;; 10

Left unit

Applying return to x and then applying >>= to the resulting value and fshould be the same as applying f directly to x

In Haskell speak:

return x >>= f =  f x

The proof in Clojure:

(def x 10)
(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))
(def f (fn [v] (* v 2)))

;; given the above, this...
(-> (return x) (>>= f)) ;; 20

;;is the same as
(f x) ;; 20

Associativity

Binding m to f and then applying >>= to the result and g should be the same as applying >>= to m and a function of argument x that first applies f to x and then binds it to g.

Phew…another mouthful, huh? Code should make it clearer. As usual, Haskell comes first:

(m >>= f) >>= g  =  m >>= (\x -> f x >>= g)

And now let’s prove it in Clojure:

(def >>= (:bind maybe-monad))
(def return (:return maybe-monad))

(def m 10)
(def f (fn [v] (* v 2)))
(def g (fn [v] (+ v 10)))

;; given the above, this...
(-> (>>= m f) (>>= g)) ;; 30

;;is the same as
(>>= m
     (fn [x]
        (>>= (f x) g))) ;; 30

Alright, we’re getting to the end now! Hold on just a little longer!

One last thing - The List Monad

Yeah, I’m sure you saw this coming. Lists are monads too! I’ll make this quick and show its implementation and usage in Clojure - bear with me one last time.

(def list-monad {
    :return (fn [v] [v])
    :bind (fn [mv f]
        (if (seq mv)
            (apply concat (map f mv))
            []))
    })

;;let's play with it

(domonad list-monad
    [a [1 2]
     b [a, (- a)]]
     (* 3 b))
;; (3 -3 6 -6)

(domonad list-monad
    [a [1 2]
     b []]
     (* 3 b))
;; () - an empty list. 

This should look familiar if you’ve used list comprehensions in Clojure or other languages such as Python:

(for [a [1 2]
     b [a, (- a)]]
     (* 3 b))
;; (3 -3 6 -6)

See? You’ve been using monads all along and didn’t even know it! How awesome is that?

Also note that we didn’t need to re-implement domonad for the list monad. It’s a generic macro that will work with any monads you throw at it!

It’s interesting to see how the list and the maybe monads differ. This time, return puts the value v inside a list and returns it because for lists, a minimum monad is a list with a single element.

bind is a bit more interesting. It first checks to see if mv is empty, in which case it returns an empty list, causing the whole computation to stop. If, however, mv is NOT empty, it maps f over every element in mv.

The resulting list is potentially a list of lists, since functions fed to monads - such as f in this case - have to return monadic values. That’s why we then apply concat to the resulting list, effectively flattening it.

Final words

Hopefully you now have a much better understanding of Monads and should start seeing in your code use cases and/or opportunities for the monads shown here.

You’ll notice that this Clojure implementation of monads used only normal functions - that was by design since I wanted this implementation to be as close as possible to Clojure’s core.algo.monads library. You should have a look at it.

Also, bear in mind that this tutorial is by no means exhaustive - there’s a lot more about monads that I could possibly cover in a blog - it was hard enough ending it here! But if you want to study more about them, I’d recommend starting with these resources:

Learn You a Haskell for Great Good - this book is an excellent intro to Haskell and it was the approach found there that made me grok monads - highly recommended and freely available online.
The Monads Section on the Haskell wikibook - another free online resource

That’s it from me. I hope you enjoyed the read and if you made it until here, a big thank you.

Monads in small bites - Part III - Monoids

2012-12-05T09:25:00+11:00

This is Part III of my Monads tutorial. Make sure you read the previous parts:

Monoids

Simply put, Monoids describe types containing a binary function and an identity value.

When applied to the identity value and a random value x, said function leaves its argument x untouched, returning it as a result.

This short description should be enough to get the conversation started.

Here’s how Haskell defines a Monoid:

class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat ms = foldr mappend mempty ms

This type introduces three new functions so let’s walk through each one of them:

mempty - I started with a lie since mempty isn’t actually a function. You can think of it as a constant of the same type of the Monoid m. It is this monoid’s identity value.

mappend - A poorly named function, mappend is the binary function I mentioned earlier. It receives two arguments of type m and returns a value of type m

mconcat - It receives a list of Monoids m and reduces them to a single Monoid of type m. What’s interesting about this snippet is that the Monoid type class provides a default implementation for mconcat: it simply calls foldr with the binary function mappend, a starting value of mempty and the list of Monoid values ms

Enough Haskell! Let’s have a look at a few examples.

Did you know that, in Clojure, the functions * and + are monoids? Yup. But don’t take my word for it. Let me prove it to you:

(def  mempty (+)) ;; 0
(def  mappend +)
(defn mconcat [ms]
    (reduce mappend mempty ms))

(mappend 3 4) ;; 7

(mconcat [2 3 4]) ;; 9

Whoa! What happened here? Am I just making this stuff up?

Not really. I only defined the same haskell names to their Clojure counterparts for clarity. Totally overkill. The code above is the same as:

(+) ;; 0

(+ 3 4) ;; 7

(reduce + [2 3 4]) ;; 9

Did you notice that on the second call to reduce we did not provide an initial value? That’s because reduce will attempt to get its initial accumulator by calling the reducing function without arguments - hence mempty == (+).

So that means we don’t even need an mconcat function since in Clojure, reduce works with monoids as well!

Update: this isn’t entirely true. When I wrote this post I had in mind the version of reduce provided by the Clojure (1.5+) reducers library. The source code shows how that is the case.

The implementation of reduce in clojure.core however uses the first element of the collection being reduced over as its seed.

But how the hell do you create a monoid in Clojure then? I’m glad you asked. Let’s create our own plus-monoid!

Your first monoid

In Part I I implemented Functors using protocols and records. In Part II I showed how Applicative Functors could be implemented using multimethods.

This time around I won’t be using any of these. I’ll implement Monoids using pure functions:

(defn plus-monoid
    ([]
        0)
    ([a b]
        (+ a b)))

(plus-monoid) ;; 0 - same as mempty

(plus-monoid 3 4) ;; 7 - same as mappend

(reduce plus-monoid [2 3 4]) ;; 9 - when working with monoids, reduce is the same as mconcat

We start by defining a function with multiple arities. The first body receives no arguments, so we just return the identity value for summation, which is 0 (zero). The second body receives two arguments so we can just add them up. Multiplication can be implemented in a similar fashion but obviously with the identity value of one.

Easy, huh?

Oh, by the way, lists are Monoids too! Who’d have thought?

Here’s its Clojure implementation:

(defn list-monoid
    ([]
        '())
    ([a b]
        (concat a b)))

(list-monoid) ;; () - remember, same as mempty

(list-monoid [1 2 3] [4 5 6]) ;; (1 2 3 4 5 6) - remember, same as mappend

(reduce list-monoid [[1 2 3] [4 5 6] [7 8 9]]) ;; (1 2 3 4 5 6 7 8 9) - mconcat in action

Same rules apply but for lists mappend is achieved by using concat inside our monoid function.

Also, since our binary function concatenates two lists together it makes sense that mempty is () (the empty list). Remember mempty is supposed to be an identity value so if we stitch () and [1 2 3] together, we’re left with [1 2 3] which is exactly what we’d expect.

You can see now why I said mappend was poorly named. While it makes sense when you think about lists, mappend doesn’t do any appending in our plus-monoid and in fact most monoids don’t append anything. Just keep this in mind if you see any haskell code using it: mappend is just a binary function.

Don’t break the law

You saw this coming, huh? Monoids also come with a couple of laws. You know the drill. Let’s prove they both hold.

Identity

Applying mappend to mempty and a monoid x should be the same as the original x monoid.

In Haskell:

mappend mempty x = x
mappend x mempty = x

And the proof in Clojure:

;; first, the plus-monoid
(def mempty (plus-monoid))

(def x 10)

;; This...
(plus-monoid mempty x) ;; 10

;; ...is the same as:
(plus-monoid x mempty) ;; 10

;;now, the list-monoid

(def mempty (list-monoid))
(def x [1 2 3])

;; This...
(list-monoid mempty x) ;; (1 2 3)

;; ...is the same as:
(list-monoid x mempty) ;; (1 2 3)

Associativity

Applying mappend to a monoid x and the result of applying mappend to the monoids y and z should be the same as first applying mappend to the monoids x and y and then applying mappend to the resulting monoid and the monoid z

In Haskell:

mappend x (mappend y z) = mappend (mappend x y) z

And the proof in Clojure - remember that calling the monoid function with two arguments is equivalent to mappend in haskell:

;; first, the plus-monoid

(def x 10)
(def y 25)
(def z 40)

;; This...
(plus-monoid x (plus-monoid y z)) ;; 75

;; ...is the same as:
(plus-monoid (plus-monoid x y) z) ;; 75

;;now, the list-monoid

(def x [40])
(def y [10 25])
(def z [50])

;; This...
(list-monoid x (list-monoid y z)) ;; (40 10 25 50)

;; ...is the same as:
(list-monoid (list-monoid x y) z) ;; (40 10 25 50)

Almost there…

This puts an end to Part III. It’s time to head to the pub.

When you’re back look for the final post in these series - Part IV - where we will conclude our journey by finally introducing Monads!

Monads in small bites - Part II - Applicative Functors

2012-12-02T21:43:00+11:00

This is Part II of my Monads tutorial. Make sure you read the previous parts:

Part I - Functors
Part II - Applicative Functors (this post)
Part III - Monoids
Part IV - Monads

Applicative Functors

In Part I I talked a little about Haskell type signatures and introduced Functors, which provide a way to map standard functions over values which are wrapped inside a Functor - we used fmap for that. You might want to skim through it again as a refresher.

Now suppose you have Functors that wrap functions and that you want to apply those wrapped functions to other Functors, maybe even composing new functions on the way!

What then?

Well you’re in luck! Applicative Functors do just that! They’re Functors on steroids.

Here’s how Haskell defines the Applicative data type:

class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b

Based on our previous knowledge of Haskell’s type signatures, we can infer from this definition that in order for it to be an Applicative Functor, f must already be a Functor.

Let’s break this down and have a closer look at the two new functions this type introduces:

pure is a function that takes a value a and wraps it into a minimal Functor f.

<*> is a function that takes two arguments: the first is a Functor f that wraps a function of type a -> b. The second argument is a Functor f that wraps a value - which could be a function! - of type a. The final result is a Functor f that wraps some value of type b - which was obtained by somehow applying the function (a -> b) to the Functor f a.

pure has a straightforward explanation whereas <*> is a bit more involved.

To clear things up, I’ll show the type signatures again but this time as if they only worked with the List Functor that we’ve been working on:

pure :: a -> [a]
(<*>) :: [(a -> b)] -> [a] -> [b]

Let’s revisit those definitions:

pure is a function that takes a value a and puts it into an empty list, returning the resulting single element list.

<*> is a function that takes two arguments: the first is a list containing one or more functions of type a -> b. The second argument is a list of one or more values - or functions! - of type a. The final result is a list of one or more values of type b - which was obtained by somehow applying the function (a -> b) to the Functor f a.

Enough definitions though! Let’s extend our List Functor and make it an Applicative as well.

While we’ll still be using the List Functor we implemented in Part I, this time I’ll implement its Applicative version using multimethods for a change. Here’s the code:

;; it dispatches on the record type since we could have implementations of pure for List, Maybe, Either etc...
(defmulti pure (fn [f _] f))
(defmethod pure List [_ v]
    "Wraps value v in a list"
    (List. [v]))

;; it dispatches on the class of the Functor instance passed in the 1st argument
(defmulti <*> (fn [fs _] (class fs)))
(defmethod <*> List [fs xs]
    "Unwraps the functions in fs, applies them to the Functors in xs, wrapping the result at the end"
    (List. (for [f (:wrapped fs)
                 x (:wrapped xs)]
                (f x))))

By focusing on the List as an Applicative Functor we can more easily understand what these functions do. From the code above, pure’s job is a simple one: all it does is wrap it’s argument v into a minimal List functor which in our case means a Functor wrapping a one element list.

<*> on the other hand is responsible for somehow unwrapping the functions brought in by the Applicatives in fs and applying them to the [Applicative] Functors in xs. It does that by using list comprehensions and wraps the result into a new List Functor.

Study this code carefully. It can be tricky.

Note: When I first encountered <*> I had no idea what this function was called. I asked the twittersphere and it seems it’s called apply. In the process of figuring this out I was enlightened by this conversation. It turns out <*> has several names. Can you guess which one is my favorite? :)

With the Applicative functions defined for our List, let’s take it for a spin:

(def fs (List. [#(* 2 %) #(+ 10 %)]))
(def xs (List. [1 2 3]))

(<*> fs xs) ;; List{:wrapped (2 4 6 11 12 13)}


(def g (pure List #(* 50 %)))
(<*> g xs) ;; List{:wrapped (50 100 150)}

There should have been no surprises here. Read the code again and make sure it’s all fresh before moving along.

Don’t break the law

Just as Functors, Applicative Functors also need to obey some laws:

Identity

Feeding a function f to pure and applying the resulting Applicative to the Functor v should be the same as directly mapping f over the Functor v

In Haskell speak:

pure f <*> v = fmap f v

And this is the proof, in Clojure:

(def f #(+ 2 %))
(def v (List. [10]))

;; given the above, this...
(<*> (pure List f) v) ;; List{:wrapped (12)}


;; ...is the same as:
(fmap v f) ;; List{:wrapped (12)}

Composition

The result of applying an Applicative Functor that yields the function composition operator to the Applicative u, then apply the resulting Functor to v and finally applying that result to the final Applicative w should be the same as applying v to w and then applying u to the resulting Applicative.

That was a mouthful! Let’s see how Haskell tells this story:

In Haskell:

pure (.) <*> u <*> v <*> w = u <*> (v <*> w)

I needed to cheat a bit in Clojure to prove this law since functions are not curried by default like they are in Haskell. But this code should still clearly show how this law holds:

(def u (List. [#(* 2 %)]))
(def v (List. [#(+ 10 %)]))
(def w (List. [1 2 3]))

;; Given the above, this...
(-> (pure List (fn [x] (partial comp x)))
  (<*> u)
  (<*> v)
  (<*> w)) ;; List{:wrapped (22 24 26)}

;; ...is the same as:
(<*> u (<*> v w)) ;; List{:wrapped (22 24 26)}

Homomorphism

The result of applying the pure value of f to the pure value of x should be the same as applying f directly to x and then feeding that into pure.

In Haskell:

pure f <*> pure x = pure (f x)

And in Clojure:

(def f #(* 2 %))
(def x 10)

;; given the above, this...
(-> (pure List f)
  (<*> (pure List x))) ;; List{:wrapped (20)}

;; ...is the same as:
(pure List (f x)) ;; List{:wrapped (20)}

Interchange

The result of applying an Applicative Functor u to the pure value of y should be the same as taking the Applicative obtained by calling pure with a function that applies its argument to y and then applying that to u

In Haskell:

u <*> pure y = pure ($ y) <*> u

This type signature presents new syntax so before proving the law in Clojure, I want to explain what ($ y) means.

In Haskell, $ is the function application operator. So if we give y a value of 10, I can show you that in this law $ essentially translates to a single argument function that applies its argument to 10:

let double a = a * 2 -- helper function. it doubles its argument

-- given the above, this...
(($ 10) double) -- 20

-- ...is the same as:
let dollarTen = (\a -> (a 10))  -- this is Haskell's lambda syntax. It's equivalent to ($ 10)
((dollarTen) double) -- 20

Now, to the proof in Clojure:

(def u (pure List #(+ 10 %)))
(def y 50)

;; given the above, this...
(<*> u (pure List y)) ;; List{:wrapped (60)}

;; ...is the same as:
(def dollar-y #(% y)) ;; it's called dollar-y to show the correlation with the explanation above
(<*> (pure List dollar-y) u) ;; List{:wrapped (60)}

This brings us to the end or Part II. Two down and two to go.

I hope you’re still with me but go home now.

Or better yet go to the gym lift some weights and think about these Functors on steroids. When you’re back, look out for Part III.

Monads in small bites - Part I - Functors

2012-11-30T01:06:00+11:00

Today I join the already bloated group of people who wrote monad tutorials. It’s a bit of a ritual, really.

Different than most tutorials though I aim to take a different approach. The good news is that I won’t be comparing monads to burritos :)

People say one needs to have his/her own epiphany in order to understand Monads and reading explanations from others is of little help. My goal is to disprove that.

To that end, this tutorial will be split in four parts:

You might want to bookmark this page - once the other parts are up, I’ll update the list above with the links to them.

Before we start

I know what you’re thinking: Do I really need to know Applicative Functors just to grasp Monads?

Well, no. However, I found that gradually building your knowledge from Parts I, II and III will allow you to fully grasp monads without the need for burritos or elephants.

You should also be familiar with a functional programming language. Any language should be fine but you’ll get the most out of this tutorial if you’re familiar with Haskell and/or Clojure.

If you’re not familiar with Clojure, fear not - Clojure is a small language and the code snippets should still make sense if you put your mind to it - they’re all short and sweet. I also encourage you to re-implement the examples in your language of choice to gain a deeper understanding on the subject.

Ready then? Let’s dive in.

Just enough Haskell

This is not a Haskell tutorial but trust me when I tell you that learning just enough about its type signatures will make all the difference in the world in understanding the concepts I’m about to present.

Although I’ll be using a little bit of Haskell syntax, I’ll also provide implementations in Clojure. They are in order so you should be able to paste all code sample in the REPL and follow along if you wish.

Type signatures

I’ll make this quick. Say you have a function called mk-vec that creates a 2D vector with x and y coordinates. Such function could easily be coded in Clojure like this:

(defn mk-vec [x y]
  {:x x :y y})

;; using it
(def my-vec (mk-vec 10 15))
(:x my-vec) ;; 10

As you can see, this function takes two arguments - x and y - and returns a map - or hash if you come from Ruby - that wraps those values in it, providing an easy way to retrieve them.

Now if this function had been implemented in haskell this would be its type signature - read the comments:

import qualified Data.Map as Map -- just giving Data.Map an alias
mkVec :: a -> a -> Map.Map [Char] a -- this is the type signature

mkVec x y = Map.fromList [("x", x), ("y", y)] -- this is the implementation. You can ignore this part.

-- using it
myVec = mkVec 10 15
Map.lookup "x" myVec -- Just 10 
--
-- ignore the actual value that is returned. Read it as 10 for now.

Whatever comes after the :: is part of the function type signature. Read it like this:

This is a function that receives two arguments of type a - which means any type - and returns a Map of key/value pairs where the key is of type [Char] - technically a list of Char values but for all effects and purposes just read it as String - and the value is of type a - the same type as its arguments.

It might help to see the type signature in this light:

mkVec :: a -> a -> (Map.Map [Char] a)

It highlights the return value in parenthesis.

Now let’s have a look at a built in function, *. As you know, it performs multiplication and this is its type signature:

(*) :: Num a => a -> a -> a

Can you guess now what it means? I’m sure you can. There’s one small difference though: this function has a type constraint - it’s that Num a => … part of the signature. Read it like this:

This is a function that receives two arguments of type a and returns a value of the same type, as long as the type of a is an instance of Num

And that’s it for now. Read it again to make sure it’s fresh in your mind and then continue.

As we encounter more type signatures, I’ll walk you through each one of them - but if you got it up until now, you’ll easily grasp the other type signatures.

Functors

In a nutshell Functors are things that can be mapped over.

Haskell defines Functors like this:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Let’s dissect that type signature:

fmap is a function that receives two arguments: the first is a function that receives an argument of type a and returns a value of type b and the second is a Functor that contains a value of type a - represented by f a. The result of calling fmap is a Functor of same type - f - containing a value of type b, which is the result of applying the function to a.

Too much? Let’s have a look at an example: the List Functor.

If we rewrite the fmap type signature as if it only worked on lists, this is what we’d come up with:

  fmap :: (a -> b) -> [a] -> [b]

This new type signature allows us to rewrite that last definition:

fmap is a function that receives two arguments: the first is a function that receives an argument of type a and returns a value of type b and the second is a List of zero or more values of type a. The result of calling fmap is a List of zero or more values of type b, each of which is the result of applying the function to each a element.

Does this sound familiar to you? It should, because this is essentially what the map function available in most functional-ish languages does! It takes a function and a list, applies the function to every element in the list while putting the results into a new list, finally returning it.

In fact, the fmap implementation of the List Functor from Haskell is implemented in terms of map.

Let’s see how that could be done in Clojure. I’ll use protocols and records but they are not strictly required for this.

Here’s our Functor protocol:

(defprotocol Functor
    (fmap [functor f] "Maps fn over the functor f"))

And now our List Functor:

(defrecord List [wrapped]
    Functor
    (fmap [functor f]
        (List. (map f (:wrapped functor)))))

In the snippet above all we’re saying is that the List record must satisfy the Functor protocol, which makes sense. fmap then is responsible for unwrapping the value contained in the list functor and mapping f over it.

Give it a go!

(def my-list-functor (List. [1 2 3])) ;; List{:wrapped (1 2 3)}

(fmap my-list-functor #(* 2 %)) ;; List{:wrapped (2 4 6)}

We can now map arbitrary functions over the values wrapped in a Functor! Awesome!

Note: In our Clojure version of the List Functor, it is implemented as a Record that wraps a primitive Clojure list/vector - []. As I mentioned this is not necessary but I chose to do it here to explicitly show the relationship with the Haskell types.

Don’t break the law

Now that we got a feel for what Functors are, it’s worth noting that they must obey a few laws to be considered full-fledged Functors.

Identity

Mapping an identity function over a Functor is the same as applying identity to the Functor itself

This is how Haskell puts this law:

fmap id functor = id functor

Translating that to Clojure:

;;This...
(fmap my-list-functor identity) ;; List{:wrapped (1 2 3)}

;;is the same as:
(identity my-list-functor) ;; List{:wrapped [1 2 3]}

Composition

If you compose the functions f and g and map the resulting function over the Functor, that is the same as first mapping g over the Functor and then mapping f over the resulting Functor.

From the description you can see that this law involves function composition. In Clojure, that’s achieved with the comp function.

Again, let’s see how this law is defined in Haskell:

fmap (f . g) functor = fmap f (fmap g functor)

Note: The . operator denotes function composition in Haskell

And the proof in Clojure:

(def f #(+ 10 %))
(def g #(* 2 %))

;; given the above, this...
(fmap my-list-functor (comp  f g)) ;; List{:wrapped (12 14 16)}

;; is the same as:
(-> my-list-functor (fmap g) (fmap f)) ;; List{:wrapped (12 14 16)}

Note: make sure you’re familiar with Clojure’s threading macro: -> . I’ll be using it in most code snippets.

Nice! All laws hold so we can sleep peacefully in the knowledge that our Functor works as expected.

Now go get a drink and stay tuned for Part II, where I’ll introduce Applicative Functors.

This is what we built in 24 hours

2012-11-05T11:12:00+11:00

Last week our current client - ninemsn - ran the 3rd edition of their HackDay.

It’s akin to Atlassian’s ShipIt days so if you’re not familiar with the concept, you should check their page but here’s the gist:

We’re given 24 hours to work on whatever we like as long as it’s related somehow to the business
We’re also free to use any technology we want

The team consisted of @romainprieto, Pranav Raja, @thepaddedcell, @stewgleadow and myself (@leonardo_borges).

The idea: Cool story, bro!

@romainprieto came up with it:

A mobile app that could scan QR codes on a printed JIRA story card and provide features such as assigning a card to yourself, moving it between columns and adding comments to it.

This is a common need. Most people will manage their stories in some sort of software such as JIRA. But it’s also common to have a physical story wall.

The problem then is keeping them in sync. It’s all too common for people to move the cards on the well and forget all about JIRA.

Well, not anymore. This is exactly what our HackDay project tackles.

In 24 hours, we built two native mobile applications - Android and iPhone - that are able to scan QR Codes printed on the story cards and, through integrating with the JIRA REST API, provide all the necessary functionality needed for:

Assigning a story to yourself - whoever is logged in to the app
Moving the story between states - e.g.: In Analysis, Resolve Issue, Reopen Issue etc…
Adding comments to a given story

All code is open source and on github. Check it out! - and bear in mind this was written in 24 hours… ;)

We didn’t stop there though. We actually finished early and had a couple of hours to spare so we shot a video - yes, a video!!! - about the app. I’m telling you, this is Hollywood quality:

Also, checkout some screenshots of the Android version:

Enjoy! :)

Clojure, leiningen 2 and Heroku: AOT compilation gotchas

2012-09-10T10:41:00+10:00

Recently I upgraded the clojure project I’m working on to Leiningen 2 in order to start using nrepl - since swank-clojure is now deprecated. Little did I know this would lead me to a small debugging adventure.

Heroku

I use Heroku as my deployment platform and my project had been running on it for a few weeks without any issues. I also use Heroku’s PostgreSQL solution.

However, by upgrading to Leiningen 2, my project started throwing some weird exceptions during deployment - it couldn’t connect to my database any longer. Everything was fine on my local environment though.

Upon inspecting the deployment logs on Heroku, I realized that the Heroku Clojure Buildpack tries to perform Ahead of Time (AOT) compilation if it identifies the project is running Leiningen 2.x

This means that after receiving a git push Heroku runs this command:

lein with-profile production compile :all

At first this might seem harmless. But step back for a second and think about what this means for code that depends on environment variables.

Case in point: Lobos

Lobos is a clojure library for manipulating database schemas akin ActiveRecord migrations in Ruby land.

The real-world example on their github page recommends this code snippet for configuring a database connection:

(ns lobos.config
  (:use lobos.connectivity))

(def db
  {:classname "org.postgresql.Driver"
   :subprotocol "postgresql"
   :user "test"
   :password "test123"
   :subname "//localhost:5432/test"})

(open-global db)

More often than not this isn’t ideal. You’ll probably want to customise your database configuration based on environment variables. Something along these lines:

(ns lobos.config
  (:use lobos.connectivity))

(def db
     {:classname "org.postgresql.Driver"
      :subprotocol "postgresql"
      :user (System/getenv "DB_USER")
      :password (System/getenv "DB_PASSWORD")
      :subname (System/getenv "DATABASE_URL")})

(open-global db)

And you’re good to go - until Heroku decides to AOT compile your code.

Compilation

The Clojure compilation process caught me by surprise. As stated by Rich Hickey on this IRC log entry, “a side effect of compiling Clojure code is loading the namespaces in order to make macros and functions they use available”.

This means that during compilation, any top level function calls - such as (open-global db) from above - will get executed. The same applies to macros that expand to top-level function calls.

If said function call has no side effects, you’re probably ok.

The trouble with open-global though is that it effectively attempts a connection to the database!

BAM!

On Heroku the environment variables you rely on - such as DATABASE_URL - aren’t available on compile time meaning a connection will be attempted to an empty url. All sorts of badness.

After having understood why the compilation process was effectively executing top level function calls, I then wrapped that call to open-global in a function declaration:

(defn init []
  (open-global (db)))

This will prevent eager evaulation during compilation since all defn does is bind the given function body to a var.

Then, in the code that needs migrations to happen - such as in my midje tests setup - I initialize the database like this:

(background
 (before :contents (lobos.config/init))
 (before :facts (migrate)
         :after (rollback :all)))

I spent some time in the #clojure IRC channel on freenode and it is accepted that top level function calls should be avoided anyway - especially if you’re dealing with side effects.

I also applied the same principle to other initialization code I have such as the configuration for Korma.

Happy ending?

Not quite. After having spent quite some time to get to this point, this was the new error that was stealing my sleep:

Caused by: java.lang.NullPointerException
    at java.util.concurrent.ConcurrentHashMap.hash(ConcurrentHashMap.java:332)
    at java.util.concurrent.ConcurrentHashMap.get(ConcurrentHashMap.java:987)
    at clojure.lang.Namespace.find(Namespace.java:188)
    at clojure.core$find_ns.invoke(core.clj:3659)
    at clojure.core$the_ns.invoke(core.clj:3691)
    at clojure.core$ns_name.invoke(core.clj:3698)
    at my_app.env__init.load(Unknown Source)
    at my_app.env__init.<clinit>(Unknown Source)

This isn’t an unknown error. It basically means you’re trying to find a namespace that doesn’t exist. Or does it?

Once again this only happened if the code got compiled Ahead Of Time. Puzzling.

A couple of debugging hours later and I tracked it down to be a problem with clj-logging-config - a logging configuration utility for clojure. This is the offending code:

(ns my-app.env
  (:use
    clojure.tools.logging
    clj-logging-config.log4j))
(set-logger!) ;; this call causes the exception

set-logger! is a macro that makes use of the *ns* var. *ns* contains the current namespace and, due to what I’m assuming to be special semantics regarding this particular var, it shouldn’t be unquoted within a macro - which is why it was failing in AOT mode.

I opened an issue in the clj-logging-config github page. I eventually forked the project and fixed the issue in this pull request. That was then merged last Friday.

My code now works perfectly - regardless of AOT compilation.

Final thoughts

This was a nice little journey and I’m actually glad I went through it. I have a much better understanding of Clojure’s compilation process, worked out some quirks on Heroku and even got my first Clojure related open-source contribution accepted. Life is good.

Hopefully this will save other people a lot of time and effort debugging similar issues.

Sean Corfield: Clojure and CFML sitting in a tree

2012-08-23T00:03:00+10:00

Last night I attended the Adobe User Group here in Sydney. That might strike some of you as a big surprise given my relationship with Adobe is pretty much limited to fiddling with Photoshop/Lightroom to get my photos looking nice.

However the reason for which I attended the meetup is that Sean Corfield - a prolific member of the Clojure community - gave a presentation on how he introduced and migrated most of his backend code at World Singles from CFML to Clojure - hence my interest.

What follows is a mix of my own notes and what I could remember from the slides:

Going faster

The original platform was built in CFML between 2001 and 2008. It was essentially monolithic procedural code. It was rewritten in 2009 - when they introduced OO and a new version of CFML

Brief Stats

3 million members
1 million emails sent every day
2k concurrent users 24x7, on average

Clojure and WorldSingles

Tried .NET - ran into all sorts of trouble. Didn’t work well in production.
Tried Scala - Memory leaks in the built-in actor library were a deal breaker. The type system also wasn’t a good cultural fit.
Evaluated Clojure in 2010 - seemed like a good language to squeeze performance out of lower level components
Clojure version released in production in 2011
- Rewrote remaining Scala Code
- 6.3k LOC - 1.5k Tests LOC
- equivalent to 4x the CFML LOC
- Clojure is essentially used in the model (as in MVC)

Why add Clojure?

It’s fast - compiles down to JVM bytecode (and it’s faster than CFML)
Immutability (automatic thread safety)
- they found several thread safety bugs in the third party ColdFusion libraries being used
Built-in concurrency / parallelism support - future, pmap, pvalues etc.
Lazy sequences - being able to work with potentially ininite collections without bringing your server down.
All high quality, production ready Java libraries easily accessible via java interop.

What do they use it for?

Email
- html generation & sending
- tracking & log file analysis
Geolocation (rest/json)
i18n
Reporting (parallel queries) - he showed a bit of this code. Heavy use of futures + deref
Search engine integration (json/xml)
- This breaks down to two Clojure components:
- One feeds the search engine based on changes to the users profiles
- The other then runs against the search engine 24x7 trying to find new matches for users
(lightweight?) Persistence layer
- no ORM - thin framework over sql instead
- Same interface for both Mysql & MongoDB
- MongoDB being used after hitting performance issues in Mysql

Clojure ecosystem/community

Having an active Community is crucial for language adoption and the clojure community got this right:

Community
- 6700 developers on the mailing list
- ~300 developers on IRC 24x7
Active library development
- #23 language on Github
- Over 7k projects on github
- Nearly 2k libs on Clojars

The Future

Looking into Cascalog for big data processing
All new back-end/model code written in Clojure
Views/Controllers will remain in CFML
- This ties up with Sean’s answer to ‘What would you not use Clojure for?’
- He mentioned HTML rendering as the major reason. You can’t hand hiccup code to a designer.
- Similarly, while designers can work on Enlive templates, updating the dynamic bits in Clojure can be cumbersome.

Summary

It was great to hear the many good things Sean had to say about Clojure. WorldSingles seem pretty happy with the decision of migration their heavy-lifting code to it and hopefully these slide notes will give you some insight into the sort of things Clojure is good at.

~~Sean is likely to put his slides up somewhere so I’ll link to it as soon as I have it.~~ Here they are.

If you want to know more about Clojure and be involved in the community, you should come to the next clj-syd meetup.

Build automation with XCode 4.3, KIF and Jenkins

2012-05-03T13:17:00+10:00

UPDATE: As pointed to me in this commment, sym links aren’t necessary for Waxsim anymore. Check Jonathan Penn’s fork on github.

After coming back from my holidays in China - which were awesome - I had no downtime at ThoughtWorks and started at a brand new client/project - a much needed change from what I had been working on lately.

It’s an iOS project, more specifically an iPad app and that’s pretty much all I can tell you about it. I will however tell you how my first few days in the project have been so far.

Being a brand new project I wanted to get our CI environment up and running as fast as possible - after all the project has only a couple of tests now. For context, here’s our setup:

XCode 4.3
GHUnit (I’m not gonna talk too much about it since this was the easy part - their docs are pretty decent)
KIF (for UI tests)
Jenkins
WaxSim (Hack to get the iPhone Simulator to run on the command line)

In most environments I had worked so far - Java, Ruby, Clojure etc.. - running acceptance tests from the command line is a given and so is integrating that into your build system.

Well, that’s just not the case with iOS projects. These tasks can be a real pain and take a while to complete. Here’s what I had to do:

On your development Mac

I’m assuming here you have an XCode project with at least one KIF test and that it builds successfully from the GUI, when you hit play. Now we can move on to run the tests from the command line.

This is the script I’m using to run my KIF tests. I call it RunKIF.sh and will walk you through it:

#!/bin/bash

killall "iPhone Simulator"
rm /tmp/KIF-*

echo "Build the "UI Tests" target to run in the simulator"
xcodebuild -target "UI Tests" -configuration Release -sdk iphonesimulator clean build

OUT_FILE=/tmp/KIF-$$.out
# Run the app we just built in the simulator and send its output to a file
# /path/to/MyApp.app should be the relative or absolute path to the application bundle that was built in the previous step
echo "Running KIF tests"
/tmp/waxsim -f "ipad" "build/Release-iphonesimulator/MyApp.app" > $OUT_FILE 2>&1

# WaxSim hides the return value from the app, so to determine success we search for a "no failures" line
grep -q "TESTING FINISHED: 0 failures" $OUT_FILE

success=`exec grep -c "TESTING FINISHED: 0 failures" $OUT_FILE`


# if there was a failure, show what waxsim was hiding and crucially return with a non-zero exit code
if [ "$success" = '0' ]
then 
    cat $OUT_FILE
    echo "==========================================="
    echo "GUI Tests failed"
    echo "==========================================="
    exit 1
else
    echo "==========================================="
    echo "GUI Tests passed"
    echo "==========================================="
fi

You’ll notice there are mainly two things happening in this script:

It runs xcodebuild to build the target against which your tests will run
uses WaxSim to finally run your tests

To get the building step to work, despite what KIF’s documentation DOESN’T tell you, you need to add KIF as a target dependency to your KIF Tests target. This SO thread can walk you through it.

Now on to the fun stuff! For some reason I didn’t have the time to dig into, WaxSim seems to expect XCode to be under /Developer/ on your Mac.

The problem is that since Apple started distributing Xcode through the AppStore, it now lives under /Applications/Xcode.app/Contents/Developer/. Bam! This can cause all sorts of issues when building both WaxSim and your project. So if you see weird error messages complaining about not being able to find DevToolsFoundation.framework and the like, these sym links will probably fix things for you:

sudo ln -s /Applications/Xcode.app/Contents/Developer/ /Developer
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsCore.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsCParsing.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsFoundation.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsInterface.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsKit.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsRemoteClient.framework /Developer/Library/PrivateFrameworks/
sudo ln -s /Applications/Xcode.app/Contents/OtherFrameworks/DevToolsSupport.framework /Developer/Library/PrivateFrameworks/

I know, right? Moving on.

By now you should be able to successfully run RunKIF.sh and get meaningful results from your test. Let’s configure our CI server now, shall we?

On your CI Mac

Depending on which state your build box is, you might need to create the same sym links I created in the previous section. So ssh into your build box and try to build your project from the command line:

xcodebuild -target "UI Tests" -configuration Release -sdk iphonesimulator clean build

This time I’ll assume you already have Jenkins installed and running.

Your Jenkins server is probably running as the jenkins user. You need to change that. Jenkins has to be running within a Desktop session - that’s a requirement from WaxSim. It needs an active desktop session in order to launch the simulator - and thus needs to run as a user who can login to your CI Mac.

If you installed Jenkins using Homebrew, here’s a plist you can use to specify which user jenkins should run as:

<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
<plist version="1.0">
<dict>
    <key>Label</key>
    <string>Jenkins</string>
    <key>ProgramArguments</key>
    <array>
    <string>/usr/bin/java</string>
    <string>-jar</string>
    <string>/usr/local/Cellar/jenkins/1.439/lib/jenkins.war</string>
    </array>
    <key>RunAtLoad</key>
    <true/>
    <key>UserName</key>
    <string>UserWhoCanLogintoThisMac</string>
</dict>
</plist>

Then load the new plist:

launchctl load -w  /Users/UserWhoCanLogintoThisMac/Library/LaunchAgents/org.jenkins-ci.plist

Don’t forget to enable automatic login on the CI Mac for the user Jenkins is using. Check this article to learn how to do it.

Now we’re mostly done. Just go ahead and configure your project.

Add a build step of the type Execute Shell and provide sh RunKIF.sh as the command string. Trigger your build and everything should work as expected.

Final thoughts

Once I actually got these steps together to write this post, it didn’t look like much. But the amount of time I wasted finding out what had to be done to actually make this work is just insane.

I’m shocked at how much behind iOS development tools seem to be. It just shouldn’t take this much effort and time only to get some UI tests automated. So far I’m disappointed with the tooling around the Apple ecosystem and I really hope this improves sooner rather than later.

clj-syd report #0

2012-02-22T21:14:00+11:00

Last night we held the first ever meetup for the Sydney Clojure User Group!

When I decided to start running the meetups I had no idea we’d end up with 37 people on the first night! What a great turn out!

As for the content, here’s what you missed:

Running Clojure apps on Heroku - Lincoln Stoll (@lstoll)

Linc works for Heroku but ended up not spending a whole lot of time talking about that - instead he showed us how to build a simple web application using Compojure, a small Clojure web framework.

He then evolved the example by implementing it using Noir - yet another web framework that builds on top of Compojure, adding some helpful macros.

To top it off, the UI was implemented in ClojureScript - so that was all Clojure from end to end!

Paredit (in Eclipse) for the IDE junkie - Matt Quail (@spudbean)

If you’re into lisps and use emacs - if not you should anyway - you learned to love paredit.

However, not everyone gets to write Clojure for a living and a lot of us end up in some sort of IDE. If you’re in Java land, a popular choice is Eclipse and Matt showed us how you can get the paredit goodness right there using the Eclipse plugin counterclockwise.

Building a better Clojure REPL - Cosmin Sterejean (@offbytwo)

Frustrated with the Clojure REPL? Wish you had more useful shortcuts? Decent line editing? Saving that nice function you’ve been working on right from the REPL? Then make sure you check out both the presentation and IClojure, Cosmin’s project.

Definetly worth a try.

Where do I put my DependentStrategyTemplateAbstractFactory? - Bayan Khalili

Bayan was in one of our internal meetups. Some people raised the fact that we don’t see a lot of the design patterns made popular by the GoF book in languages such as Ruby, Python or Clojure and the overall opinion is that in those languages, some of the problems these patterns solve in, say, Java, simply don’t exist.

Bayan decided to dig up a few and show what’s the alternative in Clojure. Interesting perspective.

Want more?

Join us on Google Groups, submit a talk proposal on the wiki and RSVP to the next meetup!

See you next time!

Project Euler: problem 4 in clojure

2012-02-05T13:29:00+11:00

I solved a few of the problems on Project Euler in the past, both in Java and Ruby, and thought it would be useful to redo them in Clojure, thus improving my skills on the language’s core functions and libraries. Today I’ll share problem 4.

Go ahead and read it but here’s the meat of it:

“Find the largest palindrome made from the product of two 3-digit numbers.”

From this statement we can tell two things: (1) we’ll need a function that can tell whether a number is a palindrome or not and (2) that the largest palindrome is given by the product of two numbers between 100 and 999, inclusive.

Let’s tackle number one first:

(defn palindrome? [n]
  (= (->> n str reverse (apply str))
     (str n)))

With our utility function in hand, one possible solution might be as follows:

(defn largest-palindrome []
  (apply max (filter #(palindrome? %)
                     (for [x (range 100 (inc 999))
                           y (range 100 (inc 999))]
                       (* x y)))))
(time
 (largest-palindrome))
;;"Elapsed time: 1405.358 msecs

While this works, I wasn’t happy with a couple of things in this solution. First, I thought I could do without using filter. Second, we have unnecessary multiplications going on, leading to poor performance - it takes ~1.4secs to finish.

You see, when we begin multiplying the numbers, we’ll see multiplications such as 100 * 100, 100 * 101, 100 * 102 … and then again, after the first loop is exhausted, 102 * 100, 102 * 101, 102 * 102 …

That led me to take a closer look at for, Clojure’s list comprehension macro. It’s a very powerful construct, providing 3 useful modifiers: let, while and when.

With that in mind, I refactored my first solution to look like this:

(defn largest-palindrome-1 []
  (apply max (for [x (range 100 1000)
                   y (range 100 1000)
                   :while (>= x y)
                   :let [z (* x y)]
                   :when (palindrome? z)]
               z)))

(time
 (largest-palindrome-1))
;;"Elapsed time: 689.262 msecs"

Here, the while modifier makes sure we aren’t wasting any time with unnecessary multiplications. The when modifier lets us get rid of the outer filter call. And as you can see, the solution is about twice as fast as its first version.

On top of that, it’s still pretty concise. Not bad.

Backlog: Ola Bini on Clojure/conj

2012-01-22T22:01:00+11:00

As I promised in my previous post, here are the highlights of what Ola Bini had to say about Clojure/conj.

Clojure/conj is the largest gathering of clojure programmers, hackers and enthusiasts, with a single track of talks spanning three days. Ola selected his favorite talks and summarised each one of them.

The actual slides for each one of the talks can be found on github.

You can find Ola’s slides here.

Fun Data Structures

This is certainly a very interesting topic. The highlight here is the approach Clojure takes to handling immutable data structures efficiently: persistent data structures through structural sharing - maybe a good short talk for the next meetup?

However, even though efficient, there are cases where the space complexity of known algorithms gets compromised. More specifically, algorithms that rely on the ability of changing data structures in-place - such as the QuickSort - will suffer from this approach.

I asked Ola about it and the short answer is that you should use a different algorithm that takes advantages of trees instead, since they often don’t rely on in-place changing.

The long answer is a book called Purely Functional Data Structures - another one added to my wish list.

Logic/constraint programming

This is a topic that’s completely new to me and it sounds fascinating at first. It also ended up being the topic of the rest of the tech night, with Ola, Sarah and Jo - also ThoughtWorkers - giving us a Logic Programming 101 crash course using Prolog. Lots to read up on.

In the Clojure world, logic programming can be achieved via core.logic.

The book The Reasoned Schemer was also mentioned as a good read on the subject.

Cascalog (github repo)

Haven’t had the time to play with it yet but it seems extremely useful. It’s a Clojure-based DSL for processing “Big Data” on top of Hadoop.

There you have it. Come join us for our next meeting!

Announcing the Sydney Clojure User Group

2012-01-20T11:35:00+11:00

Update: We now have a Meetup.com page. Head over there to learn about our next meetups as well as to RSVP to them. We’ll discontinue usage of the wiki for registering attendees, in favor of the new site. Everything else on this post however still holds.

If you’ve been following my blog, you’ll have noticed I started running internal Clojure meetups/hack nights at ThoughtWorks here in Sydney a while ago. While being closed, we’ve already had one international speaker - Ola Bini - come and share his experience as an attendee at Clojure/conj. I promise I’ll blog about it soon.

We’re a small but active group, eager to learn and as a natural result we couldn’t stay closed for any longer! :)

That’s why last Tuesday, the first time we had external guests, we decided to make the group public so anyone could join.

It was great having people from outside ThoughtWorks sharing their real world experience with Clojure. One of them, Harry Binnendijk from Whoto, even gave a presentation about how and why they’re using Clojure [1].

There was another talk, by yours truly, on Continuation Passing Style and Macros in Clojure. It was a great night.

Interested? Read on.

Our meetings will be held on the 3rd Tuesday of every month - at least to start with.

To help organize things we have a Google group where we’ll announce the next meetings, do the traditional “call for papers”, share ideas on how to improve our group, job posts and anything related to Clojure/FP.

We also have a wiki where you can see when and where the meetings are happening, sign up to talk/attend etc…

So if you’ve been thinking about learning Clojure but haven’t had the chance yet, come join us. Joining a group like this in its beginning is a perfect learning opportunity.

And if you’re a Clojure hacker already, we’d love to hear from you just as much!

We welcome all levels and encourage everyone to submit talks they’re passionate about.

I hope to see you in the next meet up. Feel free to shoot the group an email or to me directly at leonardoborges(dot)rj(at)gmail(dot)com

And don’t forget to add us to your calendar so you don’t miss out - next meetup will be on Feb 21st at ThoughtWorks Sydney!

[1] Link to the presentation will be available soon

So long 2011: Year highlights

2012-01-01T16:20:00+11:00

It’s that time of the year to look back at what you’ve done and either be happy about it or… well not. :)

To me anyway 2011 was a great year but I won’t bore you with the details so I’ll just jump straight into a couple of highlights!

The biggest one of course was the project we developed to help the Queensland flood victims back in January - which brings me to the next topic:

Speaking

Said project gave me the chance to speak at a few events, sharing this and other great stories:

Ruby On Rails Oceania User Group - Sydney - February (slides | video)
CloudCamp - Sydney - July (slides)
XConf (1) Australia - Melbourne - August
RubyConf Brazil - Sao Paulo - November (slides | video)

(1) - XConf is an internal technical conference here at ThoughtWorks

Content

Here in the blog, these are a few of the most popular articles for 2011:

Why I Like Ruby #1: Alias_method - This one still surprises me. It’s been at the top for a while
IDE Review: RubyMine
Clouds against the Floods
One Year of ThoughtWorks: A Retrospective

Languages

I decided to learn Clojure and started an internal user group at ThoughtWorks Sydney - you can read a brief report on our first meetup here.

The group’s been a bit off lately since I was on leave in Brazil and then the whole holiday season happened but it’s definitely one of the things I want to make happen more often in the new year.

Clojure is a great language and I expect it to keep gaining a lot of traction in 2012.

And I guess that’s it…

A lot more happened in the last 12 months but these are definitely my favourite parts.

Happy new year everyone! I’m sure 2012 has a lot of new challenges and surprises for us :D

Help Keep RottingNames On The Appstore

2011-12-07T00:00:00+11:00

A year ago I decided to try my hand on iPhone software development and created a very simple application to experience the whole lifecycle of putting a complete project on the Apple AppStore - I wrote about it a while back.

The result was RottingNames, a heavy metal band name generator.

Since then, I haven’t developed anything else for the iPhone - mostly because my interest lies elsewhere now - but I did notice a small yet steady amount of downloads for this cool little app.

You can download RottingNames for free from the App Store and I like keeping it that way.

However, to be able to put an application on the AppStore, Apple charges an annual fee of A$99 - even if the application itself is free.

I had decided not to renew my iOS Developer Program membership but it seems a pity to let RottingNames vanish like this. Es pecially knowing there are a few die-hard fans out there having a good laugh with it.

Here’s the deal: I’m asking for A$99 in order to renew the membership.

In return, RottingNames will stay on the AppStore for another year, for free.

So hit the button below and stay metal! \m/

RubyConf Brazil 2011

2011-11-10T00:00:00+11:00

I was in São Paulo last week - the 3rd and 4th of November - for RubyConf Brazil. For those who don’t know, RubyConf Brazil is the evolution of Rails Summit Latin America, where I had the privilege to speak in 2009.

This year though, all bets were off. Fabio Akita and Locaweb put together a great event, with over 700 attendees and about 30 speakers split in two streams and two awesome days.

Once more I had the chance to speak at the event and different from previous years, all talks were recorded and streamed live! You can check mine - in portuguese - here as well as my slides - in english - on slideshare.

All other talks can be watched from the eventials’ RubyConf Brazil page. Locaweb has also published the official Flickr album of the event.

It was great to meet up with great friends again as well as to meet amazing new people such as the guys from ThoughtWorks Brazil. I promise I’ll make the detour next time! :)

I hope to see you all again soon!