Re: preemption again (sigh...)

Given the arguments earlier about UML I think we should respect the second
paragraph.  This means we take transitions lower in the hierarchy over ones
higher in the hierarchy with document order being the tie breaker for
transitions on the same state.  We can do this with our filtering step as I
mentioned above.  Unless there is a solid, state reason to differ from UML
then, according to the quite strong efforts given earlier we shouldn't
differ.

The algorithm proceeds like ours does but I don't think it is 100% correct
or at least as stated requires parallel traversal of the atomic states or
at least of atomic states that are deepest.  Since you have to traverse the
active atomic states in some order you can't always simple 'start innermost
and work outward' without getting into a situation where you have to
through out a transition found via a previous atomic state but that exists
in a parent of the current atomic state.

So basically I am saying that the algorithm as stated is wrong or assumes
global knowledge about the graph that is expensive to maintain.  You can
always start at the 'deepest' atomic in the configuration and then proceed
in only once all children of a given state in the configuration have been
considered and this would make their algorithm work but it isn't the most
efficient way to do this I don't think nor is it the clearest.

One thing to note is that they appear to just consider the *source* of the
transition, not its arena (or the LCCA of the source and the targets) when
doing this preemption. I think this is debatable on the wrong side of the
debate.  So this appears wrong to me although I would like to still
implement it in spirit just taking the transition arena instead of the
transition source.

Chris


On Thu, Feb 28, 2013 at 4:32 PM, Jim Barnett <Jim.Barnett@genesyslab.com>wrote:

>  I also find the existing behavior intuitive – once you realize how this
> edge case works.   And you can form a simple mental model of preemption
> (pick a transition in the first state, now go to the second, pick one and
> keep it if it doesn’t conflict, etc.)   ****
>
> ** **
>
> Here is the UML 2 discussion of the issue.  The second paragraph does say
> that transitions in descendents take precedence over those in ancestors,
> but I can’t make much sense of the ‘greedy selection algorithm’ in the
> third paragraph.  In general, I think that we should be consistent with
> UML, but I don’t like trying to maintain consistency with something I can’t
> understand…****
>
> ** **
>
> **-          **Jim****
>
> ** **
>
> Two transitions are said to conflict if they both exit the same state, or,
> more precisely, that the intersection of the set of states they exit is
> non-empty. Only transitions that occur in mutually orthogonal regions may
> be fired simultaneously. This constraint guarantees that the new active
> state configuration resulting from executing the set of transitions is
> well-formed. An internal transition in a state conflicts only with
> transitions that cause an exit from that state. ****
>
> ** **
>
> *582 *UML Superstructure Specification, v2.3 *Firing priorities *In
> situations where there are conflicting transitions, the selection of which
> transitions will fire is based in part on an *implicit *priority. These
> priorities resolve some transition conflicts, but not all of them. The
> priorities of conflicting transitions are based on their relative position
> in the state hierarchy. By definition, a transition originating from a
> substate has higher priority than a conflicting transition originating from
> any of its containing states. The priority of a transition is defined based
> on its source state. The priority of joined transitions is based on the
> priority of the transition with the most transitively nested source state.
> In general, if t1 is a transition whose source state is s1, and t2 has
> source s2, then: • If s1 is a direct or transitively nested substate of s2,
> then t1 has higher priority than t2. • If s1 and s2 are not in the same
> state configuration, then there is no priority difference between t1 and
> t2. ****
>
> ** **
>
> *Transition selection algorithm *The set of transitions that will fire is
> a maximal set of transitions that satisfies the following conditions: • All
> transitions in the set are enabled. • There are no conflicting transitions
> within the set. • There is no transition outside the set that has higher
> priority than a transition in the set (that is, enabled transitions with
> highest priorities are in the set while conflicting transitions with lower
> priorities are left out). This can be easily implemented by a greedy
> selection algorithm, with a straightforward traversal of the active state
> configuration. States in the active state configuration are traversed
> starting with the innermost nested simple states and working outwards. For
> each state at a given level, all originating transitions are evaluated to
> determine if they are enabled. This traversal guarantees that the priority
> principle is not violated. The only non-trivial issue is resolving
> transition conflicts across orthogonal states on all levels. This is
> resolved by terminating the search in each orthogonal state once a
> transition inside any one of its components is fired. ****
>
> *From:* chris nuernberger [mailto:cnuernber@gmail.com]
> *Sent:* Thursday, February 28, 2013 5:42 PM
> *To:* Michael Bodell
> *Cc:* Jim Barnett; VBWG Public (www-voice@w3.org)
> *Subject:* Re: preemption again (sigh...)****
>
> ** **
>
> I doubt there is a way you could come up with something where all of the
> examples have completely intuitive results.  I agree with the analysis.***
> *
>
> ** **
>
> IF you always wanted transitions in children to have descendants over
> transitions in ancestors then that is fine but it is somewhat (or perhaps)
> a lot harder to implement than the current algorithm.  It also precludes
> short circuiting the transition selection algorithm, something that I can
> in favor of.****
>
> ** **
>
> Going back to the definition I gave a while time ago where you looked at
> preemption based on if a transition arena is the child of another arena you
> could have an efficient algorithm to allow exactly what UML suggests,
> allowing descendents to take precedence.  You would just always take the
> descendent of order of the transitions in the document.  The problem is
> that a later transition could preempt an earlier one and thus you would
> have to produce essentially a new transition list on every transition
> instead of just appending to the transition list.****
>
> ** **
>
> In any case, this could be a potentially large discrepancy from the UML
> specification.  Which would only manifest itself in subtle edge cases.
>  Seems troubling.****
>
> ** **
>
> Chris****
>
> ** **
>
> ** **
>
> On Thu, Feb 28, 2013 at 3:03 PM, Michael Bodell <bodell@247-inc.com>
> wrote:****
>
> I personally find the current behavior more intuitive, where the
> transition associated with deeplyNested1 that goes to somewhereFarAway
> “wins” over the transition as part of deeplyNested2.  I think the key thing
> for me is which atomic states you are in at the time, so thinking from that
> perspective makes the current behavior intuitive.****
>
>  ****
>
> *From:* Jim Barnett [mailto:Jim.Barnett@genesyslab.com]
> *Sent:* Thursday, February 28, 2013 1:57 PM
> *To:* VBWG Public (www-voice@w3.org)
> *Subject:* preemption again (sigh...)****
>
>  ****
>
> Johan points out that the currently proposed definition of preemption (and
> the one in the current spec) have a counter-intuitive result, which is that
> transitions placed very high in the state machine can preempt ones in
> atomic states.  Consider the following case:****
>
>  ****
>
> <state id=”s1”>****
>
> <transition event=”e” target=”someWhereFarAway”>****
>
>     … imagine a bunch of nested states here with no transitions that
> handle e…****
>
>    <parallel>****
>
>       <state id=”deeplyNested1”/>****
>
>       <state id=”deeplyNested2”>****
>
>            <transition event=”e” target=”someWhereElseFarAway”/>****
>
>   </state>****
>
> </parallel>****
>
> …….****
>
> </state>****
>
>  ****
>
> If we are within the parallel region when e occurs, then state
> deeplyNested1 will select the transition that is a child of s1 while
> deeplyNested2 will select the transition that is contained inside it.
>   These two transitions will conflict.  In our current definition, the one
> chosen by deeplyNested1 will win, since that state comes first in document
> order.   Johan finds this counterintuitive since that transition is located
> much higher up in the state machine than the one in deeplyNested2.  (In
> fact, its source state is an ancestor of deeplyNested2).    Johan argues
> that this will make the behavior of complex state machines hard to
> understand.****
>
>  ****
>
> So, my question is:  do other people find this behavior odd or confusing?
>  Do we want to try to tweak the definition so that the transition in
> deeplyNested2 would win?  (It may take a pretty big tweak…)****
>
>  ****
>
> -          Jim****
>
>  ****
>
> P.S.  I’ve looked at UML 2 and find its explanation extremely vague.  It
> does define clearly conflict in terms of intersecting exit sets.  It also
> says that transitions inside descendents take precedence over transitions
> in ancestors, but the rest of the discussion is so confusing that I’m not
> sure what algorithm they really suggest.  ****
>
>
>
> ****
>
> ** **
>
> --
> A foolish consistency is the hobgoblin of little minds - Emerson ****
>



-- 
A foolish consistency is the hobgoblin of little minds - Emerson