I started writing this two years ago and never really got around to blogging about it. In a nutshell this is a module that runs within the MetaWrap JavaScript library that allows you to define a finite state machine in XML. The finite state machine can call out to JavaScript to check values and notify the application of state transitions.

This development is a follow on from my previous research into Parsing Theory and part of an ongoing interest in streamlining web development. I’ve recently started using the state machine for its intended purpose so after 18 months I’ve finally decided to dust it off and blog it 🙂

My thesis is, in a nutshell that as developers we often end up dealing with complex logical situations in a user interface that are best explained by this sketch from Monty Python’s The Meaning Of Life.

MR HUMPHREY: I begin the lesson, will those of you who are playing in the match this afternoon move your clothes down onto the lower peg immediately after lunch, before you write your letter home, if you’re not getting your hair cut, unless you’ve got a younger brother who is going out this weekend as the guest of another boy, in which case, collect his note before lunch, put it in your letter after you’ve had your hair cut, and make sure he moves your clothes down onto the lower peg for you. Now,–
WYMER: Sir?
MR HUMPHREY: Yes, Wymer?
WYMER: My younger brother’s going out with Dibble this weekend, sir, but I’m not having my hair cut today, sir. So, do I move my clothes down, or–
MR HUMPHREY: I do wish you’d listen, Wymer. It’s perfectly simple. If you’re not getting your hair cut, you don’t have to move your brother’s clothes down to the lower peg. You simply collect his note before lunch, after you’ve done your scripture prep, when you’ve written your letter home, before rest, move your own clothes onto the lower peg, greet the visitors, and report to Mr. Viney that you’ve had your chit signed.

Now, like me your probably written an application with a user interface that ends up with complex logic all over the place and a single change results in unpredictably strange consequences. As you make changes to this the code complexity grows. As developers, the best we have been able to come up with is MVC, which puts all that logic is all in the controller, however this is distributed throughout the code of the controller and there is no guarantee that you won’t end up dabbling in the Kafkaesque.

Ideally I want some way of

1. Describing a set of integrated rules in one location in a domain specific language.
2. Decoupling this description as much as possible from the the Views.
3. Allows those rules to be provable and enforced via contracts.
4. Allow the system to be intelligent enough that it exhibits emergent behavior via its logical roots, this emergent behavior can then be leaned upon and provide complex yet intuitive behaviors to users for free.

My aim was to break the controller up into a state machine based rules system and a layer that could mediate between the state and view.  The states could be mathematically provable with contracts ensuring that no illegal state combination could be entered.  Combining this with a direct mapping layer between states and views, could result in a lot of code being abstracted away into the state machine and result in a more compact code-base.

A state machine interrogates a model via user defined JavaScript functions.The state view map defines what views and aspects of the view should be visible and triggers their display.

JavaScript Finite State-Machine

The state-machine is a formalised description of the possible states of a system. States are either ‘active’ or ‘inactive’.  The state-machine is multi-dimensional (states have sub-states) and multi-state (more than one state can active).

The state-machine description consists of an XML file that describes a list of states.

A state machine description consists of a list of states.

Each state has a collection of sub-states which can only be active if their parent is active.

Each state has…

A list of rules for validating states which allow for a degree of asserting contracts between states.

A state can ‘exclude’ another state. Which is a way of saying that if this state is active then the other state should be inactive. If not, a fault will be indicated by an exception.

A state can ‘include’ another state. Which is a way of saying that if this state is active then the other state should also be active. If not, a fault will be indicated by an exception.

A list of rules that describe how a state is affected by the activation of other states or the return from JavaScript calls.

A state can ‘require’ some conditions to be met that another state is active or that a JavaScript function returns true. Any sub-state automatically requires its parent state. If you find a state requires only one or more states to be active then it should probably be a child of one of those states.

The reverse of ‘require’ is ‘unrequire’ such that the state will require a state to be inactive and expect called JavaScript functions to return false.

Can anyone think of an alternative to ‘require’ and ‘unrequire’. I’m seriously considering ‘canhas’ and ‘doesnotwant’ as they make as much sense as any other alternatives so far.

A list of rules that describe how a states can control that activation of other states.

A state can ‘negate’ a specified state in which case when the state becomes active it will try and make the specified state inactive.

A state can ‘affirm’ a specified state in which case when the state becomes active it will try and make the specified state active.

A list of triggers that are fired when the pattern of active states changes. The trigger is the call to a JavaScript function.

A trigger can fire when a states ‘enter’ (become active).

A trigger can fire when a states ‘exit’ (become inactive).

A trigger can fire when two specified states transitions ‘from’ or ‘to’ active/inactive between determining states.

A state can have a lock which forces it into its current state until the state machine is reset.

The state machine has the following public accessible JavaScript functions

MetaWrap.State.testState(stateName) – Returns true if the named state is active

MetaWrap.State.negateState(stateName) – Tries to set the named state to inactive then determines the new state and fires transitions. Returns true if state is ‘inactive’

MetaWrap.State.affirmState(stateName) – Tries to set the named state to active then determines the new state and fires transitions. Returns true if state is ‘active’

MetaWrap.State.flipState(stateName) – Flips the named the named state from active to inactive or visa versa. Returns true if state is was flipped.

MetaWrap.State.determineState()  – Calculates the current state. Called after changes to the model are made that may require the state machine to re-evaluate.’

JavaScript State Machine Examples

1. Toaster Example

NOTE – This won’t work in Safari or Opera.. yet. Neither of these browsers support client side XSLT. I’m working on a simple solution for this.

http://test.metawrap.com/javascript/tests/state/test_10_state.html

My first serious example was to model a simple toaster in a way that used most of the functionality of the state machine.

I wanted to model two classes of behavior.

The first are based on the explicit physical properties of the toaster (power on/off, bread in/out, lever up/down). I added the typical toaster behavior that you can’t push the lever down if the toaster is not on.

The second are based on the higher level states build up on the physical states, for instance if the power is on, the bread is in and the lever down, then the toast is cooking. I have also added the state where if you put the lever down after the toast has cooked, it will burn the toast.

1. Tic Tac Toe Example

I think it was Lela who suggested that I try and model Tic Tac Toe. So I sat down and defined the finite state machine.

NOTE – This won’t work in Safari or Opera.. yet. Neither of these browsers support client side XSLT. I’m working on a simple solution for this.

http://test.metawrap.com/javascript/tests/state/test_13_state.html

One pleasant surprise is that formally describing the states as a whole makes you think about them as a….. whole 🙂 . And the formal description can make some things obvious. For example. In the way I modeled Tic Tac Toe, it could be X’s turn or O’s turn.

And I set it up for one to deny the other (note that x_turn defaults to true, so X goes first).  This means in the JavaScript my code is nice and simple.

Once the game is over, who’s turn is it? There is a fault in my current model that became obvious after examination. I thought I was being clever by inversely relating x_turn and o_turn because it gave me a way of tracking the turn inside of the state machine which would then flip the current state.

However at the end of the game when I want to make it nobody’s turn, if I negate x_turn, o_turn becomes true and then when I negate o_turn, x_turn becomes true. I solved the issue by locking the turns.

I’m probably going to modify lock so that you can specify a value to lock it on and get it to suspend all further affirmations and negations down the chain, but I need to work out what the implications for that could be.

State View Map

The state view map is a formalised description of mappings from a state to a view and a set of aspects of that view.

A state view map  description consists of a list of states and the pages and aspects that should be visible.

This will be the topic of my next post.