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?

See also