Playing With Finite State Machines And ColdFusion Components
A couple of months ago, at the jQuery NYC meeting, one of the attendees (his name escapes me at the moment) talked about using finite state machines to develop Javascript widgets. I haven't dealt with a state machine since my undergrad computer science studies. As such, I thought it would be something worth looking into in case I might see how it could best be applied to future application development.
While he (and the tutorial he referenced) talked about using state machines in the context of Javascript, I don't see why the concept could not be applied to any object that maintains an internal state. As such, I figured I would experiment with state machines using ColdFusion components. I decided to use a Person as an object that maintains internal state and updates that state based on relevant events.
Before I could start coding, though, I needed to figure out what states and events I was going to model in this Finite state machine. While drawing state machines as a graphic with circles and lines is great for visualizing workflow, using a state table is much more effective for development. For my experimentation, I decided to model three states: Indifferent, Bored, Excited, and three events: Nice, Rude, Boring. The following state table explains how transitions are made from one state to another:
Taking this state table, I then created my Girl.cfc ColdFusion component. Within this component, the event handlers are named to reflect the current state of the machine and the event being handled. So, for example, if the Girl was in the current state "Bored" and was currently handling the event, "BeNice", the event would be handled by the class method:
Girl::doBored$BeNice()
There's nothing that requires this naming convention - it was simply my adaptation of the nested structures outline in the IBM tutorial. Each of these event handler methods alters the data stored within the component and then returns the name of the resultant state. In the following code, you will see that each of these event handlers is invoked internally by a single event handler, handleEvent(), and it used to update the state of the component.
Girl.cfc
<cfcomponent
output="false"
hint="I am the state-machine representation of a Girl (not to say that they are predictable... not to say that they are completely irrational either... look, just go with it, OK??).">
<cffunction
name="init"
access="public"
returntype="any"
output="false"
hint="I initialize this component.">
<!--- Set up the internal properties. --->
<!--- I am the current state. --->
<cfset this.currentState = "Indifferent" />
<!---
I am the mood - the numeric representation of the
current state. Zero will always be the middle of
indifference.
--->
<cfset this.mood = 1 />
<!--- I am the cap to how excited this girl can get. --->
<cfset this.moodMax = 10 />
<!---
I am the threshold over which this girl cannot be
considered bored.
--->
<cfset this.indifferentThreshold = -2 />
<!---
I am the threshold over which this girl cannot be
considered indifferent.
--->
<cfset this.excitedThreshold = 3 />
<!--- Return this object reference. --->
<cfreturn this />
</cffunction>
<cffunction
name="handleEvent"
access="public"
returntype="void"
output="false"
hint="I handle the given event (NOTE: For testing purposes, we are relying on the outside environment to define the Type of event).">
<!--- Define arguments. --->
<cfargument
name="eventType"
type="string"
required="true"
hint="I am the type of event being executed."
/>
<cfargument
name="eventData"
type="any"
required="true"
hint="I am the additional event data being passed-in."
/>
<!--- Define the local scope. --->
<cfset var local = {} />
<!---
Build the name of the event handler that we want to
use for this event. This is based on the current state
and the incoming event. This will be in the form of:
this.do[state]$[eventType]()
--->
<cfset local.eventHandler = (
"do#this.currentState#$" &
arguments.eventType
) />
<!---
Check to see if given method could be found. If not,
then we'll have to use the unknown event handler.
--->
<cfif !structKeyExists( this, local.eventHandler )>
<!---
Event type is unrecognized - use the unknown
event handler.
--->
<cfset local.eventHandler = "doUnknown" />
</cfif>
<!---
Pass execution off to the event handler and store
the result into the current state.
--->
<cfinvoke
returnvariable="this.currentState"
component="#this#"
method="#local.eventHandler#"
/>
<!--- Return out. --->
<cfreturn />
</cffunction>
<cffunction
name="updateMood"
access="public"
returntype="numeric"
output="false"
hint="I increase or decrease the mood by the given value, enforcing internal constraints.">
<!--- Define arguments. --->
<cfargument
name="delta"
type="numeric"
required="true"
hint="I am the delta (plus or minus) if the current mood."
/>
<!--- Alter the internal mood. --->
<cfset this.mood += arguments.delta />
<!--- Enforce contraint. --->
<cfif (this.mood gt this.moodMax)>
<!--- Limit to upper bounds. --->
<cfset this.mood = this.moodMax />
</cfif>
<!--- Return the current mood. --->
<cfreturn this.mood />
</cffunction>
<!--- ------------------------------------------------- --->
<!--- ------------------------------------------------- --->
<cffunction
name="doIndifferent$BeNice"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Increase the mood. --->
<cfset this.updateMood( 1 ) />
<!---
Check to see if the mood is greater than the
excitement threshold.
--->
<cfif (this.mood gte this.excitedThreshold)>
<!--- This girl is now excited. --->
<cfreturn "Excited" />
<cfelse>
<!--- This girl is still indifferent. --->
<cfreturn "Indifferent" />
</cfif>
</cffunction>
<cffunction
name="doIndifferent$BeRude"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Decrease the mood. --->
<cfset this.updateMood( -1 ) />
<!---
Check to see if the mood is less than the
indifferent threshold.
--->
<cfif (this.mood lt this.indifferentThreshold)>
<!--- This girl is now bored. --->
<cfreturn "Bored" />
<cfelse>
<!--- This girl is still indifferent. --->
<cfreturn "Indifferent" />
</cfif>
</cffunction>
<cffunction
name="doIndifferent$BeBoring"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!---
At this state, being rude and being bored are pretty
much the same thing to this girl. Therefore, just use
the existing state transition.
--->
<cfreturn this.doIndifferent$BeRude() />
</cffunction>
<!--- ------------------------------------------------- --->
<!--- ------------------------------------------------- --->
<cffunction
name="doBored$BeNice"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Increase the mood. --->
<cfset this.updateMood( 1 ) />
<!---
Check to see if the mood is greater than the
indifferent threshold.
--->
<cfif (this.mood gte this.indifferentThreshold)>
<!--- This girl is now Indifferent. --->
<cfreturn "Indifferent" />
<cfelse>
<!--- This girl is still bored. --->
<cfreturn "Bored" />
</cfif>
</cffunction>
<cffunction
name="doBored$BeRude"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Decrease the mood. --->
<cfset this.updateMood( -2 ) />
<!--- This girl is still bored. --->
<cfreturn "Bored" />
</cffunction>
<cffunction
name="doBored$BeBoring"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Decrease the mood. --->
<cfset this.updateMood( -1 ) />
<!--- This girl is still bored. --->
<cfreturn "Bored" />
</cffunction>
<!--- ------------------------------------------------- --->
<!--- ------------------------------------------------- --->
<cffunction
name="doExcited$BeNice"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Increase the mood. --->
<cfset this.updateMood( 1 ) />
<!--- This girl is still Excited. --->
<cfreturn "Excited" />
</cffunction>
<cffunction
name="doExcited$BeRude"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!---
Decrease the mood. When this girl is excited, being
rude is particullarly offensive.
--->
<cfset this.updateMood( -5 ) />
<!---
With this drastic jump, we will need to check to see
if the girl crossed various states.
--->
<cfif (this.mood gte this.excitedThreshold)>
<!--- This girl is still excited. --->
<cfreturn "Excited" />
<cfelseif (this.mood gte this.indifferentThreshold)>
<!--- This girl is now Indifferent. --->
<cfreturn "Indifferent" />
<cfelse>
<!--- This girl is now bored. --->
<cfreturn "Bored" />
</cfif>
</cffunction>
<cffunction
name="doExcited$BeBoring"
access="public"
returntype="string"
output="false"
hint="I handle the given event and return the next state.">
<!--- Decrease the mood. --->
<cfset this.updateMood( -1 ) />
<!---
Check to see if the mood is greater than the
excited threshold.
--->
<cfif (this.mood gte this.excitedThreshold)>
<!--- This girl is still Excited. --->
<cfreturn "Excited" />
<cfelse>
<!--- This girl is now indifferent. --->
<cfreturn "Indifferent" />
</cfif>
</cffunction>
<!--- ------------------------------------------------- --->
<!--- ------------------------------------------------- --->
<cffunction
name="doUnknown"
access="public"
returntype="string"
output="false"
hint="I handle the unknown event and return the next state.">
<!---
Not sure what the event was. As such, just decrease
the mood by 1 (out of frustration).
--->
<cfset this.updateMood( -1 ) />
<!---
Check to see where the mood now falls in our spectrum
of thresholds.
--->
<cfif (this.mood gte this.excitedThreshold)>
<!--- This girl is excited. --->
<cfreturn "Excited" />
<cfelseif (this.mood gte this.indifferentThreshold)>
<!--- This girl is indifferent. --->
<cfreturn "Indifferent" />
<cfelse>
<!--- This girl is bored. --->
<cfreturn "Bored" />
</cfif>
</cffunction>
</cfcomponent>
As you can see above, this Girl does nothing more than respond to events trigger on her. To see how this would work, I then created a test page that would trigger a string of events on the girl and output the resultant state and mood after each event.
<!--- Create the girl instance. --->
<cfset girl = createObject( "component", "Girl" ).init() />
<!---
Create a collection of events that we are going to trigger
on the Girl object.
--->
<cfset events = [
{
type = "BeBoring",
data = "Excuse me, but is that a mirrow in your pocket? Cause I can see myself in your pants!"
},
{
type = "BeNice",
data = "Sorry about that - I get nervous around hot women."
},
{
type = "BeNice",
data = "That's a really great dress you're wearing."
},
{
type = "BeBoring",
data = "So how about those Yankees?"
},
{
type = "BeRude",
data = "Are you always this uptight?"
},
{
type = "BeNice",
data = "What I meant to say was - I think you're beautiful."
},
{
type = "BeNice",
data = "Where are you from?"
},
{
type = "BeNice",
data = "I've never been to Montana, but I hear it's great."
},
{
type = "BeNice",
data = "Do you have any family here?"
},
{
type = "BeNice",
data = "Yeah, I'd love to see a picture of your sister."
},
{
type = "BeRude",
data = "Your sister is wicked hot! Can I get her number?"
},
{
type = "BeConfusing",
data = "Wait, did Ken send you?"
}
] />
<!---
Now that we have our collection of events that we want to
trigger, let's iterate over them and trigger each one on the
girl instance. After each event, we will output the resultant
state and mood.
--->
<cfoutput>
<!--- Iterate over events. --->
<cfloop
index="event"
array="#events#">
<!--- Trigger event on the girl. --->
<cfset girl.handleEvent( event.type, event.data ) />
<!--- Output the event action. --->
[#event.type#] - #event.data#<br />
<!--- Output the resultant state. --->
>>> #girl.currentState# [#girl.mood#]<br />
<br />
</cfloop>
</cfoutput>
In this demo, we are relying on the calling context to define the type of event; this is just to keep things as simple as possible. Notice that the last event announces its type as, "BeConfusing". This is not an event type that our Girl component is designed to understand. As such, it will have to rely on its "doUnknown" event handler.
When we run the above code, we get the following output:
[BeBoring] - Excuse me, but is that a mirrow in your pocket? Cause I can see myself in your pants!
>>> Indifferent [0][BeNice] - Sorry about that - I get nervous around hot women.
>>> Indifferent [1][BeNice] - That's a really great dress you're wearing.
>>> Indifferent [2][BeBoring] - So how about those Yankees?
>>> Indifferent [1][BeRude] - Are you always this uptight?
>>> Indifferent [0][BeNice] - What I meant to say was - I think you're beautiful.
>>> Indifferent [1][BeNice] - Where are you from?
>>> Indifferent [2][BeNice] - I've never been to Montana, but I hear it's great.
>>> Excited [3][BeNice] - Do you have any family here?
>>> Excited [4][BeNice] - Yeah, I'd love to see a picture of your sister.
>>> Excited [5][BeRude] - Your sister is wicked hot! Can I get her number?
>>> Indifferent [0][BeConfusing] - Wait, did Ken send you?
>>> Indifferent [-1]
As you can see, the Girl was able to respond to the given events and changed her internal state accordingly.
State machines are definitely very interesting; but, I don't have enough of an understanding of them to really see how they might be best applied. One thing that I keep struggling with over and over again is code formatting / highlighting on my blog. It seems to me that a finite state machine might be the perfect use case for this kind of tokenizer / parser. If you think of getting a character as a sort of "event," the state of the tokenizer might change depending on the currently stored token data. For example, reading in a dash (-) with the internal token data, (<!-) might signal the change of state to a "comment" rather than "html" or "cfml".
It does seem like a lot of work to code a state machine; but, it's probably an emotional misconception that coding this type of thing should be small in effort or scope. I do get the feeling, though, that this would be worth learning more about.
Want to use code from this post? Check out the license.
Reader Comments
I noticed a small error in your State Table and your code, Your state table says you are going to Increase your mood if you are rude and are excited, your code decreases it by -5.
@Daniel,
Ah, nice catch. The code is correct - the diagram is incorrect - the penalties of copy-paste-modify.
Ben,
We use a FSM for any of our apps that require workflow. In our case, the state machine id a CFC and we wire it up to either an xml or db config via ColdSpring. It's completely configurable so that adding new states to the workflow is super simple.
Your tutorials are always too hilarious. Nice work.
Hey Ben- I came across this post while checking out your MVC framework. You're right, state machines are very powerful tools. They are sometimes overkill but understanding them is a huge plus. Nearly anything in an application (page seqeunces, workflow, etc) could be a state machine. Especially when there is distributed logic and actions may be triggered remotely that may or may not make sense.
One good example is the standard email verification on a signup. Generally, clicking the email triggers a "validate email" action on the server and that's all that's needed. But what happens if the user had already been validated? What if they've been deleted? What if they change emails and click "verify" on an old email? Or have been banned from the system? There are often bizarre combinations of these that may, while edge cases, will lead to crashes or bizarre system states if not handled. Especially on large apps with millions of users, these states will happen.
Definitely powerful, not always needed. OK, I'm off to play with corMVC. It looks promising (after being disappointed by several other frameworks)...
Cheers,
Alex
p.s. Reread your examples.... made me laugh... very "game-y"... haha.
@Rob,
So are you treating the state machine more like an interface than real encapsulated business logic (at least not at the hard-coded level)?
@Alex,
I actually just read a article that talked about using state machines for something like that; basically, the process where by you have to get a confirmation email before your email address can be verified by the system.
It left me with a lot to think about, but I'm still having some trouble codifying how I might want to apply the FSM and where it is appropriate.
Seems like it could be a nice application for the onMethodMissing method.
@Danny,
Can you expand on what you mean by that. I am interested to see where you might be going with that thought.
Ben,
I think Danny was eluding to NOT coding specific methods for the event, but catching ALL calls to the object by the OnMissingMethod and THEN handling them programatically in there (using xml lookup/database calls for a large state system?)
I could be wrong, but it negates you having to create a method for every possible event.
@Paul,
Ah, that makes sense. I am not sure if that makes it easier though - I think the separation into different methods adds clarity and maintainability; but I agree that something about it feels a little "off."
I remember when I was doing my under-graduate work with FSM's that I decided to use a text file for storing the states and transitions when writing a LOGO interpreter.
Were I to do the same thing now, I would use XML. You could easily bring that into ColdFusion and ensure that the different transition triggers are defined.
This means that, if the business logic changes, you change the XML file instead of the CFC file. Essentially, the question comes down to this: Is it easier to make changes to the business logic in the XML file or the CFC file?