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

From: David Abrahams (dave_at_[hidden])
Date: 2008-08-18 18:49:35

on Mon Aug 18 2008, Andrey Semashev <andrey.semashev-AT-gmail.com> wrote:

> David Abrahams wrote:
>> on Sun Aug 17 2008, Darryl Green <darryl.green-AT-aanet.com.au> wrote:
>> 
>>> in this trivial FSM where much of the state is directly
>>> encoded in a couple of variables,
>> 
>> I don't know what the number of variables has to do with anything.  For
>> all practical purposes, unless you allow nested states or other esoteric
>> extensions to the traditional CS meaning of FSM, 16 bits is more than
>> enough to encode the state of arbitrarily complex state machines.
>
> I'm sorry, I don't follow you. The question was not about how to encode
> the state but about whether FSM concept is needed here. 

I'm as baffled as you are about why Darryl brought up the number of
variables required to encode the state. :-)

>>> but you do seem to find the proposed libraries representation less
>>> useful. Is it simply that the "states that handle events" model is
>>> intrinsically not as clear as a diagram or transition table, 
>> 
>> I think so.  To start with, "states handle events" is not part of the
>> abstraction of what an FSM is.  Look it up in Wikipedia or any CS text.
>> You won't see any such description. 
>
> So, you're saying that the library must be designed as Wikipedia says?

No, I'm saying that a library addressing a particular domain (FSMs in
this case) with has well-established and effective notation should, if
possible, allow the user to express his code in a manner that maps
directly onto the established notation.  See for example Boost.Spirit
syntax and its relationship to EBNF.  Or the fact that we use operators
in C++ to manipulate numbers!

>> Instead, that's a point-of-view unnecessarily imposed by the proposed
>> library.  So the library's DSL isn't a faithful reflection of the
>> ways we already talk about FSMs.
>
> The library supports both approaches for defining the FSM - the
> state-based and the transition-based. I for one prefer state-based
> approach and you, I assume, prefer transition-based. 

I prefer the established FSM notations.

> To my mind, it is advantage that the library can be used both ways.

Maybe; the "transition based" description as you present it doesn't
look like an STT to me.

>>> typedef mpl::vector<
>>>   fsm::transition<Attached, fsm::event<PowerOn>, Powered>,
>>>   SetAddressTrans<Default, std::not_equal_to, Address>,
>>>   SetAddressTrans<Address, std::equal_to, Default>,
>>>   SetConfigurationTrans<Address, std::not_equal_to, Configured>,
>>>   SetConfigurationTrans<Configured, std::equal_to, Address>,
>>>   fsm::transition<fsm::any_state, fsm::event<Reset>, Default>,
>>>   fsm::transition<fsm::any_state, fsm::event<PowerOff>, Attached>
>>> >::type Transitions;
>> 
>> The bits enclosed by fsm::transition look like they might be rows in an
>> STT, although they're awfully verbose, with a great deal of surrounding
>> syntactic noise that distracts from being able to read the actual
>> semantics.  AFAICT, the other parts do not bear any obvious resemblance
>> to rows in an STT.
>
> Sorry, I don't see why the code above is worse than this:
>
>   struct transition_table : mpl::vector11<
>       row < Stopped , play        , Playing , &p::start_playback  >,
>       row < Stopped , open_close  , Open    , &p::open_drawer     >,
>       row < Open    , open_close  , Empty   , &p::close_drawer    >,
>       row < Empty   , open_close  , Open    , &p::open_drawer     >,
>       row < Empty   , cd_detected , Stopped , &p::store_cd_info   >,
>       row < Playing , stop        , Stopped , &p::stop_playback   >,
>       row < Playing , pause       , Paused  , &p::pause_playback  >,
>       row < Playing , open_close  , Open    , &p::stop_and_open   >,
>       row < Paused  , play        , Playing , &p::resume_playback >,
>       row < Paused  , stop        , Stopped , &p::stop_playback   >,
>       row < Paused  , open_close  , Open    , &p::stop_and_open   >
>   > {};

Because the rows that don't begin with fsm::transition are opaque to me
and don't appear to be symmetric with the other rows, whereas with one
line of comments I can make my table completely transparent to anyone
who knows what an FSM is:

        //   Start      Event         Next      Transition Action

> In fact, I find your syntax more verbose for the unneeded fourth column
> of the table.

It's only unneeded if you think it doesn't convey information that's
important to understanding the FSM.  From my POV, it does.  That's why
arcs in an FSM diagram are often labeled with their associated
transition actions.  How does a user of your library associate actions
with transitions if they don't go in the table?

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