Transition and reaction difference in FSM?

[Davy]

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

 

[Robert Adsett]

In article <1167015961.917372.247050@f1g2000cwa.googlegroups.com>, Davy
says...

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?

Not a terminology I'm familiar with. I'm more familiar with
condition/action or event/action (and on entry/on exit/during actions).

BTW, I am studing Statecharts (or called Hierarchical State Machine,
i.e. HSM). Is it useful in software/hardware design?

Definitely.

Robert

--
Posted via a free Usenet account from http://www.teranews.com

 

[bruno_pages]

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

 

[Davy]

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:

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

 

[H. S. Lahman]

Responding to Davy...

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?

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?

BTW, I am studing Statecharts (or called Hierarchical State Machine,
i.e. HSM). Is it useful in software/hardware design?

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
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

 

[Davy]

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
1. Hierarchy: Simplify our thinking by partition large FSM into smaller
FSM parts
2. Orthogonality: the small FSM parts which are on the same layer and
from the same super-state should behave Orthogonality functionality (or
not similar functionality)
3. Broadcast: event from sub-state of one super-state trigger sub-state
of another super-state ???
4. History: re-enter the last state ???

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

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."

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"
http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html

Best regards,
Davy

H. S. Lahman wrote:

Responding to Davy...

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?

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?

BTW, I am studing Statecharts (or called Hierarchical State Machine,
i.e. HSM). Is it useful in software/hardware design?

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
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]

In article <1167045677.901397.146760@h40g2000cwb.googlegroups.com>, Davy
says...

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?

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.

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?

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

 

[Robert Adsett]

In article <CKSjh.7022$Rc5.6726@trnddc01>, H. S. Lahman says...

Responding to Davy...

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?
snip
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.

I think you're right.

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.

Robert

--
Posted via a free Usenet account from http://www.teranews.com

 

[Robert Adsett]

In article <1167096204.044434.222080@i12g2000cwa.googlegroups.com>, Davy
says...

BTW, about reaction, I find a Boost library about Statecharts which
mention "reaction"
http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html

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

 

[H. S. Lahman]

Responding to Davy...

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
1. Hierarchy: Simplify our thinking by partition large FSM into smaller
FSM parts
2. Orthogonality: the small FSM parts which are on the same layer and
from the same super-state should behave Orthogonality functionality (or
not similar functionality)
3. Broadcast: event from sub-state of one super-state trigger sub-state
of another super-state ???
4. History: re-enter the last state ???

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?

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.]

You said: "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."


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?

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 |<----- |
| | | E4 |
| +------------+ |
| |
+-----------------------------------+

In this case there can be a transition to the Error state from either
State1 or State2 and one always transitions from Error to State2.
However, this isn't a true Harel because all the events are external
(not internally broadcast) and all the states are actually peers. That
is, one could draw it as:

+-----------------+
| Error |-------+
| | |
+-----------------+ | E4
^ ^ |
| E1 | E1 |
| | V
+-----------+ +--------------+
| State1 | E2 | State2 |
| |--------->| |
| | | |
| |<---------| |
| | E3 | |
| | | |
+-----------+ +--------------+

IOW, the superstate is simply saving the clutter of multiple E1
transitions. (Which isn't important here but could be if there were a
half dozen states from which one transitions to Error.)

BTW, about reaction, I find a Boost library about Statecharts which
mention "reaction"
http://boost-sandbox.sourceforge.net/libs/statechart/doc/tutorial.html

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
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]

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

 

[Davy]

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

 

[Robert Adsett]

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

 

[H. S. Lahman]

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

 

[H. S. Lahman]

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

 

[Robert Adsett]

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

 

[H. S. Lahman]

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

 

[Darin Johnson]

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

 

[Robert Adsett]

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

 

[H. S. Lahman]

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