SCION vs. SCXML Comparison
This document describes the similarities and differences between the semantics of SCION, and those of the "Algorithm for SCXML Interpretation" described in the SCXML draft specification. This document is targeted at developers already familiar with the "Algorithm for SCXML Interpretation", and who are interested in using SCION. Because this document is primarily targeted at developers familiar with the SCXML specification, the terminology used here will primarily be based on that of the SCXML specification, however some terminology from other papers will also be referred to.
All references to the "Algorithm for SCXML Interpretation" in this document are based on the seventh Public Working Draft of SCXML, published on 13 May 2010.
There were a number of reasons to create a semantics different from those specified in the "Algorithm for SCXML Interpretation". The first is that the "Algorithm for SCXML Interpretation" contained a serious bug regarding the execution of parallel states, such that the algorithm would cause the state machine interpreter to transition to illegal configurations for certain simple cases. It appeared as though this bug was not new, and had existed through several iterations of the specification, and it was uncertain whether and how the algorithm was being verified for correctness. Furthermore, the "Algorithm for SCXML Interpretation" diverged in unusual ways from the semantics of Statecharts defined in both "The Statemate Semantics of Statecharts" and "The Rhapsody Semantics of Statecharts" by David Harel, the creator of Statecharts. The motivation for these divergences was not always clear, and the fact that the W3C SCXML working group minutes were not publicly available made these choices difficult to investigate.
For these reasons, I felt that it would be better to base the semantics of SCION on a strong theoretical foundation, and reuse well-known scholarly work on Statecharts semantics. I thus chose to base SCION semantics on the paper "Big-Step Semantics", by Shahram Esmaeilsabzali, Nancy A. Day, Joanne M. Atlee, and Jianwei Niu. "Big-Step Semantics" describes eight semantic aspects that may be used to characterize the semantics of a Statecharts-like language. This allowed me to take the features of the "Algorithm for SCXML Interpretation" which I liked, and felt would be most salient to user interface developers, and ensure that other decisions regarding Statecharts semantic would also be well-founded.
Overall, I wanted the semantics of SCION to be well-defined with respect to the semantics described by "Big-Step Semantics", but to also be maximally intuitive for developers. There were many ideas in the "Algorithm for SCXML Interpretation" which I saw as being developer-friendly, and which were thus incorporated into the semantics of SCION. In general, SCION can be said to adhere to the general principles of Encapsulation, Causality, Determinism, Completeness, Run-to-completion, and Termination, as defined in "Algorithm for SCXML Interpretation". Specifically, some of the similarities between the "Algorithm for SCXML Interpretation" and SCION are as follows.
SCION adheres to run-to-completion semantics, where the system, when given an external event, will take multiple transitions, until it reaches a point where it is no longer possible to enable any further transitions.
SCION explicitly defines the order in which actions are executed when multiple transitions are enabled in the same microstep. The notion of using XML document order to define a total ordering on execution of transitions and entry and exit actions, and thus implicitly encode transition priority and eliminate non-determinism, seemed like an elegant and intuitive approach.
In SCION, the source state of a transition is also used to resolve conflicts when multiple transitions are activated, such that transitions originating from deeper in the state machine hierarchy have higher priority than their ancestors. This approach is similar to the notion of inheritance in Object-Oriented programming, in which a sub-class is able to override methods on the parent class, and I thus felt this notion would be most intuitive to developers.
Finally, I liked the idea of using JavaScript, a general-purpose scripting language, as the action language in actions and guards of the state machine. This seemed well-aligned with the vision for SCION as being well-suited for developing user interfaces on the Web.
The "Event Lifeline" can be described as the question of when an internal event generated by SCXML <send> can be sensed by the state machine and used to trigger transitions.
For the purposes of this paper, the terms "big-step"/"macrostep", and "small-step"/"microstep", should be considered synonyms. The terms "macrostep" and "microstep" will be preferred, as they are used in the SCXML specification, but "big-step" and "small-step" will be used in the titles of the semantic choices, as these are taken directly from "Big-Step Semantics".
In SCXML semantics, exactly one event can be sensed at a time; if multiple send actions are triggered in a single microstep, then each of those send actions will add their event to the inner event queue. At the end of each microstep, an event is dequeued from the internal event queue, and this event is sensed in the next microstep. This continues until there are no longer any transitions enabled.
In "Big-Step Semantics", a set of events may be sensed in a single microstep. Four semantic choices are possible for this:
- Whole: a generated event
- is considered present from the beginning of the current macrostep, regardless of the microstep in which it has been generated; and
- persists until the end of the macrostep
- Remainder: a generated event:
- is considered present in the intermediate snapshot after the microstep that generates it, and
- persists during the remainder of the macrostep
- Next small-step: a generated event is present only for the next microstep
- Same: a generated event is present during the current microstep
I felt that the "next small-step" semantic choice would be most intuitive for developers. This means that if multiple send actions are fired in a single microstep, the events from both will be added to a single event set, potentially containing multiple individual events, which will be dequeued and sensed in the next microstep. This will continue until a macrostep occurs which does not enable any transitions.
Because a set of events can be sensed in a microstep, rather than a single active event, the scripting interface to events must likewise be revised. The _event object available to SCXML action code is instead called _events, and contains a JavaScript array of event objects. Even though _events is exposed as an array, which is ordered, the order of events in the array is arbitrary and not meaningful. Individual events can be accessed by indexing into the array.
For convenience, and in order to provide a more familiar interface to SCXML developers, _events[0] is aliased to _event, which is also available to the scripting context.
Consider the following example, which both SCION and the SCXML step algorithm should interpret the same.
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
id="root">
<initial id="intitial1">
<transition target="a"/>
</initial>
<state id="a">
<transition target="b" event="t">
</transition>
</state>
<state id="b">
<onentry>
<send event="s"/>
</onentry>
<transition target="c" event="s"/>
<transition target="f1"/>
</state>
<state id="c">
<transition target="f2" event="s"/>
<transition target="d"/>
</state>
<state id="f1">
</state>
<state id="d">
</state>
<state id="f2">
</state>
</scxml>The statechart begins in initial state a. Upon receiving event t, the statechart transitions to state b, which on entry sends event s. The microstep then ends, and the next microstep begins. The event s, triggered in the previous microstep, is sensed and the statechart transitions to state c, ignoring the default transition to state f1. The current microstep then ends, and the next microstep begins. The event s can no longer be sensed, and so the default transition to state d is then taken.
Now consider the following example, which SCXML and SCION would interpret differently.
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
id="root">
<initial id="intitial1">
<transition target="a"/>
</initial>
<state id="a">
<transition target="b" event="t">
</transition>
</state>
<state id="b">
<onentry>
<send event="s"/>
<send event="r"/>
</onentry>
<transition target="c" event="s"/>
<transition target="f1"/>
</state>
<state id="c">
<transition target="f2" event="r"/>
<transition target="d"/>
</state>
<state id="f1">
</state>
<state id="d">
</state>
<state id="f2">
</state>
</scxml>
The statechart begins in initial state a. Upon receiving event t, the statechart transitions to state b, which on entry sends events s and r. The microstep then ends, and the next microstep begins. In SCION, events s and r could now be sensed; in SCXML, only event s could be sensed. In both SCION and SCXML, the event s, triggered in the previous microstep, would be sensed, and the statechart would transition to state c, ignoring the default transition to state f1. The current microstep then ends, and the next microstep begins. In SCION semantics, the event set containing s and r would already have been dequeued, so no events would be available to be sensed; the default transition would then be taken to state d. In SCXML, the event r would be dequeued, and the transition to state f2 would instead be taken.
"Memory protocol" refers to the question of how to obtain the value of a variable in the statechart datamodel when it is accessed in a JavaScript expression.
In the "Algorithm for SCXML Interpretation", variables in the datamodel can be assigned via <assign> tags, or via JavaScript assignment statements in action code. Assignment is performed synchronously, in the same microstep.
"Big-Step Semantics" describes two choices to assign values to variables in the statecharts datamodel:
- "Big-step", where variables stay the same throughout the macrostep, and are updated at the end of the macrostep.
- "Small-step", where variables stay the same throughout the microstep, and are updated at the end of the microstep.
Neither of these choices allow the kind of synchronous assignment that one finds in a typical procedural programming language. One consequence of this "double-buffering" of variables is additional overhead to the interpreter runtime, and more difficulty integrating these concepts with a general-purpose embedded scripting language. Furthermore, I feel that both of these choices are likely to be somewhat suprising and less intuitive to many web developers. Finally, the ability to enforce these semantics is limited in the browser environment (to my knowledge, there does not exist a general mechanism to sandbox arbitrary JavaScript assignments in the browser environment, and thus the developers would be able to side-step Memory Protocol semantics simply by assigning to global variables that are not declared in the datamodel).
For that reason, SCION supports both synchronous assignment, such that assignment actions are detected in the same microstep, and optional "small-step" memory protocol semantics, in which assignment to variables in the datamodel are detected in the next microstep. This is managed as follows:
-
In JavaScript action code, JavaScript assignment statements uses ordinary JavaScript semantics to perform synchronous assignments to variables in the datamodel. This means that the datamodel will be updated immediately, after the statement executes, and these changes to the datamodel will be detectable in the same microstep.
-
Assignment performed by the
<assign>tag uses ordinary JavaScript semantics as well. -
To use "next small-step" semantics, a getter and setter API is provided in JavaScript action code:
setData(variableName,value)getData(variableName)
Consider the following example:
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
initial="a">
<datamodel>
<data id="foo" expr="0"/>
</datamode>
<state id="a">
<transition target="b" event="t">
<assign location="foo" expr="foo + 1"/>
<assign location="foo" expr="foo - 1"/>
</transition>
</state>
<state id="b">
<transition target="c">
<assign location="foo" expr="foo + 1"/>
<assign location="foo" expr="foo - 1"/>
</transition>
</state>
<state id="c"/>
</scxml>In this example, when the statechart is started, datamodel variable foo would be initialized to value 0, and the statechart would begin in initial state a. Upon receiving event t, the statechart will transition to state b, and the transition <assign> actions would be executed in document order. foo will be updated synchronously. This means that in the first <assign>, foo + 1, will assign the value 0 + 1 = 1 to variable foo. In the second assign, foo - 1, will assign the value 1 - 1 = 0 to foo. The same would be repeated in the next microstep, in the default transition from state b to state c. Thus, foo would end with value 0.
The above example is equivalent to the following:
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
initial="a">
<datamodel>
<data id="foo" expr="0"/>
</datamode>
<state id="a">
<transition target="b" event="t">
<script>
foo = foo + 1;
foo = foo - 1;
</script>
</transition>
</state>
<state id="b">
<transition target="c">
<script>
foo = foo + 1;
foo = foo - 1;
</script>
</transition>
</state>
<state id="c"/>
</scxml>The following is an example of the way "next small-step" assignment may be used in SCION:
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
initial="a">
<datamodel>
<data id="foo" expr="0"/>
</datamode>
<state id="a">
<transition target="b" event="t">
<script>
setData('foo',getData('foo') + 1);
setData('foo',getData('foo') - 1);
</script>
</transition>
</state>
<state id="b">
<transition target="c">
<script>
setData('foo',getData('foo') + 1);
setData('foo',getData('foo') - 1);
</script>
</transition>
</state>
<state id="c"/>
</scxml>Like the first two examples, the statechart will begin in state a, variable foo will be initialized to value 0, and upon receiving event t, the statechart will transition to state b. Because the value of foo is only updated at the end of the microstep, the value of variable foo in the expr attribute of both assign actions in this transition will resolve to value 0. Because, the assign action with expression foo - 1 is executed after the assign action with expression foo + 1, at the end of the microstep foo will be assigned the value foo - 1 = 0 - 1 = -1. The statechart would end the microstep in state b. The next microstep would then begin, and the default transition to state c would then be taken. The same actions would be performed, and so at the end of the microstep, variable foo would be updated to value foo - 1 = -1 - 1 = -2.
The following is an example of how "next small-step" assignment semantics would work in a parallel state:
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
initial="a">
<datamodel>
<data id="foo" expr="0"/>
</datamode>
<parallel id="a">
<state id="b">
<onexit>
<script>
setData('foo',getData('foo') + 1);
</script>
</onexit>
</state>
<state id="c">
<onexit>
<script>
setData('foo',getData('foo') - 1);
</script>
</onexit>
</state>
<transition target="d" event="t"/>
</parallel>
<state id="d"/>
</scxml>In this example, the state machine would begin in parallel state a and basic states b and c, and variable foo would be initialized to value 0. Upon receiving event t, the statechart would transition to state d. This would trigger the onexit assign actions of both states b and c. These script actions would be executed in document order, which means that the assign action originating in state b would be executed before that originating in state c. Expression foo - 1 is thus evaluated after foo + 1. Because these assignments take place within the same small step, foo - 1 will resolve foo to have the value it had at the beginning of the microstep, which is value 0. Thus, foo would be assigned foo - 1 = 0 - 1 = -1 for the next microstep.
The scope in which action code is executed is not explicitly specified in the "Algorithm for SCXML Interpretation".
In SCION, top-level script elements (those that are children of the root element) are evaluated in a scope which is local each SCXML document instance. In this way local variables, including functions, may be defined by the SCXML model, which are visible to all action code that will be executed.
All other action code is evaluated in a restricted scope. Local variables getData, setData, _events, _event, and In, as defined in this document and the SCXML specification, are available as local variables to the evaluating script context. Furthermore, datamodel variables are available as local variables, so that they can be assigned to directly, without declaring global variables.
The following simplified example is from here.
<html xmlns="http://www.w3.org/1999/xhtml" xmlns:svg="http://www.w3.org/2000/svg">
<head></head>
<body>
<svg xmlns="http://www.w3.org/2000/svg"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:scion="https://github.com/jbeard4/SCION" width="100%" height="99%" >
<rect width="100" height="100" stroke="black" fill="red" id="rectToTranslate" >
<scxml
xmlns="http://www.w3.org/2005/07/scxml"
version="1.0"
profile="ecmascript"
id="scxmlRoot"
initial="idle">
<script>
function computeTDelta(oldEvent,newEvent){
//summary:computes the offset between two events; to be later
//used with this.translate
var dx = newEvent.clientX - oldEvent.clientX;
var dy = newEvent.clientY - oldEvent.clientY;
return {'dx':dx,'dy':dy};
}
function translate(rawNode,tDelta){
var tl = rawNode.transform.baseVal;
var t = tl.numberOfItems ?
tl.getItem(0) :
rawNode.ownerSVGElement.createSVGTransform();
var m = t.matrix;
var newM = rawNode.ownerSVGElement.
createSVGMatrix().
translate(tDelta.dx,tDelta.dy).multiply(m);
t.setMatrix(newM);
tl.initialize(t);
return newM;
}
</script>
<datamodel>
<data id="firstEvent"/>
<data id="eventStamp"/>
<data id="tDelta"/>
</datamodel>
<state id="idle">
<transition event="mousedown" target="dragging">
<assign location="firstEvent" expr="_event.data"/>
<assign location="eventStamp" expr="_event.data"/>
</transition>
</state>
<state id="dragging">
<transition event="mouseup" target="idle"/>
<transition event="mousemove" target="dragging">
<script>
tDelta = computeTDelta(eventStamp,_event.data);
translate(this,tDelta);
</script>
<assign location="eventStamp" expr="_event.data"/>
</transition>
</state>
</scxml>
</rect>
</svg>
</body>
</html>In this example, functions computeTDelta and translate would be declared in the global scope.
Datamodel variables firstEvent, eventStamp, and tDelta, as well as the event variable _event, would only be available as local variables in the restricted context in which action code is evaluated. Datamodel variables may be assign to directly, as is done in the JavaScript statement tDelta = computeTDelta(eventStamp,_event.data);.