RE: revisiting preemption

On the issue of UML compatibility, there are certainly implementations that want UML-capability (namely those built by companies with UML design tools.)  However, the group's main reason for wanting UML capability are the following:

1.       As much as possible, standards groups want to codify existing industry practice.  UML state charts have been the dominant state machine language for at least 20 years, and the world has a lot of experience working with them.  As a _standards_ group, we need a good reason to deviate from UML.

2.       Harel worked on the UML state notation.  Harel really understands state machines.  If you are arguing with Harel about state machines, you're wrong.

3.       The W3C insists on royalty-free standards.  Our fear is always that some troll will pop out with a patent that he claims our standard infringes upon.  Sticking close to Harel and UML gives us excellent prior art in such a case, since Harel's work on state charts goes back to the 70s, and UML state charts emerged some time in the 80s.   Any patent covering areas where SCXML is identical to UML is very likely invalid.

This doesn't mean that there aren't interesting alternative versions of state machines to be investigated.  Only that that investigation shouldn't be done in a _standards_ group.

That said, I think that on edge cases like the preemption of targetless transitions, we can deviate from UML if we find a good reason to do so.  But our default is always to stick with UML, for the reasons listed above.


-          Jim
From: chris nuernberger [mailto:cnuernber@gmail.com]
Sent: Monday, February 18, 2013 1:14 PM
To: David Junger
Cc: VBWG Public (www-voice@w3.org)
Subject: Re: revisiting preemption

"The most intuitive (and shortest to explain) is that optimally-enabled transitions are taken in transition order unless their source has been exited by a previous transition, in which case their are disabled during the exit step. But that's not UML-compatible."

This would also be the most efficient to implement.  Taking targetless transitions into account means you have to consider all atoms regardless of if they would be exited.  I would rather for a possibly very efficient implementation than a UML compatible implementation although of course I can offer that as an option in my library.

I don't understand the push for UML compatibility and it isn't a requirement for our implementation.

Are there any existing implementations of SCXML which require UML compatibility?

Honestly I am happy whichever way this goes; although of course I tend towards a specification which enables optimal implementation efficiency so the widest range of applications can benefit from this system.

Chris

On Mon, Feb 18, 2013 at 10:46 AM, David Junger <tffy@free.fr<mailto:tffy@free.fr>> wrote:
Le 18 feb 2013 à 15:58, Jim Barnett a écrit :


1.       Do we want another definition of preemption?  The obvious candidate is UML's definition:  two transitions conflict if their exit sets have a non-null intersection. We can tweak the definition based on transition classes/types to have the same semantics, so the real question is:  which definition is easier to understand?

The most intuitive (and shortest to explain) is that optimally-enabled transitions are taken in transition order unless their source has been exited by a previous transition, in which case their are disabled during the exit step. But that's not UML-compatible.

If you want UML-compatible transitions, then, first sort the optimaly-enabled transitions according to this comparator(t1, t2):
tie if t1 is targetless and t2 is targetless.
t1 < t2 if t1 is targetless.
t2 < t1 if t2 is targetless.
t1 < t2 if t1's LCCA is a descendant of t2's LCCA.
t2 < t1 if t2's LCCA is a descendant of t1's LCCA.
tie otherwise.

use transition order (or document order, which is equivalent at this point) to break ties (though that's unnecessary if you use a stable sort).

Then proceed as before, i.e. optimally-enabled transitions are taken in that order unless their source has been exited by a previous transition, in which case they are disabled during the exit step.

Note that this total ordering of the SC's transitions does not change depending on which transitions are enabled, so it can be compiled.



2.       What do we want to do about targetless transitions?  They have an empty exit set, so on the UML definition they don't preempt any transitions and don't preempt any other transitions.  The existing definition (based on transition types/classes) says (in effect) that a targetless transition is preempted by any preceding transition that exits its source state.  This may seem intuitively clear, but it isn't necessary by any means.  The whole point of preemption is to block transition sets that could produce an illegal configuration, and targetless transitions will never do that.   By not preempting targetless transitions, we end up with the largest set of transitions that can be guaranteed not to cause problems.

Agreed, though it might be less intuitive, I don't think it's horribly confusing to say that targetless transitions get priority. But we also have to define the transition's execution order (for determinism). If they can't be preempted then they should be executed before all others.



3.       When we discussed this issue in the past, we decided that preemption is so complicated that it should be defined in a separate place, hence we have 'filterPreempted' as a separate function.  On the other hand, the filtering could be folded  back into the selectTransitions functions, particularly if it is based on the intersection of exitSets.   So we could consider getting rid of filterPreempted as a separate function.  However, if we do this, we have to insert the same conflict/preemption-detecting logic in both selectEventlessTransitions and selectTransitions, so it may be better to keep it factored out into a  separate function.

I believe my comparator proposal solves that. You just need a quick test in the exit step to check if the transition's source is still active.

David



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