Iterated Function Systems

An Iterated Function System (IFS) is a technique for creating fractal images. The name comes from the simple way in which they work. Start at an arbitrary point and colour it in, perform a transformation of that point to some new point. Colour that in and repeat until done. The translation function typically chooses between one of any number of choices. This is also called the Chaos Game.

The classic example if the Sierpinski Triangle (which incidentally has a much cooler Clojure implementation [using a different technique] in 3d here). My 2D rendering kind of pales in comparison!



This flavour of IFS is generated using a simple two dimensional affine transform. (this limits it to scale, rotation and translation, but not shearing transforms). The equation for this is shown below:



An implementation of this in Clojure is shown below. The formula above is expanded out in calculate-point



The second example draws a simple fern leaf pattern known as Barnsley's Fern.



The code to do the rendering uses a single agent to provide the animation (by repeatedly setting individual pixels). It's a bit yucky because I've no idea how to check the bounds of an arbitrary set of functions, so I make a guess by checking the first 10000 values to get an idea of min/max (get-bounds). The ugliness is compounded by the floor, abs and inc strategically located which get around the rounding errors. (big thanks to Hoeck from #clojure who suggested using take-while instead of the hideous gumph I had before which threw an exception to abort).



Obviously the time taken is dependent on how many equations are used, but images are generated very quickly. The get-bounds function on my box computes 10000 iterations of the Sierpinski set in 30 ms!

Full code available here in the misc folder.

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.