Re: State Machine Implementation (long)

[dana@indyweb.no.xyz.spam.net]

In article <35C90369.CFE8ED98@inficad.com>, "Ray A. Lopez"
<rdsys@inficad.com> wrote:

> Does anyone have any implementions of a state machine?  The states would
> be just an enumerated type and I am guessing you would use a case
> statement.  Just looking for more info on how to implement this using
> Ada.
> 
> thanks...

That's the approach everyone starts with.  One enumeral type for the
states, and one for the events which drive the thing.  But then things get
complicated.  If you have case statements, the number of possibilities are
n (states) times M (events), then some jerk wants to add new states and
events after you've just got the thing coded up.  This works for the text
book trivial case.

case Current_State is
when S_1 =>
  case The Event is
  when E_1 =>
  ... Many events
  when E_N =>
  end;
when S_2=>
  case The_Event -- do it all over again
  end;
end;

This gets double nuts when you have to have cases for the coarse AND
destination states for the appropriate action code.  

This model falls apart with substates, and lots of conditions which
restrict when an event actually causes a transition between states, Event
(tune knob) does NOT cause the state to transition to OPEN if
Dead_Bolt=Set.  

Then there's the problem of which "action: code gets executed on ANY entry
to a state and which gets run only when traversing from a particular
state.  

I once spent 4-6 months on a project (How long was it Stephe?) while we
beat our heads on an incredibly complex state machine and all kinds
complexities with dozens of states, events, and special cases.  Not
pretty.

I was so horrified by this experience that the next time I had to work on
a project with big state machines I wrote a state machine module where I
defined the following classes (it was in C++ but should be easily doable
in Ada95):

State
Event
Transition
Condition
State_Machine
Super_State
Action

Here are their descriptions

State 
had a list of its exit transitions, entry condition, entry action, exit
action.  The one thing which you had to get over with this model was that
you could not do something like "do this while in this state" if you
wanted to do something on a regular basis while in a state, then you had
to have a tick event handled by a tick transition whose action was to do
think stuff which was to be done regularly.  

Event
These were the thingies (and the only thingies) which made the state
machine show signs of life.  No event, no transitions, no actions, no
outward signs of intelligence.  I had the events carry pointers to user
supplied data like X/Motif events do.  For instance, the keypress event
had event data (the key) and 


Transition
Caused by an event, had a source and destination state, maybe a condition,
maybe an action) Transitions are different than events because a single
event can be tied to multiple transitions.   

Condition
This called a user supplied function which returned a true/False result. 
Used to enforce special rules which did not warrant an extra state.  Or
for that matter, could make use of the current state of other state
machines.

State_Machine
The class which contained everything.  You had one instance of this class
for every state machine your system had.  It could print itself out so
that you could actually see EXACTLY how your machine was going to be
implemented.  To make your program go, you would hand events to a member
function of this class.  The handle event function caused everything to
happen from there.  Because this was done in a true object oriented
fashion, the handling of an event could cause the stack to wind up through
15-25 function calls until the action actually occurred.  

Super_State 
A cross between state_machine and state.  These are extremely handy.  They
reduce the possible number of combinations by allowing a single
event/transition take the machine out of one of many sub-states.  These
also offered the possibility of memory (when you re-enter a superstate
with memory, it immediately goes into the last sub-state it was in.  There
were lots of fine points on the behavior of super-states and tier
sub-states which I managed to dodge the bullet  and leave hanging.

Action
This was just a container for a pointer to a function.  Now possible in
Ada95 as well as C.  This was the only way for an event to cause an
externally visable response from the state machine.  


-----------------------------------------------------------------------------

I wrote this almost 4 years ago and was quite impressed with myself.  Did
I manage to re-invent the wheel?  I know there are template classes for
directed graphs, but I think this goes well beyond that.  We used this
tool in loads of places where the state machine code could have been a
bear.  We used it in a few instances where it was arguable that the
enumeral/case thing was sufficient but the thread of a new state, event,
transition, or action being added was real.  

The State Machine class had a few cool things about it, it could be set to
print out a trace of the processing which occurred when an event was
handled.  It could also report on its state.  With super-states, the state
of a state machine was not a simple enum answer.  If you were two or three
levels into superstates the answer looked more like: 

Surfing:News_Reading:Posting:Babling_Incoherantly

Anything which might ask the current state should be ready for a
non-simple answer.  

I've always wanted to code somthing like this up in Ada95.  I would make
State_Machine limited private and get rid of all the recurse and descend
sillyness of the C++ version.  I want to add a queuing mechanism for
inbound events, and maybe event priorities.  I see places were a software
state machine
which could also be configured from a config file would be extremely nice
for maintenance purposes.  I have no idea on how to handle the action
routine accesses except for a compile time lookup table.  

With some work, the performance of such a system could approach that of an
enum/case monster and I would think the improved provability/observability
would be well worth the performance hit.  

For Q/A and testing purposes, you could substitute dummy bodies for the
action routines and conditions, and feed events into the machine and
observe the reaction in a bench test.  You might even add a capability to
jam load the machine with a particular, hard to reach state, and feed it
events to test event/response type requirements.  "The system SHALL, while
in the RANTING state, POST_SILLY_STUFF when ever a SILLY_URGE event
occurs".  

Anybody else with state machine experience out there with two cents to toss in?