Boost logo

Boost :

From: Andreas Huber (ahd6974-spamgroupstrap_at_[hidden])
Date: 2005-03-09 15:34:05

Iain K. Hanson wrote:
>> If you mean a single STT per FSM then this requires knowledge about
>> the whole FSM.
> Yep. And i can't see why that would have any effect on scaleability.
> Its
> just a meta program for assembling the fsm.

With scalability I mean that an FSM can be split up in parts that are
implemented in separate TUs. E.g. in the Camera example the inner states
of Configuring could reside in one TU and the inner states of Shooting
could be implemented in a separate TU. How do you piece the information
in these two TUs together? Possibilities:
1. At compile time. I don't see how that could ever work portably.
Separate TUs don't have any knowledge of each other.
2. At runtime. Each TU could have one static variable of a type with a
constructor. Inside the ctor you register your part of the FSM with the
FSM object. This sounds like it could work. Problem is that the standard
does not give many guarantees when exactly these static objects are
constructed. You can *hope* that they are constructed before the FSM
object and on some platforms they actually are constructed at program
startup but there's no guarantee for that. So if you want to stay
portable you pretty much have to rule out runtime registration. You
surely could do it manually but I don't think users would like that.
3. At link time. The proposed FSM lib uses this method (I call it this
way because a function declaration is bound to its implementation at
link time). A states' react function can be implemented in the FSMs cpp
file and from there a transition can be initiated to a state that is
unknown in the FSMs hpp file (see Camera example code for details). The
"problem" of this method is that there is no way of knowing how many or
what states a particular FSM has, not even at runtime. Sure, you know
that a state exists when you find the machine residing in that state.
But you never know what the next state will be when the next transition
is executed.

I hope this rather lengthy explanation shows that a statically checked
FSM spread over multiple TUs cannot be collapsed into an FSM-global STT
(at least not portably).

However, since each innermost state must know all its outer states (1),
it is theoretically possible to collapse all the reactions of these
states into a STT that is local for each innermost state. At a rather
hefty price, this would give you constant-time lookup, *separately* for
each innermost state. In FSMs with orthogonal regions multiple such
innermost states can be active at the same time, which makes lookup
linear again. Hence my previous remark to Dave.

(1) Just in case you're wondering: It's not a coincidence that outer
states don't know their inner states (apart from the initial one) but an
inner state knows all its outer states.


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

Boost list run by bdawes at, gregod at, cpdaniel at, john at