Quantcast

[statechart ] UML2.0 local transitions and history

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[statechart ] UML2.0 local transitions and history

Tim Milward
I've built a small test program with the statechart library. (See below)

It seems that the sequence of exit and entry actions invoked for a
transition are modeled according to the UML 1.5 specification. In other
words it models "external" transitions from the 2.0 spec. Is it
possible, or are there any plans to extend it, to model the more useful
local transitions from the 2.0 spec?

Tests with deep history produce a static assertion if you attempt to
transition to history of a containing state. UML 2.0 explicitly permits
this. Are there any plans to modify the library to permit this?

Yours,
Tim Milward

#include <iostream>

#include <boost/statechart/event.hpp>
#include <boost/statechart/state_machine.hpp>
#include <boost/statechart/simple_state.hpp>
#include <boost/statechart/transition.hpp>
#include <boost/statechart/deep_history.hpp>

using namespace std;
namespace sc = boost::statechart;

struct S0;
struct S00;

struct Machine : sc::state_machine< Machine, S0 >
{
        Machine() { cout << "Machine()\n"; }
        ~Machine() { cout << "~Machine()\n"; }
};

struct E0 : sc::event< E0 >
{
        E0() { cout << "E0()\n"; }
        ~E0() { cout << "~E0()\n"; }
};
struct E1 : sc::event< E1 >
{
        E1() { cout << "E1()\n"; }
        ~E1() { cout << "~E1()\n"; }
};

struct S0 : sc::simple_state< S0, Machine, S00, sc::has_deep_history >
{
        // this would comile fine
// typedef sc::transition<E0, sc::deep_history< S00 > > reactions; //
this invokes exit actions of S00 and S0 (an external transition)
        typedef sc::transition<E0, S00 > reactions;
       
        S0() { cout << "S0()\n"; }
        virtual ~S0() { cout << "~S0()\n"; }
};
struct S00 : sc::simple_state< S00, S0 >
{
        // this doesn't compile
// typedef sc::transition<E1, sc::deep_history< S00 > > reactions;
        // this invokes exit actions of S00 only
        typedef sc::transition<E1, S00 > reactions;
       
        S00() { cout << "S00()\n"; }
        virtual ~S00() { cout << "~S00()\n"; }
};

int main()
{
        Machine m;
        m.initiate();
        m.process_event(E0());
        m.process_event(E1());
        return 1;
}

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Andreas Huber-2
Hi Tim

> It seems that the sequence of exit and entry actions invoked for a
> transition are modeled according to the UML 1.5 specification.

Right.

> In
> other words it models "external" transitions from the 2.0 spec. Is it
> possible,

It's certainly possible ...

> or are there any plans to extend it, to model the more
> useful local transitions from the 2.0 spec?

There weren't any plans until I read your post :-). It seems that any
local transition can always be converted to an external transition or an
in-state reaction. The only benefit I see is improved performance (one
state exit & entry less) under IME rare circumstances. So, the question
is: How often do you use such transitions?

> Tests with deep history produce a static assertion if you attempt to
> transition to history of a containing state. UML 2.0 explicitly
> permits this.

I disallowed such transitions because they don't seem to make sense and
there was no indication that they are allowed under UML 1.5. IIUC, such
a transition would simply leave & reenter the current state, right? If
so, what good is history for when the same effect can be achieved by
simply giving the state a normal transition to itself?

> Are there any plans to modify the library to permit
> this?

If there are compelling use cases I'd certainly add both features ASAP.

Thanks for the feedback!

Regards,

--
Andreas Huber

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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Tim Milward
>>or are there any plans to extend it, to model the more
>>useful local transitions from the 2.0 spec?
>
>
> There weren't any plans until I read your post :-). It seems that any
> local transition can always be converted to an external transition or an
> in-state reaction. The only benefit I see is improved performance (one
> state exit & entry less) under IME rare circumstances. So, the question
> is: How often do you use such transitions?

Unfortunately I have no practical experience of using state charts yet,
(I have done a lot of research/reading/designing), so can't answer your
question. I want to use simple HSMs to control the threads in a GUI
application (a more complex version of the Dining Philosophers Problem
essentially).

In my designs I very often use a composite state as the source for a
transition, simply to avoid repetition (- avoid lots of transition lines
  from each sub-state on my diagrams). However the behavior I want is
exactly the same as if I'd sourced the transition explicitly from each
sub state. That is, I explicitly don't want the entry and exit actions
of the composite to be called. That is perhaps why UML added local
transitions - not for performance reasons, but for behavioral
flexibility and expressivity. If you only model external transitions and
want to use entry/exit actions you've essentially lost much the power of
HSM's to represent FSM's more efficiently. This is I think a killer
argument.

>
>>Tests with deep history produce a static assertion if you attempt to
>>transition to history of a containing state. UML 2.0 explicitly
>>permits this.
>
>
> I disallowed such transitions because they don't seem to make sense and
> there was no indication that they are allowed under UML 1.5. IIUC, such
> a transition would simply leave & reenter the current state, right? If
> so, what good is history for when the same effect can be achieved by
> simply giving the state a normal transition to itself?

Giving a state a normal transition to itself would invoke it's
entry/exit actions, or if modeled as an internal transition (in-state
reaction) do none. Transitioning to deep history (of a containing state)
should (in my opinion) invoke the entry/exit actions all the way back up
to (but not including) the state containing the history. So as you can
see I was interested in notationally efficient ways to invoke chains of
entry/exit actions back up the hierarchy. The other thing to note is
that this sort of transition to history technically doesn't require any
extra storage of the deep history since it is just the current state
(the composite state might not need to be parameterised with
has_deep_history).

> Thanks for the feedback!

Hope that all makes sense. If I do use HSMs for my app, I think I'll use
boost/statechart, and for now avoid entry/exit actions. Having reviewed
several implementations, every time I think about writing my own HS
library I realise how many options there are. Also you've already done
all the queuing and locking for me.

Yours,
Tim Milward

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Andreas Huber-2
Tim Milward wrote:
[snip]

> Unfortunately I have no practical experience of using state charts
> yet, (I have done a lot of research/reading/designing), so can't
> answer your question. I want to use simple HSMs to control the
> threads in a GUI application (a more complex version of the Dining
> Philosophers Problem essentially).
>
> In my designs I very often use a composite state as the source for a
> transition, simply to avoid repetition (- avoid lots of transition
>  lines from each sub-state on my diagrams). However the behavior I
> want is exactly the same as if I'd sourced the transition explicitly
> from each sub state.

Right.

> That is, I explicitly don't want the entry and
> exit actions of the composite to be called.

After doing some digging in the UML specs, it seems that a transition
can only be local when the destination state is a direct or indirect
inner (nested) state of the origin state. I see that this can be useful
sometimes but I still think that such transitions are relatively rare.

> That is perhaps why UML
> added local transitions - not for performance reasons, but for
> behavioral flexibility and expressivity.

Ok so far, local transitions can simplify a statechart under certain
circumstances...

> If you only model external
> transitions and want to use entry/exit actions you've essentially
> lost much the power of HSM's to represent FSM's more efficiently.

I don't follow. As I mentioned before, you can always simulate an
internal transition with an external one. The only thing you have to do
is to add one state:

<code>
#include <boost/statechart/event.hpp>
#include <boost/statechart/state_machine.hpp>
#include <boost/statechart/simple_state.hpp>
#include <boost/statechart/transition.hpp>

namespace sc = boost::statechart;

struct E0 : sc::event< E0 > {};

struct S0;
struct Machine : sc::state_machine< Machine, S0 > {};

struct Intermediate;
struct S0 : sc::simple_state< S0, Machine, Intermediate >
{
  // Ctor & dtor as needed
};

  struct S00;
  struct Intermediate : sc::simple_state< Intermediate, S0, S00 >
  {
    // No ctor & dtor!
    typedef sc::transition< E0, S00 > reactions; // *** here ***
  };

    struct S00 : sc::simple_state< S00, Intermediate > {};

int main()
{
  Machine m;
  m.initiate();
  m.process_event(E0());
  return 0;
}
</code>

Now S0 has exactly one inner state, Intermediate, which in turn contains
all the states that were nested inside S0 before. If you want to add a
local transition to S0, you don't add it to S0::reactions typedef but to
the Intermediate::reactions typedef. If that reaction is triggered, any
currently active innermost state is exited, then Intermediate is exited
& entered and finally S00 is entered. S0 is never left, of course. The
only disadvantage I see with this pattern is that Intermediate is
destructed & constructed unnecessarily. Otherwise everything behaves as
if that transition was a local transition of S0.

>>> Tests with deep history produce a static assertion if you attempt to
>>> transition to history of a containing state. UML 2.0 explicitly
>>> permits this.
>>
>>
>> I disallowed such transitions because they don't seem to make sense
>> and there was no indication that they are allowed under UML 1.5.
>> IIUC, such a transition would simply leave & reenter the current
>> state, right? If so, what good is history for when the same effect
>> can be achieved by simply giving the state a normal transition to
>> itself?
>
> Giving a state a normal transition to itself would invoke it's
> entry/exit actions, or if modeled as an internal transition (in-state
> reaction) do none. Transitioning to deep history (of a containing
> state) should (in my opinion) invoke the entry/exit actions all the
> way back up to (but not including) the state containing the history.

Ok, that makes sense. From your example I assumed that you meant to
transition back to S00. But you had the more general case in mind where
you transition to history of an *indirect* outer state. This would of
course exit not just the innermost state but also an arbitrary number of
its outer states (and reenter them automatically afterwards).

> So as you can see I was interested in notationally efficient ways to
> invoke chains of entry/exit actions back up the hierarchy. The other
> thing to note is that this sort of transition to history technically
> doesn't require any extra storage of the deep history since it is
> just the current state (the composite state might not need to be
> parameterised with has_deep_history).

Right, but due to the way history is currently implemented an extension
allowing such transitions would most probably still require
has_deep_history.

>> Thanks for the feedback!
>
> Hope that all makes sense.

It does:
1. The modification in the history case should be trivial and
non-breaking, I guess I should be able to come up with a beta before
next Sunday. Would you be willing to test it?
2. I'm unsure what's the best approach in the local transition case.
Modifying the current behavior is out of the question for reasons of
backwards-compatibility. One option is to introduce sc::local_transition
and sc::simple_state::transit_locally() but I'm not sure whether that
would be such a good idea as it adds yet another way of expressing
something that can easily be achieved with little additional work.

Whatever modifications there will be, none of them will make it into
1.34, as we're already in the feature-freeze state. However, I'll add a
FAQ item that explains how local transitions can be implemented with
external ones.

> If I do use HSMs for my app, I think I'll
> use boost/statechart, and for now avoid entry/exit actions.

I would advise you not to avoid entry/exit actions. I believe doing so
would clutter your state machines much more than using the local
transition workaround I outlined above. I would be interesting to hear
some real-world experience in this case.

HTH,

--
Andreas Huber

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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Tim Milward
>>If you only model external
>>transitions and want to use entry/exit actions you've essentially
>>lost much the power of HSM's to represent FSM's more efficiently.
>
>
> I don't follow. As I mentioned before, you can always simulate an
> internal transition with an external one. The only thing you have to do
> is to add one state:

OK, I didn't spot that previously. You are right that

S0
   entry/
   exit/
   E-local->S00/

   S00
     entry/
     exit/

is equivalent to

S0
   entry/
   exit/

   Intermediate
     E-external->S00

     S00
       entry/
       exit/

in terms of entry and exit actions (ie behavior).

However in a more complex example containing 3 levels of nesting you
can't apply the same trick.

S0
   entry&exit/
   E-local->S000

   S00
     entry&exit/

     S000
       entry&exit/

   S01
     entry&exit/

Adding an intermediate state containing S00 and S01 and moving E into
that but making it external is not equivalent. For example transitioning
  via E from S000 to S000 would call the entry & exit actions for S00.
Putting the intermediate state inside S00 doesn't work either because
you've lost the ability to transition from S01 to S000.

So I do think it's correct that local transitions are necessary to take
full advantage of HSM's to simplify FSM's in the presence of entry and
exit actions. However it remains to be seen how useful it is in practice.

> 1. The modification in the history case should be trivial and
> non-breaking, I guess I should be able to come up with a beta before
> next Sunday. Would you be willing to test it?

I would be glad to, but unfortunately I may be away around that time.
It's interesting that you have to treat shallow and deep history
separately, since the shallow history can (in theory) be automatically
determined from the deep history. [I'd like to see an nth level history
in UML. n=infinity is deep, n=1 is shallow, n<0 and you count levels up
from the bottom (for example).]

> 2. I'm unsure what's the best approach in the local transition case.
> Modifying the current behavior is out of the question for reasons of
> backwards-compatibility. One option is to introduce sc::local_transition
> and sc::simple_state::transit_locally() but I'm not sure whether that
> would be such a good idea as it adds yet another way of expressing
> something that can easily be achieved with little additional work.
>
> I would be interesting to hear
> some real-world experience in this case.

Something to think about then. I don't have a good enough understanding
of the library yet to comment on the best approach. When I come across
any real examples in my work that need local transitions I'll let you know.

Yours,
Tim Milward.

_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Andreas Huber-2
Tim Milward wrote:
> Adding an intermediate state containing S00 and S01 and moving E into
> that but making it external is not equivalent. For example
>  transitioning via E from S000 to S000 would call the entry & exit
> actions for S00. Putting the intermediate state inside S00 doesn't
> work either because you've lost the ability to transition from S01 to
> S000.

Ok, I misunderstood how local transitions work. An innermost state where
any of its direct *or* *indirect* outer states define local transitions
behaves as if all those local transitions originated at the state
itself. I guess we'll have to go the sc::local_transition /
sc::simple_state::transit_locally route then...

>> 1. The modification in the history case should be trivial and
>> non-breaking, I guess I should be able to come up with a beta before
>> next Sunday. Would you be willing to test it?
>
> I would be glad to, but unfortunately I may be away around that time.

I won't make it anyway, I just learned that I'll have to do some
overtime at work before I can leave for my holidays. After the holidays
there'll typically be another hot week so I won't have anything before
start of June. Sorry.

> It's interesting that you have to treat shallow and deep history
> separately, since the shallow history can (in theory) be automatically
> determined from the deep history.

I don't really have to, it's just the way it's currently implemented.
What you say occurred to me also but at that time (about 2.5 years ago)
would have meant major changes in the then existing history facility. I
believe it would be much easier now as the history implementation has
evolved quite a bit since then.

> [I'd like to see an nth level
> history
> in UML. n=infinity is deep, n=1 is shallow, n<0 and you count levels
> up from the bottom (for example).]

I'm not sure whether that's so useful in practice. IIRC, I could have
benefitted from such history just once, where I used shallow history
initial states that were nested over two levels. I guess I could've
implemented that with n=2 and saved some repetition... Who knows, if I
ever get around to do more refactoring I might support such history.

> Something to think about then. I don't have a good enough
> understanding
> of the library yet to comment on the best approach. When I come across
> any real examples in my work that need local transitions I'll let you
> know.

As stated above, I'm now convinced that support for local transitions
must be added to Boost.Statechart in some way but I'll have to think
some more what the best approach is...

Thanks & Regards,

--
Andreas Huber

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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Tim Milward
> Ok, I misunderstood how local transitions work. An innermost state where
> any of its direct *or* *indirect* outer states define local transitions
> behaves as if all those local transitions originated at the state
> itself. I guess we'll have to go the sc::local_transition /
> sc::simple_state::transit_locally route then...

It seems I'm the one who misunderstood. I've dug a little deeper and
your are right that the difference between local and external is just
one level of entry/exit actions. So your approach of adding an
intermediate state does work.

 From the UML specs it's hard to extract the exact definition of a local
transition.
http://www.johndeacon.net/UML/UML_Appendix/Generated/UML_Appendix_behavioral.asp 
discusses this subject and warns about the pitfalls of using composite
states to de-clutter a state machine.

[I think there is a more general concept here, the same as having an nth
level history, a transition could have a level specification, n=0 is
external, n=1 is local, and n=infinity is the way I misinterpreted local
transitions. I need some real practical examples ...]


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Andreas Huber-2
Hi Tim

> > Ok, I misunderstood how local transitions work. An innermost state where
> > any of its direct *or* *indirect* outer states define local transitions
> > behaves as if all those local transitions originated at the state
> > itself. I guess we'll have to go the sc::local_transition /
> > sc::simple_state::transit_locally route then...
>
> It seems I'm the one who misunderstood. I've dug a little deeper and
> your are right that the difference between local and external is just
> one level of entry/exit actions. So your approach of adding an
> intermediate state does work.
>
>  From the UML specs it's hard to extract the exact definition of a local
> transition.

I'm still unsure which interpretation is the correct one. The one you had in
the beginning would make more sense to me. It would be nice to hear a
clarification from some UML guru on this one.

Regards,

Andreas


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: [statechart ] UML2.0 local transitions and history

Andreas Huber-2
In reply to this post by Andreas Huber-2
Andreas Huber wrote:

>>> 1. The modification in the history case should be trivial and
>>> non-breaking, I guess I should be able to come up with a beta before
>>> next Sunday. Would you be willing to test it?
>>
>> I would be glad to, but unfortunately I may be away around that time.
>
> I won't make it anyway, I just learned that I'll have to do some
> overtime at work before I can leave for my holidays. After the
> holidays there'll typically be another hot week so I won't have
> anything before start of June. Sorry.

I've finally found the time to do this. The CVS HEAD version of
statechart should now support this kind of history. The only thing I had
to do was to remove the compile time check :-).

Feedback welcome.

Regards,

--
Andreas Huber

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


_______________________________________________
Boost-users mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/boost-users
Loading...