Common Lisp, Clojure and Evolution

After my last post about Lisp IDEs, I decided to use Clojure and the Counter-Clockwise Eclipse plug-in as I continued working my way through Land of Lisp. This turned out to be a good move, as the effort of porting to Clojure forced me to really understand how the games worked and highlighted a lot of the differences between Common Lisp and Clojure. Before this, I hasn’t appreciated how close Clojure is to a traditional Lisp. This post shares my findings from translating the “Evolution” example in Land of Lisp into Clojure. This post assumes a basic familiarity with Lisp style code. As I’m still very much a beginner at this stuff, please feel free to post any suggested improvements or point out mistakes.

TL;DR: Clojure is very close to Common Lisp but has several minor syntactical differences, some bigger differences in macros, support for more intrinsic types, Java integration and, perhaps most significantly, a programming model that encourages a more functional style of development and is designed to support concurrency.

“Evolution” attempts to simulate a very simple world where animals roam in directions dictated by their genes, eating food and reproducing asexually. Reproductions cause random changes to genes and hence the movement of animals. The center of the game world has more food resources than the rest, which means we can expect different types of animal to evolve in the middle than the rest of the world. It’s apparently based on article by A.K. Dewdney: “Simulated evolution: wherein bugs learn to hunt bacteria” (searching for this will find you some interesting resources). Full source code for the Common Lisp version is in the book as well as on the Land of Lisp website, the Clojure version is available on github.

UPDATE: the above github link is to the latest version of the code, the first version is available here. Both the post and code have been updated to reflect changes suggested in comments.

We start off by defining some parameters for the game world, which is almost identical in both versions. For example, defining the *width* parameter in Common Lisp:

(defparameter *width* 100)

And in Clojure:

(def *width* 100)

However, we almost immediately stumble upon a more important difference when we try to create a hash-set to store the location of plants in the game-world. In Common Lisp, hash-sets are faked using hash-tables where the value stored is unimportant (we are only interested if the key exists in the table, not what its value is). The Evolution example uses the following code to add plants to the game world at a random location:

(defparameter *plants* (make-hash-table :test #'equal))

(defun random-plant (left top width height)
   (let ( (pos (cons (+ left (random width)) 
                     (+ top (random height)))))
        (setf (gethash pos *plants*) t)))

The position of the plant in the game world is the key and true (t in Common Lisp) is used as the value. Note the use of the equal method for testing equality rather than eq (so that the contents of the con cells are compared rather than testing if they are the same cons cell). In Clojure we can achieve something similar like this:

(def *plants* (ref #{}))

(defn random-plant [left top width height]
  (let [pos (list (+ left (rand-int width)) 
                  (+ top (rand-int height)))]
    (dosync (alter *plants* conj pos)))))

In Clojure, if you want to modify something, you instead point to it using a ref which can be changed to point at a different “thing” (refs are the one of the few things in Clojure that are allowed to mutate). All modification of refs must be synchronised in “transactions” such as the dosync method. This marks a fundamental difference between the languages; Clojure programmers are forced to think up-front about parallelism and are almost ushered down a more functional path. The #{} is just shorthand for an empty hash-set (Clojure has a intrinsic support for more data structures than just lists). Also, in this case, we don’t need to worry about the equals method in Clojure — the default does what we need. Other minor differences are the use of square brackets for function arguments (which helps make things more readable), random becoming rand-int and using list to create a new list rather cons (which appears trivial, but points towards a slightly bigger difference in how lists are constructed in Common Lisp and Clojure).

Creating the list of animals and populating with the first animal also has a few differences. In Common Lisp:

(defstruct animal x y energy dir genes)

(defparameter *animals* 
    (list (make-animal :x      (ash *width*  -1)
                       :y      (ash *height* -1)
                       :energy 1000
                       :dir    0
                       :genes  (loop repeat 8
                                     collecting (1+ (random 10))))))

And in my Clojure version:

(defstruct animal :x :y :energy :dir :genes)

(def *animals*
  (list (struct animal
          (round (/ *width* 2)) ; x
          (round (/ *height* 2)) ; y
          1000 ; energy
          0 ; dir
          (loop [genes [] i 8]
            (if (zero? i)
              genes
              (recur (conj genes (+ 1 (rand-int 10))) (dec i)))))))

Note that Conrad uses the ash function to do division. Personally, I would only use ash when I was doing bitwise operations or if it provided a large performance increase on a time-sensitive section of code, as I feel it obscures the meaning of the code slightly. Clojure does have the bit-shift-left and bit-shift-right operations to provide similar functionality but I decided to use the standard division operator instead. (Conrad later told me that he used ash to avoid using round which would have required him to explain about returning multiple values from a single Lisp function).

More interestingly, the loop construct is considerably different. The loop macro is a lot simpler in Clojure (it’s little more than a recur binding), so we need a little more coding to achieve the same effect as Common Lisp (in particular, Clojure has no collecting keyword). However, comments on this post showed me that this could be better written as:

(def *animals*
  (list {:x (round (/ *width* 2))
         :y (round (/ *height* 2))
         :energy 1000
         :dir 0
         :genes (vec (repeatedly 8 #(inc (rand-int 10))))}))

Which gets rid of the unnecessary use of structs (plain maps are easier here) and generates the random genes in a cleaner, more concise way.

At the next point, my Clojure code takes a significant departure from the Common Lisp. The Common Lisp function for moving animals in the game world looks like:

(defun move (animal)
  (let ( (dir (animal-dir animal))
        (x (animal-x animal))
        (y (animal-y animal)))
    (setf (animal-x animal) 
        (mod (+ x
                    (cond ( (and (>= dir 2) (< dir 5)) 1)
                           ( (or (= dir 1) (= dir 5)) 0)
                          (t -1))
                     *width*)
                     *width*))
    (setf (animal-y animal) 
        (mod (+ y
                    (cond ( (and (>= dir 0) (< dir 3)) -1)
                           ( (and (>= dir 4) (< dir 7)) 1)
                           (t 0))
                    *height*)
                    *height*))
    (decf (animal-energy animal))))

And my Clojure looks like:

(defn move [{:keys [x y dir] :as animal}]
    {:x (mod (+ x
             (cond 
               (and (>= dir 2) (< dir 5)) 1
               (or (= dir 1) (= dir 5)) 0
               :else -1)) ; note clojure has else form and less ()s
        *width*)
      :y (mod (+ y
             (cond (and (>= dir 0) (< dir 3)) -1
               (and (>= dir 4) (< dir 7)) 1
               :else 0))
        *height*)
      :energy (dec (:energy animal))
      :dir (:dir animal)
      :genes (:genes animal)}) ; return new animal rather than change given

Movement is calculated by using an animals “dir” which is integer representing a direction (0 is up-left, 1 is up, 2 is up-right etc).

The fundamental difference between the versions is that I decided not to directly change the animal in the function argument, but instead to return a new animal representing the animals location. This meant I could avoid worrying about refs and also let me play with programming in a more pure functional manner. Some other minor points:

  • Clojure can use destructuring to bind symbols to parts of parameter lists in functions or let bindings. This allows us to use x, y and dir directly rather than have to extract it from the map each time.
  • When we do want to pull bits out of structs/maps, it works a little differently; in Clojure you can use the key directly as a method (e.g. (:energy orig) whereas Common Lisp generates methods like animal-energy
  • The Clojure version of the cond macro has less brackets than the Common Lisp and an else keyword.
  • I removed the unneeded addition of *width* and *height* before calling mod (I think this intended to avoided negative results from mod, but both the Clojure and Common Lisp version of mod return the sign of the divisor not the dividend i.e. (mod -1 4) is 3. (This was pointed out to me by a commenter on reddit).

The eat method, which simulates an animal eating any plants in its current location, also contains a few interesting differences. In Common Lisp we have:

(defun eat (animal)
  (let ( (pos (cons (animal-x animal) (animal-y animal))))
    (when (gethash pos *plants*)
      (incf (animal-energy animal) *plant-energy*)
      (remhash pos *plants*))))

Whereas my Clojure version looks like:

(defn eat [{:keys [x y energy] :as animal}]
  (let [pos (list x y)]
    (dosync
      (if (contains? @*plants* pos)
        (do
          ; get rid of the plant first
          (alter *plants* disj pos)
          ; so we can return the updated animal
          (assoc animal :energy (+ energy *plant-energy*)))
        animal))))

(Or at least it does after I fixed the concurrency error pointed out by cgrand).

The code for checking for existence of a plant at the animal’s location is fairly similar, but note that Clojure needs to dereference the hash-map using @ and uses the contains? predicate rather than getting the value in the hash-table. In Clojure I needed to remove the plant first (which is a side-effect) before returning the updated animal. Removing the plant in Clojure is a little more complicated — rather than just calling remhash, I need to set the *plants* reference to a new hash-map which is the “disjoint” of the old hash-map and the position of the eaten plant. Whilst the Common Lisp version can just increment the energy of the animal (another side-effect), the Clojure version creates a new animal which is the same as the old animal, except with its energy increased, thorugh use of the assoc function.

The reproduce function (which I haven’t reproduced for brevity) was modified in a similar way, most notably to return a list of all animals including the new animal rather than inserting directly into animal list (which isn’t mutable in my version). The update-world function was also modified to be more functional, taking an animal list as input and returning an updated list. The Clojure version uses # as shorthand for an anonymous function rather than lambda. flatten is needed so that we keep all the animals in a single list rather have lists of lists.

The draw-world method (also not reproduced) doesn’t contain any interesting new differences, but was the source of a bug for a long time — turns out if you do print "\n" instead of println in Clojure, the output buffer won’t be flushed properly. Also worth noting is that Clojure uses first and rest instead of car and cdr, as you can see if you look at the code for the turn function.

The final function we’ll look at is the one that holds it all together and runs the simulation in response to user input. The idea is that the user can enter a number of time-steps to process or just hit enter to process a single step. The original Common Lisp code looks like this:

(defun evolution ()
  (draw-world)
  (fresh-line)
  (let ( (str (read-line)))
    (cond ( (equal str "quit") ())
          (t (let ( (x (parse-integer str :junk-allowed t)))
               (if x
                   (loop for i
                      below x
                      do (update-world)
                      if (zerop (mod i 1000))
                      do (princ #\.))
                   (update-world))
               (evolution))))))

And my, not quite equivalent, Clojure code looks like this:

(defn parseInput [x]
  (try (Integer/parseInt x) (catch Exception e 0)))

(defn evolution [animals]
  (do 
    (draw-world animals @*plants*)
    (println) ; don't do 'print "\n"' or 'newline' as won't flush
    (let [line (read-line)] ;str is a function in clojure
      (cond (= line "quit") ()
        (= line "p") (do (println animals) (evolution animals))
        :else (evolution 
                (let [x (parseInput line)]
                  (nth (iterate update-world animals) (inc x))))))))

Again, there are variations caused by differences in the loop macro (here we use iterate instead) and my decision to keep the animals list immutable. Also, I didn’t implement outputting a “.” every 1000 steps. However, the most interesting change is in the way input is parsed. Clojure doesn’t have the parse-integer function, but I was quickly able to implement something that did the job by calling out to the Java parseInt method. If the parseInt method throws an exception, we just return 0 instead which will run the simulation for 1 time step. It’s worth noting how concise this bit of code is (how many lines would the equivalent Java be?).

Out of all of these differences, the most important ones are the Java integration and the support for concurrency, with intrinsic support for more types of collections somewhere slightly behind. The Java integration wasn’t forefront in this article, but I was able to use it to quickly create a parse method that did what I needed. Having a large, tested and useful library is one of the most important requirements for a general purpose language if it is to gain uptake with the average developer. The concurrency support also didn’t really come out in this article (although you were introduced to dosync and refs), but it seems to offer a relatively simple path to scalability; I hope to play more with Clojure’s concurrency model and see if this really is the case and see what sort of speed-up is possible at what cost to simplicity (possibly I’ll try to write an agent based version of the simulation à la Rich Hickey’s ants demo).

15 Responses to “Common Lisp, Clojure and Evolution”

  1. cgrand Says:

    Hi great write-up, some stylistic/idiomatic notes though:
    * each time you write something like (ref-set *plants* (disj @*plants* pos)) you should write (alter *plants* disj pos)
    * you shouldn’t introduce an animal struct, stick to plain maps — struct are already legacy and half deprecated — if later on you need something else use a record.
    * your loop in the definition of animals, should not be a loop, there are many ways to write that, one of them is (vec (repeatedly 8 #(inc (rand-int 10)))) — loop conveys no meaning because it is very general, loop should not be your default choice but your last choice when writing “something which loops”.
    * you have a concurrency bug in the eat function because the read is outside of the dosync, so there’s no guarantee the plant will still be there when you’ll eat it.
    * the loop in your evolution function can be replaced by (nth (inc i) (iterate update-world animals)) — when learning clojure try to stay away from loop/recur and lazy-seq

  2. cgrand Says:

    edit: (nth (iterate update-world animals) (inc i))
    (and not (nth (inc i) (iterate update-world animals))

  3. un.passant Says:

    @author : nice write-up, thx !
    @cgrand : thanks for for good advices on idiomatic clojure.
    why (nth (iterate update-world animals) (inc i)) and not (repeatedly (inc i) #(update-world animals)) ? (which btw seems to show the inconsistency that tripped you between nth and iterate :( )

  4. Tim Daly Says:

    What is notable here is not just the code but the style used to document the code.
    This “literate style” not only documents the differences but includes the motivations.
    If more software documentation were written to be read (as this is) we would have
    much more maintainable code. Consider using this article in the actual source files
    to document the code.

    Tim Daly

  5. cgrand Says:

    @un.passant contrast (take 8 (iterate inc 0)) and (repeatedly 8 #(inc 0)). The original loop was effectively calling update-world on the result of the previous iteration.
    Damn, enother edit on the same line, it should be:
    (nth (iterate update-world animals) (inc x)) ; with a x not a i

  6. lambdatronic Says:

    @un.passant The nth+iterate form is the correct solution here for two reasons:

    1) repeatedly will return a lazy sequence without evaluating it out to the nth value (which is required to simulate the looping construct the author is aiming for). iterate also sets up a lazy sequence, but nth forces its evaluation.

    2) Much more importantly, repeatedly will end up running update-world on the same animals list n times, which doesn’t properly move the world forward in steps. That is, each new run of update-world is the same as the first run, rather than building off of the outputs of the previous iterations. iterate passes the output of the kth update-world call on as the input to the (k+1)st iteration of update-world. Thus, the iterate function does what its name implies: iterates. repeatedly does what its name implies: repeats something in exactly the same way over and over.

  7. lambdatronic Says:

    @author:

    A few more stylistic/syntactic notes to add on what cgrand said:

    1) There is no round function in Clojure. You’ll need to replace (round x) with (Math/round (float x)).

    2) If you do still want to use structs here, use the struct-map form for greater readability. For example, your *animals* definition could be written like this:

    (def *animals*
    (list (struct-map animal
    :x (Math/round (float (/ *width* 2)))
    :y (Math/round (float (/ *height* 2)))
    :energy 1000
    :dir 0
    :genes (repeatedly 8 #(inc (rand-int 10))))))

    3) Destructuring binding really is your friend in Clojure. Use it liberally. This would have helped reduce your LoC quite a bit in both your move and eat functions. For example:

    (defn eat [{:keys [x y energy] :as animal}]
    (let [pos (list x y)]
    (dosync
    (when (contains? @*plants* pos)
    (alter *plants* disj pos)
    (assoc animal :energy (+ energy *plant-energy*))))))

  8. Anthony Grimes Says:

    Refs aren’t actually the only thing that can mutated in Clojure. Clojure has a whole host of concurrency primitives. You can even mutate plain ol’ Vars if you really, *really* want to.

    user=> (def foo 0)
    #’user/foo
    user=> (alter-var-root #’foo inc)
    1
    user=> foo
    1

  9. Adrian Says:

    @cgrand Thanks a lot, those look like good points, especially the loop stuff

    @Tim Daly, thanks; I believe all code should be commented or self explanatory.

    @Anthony Grimes: I am aware of vars, but fair point.

    @lambatronic: there is a round function in contrib, but otherwise those look like good points.

    I’ll have a look at refactoring the code.

    BTW, I’m really happy to receive such constructive comments, sometimes they seem the exception on the interweb!

  10. un.passant Says:

    @cgand @lambatronic : thx to both of you for clearing that up. You are part of make makes the clojure community so valuable.
    Best Regards

  11. Mike Says:

    As written, atoms would work better than refs for your plants. Atoms are the better choice for doing uncoordinated changes, as the atom-manipulating functions create their own transactions rather than needing to be inside a dosync. So updating plants would be (swap plants disj pos). However, fixing the concurrency bug in eat would require refs.

  12. Adrian Mouat Says:

    Thanks for all the suggestions.

    I’ve implemented most of them on github at https://github.com/amouat/Evolution-in-Clojure.

  13. ilan berci Says:

    This was a wonderful read, thank you kindly for posting it and please consider doing more. It’s quite fascinating to read how immutability causes fundamental design shifts when crafting in Clojure vs Common Lisp.

    What drove “struct” to deprecation? Was it because it causes a reduction in functional coupling or perhaps the focus around immutability makes ‘complex’ types unnecessary? I am very interested to know more.

    Thanks again.

  14. Adrian Says:

    Thanks Ilan,

    I don’t really know the reason for deprecating struct, but they are effectively replaced with deftype and defrecord to the best of my knowledge. In evolution, the code is actually a lot simpler if you just use plain maps.

  15. Adrian Mouat Says:

    @Antony Grimes, sorry I hadn’t realise I’d written that refs were the only thing in Clojure that can be mutated. I’ve updated the sentence.

Leave a Reply