[boost] Re: Re: Re: FSM Review

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.

Regards,

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