[boost] Re: Re: Finite state machine requirements

From: Andreas Huber (spam2002_at_[hidden])
Date: 2002-09-13 16:22:13

Iain,

> Dynamic fsm's and static ones are IMHO two very different beasts and I
don't
> believe that you can use a single framework to do both without violating
the
> C++ dictum that you don't pay for what you don't use.

That's exactly what I believed as well. However, it seems that Joel de
Guzman has found a way to combine static and dynamic behavior in spirit
(spirit.sf.net). I'm still analyzing whether and how his approach could be
made to work for an FSM framework.

> Hierarchical states and guards :- could these not be better modeled as
> substates? IIRC I've
> seen them used in Colored Petri Nets but not in normal applications where
> states and
> sub-states generally suffice.

I don't understand. For me, hierarchical states and substates are exactly
the same thing. In a nutshell, this feature allows you to define a state
machine that runs "inside" a given state. E.g. in my StopWatch example, the
state Active contains a sub-statemachine consisting the two states Running
and Paused.
I believe guards are completely orthogonal to hierarchical states. Within
UML, a guard is a Boolean expression defining whether the associated
transition with will be "made" when an appropriate event is received.

> Also, what are concurrent states? I'd be interested in a use case that
used
> both concurrent
> states and hierarchical states with guards.

Concurrent states allow you to run multiple state machines simultaneously
behaving as a single state machine. A lot of problems can only be solved
cleanly with concurrent states. E.g. try to implement a state machine
modeling a standard computer keyboard. Whenever the user presses NumLock,
ScrollLock or CapsLock the keyboard has to toggle the appropriate indicator.
Without concurrent states, you need a state for every combination of the
three "Locks", i.e. 2^3 (from 000 (all indicators off) to 111 (all
indicators on)). As you can press any of the three Lock keys while the
keyboard is in any of the 8 states, you need 3*8=24 (!) transitions to
completely model the behavior of the keyboard.
With concurrent states, the situation is much simpler as you can model the
behavior of each indicator independently. That is, you need 6 states
(NumLockOn, NumLockOff, CapsLockOn, CapsLockOff, ScrollLockOn,
ScrollLockOff) and _6_ transitions. So, the state machine modeling the
keyboard consists of 3 concurrent state machines. Now whenever you have a
new event (EvNumLockPressed, EvCapsLockPressed or EvScrollLockPressed) you
simple send it to the current state of one of the 3 concurrent state
machines. If it is consumed, you're done. Otherwise you try the current
state of the second state machine ... and so on.

Please see the UML specs for more information:

http://www.omg.org/cgi-bin/doc?formal/01-09-74.pdf

> Of greater interest to general purpose applications would *I believe* be
> something like aleksey's fsm. Particularly as it does not have the
> dispatching overhead of your proposal.

As mentioned earlier, Alekseys approach has limitations (imposed by
compilers). It also has a dispatch overhead which I believe is proportional
to the number of transitions originating at the current state (Aleksey:
please correct me if I'm wrong). The dispatch overhead of my approach
depends on the dynamic_cast implementation of the compiler but I believe it
can be made constant time for non-nested states.

> Just my 2 pence worth.

Thanks for looking at it.

Regards,

Andreas