Wednesday 31 December 2008

Visualizing Bubble Sort


So I finally finished my rubbish sort visualization. It was more about learning a bit of Clojure interacting with Swing.

The code certainly isn't the prettiest, but it is very concise compared how it'd look in Java. The canvas does the drawing, using proxy to provide implementations of the paintComponent and listen to tick events from the timer.

The bubble-sort function returns a list which represents each intermediate stage of the bubble sort algorithm (well, it's not quite perfect as it includes all the swaps, not one at a time).

An atom is used to represent the mutable state (in this case, a counter which moves between 0 and the number of items in the list).

The full code is available in my Git repository here.

Tuesday 30 December 2008

Mutants!

Part of the rationale of Clojure is to get rid of free-for-all mutation: "for the concurrent programming future, pervasive, unmoderated mutation simply has to go."

Atoms are a way of performing mutation in a safe way, free from any potential race conditions.

An atom is associated with a Clojure value, in this case an integer.


(def position (atom 0))


If you want to observe the value, use deref or the @ notation.


user> (prn @position)
0
nil
user> (prn position)
#
nil
user> (prn (deref position))
0
nil


So how do you actually change the value inside the atom? swap! and compare-and-set! change the values of atoms. Both have the ! (bang) suffix to indicate that they are destructive operations.

swap! takes two arguments, the atom itself and a function to apply to the value and swap with the current value of the atom. For example:


user> (swap! position inc)
1
user> (swap! position inc)
2


compare-and-set! (CAS)is a lower level function which sets the value of an atom given the original value and the new. The value is only changed if it is observed first to be equal to the original value. A Boolean return value indicates whether the atom was changed.


user> (swap! position (fn [x] 0))
0
user> (compare-and-set! position 0 1)
true
user> (compare-and-set! position 0 2)
false


I'll use atoms to change state when animating my little sorting visualization.

Monday 29 December 2008

Clojure short-hand

After reading through some Clojure code and talking to people on IRC, I found a few ways of making code a bit more concise.

#(+ %1 %2) is short hand for (fn [x y] (+ x y)). For example, this is valid:


user> (map #(+ %1 %2) (range 0 4 ) (range 0 4))
(0 2 4 6)


Documentation for this is squirreled away on the Clojure Reader page.

Another useful function I didn't know was into which allows you to create a new data structure from an existing one. When you create literal sets, the reader creates hash types (i.e. unordered).


user> #{1 2 3 4 5 6 7 98 100}
#{1 2 98 3 4 100 5 6 7} ;; look the ordering has changed.


Using into, I can change that:


user> (into (sorted-set) #{1 2 3 4 5 6 7 98 100})
#{1 2 3 4 5 6 7 98 100}


Going back to my sort app, based on the Snake game code previously mentioned, it seems to get a drawing panel I should subclass a JPanel and override the paint method to get a canvas to draw on.



(def maxval 100)

(def model (take 100 (repeatedly (fn [] (rand-int maxval)))))

(def canvas (proxy [JPanel ActionListener] []
(paintComponent [g]
(proxy-super paintComponent g)
(.setColor g Color/RED)
(let [width (.getWidth this) height (.getHeight this) barHeight (/ height (inc (count model))) barWidthPerVal (/ width maxval)]
(prn width height)
(doseq [val (into (sorted-map) (zipmap (range 0 (count model)) model))]
(let [y (int (* (first val) barHeight)) barWidth (int (* (second val) barWidthPerVal))]
(.fillRect g 0 y barWidth barHeight)))))
(actionPerformed [e] (prn "Doing something"))))


this is still a keyword in Clojure, which is something that took me a while to work out, I guess I was hoping that I could do (.getHeight) and the this would be explicit?

proxy (as I've briefly mentioned before) allows you to override methods and implement interfaces. In this case I've overridden the painComponent method of JPanel and replaced it with some gubbins to draw the list I'm trying to sort.

I've also overridden the actionPerformed method which is where I'll mutate the model with one iteration of the chosen sort method. I've decided (again based on the Snake Clojure code) to use a Swing Timer to fire events to signal when to redraw.

On a side note, encapsulating an object behind functions is nice and simple. In the style of SICP we use a local let expression to hide x from the outside world.


(let [x (Timer. 1000 canvas)]
(defn stop-timer [] (.stop x))
(defn start-timer [] (.start x))
(defn is-running [] (.isRunning x)))


Now all I need to write in my daft demo app is a way of generating all the intermediate steps for sorting algorithms. For my implementation of bubble-sort this is simple (it generates a list of the intermediate bits and pieces), but for quick sort it's little bit harder.

Saturday 27 December 2008

Building a GUI with Clojure



Well, that's my most rubbish UI ever, but at least it gave me a chance to learn a few things. Starting from the example, I made a few very simple changes and ended up with the rubbish one above....

I'm still not fulling groking exactly how "real" applications are designed in a functional programming language. For example, in this daft app what should the separation of concerns be? Does MVC have a functional counterpart?

Next on this list is changing the code (prn alg) to actually render what's going on with quicksort and bubble sort.



(import '(javax.swing JFrame JLabel JTextField JButton JComboBox JPanel Timer)
'(java.awt.event ActionListener)
'(java.awt GridLayout))

(defn draw-sort [canvas alg]
(prn alg))

(defn sortapp []
(let [frame (JFrame. "Sort Visualizer")
canvas (JPanel. true)
algorithm-chooser (JComboBox.)
run-button (JButton. "Run Algorithm")]
(.addActionListener run-button
(proxy [ActionListener] []
(actionPerformed [evt]
(draw-sort canvas (.toString (.getSelectedItem algorithm-chooser))))))
(doto algorithm-chooser
(.addItem "Quick sort")
(.addItem "Bubble sort"))
(doto frame
(.setLayout (GridLayout. 2 2 3 3))
(.add algorithm-chooser)
(.add canvas)
(.add run-button)
(.setSize 300 300)
(.setVisible true))))


Things I have learnt:

  • doto syntax saves lots of repetition!
  • proxy is used to generate implementations of interfaces dynamically


Things I need to find out:

  • What's the idiomatic way of drawing something on the screen? Do I need to be using timers? Probably!

Friday 26 December 2008

Bubbling Clojure

There's quite a few sorting algorithms around. I wanted to do something similar to Sorting Algorithms, only in Clojure + Swing as some kind of learning exercise. (99 Problems is still on-going, but to be honest it's boring (!) I'll reach the end one day...).

Perhaps the simplest is bubble sort, go through the list and if you find two adjacent items out of order, swap them. Repeat until done.


(defn bubble [lst]
(if (or (nil? lst) (nil? (second lst)))
lst
(if (> (first lst) (second lst))
(cons (second lst) (cons (first lst) (nthrest lst 2)))
(lazy-cons (first lst) (bubble (rest lst))))))

(defn bubble-sort [lst]
(if (= (bubble lst) lst)
lst
(recur (bubble lst))))


I couldn't find a neater way of doing it. An alternative is to use iterate to apply bubble until no more swaps are necessary. This at least makes the time complexity pretty obvious.


(defn bubble-sort [lst]
(last (take (* (count lst) (count lst)) (iterate bubble lst))))


We can simplify this further. The bubble function sucks because it only applies a single swap and then just rebuilds up the sequence. Applying the function as we go up we get:


(defn bubble [lst]
(if (or (nil? lst) (nil? (second lst)))
lst
(if (> (first lst) (second lst))
(cons (second lst) (lazy-cons (first lst) (bubble (nthrest lst 2))))
(lazy-cons (first lst) (bubble (rest lst))))))


Quicksort is a much better algorithm. The algorithm is:

  • Pick a pivot X

  • Move all items less than the pivot to the left and all greater to the right

  • Apply recursively to each side



This has a very simple implementation in Clojure


(defn qsort [lst]
(if (nil? lst)
lst
(concat
(qsort (filter (partial > (first lst)) (rest lst)))
(list (first lst))
(qsort (filter (partial <= (first lst)) (rest lst))))))


How do the two compare?

First I needed to find out how to generate a big random sequence. repeatedly applies a function of no arguments and generates an infinite list. Using repeatedly and take, you can get a list of random elements like this:


(take 500 (repeatedly (fn [] (rand-int 100)))


So now I can compare the two:


user> (time (count (bubble-sort (take 1000 (repeatedly (fn [] (rand-int 100)))))))
"Elapsed time: 575.713898 msecs"
1000
user> (time (count (qsort (take 1000 (repeatedly (fn [] (rand-int 100)))))))
"Elapsed time: 38.933079 msecs"
1000


Things I still need to work out:

  • Why does my bubble sort implementation blow the stack with large lists? Shouldn't the laziness mean it shouldn't? last looks daft, replace with take/drop combo
  • Multiple return values (or faking them). It'd be nice to stop swapping in the bubble sort when no swaps are done. Clojure doesn't support multiple return values (for compatibility with Java)


Things I have learnt:

  • Iterate is a cool function

Tuesday 23 December 2008

Sieve of Eratosthenes

The Sieve of Eratosthenes is an algorithm for calculating all the prime numbers up to a given value.

In Clojure a naive sieve algorithm might look a little like this:


(defn isprime [p]
(and (> p 1)
(every? (fn [x] (not (zero? (rem p x)))) (range 2 (inc (Math/sqrt p))))))

(defn sieve [x]
(filter isprime (range 1 x)))


A number X is prime if it is only divisible by itself and items in the range 2 to Sqrt( X ). We can then apply the filter function.

We can use this in the REPL and see that it's suprisingly fast:


user> (time (count (sieve 1000)))
"Elapsed time: 1.18792 msecs"
167

user> (time (count (sieve 1000000)))
"Elapsed time: 7990.35914 msecs"
78497


This isn't in fact the Sieve algorithm at all. We recalculate the primes each time so calculating the next prime doesn't take into account the previous ones...

The Genuine Sieve of Eratosthenes (also discussed at LtU) gives some ideas on how to get it going faster...

Monday 22 December 2008

99 Problems in Lisp (Part VIII)

P26 - Generating the combinations of K distinct objects chosen from N.


(defn append-prefix [prefix lst-elements]
(mapcat (fn [x] (list (concat prefix (list x)))) lst-elements))

(defn combination [n lst]
(if (> n (count lst))
nil
(let [elem-list (split lst (dec n)) rlist (nthrest lst (dec n))]
(concat (append-prefix (first elem-list) rlist) (combination n (rest lst))))))


Only two left and I've done the lists part....

Sunday 21 December 2008

99 Problems in Lisp (Part VII)

P23 - Extract a given number of randomly selected elements from a list. This is daft looking because the previously defined remove-at function is one based!

(defn rnd-select [lst n]
(when (> n 0)
(let [x (rand-int (count lst))]
(lazy-cons (nth lst x) (rnd-select (remove-at lst (inc x)) (dec n))))))


P24 Select N different frombers from the set 1..m

(defn lotto-select [n rng]
(rnd-select (range 1 rng) n))


P25 Permute a list

(defn rnd-permu [lst]
(let [length (count lst)]
(when (> length 0)
(let [x (rand-int length)]
(lazy-cons (nth lst x) (rnd-permu (remove-at lst (inc x))))))))

Saturday 20 December 2008

Improving my Clojure style

P22 on my list of problems seems simple, "Create a list containing all integers within a given range.". My first naive (a polite way of saying crap!) implementation is shown below:


(defn my-range-crap [start end]
((fn [x y accum]
(if (= x y)
(concat accum (list x))
(recur (inc x) y (concat accum (list x))))) start end nil))


The pattern (concat accum (list x)) is very ugly. There's a much simpler way of doing that using conj. From the documentation.

(conj coll item)
Conj[oin]. Returns a new collection with the item 'added'. (conj nil item) returns (item). The 'addition' may happen at different 'places' depending on the concrete type.



Much better, so now I can do:


(defn my-range-not-quite-as-crap [start end]
((fn [x y accum]
(if (= x y)
(conj accum x)
(recur (inc x) y (conj accum x)))) start end nil))


Incidentally, this fixes another issue. If I'm using concat then (my-range-crap 1 50000) blows the stack. Not good. Using conj fixes the problem.

Talking on #Clojure, I got a much better solution from kotarak + poiuyt


(defn much-better-range
[start end]
(when (< start end)
(lazy-cons start (much-better-range (inc start) end))))


Much more concise!

Using lazy-cons means the recursion can be explicit and that you get rid of the problems with stack overflow (it only evaluates when you need it).

99 Problems in Lisp (Part VI)

P19 Rotate a list N places to the left

(defn rotate [lst n]
(if (> n 0)
(take (count lst) (drop n (cycle lst)))
(take (count lst) (drop (- (count lst) (Math/abs n)) (cycle lst)))))


P20 Remove the kth element from the list

(defn remove-at [lst n]
(concat (take (dec n) lst) (drop n lst)))


P21 - Insert an element at a given position into a list

(defn insert-at [lst elt n]
(concat (take (dec n) lst) (list elt) (drop (dec n) lst)))

99 Problems in Lisp (Part V)

I think that the style I have of using recur is probably very wrong. concat must be O(N) (since the only way to get to the end of the list is to walk it). I'm making N calls to it, so most of the code I've written is probably O(N^2).


P13 encode it directly

(defn encode-direct [lst]
((fn [xs accum]
(if (= nil xs)
accum
(recur (drop-while (fn [x] (= x (first xs))) xs)
(let [items (take-while (fn [x] (= x (first xs))) xs)]
(if (= 1 (count items))
(concat accum items)
(concat accum (list (list (count items) (first items))))))))) lst nil))


P14 Duplicate the elements of a list

(defn dupli [lst]
(mapcat (fn [x] (list x x)) lst))


P15 Replicate the elements of a list a given number of times

(defn repli [lst n]
(mapcat (fn [x] (replicate n x)) lst))


P16 Drop every nth element from a list

(defn drop-nth [lst n]
((fn [xs i accum]
(if (= nil xs)
accum
(if (= 0 (rem i n))
(recur (rest xs) (inc i) accum)
(recur (rest xs) (inc i) (concat accum (list (first xs))))))) lst 1 nil))


P17 split a list into two parts

(defn split [lst n]
(list (take n lst) (drop n lst)))


P18 extract a slice from a list

(defn slice [lst i n]
(take (inc (- n i)) (drop (dec i) lst)))

Friday 19 December 2008

Using Git to store code

I decided I should set myself up some version control software as I sporadically do really stupid crap (well, not even sure about the sporadic bit!).

Git is all the rage these days. It's a distributed revision control system, so you have both a local and remote repository. Not exactly sure what I@m doing at the moment, but the cheat sheet is helping!

GitHub provides free hosting and allows you to use git. So, I created something to dump this Clojure code. See here

And a new release of Clojure today too...

Thursday 18 December 2008

99 Problems in Lisp (Part IV)

P11 - Modified Run length encoding

(defn encode-modified [lst]
((fn [xs accum]
(if (= nil xs)
accum
(recur (rest xs)
(concat accum
(list
(if (= (count (first xs)) 1)
(ffirst xs)
(list (count (first xs)) (ffirst xs)))))))) (pack-list lst) nil))


P12 - Decode a run length encoding list


(defn decode [lst]
((fn [xs accum]
(if (= nil xs)
accum
(recur (rest xs)
(if (list? (first xs))
(concat accum (replicate (ffirst xs) (first (rfirst xs))))
(concat accum (list (first xs))))))) lst nil))

Wednesday 17 December 2008

99 Problems in Lisp (Part III)

So, onwards with spending a few minutes each day working my way through a random list of puzzles...

P08 - Eliminate consecutive duplicates of list elements


;; Ugly style
(defn eliminate-dupes [lst]
((fn [n last accum]
(if (= nil n)
accum
(if (= (first n) last)
(recur (rest n) last accum)
(recur (rest n) (first n) (concat accum (list (first n))))))) lst nil '()))

;; Nicer functional style
(defn eliminate-dupes2 [lst]
((fn [n accum]
(if (= nil n)
accum
(recur (drop-while (fn [x] (= x (first n))) n)
(concat accum (list (first n)))))) lst nil))



drop-while and take-while are functions that read from a (potentially) infinite sequence and either take or drop elements based on a predicate. They are (obviously) lazily evaluated!

P09 - Pack consecutive duplicates of list elements into sublists


;; P09 - pack consecutive duplicates of list elements into sublists
;; TODO should really use an accumulator
(defn pack-list [lst]
(if (= lst nil)
nil
(cons (take-while (fn [x] (= x (first lst))) lst)
(pack-list (drop-while (fn [x] (= x (first lst))) lst)))))

(defn pack-list2 [lst]
((fn [xs accum]
(if (= xs nil)
accum
(recur (drop-while (fn [x] (= x (first xs))) xs)
(concat accum (list (take-while (fn [x] (= x (first xs))) xs)))))) lst nil))


The transformation from non tail recursive, to tail recursive + accumulator is very formulaic. A quick search led me to LtU and in turn to LLVM.

LLVM is a low level virtual machine (doesn't provide GC / type system etc). It provides a framework for allowing optimizations to be generated and amongst these are including tail call optimization and transform. See the demo. Unfortunately, until it's possible to guarantee that this optimization is performed, you have to assume the worst and right code with explicit accumulators. Ho-hum!

P10 - Run length encoding of sublists


(defn encode [lst]
((fn [xs accum]
(if (= nil xs)
accum
(recur (rest xs) (concat accum (list (list (count (first xs)) (ffirst xs))))))) (pack-list lst) nil))


count was a difficult one to find - it returns the length of a sequence, also works on strings, arrays and Java collections.

doc is an amazingly useful function that returns the documentation string associated with a function e.g.


user> (doc count)
-------------------------
clojure.core/count
([coll])
Returns the number of items in the collection. (count nil) returns
0. Also works on strings, arrays, and Java Collections and Maps
nil

Monday 15 December 2008

99 Problems in Lisp (Part II)

P06 - Find out whether a list is a palindrome?


(defn palindrome? [x]
(= x (reverse x)))


P07 -Flatten a nested list structure.


(defn atom? [x]
(or (nil? x) (not (seq? x))))

;; Not tail recursive and generally makes me feel sick that I've even typed
;; such a monstrosity!
(defn my-flatten [list]
(if (atom? list)
list
(if (atom? (first list))
(cons (first list) (my-flatten (rest list)))
(concat (my-flatten (first list)) (my-flatten (rest list))))))


The above feels yucky! Using the example from the Haskell puzzles we can come up with a much cleaner solution.

How'd you flatten a list? If it's an atom then we're done (list x), whereas if it's a list then we want to flatten each element in turn (mapcat my-flatten2 x). This makes a really simple definition as below:


(defn my-flatten2 [x]
(if (atom? x)
(list x)
(mapcat my-flatten2 x)))


mapcat is similar to the map function but collects all of the items together with concatenation. It takes a function and a series of lists as arguments, for example:


user> (mapcat (fn [x y] (list (+ x y))) '(1 2 3) '(3 4 5))
(4 6 8)

99 Problems in Lisp

Since the only way to get up to speed with a programming language is to actually use it, thought I'd work my way through 99 Problems in Lisp, only in Clojure.

Obviously, these are probably daft implementations, so any improvements welcome. Anyways, on with the problems. Instead of using recursion, I've tried to always go for recur since calling functions directly always runs the risk of running out of stack space. This actually "feels" surprisingly clean, no more repeating function names in bodies. Odd

P01 - Find the last item in a list

(defn last-in-list [x]
((fn [x last]
(if (nil? x)
last
(recur (rest x) (first x)))) x nil))


P02 - Find the last but one in a list

(defn last-but-one-in-list [x]
((fn [x last]
(if (nil? (rest (rest x)))
last
(recur (rest x) (first (rest x))))) x nil))


P03 - Find the K'th element of a list

(defn element-at [x n]
(if (= n 0)
(first x)
(recur (rest x) (dec n))))


P04 - Find the length of a list

(defn length [x]
((fn [x acc]
(if (nil? x)
acc
(recur (rest x) (inc acc)))) x 0))


P05 - Reverse a list

(defn my-reverse [x]
((fn [list acc]
(if (nil? list)
acc
(recur (rest list) (cons (first list) acc)))) x nil))

Sunday 14 December 2008

Recursion in Clojure

How do you write functions that don't explode the stack if Clojure doesn't have TCO?

Let's start with a bad definition of factorial:


(defn factorial [x]
(if (= x 0)
1
(* x (factorial (- x 1)))))


Using it in the REPL is fine:


user> (factorial 100)
933262154439441526816992388562667004907
159682643816214685929638952175999932299
156089414639761565182862536979208272237
582511852109168640000000000000000000000
00


Up to a point...


user> (factorial 100000)
; Evaluation aborted
java.lang.StackOverflowError (NO_SOURCE_FILE:0)
[Thrown class clojure.lang.Compiler$CompilerException]

Restarts:
0: [ABORT] Return to SLIME's top level.
1: [CAUSE] Throw cause of this exception


This is barfing because the evaluator has to keep around state for each call due to the expression (* x (factorial (- x 1))) . We need to make this function tail recursive.

recur can be thought of as the Clojure operator for looping. Think of it like a function call for the nearest enclosing let or function definition supplied with new variables. Naively we can switch over to using this by doing:


user> (defn factorial2 [x]
(if (= x 0)
1
(* x (recur (- x 1)))))


But this is a compile-time error (which in itself is pretty neat!).


java.lang.UnsupportedOperationException: Can only recur from tail position (NO_SOURCE_FILE:4)


An accumulator parameter is an extra parameter to a function that's used to gather intermediate parts of the calculation. If we do this, we can make sure that the recur call is in the tail position. Using an anonymous function we get:

(defn factorial3 [x]
((fn [x y]
(if (= x 0)
y
(recur (- x 1) (* x y)))) x 1))


Now when recur is used, it doesn't need to keep any of the previous stack frame around. This means we can finally calculate factorial 1000000, which begins with 282 and ends with lots of zeros!

Thursday 11 December 2008

Clojure Videos

There's some great Clojure video online at Blip.TV. I started watching Clojure for Lisp Programmers. The following are brief notes on this.

Clojure was designed for concurrency and also targeted specifically at the Java Virtual Machine. Apparently it's OK to hate Java, but like the virtual machine. Clojure is a "language as platform" implementation rather than language + platform. This gives the benefits that you get lots of stuff for free (e.g. the virtual machine, garbage collection, byte code generation, JIT compilation etc). Compare this to most Lisp implementations where you have to build this yourself and Clojure's off to a good start!

The focus is on concurrency because we're approaching the limit of single-core speed ups (whether that's actually true or not is debatable, but certainly Intel and AMD seem to be pushing us to a multi-core future). As has been said many times before functional programming is ideally suited for concurrency - no shared state hugely simplifies things. However, Clojure isn't a pure language like Haskell; if you need to get "dirty" and modify state you can.

Clojure is not object-oriented because it encourages mutable state. "Mutable stateful objects are the new spaghetti code" was a great quote! Object-oriented polymorphism is very restrictive, CLOS has shown how useful basing it on multiple types can be, but can also base it on values, current state, relationships etc.

Clojure is a different kind of lisp for several reasons:
* First class support for sets, maps, lists and vectors (first class meaning Lisp reader support for example)
* Abstractions (all containers defined as seq interface)
* Thread aware
* Host embracing (e.g. tightly tied to the JVM)
* Not constrained by backwards compatability.

In compared to other Lisp's:
* Clojure is a lexically scoped Lisp1
* Common Lisp style macros and dynamic vars
* Dynamically compiled to JVM byte code
* No tail call optimization

In the video, Rich Hickey discussed the recent JVM summit and his (and most other attendees) hopes for getting support for TCO in the JVM. However according to a recent article support it not coming in Java 7. Worst yet, if Java 7 is 2010 then we've a long wait till Java 8!

One of the fundamental differences between Lisp and Clojure is that Lisp doesn't have the cons cell as the primary building block. Instead of a concrete implementation for lists, Clojure is based on the simple abstraction of first and rest. The seq interface is common across all containers (list,map,set,vector,string,regex matches,files etc). (seq x) will give you an available sequence interface from x. (conj x 6) will append a six on the end of any sequence.

Lazy seqs is also possible using the lazy-cons macro. As an example, take (which returns the first n values of a potentially infinite collection), can be defined as:


(defn take [n coll]
(when (and (pos? n) (seq coll)) ;pos? positive number
(lazy-cons (first coll)
(take (dec n) (rest coll)))))


From the brief look of the video, the standard library has lots of neat little functions e.g.


(drop 2 [1 2 3 4]) ; (3 4)
(take 9 (cycle [1 2 3 4])) ; (1 2 3 4 1 2 3 4 1)
(interleave [:a :b :c :d :e] [1 2 3 4 5]) ;(:a 1 :b 2 :c 3 :d 4 :e 5)
(partition 3 [1 2 3 4 5 6]) ; ((1 2 3) (4 5 6))
(map vector [:a :b :c] [1 2 3]) ; ([:a 1] [:b 2] [:c 3])
(apply str (interpose \, "asdf")) ; "a,s,d,f"
(reduce + (range 100)) ; 4950


And I'm only an hour into the video before work has to kick in :(

Monday 8 December 2008

Passing functions around in Clojure

fn is the Clojure equivalent of lambda from Lisp.


(fn [x] (+ x 1)) ; #
((fn [x] (+ x 1)) 7) ; 8


These work as you'd expect when you pass them to functions such as map


(map (fn [x] (+ x 1)) (list 1 2 3 4)) ; (2 3 4 5)
(defn adder [x] (+ x 1)) ; #'user/adder
(map #'adder (list 1 2 3 4) ; (2 3 4 5)


Sharp quote (#') works same as it does in Lisp it appears.

Clojure Java Interop

Use the "/" notation to call static methods


(Math/pow 2 3) ; 8
(Integer/toBinaryString 10) ; "1010"

;; not good style!
(. Integer toBinaryString 10) ; legal syntax but / operator preferred for clarity!


Use the "." operator to call instance methods


(. "shoes" length) ; 5
(. "1234abcd" substring 0 4) ; "1234

Sunday 7 December 2008

Five minutes with Clojure

After setting things up I had a spare five minutes to actually try some Clojure. Most frustrating thing so far is the lack of decent error messages. For example, getting messages like below isn't that helpful to me at the moment!


java.lang.IllegalArgumentException: Don't know how to create ISeq from: Integer (NO_SOURCE_FILE:1)
[Thrown class clojure.lang.Compiler$CompilerException]

Restarts:
0: [ABORT] Return to SLIME's top level.
1: [CAUSE] Throw cause of this exception

Backtrace:
;;; snip


First class support for more data structures than Lisp is great. There's Set, Map and Vector represented by the syntax below.


'(a b c) ; list
['a 'b 'c] ; vector
{:a 1 :b 2 :c 3} ; map
#{:a :b :c} ; set


I'm still a little confused with some of the syntax, for example with the latest version from SVN the following happens


'(a b c) ==> (a b c)
('a 'b 'c) ==> c


Odd. Wonder why that is? a is a symbol bound to a function that apparently returns its first or second argument if it has 1 or 2 args. It's not defined for more arguments. Weird.

For declaring functions, you don't use defun. Instead you can use fn to create a function, for example (shamelessly stolen from Practical Common Lisp)


(def make-cd (fn [title artist rating] (list title artist rating)))
(make-cd "Technology Sucks" "AC" 1) ==> ("Technology Sucks" "AC" 1)


You can simplify the above definition using the defn macro.


(defn make-cd [title artist rating] (list title artist rating))


macroexpand-1 shows that this expands into the above. defn allows you to provide some overloads. I couldn't think of a good example, but the syntax is pretty simple, just a list of forms.


(defn crazy-function
([x] (list 42))
([x y] (list (+ x y)))
([x y &more] (list y)))

(crazy-function 7) ==> 42
(crazy-function 7 11) ==> 18
(crazy-function 1 2 3 4 5) ==> 2

Clojure + Slime

Following the Bill Clementson's guide http://bc.tech.coop/blog/081205.html I was able to get Clojure + Slime playing together happily.

Now all I need to do is find the time to learn it....