Forums

Transition and reaction difference in FSM?

Started by Davy December 24, 2006
Responding to Adsett...

>>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. > > > 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.
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 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
H. S. Lahman wrote:
> Responding to Adsett... > > >>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. > > > > > > 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. > > 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 > 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
<snip> 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: 1. Harel model is elegent in visual but hard to design and debug in real system design. 2. When design a complex system, we can do following things 2.1 seperate/delegate big system into smaller ones FSM 2.2 Use other communication machanism between these independent FSM(Like UML Interaction Diagram), but not Harel Hierarchy events and Broadcast. 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 layer<->sub-state layer<->sub-sub-state layer<->...). And your model is network-like that without a kernel control unit (one indivisual FSM <=> another indivisual FSM <=> ...)? Best regards, Davy
In article <ZUckh.3386$Lc5.1656@trndny04>, H. S. Lahman says...
> 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.
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.
> 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.
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...

> Can I conclude from your post: > 1. Harel model is elegent in visual but hard to design and debug in > real system design.
Yes.
> 2. When design a complex system, we can do following things > 2.1 seperate/delegate big system into smaller ones FSM > 2.2 Use other communication machanism between these independent > FSM(Like UML Interaction Diagram), but not Harel Hierarchy events and > Broadcast.
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.
> In your design pattern, all the super-states and sub-states in one > individual FSM are at the same flat layer?
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.
> So I think Harel model is tree-like (super-state layer<->sub-state > layer<->sub-sub-state layer<->...). And your model is network-like that > without a kernel control unit (one indivisual FSM <=> another > indivisual FSM <=> ...)?
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 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
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. > > > 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.
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.
>>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. > > > 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.
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] <---------+ | | | | V | [Yellow] | | | | | V | [Red] ----------+ Whatever action is associated with [Yellow] can only occur <relatively> immediately after the action associated with [Green]. It would be illegal for the [Yellow] action to be executed immediately after the [Red] action in the problem space. Thus the transitions enforce those problem space sequencing constraints, in this case essentially defining a cyclic iteration. 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. <Hot Button> It always annoys the hell out of me when people dismiss the use of object FSMs as an R-T/E thing that isn't applicable to IT. The specific problem domain /always/ defines at least some invariant sequencing rules among an object's behaviors when there are multiple behaviors. FSMs are an ideal way to express those sequencing rules. More important, it allows managing complexity at two different levels: the sequencing among an object's intrinsic behaviors in the problem context and managing flow of control in the overall solution. [In fact, there is a rigorous DbC technique (albeit tedious) that can ensure correct overall flow of control once the local object sequencing rules have been captured in an FSM.] That's because the rules for FSAs map exactly into the OO paradigm's mandates for encapsulation, decoupling, implementation hiding, separation of message and method, and peer-to-peer communication. IOW, the use of object FSMs is the natural way to to OO development in any application context. Capturing such sequencing constraints in static FSM structure is important to any sort of software development because it reduces the amount of executable code one needs for dynamics (i.e., the code one would have to write in other objects to enforce those rules if one didn't use object FSMs). And reducing the amount of executable code reduces the opportunities for inserting defects. </Hot Button> ************* 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 <E7wkh.2096$oo4.1973@trndny09>, H. S. Lahman says...
> 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.
OK, I've used both. Even hybrids, it depends on the application characteristics.
> 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] <---------+ > | | > | | > V | > [Yellow] | > | | > | | > V | > [Red] ----------+ > > Whatever action is associated with [Yellow] can only occur <relatively> > immediately after the action associated with [Green]. It would be > illegal for the [Yellow] action to be executed immediately after the > [Red] action in the problem space. Thus the transitions enforce those > problem space sequencing constraints, in this case essentially defining > a cyclic iteration.
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.
> > 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. Robert -- Posted via a free Usenet account from http://www.teranews.com
Responding to Adsett...

>>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] <---------+ >> | | >> | | >> V | >>[Yellow] | >> | | >> | | >> V | >> [Red] ----------+ >> >>Whatever action is associated with [Yellow] can only occur <relatively> >>immediately after the action associated with [Green]. It would be >>illegal for the [Yellow] action to be executed immediately after the >>[Red] action in the problem space. Thus the transitions enforce those >>problem space sequencing constraints, in this case essentially defining >>a cyclic iteration. > > > 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.
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.
>>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". 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 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
Robert Adsett wrote:
> 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.
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
In article <x7Skh.3029$oo4.1545@trndny09>, H. S. Lahman says...
> Responding to Adsett... > > >>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] <---------+ > >> | | > >> | | > >> V | > >>[Yellow] | > >> | | > >> | | > >> V | > >> [Red] ----------+ > >> > >>Whatever action is associated with [Yellow] can only occur <relatively> > >>immediately after the action associated with [Green]. It would be > >>illegal for the [Yellow] action to be executed immediately after the > >>[Red] action in the problem space. Thus the transitions enforce those > >>problem space sequencing constraints, in this case essentially defining > >>a cyclic iteration. > > > > > > 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. > > At the risk of being picky, the sequencing constraints in the problem > domain are what drives defining which transitions are valid.
OK, the sequencing constraints are the transitions but in the problem definition rather than the SW implementation?
> 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?
> >>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. 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.
> > 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.
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.
> 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.
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...

>>>> >>>>[Green] <---------+ >>>> | | >>>> | | >>>> V | >>>>[Yellow] | >>>> | | >>>> | | >>>> V | >>>> [Red] ----------+ >>>> >>>>Whatever action is associated with [Yellow] can only occur <relatively> >>>>immediately after the action associated with [Green]. It would be >>>>illegal for the [Yellow] action to be executed immediately after the >>>>[Red] action in the problem space. Thus the transitions enforce those >>>>problem space sequencing constraints, in this case essentially defining >>>>a cyclic iteration. >>> >>> >>>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. >> >>At the risk of being picky, the sequencing constraints in the problem >>domain are what drives defining which transitions are valid. > > > OK, the sequencing constraints are the transitions but in the problem > definition rather than the SW implementation?
Yes.
>>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. Events are just messages that announce some change in the state of the overall problem solution. <aside1> 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 <direct> 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. </aside1> <aside2> 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. </aside2>
>>>>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. 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.
>>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. > > > 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.
Exactly. And that constraint was in the problem space or one would would have included the reflexive transitions in the previous example.
>>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. > > > Since E2 appears to map to 'please close' how could it be otherwise?
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 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