[boost] Re: [prereview request][fsm]

From: Andreas Huber (ah2003_at_[hidden])
Date: 2004-05-24 17:18:59

David Abrahams wrote:
> "Andreas Huber" <ah2003_at_[hidden]> writes:
>
>> David Abrahams wrote:
>>
>> [snip]
>>> Also, do I note that there's always function pointer indirection for
>>> event dispatch?
>>
>> I'm not sure I understand what you mean with "function pointer
>> indirection". Event dispatch consists of a virtual function call
>> followed by a linear search for a reaction matching the event.
>
> That's what I mean.  If you look at the FSM examples I posted, no
> virtual call is needed, and in fact the linear search could be
> optimized by the compiler into a hashed case statement or by
> metaprogramming into a log(n) search.  The 2nd example uses a
> constant-time lookup, dispatching through a single function pointer.
> There are lots of dispatching tradeoffs available.

I finally found the time to have a closer look at your examples. I believe
you can do away with one of the two double dispatch steps because you know
at compile time exactly how the whole state machine looks like (i.e. your
compile time algorithm "knows" all possible events and all possible states).
This approach works well with small FSMs. It breaks down for large FSMs
because either at some point the compiler will give up due to internal
limits or the compilation times become unbearable. During state machine
development, every little change (e.g. adding an event or a state) triggers
a recompilation of the whole state machine.
boost::fsm was designed to avoid these problems. You can spread a state
machine over multiple translation units and even have multiple developers
work on the same machine. Changes made by one developer (adding states,
transitions, events to "his" part of the machine) will not trigger a
recompilation of code implementing other parts of the machine. This
virtually limitless scalability is possible exactly because there's no
central algorithm that knows "everything". As a result, some stuff your
examples can do at compile time has to be done at runtime by boost::fsm.
More specifically, in your examples you know at compile time exactly which
states have an outgoing transition for a given event. You therefore never
need to runtime dispatch on an event that's known at compile time.
boost::fsm does not have this information available at compile time. In
fact, before a state becomes active at runtime my dispatch algorithm does
not even know that such a state exists. Consequently, my dispatcher cannot
know all the possible reactions for a given event and that's why I need to
perform a linear search for the reaction after dispatching on the current
state.

> I really like your state representation; it seems as though it should
> be possible to get all these different dispatching options with your
> state representation, rather than requiring a monolithic STT sequence
> to be assembled as my examples do.

As long as no custom_reactions are used I think this should be possible, as
all the necessary information is available at compile time in a single
translation unit. However, I don't dare to explore what this would mean
implementation-wise. It seems this pretty much requires a complete rewrite.
I'd also need to change/extend the interface to provide replacements for
some custom_reaction uses (guards and in-state reactions).
Finally, I think custom_reactions are fundamentally incompatible with all
dispatching options that implement one dispatch step at compile time. So, an
interface-compatible boost::fsm variant offering the current as well as
other dispatching options would somehow need to issue an error upon
detecting a custom_reaction or somehow fall back to current dispatch
algorithm...

Regards,

Andreas