GoTo in FSM (was Help with Exceptions)

GoTo in FSM (was Help with Exceptions)

[W. Wesley Groleau (Wes)]

I keep hearing about the value of GoTo for a finite state machine.
Perhaps my understanding of an FSM is incorrect, but every time I've
coded what I THOUGHT was a state machine, I used neither GoTo nor recursion
and didn't think the code was exceptionally ugly.  With Ada 83 the awkward
part was defining (and _maintaining_) an enumerated type with one literal
for each action (plus error).  Another type enumerated the states.  A record
 type
contains one of each.

If the conditions that trigger the transition/actions are not discrete,
another awkward part is mapping each condition to an enumeration.

Now you have an array indexed by trigger and current state of those records.
Very readable if line length and size of table don't prevent it.  (Which they
often do--sigh)

loop
   Trigger := Check_Condition_Or_Input;
   case State_Transition ( Current_State, Trigger ).Action is
     when {action_name} =>
       Do_{action_name} (...);
     when ...
     when Error =>
       Do_Error_Stuff (...);
   end case;
   Current_State := State_Transition ( Current_State, Trigger ).Next_State;
end loop;

Now I wouldn't call that beautiful, but I wouldn't call it ugly either.

And now we have access-to-subprogram, so we can eliminate the case statement
and the first enumerated type!

(But I'm still opposed to making rules a substitute for thinking--even
 a rule against GoTo.)

--
---------------------------------------------------------------------------
W. Wesley Groleau (Wes)                                Office: 219-429-4923
Magnavox - Mail Stop 10-40                               Home: 219-471-7206
Fort Wayne,  IN   46808              elm (Unix): wwgrol@pseserv3.fw.hac.com
---------------------------------------------------------------------------

Re: GoTo in FSM (was Help with Exceptions)

[Robert I. Eachus]

In article <9605151336.AA03830@most> "W. Wesley Groleau (Wes)" <wwgrol@PSESERV3.FW.HAC.COM> writes:

  > I keep hearing about the value of GoTo for a finite state machine.
  > Perhaps my understanding of an FSM is incorrect, but every time
  > I've coded what I THOUGHT was a state machine, I used neither GoTo
  > nor recursion and didn't think the code was exceptionally ugly.
  > With Ada 83 the awkward part was defining (and _maintaining_) an
  > enumerated type with one literal for each action (plus error).
  > Another type enumerated the states.  A record type contains one of
  > each.

   The problem is that you have conceptually a large two dimensional
array indexed by current state and transition.  In a parser with
several hundred tokens and a thousand or so states that array gets big
fast.   So when you get to this line:

  >    case State_Transition ( Current_State, Trigger ).Action is

  What you want to do is to make State_Transition a function which
returns a tuple, and store the array in a compact form.  The usual
form for doing that is to have a large one-dimensional array with
entries (trigger, action, next state), (default, action, next_state),
(error, ..., resume in state), or (continue, ... , state to continue
with).

   In a parser or scanner it is the routine you call State_Transition
that ends up containing the gotos.  You can also implement a (usually
less than a dozen states) state machine by having each state correpond
to a label.  In fact this is usually how the state transition routine
or parser driver is coded.  There are a few states, including panic
mode error recovery, and the parser "walks" between them.

  >  Now I wouldn't call that beautiful, but I wouldn't call it ugly
  > either. 

   Agreed.  I could pretty it up a bit, but if you can afford the
space to implement the state table as an array, there isn't a problem.

--

					Robert I. Eachus

with Standard_Disclaimer;
use  Standard_Disclaimer;
function Message (Text: in Clever_Ideas) return Better_Ideas is...