- From: Stefan Radomski <radomski@tk.informatik.tu-darmstadt.de>
- Date: Sat, 9 Feb 2013 23:08:04 +0000
- To: "<jbeard4@cs.mcgill.ca>" <jbeard4@cs.mcgill.ca>
- CC: "VBWG Public (www-voice@w3.org)" <www-voice@w3.org>
- Message-ID: <6A775895400B8040A331C2963964820C19532DEF@exchange01.tk.informatik.tu-darmstadt.>
Hey Jacob,
I re-ran the tests (informal report below) and there are definitely some issues on my part with parallel states (I submitted another respective mail to this list, but it was not yet delivered it seems). There are a couple of points I'd like to point out:
- There is no scxml "profile" attribute (anymore?)
- The delay[expr] attribute with send is supposed to be in css2 format (numeric value with "s" / "ms" prefix afaict)
- You have several occurrences of a "getData" ECMAScript function that is specified nowhere
- I replied to your framework when there were no more pending delayed sends, not after the first stable configuration, this lead to some failures
- You use the type-sensitive "===" operator in your conds, I am not sure what to make of it as I stringified all event data and the issue is pretty much unspecified
With the exception of delayed sends I do think that your overall approach is very reasonable and we would support the canonical test cases in this format. Our interpreter is obviously still a little rough around the edges (or blatantly buggy with respect to parallel and transition order :). I will rerun the suite as soon as I ironed out the more obvious bugs. In any case, having tests like these is a *tremendous* help to ensure proper implementation.
Best regards
Stefan
actionSend/send1.scxml" # passed
actionSend/send2.scxml" # passed
actionSend/send3.scxml" # passed
actionSend/send4.scxml" # won't support
actionSend/send5.scxml" # won't support
actionSend/send6.scxml" # won't support
actionSend/send7.scxml" # passed
actionSend/send8.scxml" # won't support
assign-current-small-step/test0.scxml" # passed
assign-current-small-step/test1.scxml" # passed
assign-current-small-step/test2.scxml" # passed
assign-current-small-step/test3.scxml" # passed
assign-current-small-step/test4.scxml" # passed
assign-next-small-step/test0.scxml" # failed
assign-next-small-step/test1.scxml" # getData not defined
assign-next-small-step/test2.scxml" # getData not defined
assign-next-small-step/test3.scxml" # failed
atom3-basic-tests/m0.scxml" # passed
atom3-basic-tests/m1.scxml" # passed
atom3-basic-tests/m2.scxml" # passed
atom3-basic-tests/m3.scxml" # failed: transitioning to C not B on e1
basic/basic0.scxml" # passed
basic/basic1.scxml" # passed
basic/basic2.scxml" # passed
cond-js/test0.scxml" # passed
cond-js/test1.scxml" # passed
cond-js/test2.scxml" # passed
cond-js/TestConditionalTransition.scxml" # failed: taking transition to last on t5
default-initial-state/initial1.scxml" # passed
default-initial-state/initial2.scxml" # passed
default-initial-state/initial3.scxml" # passed
delayedSend/send1.scxml" # won't support: stable config is c not b
delayedSend/send2.scxml" # won't support: stable config is c not b
delayedSend/send3.scxml" # won't support: stable config is c not b
documentOrder/documentOrder0.scxml" # passed
foreach/test1.scxml" # passed
hierarchy/hier0.scxml" # passed
hierarchy/hier1.scxml" # failed: taking transition to b not a2
hierarchy/hier2.scxml" # failed: taking transition to a2 not b
hierarchy+documentOrder/test0.scxml" # failed: taking transition to b not a2
hierarchy+documentOrder/test1.scxml" # failed: taking transition to a2 not b
history/history0.scxml" # passed
history/history1.scxml" # passed
history/history2.scxml" # passed
history/history3.scxml" # passed
history/history4.scxml" # invalid configuration: see mail to w3c list
history/history5.scxml" # passed
history/history6.scxml" # passed
if-else/test0.scxml" # failed: we enter state b with a === 11
in/TestInPredicate.scxml" # passed
more-parallel/test0.scxml" # invalid configuration: see mail to w3c list
more-parallel/test1.scxml" # invalid configuration
more-parallel/test2.scxml" # invalid configuration
more-parallel/test3.scxml" # invalid configuration
more-parallel/test4.scxml" # passed
more-parallel/test5.scxml" # passed
more-parallel/test6.scxml" # invalid configuration
more-parallel/test7.scxml" # passed
more-parallel/test8.scxml" # passed
more-parallel/test9.scxml" # passed
multiple-events-per-transition/test1.scxml" # passed
parallel/test0.scxml" # passed
parallel/test1.scxml" # passed
parallel/test2.scxml" # passed
parallel/test3.scxml" # passed
parallel+interrupt/test0.scxml" # invalid configuration
parallel+interrupt/test1.scxml" # invalid configuration
parallel+interrupt/test10.scxml" # passed
parallel+interrupt/test11.scxml" # invalid configuration
parallel+interrupt/test12.scxml" # invalid configuration
parallel+interrupt/test13.scxml" # failed: transitioning to d not {c1, c2} on t
parallel+interrupt/test14.scxml" # invalid configuration
parallel+interrupt/test15.scxml" # invalid configuration
parallel+interrupt/test16.scxml" # invalid configuration
parallel+interrupt/test17.scxml" # invalid configuration
parallel+interrupt/test18.scxml" # failed: transitioning to a1 not a2
parallel+interrupt/test19.scxml" # failed
parallel+interrupt/test2.scxml" # failed
parallel+interrupt/test20.scxml" # failed
parallel+interrupt/test21.scxml" # failed
parallel+interrupt/test22.scxml" # failed
parallel+interrupt/test23.scxml" # failed
parallel+interrupt/test24.scxml" # failed
parallel+interrupt/test25.scxml" # failed
parallel+interrupt/test26.scxml" # failed
parallel+interrupt/test27.scxml" # failed
parallel+interrupt/test28.scxml" # failed
parallel+interrupt/test29.scxml" # failed
parallel+interrupt/test3.scxml" # failed
parallel+interrupt/test30.scxml" # failed
parallel+interrupt/test31.scxml" # failed
parallel+interrupt/test4.scxml" # failed
parallel+interrupt/test5.scxml" # failed
parallel+interrupt/test6.scxml" # failed
parallel+interrupt/test7.scxml" # failed
parallel+interrupt/test8.scxml" # failed
parallel+interrupt/test9.scxml" # failed
script/test0.scxml" # getData not defined
script/test1.scxml" # getData not defined
script/test2.scxml" # getData not defined
script-src/test0.scxml" # getData not defined
script-src/test1.scxml" # getData not defined
script-src/test2.scxml" # getData not defined
script-src/test3.scxml" # getData not defined
scxml-prefix-event-name-matching/star0.scxml" # passed
scxml-prefix-event-name-matching/test0.scxml" # passed
scxml-prefix-event-name-matching/test1.scxml" # passed
send-data/send1.scxml" # failed: typing issue with ===
send-internal/test0.scxml" # failed: typing issue with ===
targetless-transition/test0.scxml" # passed
targetless-transition/test1.scxml" # passed
targetless-transition/test2.scxml" # failed
targetless-transition/test3.scxml" # failed
On Feb 8, 2013, at 2:37 PM, Jacob Beard <jbeard4@cs.mcgill.ca<mailto:jbeard4@cs.mcgill.ca>> wrote:
Hi Stefan,
Thanks for your comments. It's nice to know that it's possible for other SCXML implementations to use the scxml-test-framework test client and protocol.
One aspect of the protocol which might not be clear is that it is that it tests the basic configuration of a state machine. A "basic configuration" is defined by Harel as follows:
It follows that configurations are “closed upwards”; that is, when the system is in any state A, it must also be in A’s parent state (unless, of course, A is the root, in which case it has no parent). In fact, to uniquely determine a configuration it is sufficient to know its basic states. Consequently, we use the term basic configuration to refer to a maximal set of basic states that the system can be in simultaneously, or in other words, the set of basic states in a legal configuration. [1]
Because the configuration, containing the set of ancestors of a basic state, can be derived from the basic configuration, it is sufficient simply to specify the expected basic configuration in the test cases. This does not imply that the configuration is expected to contain only the basic states specified, and not its ancestors, which, as you have mentioned, would be illegal in SCXML.
This is actually mentioned in the scxml-test-framework's README:
Note that the "initialConfiguration" and "nextConfiguration" properties should only contain the ids of expected basic states, which is to say "initialConfiguration" and "nextConfiguration" specify a "basic configuration", or a configuration of basic states. As a "full configuration", or a configuration composed of both basic and non-basic states, can be derived from a basic configuration, specifying only basic configurations in the test script can be done without leading to a loss of safety or generality. [2]
Note that this method of testing is not dependent on SCION semantics, but should be applicable to SCXML/Statecharts implementations in general.
With that in mind, assuming you have a way of querying the basic configuration from uscxml, you should be able to re-run the test suite. I'd be curious to know what passes and what doesn't, which is to say, how divergent our implementations might be.
If you have any questions, please don't hesitate to ask. Best,
Jake
[1] http://inst.eecs.berkeley.edu/~ee249/fa07/discussions/p293-harel.pdf
[2] https://github.com/jbeard4/scxml-test-framework#json-test-script
On Fri, Feb 8, 2013 at 7:36 AM, Stefan Radomski <radomski@tk.informatik.tu-darmstadt.de<mailto:radomski@tk.informatik.tu-darmstadt.de>> wrote:
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
Stefan
[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:
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<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 Saturday, 9 February 2013 23:08:34 UTC