RE: ISSUE-826 Re: More Problems with Preemption

Chris,
Different people find different definitions to be clear.    I agree that most people don't find the definition based on classes/types to be very clear, so I am proposing dropping it.  The definition based on exit sets is as clear a one as I can find, and matches the UML definition.  Compatibility with UML is a high priority for us, because a) it is a very widely used state machine notation, b) Harel consulted on its definition (and SCXML is very definitely intended to be based on Harel's semantics).  It is very useful to be able to  say that there is equivalent SCXML document for any UML state machine diagram.

Efficiency arguments are a red herring, given that the point of the algorithm is to define the semantics of the language, _not_ to tell implementers how they should implement it.  You are free to use any algorithm you want, as long as it the result behaves the same as the one in the spec.

If you are proposing a definition of preemption that gives a different result than the one based on intersecting exit sets, we can discuss which provides better semantics.   As I indicated before, I think that targetless transitions can be handled either way (preempted or not preempted).  They're really an edge case because there's a sense in which they are not _transitions_ at all (they don't leave or enter any state).

I'm very interested if there are differences in which transitions are preempted in cases that don't involve targetless transitions.  From what you've said, I don't think that  there are any.  (Let me know if I'm wrong.)  If there aren't any, then the definition of  the language is fixed and all we are discussing is the best way to present it.   As I said before,  that is a matter of taste.


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Friday, February 08, 2013 11:37 AM
To: Jim Barnett
Cc: www-voice@w3.org
Subject: Re: ISSUE-826 Re: More Problems with Preemption

Jim,

What precisely about nonconflicting arenas isn't clear?  It is a *lot* more clear than the type system given in the specification.

Given a clear definition of arena you could refactor EnterStates, ExitStates and IsPreempted to all use transition arena.  The pseudocode would be easier to understand, more factored, and easier to prove correct if the definition of a transitions enter-set and exit-set were based off of arena.

An implicit assumption I have is that we have to preempt transitions from states that would be exited.  I think this would happen automatically due to the transition selection process but without proving it I think the preemption algorithm should take that into effect.  I can see, however, that it perhaps doesn't need to happen because code in that transition could be protected with an 'In' query.

The problem with classes or types is that they don't take the graph of *both* transitions into account.  So either you get transitions in logically distinct regions of the state graph that are unnecessarily preempted *or* you get invalid transitions like we see in the example.  You can't come up with a definition of transition class that will avoid this problem because it doesn't take the *other* transition's local position in the state graph into account.

Subgraph roots or arenas is *more*  efficient than set comparison and is what is used in other more proven state machine systems (see paper below).

Pretty much it boils down to this:

1.  Types or categories are either too permissive or too restrictive because they don't take the combined graph defined by both transitions into account.

2.  If you are going to go with arenas, then my definition is easier to understand and prove correct because it isn't immediately obvious that the transition's entry set will be protected in your algorithm.

The set algorithm you proposed is slower and doesn't take targetless transitions nor the entry set into account.  It's only benefit compared to what I proposed is that it is 'like UML' as far as I can see.

The isDescendant function can be computed in O(1) given nodes that are numbered in a depth first traversal.  The transition arena can be precomputed, identically as a type or class.  Thus, really, the algorithm I proposed is O(1) given some simple precomputation on the state graph.


Do you have a solid, technical reason why the specification shouldn't be change to include the definition of arena along with the algorithm that I proposed?  I don't agree that going with inferior algorithms in order to be 'like' something else is a solid technical reason.  I *know* (can prove) that any solution based on types or classes will not be as correct and it is sure harder to see what its implications are from reading it.

Given a choice, I certainly would pick set comparison over any sort of type or class comparison but we should look for the 'best' option and since people are implementing their machines by directly translating the pseudo-code, why not put the best algorithm in the code as possible?  Furthermore it allows the introduction of a new, clear, and unambiguously defined concept (arenas).  This concept allows the pseudocode to be refactored to be clearer in three places (enterSet, exitSet, isPreempted).

https://cs.uwaterloo.ca/~nday/Papers/uw-scs-tr-2009-05.pdf

Chris


On Fri, Feb 8, 2013 at 8:39 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
Chris,
There doesn't seem to be any definition of  preemption that everyone finds clear.  I like the one involving transition classes (and it's very efficient, since the classes can be computed at design time), but most other people seem not to.

We don't define 'conflict' for entry sets, so the question would be whether transitions with non-conflicting exit sets can put the state machine in an illegal state configuration.  It would be complex to prove that they cannot, but an informal argument is:  the  only transitions with intersecting exit sets are pairs of class 2 and class 3 transitions or pairs of class3 transitions.  Furthermore, if you're in a legal state set, the only way to get into an illegal one would be to take a class3 transition, plus a class2 or class3 transition, and this definition blocks that.  (This argument assumes that the rest of the algorithm is correct, of course  - you could end up in an illegal configuration if you selected two transitions within a single state, etc., but the algorithm makes sure that doesn't happen.)


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com<mailto:cnuernber@gmail.com>]
Sent: Friday, February 08, 2013 10:14 AM

To: Jim Barnett
Cc: www-voice@w3.org<mailto:www-voice@w3.org>
Subject: Re: ISSUE-826 Re: More Problems with Preemption

OK, I can buy that although I do think it is odd to propose an algorithm that is demonstrably less efficient.  I guess I just find this definition much clearer:

Arena Orthogonal : Two transition occurrences are included in the same small-step only if their arenas are orthogonal, where the arena of a transition is the smallest (lowest in the hierarchy of the composition tree) Or-state that is the (grand)parent of the source and destination control states of the transition.

Obviously that would be the transition arena would be defined by the transition subgraph root.

This is also the definition used in the white paper linked to from SCION's comparison page.

Is it possible that transactions with non-conflicting exit sets would have conflicting entry sets?

Chris

On Fri, Feb 8, 2013 at 8:07 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
Speed is not an issue in the algorithm, since implementations are only required to behave _as if_ they are implementing the algorithm in the spec.  There are all sorts of places where the spec algorithm can be optimized (it calculates certain values over and over again, instead of caching them.  And you wouldn't bother with  filterPreempted at all if you only had a single transition.)

I think that the advantage of the version that I proposed is that it is very close to the normative wording of the spec, which is in turn taken from UML, with which we try to stay consistent.


-          Jim

From: chris nuernberger [mailto:cnuernber@gmail.com<mailto:cnuernber@gmail.com>]
Sent: Friday, February 08, 2013 10:02 AM
To: Jim Barnett
Cc: www-voice@w3.org<mailto:www-voice@w3.org>
Subject: Re: ISSUE-826 Re: More Problems with Preemption

In which cases would this algorithm differ from the one I proposed?

The one I proposed is far faster.

Chris



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



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