Forums

Transition and reaction difference in FSM?

Started by Davy December 24, 2006
Davy wrote:

> Hi all, > > I found there are transition and reaction in FSM/HSM. I only know there > is state transition in FSM. What's reaction mean? And what's there > difference? > > BTW, I am studing Statecharts (or called Hierarchical State Machine, > i.e. HSM). Is it useful in software/hardware design? > > Any suggestions are welcome! > > > Best regards, > Davy >
Generally state machines are divided into Mealy and Moore: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Seq/fsm.html Once you get beyond that, there are hierarchical state machines, timed automata, etc. It depends on what you are trying to do with the model (generate code, verify properties, both, neither, etc.). The goal of most modeling frameworks is to allow enough modeling richness that humans can understand the model, and allow enough independence that models can be reused in other systems. That first one is a losing battle--humans aren't good at understanding all possible behaviors of stateful systems. Generally, all state machines are equivalent regardless of the modeling framework. There are algorithms to convert from various formalisms to various other formalisms. As far as the construction of software, the absolute minimization of state is usually more important than the modeling framework. There is much to say in that department, but you didn't ask. State machine design is very important in embedded systems. ------------------------------------------------------------ David T. Ashley (dta@e3ft.com) http://www.e3ft.com (Consulting Home Page) http://www.dtashley.com (Personal Home Page) http://gpl.e3ft.com (GPL Publications and Projects)
In article <%1clh.20$SQ1.14@trnddc03>, H. S. Lahman says...
> Responding to Adsett... > >>One is required to "follow" those transitions in the software external > >>to the FSM in the sense that events must be generated and delivered in > >>an order consistent with the FSM structure (i.e., events arrive when the > >>FSM is in the proper current state). But I think that is a separate > >>problem for asynchronous communications (e.g., handshaking protocols) > >>and serializing mechanisms like event queues. > > > > > > I can see you could build a FSM this way and it might even be required > > in some cases but it does seem rather cumbersome. It seems to require > > two copies of the FSM one to perform the transitions and one to decide > > which transitions are valid. Surely part of the essence of a state > > machine is you deal with events as they occur rather than reording them > > to suit? > > Sorry, but you have lost me here. I only see one FSM. Defining the > states and transitions in an FSM is driven by the problem space. The > result of that process of problem space abstraction is the <single> FSM > that executes as the problem is solved.
It appears to be implied by your requirement above that the software external to the FSM must know what state the FSM is in in order ro generate the proper events.
> Events are just messages that announce some change in the state of the > overall problem solution.
And here you lose me again. 1 - Events cause transitions 2 - Transistions change states 3 - Changes in state are annouced via events 4 - See step 1
> >>>>Even in a trivial case like: > >>>> > >>>>[Opened] > >>>> | ^ > >>>> | | > >>>> V | > >>>>[Closed] > >>>> > >>>>there are problem space rules that say that it makes no sense to execute > >>>>the [Opened] action twice in succession. > >>> > >>> > >>>Which would be why the during action is such a state would be null > >>>presumably. Or the opened state would have a transition to an idle > >>>state occupied once the open was successful. > >> > >>I'm not sure what you mean by "during action". > > > > > > OK, the FSMs I build use the following basic contructs. > > > > Transitions with > > conditions (such as load > LOAD_MAX) > > actions (such as motor_off(); ) > > States with > > on-entry actions executed on entry to the state > > on-exit actions executed on exit from the state > > during actions executed while in the state. > > IOW, a "during action" is something like a continuously running polling > loop? FWIW, I think that notion violates the basic rules of finite > state automata in a major way.
No, it's a periodically executed action. It performs actions, I don't think I've ever done one that polled input.
> In an FSA, the action processes the input alphabet and it assumed to be > instantaneous. [The Mealy FSM model was developed because some purists > had a problem with the fact that actions took finite time to execute in > practice and that meant there was an ambiguous period when the FSM was > not in either the prior state or the new state for the transition. > Putting actions on transitions allowed the FSM to remain in the prior > state until the transition was completed and then instantaneously > transition to the target state.]
A quick aside on timing. The transistions may in some abstract sense be instantaneous but in most of the state machines I write the transitions from state to state are 'clocked' in the sense they can take place only at certain regular intervals. This clocking is vital to the correct behaviour.
> > I would also argue that for the "during action" to do anything useful it > must somehow change the state of the overall solution (e.g., generate an > event or set an attribute if the hardware provides an interrupt). IOW, > the action must do something that will observable externally or after > its completion. Otherwise there would be no way to determine that it > actually did anything. So if the "during action" does do something > visible outside the state, then it is modifying the the state. This is > particularly worrisome because that change could take place _at any > time_ while the object is supposedly in the state.
Let me provide a simplified example. Consider a motor control with the following inputs: - Forward (on or off) - Reverse (on or off) - Throttle (0 to Max) From these and domain knowledge (which I leave out for brevity) we end up with a simple state chart to describe the drive control signal that will be sent to the drive control process. State 1 - Stop Waiting for a proper direction signal. The throttle must be zero and both direction switches off before exiting this state. Only one transition allowed which is to neutral when the previous conditions are satisfied. On Entry Action -> DriveRequest = 0; State 2 - Neutral Waiting for direction. Multiple possible transistions On Entry Action -> DriveRequest = 0; Tr A - ((Throttle > 0) || (Forward && Reverse)) Back to Stop. State 1 Tr B - (Forward && !Reverse) To Forward. State 3 Tr C - (!Forward && Reverse) To Reverse. State 4 State 3 - Forward. Multiple possible transistions During Action -> DriveRequest = Throttle; Tr A - (Forward && Reverse) To Stop. State 1 Tr B - (!Forward && Reverse) To Reverse. State 4 Tr C - (!Forward && !Reverse) To Neutral. State 2 State 4 - Reverse. Multiple possible transistions During Action -> DriveRequest = -Throttle; Tr A - (Forward && Reverse) To Stop. State 1 Tr B - (Forward && !Reverse) To Forward. State 3 Tr C - (!Forward && !Reverse) To Neutral. State 2 Now I suppose you could take each possible throttle setting as a separate state but... I would argue that the during action doesn't actually cause any change of state, it is essential to proper operation though.
> I have a similar problem with exit actions. If they do something > useful, then the state of the application is different than it was when > the entry action completed and it is different than the result of any > actions associated with the target state. IOW, one really has an > intermediate FSM state that isn't shown in the FSM. If purists could > get upset enough about Moore to provide Mealy, they would surely be > uptight about this. B-)
Let me pose another simple example. Some states need to be reflected to the operator in an explicit fashion so for a state that needs this I might have the following: On Entry Action -> SetIndicatorLamp(); On Exit Action -> ClearIndicatorLamp(); Also, rather than setting a lamp this might be something essential to operation like turning on lubrication or cooling. Now this could be simulated with multiple states and transitions but this introduces timing issues for clocked machines (there are workarounds) and expands the number of states for IMHO no apparent good reason.
> As it happens I can accept exit actions in an OO context because object > FSMs have some of their input alphabet provided by state variables > rather than event data packets. So the notion of processing one subset > of the input on entry and another subset on exit makes some degree of > sense -- given that the OO context also has to deal with actions taking > finite time because Moore is a better fit. IOW, to accept exit actions > one is accepting the same furry boundary between states that one accepts > with the Moore FSM model. > > So I can rationalize exit actions, but "during actions" are far too > open-ended in their abuse of the notion of 'state'. As a practical > matter one has mechanisms to deal with ambiguities around actions taking > finite time to execute (e.g., an event queue waiting until the current > event is fully consumed before popping the next event) on the boundary > between states. But there are no equivalent mechanisms for managing a > "during action" that is executing in the background even when the object > is quiescent. Essentially one is introducing concurrent processing > without benefit of management.
Ahh, maybe I see. A during action doesn't imply a background execution process. It implies an action that takes place on each cycle of the state machine. See my note about clocked execution earlier. Robert -- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...

>>>>One is required to "follow" those transitions in the software external >>>>to the FSM in the sense that events must be generated and delivered in >>>>an order consistent with the FSM structure (i.e., events arrive when the >>>>FSM is in the proper current state). But I think that is a separate >>>>problem for asynchronous communications (e.g., handshaking protocols) >>>>and serializing mechanisms like event queues. >>> >>> >>>I can see you could build a FSM this way and it might even be required >>>in some cases but it does seem rather cumbersome. It seems to require >>>two copies of the FSM one to perform the transitions and one to decide >>>which transitions are valid. Surely part of the essence of a state >>>machine is you deal with events as they occur rather than reording them >>>to suit? >> >>Sorry, but you have lost me here. I only see one FSM. Defining the >>states and transitions in an FSM is driven by the problem space. The >>result of that process of problem space abstraction is the <single> FSM >>that executes as the problem is solved. > > > It appears to be implied by your requirement above that the software > external to the FSM must know what state the FSM is in in order ro > generate the proper events.
The software external to the FSM does not even have to know the FSM exists. The event is simply an announcement of something that happened externally. It is the job of the developer to determine who cares (i.e., which FSM) about what happened and address the event properly (e.g., at the level of a UML Interaction Diagram).
>>Events are just messages that announce some change in the state of the >>overall problem solution. > > > And here you lose me again. > > 1 - Events cause transitions > 2 - Transistions change states > 3 - Changes in state are annouced via events > 4 - See step 1
Your step (3) is essentially what I am talking about. When the state changes in a particular FSM, that manifests a change in the overall state of the solution. So the event generated in (3) is an announcement of that change. However, the link between (3) and (1) is achieved by addressing that announcement to an FSM that cares about the change. That mapping is driven by the overall solution to the problem (e.g., algorithmic sequencing or data integrity issues for state variables) rather than any inherent expectation of what should happen next _in the action for (3)_. Note the the underlying rules for FSAs stipulate that a state cannot know what the prior state was or the next state will be. So the action in (3) cannot anticipate what transition in (1) will be triggered (or even what FSM that transition lives in).
>>>>>>Even in a trivial case like: >>>>>> >>>>>>[Opened] >>>>>> | ^ >>>>>> | | >>>>>> V | >>>>>>[Closed] >>>>>> >>>>>>there are problem space rules that say that it makes no sense to execute >>>>>>the [Opened] action twice in succession. >>>>> >>>>> >>>>>Which would be why the during action is such a state would be null >>>>>presumably. Or the opened state would have a transition to an idle >>>>>state occupied once the open was successful. >>>> >>>>I'm not sure what you mean by "during action". >>> >>> >>>OK, the FSMs I build use the following basic contructs. >>> >>> Transitions with >>> conditions (such as load > LOAD_MAX) >>> actions (such as motor_off(); ) >>> States with >>> on-entry actions executed on entry to the state >>> on-exit actions executed on exit from the state >>> during actions executed while in the state. >> >>IOW, a "during action" is something like a continuously running polling >>loop? FWIW, I think that notion violates the basic rules of finite >>state automata in a major way. > > > No, it's a periodically executed action. It performs actions, I don't > think I've ever done one that polled input.
OK, but I think my same arguments apply so long as those activities occur /while/ the object in some state. Typically that sort of periodic behavior is handled with timers. The timer generates an event that triggers a transition in some FSM and the action executes the periodic behavior. Thus each execution of the periodic action is triggered by an individual event and there is a transition of the FSM (albeit usually reflexive). [Note that in OOA/D the timers, like event queues, are not even explicitly modeled. They are assumed to be implemented in some architectural subsystem.]
>>In an FSA, the action processes the input alphabet and it assumed to be >>instantaneous. [The Mealy FSM model was developed because some purists >>had a problem with the fact that actions took finite time to execute in >>practice and that meant there was an ambiguous period when the FSM was >>not in either the prior state or the new state for the transition. >>Putting actions on transitions allowed the FSM to remain in the prior >>state until the transition was completed and then instantaneously >>transition to the target state.] > > > A quick aside on timing. The transistions may in some abstract sense be > instantaneous but in most of the state machines I write the transitions > from state to state are 'clocked' in the sense they can take place only > at certain regular intervals. This clocking is vital to the correct > behaviour.
That's fine, but I think it is a separate issue that one handles with timers and explicit events/transitions in the FSM. The Mealy/Moore issue is about the ambiguity of what state the FSM is in while the action is executing. It doesn't make any difference because we have other rules, such as an event queue only popping one event at a time, that ensure the ambiguity is transparent in practice. IOW, the infrastructure around the FSM ensures the software behaves exactly _as if_ the action execution were instantaneous.
>>I would also argue that for the "during action" to do anything useful it >>must somehow change the state of the overall solution (e.g., generate an >>event or set an attribute if the hardware provides an interrupt). IOW, >>the action must do something that will observable externally or after >>its completion. Otherwise there would be no way to determine that it >>actually did anything. So if the "during action" does do something >>visible outside the state, then it is modifying the the state. This is >>particularly worrisome because that change could take place _at any >>time_ while the object is supposedly in the state. > > > Let me provide a simplified example. Consider a motor control with the > following inputs: > - Forward (on or off) > - Reverse (on or off) > - Throttle (0 to Max) > > From these and domain knowledge (which I leave out for brevity) we end > up with a simple state chart to describe the drive control signal that > will be sent to the drive control process. > > State 1 - Stop Waiting for a proper direction signal. The throttle > must be zero and both direction switches off before exiting this state. > Only one transition allowed which is to neutral when the previous > conditions are satisfied. > On Entry Action -> DriveRequest = 0; > > State 2 - Neutral Waiting for direction. Multiple possible > transistions > On Entry Action -> DriveRequest = 0; > Tr A - ((Throttle > 0) || (Forward && Reverse)) Back to Stop. > State 1 > Tr B - (Forward && !Reverse) To Forward. State 3 > Tr C - (!Forward && Reverse) To Reverse. State 4 > > > State 3 - Forward. Multiple possible transistions > During Action -> DriveRequest = Throttle; > Tr A - (Forward && Reverse) To Stop. State 1 > Tr B - (!Forward && Reverse) To Reverse. State 4 > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > State 4 - Reverse. Multiple possible transistions > During Action -> DriveRequest = -Throttle; > Tr A - (Forward && Reverse) To Stop. State 1 > Tr B - (Forward && !Reverse) To Forward. State 3 > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > Now I suppose you could take each possible throttle setting as a > separate state but... I would argue that the during action doesn't > actually cause any change of state, it is essential to proper operation > though.
I am reluctant to pull a Topmind and start critiquing the FSM for reasons unrelated to the point in hand (using "during actions"). Instead, let just say I think I would do it differently... B-) Apropos of my point above, I think I would want an FSM where one of the events signaled a change in throttle because changing the throttle setting seems like it it quite important to running a motor. I am also suspicious that the notions of 'forward' and 'reverse' can be completely captured in object attributes rather than FSM states. That's because the direction and throttle settings are really just register writes of values. IOW, I think When one is allowed to change direction and throttle is more important to the solution than the specific values. So I would probably abstract an object like: [Motor] + direction + currentThrottleSetting with an FSM something like (assuming the motor must stop before changing direction when running): E3:ThrottleChange +-------+ | | | V [ThrottleChanged] <---------------+ | | | E1:Stop | V | [Stopped] | E3:ThrottleChange | | | E2:DirectionChange | V | [DirectionChanged]----------------+ State: Stopped. Same as yours State: DirectionChanged. Changes Motor.direction and talks to hardware. State: ThrottleChanged. Changes Motor.currentThrottleSetting and talks to hardware. If Motor.currentThrottleSetting is 0, generate E1:Stop. Event: E1:Stop () Event: E2:DirectionChange (direction) Event: E3:ThrottleChange (setting) [A purist would get bent over E1 being a self-directed event but this happens to be one of the classic examples where avoiding it would require additional states and transitions that would (IMO) substantially reduce comprehensibility. So it is a practical trade-off I am willing to make.] Note that if the hardware allows the direction to be reversed without stopping, then all one adds are a couple of more transitions for E2 and E3 events. Also note that in addition to eliminating the "during action", this model also eliminates the complexity of conditional transitions. Bottom line: I think one can construct relatively simple FSMs without "during actions".
>>I have a similar problem with exit actions. If they do something >>useful, then the state of the application is different than it was when >>the entry action completed and it is different than the result of any >>actions associated with the target state. IOW, one really has an >>intermediate FSM state that isn't shown in the FSM. If purists could >>get upset enough about Moore to provide Mealy, they would surely be >>uptight about this. B-) > > > Let me pose another simple example. Some states need to be reflected to > the operator in an explicit fashion so for a state that needs this I > might have the following: > On Entry Action -> SetIndicatorLamp(); > On Exit Action -> ClearIndicatorLamp(); > > Also, rather than setting a lamp this might be something essential to > operation like turning on lubrication or cooling. > > Now this could be simulated with multiple states and transitions but > this introduces timing issues for clocked machines (there are > workarounds) and expands the number of states for IMHO no apparent good > reason.
Not necessarily. I think a lot depends upon where one allocates the intelligence in the overall solution. One can imagine | | E1:toggle V [IndicatorChanged] <--------+ | | | | +-------------------+ E1:toggle for the first example. Here the ON/OFF state is maintained as a state variable and one just writes to the hardware based on <changing> the current value. The real smarts that understands the broader context and determines WHEN the indicator needs to change lives elsewhere. For the second example, lubrication vs. cooling, I submit that in an OO context those are distinct behavior responsibilities at the object level that should be self-contained and encapsulated. That is, they each represent a unique set of rules and policies in the hardware control realm. When mapping to object FSMs, one usually thinks of a state as a condition where a unique suite of rules and policies prevails. So I submit that in an OO context one /wants/ to associate lubrication and cooling with different states to decouple them explicitly. If one does that, then managing the object FSM interactions becomes a whole lot easier. However, I think this is somewhat academic since I already agreed that exit actions have their uses in practice and the theoretical issues really aren't a problem in practice. So let's agree to partially agree on exit actions.
>>As it happens I can accept exit actions in an OO context because object >>FSMs have some of their input alphabet provided by state variables >>rather than event data packets. So the notion of processing one subset >>of the input on entry and another subset on exit makes some degree of >>sense -- given that the OO context also has to deal with actions taking >>finite time because Moore is a better fit. IOW, to accept exit actions >>one is accepting the same furry boundary between states that one accepts >>with the Moore FSM model. >> >>So I can rationalize exit actions, but "during actions" are far too >>open-ended in their abuse of the notion of 'state'. As a practical >>matter one has mechanisms to deal with ambiguities around actions taking >>finite time to execute (e.g., an event queue waiting until the current >>event is fully consumed before popping the next event) on the boundary >>between states. But there are no equivalent mechanisms for managing a >>"during action" that is executing in the background even when the object >>is quiescent. Essentially one is introducing concurrent processing >>without benefit of management. > > > Ahh, maybe I see. A during action doesn't imply a background execution > process. It implies an action that takes place on each cycle of the > state machine. See my note about clocked execution earlier.
Then I'm now confused. B-) What do you mean by "each cycle of the state machine"? In particular, what is actually going on in your FSM where you have: During Action -> DriveRequest = Throttle How does the During Action get invoked if there is no event triggering a transition? (I assumed it was some asynchronous mechanism like a callback method being invoked, but that invocation would be independent of the FSM cycle.) What exactly is a Drive Request? (I assumed it was some attribute.) What does During Action actually do? (I assumed something more than just setting the DriveRequest attribute, since that would just be an orthogonal knowledge setter.) How do you ensure that this During Action is not invoked when the FSM is in some other state? ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
In article <L9ylh.6082$c94.5368@trndny09>, H. S. Lahman says...
> Responding to Adsett... > > >>>>One is required to "follow" those transitions in the software external > >>>>to the FSM in the sense that events must be generated and delivered in > >>>>an order consistent with the FSM structure (i.e., events arrive when the > >>>>FSM is in the proper current state). But I think that is a separate > >>>>problem for asynchronous communications (e.g., handshaking protocols) > >>>>and serializing mechanisms like event queues. > >>> > >>> > >>>I can see you could build a FSM this way and it might even be required > >>>in some cases but it does seem rather cumbersome. It seems to require > >>>two copies of the FSM one to perform the transitions and one to decide > >>>which transitions are valid. Surely part of the essence of a state > >>>machine is you deal with events as they occur rather than reording them > >>>to suit? > >> > >>Sorry, but you have lost me here. I only see one FSM. Defining the > >>states and transitions in an FSM is driven by the problem space. The > >>result of that process of problem space abstraction is the <single> FSM > >>that executes as the problem is solved. > > > > > > It appears to be implied by your requirement above that the software > > external to the FSM must know what state the FSM is in in order ro > > generate the proper events. > > The software external to the FSM does not even have to know the FSM > exists.
Beg pardon? 'One is required to "follow" those transitions in the software external to the FSM'
> The event is simply an announcement of something that happened > externally.
OK, but that appears to be inconsistent with 'events arrive when the FSM is in the proper current state'. Maybe you meant something different but that reads to me as the events the FSM recieves depends on the state it is in, and the 'required to follow' reads as the external SW is reponsible for ensuring that the proper filtering and sorting is done to ensure the proper arrival of the events.
> It is the job of the developer to determine who cares > (i.e., which FSM) about what happened and address the event properly > (e.g., at the level of a UML Interaction Diagram).
Um, yes, of course. But what has that to do with the original statement? Methinks we have a language gap of some sort.
> > >>Events are just messages that announce some change in the state of the > >>overall problem solution. > > > > > > And here you lose me again. > > > > 1 - Events cause transitions > > 2 - Transistions change states > > 3 - Changes in state are annouced via events > > 4 - See step 1 > > Your step (3) is essentially what I am talking about. When the state > changes in a particular FSM, that manifests a change in the overall > state of the solution. So the event generated in (3) is an announcement > of that change. > > However, the link between (3) and (1) is achieved by addressing that > announcement to an FSM that cares about the change.
So there's more than one FSM involved? That changes things. If you are generating events in one FSM to be consumed in other separate FSMs then in that case all you are saying is the output of an FSM is useful.
> That mapping is > driven by the overall solution to the problem (e.g., algorithmic > sequencing or data integrity issues for state variables) rather than any > inherent expectation of what should happen next _in the action for (3)_.
I'm confused again. What mapping are you talking about?
> Note the the underlying rules for FSAs stipulate that a state cannot > know what the prior state was or the next state will be. So the action > in (3) cannot anticipate what transition in (1) will be triggered (or > even what FSM that transition lives in).
Say what?
> >>>OK, the FSMs I build use the following basic contructs. > >>> > >>> Transitions with > >>> conditions (such as load > LOAD_MAX) > >>> actions (such as motor_off(); ) > >>> States with > >>> on-entry actions executed on entry to the state > >>> on-exit actions executed on exit from the state > >>> during actions executed while in the state. > >> > >>IOW, a "during action" is something like a continuously running polling > >>loop? FWIW, I think that notion violates the basic rules of finite > >>state automata in a major way. > > > > > > No, it's a periodically executed action. It performs actions, I don't > > think I've ever done one that polled input. > > OK, but I think my same arguments apply so long as those activities > occur /while/ the object in some state. > > Typically that sort of periodic behavior is handled with timers. The > timer generates an event that triggers a transition in some FSM and the > action executes the periodic behavior. Thus each execution of the > periodic action is triggered by an individual event and there is a > transition of the FSM (albeit usually reflexive).
Yes it could be simulated by a reflexive transistion. If it makes you any happier think of it as a reflexive transition that skips any on- entry or on-exit actions. I see no way that it is any different. It just leaves the diagram a little cleaner.
> > A quick aside on timing. The transistions may in some abstract sense be > > instantaneous but in most of the state machines I write the transitions > > from state to state are 'clocked' in the sense they can take place only > > at certain regular intervals. This clocking is vital to the correct > > behaviour. > > That's fine, but I think it is a separate issue that one handles with > timers and explicit events/transitions in the FSM.
Not at all, that would clutter up the FSM with timers on every transition.
> > Let me provide a simplified example. Consider a motor control with the > > following inputs: > > - Forward (on or off) > > - Reverse (on or off) > > - Throttle (0 to Max) > > > > From these and domain knowledge (which I leave out for brevity) we end > > up with a simple state chart to describe the drive control signal that > > will be sent to the drive control process. > > > > State 1 - Stop Waiting for a proper direction signal. The throttle > > must be zero and both direction switches off before exiting this state. > > Only one transition allowed which is to neutral when the previous > > conditions are satisfied. > > On Entry Action -> DriveRequest = 0; > > > > State 2 - Neutral Waiting for direction. Multiple possible > > transistions > > On Entry Action -> DriveRequest = 0; > > Tr A - ((Throttle > 0) || (Forward && Reverse)) Back to Stop. > > State 1 > > Tr B - (Forward && !Reverse) To Forward. State 3 > > Tr C - (!Forward && Reverse) To Reverse. State 4 > > > > > > State 3 - Forward. Multiple possible transistions > > During Action -> DriveRequest = Throttle; > > Tr A - (Forward && Reverse) To Stop. State 1 > > Tr B - (!Forward && Reverse) To Reverse. State 4 > > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > > > State 4 - Reverse. Multiple possible transistions > > During Action -> DriveRequest = -Throttle; > > Tr A - (Forward && Reverse) To Stop. State 1 > > Tr B - (Forward && !Reverse) To Forward. State 3 > > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > > > Now I suppose you could take each possible throttle setting as a > > separate state but... I would argue that the during action doesn't > > actually cause any change of state, it is essential to proper operation > > though. > > I am reluctant to pull a Topmind and start critiquing the FSM for > reasons unrelated to the point in hand (using "during actions"). > Instead, let just say I think I would do it differently... B-) > > Apropos of my point above, I think I would want an FSM where one of the > events signaled a change in throttle because changing the throttle > setting seems like it it quite important to running a motor.
One of the issues with that is the throttle changes continuously. This sort of state machine usually executes one cycle per control loop. A throttle changed event would fire every cycle. It's a lot simpler to just view it as a continuous input.
> I am also > suspicious that the notions of 'forward' and 'reverse' can be completely > captured in object attributes rather than FSM states. That's because > the direction and throttle settings are really just register writes of > values.
Ultimately everything can be completely captured with attributes and calculated as needed. A state machine just captures some of that information in the state. The key is whether the state machine captures the intent in a simpler and/or more robust fashion. Of course many of those constructs will just be state machines developed in a more opaque fashion. The incoming signals can indicate forward, reverse, neutral or be invalid. The throttle can independantly be anywhere in its range. In a complete example it could also be out of range but I did want a simple example :) I also don't deal here with finite allowable tme to switch directions, deadman switches and anti-tiedown logic :) As a result of these the output could be forward, reverse, neutral or stop. Forward and reverse are distinct, it's tempting to treat them identically but there is usually an assymetry in speed or some other associated behaviour. You could treat forward and reverse the same but IME it's easier to disentangle them here rather than later. And once you treat them separately they really are distinct states. There is duplication only in the degenerate case. There is not a lot of distinction visible in this example between neutral and stop but they are different. Neutral is a normal operating state but stop is a fault state from which the operator is required to return to a specified starting setup before continuing. I'll try to make the distinction clearer in the modified example.
> IOW, I think When one is allowed to change direction and > throttle is more important to the solution than the specific values. So > I would probably abstract an object like: > > [Motor] > + direction > + currentThrottleSetting > > with an FSM something like (assuming the motor must stop before changing > direction when running):
Hmm, I don't think I was clear enough here. Actually I wasn't clear at all, my apologies. This FSM describes the evaluation of the control signals not the motor control. The actual motor control is done elsewhere.
> E3:ThrottleChange > +-------+ > | | > | V > [ThrottleChanged] <---------------+ > | | > | E1:Stop | > V | > [Stopped] | E3:ThrottleChange > | | > | E2:DirectionChange | > V | > [DirectionChanged]----------------+ > > State: Stopped. Same as yours
Hmm, I'm not sure it does. It looks closer to my neutral state. but I think I simplified my neutral state too much.
> > State: DirectionChanged. Changes Motor.direction and talks to hardware. > > State: ThrottleChanged. Changes Motor.currentThrottleSetting and talks > to hardware. If Motor.currentThrottleSetting is 0, generate E1:Stop. > > Event: E1:Stop () > Event: E2:DirectionChange (direction) > Event: E3:ThrottleChange (setting) > > [A purist would get bent over E1 being a self-directed event but this > happens to be one of the classic examples where avoiding it would > require additional states and transitions that would (IMO) substantially > reduce comprehensibility. So it is a practical trade-off I am willing > to make.]
Purists didn't much like Dirac deltas when they were introduced either. That didn't prevent everybody else from using them to advantage though. Not that I'm claiming any of this approaches the usefulness of a delta function though. :)
> Note that if the hardware allows the direction to be reversed without > stopping, then all one adds are a couple of more transitions for E2 and > E3 events. Also note that in addition to eliminating the "during > action", this model also eliminates the complexity of conditional > transitions.
?? The transitions are still conditional, they still rely on the events occuring. I see no difference between your conditions and the conditions I used other than a layer of syntactic sugar. You are also missing start sequencing and the direction interlock both of which are critical.
> > Bottom line: I think one can construct relatively simple FSMs without > "during actions".
This reworking partly works as long as the directions are symmetrical but it also moves a fair piece of the logic outside the state machine making it less clear what is happening. You have removed the during action but at the expense of implementing it elsewhere. It's now more difficult to tell if the result is correct. It's certainly possible to implement FSMs without during actions. It's also possible to implement procedural code without for, while or do loops. That doesn't mean the constructs are not useful though.
> > Let me pose another simple example. Some states need to be reflected to > > the operator in an explicit fashion so for a state that needs this I > > might have the following: > > On Entry Action -> SetIndicatorLamp(); > > On Exit Action -> ClearIndicatorLamp(); > > > > Also, rather than setting a lamp this might be something essential to > > operation like turning on lubrication or cooling. > > > > Now this could be simulated with multiple states and transitions but > > this introduces timing issues for clocked machines (there are > > workarounds) and expands the number of states for IMHO no apparent good > > reason. > > Not necessarily. I think a lot depends upon where one allocates the > intelligence in the overall solution. One can imagine > > | > | E1:toggle > V > [IndicatorChanged] <--------+ > | | > | | > +-------------------+ > E1:toggle > > for the first example. Here the ON/OFF state is maintained as a state > variable and one just writes to the hardware based on <changing> the > current value. The real smarts that understands the broader context and > determines WHEN the indicator needs to change lives elsewhere.
Doesn't that add another state machine where previously there was one? It also changes an absolute set/clear to a toggle. Something I'd be reluctant to do without a lot bigger benefit than getting rid of exit actions.
> >>So I can rationalize exit actions, but "during actions" are far too > >>open-ended in their abuse of the notion of 'state'. As a practical > >>matter one has mechanisms to deal with ambiguities around actions taking > >>finite time to execute (e.g., an event queue waiting until the current > >>event is fully consumed before popping the next event) on the boundary > >>between states. But there are no equivalent mechanisms for managing a > >>"during action" that is executing in the background even when the object > >>is quiescent. Essentially one is introducing concurrent processing > >>without benefit of management. > > > > > > Ahh, maybe I see. A during action doesn't imply a background execution > > process. It implies an action that takes place on each cycle of the > > state machine. See my note about clocked execution earlier. > > Then I'm now confused. B-) What do you mean by "each cycle of the > state machine"? In particular, what is actually going on in your FSM > where you have: > > During Action -> DriveRequest = Throttle > > How does the During Action get invoked if there is no event triggering a > transition? (I assumed it was some asynchronous mechanism like a > callback method being invoked, but that invocation would be independent > of the FSM cycle.) What exactly is a Drive Request? (I assumed it was > some attribute.)
Caareful about your assumptions ;). It's just meant to be an assignment statement. The value is then fed on to the actual motor control which could be another state machine or a D/A setting to another controller entirely or ....
> What does During Action actually do? (I assumed > something more than just setting the DriveRequest attribute, since that > would just be an orthogonal knowledge setter.) How do you ensure that > this During Action is not invoked when the FSM is in some other state?
I don't understand the question, how could it get invoked if you were in another state? Let me revise the example a bit to include asymmetry in the directions as would be typical. I'll also walk through a couple of iterations so you can get an idea of how the during actions work. State 1 - Stop Waiting for a proper direction signal. The throttle must be zero and both direction switches off before exiting this state. Only one transition allowed which is to neutral when the previous conditions are satisfied. On Entry Action -> DriveRequest = 0; State 2 - Neutral Waiting for direction. Multiple possible transistions On Entry Action -> DriveRequest = 0; Tr A - (Forward && Reverse) Back to Stop. State 1 Tr B - (Forward && !Reverse) To Forward. State 3 Tr C - (!Forward && Reverse) To Reverse. State 4 State 3 - Forward. Multiple possible transistions During Action -> DriveRequest = Throttle; Tr A - (Forward && Reverse) To Stop. State 1 Tr B - (!Forward && Reverse) To Reverse. State 4 Tr C - (!Forward && !Reverse) To Neutral. State 2 State 4 - Reverse. Multiple possible transistions On Entry Action -> SetReverseAlarm(); During Action -> DriveRequest = -Throttle/2; On Exit Action -> ClearReverseAlarm(); Tr A - (Forward && Reverse) To Stop. State 1 Tr B - (Forward && !Reverse) To Forward. State 3 Tr C - (!Forward && !Reverse) To Neutral. State 2 Note 1: The reverse alarm setup is more naive than would actually be used (by a fair amount) but it keeps the example simpler. Note 2: I've modified the neutral state to more properly reflect the difference between it and the stop state. In a less naive example the neutral state would be a little more complex. The statechart is implemented as a function, each call check for valid transitions and performs them before returning. The values checked and returned will be in the argument list, I'll leave the details out. Now to walk through. The state machine is already initialized to be in state 1 Time=t0 Conditions - Forward and Reverse are false, throttle is 0, DriveRequest is 0 (from entering state 1 some time previously) call to statechart state changes to state 2 DriveRequest is set to 0 returns Time=t1 Conditions - Forward is false, Reverse is true, throttle is 0 call to statechart state changes to state 4 DriveRequest is set to 0 call to SetReverseAlarm() returns Time=t2 Conditions - Forward is false, Reverse is true, throttle is 500 call to statechart DriveRequest is set to -250 returns Time=t3 Conditions - Forward is false, Reverse is true, throttle is 490 call to statechart DriveRequest is set to -245 returns Time=t4 Conditions - Forward is true, Reverse is false, throttle is 310 call to statechart call to ClearReverseAlarm() state changes to state 3 DriveRequest is set to 310 returns etc... And of course this could be implemented in just about any language C, ASM, ST or even as a method in an OO language. Robert -- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...

It wasn't until I got to the end that I realized most of this thread is 
a tempest in a teapot and we have been talking past on another.  You 
might want to skip to the end an read my closing comments first.

In addition, I am suspicious that you are not developing in an OO 
environment despite posting to comp.object (where I live).

>>>>>>One is required to "follow" those transitions in the software external >>>>>>to the FSM in the sense that events must be generated and delivered in >>>>>>an order consistent with the FSM structure (i.e., events arrive when the >>>>>>FSM is in the proper current state). But I think that is a separate >>>>>>problem for asynchronous communications (e.g., handshaking protocols) >>>>>>and serializing mechanisms like event queues. >>>>> >>>>> >>>>>I can see you could build a FSM this way and it might even be required >>>>>in some cases but it does seem rather cumbersome. It seems to require >>>>>two copies of the FSM one to perform the transitions and one to decide >>>>>which transitions are valid. Surely part of the essence of a state >>>>>machine is you deal with events as they occur rather than reording them >>>>>to suit? >>>> >>>>Sorry, but you have lost me here. I only see one FSM. Defining the >>>>states and transitions in an FSM is driven by the problem space. The >>>>result of that process of problem space abstraction is the <single> FSM >>>>that executes as the problem is solved. >>> >>> >>>It appears to be implied by your requirement above that the software >>>external to the FSM must know what state the FSM is in in order ro >>>generate the proper events. >> >>The software external to the FSM does not even have to know the FSM >>exists. > > > Beg pardon? 'One is required to "follow" those transitions in the > software external to the FSM'
As I explained in the description of applying DbC, the developer can decide where <announcement> events go /after/ designing the object FSMs. So one does not need to know anything about that when designing an individual object FSM. Hence the individual object FSM is independent of context and does not need to know the receiving FSM even exists. What I was referring to with the "follow" remark was that object FSMs are not designed in a vacuum. Objects are abstracted from the problem space with one eye on the problem to be solved. That is, the object abstraction is tailored to the needs of the overall solution by determining what knowledge and behavior responsibilities must be abstracted to solve the problem in hand. The OO paradigm provides methodological guidance for how to do problem space abstraction (e.g., defining logically indivisible behavior responsibilities) that ensures that once the object is properly abstracted, an asynchronous behavior communication model will Just Work if one uses object state machines. For example, handshaking is an ancient notion in R-T/E. So the traditional way of designing interacting FSMs was to define handshaking protocols for synchronization and then build the FSMs around those protocols. But what those protocols were really doing is providing a systematic approach to ensuring a functional granularity that was detailed enough so that one could connect the flow of control dots with messages. The OO paradigm essentially already provides that when doing problem space abstraction. You lubrication vs. cooling example demonstrates that. The OO paradigm dictates that they are distinct responsibilities that need to be encapsulated separately and decoupled. That leads to associating each one with its own state so they are triggered by different messages. In turn, that guarantees a granularity such that one can synchronize the flow of control by connecting the dots with individual events using DbC (with a little serialization help from the event queue).
>>The event is simply an announcement of something that happened >>externally. > > > OK, but that appears to be inconsistent with 'events arrive when the > FSM is in the proper current state'. Maybe you meant something > different but that reads to me as the events the FSM recieves depends on > the state it is in, and the 'required to follow' reads as the external > SW is reponsible for ensuring that the proper filtering and sorting is > done to ensure the proper arrival of the events.
I submit that is the only way a rigorous DbC approach to flow of control can work. The event cannot depend on what is going to happen; it can only depend on what it is announcing that the sender did. As for the synchronization with current state, that is what DbC provides in the OO paradigm (or handshaking protocols in non-OO paradigms).
>>It is the job of the developer to determine who cares >>(i.e., which FSM) about what happened and address the event properly >>(e.g., at the level of a UML Interaction Diagram). > > > Um, yes, of course. But what has that to do with the original statement?
I was responding to your assertion: "It appears to be implied by your requirement above that the software external to the FSM must know what state the FSM is in in order to generate the proper events." I was trying to explain why that inference is not valid.
>>>>Events are just messages that announce some change in the state of the >>>>overall problem solution. >>> >>> >>>And here you lose me again. >>> >>> 1 - Events cause transitions >>> 2 - Transistions change states >>> 3 - Changes in state are annouced via events >>> 4 - See step 1 >> >>Your step (3) is essentially what I am talking about. When the state >>changes in a particular FSM, that manifests a change in the overall >>state of the solution. So the event generated in (3) is an announcement >>of that change. >> >>However, the link between (3) and (1) is achieved by addressing that >>announcement to an FSM that cares about the change. > > > So there's more than one FSM involved? That changes things. If you are > generating events in one FSM to be consumed in other separate FSMs then > in that case all you are saying is the output of an FSM is useful.
Purists would argue that self-directed events are illegal; that all the events triggering transitions must be generated outside the FSM. In addition, the events must be synchronized in some manner with the inherent sequencing rules of the FSM transitions. So there are almost always at least two FSMs. In an OO application if FSMs are used at all, then every object having behavior responsibilities will have an FSM. (In translation methodologies the use of FSMs is mandatory for all applications.)
>>That mapping is >>driven by the overall solution to the problem (e.g., algorithmic >>sequencing or data integrity issues for state variables) rather than any >>inherent expectation of what should happen next _in the action for (3)_. > > > I'm confused again. What mapping are you talking about?
The mapping between the event generated in (3) and what transition it triggers in (1).
>>Note the the underlying rules for FSAs stipulate that a state cannot >>know what the prior state was or the next state will be. So the action >>in (3) cannot anticipate what transition in (1) will be triggered (or >>even what FSM that transition lives in). > > > Say what?
In an FSA the state action can only process the input alphabet. IOW, the only thing the state action can understand about context is the provided alphabet.
>>>>>OK, the FSMs I build use the following basic contructs. >>>>> >>>>> Transitions with >>>>> conditions (such as load > LOAD_MAX) >>>>> actions (such as motor_off(); ) >>>>> States with >>>>> on-entry actions executed on entry to the state >>>>> on-exit actions executed on exit from the state >>>>> during actions executed while in the state. >>>> >>>>IOW, a "during action" is something like a continuously running polling >>>>loop? FWIW, I think that notion violates the basic rules of finite >>>>state automata in a major way. >>> >>> >>>No, it's a periodically executed action. It performs actions, I don't >>>think I've ever done one that polled input. >> >>OK, but I think my same arguments apply so long as those activities >>occur /while/ the object in some state. >> >>Typically that sort of periodic behavior is handled with timers. The >>timer generates an event that triggers a transition in some FSM and the >>action executes the periodic behavior. Thus each execution of the >>periodic action is triggered by an individual event and there is a >>transition of the FSM (albeit usually reflexive). > > > Yes it could be simulated by a reflexive transistion. If it makes you > any happier think of it as a reflexive transition that skips any on- > entry or on-exit actions. I see no way that it is any different. It > just leaves the diagram a little cleaner.
You can only do that with a Mealy model because the action depends on the transition rather than the state. As I indicated, I think the Moore model is better suited to the OO paradigm. Since Moore and Mealy models are convertible, though, one could always convert the Mealy to a Moore (albeit possibly at the cost of an extra state). So one can get to the same <Moore> place without "during actions". My argument here is that if the "during action" is triggered by something other than a transition, then one is asking for trouble because one cannot rely on the usual infrastructures like event queues to ensure data and referential integrity "for free".
>>>A quick aside on timing. The transistions may in some abstract sense be >>>instantaneous but in most of the state machines I write the transitions >>>from state to state are 'clocked' in the sense they can take place only >>>at certain regular intervals. This clocking is vital to the correct >>>behaviour. >> >>That's fine, but I think it is a separate issue that one handles with >>timers and explicit events/transitions in the FSM. > > > Not at all, that would clutter up the FSM with timers on every > transition.
The timers aren't in the FSM. They are architectural mechanisms that are orthogonal to the FSM. In an OOA/D model they wouldn't even appear explicitly; they would be manifested in external events that trigger the transitions in the FSM. In addition, one only uses the timer to provide the sort of periodic triggering that you described. Then the event condition raised is based on some duration of clock time elapsing. That is completely independent of the dynamic sequencing within the solution. So one needs an orthogonal mechanism like timers to deal with it.
>>>Let me provide a simplified example. Consider a motor control with the >>>following inputs: >>> - Forward (on or off) >>> - Reverse (on or off) >>> - Throttle (0 to Max) >>> >>>From these and domain knowledge (which I leave out for brevity) we end >>>up with a simple state chart to describe the drive control signal that >>>will be sent to the drive control process. >>> >>> State 1 - Stop Waiting for a proper direction signal. The throttle >>>must be zero and both direction switches off before exiting this state. >>>Only one transition allowed which is to neutral when the previous >>>conditions are satisfied. >>> On Entry Action -> DriveRequest = 0; >>> >>> State 2 - Neutral Waiting for direction. Multiple possible >>>transistions >>> On Entry Action -> DriveRequest = 0; >>> Tr A - ((Throttle > 0) || (Forward && Reverse)) Back to Stop. >>>State 1 >>> Tr B - (Forward && !Reverse) To Forward. State 3 >>> Tr C - (!Forward && Reverse) To Reverse. State 4 >>> >>> >>> State 3 - Forward. Multiple possible transistions >>> During Action -> DriveRequest = Throttle; >>> Tr A - (Forward && Reverse) To Stop. State 1 >>> Tr B - (!Forward && Reverse) To Reverse. State 4 >>> Tr C - (!Forward && !Reverse) To Neutral. State 2 >>> >>> State 4 - Reverse. Multiple possible transistions >>> During Action -> DriveRequest = -Throttle; >>> Tr A - (Forward && Reverse) To Stop. State 1 >>> Tr B - (Forward && !Reverse) To Forward. State 3 >>> Tr C - (!Forward && !Reverse) To Neutral. State 2 >>> >>>Now I suppose you could take each possible throttle setting as a >>>separate state but... I would argue that the during action doesn't >>>actually cause any change of state, it is essential to proper operation >>>though. >> >>I am reluctant to pull a Topmind and start critiquing the FSM for >>reasons unrelated to the point in hand (using "during actions"). >>Instead, let just say I think I would do it differently... B-) >> >>Apropos of my point above, I think I would want an FSM where one of the >>events signaled a change in throttle because changing the throttle >>setting seems like it it quite important to running a motor. > > > One of the issues with that is the throttle changes continuously. This > sort of state machine usually executes one cycle per control loop. A > throttle changed event would fire every cycle. It's a lot simpler to > just view it as a continuous input.
You mentioned "throttle settings". To me that implies a <smallish> finite number of discrete values. And in your example below you employ discrete values. I am also unsure what you mean by 'cycle' and 'control loop' here. In any event, I don't see how you can view it as continuous changes unless there is a direct hardware link between the physical throttle control and the motor -- in which case the software is irrelevant. Software is digital, which means that it is inherently discrete. In the end a software controller for hardware can only read and write hardware registers at discrete intervals. So one can only emulate analog (continuous) hardware processes with some variant of time slicing and that infrastructure needs to be built into the software explicitly. [I've done hardware controllers for analog devices and it is a real pain. The hardware has to provide the D-to-A conversion. Even then, trying to provide the required granularity is tough to do. So much so that I would be very tempted to put the throttle's continuous emulation (i.e., the infrastructure needed to slice it) in its own object with its own FSM and leave stuff like direction changing to somebody else who is looking at the Big Picture.]
>>I am also >>suspicious that the notions of 'forward' and 'reverse' can be completely >>captured in object attributes rather than FSM states. That's because >>the direction and throttle settings are really just register writes of >>values. > > > Ultimately everything can be completely captured with attributes and > calculated as needed. A state machine just captures some of that > information in the state. The key is whether the state machine captures > the intent in a simpler and/or more robust fashion. Of course many of > those constructs will just be state machines developed in a more opaque > fashion. > > The incoming signals can indicate forward, reverse, neutral or be > invalid. The throttle can independantly be anywhere in its range. In a > complete example it could also be out of range but I did want a simple > example :) I also don't deal here with finite allowable tme to switch > directions, deadman switches and anti-tiedown logic :) > > As a result of these the output could be forward, reverse, neutral or > stop.
My issue is: why can't the incoming signal be changeDirection rather than an explicit Forward/Reverse couplet? The only problem space rule that seems likely to be relevant is that the motor needs to be in Neutral when the direction is changed. The direction itself is just a data element that the hardware interprets. The fact that it is stored in a hardware register rather than a memory location doesn't prevent it from being viewed as an object knowledge attribute that some other object sets.
> > Forward and reverse are distinct, it's tempting to treat them > identically but there is usually an assymetry in speed or some other > associated behaviour. You could treat forward and reverse the same but > IME it's easier to disentangle them here rather than later. And once > you treat them separately they really are distinct states. There is > duplication only in the degenerate case.
>
> There is not a lot of distinction visible in this example between > neutral and stop but they are different. Neutral is a normal operating > state but stop is a fault state from which the operator is required to > return to a specified starting setup before continuing. I'll try to > make the distinction clearer in the modified example.
OK.
>>IOW, I think When one is allowed to change direction and >>throttle is more important to the solution than the specific values. So >>I would probably abstract an object like: >> >>[Motor] >>+ direction >>+ currentThrottleSetting >> >>with an FSM something like (assuming the motor must stop before changing >>direction when running): > > > Hmm, I don't think I was clear enough here. Actually I wasn't clear at > all, my apologies. This FSM describes the evaluation of the control > signals not the motor control. The actual motor control is done > elsewhere.
I agree, that is a big difference. B-) Alas, without more words around what "evaluation" means in your problem context, I can't speculate on how I would eliminate the "during action".
>>Note that if the hardware allows the direction to be reversed without >>stopping, then all one adds are a couple of more transitions for E2 and >>E3 events. Also note that in addition to eliminating the "during >>action", this model also eliminates the complexity of conditional >>transitions. > > > ?? The transitions are still conditional, they still rely on the events > occuring. I see no difference between your conditions and the > conditions I used other than a layer of syntactic sugar. You are also > missing start sequencing and the direction interlock both of which are > critical.
There are no conditional events for my Motor abstraction. The events are raised in other objects that understand when and why, say, a direction needs to be changed. It is up to the developer to connect the flow of control dots via DbC to provide the necessary synchronization unconditionally. For example, Let's say object A has an action, doIt, that issues the E3:changeDirection event. The precondition for transitioning to the A::doIt state is that Motor is in the Stopped state (neutral now). That condition is announced by generating, say, the E52:inNeutral event when the Motor enters that state. The developer then matches the Motor::neutral postcondition to the A::doIt precondition and addresses that event to A's FSM. That handshaking synchronizes the FSMs.
>>Bottom line: I think one can construct relatively simple FSMs without >>"during actions". > > > This reworking partly works as long as the directions are symmetrical > but it also moves a fair piece of the logic outside the state machine > making it less clear what is happening. You have removed the during > action but at the expense of implementing it elsewhere. It's now more > difficult to tell if the result is correct.
I don't buy that argument because one is managing complexity through separating concerns and decomposing functionality into more manageable chunks. Providing better maintainability, of which comprehensibility and verifying correctness are important aspects, is the raison d'etre of the OO paradigm. Providing simple, highly cohesive, and context-independent objects is crucial to achieving that. In addition, DbC provides a quite formal and rigorous technique for ensuring correctness. However, I think the real issue with "during actions" is that they invite problems because they violate the underlying FSA rules. If the "during action" does anything at all useful to the solution, it is actually changing the state of the solution, as manifested by the FSM state. So long as that can happen at any time while the FSM is in a given state, one has opened a Pandora's Box of data and referential integrity problems that are far worse that any delegation of responsibilities among multiple objects. IMO, a "during action" completely trashes the primary value of using FSMs in the first place: providing a disciplined framework for execution.
>>>Let me pose another simple example. Some states need to be reflected to >>>the operator in an explicit fashion so for a state that needs this I >>>might have the following: >>> On Entry Action -> SetIndicatorLamp(); >>> On Exit Action -> ClearIndicatorLamp(); >>> >>>Also, rather than setting a lamp this might be something essential to >>>operation like turning on lubrication or cooling. >>> >>>Now this could be simulated with multiple states and transitions but >>>this introduces timing issues for clocked machines (there are >>>workarounds) and expands the number of states for IMHO no apparent good >>>reason. >> >>Not necessarily. I think a lot depends upon where one allocates the >>intelligence in the overall solution. One can imagine >> >> | >> | E1:toggle >> V >>[IndicatorChanged] <--------+ >> | | >> | | >> +-------------------+ >> E1:toggle >> >>for the first example. Here the ON/OFF state is maintained as a state >>variable and one just writes to the hardware based on <changing> the >>current value. The real smarts that understands the broader context and >>determines WHEN the indicator needs to change lives elsewhere. > > > Doesn't that add another state machine where previously there was one? > It also changes an absolute set/clear to a toggle. Something I'd be > reluctant to do without a lot bigger benefit than getting rid of exit > actions.
I don't think so. I am replacing your state having entry and exit actions with state that has only one entry action. The difference is that instead of two different events in sequence to turn ON and then turn OFF (one transitioning to the state and the other transitioning out of it), one sends two toggle events that both transition to it.
>>>>So I can rationalize exit actions, but "during actions" are far too >>>>open-ended in their abuse of the notion of 'state'. As a practical >>>>matter one has mechanisms to deal with ambiguities around actions taking >>>>finite time to execute (e.g., an event queue waiting until the current >>>>event is fully consumed before popping the next event) on the boundary >>>>between states. But there are no equivalent mechanisms for managing a >>>>"during action" that is executing in the background even when the object >>>>is quiescent. Essentially one is introducing concurrent processing >>>>without benefit of management. >>> >>> >>>Ahh, maybe I see. A during action doesn't imply a background execution >>>process. It implies an action that takes place on each cycle of the >>>state machine. See my note about clocked execution earlier. >> >>Then I'm now confused. B-) What do you mean by "each cycle of the >>state machine"? In particular, what is actually going on in your FSM >>where you have: >> >>During Action -> DriveRequest = Throttle >> >>How does the During Action get invoked if there is no event triggering a >>transition? (I assumed it was some asynchronous mechanism like a >>callback method being invoked, but that invocation would be independent >>of the FSM cycle.) What exactly is a Drive Request? (I assumed it was >>some attribute.) > > > Caareful about your assumptions ;). It's just meant to be an assignment > statement. The value is then fed on to the actual motor control which > could be another state machine or a D/A setting to another controller > entirely or ....
[ed. Here is where we really diverge. It becomes clear later that what you meant by "during action" and what I inferred were two very different things.] But then it is nothing but a knowledge setter and has no business being in an FSM. One uses object FSMs to describe behavior responsibilities. Knowledge and behavior responsibilities are completely different worlds because knowledge accessors are always synchronous in OOA/D while FSMs are inherently asynchronous.
>>What does During Action actually do? (I assumed >>something more than just setting the DriveRequest attribute, since that >>would just be an orthogonal knowledge setter.) How do you ensure that >>this During Action is not invoked when the FSM is in some other state? > > > I don't understand the question, how could it get invoked if you were in > another state?
By your description the "during action" is an action that is invoked while the containing FSM is in a particular state. My understanding of "during" is that the action gets invoked at any arbitrary time within the time interval that the FSM is in that state. Since it is not triggered by an FSM event, someone external to the FSM must invoke it. That invocation mechanism is orthogonal to the FSM invocation mechanism (triggering transitions). Therefore it would seem possible that whoever that is could be invoking the action asynchronously without regard to or knowledge of the current FSM state. So my question is: how do you make sure that external entity only invokes the method when the FSM is in a particular state?
> > Let me revise the example a bit to include asymmetry in the directions > as would be typical. I'll also walk through a couple of iterations so > you can get an idea of how the during actions work. > > State 1 - Stop Waiting for a proper direction signal. The throttle > must be zero and both direction switches off before exiting this state. > Only one transition allowed which is to neutral when the previous > conditions are satisfied. > On Entry Action -> DriveRequest = 0; > > State 2 - Neutral Waiting for direction. Multiple possible > transistions > On Entry Action -> DriveRequest = 0; > Tr A - (Forward && Reverse) Back to Stop. State 1 > Tr B - (Forward && !Reverse) To Forward. State 3 > Tr C - (!Forward && Reverse) To Reverse. State 4 > > > State 3 - Forward. Multiple possible transistions > During Action -> DriveRequest = Throttle; > Tr A - (Forward && Reverse) To Stop. State 1 > Tr B - (!Forward && Reverse) To Reverse. State 4 > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > State 4 - Reverse. Multiple possible transistions > On Entry Action -> SetReverseAlarm(); > During Action -> DriveRequest = -Throttle/2; > On Exit Action -> ClearReverseAlarm(); > Tr A - (Forward && Reverse) To Stop. State 1 > Tr B - (Forward && !Reverse) To Forward. State 3 > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > > Note 1: The reverse alarm setup is more naive than would actually be > used (by a fair amount) but it keeps the example simpler. > > Note 2: I've modified the neutral state to more properly reflect the > difference between it and the stop state. In a less naive example the > neutral state would be a little more complex. > > The statechart is implemented as a function, each call check for valid > transitions and performs them before returning. The values checked and > returned will be in the argument list, I'll leave the details out. > > Now to walk through. The state machine is already initialized to be in > state 1 > > Time=t0 > Conditions - Forward and Reverse are false, throttle is 0, > DriveRequest is 0 (from entering state 1 some time previously) > call to statechart > state changes to state 2 > DriveRequest is set to 0 > returns > > Time=t1 > Conditions - Forward is false, Reverse is true, throttle is 0 > call to statechart > state changes to state 4 > DriveRequest is set to 0 > call to SetReverseAlarm() > returns > > Time=t2 > Conditions - Forward is false, Reverse is true, throttle is 500 > call to statechart > DriveRequest is set to -250 > returns > > Time=t3 > Conditions - Forward is false, Reverse is true, throttle is 490 > call to statechart > DriveRequest is set to -245 > returns > > Time=t4 > Conditions - Forward is true, Reverse is false, throttle is 310 > call to statechart > call to ClearReverseAlarm() > state changes to state 3 > DriveRequest is set to 310 > returns > > etc... > > And of course this could be implemented in just about any language C, > ASM, ST or even as a method in an OO language.
OK. AFAICT, this a function takes arguments of {isForward, isReverse, throttle} and uses them to set the value of DriveRequest and, optionally, invoke two other functions for ReverseAlarm. To do that it needs to understand the history of prior invocations, which is summarized in a value for current state. If so, then I don't see any "during action". There is only one "event" and it is always the call to the function. The only thing that changes are the values in the data packet. That "event" is dispatched to the appropriate "call to statechart" method for each state based on the value of current state and the data packet values. Then the value of DriveRequest is always set on entry to the current state using the rules and policies that prevail for that state. IOW, this seems to be an ordinary Moore FSM with only entry actions (i.e., the individual "call to statechart" method for each state). All you are doing is including the STT dispatch mechanism that would usually be in external supporting infrastructure (i.e., the event queue or static class-level lookup) in the function call. The state actions are the individual methods for "call to statechart". The body of those methods, including setting DriveRequest, is executed all at once on entry to the state. BTW, I would argue that this is not an FSM at all. It is simply a single synchronous service that uses a state variable to record history. That is, "current state" really represents a state variable for context that is computed from the prior context variable value and the current input values. The calls to ReverseAlarm are just ordinary conditional message generation based on the state variable values. IOW, new context value = F(last context value, isForward, isReverse, throttle). is a single deterministic computation. Because it depends upon the input alphabet values rather than just {event ID, current state}, it isn't a true FSM. I could easily implement your function as a single procedure without distinct "action" methods. [That's not a criticism, BTW. Using FSM-like reasoning and structure provides good discipline. I am just arguing that (a) it isn't a true FSM because current state is computed from the input alphabet and (b) it would be an ordinary Moore FSM even if it were.] ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
In article <TrUlh.1145$kB3.113@trnddc08>, H. S. Lahman says...
> Responding to Adsett... > > It wasn't until I got to the end that I realized most of this thread is > a tempest in a teapot and we have been talking past on another. You > might want to skip to the end an read my closing comments first.
Sigh I had a detailed reponse but it just got lost. Maybe we're better off :)
> In addition, I am suspicious that you are not developing in an OO > environment despite posting to comp.object (where I live).
If you check you'll see it's cross posted to c.a.e. Why the original poster crosposted this way I don't know but I've been using this discussion to try to learn from your perspective. I figure the sig I'm adding may be appropriate though.
> You lubrication vs. cooling example demonstrates that.
Um, it's not vs, They were separate examples.
> > The incoming signals can indicate forward, reverse, neutral or be > > invalid. The throttle can independantly be anywhere in its range. In a > > complete example it could also be out of range but I did want a simple > > example :) I also don't deal here with finite allowable tme to switch > > directions, deadman switches and anti-tiedown logic :) > > > > As a result of these the output could be forward, reverse, neutral or > > stop. > > My issue is: why can't the incoming signal be changeDirection rather > than an explicit Forward/Reverse couplet?
I suppose they could be but you would then still have to figure out which direction it had changed to. I suppose you could generate different events for each possibility but I think we've lost the advantage at that point.
> The only problem space rule > that seems likely to be relevant is that the motor needs to be in > Neutral when the direction is changed. The direction itself is just a > data element that the hardware interprets. The fact that it is stored > in a hardware register rather than a memory location doesn't prevent it > from being viewed as an object knowledge attribute that some other > object sets.
Agreed, in fact in some cases it's not a direct input.
> > Let me revise the example a bit to include asymmetry in the directions > > as would be typical. I'll also walk through a couple of iterations so > > you can get an idea of how the during actions work. > > > > State 1 - Stop Waiting for a proper direction signal. The throttle > > must be zero and both direction switches off before exiting this state. > > Only one transition allowed which is to neutral when the previous > > conditions are satisfied. > > On Entry Action -> DriveRequest = 0; > > > > State 2 - Neutral Waiting for direction. Multiple possible > > transistions > > On Entry Action -> DriveRequest = 0; > > Tr A - (Forward && Reverse) Back to Stop. State 1 > > Tr B - (Forward && !Reverse) To Forward. State 3 > > Tr C - (!Forward && Reverse) To Reverse. State 4 > > > > > > State 3 - Forward. Multiple possible transistions > > During Action -> DriveRequest = Throttle; > > Tr A - (Forward && Reverse) To Stop. State 1 > > Tr B - (!Forward && Reverse) To Reverse. State 4 > > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > > > State 4 - Reverse. Multiple possible transistions > > On Entry Action -> SetReverseAlarm(); > > During Action -> DriveRequest = -Throttle/2; > > On Exit Action -> ClearReverseAlarm(); > > Tr A - (Forward && Reverse) To Stop. State 1 > > Tr B - (Forward && !Reverse) To Forward. State 3 > > Tr C - (!Forward && !Reverse) To Neutral. State 2 > > > > > > Note 1: The reverse alarm setup is more naive than would actually be > > used (by a fair amount) but it keeps the example simpler. > > > > Note 2: I've modified the neutral state to more properly reflect the > > difference between it and the stop state. In a less naive example the > > neutral state would be a little more complex. > > > > The statechart is implemented as a function, each call check for valid > > transitions and performs them before returning. The values checked and > > returned will be in the argument list, I'll leave the details out. > > > > Now to walk through. The state machine is already initialized to be in > > state 1 > > > > Time=t0 > > Conditions - Forward and Reverse are false, throttle is 0, > > DriveRequest is 0 (from entering state 1 some time previously) > > call to statechart > > state changes to state 2 > > DriveRequest is set to 0 > > returns > > > > Time=t1 > > Conditions - Forward is false, Reverse is true, throttle is 0 > > call to statechart > > state changes to state 4 > > DriveRequest is set to 0 > > call to SetReverseAlarm() > > returns > > > > Time=t2 > > Conditions - Forward is false, Reverse is true, throttle is 500 > > call to statechart > > DriveRequest is set to -250 > > returns > > > > Time=t3 > > Conditions - Forward is false, Reverse is true, throttle is 490 > > call to statechart > > DriveRequest is set to -245 > > returns > > > > Time=t4 > > Conditions - Forward is true, Reverse is false, throttle is 310 > > call to statechart > > call to ClearReverseAlarm() > > state changes to state 3 > > DriveRequest is set to 310 > > returns > > > > etc... > > > > And of course this could be implemented in just about any language C, > > ASM, ST or even as a method in an OO language. > > OK. AFAICT, this a function takes arguments of {isForward, isReverse, > throttle} and uses them to set the value of DriveRequest and, > optionally, invoke two other functions for ReverseAlarm. To do that it > needs to understand the history of prior invocations, which is > summarized in a value for current state. > > If so, then I don't see any "during action". There is only one "event" > and it is always the call to the function. The only thing that changes > are the values in the data packet. That "event" is dispatched to the > appropriate "call to statechart" method for each state based on the > value of current state and the data packet values. Then the value of > DriveRequest is always set on entry to the current state using the rules > and policies that prevail for that state. IOW, this seems to be an > ordinary Moore FSM with only entry actions (i.e., the individual "call > to statechart" method for each state).
OK, seems an odd way to view it to me but I can see the equivalency.
> All you are doing is including the STT dispatch mechanism that would > usually be in external supporting infrastructure (i.e., the event queue > or static class-level lookup) in the function call. The state actions > are the individual methods for "call to statechart". The body of those > methods, including setting DriveRequest, is executed all at once on > entry to the state. > > BTW, I would argue that this is not an FSM at all. It is simply a > single synchronous service that uses a state variable to record history. > That is, "current state" really represents a state variable for > context that is computed from the prior context variable value and the > current input values. The calls to ReverseAlarm are just ordinary > conditional message generation based on the state variable values. IOW, > > new context value = F(last context value, isForward, isReverse, throttle). > > is a single deterministic computation. Because it depends upon the > input alphabet values rather than just {event ID, current state}, it > isn't a true FSM.
OK, although I suspect the denizens of c.a.e would recognize both as state machines. I could be wrong on that though the participants cover quite a broad spectrum.
> I could easily implement your function as a single procedure without > distinct "action" methods. [That's not a criticism, BTW. Using > FSM-like reasoning and structure provides good discipline. I am just > arguing that (a) it isn't a true FSM because current state is computed > from the input alphabet and (b) it would be an ordinary Moore FSM even > if it were.]
I've done it that way myself. I switched to an explicit state appraoch for the reasons you suggested. Also to make it easier to explain andverify the logic with people who are not familiar with progrmming languages. A visual statechart is a little more obvious, unfortuanately it's only a little. I have enjoyed this BTW, hopefully it's not been too much of an annoyance to you or anyone else. Robert -- From the Divided by a Common Language File (Edited to protect the guilty) ME - "I'd like to get Price and delivery for connector Part # XXXXX" Dist./Rep - "$X.XX Lead time 37 days" ME - "Anything we can do about lead time? 37 days seems a bit high." Dist./Rep - "that is the lead time given because our stock is live.... we currently have stock." -- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...

>>You lubrication vs. cooling example demonstrates that. > > > Um, it's not vs, They were separate examples.
?? You combined them for one state condition. I was using 'versus' to argue against that precisely because of the apples/oranges thing.
>>>The incoming signals can indicate forward, reverse, neutral or be >>>invalid. The throttle can independantly be anywhere in its range. In a >>>complete example it could also be out of range but I did want a simple >>>example :) I also don't deal here with finite allowable tme to switch >>>directions, deadman switches and anti-tiedown logic :) >>> >>>As a result of these the output could be forward, reverse, neutral or >>>stop. >> >>My issue is: why can't the incoming signal be changeDirection rather >>than an explicit Forward/Reverse couplet? > > > I suppose they could be but you would then still have to figure out > which direction it had changed to. I suppose you could generate > different events for each possibility but I think we've lost the > advantage at that point.
If one captures current direction in a state variable rather than in an FSM state, then all one has is a toggle that is triggered by a single event with no data packet. So I don't see a need for "different events". Thus in your example one could change the function arguments to {directionIsToggled, throttleSetting}. Then the function logic checks directionIsToggled and the currentDirection state variable's value to decide what to do. The result would be just as deterministic; only the IF conditions would change.
>>><snip FSM example> >> >>OK. AFAICT, this a function takes arguments of {isForward, isReverse, >>throttle} and uses them to set the value of DriveRequest and, >>optionally, invoke two other functions for ReverseAlarm. To do that it >>needs to understand the history of prior invocations, which is >>summarized in a value for current state. >> >>If so, then I don't see any "during action". There is only one "event" >>and it is always the call to the function. The only thing that changes >>are the values in the data packet. That "event" is dispatched to the >>appropriate "call to statechart" method for each state based on the >>value of current state and the data packet values. Then the value of >>DriveRequest is always set on entry to the current state using the rules >>and policies that prevail for that state. IOW, this seems to be an >>ordinary Moore FSM with only entry actions (i.e., the individual "call >>to statechart" method for each state). > > > OK, seems an odd way to view it to me but I can see the equivalency.
Hmmm. I thought I was just mapping what you provided, so let me expand on my analysis of the example... By your description (i.e., the statechart is implemented as a single function) the function call is the event message to the FSM from the external world. Since there is only one function call and it always has the same data packet, there is only one event that triggers all transitions. That's unusual for practical FSMs but not illegal; one only /needs/ different events if there are multiple unconditional transitions out of a state. (In your example multiple exiting transitions is handled by conditional events.) In your example, you identified a "call to statechart" whose body did different things depending on what the state was. I assumed those were the methods for individual state or transition actions since all the business rules seemed to be contained in them. Those methods mapped uniquely to states since you associated each one with a state number. In addition, there were no other methods doing anything (other than the transition dispatch in the function itself). Those methods seem to be the only FSM actions in the example AND they were explicitly associated with a particular state AND they were called after a transition had been selected but before the 'current state' was set. So they had to be executed while entering the state. Consequently the FSM has to be a simple Moore FSM. Since DriveRequest is set in the body of those actions rather than in some other method, I don't see any "during action". That is, Drive Request can only be set if an FSM event is consumed (i.e., the statechart function is called) AND it is only set after a <conditional> transition is selected to a specific state AND the action seems to be a Moore action. So I don't see any other interpretation. The only thing I see as unusual in the example is the way that way transitions were selected. It is done within the statechart function rather than in a spearate event queue or through a static class STT lookup table. IOW, you are combining the event queue and STT in the single function that initially consumes the event. In addition, the dispatch is based upon the value of 'current state' and the values of the input alphabet (event data packet). In a true FSM the input alphabet is irrelevant and the dispatch is based the value of 'current state' and the event ID. That is, conditional transitions are an overlay to a pure FSM that explicitly employs state variables, which don't exist for FSAs. FWIW, with regard to conditional transitions, I am a purist and don't regard them as true FSMs for two reasons. One is that they aren't necessary, as my model for Motor demonstrated. In three decades of mucking with FSMs I've never used one. (That is the main thing I meant when I said I would do the FSM "differently".) IOW, I see value in keeping the notation simple even if is occasionally causes the developer some slight inconvenience. <aside> Back in the '80s there was an OO guru who showed up at conferences with papers proposing enhancements to the OOA/D notations. Invariably these were special cases of existing notation mechanisms that were tied to specific problem semantics. His enhancements were elegant and they made the problem space intent quite clear. But the OOP would be implemented exactly the same way with or without his enhancements. That is, the existing, more generic notational elements were just as complete, precise, and unambiguous in specifying what the application had to do. To me he was missing the point of having an OOA/D notation. In the end one is specifying what the application needs to do, so correct specification is pretty much a given. OTOH, an OOA/D notation deals with a complex conceptual subject matter so correct OOA/D models aren't all that easy to construct. It is generally recognized that simplicity aids communication and has value in managing complexity. Thus one wants a notation that is simple and easy to understand _in order to get the specification right_ because one does not want to be distracted by the complexity the notation itself. So one doesn't want several different ways of specifying the same thing that can cause confusion. A classic example was COBOL. COBOL was universally vilified because it was verbose and yet until the RAD IDEs and infrastructures of the '90s the vast majority of the world's software was written in COBOL. That was despite the fact that languages like PL/I and C offered lots of elegant ways to solve the same basic problems. Why? Because it was simple. The language was verbose only because of the number of keystrokes needed to type in its constructs. But the constructs themselves were quite unambiguous and remarkably simple semantically compared to languages like C or PL/I. So COBOL allowed the big IT shops to employ acres of entry level developers while shops using tricky languages like PL/I and C had to hire experts and there are a lot more journeyman developers than experts. [Grace Hopper is still one of my heroes because she got it so close to right in the 2nd 3GL ever invented. Tough lady, too; she made Admiral in an era when Navy women were supposed to be secretaries and nurses!] </aside> The second reason has to do with the scope of data integrity. When a state action messes with state variables the scope is well defined as the method boundary. In the OO paradigm this is further augmented because methods are self-contained and messages rarely have data packets since methods are expected to access the data they need synchronously on an as-needed basis. Under those conditions the method boundary is a very convenient scope for managing data integrity, especially in concurrent environments (i.e., providing blocking semaphores, pausing threads, etc. is <relatively> easy because of the bounded scope). [It also helps that in stack-based hardware architectures one gets some scope management "for free".] However, when selecting the transition to a state depends on state variable values, one is in another ballpark because accessing those variables is outside the scope of the target state action. In effect one needs to manage two different scopes for data integrity while consuming an event and one of them is not conveniently bounded by the call stack. As a translationist I am especially sensitive to this because a full code generator needs to optimize around this sort of thing. If the scope of data integrity is not limited to the scope of a single method, it tends to significantly impede any optimization. I submit that the same complexity that impedes optimization is also a potential problem for future maintenance. [Commercial code generators tend to ignore the problem if they support conditional transitions in UML Statecharts. IOW, they assume the developer will make sure the tested state variable is correct in all circumstances where an event can be consumed. But that just puts the optimization problem in the developer's lap and adds the resolution of nonfunctional requirements to the developer's problems.]
> I have enjoyed this BTW, hopefully it's not been too much of an > annoyance to you or anyone else.
I'm retired now so I've got time on my hands. B-) In addition, after many moons in the business I find that I have an oversupply of opinions that I need to get rid of anyway, so I welcome the opportunity. ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH
In article <oQxmh.21185$c94.3340@trndny09>, H. S. Lahman says...
> Responding to Adsett... > > >>You lubrication vs. cooling example demonstrates that. > > > > > > Um, it's not vs, They were separate examples. > > ?? You combined them for one state condition. I was using 'versus' to > argue against that precisely because of the apples/oranges thing.
No, at least that was not the intent. I was presenting them as examples of behaviours that could be tightly coupled to a machines operating state.
> >>>The incoming signals can indicate forward, reverse, neutral or be > >>>invalid. The throttle can independantly be anywhere in its range. In a > >>>complete example it could also be out of range but I did want a simple > >>>example :) I also don't deal here with finite allowable tme to switch > >>>directions, deadman switches and anti-tiedown logic :) > >>> > >>>As a result of these the output could be forward, reverse, neutral or > >>>stop. > >> > >>My issue is: why can't the incoming signal be changeDirection rather > >>than an explicit Forward/Reverse couplet? > > > > > > I suppose they could be but you would then still have to figure out > > which direction it had changed to. I suppose you could generate > > different events for each possibility but I think we've lost the > > advantage at that point. > > If one captures current direction in a state variable rather than in an > FSM state, then all one has is a toggle that is triggered by a single > event with no data packet. So I don't see a need for "different events".
Remember the incoming direction signal has four possible states. A simple toggle won't work since from any specific diection indication you could get any of the remaining three. So either you provide different events for all possibilities or you pass in the new direction signal information.
> Thus in your example one could change the function arguments to > {directionIsToggled, throttleSetting}.
You need more information.
> >>OK. AFAICT, this a function takes arguments of {isForward, isReverse, > >>throttle} and uses them to set the value of DriveRequest and, > >>optionally, invoke two other functions for ReverseAlarm. To do that it > >>needs to understand the history of prior invocations, which is > >>summarized in a value for current state. > >> > >>If so, then I don't see any "during action". There is only one "event" > >>and it is always the call to the function. The only thing that changes > >>are the values in the data packet. That "event" is dispatched to the > >>appropriate "call to statechart" method for each state based on the > >>value of current state and the data packet values. Then the value of > >>DriveRequest is always set on entry to the current state using the rules > >>and policies that prevail for that state. IOW, this seems to be an > >>ordinary Moore FSM with only entry actions (i.e., the individual "call > >>to statechart" method for each state). > > > > > > OK, seems an odd way to view it to me but I can see the equivalency. > > Hmmm. I thought I was just mapping what you provided, so let me expand > on my analysis of the example...
I'm not disagreeing it just seems an odd viewpoint.
> By your description (i.e., the statechart is implemented as a single > function) the function call is the event message to the FSM from the > external world. Since there is only one function call and it always has > the same data packet, there is only one event that triggers all > transitions. That's unusual for practical FSMs but not illegal; one > only /needs/ different events if there are multiple unconditional > transitions out of a state. (In your example multiple exiting > transitions is handled by conditional events.) > > In your example, you identified a "call to statechart" whose body did > different things depending on what the state was. I assumed those were > the methods for individual state or transition actions since all the > business rules seemed to be contained in them. Those methods mapped > uniquely to states since you associated each one with a state number. > In addition, there were no other methods doing anything (other than the > transition dispatch in the function itself). > > Those methods seem to be the only FSM actions in the example AND they > were explicitly associated with a particular state AND they were called > after a transition had been selected but before the 'current state' was > set. So they had to be executed while entering the state. Consequently > the FSM has to be a simple Moore FSM.
OK. The separation into On-entry/during/on-exit (and transition actions too) actions is still useful though. The code generator then picks up the appropriate combination for each transistion. That would otherwise have to be done by the designer. The computer is much better at consistently doing that than I am.
> Since DriveRequest is set in the body of those actions rather than in > some other method, I don't see any "during action". That is, Drive > Request can only be set if an FSM event is consumed (i.e., the > statechart function is called) AND it is only set after a <conditional> > transition is selected to a specific state AND the action seems to be a > Moore action. So I don't see any other interpretation. > > The only thing I see as unusual in the example is the way that way > transitions were selected. It is done within the statechart function > rather than in a spearate event queue or through a static class STT > lookup table.
STT?
> IOW, you are combining the event queue and STT in the > single function that initially consumes the event. > > In addition, the dispatch is based upon the value of 'current state' and > the values of the input alphabet (event data packet). In a true FSM the > input alphabet is irrelevant and the dispatch is based the value of > 'current state' and the event ID. That is, conditional transitions are > an overlay to a pure FSM that explicitly employs state variables, which > don't exist for FSAs.
I suppose you could convert all the conditional checks by running them externally and producing event ids for each one. Seems a lot of work just get get a abstract ID though. The other disadvantage I see with that is the actual condition is now several steps removed from the transition it causes.
> FWIW, with regard to conditional transitions, I am a purist and don't > regard them as true FSMs for two reasons. One is that they aren't > necessary, as my model for Motor demonstrated. In three decades of > mucking with FSMs I've never used one. (That is the main thing I meant > when I said I would do the FSM "differently".) IOW, I see value in > keeping the notation simple even if is occasionally causes the developer > some slight inconvenience.
So far I don't see the abstract IDs as any simpler than the conditional check. Actually I don't see that they are not fundamentally identical unless you have something running around changing values behind the state machines back which would be bad design practice IMO. Why is if( a < DFG ) { QueueEvent(queue, QW); } if( b == GHJZZ ) { QueueEvent(queue, QE); } StateChart( queue, out); superior to StateChart( a, b, out);
> However, when selecting the transition to a state depends on state > variable values, one is in another ballpark because accessing those > variables is outside the scope of the target state action. In effect > one needs to manage two different scopes for data integrity while > consuming an event and one of them is not conveniently bounded by the > call stack.
You've lost me completely. The data passed in is valid for the call. Sounds like it's bounded by the call stack to me.
> [Commercial code generators tend to ignore the problem if they support > conditional transitions in UML Statecharts. IOW, they assume the > developer will make sure the tested state variable is correct in all > circumstances where an event can be consumed. But that just puts the > optimization problem in the developer's lap and adds the resolution of > nonfunctional requirements to the developer's problems.]
If you are referring to the inputs then how is that any different from any other function or method call? Indeed unless you are passing in the values via reference how would the issue arise at all?
> > > I have enjoyed this BTW, hopefully it's not been too much of an > > annoyance to you or anyone else. > > I'm retired now so I've got time on my hands. B-) In addition, after > many moons in the business I find that I have an oversupply of opinions > that I need to get rid of anyway, so I welcome the opportunity.
In that case, glad to take up your excess time :) Robert -- Posted via a free Usenet account from http://www.teranews.com
Davy escribi&#2013265923;:
> Hi all, > > I found there are transition and reaction in FSM/HSM. I only know there > is state transition in FSM. What's reaction mean? And what's there > difference?
IIRC, reaction is the name given by Rhapsody's creators to internal transitions. An internal transition is one that causes an action without leaving a state.
> BTW, I am studing Statecharts (or called Hierarchical State Machine, > i.e. HSM). Is it useful in software/hardware design?
Yes.
Responding to Adsett...

>>>>You lubrication vs. cooling example demonstrates that. >>> >>> >>>Um, it's not vs, They were separate examples. >> >>?? You combined them for one state condition. I was using 'versus' to >>argue against that precisely because of the apples/oranges thing. > > > No, at least that was not the intent. I was presenting them as examples > of behaviours that could be tightly coupled to a machines operating > state.
The operative word is "a" [machine's operating state]. B-) In the context I was arguing that /because/ they were quite different things they should not be associated with the same state as entry and exit actions. In a software FSM a state represents a condition where a unique set of rules and policies prevails. A corollary is that the rules and policies in that set will be cohesive. I believe this is important because it can affect subsequent maintenance. Suppose we originally have | | E1:prepare V [Prepared] | | E2:start V [Running] where the [Prepared] state has an entry action to lubricate and an exit action to start cooling. Now consider what happens when requirements change such that cooling is triggered by a temperature sensor. Now cooling is triggered after the motor is running rather than before. So one might introduce a new state and transition: | | E1:prepare V [Prepared] | | E2:start V [Running] | | E3:cool V [Cooled] To do that surgery must be performed to the [Prepared] state implementation. Now suppose we recognized cooling as a distinct suite of rules and policies in the /original/ state machine: | | E1:prepare V [Prepared] | | E3:cool V [Cooled] | | E2:start V [Running] To convert to the new state machine for the new requirements, all we have to do is update the STT and, perhaps, change where the E3 event is generated. IOW, we can implement the change at the message flow of control level without touching the [Prepared] state implementation.
>>>>>The incoming signals can indicate forward, reverse, neutral or be >>>>>invalid. The throttle can independantly be anywhere in its range. In a >>>>>complete example it could also be out of range but I did want a simple >>>>>example :) I also don't deal here with finite allowable tme to switch >>>>>directions, deadman switches and anti-tiedown logic :) >>>>> >>>>>As a result of these the output could be forward, reverse, neutral or >>>>>stop. >>>> >>>>My issue is: why can't the incoming signal be changeDirection rather >>>>than an explicit Forward/Reverse couplet? >>> >>> >>>I suppose they could be but you would then still have to figure out >>>which direction it had changed to. I suppose you could generate >>>different events for each possibility but I think we've lost the >>>advantage at that point. >> >>If one captures current direction in a state variable rather than in an >>FSM state, then all one has is a toggle that is triggered by a single >>event with no data packet. So I don't see a need for "different events". > > > Remember the incoming direction signal has four possible states. A > simple toggle won't work since from any specific diection indication you > could get any of the remaining three. So either you provide different > events for all possibilities or you pass in the new direction signal > information.
I didn't want to go here, but this was one of the things I was referring to when I said I would do things differently; but it has nothing to do with FSMs per se. In your example the Forward and Reverse data are serving double duty. Certain combinations (both ON or both OFF) have additional semantics unrelated to direction. That is very similar to return values being "normal" data when positive and error codes when negative. Such semantic double duty can lead to problems during maintenance (e.g., when requirements change and make some negative values "normal" data or when your criteria for stopping changes). IOW, separation of concerns applies to data domains are well as behaviors. I also have a problem with using them to trigger a transition to the [Stop] state, which you said was an error state. Since they are input alphabet values (i.e., part of the event data packet), what is being checked is that consistent data is being provided. If one is using DbC for design, that should be a responsibility of whoever generates the event. Thus it is a precondition of consuming the event that the data in the data packet be consistent. IOW, when using DbC any assertions made about the input data are checking the correctness of the software, not the consistency of the data. When the software becomes broken, that's a job for exception handling. One might still need a [Stop] state for recovery, but getting there is a job for the exception handler rather than FSM design. (Typically the exception handler is going to have to do other things, like flushing the event queue, that the FSM itself should not be concerned with.) However, this is getting pretty far OT.
>>>>OK. AFAICT, this a function takes arguments of {isForward, isReverse, >>>>throttle} and uses them to set the value of DriveRequest and, >>>>optionally, invoke two other functions for ReverseAlarm. To do that it >>>>needs to understand the history of prior invocations, which is >>>>summarized in a value for current state. >>>> >>>>If so, then I don't see any "during action". There is only one "event" >>>>and it is always the call to the function. The only thing that changes >>>>are the values in the data packet. That "event" is dispatched to the >>>>appropriate "call to statechart" method for each state based on the >>>>value of current state and the data packet values. Then the value of >>>>DriveRequest is always set on entry to the current state using the rules >>>>and policies that prevail for that state. IOW, this seems to be an >>>>ordinary Moore FSM with only entry actions (i.e., the individual "call >>>>to statechart" method for each state). >>> >>> >>>OK, seems an odd way to view it to me but I can see the equivalency. >> >>Hmmm. I thought I was just mapping what you provided, so let me expand >>on my analysis of the example... > > > I'm not disagreeing it just seems an odd viewpoint.
I guess it depends on where the observer is standing...
>>By your description (i.e., the statechart is implemented as a single >>function) the function call is the event message to the FSM from the >>external world. Since there is only one function call and it always has >>the same data packet, there is only one event that triggers all >>transitions. That's unusual for practical FSMs but not illegal; one >>only /needs/ different events if there are multiple unconditional >>transitions out of a state. (In your example multiple exiting >>transitions is handled by conditional events.) >> >>In your example, you identified a "call to statechart" whose body did >>different things depending on what the state was. I assumed those were >>the methods for individual state or transition actions since all the >>business rules seemed to be contained in them. Those methods mapped >>uniquely to states since you associated each one with a state number. >>In addition, there were no other methods doing anything (other than the >>transition dispatch in the function itself). >> >>Those methods seem to be the only FSM actions in the example AND they >>were explicitly associated with a particular state AND they were called >>after a transition had been selected but before the 'current state' was >>set. So they had to be executed while entering the state. Consequently >>the FSM has to be a simple Moore FSM. > > > OK. The separation into On-entry/during/on-exit (and transition actions > too) actions is still useful though. The code generator then picks up > the appropriate combination for each transistion. That would otherwise > have to be done by the designer. The computer is much better at > consistently doing that than I am.
My point here is that in your example I don't see any separation at all. That is, I don't see a "during action". All I see is a simple Moore FSM. The value of DriveRequest is always set in that <entry> action as a direct result of consuming the event that triggered going to the state.
>>Since DriveRequest is set in the body of those actions rather than in >>some other method, I don't see any "during action". That is, Drive >>Request can only be set if an FSM event is consumed (i.e., the >>statechart function is called) AND it is only set after a <conditional> >>transition is selected to a specific state AND the action seems to be a >>Moore action. So I don't see any other interpretation. >> >>The only thing I see as unusual in the example is the way that way >>transitions were selected. It is done within the statechart function >>rather than in a spearate event queue or through a static class STT >>lookup table. > > > STT?
State Transition Table. There are two forms. In one the table cells are the event ID and the rows/columns are [current state, new state]. That is the one commonly seen in theoretical discussions. In the other the cells are new state and the rows/columns are [current state, event ID]. In practice the second form is used in software FSMs but the cells are pointer-to-function for the specific state action. Then the event queue can dispatch directly to the action when an event is popped. No offense intended, but how often have you used FSMs? This is a very basic acronym for FSMs and almost all FSMs are implemented using one for efficiency. I was already suspicious that you don't use a lot because you used the "statechart function" to implement the event with embedded processing for the conditional event dispatch. I had never seen anyone do that before. B-) BTW, the two most common ways for implementing software FSMs are the GoF State pattern (where the STT is used to dynamically instantiate the relationship between Context and State) and utilizing a reusable event queue infrastructure. [All commercial full code generators employ the event queue infrastructure. Personally I regard the GoF State pattern for FSMs as a misuse of the pattern, but let's not go there.]
>>IOW, you are combining the event queue and STT in the >>single function that initially consumes the event. >> >>In addition, the dispatch is based upon the value of 'current state' and >>the values of the input alphabet (event data packet). In a true FSM the >>input alphabet is irrelevant and the dispatch is based the value of >>'current state' and the event ID. That is, conditional transitions are >>an overlay to a pure FSM that explicitly employs state variables, which >>don't exist for FSAs. > > > I suppose you could convert all the conditional checks by running them > externally and producing event ids for each one. Seems a lot of work > just get get a abstract ID though. The other disadvantage I see with > that is the actual condition is now several steps removed from the > transition it causes.
Not necessarily. Recall my model for Motor. It was actually somewhat simpler than your model. Its actions could do everything you said were done in your FSM actions and its transitions enforced the same sequencing rules that yours did. It just did it with different conditions (states), events, and state variables. I think the condition is only one step removed. The DbC precondition for executing any state action exactly matches the postcondition of some other action (i.e., the one where the event is generated to announce that its postcondition prevails). Having the condition decoupled from the action is actually an advantage for maintenance. (One can argue that the entire OO paradigm is designed around the separation of message and method to eliminate the hierarchical dependencies associated with procedural imperatives.) So long as the state actions are cohesive and self-contained, one can easily connect the flow of control dots via DbC using event generation.
>>FWIW, with regard to conditional transitions, I am a purist and don't >>regard them as true FSMs for two reasons. One is that they aren't >>necessary, as my model for Motor demonstrated. In three decades of >>mucking with FSMs I've never used one. (That is the main thing I meant >>when I said I would do the FSM "differently".) IOW, I see value in >>keeping the notation simple even if is occasionally causes the developer >>some slight inconvenience. > > > So far I don't see the abstract IDs as any simpler than the conditional > check. Actually I don't see that they are not fundamentally identical > unless you have something running around changing values behind the > state machines back which would be bad design practice IMO. > > Why is > if( a < DFG ) { > QueueEvent(queue, QW); > } > if( b == GHJZZ ) { > QueueEvent(queue, QE); > } > StateChart( queue, out); > > superior to > StateChart( a, b, out);
There are several reasons. From an aesthetic perspective the FSM provides /invariant/ constraints on /relative/ sequencing. They should be invariant relative to the external context. However, 'a' and 'b' are external context variables. If one moves the conditional dispatch into the FSM, one is making the FSM context-dependent and increases the probability of maintenance problems. There are two ways the FSM can utilize context variables. The FSM actions can access them parametrically for a computation within a state action. That usage is well constrained with respect to scope. The other thing they can affect is the sequencing of actions within the FSM. That is essentially what conditional events do; they use context variables to change the structure of the FSM on the fly. To me that is kind of like an assigned GOTO in FORTRAN; it opens all sorts of opportunities for unexpected side affects. IOW when one changes the data semantics of the state variables one not only needs to worry about what one computes from the data but which formula one uses to do the computation. That is an issue of separation of concerns. The FSM structure is inherently static. Modifying transitions dynamically adds another dimension of complexity to the FSM structure and that is probably not a good idea. One way that is manifested is in the notion of OO announcement messages (I'm Done) compared to procedural imperative messages (Do This). The event being generated announces a change in condition /outside/ the FSM. That is, the event itself is announcing something happening externally. As it happens that depends upon 'a' and 'b'. But it announces a compound condition that also includes whatever the caller did. IOW, the condition being announced is {(a < DFG), caller completed its part of the solution} OR {(b == GHJZZ), caller completed its part of the solution}. More importantly, it includes a context decision that the IF statements themselves define. Those IF statements implement problem space rules and policies to determine exactly What should be announced. The FSM only responds to the announcement. If one moves the IF statements into the FSM itself, one is moving that external context decision into the FSM. That external context decision probably isn't any of the FSM's business; it should just respond to the decision's /result/. Finally, when managing complexity it is wise to isolate related rules and policies via encapsulation. It is highly unlikely that the rules and policies that determine what event to generate will be logically related to the rules and policies that the FSM exists to resolve. So if one moves those rules and policies into the FSM, one is trashing the cohesion of the FSM. The bottom line is that the software will be more maintainable if one decouples message and method, separates concerns, and encapsulates rules and policies in a cohesive fashion. Superficially both your examples do the same thing. But devil is in the details and from the perspective of maintainability there are potentially huge differences when one gets to the details.
>>However, when selecting the transition to a state depends on state >>variable values, one is in another ballpark because accessing those >>variables is outside the scope of the target state action. In effect >>one needs to manage two different scopes for data integrity while >>consuming an event and one of them is not conveniently bounded by the >>call stack. > > > You've lost me completely. The data passed in is valid for the call. > Sounds like it's bounded by the call stack to me.
Sorry, I was thinking about the more common situation where conditional transitions are based upon the values of persistent state variables rather than values in the event data packet. [I am biased because in OO applications one rarely sees data in event data packets. Data integrity is easier to manage if the method accesses attribute data directly on an as-needed basis since there is potentially an arbitrary delay between when an event is generated and when it is consumed in the asynchronous execution model. So pretty much the only time one sees data packets is for situations like sensor readings where all the values need to be taken from the same time slice.] ************* There is nothing wrong with me that could not be cured by a capful of Drano. H. S. Lahman hsl@pathfindermda.com Pathfinder Solutions http://www.pathfindermda.com blog: http://pathfinderpeople.blogs.com/hslahman "Model-Based Translation: The Next Step in Agile Development". Email info@pathfindermda.com for your copy. Pathfinder is hiring: http://www.pathfindermda.com/about_us/careers_pos3.php. (888)OOA-PATH