Re: more on preemption

You aren't missing anything.  I think the proposed algorithm will not put
is in an invalid configuration as far as exit states are concerned.  It
just decides exit sets on one criteria and then preemption on another
criteria; an inconsistency that will be difficult for an end use of the
system to decipher.

In the end this may just be a judgement.  Doing preemption based off of
arenas provides an answer consistent with how to generate exit sets in the
first place.  Doing it off of source will match UML closer.

I think source is a poor technical choice but it will work.  As I think
exit sets is a poor technical choice, but they will work.  They will both
just lead to more questions and more bugs in implementation later down the
road than a short definition based off of arenas but this is the path that
you are absolutely dead set to go down.

Chris


On Fri, Mar 8, 2013 at 12:41 PM, Jim Barnett <Jim.Barnett@genesyslab.com>wrote:

>  By ‘correctness’, I mean that the preemption algorithm will never put us
> in an illegal state configuration.  As far as I can tell, as long as we
> detect conflicts correctly, then we can use any heuristic we want to
> resolve conflicts, including flipping a coin, and the algorithm will be
> ‘correct’.   Unless I’m missing something, the issues with preemption
> heuristics are whether they are clear, or intuitive, or consistent with
> UML, etc.  ****
>
> ** **
>
> **-          **Jim****
>
> ** **
>
> *From:* chris nuernberger [mailto:cnuernber@gmail.com]
> *Sent:* Friday, March 08, 2013 1:27 PM
>
> *To:* Jim Barnett
> *Cc:* VBWG Public (www-voice@w3.org)
> *Subject:* Re: more on preemption****
>
>  ** **
>
> I don't have time right now.  The error isn't in calculating the exit sets
> but specifically in deciding how to preempt things.****
>
> ** **
>
> The error is line:****
>
> if isDescendent(t1.source, t2.source):****
>
>                     transitionsToRemove.add(t2)****
>
>                 else:****
>
>                     t1Preempted = true****
>
>                     break****
>
> ** **
>
> Where it reads t1.source and t2.source is should be getArena(t1) and
> getArena(t2).****
>
> ** **
>
> Chris****
>
> ** **
>
> ** **
>
> On Fri, Mar 8, 2013 at 11:20 AM, Jim Barnett <Jim.Barnett@genesyslab.com>
> wrote:****
>
> Chris,****
>
> Are you saying that we are calculating exit sets incorrectly?  The
> algorithm detects a conflict between two transitions whenever their exit
> sets intersect.  There’s no mention of source states here (i.e., in the
> definition of conflict) except insofar as they help determine the exit set.
> ( Internal transitions are handled in getTransitionDomain(), so their
> influence on the exit set should also be reflected in the algorithm) Then
> once a conflict is detected, we look at the source state relationships to
> determine who preempts whom.   That’s our heuristic for resolving
> conflicts, inherited from UML, but I don’t think it effects correctness.
> But if we’re calculating exit sets incorrectly, that would cause us to be
> incorrect.  ****
>
>  ****
>
> Can you send around an example that shows the problem?****
>
>  ****
>
> Thanks,****
>
> Jim****
>
>  ****
>
> *From:* chris nuernberger [mailto:cnuernber@gmail.com]
> *Sent:* Friday, March 08, 2013 1:07 PM****
>
>
> *To:* Jim Barnett
> *Cc:* VBWG Public (www-voice@w3.org)
> *Subject:* Re: more on preemption****
>
>  ****
>
> I don't think the algorithm is correct.  This goes back to the UML spec
> which I *also* think is incorrect.****
>
>  ****
>
> This argument ignores transitions of internal types which is a detail.****
>
>  ****
>
> The exit set is calculated via the LCCA of the source and the target
> states.  Let's call this item the transition arena as we have before.****
>
>  ****
>
> It may be the source but it also may be considerable higher up the state
> graph than the source.****
>
>  ****
>
> Your given algorithm only compares the transition sources for descendant
> qualities when it should compare the transition arenas *because* the
> sources may be unrelated in the graph *but* the exit sets collide.  A
> correct algorithm would look *just* like the one given except you would
> compare the transition arena's for descendent instead of transition sources.
> ****
>
>  ****
>
> Chris****
>
>  ****
>
>  ****
>
>  ****
>
> On Fri, Mar 8, 2013 at 8:12 AM, Jim Barnett <Jim.Barnett@genesyslab.com>
> wrote:****
>
> There hasn’t been any further discussion on this.  Based on the discussion
> so far, I think that we should say that transitions in descendents preempt
> transitions in ancestors.)  The UML spec requires this quite clearly (even
> if the rest of the discussion is confusing) and “descendents preempt
> ancestors” is one of the basic principles of the language.  Here’s a
> modified preemption algorithm that implements it.   ****
>
>  ****
>
> Implementations will be able to do something more efficient.  For example,
> this algorithm tries to handle the case where a transition t1 conflicts
> with multiple transitions, say t2 and t3, where t1’s source state is a
> descendent of t2’s, but not of t3’s.  in this case, t1 is preempted by t3
> (because t3 was chosen in a preceding state), so we _*keep*_ t2, even
> though it would be preempted by t1 if t1 weren’t blocked by t3.  I’m pretty
> sure that this case can’t arise in practice, but I haven’t been able to
> prove it, so I have tried to make the algorithm handle it.  ****
>
>  ****
>
> Let me know what you think about both the clarity and correctness of this
> version.  ****
>
>  ****
>
> -          Jim****
>
>  ****
>
> *function removeConflictingTransitions(enabledTransitions)*****
>
> enabledTransitions will contain multiple transitions only if a parallel
> state is active. In that case, we may have one transition selected for each
> of its children. These transitions may conflict with each other in the
> sense that they have incompatible target states. Loosely speaking,
> transitions are compatible when each one is contained within a single
> <state> child of the <parallel> element. Transitions that aren't contained
> within a single child force the state machine to leave the <parallel>
> ancestor (even if they reenter it later). Such transitions conflict with
> each other, and with transitions that remain within a single <state> child,
> in that they may have targets that cannot be simultaneously active. The
> test that transitions have non-intersecting exit sets captures this
> requirement. (If the intersection is null, the transitions are contained in
> separate <state> descendents of <parallel>. If intersection is non-null,
> then at least one of the transitions is exiting the <parallel>). When such
> a conflict occurs, then if the source state of one of the transitions is a
> descendent of the source state of the other, we select the transition in
> the descendent. Otherwise we prefer the transition that was selected by the
> earlier state in document order and discard the other transition. Note that
> targetless transitions have empty exit sets and thus do not conflict with
> any other transitions. ****
>
> We start with a list of enabledTransitions and produce a conflict-free
> list of filteredTransitions. For each t1 in enabledTransitions, we test it
> against all t2 that are already selected in filteredTransitions. If there
> is a conflict, then if t1's source state is a descendent of t2's source
> state, we prefer t1 and say that it preempts t2 (so we we make a note to
> remove t2 from filteredTransitions). Otherwise, we prefer t2 since it was
> selected in an earlier state in document order, so we say that it preempts
> t1. (There's no need to do anything in this case since t2 is already in
> filteredTransitions. Furthermore, once one transition preempts t1, there is
> no need to test t1 against any other transitions.) Finally, if t1 isn't
> preempted by any transition in filteredTransitions, remove any transitions
> that it preempts and add it to that list. ****
>
> function removeConflictingTransitions(enabledTransitions):****
>
>     filteredTransitions = new OrderedSet()****
>
> // toList sorts the transitions in the order of the states that selected
> them****
>
>     for t1 in enabledTransitions.toList():****
>
>         t1Preempted = false;****
>
>         transitionsToRemove = new OrderedSet()****
>
>         for t2 in filteredTransitions.toList():****
>
>             if computeExitSet(t1).hasIntersection(computeExitSet(t2)):****
>
>                 if isDescendent(t1.source, t2.source):****
>
>                     transitionsToRemove.add(t2)****
>
>                 else: ****
>
>                     t1Preempted = true****
>
>                     break****
>
>         if not t1Preempted:****
>
>             for t3 in transitionsToRemove.toList():****
>
>                 filteredTransitions.delete(t3)****
>
>             filteredTransitions.add(t1)****
>
>            ****
>
>     return filteredTransitions****
>
>  ****
>
>
>
> ****
>
>  ****
>
> --
> A foolish consistency is the hobgoblin of little minds - Emerson ****
>
>
>
> ****
>
> ** **
>
> --
> A foolish consistency is the hobgoblin of little minds - Emerson ****
>



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