Flocking about with Clojure

Emergent behaviour describe the way complex behaviours emerge from simple rules.

Conway's Game of Life is a good example. Just a handful of simple rules about how to behave in the presence of neighbours result in really complicated behaviours. Visualizing Conway's Game of Life has some great examples.

Nature provides even better examples such as flocks of birds or shoals of fish. How do these behaviours emerge? Computer simulations can simulate a similar effect by just following a few simple rules. The classical paper was written by Craig Reynolds who presented at SIGGRAPH three simples rules to allow flocking behaviour to emerge:

1. Collision Avoidance - members of the flock don't like flying/swimming into each other!
   
2. Velocity Matching - members of the flock tend to fly together at the same speed
   
3. Flock Centering - stay close to members of the flock
   

Modeling this in Clojure gives me a chance to get a bit more familiar with agents. Agents provide a way to get independent asynchronous access to state. An agent is bound to some state (e.g. a Clojure data structure). Data is manipulated by sending messages (functions) to the agent.

To get some flocking behaviour, we'll model each member of the flock (a boid, after the paper) as an agent. Each agent has some state (a position and a velocity). Messages will be sent to the agents corresponding to the rules above. A single agent will be used to manage the animation thread.



(I realize an animation would be much better, but all the desktop recording software I tried, gtk-recordmydesktop, didn't get a high enough frame rate to make it worth recording!)

The code for the behaviours is shown below (it's missing a few helper methods here and there, but see Clojure Projects for the full version).



The behaviours are as simple as they can be. Big thanks to kfish for a nice lucid explanation of how to implement this!

The animation loop is an agent with no state whose only job is to make the other boids behave, by sending them the appropriate message. This is all rendered within a subclass of JPanel which has a custom paint method.



The code is nice and simple, and easy to play with and extend. The behaviours can be mixed and matched to show all sorts of crazy effects (for example, with just cantering and separation behaviours the flock tends to go into a crazy implode/explode cycle!). Further extensions could be:

• Have separate flocks (they avoid each other, but follow the same rules within each other)
  
• Three dimensions (more or less exactly the same maths)
  
• Sphere of Influence (at the moment each boid affects every other, perhaps it should only be within a certain area)
  

It makes a good example of the power of agents and STM. There's no threading problems whatsoever, all I need to do is take a consistent view of the boids each time I go to draw them (and STM provides that for free).

STUDENT

After adventures with Google Wave, back to PAIP. Next on the list is understanding and implementing the STUDENT problem solving system. The abstract of Daniel Bobrow's thesis is shown below:

The STUDENT problem solving system, programmed in LISP, accepts as input a comfortable but restricted subset of English which can express a wide variety of algebra story problems. STUDENT finds the solution to a large class of these problems. STUDENT can utilize a store of global information not specific to any one problem, and may make assumptions about the interpretation of ambiguities in the wording of the problem being solved. If it uses such information or makes any assumptions, STUDENT communicates this fact to the user.

On a side note, being at MIT in the 60's must have been amazing. The acknowledgements name Noam Chomsky, Marvin Minksy, Seymour Papert and Herbert Simon. Wow!

STUDENT consists of two parts. Linguistic analysis (pattern matching) is used to break the sentences into equations. The second part is simply solving those equations. This can be thought of as the precursor to systems like Wolfram Alpha. The Linguistic Analysis searches for certain patterns (kernel sentences). This pattern matching is expressed very simply using the pattern matching tools discussed previously. PAIP makes heavy use of symbols which means you need to learn how to escape. Clojure uses , as a symbol so if you want to put it in a pattern you need to use a back quote and use a ~ to evaluate the inner bit. For example:

`[~[(list 'if '?x* (symbol ",") 'then '?y*) '(?x ?y)]]

Constraint Propagation is a problem solving technique that relies on logical inference, not search. A good example would be Sudoku. Placing a number in a square places constraints on the other square (e.g. once you've put a 1 in a row, no other number in that row can be a 1). There's a good description of using constraint propagation to solve Sudoku here.

The equation solving part of Norvig's implementation of STUDENT is a good example of making a complex sounding problem simple. The algorithm for solving a list of equations is dead simple and the Clojure code itself explains it well.



Find an equation with one unknown, isolate the unknown, substitute and repeat until solved. Isolate itself is a simple rule based approach to isolating a variable on one side.



So how does this constraint propagation work?

(solve-equations '((= (+ 3 4) (* (- 5 (+ 2 x)) 7))
(= (+ (* 3 x) y) 12)))

From the list of equations we figure that the first equation has a single unknown, x. This is isolated by repeatedly applying the simple rules until we determine x is 2. This is then replaced in the second equation and the results returned.

One big difference between my Clojure implementation and the ANSI Common Lisp is the use of the struct to represent the expressions. I (foolishly!) represented mine with named keys which made life very painful. Lisp's defstruct is more powerful than Clojure's because it supports more representations. For example, you can choose whether you want a list or hash representation; in my case I went for hash in Clojure (that's the only choice), but that was painful. This could be addressed by defining a better defstruct for Clojure.

Google Wave and Clojure

Google Wave is an attempt to reinvent communication and collaboration on the web. Or, it's just a web site where you can share information, with a documented protocol and an API for extensions. Google wave consists of three pieces:

1. The User Interface (Google Wave Client application)
   
2. The Programming Interface (Google Wave APIs)
   
3. The Communication Protocol (Google Wave Federation Protocol)
   

A wave is a conversation which may include both human and computer participants. The wave stores state and maintains historical information. Participants can modify the wave in real-time. A wave contains one of more wavelets.

A wavelet is a threaded conversation spawned from a wave. A wavelet contains one or more messages, also known as blips. A wavelet spawned from a wave is an independent entity with it's own access control. This means, for example, you could spawn off a side conversation bemoaning your PHB and safely (hopefully) keep that wavelet under wraps.

A blip is the basic unit of conversation and consists of a single message (or interaction event) that appears on a wavelet. Blips can be stored as a draft before being published. Each wavelet always consists of at least one root blip. Finally, a document represents the actual content of a blip. This is in XML format which can be retrieved, modified or added to by the API. Documents are typically managed through an API rather than direct XML manipulation.

You can interact with the Wave API by extension or integration.

One of the ways to extend Google Wave is via a Robot. A Robot is an automated participant on a wave. A robot has exactly the same rights as any other participant in a wave. For example, a robot can modify information in a wave, talk with other participants and communicate details to the outside world. A robot communicates using the Wave Robot HTTP protocol (which is currently undocumented). For now, the only way in which a robot can be created is to build one using the Google App Engine. Now that GAE supports Java we've already seen how easy it is to write a Google App using Clojure, so it should be pretty simple to write a basic Wave Robot in Clojure.

The first step is to create and register with Google App Engine (see http://appengine.google.com). A Google Wave robot is basically exactly the same as a GAE application. A robot is represented as a standard servlet. The directory structure used is almost exactly the same as that described here.

Project Root
|-build.xml   
|-src/
|-war/
  |- WEB-INF/
     |- app-engine.xml
     |- web.xml
     |- lib
  |- _wave
     |- capabilities.xml

As it involves Java, there's a pretty heavy amount of XML involved. We'll pretend that doesn't exist for the moment and look at the basic implementation of a robot.



This is the "parrot" example from the Google Wave Robots Java Tutorial. It monitors events and when participants join or leave utters a really exciting greeting. processEvents is the event loop for robots. In this case we just filter out the interesting events (me joining a conversation, or people joining a conversation I'm in) and spout out some gibberish.

Back to the XML files. The tutorial explains them better than I can, but in short:

• capabilities.xml - what your robot can do, versioning
  
• web.xml - servlet mappings
  
• appengine-web - name and version information of your application.
  

Examples of all these files and the directory structure is available here. Using this and the SDK to deploy you can get your robot up and running in the Google wave sand box.



So do I think Google Wave is going to change the way we communicate? It's (obviously) too early to tell. If it becomes integrated within standard email clients, allows me to mix mediums (e.g. Twitter, Facebook, email, IM, voice mail) and so on, then it has the potential to unseat email. There's some big questions too. How will robots be regulated? How will you stop spam becoming a nightmare? (you should see Eliza dishing out advice!). Exciting times ahead though!

Parsing Logs with Map/Reduce

Map/Reduce is a software pattern for processing large data sets. It's been popularized by Google, and has now inspired other frameworks, such as Hadoop and CouchDB.

Map/Reduce is based on two very simple functions. Map simply converts values from one domain to the other. reduce (also known as fold) takes a sequence of values and converts them into a single value. For example (reduce + [1 2 3 4 5]) translates to 1 + 2 + 3 + 4 + 5. Distribution is simple to achieve for map because it is functional (no side effects, translating one value doesn't affect any other). Reduce usually operates on particular keys, allows the results to be computed in parallel (though this depends on some logic when distributing workloads).

I recently had to parse some log files and get an idea of the distribution of some timing information. Usually, I'd knock together a Perl script or just use Excel, but I thought I'd try it with a "functional programming" slant with Clojure.

The log file was in the following format.

  Event 23435 
  3.4
  Event 23511
  32

And so on. The actual events are of no consequence, I just wants to get an idea of what the distribution was like. Using clojure.contrib.duck-streams file reading is very simple (read-lines returns a lazy sequence of lines from the file).


(map second (partition 2 (read-lines filename)))


(update: Alternatively (take-nth 2 (drop 1 (read-lines filename)) does the same thing and feels nicer).

This returns a lazy list of all the timing information. Now all I need to do is get a distribution. All we do is use reduce to build up an association between the value of each element (floored to be within a range) and the number of times it occurs. The code below bunches it up into 10 second chunks and counts the occurrences of each.



Less than 10 lines of code to produce a histogram of a silly log file format. And using Map/Reduce, I could scale exact same example up to run on hundreds of gigabytes of data on huge clusters of computers.

This is exactly why, as a software developer, you should be excited about programming languages (not just functional programming!). The quote below is from Joel Spolsky and sums it up well.

Without understanding functional programming, you can't invent MapReduce, the algorithm that makes Google so massively scalable. The terms Map and Reduce come from Lisp and functional programming. MapReduce is, in retrospect, obvious to anyone who remembers from their 6.001-equivalent programming class that purely functional programs have no side effects and are thus trivially parallelizable. (The Perils of Java Schools)

Pattern Matching Tools

In order to implement the STUDENT program, we first need a more advanced series of pattern matching tools. Chapter 6 of PAIP generalizes the pattern matching tools we saw in Eliza (see here).

The idea is that matching is extended to be customizable. The algorithm is presented in a "data-driven programming" manner. Each pattern (such as is, or, and, not, if) is associated with a corresponding function that does the work. It's a very extensible system because if we want to add an extra pattern, we just add an entry to the table and the job is done. This is a common theme throughout the book so far, and it's slowly beginning to sink in!

The Common Lisp version uses symbol properties to associate data with symbols. To my knowledge, Clojure doesn't support this (please correct me if I'm wrong!), so I modelled this as a simple associative structure with lookups based on the symbol name.



Most of the other functions were pretty trivial to port across to Clojure, but progv presented some problems. progv is a special operator which creates special bindings. This effectively allows you to inject additional environment into a lump of code you want to evaluate. For the match-if function, the Common Lisp code looks like this:



This effectively makes bindings available to the item that you want to fiddle with. From some of the comments on Critiquing Clojure it looks like there may be a better way of doing this, than the hacky way I've done it. I simply replaced all occurrences of the variables (?var) with the appropriate bindings. On the way, I discovered the oddly named postwalk-replace which traverses deeply into a structure and replaces using a provided map. (note that this is in no way the same as progv because it's just search and replace and doesn't handle the fact that someone could declare a variable overwriting the bindings).



You can find the complete source for the pattern matching chapter of PAIP on my Clojure Projects github page.

Merging RSS Feeds

In order to investigate XML parsing in Clojure I knocked up a quick utility to aggregate RSS feeds. The idea is that a user provides a number of URLs, runs the program and a merged RSS feed is returned, sorted by publish date.

Firstly, let's write a trivial function to join any number of lists together according to a selection function. This will be used to merge together the XML by selecting the minimum published date each time.



The function f should be a function of two arguments that returns one of the arguments. For example:

  user> (join-all min [1 2 3] [1 1 3])
  (1 1 1 2 3 3)

  user> (join-all min [2 4 6 8 10] [1 3 5 7 9])
  (1 2 3 4 5 6 7 8 9 10)

Next, we want some utilities to mess around with RSS format and select various XML elements. Clojure Contrib provides a lazy xml package, together with some utilities to make XML zip filtering easier (I previously looked at zip filtering here).

Since the examples for clojure.contrib.zip-filter.xml already use RSS this is really trivial:



Note that the code above already handles URLs (if the supplied type to parse-trim is a URI then this is resolved, retrieved and parsed. Finally, all we need to do is put it together:



Comparing XML dates is very tiresome in Java because it's supplied date/time libraries are painful. Thankfully, Joda Time provides a solution (see here for a description of the best way to parse a date time).

Searching Graphs

Continuing from the previous post, Finding the Target, it's now time to focus on the basic graph searching algorithms introduced in Chapter 6 of PAIP.

The major difference between searching a graph and searching a tree is that a graph may contain cycles. If you're not careful you'll end up in a infinite loop, constantly searching the same cycle. graph-search handles this by keeping track of old states and defining an equality function that allows you to customize the way two states are considered equal (for example, in a board game, states may be equal if they are rotations of each other). new-states generates successors that haven't been seen before.

This code compares quite well with the ANSI Common Lisp code in PAIP, not needing to use funcall simplifies the code a little, and fn instead of lambda is less verbose. The implementation of A* search below doesn't fair so well!

The A* Search algorithm is a best-first graph search algorithm based on the heuristics you supply. Paths with the least cost so far are explored first. The code below gives an implementation heavily based on the one in PAIP. The code feels butt-ugly and I think this is due to the mutable state that I've ported over from the original. There's almost certainly a nicer functional implementation in there somewhere!



So how can we see what the A* search is doing? I wrote a quick maze algorithm to visualize which is shown in the image. The app uses the A* algorithm to find a route from the top-left to the bottom-right, avoiding the black walls. It's is interactive, left clicking builds a wall, left clicking again destroys it. Right-clicking solves the maze if possible, and shows the shortest solution in pink.



The complete code can be seen in my Git repository. There's a really nice Javascript visualization out there if you don't fancy building the Clojure code.

Finding the Target

I've been steadily working my way through Paradigms of Artificial Intelligence Programming which I am thoroughly enjoying. This time round it's time to look at simple search algorithms. Norvig introduces all the traditional tree search algorithms based off a single function shown below:



From this basic algorithm we can express two simple tree search algorithms, depth first and breadth first.



For depth-first, we simply follow one branch of the tree until it matches the goal or fails to complete. The combiner function puts the next node to be searched at the front of the list of states so that we always follow paths to completion. Depths first search can have problems when the structure to be searched is infinite, as it will blindly follow a path forever. Breadth-first works by exploring all paths at the same level. Breadth-first search doesn't suffer from the same infinite search problem as depth-first search, but it's potentially slower because it is covering each and every node. Both depth and breadth based searches have the same fundamental disadvantage, they don't have any knowledge about the state space and just methodically follow the same pattern regardless of the search.

Best-first search chooses the successor nodes to search first by searching on the results of a cost-function.



This will still visit all the nodes, but the choice of what to search next is based on the cost function. If the cost function is right, then best-first-search can be significantly better than depth or breadth first searching. Beam search is an optimization of best search that forgoes the requirement of searching every node. Instead only a fixed number of alternative states (the beam width) are considered.



The advantage of this is lower memory requirements and that the nodes that the beam width covers can be searched deeper. However, if the beam width is too small, then this search algorithm can fall into the trap of endlessly searching down the wrong path.

To illustrate these search algorithms, we'll use the ridiculous example of the game of darts. Briefly, Darts is played by drinking vast quantities of alcohol and then trying to throw darts at a board. You score points between 1 and 20 (either normal, double or triple), and there's also a outer bull (25) and an inner bull (50). You start from 501, and try to get to zero as quickly as possible, with the caveat that the last dart you throw should be a double or a bulls-eye.

The code below models darts as a series of throws:



Now we can use this with the search algorithms described above.

From the descriptions, you'd expect breadth and depth first search to find the right solution, but be a bit rubbish about doing so. Because they have no idea of the means to get to the goal, they'll just chuck darts about randomly and eventually weave their way to a solution. And indeed they do.



Solving the game of darts using depth-first search from 501 is not ideal! The first branch is happens to explore is the contains 1, so the search repeatedly throws 1's until it's not a legal move. Not good!

uk.co.fatvat.search> (count (:throws (solve-darts-depth-first 501)))     
500

Let's see if beam search can do any better:



The cost function models it as however close we are to zero divided by the number of throws of the data. The goal should be to get to the finish as quickly as possible.

uk.co.fatvat.search> (:throws (solve-darts-beam-search 501))
[441 381 321 261 201 141 84 30 0]    

We can see that this does achieve the perfect 9 dart finish. (T20,T20,T20,T20,T20,T20,T19,T17,D15). Finishing from 1000001 will apparently take 16667 darts!

The approach described in the book is very clear. The key realization for me was that you don't have to have the entire state space in memory at once for a tree algorithm to succeed; you just need to think in terms of the next step to take.