Hi Christophe and Dave!

Let me reply to you both by replying to Dave's post.

On Apr 20, 10:16 am, Dave Abrahams <d...@boostpro.com> wrote:
> on Fri Apr 20 2012, Christophe Henry
> <christophe.j.henry-AT-googlemail.com> wrote:
> > To be honest, the idea is not mine but Dave's, so I hope I will do
> > him justice. If you read Dave's and Aleksey's book, you might see
> > that the first level of the double-dispatch is done by the templated
> > process_event(), which makes process_event unique for each
> > event. This makes your first dispatch in O(1). The second
> > dispatching (state) is not done like in the book (which was O(n))
> > but on the model of a more advanced example provided in the
> > Boost.MPL documentation. It amounts to building, for each event, an
> > array of pointers to static functions representing a transition, one
> > entry for each possible source state. A metafunction generates an
> > index for each state, so that dispatching on state also is O(1),
> > which is pretty much the best complexity you can get ;-) ...
> > ...

This is very interesting (to me, maybe not to others) to see
that you discriminate first on the event, and then on the state.

I have hand-coded state machines that worked this way. (Events
were handles -- typically function pointers -- to event-handler
functions, and the event-handler functions used a switch statement
to discriminate on the state.) For whatever reason, this felt
unnatural to me, and now I prefer to discriminate first on the
state, and then on the event. But I certainly can't give you a
good explanation of why I feel this way.

(Of course, as a user of msm, it really makes no difference to
me in which order the double dispatch in implemented under the
hood.)

Concerning complexity, if I understand things correctly, the
hand-coded pointer-to-member-function / switch-statement
state-machine implementation with which I began this thread
should also perform the double dispatch in O(1) (although
this is potentially implementation dependent). The state
variable is a pointer-to-member-function that is presumably
implemented as an offset into the vtable, so that should resolve
in O(1), and the switch-on-event switch statements in the
state-handler functions are presumably implemented with jump
tables, so that should also be O(1).

>
> You did it justice of course, Christophe!
>
> A few additional points:
>
> * there are real scenarios where you don't know the event until
> runtime, e.g. if events are queued somewhere.

I don't follow what you're saying here. Isn't the normal -- and
by far and away most common -- use case the one where you don't
know the events until runtime? Which gui button was clicked,
what signal came from some hardware controller, and so on?

Unless you're talking about something completely different
where the state machine is constructed at runtime. (I've seen
a number of state-machine frameworks that work this way. It's
certainly a legitimate approach, but it's not my preference.)

> For those you need
> an additional layer of dispatching. It's easy enough to build and
> I presume MSM has some facility for that.
> ...

{ Quoted signature removed -mod }

Thanks again for your answers and sharing your experience.


K. Frank


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]