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!