Re: Soliciting Comments from SCXML Users

Hi,

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:

<scxml>

    <parallel id="P">

        <state id="A"/>

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

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

    </parallel>

    <state id="C"/>

    <state id="D"/>

</scxml>

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:

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

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

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

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

    <state id="c"/>
</scxml>

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,

Jake

[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>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 Saturday, 2 February 2013 00:00:22 UTC