Tuesday, May 28, 2013

Bugs on a board - modern concurrency in Clojure

[ Inspired by Rick Hickey's Ant Colony Simulation ]
Having said before that Clojure is great, I feel obliged to provide a concrete example of a concurrent Clojure program. We will implement a simulation of N bugs walking randomly on an X x Y board. If two bugs walk onto the same cell, they both vanish. Let's start!

The board has dimensions specified as follows:

(def dimx 50)
(def dimy 50)

A bug performs one step from the current cell by randomly altering its (x,y) coordinates. Each coordinate is incremented or decremented by 1, or it stays the same.

(defn random-step [n]
  (let [step (rand-int 3)]
    (cond (= step 2) (dec n)
      (= step 1) (inc n)
      (= step 0) n)))

Next location for a bug will be randomly generated, unless a bug is at a border. In that case, it immediately jumps in the opposite direction.

(defn next-loc [loc]
(let [x (loc 0) y (loc 1)
      newx (cond (= x (dec dimx)) (dec x)
                 (= x 0) (inc x)
                 :else (random-step x))
      newy (cond (= y (dec dimy)) (dec y)
                 (= y 0) (inc y)
                 :else (random-step y))]
   [newx newy]))

Unique initial locations for bugs are generated at the start using this function:

(defn initial-locs [locs numof]
(if (= numof 0) locs
  (let [x (rand-int dimx) y (rand-int dimy)]
    (if (not-any? (fn [loc] (and (= x (loc 0)) (= y (loc 1)))) locs)
      (initial-locs (conj locs [x y]) (dec numof))
      (initial-locs locs numof)))))

We will initially have 20 bugs at 20 different locations:

(def init-locs (initial-locs [] 20))

Our simulated world will be a hashtable of agents (later we will see that the bugs are agents).

(defn init-world [w agent-list]
  (if (empty? agent-list) w
    (init-world (assoc w @(first agent-list) (first agent-list)) (rest agent-list))))

We create a list of bugs (agents) and  the world:

(def bugs (map #(agent %) init-locs))
(def world (atom (init-world {} bugs)))

We need a function that updates the world, given the world, old bug location, new bug location and bug alias. The function will also detect if the moving bug ends up at a cell occupied by another bug - in this case both need to be removed from the world.

(defn upd-world [world-map old-loc new-loc agent-alias]
  (= nil (world-map old-loc)) world-map
  (or (identical? agent-alias (world-map new-loc))
      (= nil (world-map new-loc)))
    (let [foo (dissoc world-map old-loc)]
      (assoc foo new-loc agent-alias))
    (let [foo (dissoc world-map old-loc)]
      (dissoc foo new-loc))))

We also need a function that directs the crawl of a bug. It will update the world upon each step.

(defn crawl [loc]
(if (= nil (@world loc)) loc
    (Thread/sleep 50)
    (send *agent* crawl)
    (let [newloc (next-loc loc)]
      (swap! world upd-world loc newloc *agent*)

Now we need some GUI stuff. Bugs will be represented as squares. Let's define bug size in pixels.

(def bugsize 5)

Import some useful GUI components:

(import [javax.swing JPanel JFrame])

(import [java.awt Color Dimension])

'Now the function for creating the frame:

(defn create-frame [panel]
(let [frame (JFrame.)]
(doto frame
  (.add panel)
  (.setVisible true)

And the main function for rendering the world:

(defn render [g]
  (.setColor g Color/white)
  (.fillRect g 0 0 (* bugsize dimx) (* bugsize dimy))
  (.setColor g Color/black)
  (doseq [k (vec (keys @world))]
    (if (@world k) (.fillRect g (* bugsize (k 0)) (* bugsize (k 1))
      bugsize bugsize)))))

One more GUI function:

(defn create-panel []
(let [panel (proxy [JPanel] []
  (paint [g]
    (render g)))]
(doto panel
  (.setPreferredSize (Dimension. (* bugsize dimx) (* bugsize dimy))))))

And we are really close - just initialize the GUI:

(def panel (create-panel))
(def frame (create-frame panel))

Define the animation agent that will repaint the frame periodically:

(def anim (agent nil))
(defn animate [x]
(when (> (count @world) 1)
    (Thread/sleep 10)
  (send-off *agent* animate)
  (.repaint panel)
  (.validate panel)))
(send-off anim animate)

And send the crawl function to all the bugs:

(dorun (map #(send-off % crawl) bugs))

That's it! Do Copy&Paste, remove my comments, download the latest Clojure jar from clojure.org and start it:

java -jar clojure.jar

And from the Clojure REPL load the file containing the program:

(load-file 'bugs.clj')

This program is 96 lines long, including some empty newlines. This is an example of the expressive power of Clojure. It doesn't contain any locking, mutexes or semaphore handling code. All thread coordination is implemented using STM. So, comparing it to what it would take to implement the same thing in one of the more popular languages, what do you say?

Friday, May 24, 2013

Code Kata: shopping list search

We have a list of, let's say, goods we bought at a shop (or you can imagine any other list that you like):

|        Name        |      Quantity      |       Price      |
|        Beer          |           10          |        30            |
|       Pickles        |           1           |        12            |
|     Red beans    |            2           |        22            |

The task is to write a piece of code that will search through the list and will display each row that matches search criteria. Too simple? Maybe. But consider these additional hints:
  • search criteria may not be exact. The string "bean" might match "Red beans"
  • we may even be searching for any of a few items: rows one and three will both match if our search criteria are "any of 'beer', 'bean' ".
I recommend that you start this kata with an exact search for one item and then gradually move towards the "like/contains" criteria and to "any of" criteria and that you observe the impact these changes will have on your unit tests (needless to say, this should all be done using TDD).

Monday, May 6, 2013

Do I really have to call super(...).__init__ in Python?

Yes. But, if you prefer a longer answer:

Class B inherits from class A. When implementing B's __init__ function, we may call A's init by writing:

super(B, self).__init__(arguments of A's __init__)

Is it really necessary? After all, in C++ or Java the constructor of base class is called automatically, so shouldn't it be called automatically in Python as well?

The point is that __init__ is not a constructor. Python objects are constructed with __new__. __init__ is used to initialize an object with concrete values, either defaults or passed as __init__'s parameters.

Need more details? Read Python docs at http://docs.python.org/2/reference/datamodel.html#object.__new__

See also