State Machines described and a few examples
State machines part nine
Around this time last year I started publishing a series of entries about state machines and workflows. The topic has recently resurfaced in a couple areas. There's clearly more that I want to say.
What interested me last year was all the various places I was seeing state machines and workflows. Looking over it a year later I notice a glaring omission: I wrote everything with the assumption that the reader knows what a state machine is and how to code one. Let me now drop that assumption and briefly describe state machines.
The Gang of Four explain that the state pattern allows an object "to alter its behavior when its internal state changes." [Design Patterns p.305] That's about as succinct as it gets. I personally needed a bit more explanation.
They offered two example applications of the state pattern: a TCP connection object and the different drawing tools in graphics applications like Photoshop or Illustrator. In Agile Software Development Bob Martin offered a couple other examples: a turnstile and a comment parser.
All of these examples have an object which moves through a finite collection of states, responding to a specific set of events. The behavior in response to the events is different depending on the current state of the object. The turnstile is the simplest of these examples to explain. I'm just paraphrasing Bob Martin's story here. That book is exceptional and his explanation of state machines is really worth your time.
The turnstile takes two events: you either drop a coin in it, or you try to pass through it. Call the events 'coin' and 'pass'. It also has only two states: locked and unlocked. When it's locked the 'coin' and 'pass' events invoke different behavior than when it's unlocked. When locked 'pass' will sound an alarm and 'coin' will change the state to unlocked. When unlocked 'coin' should trigger a refund of the coin and 'pass' should change the state to locked. Different behaviors depending on the state.
How this might look in Java:
public class Turnstile {
State state;
public Turnstile {
state = new Locked(this);
}
public void coin() {
state.coin();
}
public void pass {
state.pass();
}
}
public interface State {
public void coin();
public void pass();
}
public class Locked implements State {
private Turnstile t;
public Locked(Turnstile t) {
this.t = t;
}
public void coin() {
t.state = new Unlocked(t);
}
public void pass() {
throw new FreeloaderException("Come back here!");
}
}
public class Unlocked implements State {
private Turnstile t;
public Unlocked(Turnstile t) {
this.t = t;
}
public void coin() {
//refund coin
}
public void pass() {
t.state = new Locked(t);
}
}Bob also suggests using a state transition table to sketch out the different states and their events:
Turnstile state event result Locked coin set Unlocked Locked pass sound alarm Unlocked coin refund coin Unlocked pass set Locked
In his state machine compiler he offers a more formal syntax for a state transition table to define states and events and results. It can then be compiled into a pile of objects similar to what I sketched above. I've already exclaimed about how cool I think that trick is in State Machines and Agile Software Development. In that entry, you'll also find an example of the config file for the Turnstile state machine.
I won't cover the other examples in as much detail. The TCP connection has to respond to open, close, and acknowledge events differently depending on whether the connection is established, listening, or closed. The drawing tools have to respond to mouseup, mousedown, and mouse position events and do different things to the drawing depending on which tool is selected (or what state the palatte is in). The comment parser responds to a stream of characters and changes states depending on whether it is in an inline comment, a comment block or whathaveyou. Hopefully those few examples give a sense of how widely applicable the state pattern can be.
As a web developer, I'm particularly interested in how state machines can model web applications. You have GETs and POSTS and PUTs and DELETEs as the collection of events. The URL and cookies describe the current state. New requests change the state of the application for the user. You can use a state transition table to describe the navigation and flow through the application. If you're familiar with Struts, you can kinda squint your eyes and see a state transition table in the struts-config.xml file. Unfortunately, struts mixes the concerns of the navigation with actions that change the model. It's sorta like mashing the 'event' and 'result' columns together in the state transition table I showed above. It looks like WebWork2 does this better and like JSF will too. Of course these days I'm partial to bOP.
The Wikipedia has some useful, though more formal entries:
Chris Winters commented
Here's a useful workflow patterns site: http://tmitwww.tm.tue.nl/research/patterns/patterns.htm
It also may be worth noting that I recently published on CPAN the Workflow module. It's very simple and missing lots of features, but I figured it would be useful to get a generic framework out there rather than have everyone rewrite it for their own apps. (This seemed to be the consensus at YAPC as to why there wasn't a workflow module already on CPAN -- everyone just makes a new custom workflow system with every large app they create.)