March 11, 2014

Clojure's Eval

As a Clojure beginner, I’ve had a number of Bad Ideas™. One of these bad ideas involved the use of eval to create a genetic algorithm.

Two weeks ago, my project was a genetically-evolving Mancala-playing bot with a similar strategy to John Ahlschwede’s bot. He chose to represent his bot as a tree of operations, where there are numbers at the tips of the tree, operations to add numbers, subtract numbers, and get the number of seeds in a house whose ID is some number. The operations and numbers on the tree are evaluated, and the bot’s move is whichever number pops out at the top of the tree, mod 5.

The concept of a tree of operations mirrors Clojure’s structure very closely, and I’d heard of Clojure’s useful metaprogramming facilities. My thought was to simply represent the bot’s tree as a tree of code in Clojure. For instance, John’s example tree above would be represented like:

'(+ (- 9 8) (nth board 3))

Then, I could genetically evolve these trees, and use Clojure’s magical macros to pull numbers out of them. “Hahaha,” I thought, “this will be easy!”

I soon realized a critical problem, which is probably obvious if you aren’t a Clojure beginner like me. Clojure macros are evaluated at compile time. They’re useless if you want to change the structure of code after the compiler has finished compiling, which is exactly what I was hoping to do. So how could I evaluate these bots, while still being able to modify them at runtime? That’s when I came across eval. It would let me evaluate the bots, while still keeping the bots as a modifiable, evolvable list.

(let [board [3 3 3 3 3 3 0 3 3 3 3 3 3 0]]
  (eval '(+ (- 9 8) (nth board 3))))

However, the code above won’t run. eval runs the contents passed to it in a different scope, which means it can’t access the local board. So we can wrap our bot with a function…

   '(fn [board] (+ (- 9 8) (nth board 3))))
 [3 3 3 3 3 3 0 3 3 3 3 3 3 0])

Although this code is both working and kinda…interesting, I ultimately decided that using and dealing with eval was more trouble than it was worth, especially considering various bugs and complains that I’ve found on the internet, not to mention that it’s more difficult to debug. It’s just not considered a good practice. So, I changed the bots to have a structure more like the following:

[:add [:sub 9 8] [:val 3]]

With a structure like this, writing an interpreter with a recursive function is pretty simple.

(defn eval-bot
  "Evaluate a statement from a bot"
  [board bot]
  (if (number? bot)
    (condp = (first bot)
      :add (+ (eval-bot board (nth bot 1)) (eval-bot board (nth bot 2)))
      :sub (- (eval-bot board (nth bot 1)) (eval-bot board (nth bot 2)))
      :val (nth board (eval-bot board (nth bot 1)))
      :rand (rand-int 6)
      (first bot))))

The code above recursively evaluates a bot to get its move. :add adds two numbers, :sub subtracts numbers, :val gets the number of seeds at a position, and :rand returns a random number between 0 and 5. I’m pretty sure this system is cleaner than using eval, and, since it has a limited number of functions, is hopefully less likely to gain sentience and take over the world.