Przejdź do głównej zawartości

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]
(cond
  (= 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))
  :else
    (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
  (do
    (Thread/sleep 50)
    (send *agent* crawl)
    (let [newloc (next-loc loc)]
      (swap! world upd-world loc newloc *agent*)
      newloc))))



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)
  (.pack)
  (.show))))

And the main function for rendering the world:

(defn render [g]
(do
  (.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?

Komentarze

Popularne posty z tego bloga

Unit Testing code with IO file operations (in Python)

We may often come across a piece of code that was written without Unit Tests at all. In addition, the piece of code may be dealing with IO like file writing and reading, which makes it more difficult to Unit Test it when we are trying to refactor and modify. Let's suppose the code in question looks like this:

def writeInitialsToFile(filename, name, surname):
    initials = name[0] + '.' + surname[0] + '.'
    with open(filename, 'w') as file:
        file.write(initials)

def readInitials(filename):
    initials = None
    with open(filename, 'r') as file:
        initials = file.readline()
    return initials

A straightforward and bad idea would be to write a couple of Unit Tests that make use of a real file and simply test the reading and writing. Is therea a better way to test this code?

First of all, we need a way to replace the real file with something else. For both reading and writing we will now have a couple of functions, one that expects a stream fo…

Piotr's Less Obvious Advice on Google Mock: State maintenance

Google Mock provides several ways to maintain state inside mock objects. One way of implementing state maintenance is with SaveArg. Consider the following example.

We have a class Configurator, which allows a caller to set and get values of a parameter:

class Configurator
{
    public:

    virtual ~Configurator() {}

    virtual void setParamX(int n) = 0;
    virtual int getParamX() = 0;
};

And we have a class Client that calls Configurator's methods and it also has a method incParamXBy, that can be used to increase the current value of paramX by a certain value.

class Client
{
    public:

    Client(Configurator & cfg);
    virtual ~Client() {}

    void setParamX(int n);
    void incParamXBy(int n);
    int getParamX();

    private:

    Configurator & _cfg;
};

incParamXBy internally calls setParamX and getParamX on Configurator:

void Client::incParamXBy(int n)
{
    _cfg.setParamX(_cfg.getParamX() + n);
}

Let's assume that the initial value of paramX is A and that we want to increase paramX by…

Piotr's Less Obvious Advice on Google Mock: Returning new objects from a mock

Google Mock provides a way to return newly created objects from a mock method. Suppose we have a  Generator class that is supposed to generate new objects when createNewRecord method is called:

class Generator
{
    public:
    virtual ~Generator() {}
    virtual Record * createNewRecord() = 0;
};

...and suppose we want to mock this class:

class MockGenerator : public Generator
{
    public:
    MOCK_METHOD0(createNewRecord, Record * ());
};

Suppose the caller class Client has run method defined as follows:

void Client::run()
{
    for(int i = 0; i < 3; i++)
    {
        rec_tab[i] = gen.createNewRecord();
    }
}

We want the mock to return a pointer to a new object each time createNewRecord is called. This is how we can express this in the test code:

TEST(ClientTest, CanRun)
{
    MockGenerator gen;
    Client c(gen);

    EXPECT_CALL(gen, createNewRecord())
        .Times(3)
                 //this is equivalent of returning new Record(1,2,3)
        .WillOnce(ReturnNew<Record>(1,2,3))
        .Will…