Re: Soliciting Comments from SCXML Users

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> 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> 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>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)****
>>
>
>
>