Practical Applications Of Finite State Machines In Web Development

In my last post I described the basic State Machine/Theorem Prover developed in JavaScript – here is a recap, update and continuation of that post based on the latest development.

And BTW – This is my presentation for WebJam 08 Sydney Australia so if this post seems a little scattered its because its kind of half blog, half crib sheet for a 3 minute presentation.

JavaScript Finite State-Machine Engine

What is a Finite State Machine?

244px-Finite_state_machine_example_with_comments.svg

finite state machine (FSM) or finite state automaton (plural: automata) or simply a state machine, is a model of behavior composed of a finite number of states, transitions between those states, and actions. A finite state machine is an abstract model of a machine with a primitive internal memory. Source: Wikipedia

The state-machine is a formalised description of the possible states of a system. States are either ‘active’ or ‘inactive’.  My 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 and a legal ways for transitioning between those states.

The 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.

image

Each state has…

A list of passive 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 passive rules that describe how a state is affected by the activation of other states or the return from JavaScript calls.

A state can require that a state is active or inactive.

image

And require 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.

state can only be active if isInviteSent() returns true

A list of active 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.

When x has won, the game is over.

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.

When we transition to 'off' from 'on' then call some javascript.

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

When an O is placed at position 1,2 - we ensure that X can't be placed there and that this state can't change by locking it.

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

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.

image

image

image

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. Two Simple solutions soon.

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

image

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.

image

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.

image

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 issu
e 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.

image

image

So you say that’s really…. neat and BTW how is the Asperger’s treating you?… …but how can we use this in web development?

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.

Monty Python Sex Education Sketch From “The Meaning Of Life” 0:15 to (0:40 short) – (1:12 full)

Now, like me your probably written an application with a user interface that ends up after a few rounds of maintenance and changes 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 in the controller, however this is distributed throughout the source code files of the controller and there is no guarantee that you won’t end up dabbling in the Kafkaesque.

Two random images from the web describing Model View Controller

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.

Drawing3

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.

Aspect Orientated Views In JavaScript

Lets start with a simple HTML based template system which exposes something I can control with the state machine.

The basic thing we need to control is a View – so I recycled a JavaScript template engine system I built in late 2005.

I desired a system that enabled me to edit and compose the CSS and HTML without special tool chain or publishing or ingestion process slowing me down. Ideally wanted to allow people to use WYSIWYG editors or preview a template browser. Quick feedback for developing CSS.

I use a <span> inside of a <div>. Working on making this more compact. Can have multiple spans inside of a div to provide alternative view. At the moment the templating system prototype works on server side as well so I can strip out elements and send fragments back up from the server.

I built this about a year before AJAX.NET came out – but was thrilled that it did the same kind of fragment update. Obviously on the right track.

May end up with span only notation. At the moment this gives me more flexibility at the cost of forcing the developer to add <div>s at logical locations – which may or may not be a bad thing.

image

So I can see everything in the base view in activated state. If I want to edit in a particular state I play with CSS  to show hide what I want.

I want this aspect based and I want the aspects to cross multiple parts of a page and across views so I added aspects.

Eg  the Logged in aspect.

image

image

So if I turn on the aspect ‘loggedin’ these will show unless they are inside an aspect that is off. Aspects are hierarchical. Visibility obeys the laws of physics.

So consider this statemachine and in particular the part for managing the classical Web 2.0 Invite system.

image

So now we need to map between the states and the views

The 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.

A state can be mapped to a particular page – so if that state is true then it switches to that page/view.

A state can be mapped to an aspect. For this example check out the invite mappings. This is a very simple example – I only have three minutes! 🙂

image

Bringing it all together in an application. Template for the view. If you include the history iframe it will do the classic AJAX history tracking.

image

The function that starts it all.

image

Every time there is a key hit in the invite email input, we re-determine the current state.

image

When we re-determine the state the state machine definition knows that for the send invite button to be ready we need to return true from isInviteReady()

image

And that function simply returns true if there is a regex match on an the content of the invite email field.

image

And here is a Demo of it in action.

The End

James Mc Parlane https://blog.metawrap.com/

http://twitter.com/DrMiaow

Next Presentation At WebJam – Adding a dynamic Layout / Skinning engine to State/View engine.

Oh and BTW…

Massive Are Hiring HTML/JS/CSS Front End developers

Knowing XML/XSLT Is a bonus!

Mail work@massive.com.au

image

Advertisements

About metawrap

CTO Massive Interactive. Ex Computer Whiz Kid - Now Grumpy Old Guru.
This entry was posted in JavaScript, Massive, Web2.0, XML. Bookmark the permalink.

One Response to Practical Applications Of Finite State Machines In Web Development

  1. Nice writeup! Lots of interesting ideas generated in my brain, thanks! 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s