My experience and issues implementing an SCXML Interpreter

I have created a 90%-working SCXML interpreter written in the Ruby programming language. Following are notes I kept during implementation about confusions/bugs/issues I ran into. Hopefully some of these can be used to improve a future draft of the standard. I couldn't decide if I should start one thread per item or not, so I took the lazy route and have included them all numbered below. Please feel free to fork the discussion into more targeted points with changed subjects as appropriate.

Note that several of the items below are not just recommendations for change, but also personal requests for clarification. I would greatly appreciate direct responses for items 8 and 12-16 below.

1. The Predicates section of Appendix A and some prose mentions "entryOrder", but the only location where this is used in the pseudo-code it is used as "enterOrder".

2. Appendix A uses isDescendant(a,b) in many locations, but never defines: is it testing that a is a descendant of b, or that b is a descendant of a? Without specifying any implementation, a note would be helpful describing this function directly (and any other function where the spec authors assumed that the function/procedure title was self-evident.)

3. Prose in various sections of Appendix A uses the word "proper" as in "proper ancestors" and "proper descendants", but the meaning of this phrase is never made clear. What is an improper ancestor? :) Why is this word used at all? (My eventual conclusion was that it meant that the starting element cannot be considered part of its "ancestors" or "descendants", but I don't know if this is correct or not.)

4. There exists a pseudo-code function "initializeDatamodel" that is used in two ways: initializeDatamodel(datamodel, doc) and initializeDataModel(datamodel.s,doc.s). I believe the former means "initialize the data model with respect to all states in the document" and the latter is "initialize the datamodel just for this state", but the parameters make little sense to me for the second. A comment or aside description would be welcome.

5. (very minor) Is there a compelling reason to differentiate "procedures" versus "functions" in the pseudo-code?

6. The Datatypes section in Appendix A describes the interface for List as having "function tail()      // Returns the tail of the list". The interpreter details makes it appear that the "tail" here is not the last element, but rather all except the head/first element. This comment should be clear about this.

7. Appendix A mentions that there is a global variable "historyValue", and uses it as an associative hash throughout the code, but no code ever initializes this variable or sets its type. Presumably this should be set during the "interpret" procedure to a data type not listed in the Datatypes preamble.

8. The function getChildStates() is used throughout the algorithm without definition. I cannot tell if this function is intended to return only "proper" states or also pseudo-state children. Please clarify both in email and the spec.

9. The mainEventLoop includes the code "for inv in state.invoke: inv.invoke(inv)". Why is is this written as an object-oriented method invocation that takes the receiver as a parameter? I suggest this should either be "invoke(inv)" or "inv.invoke()".

10. The specs do not explain the semantics of a "continue" statement during a "while" loop. Presumably this exits the loop at the current location and resumes at the top of the loop, as in "continue" in JavaScript, the "next" statement of Ruby, or a manual "goto" statement in Lua. It would be nice if the spec were clear about this.

11. Various "if" statements in the pseudo code have two colons at the end of the line, while others have only one colon. I'm assuming that the double-colons are typos and not indicative of some subtle behavioral change.

12. The preemptsTransition function is confusing. It is used in exactly one spot in the code, passing the variables "(t2, t)". However, the signature of the function is written with swapped parameters, "(t1, t2)". But then, the body of the function uses the variables "t" and "t2". Not only is this broken, but it casts serious doubt on which transition is supposed to preempt the other. Please clarify this via email and fix the spec.

13. I find the Type1/Type2/Type3 confusing for transitions. First, <transition> elements already have a "type" attribute that is unrelated; a better term (Category?) should be used. Secondly, the prose descriptions for both Type 2 and Type 3 do not seem rigorous. What is a "transition within a single child of <parallel>"? A transition that is in a state that is the sole child of a parallel? A single transition that is a direct child of a <parallel> node? Please revisit the preemptsTransition description and pseudo-code to make this subtle area for bugs robust and clear.

14. Section C.2.1 shows invalid SCXML in the example; not only is the <scxml> element missing the xmlns, but the "CEO" element has incorrectly escaped the XML attribute values.

15. Example G.3 includes (excerpted heavily) the markup: <state id="engine"><transition target="off"/><state id="off">…</state></state>. It would appear that every step of evaluation an engine that is in state "engine" should transition to "off"; as this is a substate of "engine", this is an endless loop. (In my likely-flawed implementation it certainly results in an infinite loop as the machine never gets to "stable=true".) Is this transition intended to be wrapped in an <initial> element instead? Or have I misunderstood and mis-implemented how the intepreter should handle such a situation?

16. I could not discern what should occur for a machine whose content is a single <scxml> element with no state children. While so trivial as to be almost useless (except for unit tests that are testing the datamodel), this appears to be a legal state machine. However, given that this <scxml> element lacks an initial attribute or element (it s an atomic state, after all), the pseudo-code for interpret: "executeTransitionContent([doc.initial.transition] enterStates([doc.initial.transition])" is in error (there is no doc.initial). Guarding against this prevents the <scxml> state from ever being entered into the configuration, leaving the state machine in a null state.

17. In general, I strongly echo the request for a set of SCXML examples, example event input and the configurations and log output that should come from each. These would ideally range from the simple to (eventually) tests that exercise all aspects of the interpretation algorithm. But do not let the "perfect" be the enemy of the "good": any examples (and their expected behavior in the presence of a series of events) would be a boon.

The current situation is a large set of interconnected rules described over (and cross-linked throughout) 20+ pages coupled with normative pseudo-code that can't actually be run and that has bugs that would prevent it from compiling/parsing if it were real code. Making the pseudo-code robust would be a nice step. Providing a normative reference implementation that can actually run (in ECMAScript, perhaps?) would be even better.


To cap off all the complaining and mistakes, I'd like to thank everyone who has worked on this standard. By and large it is well-written and helpful. As one who writes standards and specifications for his job often, I appreciate that while mistakes and bugs will happen, a considerable amount of passionate effort appears to have been applied over the years. :)

--
Gavin Kistner
Product Designer
NVIDIA, Inc.

Received on Thursday, 24 January 2013 23:44:53 UTC