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.
What is a Finite State Machine?
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.
Each state has a collection of sub-states which can only be active if their parent is active.
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 state can require that a state is active or inactive.
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.
A list of triggers that are fired when the pattern of active states changes.
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.
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.’
NOTE This wont work in Safari or Opera.. yet. Neither of these browsers support client side XSLT. Im working on a simple solution for this.
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 cant 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.
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 wont work in Safari or Opera.. yet. Neither of these browsers support client side XSLT. Two Simple solutions soon.
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 Xs turn or Os turn.
Once the game is over, whos 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.
Im 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.
So you say thats really . neat and BTW how is the Aspergers 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,–
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
- Describing a set of integrated rules in one location in a domain specific language.
- Decoupling this description as much as possible from the the Views.
- Allows those rules to be provable and enforced via contracts.
- 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.
Lets start with a simple HTML based template system which exposes something I can control with the state machine.
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.
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.
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.
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! 🙂
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.
The function that starts it all.
Every time there is a key hit in the invite email input, we re-determine the current state.
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()
And that function simply returns true if there is a regex match on an the content of the invite email field.
And here is a Demo of it in action.
James Mc Parlane https://blog.metawrap.com/