W3C home > Mailing lists > Public > www-voice@w3.org > January to March 2013

RE: proposed new definition of preemption

From: Jim Barnett <Jim.Barnett@genesyslab.com>
Date: Tue, 26 Feb 2013 18:23:27 +0000
To: chris nuernberger <cnuernber@gmail.com>
CC: David Junger <tffy@free.fr>, "VBWG Public (www-voice@w3.org)" <www-voice@w3.org>
Message-ID: <57A15FAF9E58F841B2B1651FFE16D2810234C5@GENSJZMBX03.msg.int.genesyslab.com>
I'm not sure that I understand your point about ordering.  If we have a parallel state P with children S1 and S2, and a transition T1 before S1 and T2 after S2, then it is always possible that S1 will select T2 and S2 will select T1, so we end up bouncing back and forth no matter what order we visit S1 and S2 in.

I think that the suggestion that we use the document order of the atomic states makes sense.  It makes the processing easy to visualize. You pick a transition in S1 and keep it no matter what.  Then you move to S2 and if you find something that doesn't conflict you keep it and move on.  Anything that has already been selected trumps anything new.

We put very few restrictions on element ordering in our schema because we don't see any reason to restrict implementations.  But any good GUI will put all the transitions in one place, states in another, etc., which will make things easier to understand.

-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Tuesday, February 26, 2013 9:41 AM
To: Jim Barnett
Cc: David Junger; VBWG Public (www-voice@w3.org)
Subject: Re: proposed new definition of preemption

I like the new algorithm.

David, a simplification would be to take the (in general) lcca of the transition's source and it's targets and *then* you can do the descendent check (if either is a descenant of the other then you can't run the later transition).  If you browse earlier emails you will see that was the algorithm I proposed; it is faster than this one and would get any case correct that this one would get correct.

But Jim and I talked about this to great length and we agree that because the algorithms have identical results (exit set vs. arena check) then it didn't matter and Jim liked the exit set definition more because he felt it was closer to UML specs.  I don't care at all really as long as we move to using actual graph topology to do the check.

I think you pointed this out but if you want things to work out visually in terms of preemption then you also want to select transitions in reverse child order on the state when you are checking them.  Really, for transitions you want complete reverse document order and this would mean that you could, with your eyes, walk from an activated atom *up* the document and the transition selection process would consistently move *up* the document toward the root.  Currently we sort of move up, then down, then up, then down as you pointed out earlier.

I would be in favor of such a change (select and preempt in reverse document order).


On Tue, Feb 26, 2013 at 6:39 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
For your first point, using 'transition order' amounts to using document order of the _states_ that selected the transitions, not the transitions themselves.  I agree that may be clearer.  All we have to do with the existing definition is call enabledTransitions.toList(), which will sort  them in the order in which the items were added, which is the order of the selecting states.  (By the way, the definition I sent around is wrong, in that it doesn't sort them in any order.)

On your third point, I think that you are right that targeted transitions will conflict if one's source state is a descendent of the other's, but that is not the only condition under which they conflict.  Consider a parallel element P with children S1, S2, and put transitions in S1, S2 that both exit P and go to different remote states (i.e., ones that cannot be simultaneously active).  The transitions in S1, S2 conflict, but neither's source state is a descendent of the other's.  However, I agree that practical implementations will not want to compute exit sets.

-          Jim

From: David Junger [mailto:tffy@free.fr<mailto:tffy@free.fr>]
Sent: Tuesday, February 26, 2013 4:18 AM
To: VBWG Public (www-voice@w3.org<mailto:www-voice@w3.org>)
Subject: Re: proposed new definition of preemption

Le 25 feb 2013 à 16:53, Jim Barnett a écrit :

First, I think we should preempt in transition order, not document order (i.e. a transition should be preempted by transitions that are selected before it, not witten before it). If we use document order, then we'll end up with <state>s and <transition>s mixed in complex states to achieve a precise result, very hard to read or visualize.
3.       Is it a good idea to get rid of the word "preemption"?  (the selectTransitions functions have to be modified to call removeConflictingTransitions instead of filterPreempted, but the argument to the functions and the return values are the same.  hasIntersection() und union() are defined in the list of functions/procedures at the top of the algorithm)

I don't mind the word. I just hoped we could find an elegant solution that made it unnecessary.

4.       Is there a better way to do this?

It seems that targeted transitions will always conflict if one's source state is a descendant of the other's and that those cases are precisely the cases that trip the source state approach. Is that correct? I don't think that would be a "better" way to explain it in the spec but if it is equivalent then I like it better for my implementation (in which I don't want to compile exit sets in advance, for example).


A foolish consistency is the hobgoblin of little minds - Emerson
Received on Tuesday, 26 February 2013 18:23:55 UTC

This archive was generated by hypermail 2.3.1 : Tuesday, 6 January 2015 21:07:43 UTC