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

Re: Soliciting Comments from SCXML Users

From: Stefan Radomski <radomski@tk.informatik.tu-darmstadt.de>
Date: Fri, 8 Feb 2013 12:36:41 +0000
To: "<jbeard4@cs.mcgill.ca>" <jbeard4@cs.mcgill.ca>
CC: Jim Barnett <Jim.Barnett@genesyslab.com>, "VBWG Public (www-voice@w3.org)" <www-voice@w3.org>
Message-ID: <6A775895400B8040A331C2963964820C1952F81B@exchange01.tk.informatik.tu-darmstadt.de>
Hey Jacob,

we implemented a test client on top of uscxml for your test framework[1] and do support your overall approach with the interpreter receiving events via http and sending stable configurations back to the test framework. But your set of tests is problematic as you do not test for SCXML but SCION-ML. In fact, you even test for configurations that are explicitly invalid as per SCXML draft. Take for instance [2] and [3]: The interpreter can never be in bX without being in b as well, as the draft specifies:

"When the configuration contains an atomic state [e.g. b2], it contains all of its <state> and <parallel> ancestors [b in this case]."

If there were to be a set of these tests that would test for SCXML, we are very much in favour for it.

Best regards

[1] https://github.com/tklab-tud/uscxml/blob/master/test/src/scxml-test-framework-client.cpp
[2] https://github.com/jbeard4/scxml-test-framework/blob/master/test/history/history0.scxml
[2] https://github.com/jbeard4/scxml-test-framework/blob/master/test/history/history0.json

On Feb 2, 2013, at 12:59 AM, Jacob Beard <jbeard4@cs.mcgill.ca<mailto:jbeard4@cs.mcgill.ca>> wrote:


There have already been several requests for an SCXML test suite. I'd like to voice my support for this request, as well as take this one step farther and suggest that a canonical SCXML test suite be created that is *normative* with regard to SCXML semantics, and which would have priority over the pseudocode specification of semantics. I will provide a few examples to support this position.

First, some background. When I began implementing SCION in 2010, the first step was to choose a Statechart semantics. I had already chosen to use SCXML syntax, and so I started by performing a straightforward implementation of the SCXML step algorithm from the seventh Public Working Draft of SCXML [1]. This lead to me finding a bug in the algorithm, which was later corrected [2].

This bug lead to an illegal configuration under certain conditions, and was thus easily identifiable as a bug. However, there were certain other semantics captured by the step algorithm which were not easily identifiable as bugs. Instead, they could have been interpreted as an unorthodox semantic choices.

I'll provide one particular example of this:

Most hierarchical state machine semantics specify a function for determining transition priority. This can be as simple as defining a function which takes a pair of transitions and returns the transition that has higher priority. Often, this transition comparison function is based on static properties of the transition, such as depth of the source state. For example, Rhapsody semantics uses "source-state/inner-first" semantics, meaning that transitions with source states that are deeper in the state hierarchy have a higher priority. Another example of the way transitions can be compared is based on the depth of their "arena", which is the least common ancestor of their source and destination states. For example, the Statemate semantics of Statecharts prioritizes transitions based on the arena.

The SCXML specification currently describes its semantics primarily based on the step algorithm, so one must analyze function "selectTransitions" to determine how transitions are prioritized. In the 2010 version of the step algorithm, the behaviour described by "selectTransitions" could not be neatly categorized as "source-state/inner-first" or any other common semantics, but instead could best be described as *mostly* like "source-state/inner-first", but with unusual edge cases, which I'll describe below.

In SCXML Draft 7, "selectTransitions" loops through each atomic state in the configuration, and if that state is not preempted by the set of selected transitions, then it loops through that atomic state and its ancestors in ascending order. When a transition is found whose trigger matches a given event and whose condition is truthy, it is added to the set of enabled transitions, and the algorithm proceeds to the next atomic state. At first glance, this would appear to be like Rhapsody's inner-first semantics, because it iterates through each atomic state's ancestors in ascending order, and breaks on the first transition that it matches. Therefore the transitions of states deeper in the hierarchy will be selected before transitions of outer states. However, the way the algorithm is written leads to an unusual edge case which does not seem to align with inner-first semantics. Consider the following simple test case:


    <parallel id="P">

        <state id="A"/>

        <state id="B">
            <transition target="C" event="t"/>

        <transition target="D" event="t"/>


    <state id="C"/>

    <state id="D"/>


The state machine would start in configuration ['A','B']. Upon receiving event 't', one might expect the resulting configuration would be ['C'], because transitions B -> C and P -> D should both be selected, and B -> C, as the innermost transition, should have the higher priority. However, if one executes "selectTransitions" from Draft 7, what happens is the following:

* enabledTransitions is initialized as the empty set
* The outer loop starts with state = 'A', as it comes first in document order.
* state 'A' is not preempted by any transitions in the empty set enabledTransitions
* The algorithm loops through the ancestors of state 'A', including state 'P'. Transition P -> D is selected and added to set enabledTransitions, and the inner loop is broken.
* The outer loop continues with state = 'B'
* 'B' is preempted by transition P -> D, which has been added to enabledTransitions, so state 'B' and its ancestors are skipped.
* The loop ends with enabledTransitions containing one transition: P -> D.

This unusual behaviour has since been corrected in the spec so that the algorithm behaves like inner-first/source-state semantics. This problem is that at the time, there was no way of knowing whether or not this unusual behaviour was intentional.

My concern is that when defining semantics primarily via pseudocode, the resulting semantics often have a lot of unusual or unintended "features", leading to ambiguity in the spec. This is the main reason why I chose not to base SCION semantics on the SCXML step algorithm: it wasn't clear that every "semantic decision" captured by the pseudcode was actually a useful and meaningful choice regarding semantics that the author had made.

This is particularly problematic, in that the spec makes the pseudocode step algorithm *normative*, as it states "Implementations are free to implement SCXML interpreters in any way they choose, but they must behave as if they were using the algorithm defined here." This means that any conformant implementation would need to implement aspects of the step algorithm which might simply be unintentional behaviour. Furthermore, the pseudocode cannot be executed, which makes it difficult to test.

There are other features that strike me as unusual that remain in the pseudocode in the current draft spec. For example, in function "exitStates", for each state to exit, the algorithm executes its exit actions, and then immediately removes the state from the configuration. This means that the configuration is being modified continually as the entry/exit actions are executed. This in turn means that calls to In() within entry and exit actions are dependent on the document order of their parent state. Consider the following example:

        <data id="i" expr="0"/>

    <parallel id="p">
        <state id="a">
                <if cond="In('a')">
                    <assign location="i" expr="i + 1"/>

        <state id="b">
                <if cond="In('a')">
                    <assign location="i" expr="i + 1"/>

        <transition target="c" event="t"/>

    <state id="c"/>

The state machine starts in configuration ['a','b'], with datamodel variable 'i' set to 0. What will be the value of 'i' after sending in event 't'? It will be 1, because, according to the step algorithm, 'a' will be removed from the configuration by the time b's exit action executes.

This seems peculiar to me when comparing the SCXML step algorithm to other Statechart semantics. For example, the Statemate semantics of Statecharts and Rhapsody semantics of Statecharts describe this operation as transactional, so that the configuration is updated after executing all exit actions, transition actions, and entry actions. Here's a snippet from the Rhapsody semantics of Statecharts[3] (note that by CTs/SRs, he's referring to "compound transitions" and "static reactions", which roughly equate to transitions with and without target attributes, respectively, in SCXML):

– Perform the CTs/SRs that we found should fire:
For each transition do:
• Update histories of exited states.
• Perform the exit actions of the exited states according to the order states are exited, from low state to high state.
• Perform the actions on the CT/SR sequentially according to the order in which they are written on the transition, from the action closest to source state to the action closest to target state.
• Perform the entry actions of the entered states according to the order states are entered, from high state to low state.
• For lowest level states that were entered, which are not basic states, perform default transitions (recursively) until the statechart reaches basic states.
• Update the active configuration.

One must then ask whether the authors of the SCXML step algorithm truly intended that the step algorithm capture the peculiar behaviour described above? Or is this semantic decision an unintentional consequence that occurred because putting the calls to "executeContent" and "configuration.delete" in the same loop made the step algorithm easier to code? How can we meaningfully distinguish between the two? Stated another way, would this be a feature that would be tested in a test suite?

If a step algorithm should not be used to define SCXML semantics, what could be used as an alternative? I feel that what you want to do when describing a semantics is to define the high-level features of the semantics that are important to test, and then test them. Therefore a better approach would be to create a thorough test suite that is normative; furthermore, the step algorithm should be made non-normative.

There are two main advantages to making a test-suite normative with regard to semantics. First, a test suite is more practical than pseudocde, as it can be executed against an implementation to ensure conformance. Second, tests are at a higher level than pseudocode, and it will be easier to reason about them and identify unintended behaviour than it would with pseudocode. In short, a test suite would be more practical and less ambiguous than pseudocode for both specification and implementation.

While it's impossible to write a truly comprehensive test suite that tests every edge case of a Statechart semantics, it is possible to be quite thorough. For example, I feel the above examples I cited could be made into simple tests, which could be understood unambiguously, and would have provided a mechanism for identifying erroneous behaviour in the pseudocode. As another example, the scxml-test-framework I wrote to test SCION includes 112 tests, and I feel it does a good job of testing every aspect of SCION semantics that is important to test. Using just the scxml-test-framework and associated documentation, I feel that a developer would be able to develop their own SCXML interpreter that correctly implements SCION semantics. The tests ensure conformance, and eliminate any ambiguity in the documentation.

The W3C Test Development FAQ neatly summarizes my feelings on this issue:

"Typically, Working Groups develop their test suites when the specifications have reached a reasonable level of stability. However, it is important to start the test development process before the specification is frozen since this helps to identify problems (ambiguities, lack of clarity, omissions, contradictions) while there is still time to correct them." [4]

The question of how the SCXML test suite should be developed requires a separate discussion, and the W3C Test Development FAQ could be used to provide further guidance on this. In particular, the FAQ supports the notion that the WG may solicit the community for tests (section 4), and that tests should be published with a test harness (section 12). These are both positions which I feel would greatly benefit the development of the SCXML test suite.

In conclusion, I'll reiterate my specific calls to action: I think that the spec should be revised to indicate that where the test suite and algorithm are deemed to be inconsistent, the test suite will have priority over the step algorithm. The statement "Implementations are free to implement SCXML interpreters in any way they choose, but they must behave as if they were using the algorithm defined here" should be dropped from the spec, and instead, the spec should indicate that the step algorithm can be used to help guide developers in implementing SCXML, but the test suite is what should be used to verify the correct implementation of SCXML semantics.

I welcome your comments and suggestions. Thanks,


[1] http://www.w3.org/TR/2010/WD-scxml-20100513/
[2] http://lists.w3.org/Archives/Public/www-voice/2011JanMar/0033.html
[3] http://research.microsoft.com/apps/pubs/default.aspx?id=148785, p. 23-24
[4] http://www.w3.org/QA/WG/2005/01/test-faq

On Mon, Jan 7, 2013 at 11:16 AM, Jim Barnett <Jim.Barnett@genesyslab.com<mailto:Jim.Barnett@genesyslab.com>> wrote:
The W3C is soliciting comments from users or implementers of SCXML as part of the standardization process.  We are very interested in hearing from anyone who has worked with the language.  The comments can include a discussion of what it is (or isn’t) useful for, requests for new features, bug reports, or requests for clarifications and changes in the wording.

So if you are using or have used SCXML, please take the time to send us your comments.  The more comments we get, the more confident we can be that we are producing a sound and useful standard.

Thank you,

Jim Barnett (Editor)
Received on Friday, 8 February 2013 12:37:15 UTC

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