RE: SCXML: interpretation algorithm

Add 2) Ordering issues
 
I realized that "exitOrder" and "entryOrder" is in fact "element exit order" and "element entry order" in the SCXML document => ordering of entering and exiting states is therefore clear. I would however state this in the SCXML draft, because it is not clear at first sight since you mix up ordering of entering/exiting elements in XML with ordering of states that should be entered/exited as result of transition.
 
However, the issue with unspecified ordering of transitions (as result od unordered configuration set) is still problem.
 
Aleš Doleček	
Senior Consultant	
NextiraOne Czech s.r.o.	
 	
email:	 ales.dolecek@nextiraone.cz	
tel:	 +420 255 770 737	
mobil:	 +420 737 269 737	
fax:	 +420 255 770 120	
www.NextiraOne.cz <http://www.nextiraone.cz/> 	
 	
 	
 

________________________________

From: www-voice-request@w3.org [mailto:www-voice-request@w3.org] On Behalf Of DOLECEK Ales
Sent: Monday, January 25, 2010 3:07 AM
To: www-voice@w3.org
Subject: SCXML: interpretation algorithm


Hello,
 
  I'm trying to implement SCXML interpreter and came across several issues.
 
---------------------
 
1) The algorithm may lead to invalid configuration
 
<parallel id="P">
    <state id="S1">
        <state id="S11"/>
        <state id="S12"/>
    </state>
    <state id="S2"/>
    <state id="S3"/>
</parallel>
 
Configuration C1 is [P, S1, S11, S2, S3]. At this moment arrive event that triggers following transitions:
 
T1: S11 => S12
T2: S2 => S3
 
Note: I haven't found constraint that prohibits transition between compound states that are children of common parallel.
 
i) Both transitions are enabled
    T1: checked first because S11 is first atomic state in configuration => enabled
    T2: transition T1 does not leave P so it does not preempt state S3 => enabled
 
ii) States to exit
    T1: S1 is LCA of [S11, S12] => exit [S11]
    T2: P is LCA of [S2, S3] => exit [S11, S1, S2, S3]
 
Now we are in intermediate configuration C2 [P]
 
iii) States to enter
    T1: S1 is LCA of [S11, S12] => enter [S12]
    T2: P is LCA of [S2, S3] => enter [S3]
 
So we end up with configuration C3 [P, S12, S3] which is illegal.
 
What went wong:
 
a) Since source of transition must be in starting configuration and all targets of transition must be in end configuration the LCA of them will not exit. Here, however the LCA for T1 was exited because of T2. That is why S1 is missing in C3. This problem does not relate to fact that T2 is between children of parallel state. If it was aiming out of P the result would be similar - only this time the C3 would be missing also P as well and possibly even more states up the tree.
b) Because S2 was targeting sibling in parallel state their LCA was P and was not exited, and thus later entered again, which would (in turn) force entering of child states. That is why S2 is missing in C3.
c) There is also 3rd problem possible. If S1 had one more state S13 and it was target of T2 then C3 would be [P, S1, S12, S13] - two active sub-states of <state> at same time.
 
The problems raise from use of parallel. The standard does not mandate that transition target must explicitly name states from all children of parallel. It only prohibits to name two states from same child state. This is clearly because the target can be any descendant of parallel not just its direct child. The procedure "addStatesToEnter" tries to compensate for this as it walks up the ancestors of target state - adding sibling states (that are not already selected for entry) when it enconuters parallel state. Here however the parallel state P is not exited so it is not discovered.
 
Possible solutions:
 
a) walk up the ancestors until state that is in configuration or statesToEnter is found => this would fix the first problem that one transition force exit of state that is LCA (or its ancestor) of other transitions source and target(s)
b) if the LCA of tranistion source and target(s) is parallel add it to the the statesToExit => this would fix the second problem when transition is taken between children of parallel state
c) when adding new transition to enabledTransitions check source states of previously added transitions if they are preempted by the new transition - if they are remove the previous transition
 
Note:
The 3rd change to algorithm not only fixes the problem but also makes the state machine more reasonable. If there was third transition completly inside S3 it would not be enabled because S3 would be preemted by T2 at the time of check. Why should be T1 enabled and T3 ignored if they are principially eual? The extra check for already added transitions is not very expensive because the list is usually very short. If there are no parallel states then there will be only one transition so the list will be empty when it is added.
 
---------------------
 
2) In the "Open Issues" A.4 section (parallel transition order) standard says:

	In the case of transitions selected from parallel regions, the current algorithm completely specifies a) which transition is to be selected in case of conflicts (see isPreempted in B Algorithm for SCXML Interpretation) and b) the order in which those transitions should be taken (see microstep in B Algorithm for SCXML Interpretation). However, we could avoid completely specifying one or both of these choices. This would give implementations greater flexibility, but would impair the portability of applications, which would not necessarily behave the same way on different platforms. We solicit feedback on these alternatives.

It is however not clear in which order will be states exited and entered - not even which transition will be selected. Procedures "exitStates" and "enterStates" employ so called "exitOrder" and "enterOrder" which are not specified anywhere.
 
i) the "natural" exit order (before sorting) is determined by
    a) order in which transitions are selected - which is in turn determined by order of list of atomic states returned from configuration
    b) order of atomic states - second time in procedure "exitStates" when the atomic states are checked agains LCA
 
Configuration is "set" and normally, unless explicitly requested, are sets unsorted. Definition of "Set" nor "Configuration" used in draft does not make this clear. Given the SCXML from previous section if the C1 returned atomic states as [S3, S2, S12] then T2 would be enabled and T1 not (contrary to order [S12, S2, S3] where both transitions are selected - see above).
 
If the standard explicitly requested ordering of states in configuration, or better just ordering of list of atomic states provided by configuration, it would not have to employ the magic exitOrder clause. Not to mention that sorting atomic states will be much, much faster because there is only 1 unless some parallel state is active.
                
ii) the "natural" enter order (before sorting) is determined by
    a) order of transitions - which is in turn determined by order of atomic states in configuration
    b) order of children of parallel states found while traversing up the ancestors of entered state (asuming document order, but not stated explicitly)
    c) order of states in historyValue - whih is in turn determined by order of (all) states in configuration
 
Same as in case of exiting, only now history makes it bit more difficult as it works with all states in configuration.
 
Solution:
a) Define ordering of configuration
The "document order" is probably easiest to implement. It has, however, the wrong property that it might return parent states of atomic states first. (Is it really problem?) The "reverse document order" (used for example by Apache SCXML implementation to sort exit states) returns atomic states first, but also inverts ordering of atomic states of children of parallel. This would influence the selection ordering of transitions if used generally. What suits best is "element exit order" - e.g. traverse tree in document order and "emit" states as their element is left.
 
Since configuration is actually tree with very low branching factory (only on active parallel states) it is quite simple to achieve "element exit order" by implementing it as tree. Comapred to non-trivial comparator of two states needed to sort the configuration Set or List it returns.
 
b) define "exitOrder" as "reverse document order" and "enterOrder" as "document order"
This leaves implementors more freedom in the way they implement the algorithm. Drawback is that it does not avoid the sorting - especially the entryOrder. This sorting can't take advantage of the configuration (which is always relatively small) and might be problem for HUGE state charts.
 
---------------------
 
3) Shallow history of parallel state is useless
 
Let me remind: "Shallow history is set of active states of composite state that contains the history, that were in configuration when the state was exited."
 
For <parallel> it is simply list of its children.
 
Much better, IMHO, would be to define shallow history of <parallel> as union of shallow histories of its children. This would even work for <parallel> containing other <parallel> as it's immediate child.
 
---------------------
 
In the end, as I'm now implementor :-) , I humbly present my opinions on the "Open Issues":
 
1) Removing restrictions on <invoke>
    Both issues (invoke in non-atomic states and more than one invoke in one state) does not present conceptional dificulty. => I would allow it.
 
    Note: There is other issue I see with invocation of multiple external services - inter-service communication. It is, however, already there thanks to parallel states. Currently the parent must arrange for marshalling events between external services it invoked. And if the external services are remote and use transport mechanism can not guarantee ordered delivery state machine become either non-deterministic or will have to take control of synchronisation by confirming event delivery before proceeding - not suitable for all transports especially asynchronous that are on the other hand suitable for messaging.
 
2) Iterative constructs
    I belive that targetless transitions are not same as iterative constructs. If there are 2 or more enabled transitions in children of parallel, you are risking horse race condition, because they will take turns when processing individual steps of iteration. Also nested iterations are hardly achievable with transitions.
    Allowing iterative constructs in this case works as "hygienic factor" and would be probably also more effective. But I would consider use of break and continue constructs. They make things bit more complicated and in-turn degrade the efficiency.
 
    => I would allow it, but considered use of break and/or continue
 
3) Alternative notation
    I would not change the current "wording", maybe with the exception of transition since verb makes more sense than noun. Although the SCXML is still draft, there are already implementations out there and changing the element/attribute names just to make them "feel better" does not justify the effort. Real world end users would probably use some tools and edit the SCXML using GUIs (like the Shall example in draft). Or maybe generate from them UML.
    => indifferent, rather not
 
4) Parallel transition order
    Definitelly would explicitly specify it. Interoperability is very importatnt.
    Current draft is however not explicit enough - as shown above
    => specify as exactly as possible
 
5) Error handling
    Note: What should error report the caouse or the source. Eg. if there is error in assign because of illegal location or data then "error.invalidloc" or "error.invaliddata" is queued. But how should state determine that it was it's error? Or was from current visit of the state?
    - Should there be "source" attribute in the event?
    - Could it be usefull to count number of events and/or number of configuration changes?
    => This would allow to determine if the event was raised during crrent visit of state or while processing current event
    => Needs work
 
6) Simplification of raise and send
    I belive that sending events into internal event queue of other SCXML interpretter is evil. It is sign of bad design and makes the state machine non-deterministic from the point of single instance. This in turn makes things much harder for authors of state machines as they must count with "unsolicited" events in the sequence of events they expect in handling external events. What is the point to distinguish between internal and external events then?
    Also makes implementations more vulnerable to issues of concurrent programming. If for example you are precessing every external event by different thread (sharing threads between possible very high number of SCXML sessions) you might expect that all events in internal queue were created by same thread. It might be very important to things like garbage collection (memory leaks or double disposal), class loading issues in java, or even evaluation of conditional/location/value expressions.
    => Definitelly revert
 
---------------------
 
Sincierly yours
 
Aleš Doleček	
Senior Consultant	
NextiraOne Czech s.r.o.	
 	
email:	 ales.dolecek@nextiraone.cz	
tel:	 +420 255 770 737	
mobil:	 +420 737 269 737	
fax:	 +420 255 770 120	
www.NextiraOne.cz <http://www.nextiraone.cz/>