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
Not a terminology I'm familiar with. I'm more familiar with condition/action or event/action (and on entry/on exit/during actions).
Definitely.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
I agree with Robert Adsett, first there are useful, second the terminology you use is 'strange'.
Where do you found "there are transition and reaction in FSM/HSM" ? Perhaps a 'reaction' is a transition made in respons to an external stimulus (a 'true' event) ?
Best regards
Sorry. I am familiar with FSM, but not familiar with its terminology. We know that transition is state transition. And do you mean reaction is the output when state transition complete?
And I learned that there is "behavioral inheritance(i.e. same transition in all sub-state of one super-state) " in statecharts/HSM. Is it useful in practical system design?
Best regards, Davy
bruno_pages wrote:
Responding to Davy...
Like the others, I don't know what 'reaction' means in the context of finite state machines. (I have never heard that term used in FSM context and I've been using FSMs for decades.) Could you provide the context for where the term was used?
Actually, I think HSM means Harel State Machine; named after the inventor. (The dominant FSM models are: Mealy, Moore, and Harel.) While hierarchical structure of Harel FSMs is their most prominent feature, Harel FSMs also include history of past states or events.
Harel FSMs are useful for describing very complex behavior in asynchronous environments in a single model. So they are commonly used for describing things like requirements for network protocol standards. However, that model complexity makes them difficult to construct and maintain.
IME, one is better off with a simple Mealy FSM in procedural development or a Moore FSM in OO development. In fact, in an OO environment if one is tempted to use Harel for an object state machine it is almost always a sign that there was something wrong with problem space abstraction. IOW, in an OO environment one uses problem space abstraction to manage complexity by allocating complex behavior responsibilities across multiple peer objects using delegation. (AFAIK, the only OO methodology that advocates the use of Harel is ROOM.)
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
Hi Lahman,
I want to partition my large FSM to smaller ones. And I get some idea from the statecharts.
In Harel's paper the HSM have four feature
I think feature 1 and 2 is very useful when you try to partition large FSM. And I think feature 3 will cause complex implementation. So you think so?
You said: "In fact, in an OO environment if one
But if you want a Hierarchy FSM or partition the FSM into small FSM parts, how can you do that without the idea from statecharts?
BTW, about reaction, I find a Boost library about Statecharts which mention "reaction"
Best regards, Davy
H. S. Lahman wrote:
First, this is a lot easier to follow if you don't top-post.
Second, I believe what everyone has said so far is that they are not familiar with the term reaction in the context of state machines. Althoug I'm beginning to suspect it's a synonym for action.
Again a term I've not seen before, but if you mean defining a transition from a state such that that transition occurs regardless of the contained state then yes, it's a construct I use regularly. If you mean an on-entry, during or on-exit action that occurs in a state regardless of the contained state then again yes.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
I think you're right.
I'll disagree here a bit. You may be right for some models, I can see building a statechart that was impossible to maintain and update. Having said that though I've used the Harel Statecharts to very good effect to simplify from what the state model would have been with a flat representation. The result was IMO also more maintainable and understandable mostly since it represented the desired behaviour with fewer transistion and/or states. Without automatic code generation from the statechart diagram I'm not sure that would have been the case though.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
That makes reaction look like a synonym for action. Unfortuantely they never appear to actually define the term.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
Responding to Davy...
I agree that 1 and 2 are a good idea. But if one is going to create independent peer FSMs (e.g., object state machines in an OO development), then they should /be/ independent. In Harel they are not because the protocol for their interactions are built into the superstate responsibilities. For example, one must provide rules for the broadcast in 3. That makes one large and complex state machine rather than multiple simple, independent state machines that interact asynchronously.
BTW, without the hierarchy, one would usually design the peer FSMs somewhat differently than in the Harel perspective because the interaction protocols would likely be different. However, that just demonstrates that there is additional design structure needed in Harel to provide a single FSM.
FWIW, I am not a fan of 4 at all because it seems to violate one of the fundamental rules of finite state automata on which FSMs are based. When processing the input alphabet a state should be context-independent; it should not know what the last state was or what the next state will be. [Note that is very important in an OO context because responsibilities are supposed to be intrinsic and self-contained.]
I submit that one wants to decompose complex state machines into simpler ones, but one does not need a hierarchical structure to do that. Once the simpler, independent state machines are defined they can talk to each other by sending events. Occasionally the Harel model will be more elegant (i.e., fewer states and transitions in total) but one pays for that in getting it to work properly, testing it, and modifying it when requirements change.
[Caveat. There is a common use of superstates as a /notational/ artifact to reduce transition clutter in Statecharts: +-----------------------------------+ | Error ^ | | | | | +------------+ | E1 | | | State1 | | | | | | | +------------+ | | | ^ | | | E2 | E3 | | | | | | V | | | +------------+ | | | State2 |The reference still doesn't define what it means. However, from the usage I would guess that they are talking about a Mealy FSM model where actions are associated with transitions rather than states. In that case one when there are multiple transitions into a state, one could have different actions execute depending on which transition was actually triggered to get to the state.
Then "reaction" would simply be a synonym for the more common notion (at least in OO circles) of a response.
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
Responding to Adsett...
To me the real issue is separation of concerns. I think that methodologically the OO paradigm drives one to a situation where complexity is managed so that Harel is unnecessary before one ever gets to FSM design.
In any FSM the transitions represent static sequencing constraints among multiple behaviors. The problem with Harel is that those sequencing constraints are specified at two different levels of abstraction; the constraints among the states of the individual leaf FSMs and the constraints for the interactions with the superstate. In addition, because of the broadcast feature, one gets different /combinations/ of behaviors executed in response to a single external stimuli. Finally, history introduces a context dependency based on prior states or events.
IMO, all of these things conspire to make Harel models more difficult to get right, test, and maintain _as soon as one decides one needs Harel_. IOW, as soon as one thinks one needs Harel, one is already dealing with an FSM that is too complex and responsibilities need to be delegated elsewhere. Harel manages the complexity within a single FSM structure while I submit that the complexity should be managed by separating and isolating disparate concerns.
So if one breaks up the /responsibilities/ through delegation to different objects, each individual object state machine will tend to be easier to understand, test, and modify even if there are a few more states and transitions in total than in a single elegant Harel model. That's because each object state machine captures intrinsic behaviors and sequencing rules for a single problem space entity without regard to other entities in the problem space. (Corollary: the peer object FSMs will probably be designed somewhat differently than the leaf FSMs in a corresponding Harel model.)
One still needs to address the overall coordination of the individual peer FSMs, but that is handled at a quite different level of abstraction (e.g., a UML Interaction Diagram) where one can focus on communication rather than FSM structure. Thus one has effectively separated the concerns of large scale solution (communication) from the detailed concerns of object implementations (FSM structure).
Of course all this depends upon being disciplined in designing individual peer state machines. Outside the OO context this puts a lot of pressure on the developer because there are no convenient constructs and methodological approaches that enforce decoupling. I submit that within an OO environment, one seeks to manage complexity by limiting behaviors to /intrinsic/ object properties, making objects communicate on a peer-to-peer basis, forcing behavior responsibilities to be self-contained, and limiting the responsibilities of individual objects to make them cohesive. Once one has done all that it is possible to connect the solution flow of control dots at a much higher level of abstraction than individual object implementations.
IOW, the whole paradigm drives one towards simple peer object state machines and if one has two independent FSMs, they should be in different objects to achieve better cohesion and separate concerns within the overall solution. Thus when one has finished OO problem space abstraction at the Class Model level, the object behavior responsibilities should be few and simple enough so that one doesn't /need/ Harel. That's why I asserted that if one is tempted to use Harel, it is symptomatic of having screwed up before ever getting the FSM design.
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
Hi Lahman,
I partly agree with you.
AFAIK, David Harel (the inventor of statecharts, see his paper from '87, e.g. on citeseer) designed statecharts as a visual language to enable thinking (alone and in the team) about the behaviour of systems. This is what we can learn from.
Can I conclude from your post:
In your design pattern, all the super-states and sub-states in one individual FSM are at the same flat layer?
So I think Harel model is tree-like (super-state layersub-state layersub-sub-state layer...). And your model is network-like that without a kernel control unit (one indivisual FSM another indivisual FSM ...)?
Best regards, Davy
Even w/o bringing OO into the picture I think we agree. You refered in another post to the hierachacal method I use as a notoational convienience, which it surely is although an immensely useful one.
Although occaisionally momemtarily tempted by history states I've always found so far that when the problem is fully thought out the desire for history states disappears.
I'm not sure what you are referring to as constraints though.
I think we may be referring to differnt types of statecharts.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
Responding to Davy...
Yes.
It is not so much about decomposing FSMs into smaller ones; Harel does that. It is about separating behavior responsibilities /before/ one gets to the point of implementing them as FSMs.
Harel does not attempt to isolate small bundles of logically cohesive behaviors so that they can be resolved independently in different models. Instead Harel tries to resolve them all together in a single model.
Yes, at least in an OO context. All objects that abstract problem space entities are peers and are supposed to talk to one another on a peer-to-peer basis.
Yes. In general hierarchical dependencies are a no-no in OO development. One can argue that the main thing that the OO paradigm brings to the table is the elimination of the functional decomposition trees of Structured Programming that led to spaghetti code dependencies when higher level nodes were reused.
One still has a functional decomposition of sorts; objects are analogous to leaf nodes in a functional decomposition tree. One just doesn't implement any of the higher level tree nodes explicitly. Instead one employs abstraction and flexible logical indivisibility so that the objects can be arbitrarily complex (rather than limited of language operators in traditional functional decomposition). Thus the tree is "flattened" into a network. IOW, in the OO paradigm one uses the level of abstraction to define the granularity of the nodes in the network.
I submit that the level of abstraction for bundling behavior responsibilities as logically indivisible "leaf nodes" will always be lower than the level of abstraction where a single Harel model would be formed.
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
Responding to Adsett...
Just to be clear, though, that wasn't Harel. It was a purely notational artifact for representing an ordinary Mealy/Moore FSM to eliminate transition clutter.
OK, let me try to clarify what I meant. In an FSM there are behaviors (actions) associated with entering each state (Moore) or transitioning to each state (Mealy). Those behaviors can only be executed if a specific transition takes place from some other specific state.
An FSM would not be very useful if it were possible to transition combinatorially between any two states; that's a function library rather than a state machine. The fact that some transitions are invalid implies that certain behaviors cannot take place sequentially. So in a Traffic Light FSM one might have
[Green]
OK, I've used both. Even hybrids, it depends on the application characteristics.
OK, so the constraints are what restricts you to follow the transistions. As opposed to viewing the transistions as what allow you to change states.
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.
Robert
-- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...
At the risk of being picky, the sequencing constraints in the problem domain are what drives defining which transitions are valid.
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'm not sure what you mean by "during action".
I was actually thinking more about reflexive transitions:
+---+ | | E1 | V [Opened] | ^ E2 | | E1 | | V | [Closed] | ^ | | E2 +---+Now the [Opened] action can be executed multiple times in succession.
However, there is still an implicit sequencing constraint relative to the external conditions triggering the transitions since one cannot trigger successive executions of the [Opened] action with an E2 event. That mapping of the sequencing constraint to the external conditions is always present in an FSM. (That's what I meant about being a function library; if the problem space allows one to execute the actions in any order under any conditions, an FSM would be inappropriate.)
I agree, though, that one cannot design object FSMs in a complete vacuum. One needs to decide which states and transitions are consistent with the problem space and, more specifically, which are needed for the particular problem in hand. The tricky part is to extract the invariants of the sequencing constraints as /intrinsic/ constraints on the object behaviors when defining FSM transitions. Once one does that properly one can solve the asynchronous communication problem for the overall flow of control.
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
They use these terms where I work. Every transition edge has an action; a "reaction" just a transition that doesn't change state. It could always be done without a separate name for it. I don't know where this idea came from initially.
A transition that returns to the original state would execute both the on-exit and on-entry actions. If a system doesn't have on-exit or on-entry actions, then the reaction vs transition distinction idea wouldn't be necessary.
-- Darin Johnson
OK, the sequencing constraints are the transitions but in the problem definition rather than the SW implementation?
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?
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.
In addition the SW I use optionally supports explicit events rather than simple conditions but I haven't used that facility since what I do doesn't usually naturally map to that.
Yes, or more to the point the opened state can be entered multiple times in succession. In your previous example it could only be entered once.
Since E2 appears to map to 'please close' how could it be otherwise?
Robert
-- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...
Yes.
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 FSM that executes as the problem is solved.
Events are just messages that announce some change in the state of the overall problem solution.
There is a rigorous, albeit tedious, DbC approach to defining interactions between different state machines. One can define all the object FSMs independently (i.e., without any regard for other FSMs needed in the overall solution). One can then associate arbitrary and unique event IDs with each of the transitions.
To execute the action associated with a state some precondition must prevail in the overall solution. In an OO context that precondition is usually compound, consisting of both algorithmic sequencing constraints between object behaviors and ensuring correct values for state variables (object attributes) are available for the action's input alphabet.
That precondition will prevail only as a postcondition of some other FSM action executing. Therefore to determine where the event for a particular transition must be generated, one matches the action precondition to other action postconditions until there is an exact match. One then generates the event in the action where the postcondition is an exact match. One repeats this for all transitions and when one is done one has the overall flow of control that will Just Work. (Provided the object FSMs were defined around intrinsic, self-contained behavior responsibilities in good OOA/D fashion.)
[Of course life is not quite this simple. Because of the introduction of state variables in an OO context, one may need to decompose a compound precondition so that some of its elements (the ones depending on state variable values) become elements of the precondition of the action triggering the event. That will occur when the candidate event generator is the algorithmic predecessor but does not have the responsibility for setting the state variables. IOW, one may need to provide a chain of events for compound preconditions. So, in practice, one works in both directions to daisy-chain compound conditions.]Note that one does not define event generation in the actions when the FSMs are originally designed. All one needs to know is what the actions must do (i.e., the requirements the responsibility addresses). That determines how one abstracts the state conditions and the transitions. Then DbC handles the rest using the constraints implicit in the overall solution design.
Earlier I mentioned that Mealy FSMs are a better fit to procedural development while Moore FSMs are a better fit to OO development. The reason is related to your last sentence.
In a procedural environment communication is based on imperatives (Do This). So there is an expectation when sending a message about what will happen as a result. In the Mealy FSM model actions are associated with transitions rather than states. Thus one could have different actions execute when transitioning to a given state when there are multiple transitions to it. Since the events on each transition can announce different external contexts, it is a small step to associate the action with the external context. IOW, "in this context we should Do This".
[Note that 3GLs are so close to the hardware computational models that they all institutionalize this view through procedural message passing. IOW, message and method are inextricably married since the message is defined to be the method signature. So even the OOPLs are inherently procedural languages (though some, like Smalltalk, do a pretty good job of hiding it in the syntax). Thus one must rely on proper OOA/D to avoid any dependency pitfalls stemming from that marriage.]However, in an OOA/D context messages are separated from methods and they represent simple announcements of something the sender has done (I'm Done). There is no expectation in the message sender context of what the response will be, if any. It is up to the developer to connect the communication dots by directing the message to somebody who cares what was done and who may provide an appropriate response in the overall solution. In addition, object responsibilities are supposed to be intrinsic (i.e., independent of other objects' responsibilities or solution context). The most natural way for all that to work is for FSM actions to be associated with entering the state rather that with the transitions (i.e., the Moore FSM model). IOW, the Moore FSM model provides exactly the sort of decoupling of message and method that the OO paradigm demands.
BTW, this is another, more aesthetic reason why I don't like Harel in an OO context. Harel is necessarily based on a Mealy view to support history.
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.
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.]
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.
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-)
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.
Exactly. And that constraint was in the problem space or one would would have included the reflexive transitions in the previous example.
Right. My point was that something in the problem space is saying that one can't execute the [Opened] action if the current solution state is whatever the E2 event announces.
************* There is nothing wrong with me that could not be cured by a capful of Drano.H. S. Lahman snipped-for-privacy@pathfindermda.com Pathfinder Solutions
ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.