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

From: Darryl Green (darryl.green_at_[hidden])
Date: 2005-03-03 05:18:30

Augustus Saunders <infinite_8_monkey <at> yahoo.com> writes:
> 
> First, I appologize for messing up the threading, but I get the
> digest and so can't respond directly.

OT: the gmane web interface isn't too bad if that helps at all.

>  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 & )" ?

Why the interest in minimising the effort of writing custom reactions? They
are a bit of a low level access method, and result (in less trivial, non-inline
examples) in hiding what the transitions destination state is. Normally, you
wouldn't use many custom reactions.

> >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'm not seeing what there is that I would want hidden. What do you think needs
hiding?

> >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.
> 
> >> In general, I would drop all mention of UML except for some
> >> appendix somewhere (and the reference manual too).
> >
> >Why?
> 
> I think it's a distraction.  Sure, it's great that you've got this
> nice correspondance with UML, but that's unimportant *in the
> tutorial*.  Mention it on the about page, have an appendix all about
> it, go into detail in the references, etc.

I disagree. There needs to be some model, language etc to base the tutorial
description on. You have already said that you don't think writing a guide
to FSMs is the right thing to do. There are any number of books and even a
standard ;-) that describe the UML FSM concepts so that Andreas doesn't need
to. It would have been possible to pick some other complex FSM description
language, but UML is supposed to be universal, and gets plenty of books, tools,
courses etc built around it, so why not use it?

> 
> >> I think the example state machines are basically OK, but I
> >> think that it is absolutely essential that you include a simple
> >> example that is alphabet-based.  In fact, some helper functions
> for
> >> alphabet-based languages are probably a good idea, just to make
> the
> >> tutorial easier.
> >
> >Why?
> 
> Well, maybe this isn't the norm, but I was taught FSMs using
> alphabets-as-events.  One of the first things *I* would do with the
> library is try and implement some examples out of my old college
> text.  I figured most people were taught this way, and so having an
> example with that would help connect with something familiar.

Ah. So you probably want an example that is a recogniser for some regular
language. I'd be very suprised if this was an area where boost fsm is a good
choice, it would be interesting to see how you go. Also, if you want to
constuct fsms to do this sort of thing quickly and easily, wouldn't you just
use a regexp, or one of the plethora of lexer/parser construction tools and
let it figure out the tedious details for you? I would expect (haven't got
around to looking at it yet) expressive to be just the thing for that, but
spirit would do the job too with a lot less typing than using boost fsm.

> 
> >You mean the mapping between the pressed key and the generated
> event?
> > Why?
> 
> I think it's probably a common thing to want to test your state
> machine by triggering events from the keyboard in a console app.

This isn't very useful if the fsm uses more complex event types. And
conversely the despatch method used by boost fsm is less than
spectacularly efficient if your events really are simple values.

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

Think of a state as a scope. Think RAII.

> 
> >> 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.  I think this needs to be
> explained in big neon signs.  I don't think of exiting a state as
> destroying it, just that it's no longer "active" or whatever.  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.  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.

If you don't have nested states then your machine is flat and you would
almost certainly have empty states and place all your actions and data in the
machine. What is the problem?

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

What do you want the accept state to do that is so special?

> >
> >I don't know what accept states are. UML doesn't have them.
> 
> Now, I'm in no way an academic, so I'm relying on Wikipedia to tell
> me what's "normal."  Since it's in line with my old textbook, I guess
> it's reasonably standard.  Wikipedia tells me that there "acceptor"
> and "transducer" finite state machines.  I've not worked with the
> "transducer" variety before; my text deals with them only in the
> exercises.

I'm more familiar with the use of the terms recogniser or scanner rather than
refering to the fsm as an acceptor fsm, but yes, in lnaguage processing those
terms are standard. Unfortunately, I think you are going to be disappointed if
you try to use boost fsm in that sort of application. Not that that wouldn't be
useful review feedback. Boost fsm is much better for what wikipedia informs me
are called transducer fsms, a term I am unfamiliar with, but a class of fsm that
I am very familiar with.

>  At any rate, with an "acceptor" FSM, if after processing
> all input you are in an "accept" state, the input was legal, the
> operation was successful, whatever.  Otherwise there was an error. 
> Not that everybody will use them, but it would be nice to be able to
> mark states as accept-states and ask the machine if the current state
> is an accept-state.

Ok - so given an otherwise flat fsm, put all your accept states in an outer
state called - um - accept, and all the rest in an outer state called reject.
When you receive the eof event it should be handled by the accept or reject
outer state in an appropriate way.

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

It is not all that informative, but I learned a new word :-) Of course the
important thing would be to make the link reciprocal - there are some pretty
average links there now.