Re: [boost] [fsm review] Comparison with ad-hoc FSM coding

From: Michael Caisse (boost_at_[hidden])
Date: 2008-08-16 21:00:00

David Abrahams wrote:
>> State machines consist of states and transitions. Transitions are
>> transversed upon some stimulus. The *machine* part of the state
>> machine receives the stimulus and then causes the transition to a new
>> state. 
>>     
>
> Sure, I'm familiar with the abstraction.  So far his code meets the
> definition.
>   
I figured you were familiar with the abstraction; however, I was unsure
what part you couldn't "picture" so I got verbose. His code has states
and transitions but it does not handle events. Calling a method is not 
an event. The methods in the structure are transitions.

> OK, or an "event," as I've heard it.
>   
I personally like "event".

> Well, sure, you could make all the member functions overloads of the
> same member function taking different event types (as does the one in
> C++TMP), and then it looks more like there's only one "tick" or "clock"
> entry point.  However, the effect is nearly the same even though the
> abstraction is slightly weaker.  The specific function being called is
> chosen at compile-time, and that's perfectly adequate for many
> applications.  It's true that in some designs events can be queued or
> otherwise need to be dispatched dynamically, but there's no need to make
> all FSM users pay for dynamic double-dispatch, and it's easily handled
> in a layer on top of the statically-dispatched design.
>   
There are many ways to perform the dispatching but what I am suggesting
is that dispatching an event in the form of a transition is what makes it
a *machine*. If I have a state machine that is in state A and I receive
event Q then the logic to determine what occurs is part of the state machine.

I've also implemented USB engine state machines, so lets just continue with
that example (and we also have a nice little diagram). If you are in the Address
state there are four valid transitions: Bus Inactive, Device Configured, Reset
and Power Interruption. Associated with each of those transitions is some
event that will cause the transition to be taken. Receiving an event not
associated with one of the valid transitions must also be considered. The 
logic to determine which transition to take based on the current state and 
event received is part of the state machine. Without that logic you do not
have a machine.

>> What was described allows the user to take any transition at any time
>> by invoking a method which then stores the new state. It lacks a
>> concept of stimulus causing a transition.
>>     
>
> I disagree.  Each entry point called can be viewed as a stimulus.
>   
By using that definition every class or structure that has a member function
and modifies a member variable is a state machine. While that could be
an academic use of the term it surely isn't going to be very useful for
event driven state machines. The methods described in the ad-hoc machine
are transitions, not events. Events must be evaluated against the current
state to determine a transition.

> I'll re-post the links:
>
> http://www.boostpro.com/mplbook/examples/player.cpp
> http://www.boostpro.com/mplbook/examples/player2.cp
>
> Please keep in mind that these are simple frameworks designed to
> demonstrate how template metaprogramming can be used to build
> domain-specific languages, and not intended to be complete FSM
> libraries.  That said, I've heard of several people picking up this
> design and using it successfully when they needed to build an FSM.
>   
Thank you for the links. I will take some time later to look at them.

>> State machines are not foreign to me. I commercially offer my own UML
>> (Real-time Object Oriented Methodology ROOM) package that takes a
>> graphical representation through code generation and targets many OS's
>> or bare metal. I extensively use state machines in FPGA
>> implementations.
>>     
>
> I bow to your greater depth of experience with FSMs.
>   
Sorry, my text does sound a bit rude doesn't it? That was not the intent but
I haven't written a book that I can point at for credibility  (o;

> What's the difference between an "event" and a "token" or "message?"
>
>   
I think event and token can be used interchangeably. I prefer event personally
but token seems more prevalent in hardware settings. Message seems to typically
hold one of two meanings: equivalent to event or a package containing both
the event and a payload (data).

-- 
----------------------------------
Michael Caisse
Object Modeling Designs
www.objectmodelingdesigns.com