State Machine Implementation

State Machine Implementation

[Ray A. Lopez]

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

Re: State Machine Implementation

[Robert Dewar]

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

A case statement is possible certainly, and it is hard to know exactly what
you mean by "an implementation", since this is the sort of thing that occurs
all the time in a programs, and the application dependent details are 95%
of the code anyway.

Note that an alternative, probably more efficient, and for many people more
readdable way of coding a finite state machine in languages like Ada is
to use a label on each state, and goto's to effect state transition, thus
efficiently encoding the state in the program counter.

Some people have this silly allergy to goto's (a case of understanding an
important principle without really understanding it), but in fact this is
for many programmers one of the very few legitimate uses of gotos.

Re: State Machine Implementation

[Matthew Heaney]

"Ray A. Lopez" <rdsys@inficad.com> writes:

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

I prefer to implement a state machine using labels and gotos.  That's
how I usually write tasks.  For example:

task body IO_Manager is

   Mode : Missle_Mode;

begin

   <<Idle>> null;

   select
      accept Start;
   or
      accept Stop; 
      goto Idle;
   or
      terminate;
   end select;

   <<Main>> null;

   select
      accept Change_Mode (Mode : Missle_Mode) do
         IO_Manager.Mode := Mode;
      end;

      <transmit mode>
      <make asynchorous read>

      <<Waiting_For_Response>> null;

      select
        accept IO_Completion;
        goto Main;

      or 
        accept ...;
        goto Waiting_For_Response;

      ...


Scanners typically have a state-machine implementation.  I just wrote a
scanner to parse real literals that weren't quite in legal Ada format,
using gotos to skip over optional parts of the lexical expression.

Re: State Machine Implementation

[dennison]

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.

I just finished a lexical analizer, and that's how I did it. There are some
folks here who feel like goto's are more straighforward for that purpose,
though.

T.E.D.

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/rg_mkgrp.xp   Create Your Own Free Member Forum

Re: State Machine Implementation

[John M. Mills]

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

I would consider something like:

type Handlers is array(STATE) of access function(...) return STATE;

(give or take the grammar, sorry).  Each handler is associated with one
state.  Each handler performs what action it can, then determines if the
machine's state has changed, returning the appropriate new or old value 
of STATE, which is used as the call index on the next iteration.

Advantages: clean logic from outside the machine, and no massive case branch
or decision tree. State handlers are totally decoupled from one another.

Disadvantage: no externally obvious logic flow.

-- 
 John M. Mills, Senior Research Engineer   --   john.mills@gtri.gatech.edu
   Georgia Tech Research Institute, Georgia Tech, Atlanta, GA 30332-0834
        Phone contacts: 404.894.0151 (voice), 404.894.6258 (FAX)
           "Lies, Damned Lies, Statistics, and Simulations."

Re: State Machine Implementation (long)

[dana]

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?

Re: State Machine Implementation (long)

[Tarjei Tj�stheim Jensen]

dana@indyweb.no.xyz.spam.net wrote in message ...
>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.


Plauger's Standard C library uses such state machines for character comparison
and classifications. It is quite clear that such a thing would be very nice to
have around.


Greetings,

Re: State Machine Implementation

[Bill Meahan]

See http://www.imatix.com

Look at Libero - a _really_nice state machine package. No Ada code
generator schema currently but it should be relatively easy to write and
maybe Peter at Imatix will write one for you.

Free software to boot!

Ray A. Lopez 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...

--
Bill Meahan  wmeahan@ford.com
Ford Motor Company -- Ford Systems Integration Center
Not an official statement of Ford Motor Company or anyone else
except the author.