B Algorithm for SCXML
Interpretation
This section presents a normative algorithm for the
interpretation of an SCXML document. 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.
The fact that SCXML implements a variant of the Statechart
formalism does not as such determine a semantics for SCXML. Many
different Statechart variants have been proposed, each with its own
semantics. This section presents an informal semantics of SCXML
documents, as well as a normative algorithm for the interpretation
of SCXML documents.
Informal Semantics
The following definitions and highlevel principles and
constraint are intended to provide a background to the normative
algorithm, and to serve as a guide for the proper understanding of
it.
Preliminary definitions
- state
- An element of type <state>, <parallel>,
<final> or <scxml>.
- pseudo state
- An element of type <initial> or <history>.
- transition target
- A state, or an element of type <history>.
- atomic state
- A state of type <state> with no child states, or a state
of type <final>.
- compound state
- A state of type <state> with at least one child state, or
a state of type <scxml>.
- start state
- A dummy state equipped with a transition which when triggered
by the Run event leads to the initial state(s). Added by the
interpreter with an id guaranteed to be unique within the
statemachine. The only role of the start state is to
simplify the algorithm.
- configuration
- The maximal consistent set of states (including parallel and
final states) that the machine is currently in. We note that if a
state s is
in the configuration c, it is always the
case that the parent of s (if any) is also
in c. Note, however, that <scxml> is not a(n
explicit) member of the configuration.
- source state
- The source state of a transition is the atomic state from which
the transition is leaving.
- target state
- A target state of a transition is a state that the transition
is entering. Note that a transition can have zero or more target
states.
- targetless transition
- A transition having zero target states.
- eventless transition
- A transition lacking the 'event' attribute.
- external event
- An SCXML event appearing
in the external event
queue. See section ? for details.
- internal event
- An event appearing
in the internal event queue.
It's exact representation is implementation dependent, but a simple
string would work.
- macrostep
- An external event causes an SCXML state machine to take exactly
one macrostep. A macrostep consists of a sequence (a chain) of
microsteps. However, if the external event does not enable any
transitions, no microstep will be taken, and the corresponding
macrostep will be empty.
- microstep
- If an external event enables one or (in the
case
of parallel states) more transitions, a microstep is taken,
involving the processing of each of the enabled transitions. This
microstep may change the the current configuration, update the
datamodel and/or generate new (internal and/or
external) events. This, by causality, may in turn
enable additional transitions which will be handled in
the next microstep in the sequence, and so on.
Principles and Constraints
We state here some principles and constraints, on the level of
semantics, that SCXML adheres to:
- Encapsulation
- An SCXML processor is a pure event processor. The only
way to get data into an SCXML statemachine is to send external
events to it. The only way to get data out is to receive events
from it.
- Causality
- There shall be a causal justification of why events
are (or are not) returned back to the environment, which can be
traced back to the events provided by the system environment.
- Determinism
- An SCXML statemachine which does not invoke any external event
processor must always react with the same behavior (i.e. the same
sequence of output events) to a given sequence of input events
(unless, of course, the statemachine is explicitly programmed to
exhibit an non-deterministic behavior). In particular, the
availability of the <parallel> element must not introduce any
non-determinism of the kind often associated with concurrency. Note
that observable determinism does not necessarily hold for state
machines that invoke other event processors.
- Completeness
- An SCXML interpreter must always treat an SCXML document as
completely specifying the behavior of a statemachine. In
particular, SCXML is designed to use priorities (based on document
order) to resolve situations which other statemachine frameworks
would allow to remain under-specified (and thus non-deterministic,
although
in a different sense from the above).
- Run to completion
- SCXML adheres to a run to completion semantics
in
the sense that an external event can only be processed when the
processing of the previous external event has completed, i.e. when
all microsteps (involving all triggered transitions) have been
completely taken.
- Termination
- A microstep always terminates. A macrostep may not. A macrostep
that does not terminate may be said to consist of an infinitely
long sequence of microsteps. This is currently allowed.
Algorithm
This section presents a normative algorithm for the
interpretation of SCXML documents. 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.
Datatypes
These are the abstract datatypes that are used in
the algorithm.
datatype List
function head() // Returns the head of the list
function tail() // Returns the tail of the list
function append(l) // Returns the list appended with l
function filter(f) // Returns the list of elements that satisfy the predicate f
function some(f) // Returns true if some element in the list satisfies the predicate f
function every(f) // Returns true if every element in the list satisfies the predicate f
datatype Set
procedure add(e) // Adds e to the set
procedure delete(e) // Deletes e from the set
function member(e) // Is e a member of set?
function isEmpty() // Is the set empty?
function toList() // Converts the set to a list
datatype Queue
procedure enqueue(e) // Puts e last in the queue
function dequeue() // Removes and returns first element in queue
function isEmpty() // Is the queue empty?
datatype BlockingQueue
procedure enqueue(e) // Puts e last in the queue
function dequeue() // Removes and returns first element in queue, blocks if queue is empty
Global variables
The following variables are global from the point of view of the
algorithm. Their values will be set in the procedure
interpret().
global datamodel;
global configuration;
global internalQueue;
global externalQueue;
global historyValue;
global continue
Procedures and Functions
This section defines the procedures and functions that make up
the core of the SCXML interpreter.
procedure interpret(scxml,id)
The purpose of this procedure is to initialize the interpreter.
It is called with a parsed representation of an SCXML document.
In order to interpret an SCXML document, first perform inplace
expansions of states by including SCXML source referenced by URIs
(see 3.11 Referencing External Files)
and change initial attributes to initial container children with
empty transitions to the state from the attribute. Then
(optionally) validate the resulting SCXML, and throw an exception
if validation fails. Create an empty configuration complete with a
new populated instance of the data model and a execute the global
scripts. Create the two queues to handle events and set the global
continue variable to true. Call executeTransitionContent on the
initial transition that is a child of scxml. Then call enterState
on the initial transition. Finally, start the interpreter's event
loop.
procedure interpret(doc):
expandScxmlSource(doc)
if (!valid(doc)) {fail with error}
configuration = new Set()
datamodel = new Datamodel(doc)
executeGlobalScriptElements(doc)
internalQueue = new Queue()
externalQueue = new BlockingQueue()
continue = true
executeTransitionContent([doc.initial.transition])
enterState([doc.initial.transition])
startEventLoop()
procedure startEventLoop()
The interpreter's event loop has two main parts. First it
selects enabled transitions. Then it executes the selected
transitions. It stays in a continuous loop of selecting and
executing transitions until the interpreter is finished. The
details of how it selects transitions are specified to achieve the
desired run to completion semantics and final processing.
The interpreter's event loop enforces the run to completion
semantics by only breaking at the end of handling all of the
microsteps associated with any given event. It accomplishes this by
each and every time through the loop enforcing an ordering on which
transitions are selected. First the interpreter checks to see if
there are any eventless transitions that need to be taken. If there
are any then they are executed by the microstep being performed and
the next iteration of the loop continues. If there were no
eventless transitions to execute then the internal event queue is
checked and if there is an internal event then transitions are
selected based on this event. If there were transitions selected
based on this event then these are executed by the microstep being
performed and the next iteration of the loop continues. If there
were no transitions enabled then we check if we have reached a
final state by checking if continue is true. If continue is false
the statemachine is done and we break out of the startEventLoop. If
continue is true then we grab an external event from the external
event queue, blocking if necessary. Once we have the external event
we perform the appropriate data model manipulation related to
finalizing the event and modifying the data model with the event
information. Finally we select transitions that were enabled by
this event. If there were transitions enabled by the event we
execute them by the microstep function and start the next iteration
of the loop. If there were no transitions selected by the external
event we also start the next iteration of the loop.
procedure procedure startEventLoop():
while (true):
enabledTransitions = selectTransitions(null)
if (enabledTransitions.isEmpty() && !internalQueue.isEmpty()):
enabledTransitions = selectTransitions(internalQueue.dequeue())
if (enabledTransitions.isEmpty()enabledTransitions.isEmpty() && !internalQueue.isEmpty():
if (continue):
ee = externalQueue.dequeue()
datamodel.assignID("event",ee)
enabledTransitions = selectTransitions(ee)
else:
break
if (!enabledTransitions.isEmpty()):
microstep(enabledTransitions.toList())
procedure exitInterpreter()
The purpose of this procedure is to exit the
current SCXML process by halting the interpreter's event loop. It
does so by setting the global variable continue to
false
procedure exitInterpreter():
continue = false
function selectTransitions(event)
The purpose of the selectTransitions()
procedure is to collect the transitions that are
enabled in a given configuration.
Create an empty set of enabledTransitions. For each
atomic state in the configuration, first test if the
state has been preempted by a transition that has already been
selected and that will cause the state to be exited when the
transition is taken. If the state has not been preempted, find a
transition whose 'event' attribute is either empty or matches
event and whose condition evaluates to
trueevent is
nullin document order. If none are present,
search in the state's ancestors in
ancestory order until one is found. As soon as such a transition is
found, add it to enabledTransitions, and proceed to
the next atomic state in the configuration. If no such
transition is found in the state or its ancestors,
proceed to the next state in the configuration. When
all atomic states have been visited and transitions selected,
return the set of enabled transitions.
function selectTransitions(event):
enabledTransitions = new Set()
atomicStates = configuration.toList().filter(isAtomicState)
for state in atomicStates:
if !(isPreempted(s, enabledTransitions)):
loop: for s in [state].append(getProperAncestors(state,null)):
for t in s.transition:
if ((event == null && t.attribute('event') == null && conditionMatch(t)) ||
(event != null && nameMatch(event,t) && conditionMatch(t))):
enabledTransitions.add(t)
break loop
return enabledTransitions
procedure isPreempted?(s transitionList)
Return true if a transition T in transitionList exits an
ancestor of state s. In this case, taking T will pull the state
machine out of s and we say that it preempts the selection of a
transition from s. Such preemption will occur only if s is a
descendant of a parallel region and T exits that region. If we did
not do this preemption check, we could end up in an illegal
configuration, namely one in which there were multiple active
states that were not all descendants of a common parallel
ancestor.
procedureisPreempted?(s transitionList):
boolean preempted = false
for t in transitionList:
if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
if (isDescendant(s,LCA)):
preempted = true
break;
return preempted
procedure microstep(enabledTransitions)
The purpose of the microstep procedure is to
process the set of transitions enabled by an external event, an
internal event, or by the presence or absence of certain values
in the datamodel at the current point in
time. The processing of the enabled transitions must be done
in parallel ('lock step') in the sense
that their source states must first be exited, then their actions
must be executed, and finally their target states entered.
procedure microstep(enabledTransitions):
exitStates(enabledTransitions)
executeTransitionContent(enabledTransitions)
enterStates(enabledTransitions)
procedure exitStates(enabledTransitions)
Create an empty statesToExit set. For each
transition t in
enabledTransitions, if t is targetless
then do nothing, else let LCA be the least common
ancestor state of the source state and target states of
t. Add to the statesToExit set all states
in the configuration that are descendants of
LCA. Convert the statesToExit set to a
list and sort it in exitOrder.
For each state s in the list, if
s has a deep history state h, set the
history value of h to be the list of all atomic
descendants of s that are members in the
current configuration, else set its value to be the list of all
immediate children of s that are members of the
current configuration. Again for each state s
in the list, first execute any onexit handlers, then
cancel any ongoing invocations, and finally remove s
from the current configuration.
procedure exitStates(enabledTransitions):
statesToExit = new Set()
for t in enabledTransitions:
if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
for s in configuration.toList():
if (isDescendant(s,LCA)):
statesToExit.add(s)
statesToExit = statesToExit.toList().sort(exitOrder)
for s in statesToExit:
for h in s.history:
f = (h.attribute('type') == "deep") ?
lambda(s0): isAtomicState(s0) && isDescendant(s0,s) :
lambda(s0): s0.parent() == s
historyValue[h.attribute('id')] = configuration.toList().filter(f)
for s in statesToExit:
for content in s.onexit:
executeContent(content)
for inv in s.invoke:
cancelInvoke(inv)
configuration.delete(s)
procedure executeTransitionContent(enabledTransitions)
For each transition in the list of
enabledTransitions, execute its executable
content.
procedure executeTransitions(enabledTransitions):
for t in enabledTransitions:
executeContent(t)
procedure enterStates(enabledTransitions)
Create an empty statesToEnter set, and an empty
statesForDefaultEntry set. For each transition
t in enabledTransitions, if
t is targetless then do nothing, else let
LCA be the least common ancestor state of the source
state and target states of t. For each target state
s, if s is a history state then add
either the history values associated with s or
s's default target to statesToEnter. Else
(if s is not a history state), add s to
statesToEnter. Convert statesToEnter to a
list and sort it in enterOrder.
For each state s in the list, first
add s to the current configuration, then invoke any
external processes specified in <invoke>
elements and assign their sessionIDs to the datamodel,
keyed on the <invoke> element's ID, then execute any onentry
handlers, and finally, if s is a final state, generate
relevant Done events. If we have reached a top-level
final state, exit the interpreter.
procedure enterStates(enabledTransitions):
statesToEnter = new Set()
statesForDefaultEntry = new Set()
for t in enabledTransitions:
if (t.attribute('target') != null):
LCA = findLCA([t.parent()].append(getTargetStates(t)))
for s in getTargetStates(t):
if (isHistoryState(s)):
if (historyValue[s.attribute('id')] != null):
for s0 in historyValue[s.attribute('id')]:
addStatesToEnter(s0,LCA,statesToEnter,statesForDefaultEntry)
else:
for s0 in getTargetStates(s.transition):
addStatesToEnter(s0,LCA,statesToEnter,statesForDefaultEntry)
else:
addStatesToEnter(s,LCA,statesToEnter,statesForDefaultEntry)
statesToEnte for anc in getProperAncestors(stateList.head(),null):
r = statesToEnter.toList().sort(enterOrder)
for s in statesToEnter:
configuration.add(s)
for inv in s.invoke:
sessionID = executeInvoke(inv)
datamodel.assignValue(inv.attribute('ID'),sessionID)
for content in s.onentry:
executeContent(content)
if (statesForDefaultEntry.member(s)):
executeContent(s.initial.transition.children())
if (isFinalState(s)):
parent = s.parent()
grandparent = parent.parent()
internalQueue.enqueue(parent.attribute('id') + ".Done")
if (isParallelState(grandparent)):
if (getChildStates(grandparent).every(isInFinalState)):
internalQueue.enqueue(grandparent.attribute('id') + ".Done")
for s in configuration.toList():
if (isFinalState(s) && isScxmlState(s.parent())):
exitInterpreter()
procedure addStatesToEnter(s,root,statesToEnter,statesForDefaultEntry)
The purpose of this procedure is to add to
statesToEnter all states that must be entered as a
result of entering state s. These include ancestors of
s, parallel siblings of s or its
ancestors, and s's default children, if s
is a parallel or compound state. Note that this
procedure permanently modifies both
statesToEnter and
statesForDefaultEntry.
First, add s to statesToEnter. Then,
if s is a parallel state, add each of s's
children to statesToEnter. Else, if s is
a compound state, add s to
statesForDefaultEntry and add its default initial
state to statesToEnter. Finally, for each ancestor
anc of s, add anc to
statesToEnter and if anc is a parallel
state, add the children of anc that does not have a
descendant on statesToEnter to
statesToEnter.
procedure addStatesToEnter(s,root,statesToEnter,statesForDefaultEntry):
statesToEnter.add(s)
if (isParallelState(s)):
for child in getChildStates(s):
addStatesToEnter(child,s,statesToEnter,statesForDefaultEntry)
elif (isCompoundState(s)):
statesForDefaultEntry.add(s)
addStatesToEnter(getDefaultInitialState(s),s,statesToEnter,statesForDefaultEntry)
for anc in getProperAncestors(s,root):
statesToEnter.add(anc)
if (isParallelState(anc)):
for pChild in getChildStates(anc):
if (!statesToEnter.toList().some(lambda(s): isDescendant(s,anc))):
addStatesToEnter(pChild,anc,statesToEnter,statesForDefaultEntry)
procedure isInFinalState(s)
Return trues is
a compound <state> and one of its children is a <final>
state and is a member of the configuration, or if s is
a <parallel> state and isInFinalState is
true of all its children.
function isInFinalState(s):
if (isCompoundState(s)):
return getChildStates(s).some(lambda(s): isFinalState(s) && configuration.member(s))
elif (isParallelState(s)):
return getChildStates(s).every(isInFinalState)
else:
return false
function findLCA(stateList)
Return the state s such that s is a
proper ancestor of all states on stateList and no
descendant of s has this property. Note that there is
guaranteed to be such a state since the <scxml> element
(which we treat as a state here) is a common ancestor of all
states. Note also that since we are speaking of proper ancestor
(parent or parent of a parent, etc.) the LCA is never a member of
stateList.
function findLCA(stateList):
for anc in getProperAncestors(stateList.head(),null):
if (stateList.tail().every(lambda(s): isDescendant(s,anc))):
return anc
B.1
Semantics of <anchor>
There are a number of ways of defining the semantics of
<anchor>. We choose the following because it shows that,
except for the rollback of the data model, <anchor> can be
viewed as a syntactic shortcut that does not extend the basic Harel
semantics. We emphasize that implementations are required only to
behave as if they assigned the following interpretation to
<anchor> and that simpler and more efficient implementations
are possible.
First, we add a special branch 'anchors' to the data model, with
a child for each anchor type defined in the document. Thus if the
document defines anchor types "foo" and "bar", the data model will
have paths 'anchors.foo' and 'anchors.bar'. Whenever the state
machine enters a state with an <anchor> element, it sets the
value of the corresponding anchor entry in the datamodel to the ID
of that state. Thus if a <state> with ID 'state27' defines an
<anchor> with 'type' "foo", whenever the state machine visits
this state, it sets 'anchors.foo; to 'state27'. Furthermore, the
state machine automatically adds the 'anchors' branch to the
snapshot specified in the <anchor> element.
Now any <transition> which specifies an 'anchor' is
replaced with a set of <transition>s, one for each
<state> that defines that <anchor>. Each of the
<transition>s takes as its 'target' one of the <state>s
that defines the <anchor>. Furthermore, an extra clause is
added to the 'cond' of the original <transition>, specifying
that the corresponding location in the data model match the target
<state>'s ID. Finally, a default transition is added
reentering the current <state>. For example, if the anchor
type "foo" is defined in <state>s 'state27' and 'state33',
then in <state> 'thisState', a transition with "event"
"someEvent", "cond" "someCond" and "anchor" 'foo' will be replaced
by three transitions, as shown below:
<transition event="someEvent" cond="someCond" anchor="foo"/>
is equivalent to
<transition event="someEvent" cond="datamodel.anchors.foo==state27 && someCond" target="state27"/>
<transition event="someEvent" cond="datamodel.anchors.foo==state33 && someCond" target="state33"/>
<transition event="someEvent" cond="someCond" target="state33"/> target="thisState"/>
At runtime when "someEvent" is raised and "someCond" is true, if
either state27 or state33 has been visited, 'datamodel.anchors.foo'
will have the corresponding stateID as its value and the
corresponding transition will be selected. The only complication is
that the transitions must retain the original 'anchor' attribute,
so that the datamodel must be rolled back to the snapshot specified
in the corresponding <anchor> element. Note that the
'anchors' branch must be automatically added to this snapshot, so
that it will be automatically rolled back as well. (This has the
effect of erasing any intermediate anchors that have been visited
since the target state was exited.) If neither state27 nor state33
has been visited, the third transition will be taken, causing the
state machine to exit and reenter 'thisState' without any rollback
of the datamodel.
