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

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-17 00:20:31

on Sat Aug 16 2008, Michael Caisse <boost-AT-objectmodelingdesigns.com> wrote:

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

Why not?

> The methods in the structure are transitions.

Or you could say that they're events with bundled transition actions.

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

Sorry, "in the form of a transition" doesn't make any sense to me in
this context.  In my world:

  An _event_ triggers a _state change_ and an associated _transition
  action_.  The triggered state change may depend on the machine's
  _current state_.

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

No argument there.  I don't see how it relates to the example.

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

Depending on the application, yes.  As the OP said, he was assuming that
any effects at all were allowable on an invalid event, i.e. undefined
behavior.  A valid assumption, as long as its stated.

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

I see that logic in the OP's code plain as day.

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

As long as it doesn't allocate memory.  Once a class  ;-)

Seriously, though: the point is that the OP's code was a fairly direct
translation into code of (a portion of) the FSM in the picture.

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

Would your objection be satisfied if one of those functions tested the
current state to determine the next state and/or transition action?
Maybe it's a degenerate and not-very-interesting FSM, but it's still a
FSM AFAICT.

Would you say that the equivalent code posted that used the FSM library
was also not an FSM?

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

Not in the least.

> That was not the intent but I haven't written a book that I can point
> at for credibility (o;

My book shouldn't be viewed as giving me any significant credibility in
the area of FSMs.  However, I have thought quite a bit about
abstractions and their representations.  I think that's what this
argument is primarily about.

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

Good.

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com