Archive for February, 2011

Common Lisp, Clojure and Evolution

Sunday, February 27th, 2011

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)
              (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))
    (setf (animal-y animal) 
        (mod (+ y
                    (cond ( (and (>= dir 0) (< dir 3)) -1)
                           ( (and (>= dir 4) (< dir 7)) 1)
                           (t 0))
    (decf (animal-energy animal))))

And my Clojure looks like:

(defn move [{:keys [x y dir] :as animal}]
    {:x (mod (+ x
               (and (>= dir 2) (< dir 5)) 1
               (or (= dir 1) (= dir 5)) 0
               :else -1)) ; note clojure has else form and less ()s
      :y (mod (+ y
             (cond (and (>= dir 0) (< dir 3)) -1
               (and (>= dir 4) (< dir 7)) 1
               :else 0))
      :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)]
      (if (contains? @*plants* pos)
          ; get rid of the plant first
          (alter *plants* disj pos)
          ; so we can return the updated animal
          (assoc animal :energy (+ energy *plant-energy*)))

(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 ()
  (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 #\.))

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

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

(defn evolution [animals]
    (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).