08
qr-code

An example of literate programming in Clojure, using Emacs+Org

As first envisioned by the legendary Donald Knuth, literate programming (LP) is a higher-abstraction approach to creating software, emphasizing human understandability first. It is well-supported by the superb Emacs Org mode.

This blog post only shows the HTML export of a relatively small LP effort: my literate version of Rich Hickey's Clojure ants simulator. The HTML content below was produced with a single Org command, from the literate-ants.org file. To get the whole story, visit the github repository for literate-ants.

Introduction

What is this, why is it worthwhile? Quickly please!

  • You're looking at a literate programming (LP) style, single-file version of Rich Hickey's Clojure ants simulator, in Org mode format.
  • For best results please use Emacs with Org mode to view this =.org= file. If you're looking at this on Github.com, STOP - the rendering there is neither complete nor correct!
  • The benefits of LP+Emacs+Org:
    1. Coherence: a unified, single-file approach to software development that is more than the sum of its parts. LP is not just documentation and code together: it's a process and abstraction unifying the development lifecycle: requirements, architecture, design, code, tests, deployment, and maintenance - coherently bound in one active format.
    2. Flexibility: provided mostly by Org mode's mature features:
      • Org's plain-text markup is lightweight, yet more powerful than Markdown, and cleaner than rST. And of course, it's easy to version-control Org files.
      • The structural editing provided by Org documents lets you organize your thoughts/writing/code very quickly, and change/revise with minimum friction.
      • Org's exporter lets your write-once, express-many-times: you can export an Org file to HTML (e.g. for blogging) or LaTeX (for serious publishing).
  • Essentials
    • SHIFT-TAB will cycle the display: top-level headings only, all headings, or fully-expanded.
    • CTRL-c-v-t will tangle code; Org will process each code block below, and generate the source file literate-ants.clj
    • Within a code block, CTRL-c-'= will open a buffer to edit the code. For full power, be sure =clojure-mode, paredit, and nrepl are installed.
    • Export this file to HTML with CTRL-c-e h or, to see it immediately in a browser window, CTRL-c-e b.
    • Org docs: see main documentation, especially sections on structure, links, markup, and literate programming features.

Why Clojure?

Clojure is a modern Lisp dialect that runs (primarily) on the Java Virtual Machine. As a language its main paradigm is functional programming (vs. the usual OO or imperative languages of Java, Python, Ruby), and it also provides powerful constructs for concurrency such as software transactional memory (STM).

So why use or learn Clojure?

  1. There are technical reasons, better covered elsewhere.
  2. There are aesthetic reasons: code is poetry, and like the best poems, expressiveness (the ratio of power:symbols) matters, and Clojure excels there.
  3. Last but certainly not least, there are human reasons: I've found the Clojure community to be one of the smartest and friendliest around: there's a lot of brilliant-yet-humble innovation going on. If you've watched Hickey's talks and gotten a sense of his character, the same spirit generally pervades Clojurians.

Why literate ants?

When Clojure was invented and began picking up interest from 2007/2008, its creator Rich Hickey would highlight Clojure's features with a demo program: a visual simulation of ants seeking food on a finite 2-D "world" board. I found the ants.clj program fascinating, particularly as simulation is a core interest. Historically, simulations motivated the object-oriented programming paradigm, so seeing a very different yet concise way to fulfill requirements of encapsulation, concurrent state, and modeling changes over time drew me in to Clojure.

To build more skill in Clojure, I wanted to fully understand ants.clj. I also wanted to try Knuth's literate programming approach (LP), using my favorite tool: Emacs and its peerless org-mode. Thus this .org file (and its HTML or PDF version) you're now looking at is the literate version of Hickey's ants.clj code. I took the original program, made minor changes for my comprehension, and offer it as a working example of literate Clojure.

Overview and setup

Prerequisites
  1. A recent version of Emacs (ideally 24.3+).
  2. Both org-mode and clojure-mode installed; use Emacs ELPA.

Then if you start Emacs and load this file, you'll see it the way it's meant to be seen: as a multi-level, hierarchically organized and structured literate code file, w/ syntax-highlighted code blocks.

Useful commands
  • Use SHIFT-TAB and org-mode will cycle through top-level, headings, and full-expanded displays.
  • To generate a source-file from this .org file, CTRL-c-v-t to do the tangling step; that means org-mode will process each code block below, and generate the source file literate-ants.clj
Skip to the end? Good idea!

Before you dive into the actual code, you may want to run the ants simulation first - seeing it in action will help with understanding the details too. So tangle this literate file per above instructions, so you have the literate-ants.clj file, then jump down to Running the Program.

Caveats - this may not be the LP you're looking for

  1. Don't take this file as anything like an ideal literate programming example! This is just my version of understanding Rich Hickey's code, thus it does not reflect a complete or proper literate programming approach to use.
    • And what's proper LP? See the last 2009 comment on the literateprogramming.com page. LP is not just about documentation, but is a tool/approach for higher-level abstraction, combining human thought and code.
    • So beware: much of my prose below is relatively verbose and explanatory (the what and how of code), as opposed to what could/should be in the literate sections: meta, why, high-level discussion of major design choices.
  2. This version does not yet reflect more recent (post Clojure 1.2) changes to the language, e.g. defstruct is still used below, but has been deprecated in favor of Clojure records.
  3. My Java experience is quite limited, so parts which rely heavily on Java, such as the UI, I don't attempt to explain in-depth.

The Simulation World

The first part of ants.clj sets up the simulation world, where we'll be introduced to some of Clojure's powers.

Initial setup of constants/magic-numbers

After the copyright notice, the initial setup code of ants.clj is easy to understand (for coders at least), even if you've never dealt with Lisp before. We see parameters (aka constants and magic numbers) being defined for later use using Clojure's =def= special form: def creates a var (a mutable storage location) which connects a symbol to a value in the current namespace.

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;; ant sim ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;   Copyright (c) Rich Hickey. All rights reserved.
;;
;;   The use and distribution terms for this software are covered by the
;;   Common Public License 1.0 (http://opensource.org/licenses/cpl.php)
;;   which can be found in the file CPL.TXT at the root of this distribution.
;;   By using this software in any fashion, you are agreeing to be bound by
;;   the terms of this license.
;;
;;   You must not remove this notice, or any other, from this software.


;; Set dimensions of the world, as a square 2-D board:
(def dim 80)
;; Number of ants = nants-sqrt^2
(def nants-sqrt 7)
;; Number of places with food:
(def food-places 35)
;; Range of amount of food at a place:
(def food-range 100)
;; Scale factor for pheromone drawing:
(def pher-scale 20.0)
;; Scale factor for food drawing:
(def food-scale 30.0)
;; Evaporation rate:
(def evap-rate 0.99)

(def animation-sleep-ms 100)
(def ant-sleep-ms 40)
(def evap-sleep-ms 1000)

(def running true)

The board: ready to mutate via transactions

Things get more interesting once the actual simulation environment needs defining:

(defstruct cell :food :pher)  ; May also have :ant and :home values

First, a call to =defstruct= (like a hashmap or dictionary in other languages) defines a baseline cell.

  • defstruct is like a very lightweight class or constructor/template function, and conveniently wraps Clojure's =create-struct=.
  • Here, a cell has two keys to start, :food and :pher, to indicate the presence of food and pheromones. A cell may also have keys of :ant and :home, depending on whether an ant and/or the home-colony is present.

Next, the world function creates the 2-dimensional "board" of cells (here, a square of 80x80 cells), represented as vectors (rows or the vertical y-dimension) of a vector (the horizontal x-dimension columns in one row):

;; World is a 2d vector of refs to cells
(def world
     (apply vector
            (map (fn [_]
                   (apply vector
                          (map (fn [_]
                                 (ref (struct cell 0 0)))
                               (range dim))))
                 (range dim))))

How to read the above:

  • Start with the innermost =map= call, which uses an anonymous function to create one column of 80 cells, per (range dim). The =struct= returns a new structmap instance using the earlier cell as the basis, initializing the :food and :pher values to zero.
  • But notice that struct is wrapped with a transactional ref, and here's the first glimpse of Clojure's concurrency powers. With each cell being stateful (possibly time-varying values of :food, :pher, :ant, and :home values) and with multiple threads updating the board and board elements, we'd typically think of using locks on each cell when updating its state.

    But in Clojure with its software transactional memory (STM), we just use ref for safe references to mutable collections (here, a struct) - all changes to a cell will then be atomic, consistent, and isolated!1 Like using an RDBMS, you don't need to manually manage concurrency.

  • Once you understand the innermost (ref (struct cell 0 0 )) map call, the rest of (def world...) is straightforward: apply uses vector as a constructor function with the map function producing the vector's arguments, creating a "column" in the 2-D board.
  • Then the pattern is repeated in the outermost (apply vector (map...)) call, creating all the columns of the 2-D board.
  • Note that as defined, each vector in world (again, a 2-D vector of vectors) corresponds to an x-position, and of course, within that vector are the y-positions (here, a total of 80 cells).

The place function is a selector function (think of "place" as the noun, not the verb) returning particular cells in the 2-D world. Once we have a cell, we can then mutate it to represent ants, food, and pheromones (or their absence):

(defn place [[x y]]
  (-> world (nth x) (nth y)))
  • place takes a single vector argument (having two elements x and y), then applies the thrush operator (the arrow-like ->) on the world object, first selecting the "column" (nth x) on world, then the "row" (nth y) on that column.
Aside: the thrush operator

The thrush operator helps make code more concise, and arguably clearer: instead of reading code "inside-out" to mentally evaluate it, we can read it left-to-right.2 Consider how the equivalent place function would look without thrushing:

(defn place-verbose [[x y]]
  (nth (nth world x) y))

Ants as agents - doing asynchronous uncoordinated changes

Next we'll consider the "active things" in ants.clj, the ants themselves. As before, we start with defstruct, defining an ant as having only one required key, its direction. (An ant may temporarily have another key, :food.)

(defstruct ant :dir)  ; Always has dir heading; may also have :food

(defn create-ant
  "Create an ant at given location, returning an ant agent on the location."
  [location direction]
    (sync nil
      (let [the-place (place location)
            the-ant (struct ant direction)]
        (alter the-place assoc :ant the-ant)
        (agent location))))

To explain the above constructor function for ants, create-ant:

  • Takes two arguments, location and direction. location will be a vector [x y], and as we saw, passed on to the place function as an argument; direction is a number from 0-7 inclusive corresponding to one of the eight cardinal directions.
  • More concurrency support: the sync function takes a flags argument (as of Clojure 1.3, it's still ignored so just pass nil), and then a list of expressions that will be executed together atomically (all or nothing) as a transaction.
  • The let special form binds pairs of symbols and expressions in its arguments vector, providing local, lexical bindings within the scope of the body following.
  • sync will ensure that any mutations of refs using the alter function will be atomic. Previously we had used ref around each cell, so in the above code where the-place is such a ref-wrapped cell, alter takes the-place ref as its first argument, then =assoc= as the function to be apply'ed on the-place, tying a new ant instance to it (remember that as a cell, the-place is sure to have :food and :pher key-values already, now we add :ant). Like the thrush operator earlier, the syntax of alter enables convenient left-to-right reading.
  • Finally, the agent function. What are Clojure agents? To quote the docs,

    Agents provide shared access to mutable state. They allow non-blocking (asynchronous as opposed to synchronous atoms) and independent change of individual locations (unlike coordinated change of multiple locations through refs).

    Clojure's agent function takes one required argument of state, returning an agent object with initial value of that given state. Here, as the last line of create-ant, agent effectively returns the ant object at its starting location. Ants as agents make sense: we expect them to move around independently (i.e. asynchronously) in the simulation world.

Setting up the home, and ants

The home of the ants is not a single cell on the world-board, but a square of cells, with its top-left corner offset from the origin (0, 0). Its sides are proportional to the number of ants because the home square will initially contain all the ants - one ant per cell - before the simulation runs. We can see these two aspects of the home-square in the two def calls for home-offset and home-range below.

(def home-offset (/ dim 4))
(def home-range (range home-offset (+ nants-sqrt home-offset)))

(defn setup
  "Places initial food and ants, returns seq of ant agents."
  []
  (sync nil
    (dotimes [i food-places]
      (let [p (place [(rand-int dim) (rand-int dim)])]
        (alter p assoc :food (rand-int food-range))))
    (doall
     (for [x home-range y home-range]
       (do
         (alter (place [x y]) assoc :home true)
         (create-ant [x y] (rand-int 8)))))))

The setup function's docstring tells us what it's doing, so on to the details:

  • setup takes no arguments.
  • As we saw before in create-ant, the sync function wraps a sequence of expressions that together should be executed atomically, all-or-nothing.
  • Setup initial food: The dotimes function takes two arguments, the first a vector [name n] with n being the number of times that the body (the second argument) will be repeatedly executed, usually for its side-effects/mutations.
    • Here, the unused name i is bound to the integers from 0 to 34, since we had specified food-places as 35 initially.
    • The body is clear enough: bind p to the randomly chosen place on the world-board (using the rand-int function for x, y). The already-seen alter function modifies that p to have a random amount of food value.
  • Placing the ants in their starting positions: The doall function forces immediate evaluation of a lazy sequence - in this case the lazy sequence produced by the for function.
    • Here, the for function's first argument is: two binding-form/collection-expr pairs for every x and y position within the square of the ants' home.
    • The for function's second argument is the body-expression, here wrapped in the do special form which ensures order of evaluation (usually, of expressions having side-effects): designate the place as a home position, then create an ant on that place with a random initial direction.

In sum, the setup function shows how to deal with state and its mutation in Clojure: we started with a 2-D world-board of places (cells) as Clojure refs; then we modify/mutate each place using alter. We can use various looping functions such as dotimes and doall to process a batch of state-mutations (of the world-board) atomically and consistently.

Orientation and moving around the world

Next, consider facing/orientation and moving to another place in the 2-D world. Three functions below, followed by explanations:

(defn bound
  "Returns given n, wrapped into range 0-b"
  [b n]
  (let [n (rem n b)]
    (if (neg? n)
      (+ n b)
      n)))

;; Directions are 0-7, starting at north and going clockwise. These are
;; the 2-D deltas in order to move one step in a given direction.
(def direction-delta {0 [0 -1]
                      1 [1 -1]
                      2 [1 0]
                      3 [1 1]
                      4 [0 1]
                      5 [-1 1]
                      6 [-1 0]
                      7 [-1 -1]})

(defn delta-location
  "Returns the location one step in the given direction. Note the
  world is a torus."
  [[x y] direction]
  (let [[dx dy] (direction-delta (bound 8 direction))]
    [(bound dim (+ x dx)) (bound dim (+ y dy))]))

With the 2-D world board, we have the 8 cardinal directions (North, North-East, East, etc.), and board edges that wrap-around to the opposite side - like the old arcade games of the 1980's, e.g. Pac-Man and Asteroids. The functions bound and delta-location help enforce these world-behaviors, while the definition of direction-delta maps a movement in a cardinal direction to the corresponding change in x and y. A few comments on each:

  • The bound function using the built-in rem (i.e. remainder) function is straightforward. Observe how bound is used in delta-location to ensure wrap-around behavior in: 1) cardinal directions; 2) the world-board, at its edges given by dim.
  • direction-delta maps the eight cardinal directions (0 is North) to the corresponding changes in [x y]. Note the syntax: it's an array-map literal, where the order of insertion of key-value pairs (here, keys 0-7) will be preserved.
  • delta-location takes the current [x y] location and a direction, returning the new corresponding location on the world-board.

Ant-agent behavior functions

In Hickey's simulation, ants need to move (rotation and translation), pick up and drop-off food, and make rudimentary decisions.

Ant movements

Our ants need two behaviors to get around their world: turning (or changing the direction they "face"), and stepping forward. Let's deal with turning first:

;; An ant agent tracks the location of an ant, and controls the
;; behavior of the ant at that location.

(defn turn
  "Turns the ant at the location by the given amount."
  [loc amt]
  (dosync
   (let [p (place loc)
         ant (:ant @p)]
     (alter p assoc :ant (assoc ant :dir (bound 8 (+ (:dir ant) amt))))))
  loc)

The turn function takes two arguments, location and the amount of turn. What's interesting is the usage of the dosync function, which ensures the ant's turn - the changes of state within the assoc function calls - is all-or-nothing. The ant gets a new direction per the innermost assoc, then the outermost assoc updates the place with the updated ant.

Now for actual movement to a new place:

(defn move
  "Moves the ant in the direction it is heading. Must be called in a
  transaction that has verified the way is clear."
  [startloc]
  (let [oldp (place startloc)
        ant (:ant @oldp)
        newloc (delta-location startloc (:dir ant))
        newp (place newloc)]
    ;; move the ant
    (alter newp assoc :ant ant)
    (alter oldp dissoc :ant)
    ;; leave pheromone trail
    (when-not (:home @oldp)
      (alter oldp assoc :pher (inc (:pher @oldp))))
    newloc))

The move function changes state of both the ant and board, thus the doc-string note that it must be called in a transaction. The code is self-explanatory, though if "pheromone" is a new term to you, you'll want to learn about a dominant form of chemical communication on Earth. Whenever our artificial ant is not within its home, it will "secrete" pheromone (inc the :pher value by 1) at the place it just left, making it easier (more likely) for it and other ants to travel between home and food locations in the future (instead of doing a completely random walk).

Ants and food

When an ant finds food, it "picks up" one unit of it; when it returns home with a food unit, it will "drop" its food there. These two interactions (each having two steps) change the board, and as with the move function, they need to occur atomically (all-or-nothing) to ensure the world is in a consistent state.

(defn take-food [loc]
  "Takes one food from current location. Must be called in a
  transaction that has verified there is food available."
  (let [p (place loc)
        ant (:ant @p)]
    (alter p assoc
           :food (dec (:food @p))
           :ant (assoc ant :food true))
    loc))

(defn drop-food [loc]
  "Drops food at current location. Must be called in a
  transaction that has verified the ant has food."
  (let [p (place loc)
        ant (:ant @p)]
    (alter p assoc
           :food (inc (:food @p))
           :ant (dissoc ant :food))
    loc))

Notice how similar the structure is for the two functions above; possibly they're candidates for macro refactoring.

Ant judgment

Our ants need some decision-making for their overall task of finding food and bringing it home. As we'll see shortly, an ant's behavior is based on two states, either:

  1. The ant does not have food, and is looking for it. In this mode, it weighs the three map locations ahead of it (ahead, ahead-left, ahead-right) by the presence of either food or pheromone.
  2. The ant has food, and needs to bring it to the home box/location. Now it weighs which of the three ahead-positions to take by the presence of pheromone, or home.

So we need functions to express preference of the next location for an ant. The functions rank-by and wrand help with that.

(defn rank-by
  "Returns a map of xs to their 1-based rank when sorted by keyfn."
  [keyfn xs]
  (let [sorted (sort-by (comp float keyfn) xs)]
    (reduce (fn [ret i] (assoc ret (nth sorted i) (inc i)))
            {} (range (count sorted)))))

The rank-by function gives weights to where an ant will move next in the simulation world. It takes two arguments, keyfn and xs - but what do those args look like, and where is rank-by used? In the behave function below; you'll see that the keyfn checks for the presence of :food, :pher, or :home - in the three cells (board locations) of the xs vector of [ahead ahead-left ahead-right].3

  • The (sort-by keyfn coll) function returns a sorted sequence of items in coll, ordered by comparing (keyfn item). Here, for the local value sorted, it will be ascending order of cells/places, by their :food/:home/:pher values - each of those is valuable to an ant depending on whether it's looking for food, or bringing it home.
  • The (reduce f initial-val coll) functionn in its 3-arguments form here has its 1st argument f as a function taking two arguments, the current/initial-val value and the next/first item from coll. In this case, it will "build-up" a map from the local sorted value, with the keys being the ranked cells/places, and the values being integers 1, 2 and 3. To get a sense of what's going on, try this on your Clojure REPL:
      (let [sorted [0 0.7 1.0]]
        (reduce (fn [ret i] (assoc ret (nth sorted i) (inc i)))
                {}
                (range (count sorted))))
      ;; You should see {1.0 3, 0.7 2, 0 1}
      ;;
      ;; Within the behave function below, the return value might be
      ;; like {<cell-ahead-left> 3, <cell-ahead-right> 2, <cell-ahead> 1}
      ;; or similar.
    

Next: The wrand function helps with the larger task of randomizing which location/cell the ant moves to next in a weighted manner; i.e. the "dice" are loaded with rank-by, then "rolled" here:

(defn wrand
  "Given a vector of slice sizes, returns the index of a slice given a
  random spin of a roulette wheel with compartments proportional to
  slices."
  [slices]
  (let [total (reduce + slices)
        r (rand total)]
    (loop [i 0 sum 0]
      (if (< r (+ (slices i) sum))
        i
        (recur (inc i) (+ (slices i) sum))))))

How is wrand used? Like rank-by, look in the behave function: its single argument of slices is a vector of 3 integers (from rank-by above), corresponding to the relative desirability of the 3 cells ahead of the ant. So if the slices argument looked like [0 3 1], that would correspond to zero probability of moving ahead, and 3/4 chance moving to the ahead-left cell over the ahead-right cell.

  • The let value total uses reduce to set the upper bound on the random number; loosely like setting the maximum number of faces on the die to be rolled (albeit that some die numbers are geometrically impossible).
  • The rand function returns a random floating point number from 0 (inclusive) to n (exclusive).
  • Here's the only looping construct in the entire ants program: it's analogous to checking which compartment of the roulette wheel the ball fell in. The if checks if r "fell into" the current pocket - the size of which is given by (slices i). If yes, return the index corresponding to that pocket; if not, check the next pocket/slice.
Tying it all together: the behave function for ants

The behave function below is the largest one, so it helps to keep in mind its main parts while diving into details:

  1. let values - help with readability.
  2. Thread/sleep - helps slow down ants in the UI display.
  3. dosync - ensures ants behavior is transactional, all-or-nothing.
  4. if branch: main logic for an ant, if ant has :food take it home, otherwise look for food.

Also, consider the context of how behave is first used: within the main invocation at the end, there's the expression:

(dorun (map #(send-off % behave) ants))

So the behave function is called on every ant agent via the send-off function, which is how Clojure dispatches potentially blocking actions to agents. And there certainly are potentially blocking actions when using behave, since ants may try to move into the same cell, try to acquire the same food, etc.

(defn behave
  "The main function for the ant agent."
  [loc]
  (let [p (place loc)
        ant (:ant @p)
        ahead (place (delta-location loc (:dir ant)))
        ahead-left (place (delta-location loc (dec (:dir ant))))
        ahead-right (place (delta-location loc (inc (:dir ant))))
        places [ahead ahead-left ahead-right]]
    ;; Old way of Java interop: (. Thread (sleep ant-sleep-ms))
    ;; New idiomatic way is,
    (Thread/sleep ant-sleep-ms)
    (dosync
     (when running
       (send-off *agent* #'behave))
     (if (:food ant)
       ;; Then take food home:
       (cond
        (:home @p)
          (-> loc drop-food (turn 4))
        (and (:home @ahead) (not (:ant @ahead)))
          (move loc)
        :else
          (let [ranks (merge-with +
                        (rank-by (comp #(if (:home %) 1 0) deref) places)
                        (rank-by (comp :pher deref) places))]
          (([move #(turn % -1) #(turn % 1)]
            (wrand [(if (:ant @ahead) 0 (ranks ahead))
                    (ranks ahead-left) (ranks ahead-right)]))
           loc)))
       ;; No food, go foraging:
       (cond
        (and (pos? (:food @p)) (not (:home @p)))
          (-> loc take-food (turn 4))
        (and (pos? (:food @ahead)) (not (:home @ahead)) (not (:ant @ahead)))
          (move loc)
        :else
          (let [ranks (merge-with +
                                  (rank-by (comp :food deref) places)
                                  (rank-by (comp :pher deref) places))]
          (([move #(turn % -1) #(turn % 1)]
            (wrand [(if (:ant @ahead) 0 (ranks ahead))
                    (ranks ahead-left) (ranks ahead-right)]))
           loc)))))))
The let values

The let values: quite straightforward, just note the twist in how behave receives a cell/location as its argument, not an ant (which an OO-centric design might expect).

The only JVM/concurrency leakage: Thread/sleep

The #+BEGINSRC clojure (. Thread (sleep ant-sleep-ms))

(Thread/sleep ant-sleep-ms)

with Clojure's Java Interop.

  • The first version uses the dot special form and in particular, the
    (. Classname-symbol (method-symbol args*))
    

    Thread as the Classname-symbol, and sleep as the method-symbol.

  • However, outside of macros, the idiomatic form for accessing method members is the second form, #+BEGINSRC clojure

(Classname/staticMethod args*) (one ant-agent per thread) between their movements, so you can see in the UI what they're doing, and they'll appear more realistic. ORG-LIST-END-MARKER But more interesting still: in this highly concurrent program, the sleep expression is about the only explicit reference to threads in the entire code, i.e. one of the very few "leaky abstractions" hinting at Clojure's use of underlying JVM concurrency constructs. Besides this call, there are no locks, and no explicit thread allocations.

The main dosync call

Next, let's look at what's going on within the dosync transaction.

Repeating asynchronously, without looping

The first expression is:

(when running (send-off *agent* #'behave))

Initially this may seem strange; aren't we in the behave function because send-off already called it before entering it? Won't this just loop uselessly, not hitting the core if code below? Not quite:

  • Instead, send-off adds another execution of behave to the current agent's queue of work/functions, and immediately returns.
    • The current agent is referenced by the asterisk-surrounded *agent* which Clojure dynamically binds to the current active agent on a thread-local basis.
  • Thus after finishing this call of behave the ant will do another action (execute behave again), and another, and so on. No explicit looping, just queue and repeat.

Also, note the ~#'~ sharp-quote, before behave; this is a Clojure Var, one of Clojure's mutable reference types. It's just syntactic sugar for (var behave). Invoking a Var referring to a function is the same as invoking the function itself…so why bother with it? I don't know; here's what I could find:

Why use send-off instead of send ?

Determining what the ant does next

Finally, the ant's logic for what to do next is in the large if expression. The code looks dense but at the top level it's just a binary choice:

  • If the ant has food, take it home; the cond specifies 3 sub-cases:
    1. At a home cell, drop the food and turn around 180 degrees, to exit home for more food.
    2. If a home cell is ahead, move to it.
    3. Otherwise, do a ranking of cells ahead (places has the cells ahead, ahead-left, ahead-right) per presence of pheromones, or home, and then randomly select from those 3 cells per their ranking/weighting.

World behavior: pheromone evaporation

(defn evaporate
  "Causes all the pheromones to evaporate a bit."
  []
  (dorun
   (for [x (range dim) y (range dim)]
     (dosync
      (let [p (place [x y])]
        (alter p assoc :pher (* evap-rate (:pher @p))))))))

For a bit of realism and a cleaner UI/visual, it's useful to have the ants' pheromones diminish and evaporate from the world over time. The evaporate function fulfills that requirement:

  • It takes no arguments, it will work over the entire world/board of cells, accessed via the tuples of x and y.
  • The =dorun= function takes a lazy collection/sequence (here, that of the for expression) and forces the realization of that collection for its side effects, discarding any returned values.
    • It's unlike the similarly-named doall where we do care about the values.
    • And it's unlike doseq, which is like Clojure's for but runs immediately and does not collect the results.
  • dosync is used as before, for lock-free updating of a place cell. Here, the desired side-effect/"mutation" is to update the :pher value at the place cell with a lower number.

We'll see shortly that evaporate will run every second, a process that (like the ants) will be handled asynchronously using a Clojure agent.

The UI

The user interface for the ants relies heavily on Clojure's Java inter-operation capabilities. But as we'll see, it's more than just wrapping calls to Java.

Using the Java AWT

(import
 '(java.awt Color Graphics Dimension)
 '(java.awt.image BufferedImage)
 '(javax.swing JPanel JFrame))

The import pulls in classes from Java's Abstract Window Toolkit (AWT) package, and from the Java Swing package. (Aside: curious why Swing is in the javax namespace?) Assuming unfamiliarity with Java Swing, let's describe the classes used:

  • The =Color= class encapsulates a color in the standard RGB color space. In the code below, its usage as a constructor for a color instance follows several arities:
    • 4 integer arguments: r, g, b, and a for the alpha/transparency (0 transparent, 255 opaque)
    • 3 integer arguments: r g b
    • 1 argument: not a constructor call, but an access of a predefined static Color field by name, returning the color in the RGB color space.
  • The =Graphics= class is an abstract base class for all graphics contexts, i.e. a Graphics instance holds the current state data needed for rendering it: the =Component= object on which to draw, the current clip, color, and font, etc. Below, we'll see that the Clojure functions that take a Graphics instance as an argument:
    • fill-cell
    • render-ant
    • render-place
    • render

    …all do some kind of rendering/drawing.

  • The =Dimension= class encapsulates the integer width and height of a component. This class is used just once below, in setting the size of the panel of the UI.
  • =BufferedImage= class is needed for raster image data; below, the render function uses it to paint the background panel.
  • The =JPanel= class is the generic "lightweight" UI container in Java Swing (seems like the div element in HTML). Below, it's used just once for the main display.
  • The =JFrame= class creates a top-level window (w/ title and border) in Swing; it's used just once below for the main ants UI window.

Functions to render the board and the ants

Each discrete cell on the world board is a square matrix of pixels; with an odd number of pixels chosen, we can have a central position:

(def scale 5)  ; A world cell is 5x5 pixels.

By default, cells are empty; drawing cells having food or ant-deposited pheromones is done by filling with symbolic colors - here by running the Java methods setColor and fillRect:

(defn fill-cell [#^Graphics g x y c]
  (doto g
    (.setColor c)
    (.fillRect (* x scale) (* y scale) scale scale)))

Note the use of the =doto= function here and in many places below: in Java, procedural mutation of a newly constructed instance is common for initialization. Clojure's doto function is meant to be more concise in specifying the target object just once, and then methods/setters acting on it and then returning it, implicitly.

Drawing an ant: the graphical appearance of an ant is just a (5-pixel long) line pointing in one of the 8 cardinal directions, of two different colors (having food or not):

(defn render-ant [ant #^Graphics g x y]
  (let [black (. (new Color 0 0 0 255) (getRGB))
        gray (. (new Color 100 100 100 255) (getRGB))
        red (. (new Color 255 0 0 255) (getRGB))
        [hx hy tx ty] ({0 [2 0 2 4]  ; Up/North pointing
                        1 [4 0 0 4]
                        2 [4 2 0 2]
                        3 [4 4 0 0]
                        4 [2 4 2 0]  ; Down/South
                        5 [0 4 4 0]
                        6 [0 2 4 2]
                        7 [0 0 4 4]}
                       (:dir ant))]
    (doto g
      (.setColor (if (:food ant)
                  (new Color 255 0 0 255)
                  (new Color 0 0 0 255)))
      (.drawLine (+ hx (* x scale)) (+ hy (* y scale))
                (+ tx (* x scale)) (+ ty (* y scale))))))

Note the cleverly concise destructuring for the start and end drawing coordinates, needed in AWT's =drawLine= method.

If a cell in the ants' world is not empty, it has one or more of three things present: pheromone, food, or an ant. The render-place function updates the cell's appearance accordingly:

(defn render-place [g p x y]
  (when (pos? (:pher p))
    (fill-cell g x y (new Color 0 255 0
                          (int (min 255 (* 255 (/ (:pher p) pher-scale)))))))
  (when (pos? (:food p))
    (fill-cell g x y (new Color 255 0 0
                          (int (min 255 (* 255 (/ (:food p) food-scale)))))))
  (when (:ant p)
    (render-ant (:ant p) g x y)))

Finally, the render function ties everything together: initializing the UI/window appearance by applying render=place to every cell, and also drawing the home space of the ants. Note the heavy usage of the dot special form: the UI code relies heavily on Java, though Clojure's for and doto help us avoid Java boilerplate and stay concise:

(defn render [g]
  (let [v (dosync (apply vector (for [x (range dim) y (range dim)]
                                   @(place [x y]))))
        img (new BufferedImage (* scale dim) (* scale dim)
                 (. BufferedImage TYPE_INT_ARGB))
        bg (. img (getGraphics))]
    ;; First paint everything white, on the bg instance:
    (doto bg
      (.setColor (. Color white))
      (.fillRect 0 0 (. img (getWidth)) (. img (getHeight))))
    (dorun
     (for [x (range dim) y (range dim)]
       (render-place bg (v (+ (* x dim) y)) x y)))
    ;; Draw the home space of the ants:
    (doto bg
      (.setColor (. Color blue))
      (.drawRect (* scale home-offset) (* scale home-offset)
                 (* scale nants-sqrt) (* scale nants-sqrt)))
    (. g (drawImage img 0 0 nil))
    (. bg (dispose))))  ; Finished using Graphics object, release it.

Setting the scene, then updating it continuallyy

Almost ready to begin our simulation; we need to setup some additional elements per AWT conventions: the main UI panel where visual changes take place, the top-level window frame, and an animator agent that continually updates the visual elements:

(def panel (doto
             (proxy [JPanel] [] (paint [g] (render g)))
             (.setPreferredSize (new Dimension
                                     (* scale dim)
                                     (* scale dim)))))

(def frame (doto (new JFrame) (.add panel) .pack .show))

(def animator (agent nil))
Animation, panel-by-panel

Now for bringing the static starting "picture" to life - like the cartoons of old, the animation function will "draw" the next state of the main panel displaying the ants. Below, Hickey uses the queue-itself-then-run, again-and-again code pattern we've seen before (above, in updating an ant's state):

(defn animation [x]
  (when running
    (send-off *agent* #'animation))
  (. panel (repaint))
  (. Thread (sleep animation-sleep-ms))
  nil)

Finally, we need another agent to handle one more time-track of changes: evaporation, using the evaporate function defined above.

(def evaporator (agent nil))

(defn evaporation [x]
  (when running
    (send-off *agent* #'evaporation))
  (evaporate)
  (. Thread (sleep evap-sleep-ms))
  nil)

Running the Program

The project.clj file

When you tangle this file, the local project.clj file will be created alongside ants.clj. Assuming you've installed the excellent Leiningen, you'd then:

  1. Enter lein deps at the shell prompt to get dependencies.
  2. Then you can start a REPL with lein repl, from which you can start the simulator (see next section).
(defproject literate-ants "1.0.0-SNAPSHOT"
  :description "This is a literate version of: Rich Hickey's Ants simulator, demonstrating Clojure's concurrency support."
  :dev-dependencies []
  :dependencies [[org.clojure/clojure "1.5.1"]]
  )

Running the simulator

At the REPL, you can enter the entire do expression below, or try each line within it separately:

(do
  (load-file "./literate-ants.clj")
  (def ants (setup))
  (send-off animator animation)
  (dorun (map #(send-off % behave) ants))
  (send-off evaporator evaporation))

Either way you'll see a new window appear with a white background, blue square representing the ants' home, red squares of food, black or red (w/ food) moving lines representing each ant, and green squares for pheromones in various concentrations. A lot happening concurrently, with no locks, and beautifully concise code - welcome to Clojure!

Footnotes:

1 STM is like a memory-only SQL database, thus the last property of being durable/persistent won't be satisfied.

2 Apparently Clojure's thrush is not quite a true thrush, see Michael Fogus' article.

3 Remember that :food, :pher, and :home are mutually exclusive in a cell. When an ant wants to go home with food, and the home cell(s) is ahead of it, it will always go home, there won't be competing :pher presence.

blog comments powered by Disqus