[boost] Re: ANN: review of FSM library starts

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-03 10:41:56

Darryl has already answered some of the questions (thanks again!), I'll only 
answer the stuff that he didn't cover.

> >Have you ever had a look at other FSM libraries? I think boost::fsm
> >is less messy than any other library I've seen.
> 
> Unfortunately, no.  My response is based on the fact that 1) I
> generally think I know what fsm are about, 2) I'm comfortable seeing
> complex template stuff, yet 3) sample code for simple state machines
> just didn't click for me.  I feel like I'm in the target audience of
> the library, so I'm looking deeper to see if I can figure out why.

Ok.

> >>   // I guess there's no way to avoid declaring
> >>   //  these ahead of time??
> >>   class Machine, State1, State2, Event1, Event2;
> 
> >Actually there is, but I found out about this only recently (Peter
> > Dimov mentioned this in an unrelated post) and haven't changed the
> > docs because I feared that this does not work on all compilers:
> >
> >Instead of
> >
> >struct Greeting;
> >struct Machine : fsm::state_machine< Machine, Greeting > {};
> >
> >you can write:
> >
> >struct Machine : fsm::state_machine< Machine, struct Greeting > {};
> 
> Ok, good to know.  I'd like to hash out what the "ideal world" would
> look like and compromise from there, if you know what I mean.

I think so, yes. I hope at the end of this discussion it becomes apparent that 
this is very much how the fsm library was designed.

> >>   struct S1Data
> >>   {
> >>      int i;
> >>      S1Data() : i(0) {}
> >>   };
> >> 
> >>   typedef simple_state< Machine, S1Data,
> >>       BOOST_TYPEOF( cout << constant("Entering State1.") ),
> >>       BOOST_TYPEOF( cout << constant("Exiting State1.") ),
> >>          on_event<Event1, BOOST_TYPEOF( _1->i++ ) >,
> >>          transition<Event1, State2> >
> >>     State1;
> >>   // the "data" member of State1 has type S1Data, and is 
> >>   //  passed into event handlers
> 
> >You consider this more readable? Sorry, I have to disagree. For
> entry
> > and exit actions and extended state variables I consider my
> approach
> > superior, for reaction definition, your approach seems about
> > equivalent.
> 
> I think this is how my example would look using the current library,
> right?
> 
> struct State1 : simple_state< State1, Machine,
>   custom_reaction< Event1 >, transition< Event1, struct State2 > >
> {
>   int i;
> 
>   State1() : i(0) { cout << "Entering State1."; }
>   ~State1() { cout << "Exiting State1."; }
> 
>   result react( const Event1 & ) { i++; }
> };

Almost. You'd write the state declaration as follows:

struct State1 : simple_state< State1, Machine, mpl::list<
  custom_reaction< Event1 >,
  transition< Event1, struct State2 > > >
{ /* ... */ }

Moreover, you have to return with a function call from react, as follows:

result react( const Event1 & ) { i++; return forward_event(); }

> That's actually not so bad.  I've defined both a reaction and a
> transition on the same event; not sure if you're supposed to do that.

You're not supposed to do that. While your example makes perfect sense, it 
does not make any sense to mix other reactions triggered by the same event 
(e.g. termination with transition). Therefore, there's the general rule that 
for a given event only the first reaction is executed (this is only documented 
in the reference). However, there is a chance that this will change due to 
unrelated reasons I don't want to outline here. To do what you want you'd 
write the following:

struct State1 : simple_state< State1, Machine,
  custom_reaction< Event1 > >
{
  int i;

  State1() : i(0) { cout << "Entering State1."; }
  ~State1() { cout << "Exiting State1."; }

  result react( const Event1 & ) { i++; return transit< State2 >(); }
};

Note that it makes little sense to increment i before transiting (unless you 
access i in the exit action) because this will inevitably lead to the 
destruction of the state object.

>  Now I'm wondering if there's a way with mpl to determine if a class
> has a function with a certain signature.  Can you eliminate the need
> for "custom_reaction< Event1 >" and just test whether or not the
> class implements "result react( const Event1 & )" ?

Not in a portable way, AFAICT.

> If you could
> somehow hide the CRT mechanism,

CRT?

> and specify children instead of
> parents, maybe you could boil down to something like so:

I don't understand, somewhere you absolutely must specify exactly where in the 
state chart your state "sits". I don't see how you can do that by only 
specifying children.

> 
> DEFINE_STATE(State1, transition< Event1, struct State2 >)
> {
>   int i;
> 
>   State1() : i(0) { cout << "Entering State1."; }
>   ~State1() { cout << "Exiting State1."; }
> 
>   result react( const Event1 & ) { i++; }
> };
> 
> And I think that's about as obvious as you can make it.  But that may
> just be wishful thinking.

I think so, see above.

> >I don't understand, you do define states top-down in boost::fsm.
> 
> Maybe I'm confused, but as best as I can tell, you specify parents
> instead of specifying children.

For the moment I'll ignore the fact that you'll have to specify the inner 
initial state for each outer state (IIUC, this would qualify as specifying 
children).
To answer your question: Yes, one needs to specify the parent (context) for 
each state and that context needs to be a complete type. This leads to the 
rule that you need to define your state_machine<> subtype first, then the 
outermost states then the states inside the outermost states and so on. To me, 
this is perfect top-down, is it not?

> So, if StateX has StateY and StateZ
> as inner states, instead of saying StateX : StateY + StateZ, you say
> StateY -> StateX; StateZ -> StateX.

Yes, see above.

> >> it's my impression that with mpl one can iterate
> >> through the template arguments and figure out if they are events
> or
> >> transitions or whatever.  So I smushed together the different
> 
> >One sure can but that would duplicate mpl::list<> functionality to a
> > certain degree.
> 
> For "real-world" uses, this seems unimportant.  However, for the
> tutorial and basic examples, I think it would be a good idea if you
> can silently ignore mpl.  Of course those examples should compile and
> work...  I don't have a feel for whether I'm asking for a mountain or
> a molehill here, so I'll let it be.

BTW, there's also a technical reason, not just lazyness on my part. A complete 
state definition can have *two* lists of things (one is the reaction list, the 
other is the list of inner initial states). You therefore absolutely need to 
have some kind of grouping or container construct. mpl::list is just perfect 
for that.

> >Given that the approach you outlined above really works, I think you
> > can use lambda for transitions without changing a single line of
> > boost::fsm, you simply define your own reaction that accepts
> > typeofed lambda expressions instead of function pointers for
> > transition actions. I'm not so sure whether the same is possible
> > with entry/exit actions but I'm inclined to think that it
> > is (that would require deriving your own state class template from
> > simple_state).
> 
> I think it would be nice to have a mechanism that accepts lambdas,
> though I'll concede it is better to avoid it for "average joe"
> programmer.  But since fsm is compile time, an advanced user might
> use another library/technique to programmatically generate the code
> she wants as a lambda type.  It's always seemed that lambda had great
> potential as a compile time code generator, and fsm is a place where
> one might concievably stick it.

That's alright with me. As I said, I think it is possible to do that as a pure 
extension. You're welcome to submit such an extension.

> >Most people get used to the syntax 
> >of boost::fsm quite quickly. Also, I've received feedback that
> people
> > really like the fact that they can easily put the bodies of complex
> > actions in cpp files, I *guess* that would be a little more
> > difficult with your approach.
> 
> Now I'm thinking that maybe a macro or two added to what you've got,
> just to hide some of the machinery, is all that it would take to get
> what I'm looking for.  I'll grant you that I'm struggling to come up
> with what I think is "ideal."  My main goal is boost::fsm using code
> should be reasonably "guessable" by an educated reader in short
> order.  Basically, my coworkers should be able to look at my code and
> mostly be able to guess what was going on.

That was also one of my goals. Problem is that these "users" are just one part 
of the picture. The other part are the regular users and I'll always give the 
latter group the priority. If I can't satisfy the regular users I don't think 
the library is worthy for inclusion into boost, period. Now this doesn't mean 
that I can/will ignore the beginners but it means that I sometimes need to 
compromise in favor of the experienced user group.
That said, I don't think it takes a lot of time (an hour at most) for an FSM-
savvy first-time reader to understand code that uses boost::fsm. Of course, 
learning how to write such code takes a little longer.

> [snip]
> 
> > I'd say it takes one day tops of playing around with boost::fsm to
> > learn this. 
> 
> My concern is intimidating potential new users more than necessary. 

Noted, this is a concern for me too. However, I don't see a lot of potential 
how I can further simplify the interface without constraining the 
functionality. I could surely provide state definition macros, but then again, 
I only want to introduce macros if I see *substantial* code-reduction. User 
who don't buy that can always define their own macros.

> Like I said initially, I might have missed a ton of discussion about
> this from before.  If you can point me to a thread where interface
> issues were hashed out in great detail already, I'll take a look.

IIRC, there never was a discussion about the pros and cons of the current 
interface.

> > I did consider using named template parameters, but
> > rejected it because it would add to the amount of text you have to
> > write and would offer a benefit only for beginners.
> 
> Me, I would probably cater a little more to the beginners, since I
> think getting more people to use FSM than previously would have to be
> a good thing.

As always it's a trade-off, see above.

> >> tutorial just made my head spin, especially trying to figure out
> >> how states and machines get tied together (this is still unclear
> to
> >> me). 
> 
> > I guess you mean how the implementation ties them toghether? As a
> > user, why do you need to know that? 
> 
> When I first looked at the sample code, I was hunting high and low,
> thinking to myself, "Where on earth does it specify which states
> belong to which?"

Ok, but you're the first to wonder about that.

> >As I already mentioned in another post: Targetting every C++
> > developer would require an *additional* document at least as thick
> > as the current tutorial. I think it is reasonable to expect
> previous
> > exposure to FSMs. 
> 
> Yes, I do not suggest writing your own guide to FSMs.

Good.

[snip]
> >> Getting Started" and
> >> "Target Audience" should be in a differenct document, and
> >
> >Please make a suggestion.
> 
> Probably just in index.html.

I don't have an opinion on that. I guess I'll change it and see whether 
there's any negative feedback.

> >> "How to read this tutorial" should be removed.
> >
> >Why?
> 
> To me, is unnecessary verbiage.  It doesn't say anything important. 
> Perhaps you need better headings in the TOC.  The ToC is currently
> broken up by the name of the example; perhaps rather than
> "StopWatch," say "Simple Finite State Machines - A StopWatch
> example."  

Ok, noted. I'll see how it looks and proceed as above if I like it.

> >> In general, all of your "remarks" and "comments" need to be in the
> >> code!
> >
> >You're the second person to request that. I personally think it is
> > better to not clutter code with too many comments. If people think
> > it is better to have all comments in the code, I'll sure change it.
> 
> Having it in the code, both in the tutorial and in the example files,
> would help a lot, IMO.  Especially the example files.  If you could
> give me a better overview of the process and hold my hand better
> about which template parameters are which, I think I would have been
> much less confused.

Ok, I'll change that then.

[snip]
> >> I'm confused about why entering/exiting states causes
> construction/
> >> destruction.  It's taken as a given,
> >
> >It is not: http://tinyurl.com/5mjra (State-local storage)
> 
> That's explaining why you offer state-local storage, which I have no
> qualms with.  It doesn't explain why you use the
> constructor/destructor mechanism, it's just stated that's the way it
> is.

Well, if you accept all the reasons/requirements I give for state-local 
storage (and it seems you do) then I think the current design is one natural 
way to satisfy all these requirements. Especially, if you accept that some 
data is only useful as long as the machine resides in a certain state.

> >> but I would tend to assume that
> >> state-local-storage is maintained throughout unless I explicitly
> >> reset it.
> >
> >Why?
> 
> Ok, I think I figured something out since I wrote this.  You're
> relying on nesting states to maint data.

Exactly.

> I think this needs to be explained in big neon signs. 

I think part of your misunderstanding is that you've never used nested states 
before. Anyway, in the Rationale for state-local storage I will add the code 
for a StopWatch that does not use state-local storage at all and I will 
explain there the benefits compared to the version in the tutorial. I will 
cross-link the two versions. I hope this will make it more apparent how I rely 
on state nesting.

> I don't think of exiting a state as
> destroying it, just that it's no longer "active" or whatever.

See above, extended-state variables tend to have exactly the same lifetime as 
already existing states. Also, think of a state being represented by one bit. 
Zero means state is inactive, 1 means state is active. With state-local 
storage you can augment this one bit with whatever information you like.

> Your
> model is like a window manager that closes a window every time a
> different window gets the focus and reopens the first window upon
> return.

I don't think that is an adequate comparison.

> Of course, having lost all data imbetween.  Maybe hoisting
> your data up to an enclosing space is a good idea, but I'm not used
> to working with nested states, so I don't really think that way.  I'm
> willing to be convinced, although I'm suspicious.

See above, let me know if that did some convincing.

> >> I'm also surprised by the lack of "accept" states.  Maybe
> >> it's not universal, but my theory certainly had them, and it's
> just
> >> disconcerting for them not to be there.
> >
> >I don't know what accept states are. UML doesn't have them.

[snip]
> I would certainly recommend adding
> http://en.wikipedia.org/wiki/Finite_state_machine to your list of
> links about FSMs.

I'm not sure whether that would help people a lot. Mealy/Moore is explained 
but the more important (and more practical) Harel/UML approach isn't covered 
at all.

Regards,

-- 
Andreas Huber
When replying by private email, please remove the words spam and trap
from the address shown in the header.