G An Overview of UML Notation and SCXML Semantics
This section will outline the most salient features of SCXML semantics, as well as the corresponding
UML notation. A future version of this document will define the semantics of SCXML in greater detail. Diagram 1 shows a simple state machine
with three states S1, S2, and S3.
G.1 A Simple State Machine
SCXML Equivalent
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<state id="S1">
<transition event="Event1" target="S2"/>
</state>
<state id="S2">
<transition event="Event2" cond="X>0" target="S1"/>
<transition event="Event2" cond ="X<0" target next="S3"/>
</state>
<state id="S3">
</state>
</scxml>
These states linked by transitions, which are triggered by events.
In this example State S1 transitions to state S2 when the event Event1 occurs. This is the only way the
system can move from S1 to S2, since it is the only transition between those two states. Any other
events that occur while the system is in S1 will therefore be ignored. The logic in S2
is slightly more complex. It has two transitions, both triggered by event Event2. Both transitions have
guard conditions that check the value of the variable X. If X < 0, S2 will transition to S3 when Event2 occurs.
If X > 0, it will transition back to S2. Note that there is no condition covering the case where X = 0. Therefore
the system will remain in state S2 if X = 0 when Event2 occurs. As in state S1, all events not mentioned in
transitions will be ignored.
G.2 Executing Actions On Entering And Exiting
OnEntry and OnExit handlers are a useful feature of Harel State Tables. They allow code to be embedded
in states that will be executed whenever the state is entered or exited. In Diagram 2
we see the same three states, but now S1 has an OnEntry handler that decrements X , while S2 has an OnExit handler
that also decrements X. S3 has both OnEntry and OnExit handlers, both of which increment X. Now suppose that X
has a current value of 2, and that the system enters S1. When it does so, X is decremented to 1.
When Event1 occurs, the system will transition to S2, as before. Now when Event2 occurs, X is equal to 1, so
the system will transition back to S1. As the system exits state S2, the OnExit handler will decrement X to 0.
Note that this happens after the transition is selected and the guard condition has been evaluated.
X. The entry into S1 decrements X again to -1. Now if Event1 occurs again and the system returns to S2, it will
transition to S3 when Event2 occurs, since X is now < 0. Leaving S2 will decrement X again, but entering
S3 will increment it, so X = -1 when the system is in S3. S3 has no transitions so the system will stay in S3
forever. However if a transition is added to S3, the OnExit handler in S3 will set Y to 0 when S3 is exited.
SCXML Equivalent
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<datamodel>
<data name="X" expr="2"/>
</datamodel>
<state id="S1">
<onentry>
<assign name="X" expr="X--"/>
</onentry>
<transition event="Event1" target="S2"/>
</state>
<state id="S2">
<transition event="Event2" cond= "X>0" target="S1"/>
<transition event="Event2" cond ="X><0" target="S3"/>
<onexit>
<assign name="X" expr="X--"/>
</onexit>
</state>
<state id="S3">
<onentry>
<assign name="X" expr="X++"/>
</onentry>
<onexit>
<assign name="Y" expr="0"/>
</onexit>
</state>
</scxml>
G.3 Complex States
Of particular interest is the concept of a complex state, namely one that has substates.
In Diagram 3 below, the State S1 now has two substates, labeled
S11 and S12.
SCXML Equivalent
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<state id="S1">
<state id="S11">
</state>
<state id="s12">
</state>
<initial>
<transition target next="S11"/>
</initial>
</state>
</scxml>
In this particular case, S1 has sequential substates. When a state machine is in a state with such
substates, it must also be in one and only one of the substates. The substates have a kind of "Or" semantics and
can be thought of as representing a decomposition of the parent state. A transition moving the system
to S1 may specify S11 or S12 as its "target" directly. However, to handle the case where it
doesn't, S1 contains an <initial> element defining the default substate that it will start
in if the transition simplify specifies S1 as its destination. In Diagram 3, the default substate is S11.
G.4 Parallel States
In addition to sequential substates, Harel State
Charts provide concurrent substates, which represent a form of "And" logic. When a
state machine is in a state with concurrent substates it must be simultaneously in each of the concurrent
child states. The concurrent child states operate independently until they all terminate (normally by reaching
terminal child states) at which point the parent state also terminates. Concurrent substates thus represent
fork and join logic. They are represented in our notation by the <parallel> tag. Diagram 4 below
represents an elaboration of Diagram 3. First of all, State S11 has been decomposed
into further sequential substates, S111 and S112, with S111 being the default initial state. Secondly, concurrent substates
S121, S122, and S123 have been added to State S12.
SCXML Equivalent
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<state id="S1">
<state id="S11">
<state id="S111"/>
<state id="S112"/>
<initial>
<transition target next="S111"/>
</initial>
</state>
<state id="s12">
<parallel>
<state id="S121"/>
<state id="S122"/>
<state id="S123"/>
</parallel>
</state>
<initial>
<transition target="S11"/>
</initial>
</state>
<state>
</state>
</scxml>
As Diagram 4 shows, the notion of complex state is fully recursive, so that
the child states of a complex parent may themselves have
sequential or concurrent children. Thus a complex state machine is not normally
in a single state, but in a configuration
of compatible states. Applying the rules for sequential and concurrent
states recursively in Diagram 4, we see that when the machine is in S1
it must also be in S11 or S12. When the machine is in S11,
it must be in S111 or S112. When the machine is in S12, on the other hand,
it must simultaneously be in all three substates S121,
S11 and S1123. Thus there are 3 legal configurations they machine can be in:
S1 plus S11 plus S111, S1 plus S11 plus S112, and S1 plus S12 plus S121, S122,
and S123.
G.5 Concurrency And Event Queues
The Harel semantics for transitions is based on the notion of an underlying event
queue. At any given point, the state machine is in a specific configuration of
states. If there is an event in the queue, it is processed according
to the given state configuration, and a transition may be triggered.
The transition is then taken and it and all actions associated with it are
executed before the next event in the queue is examined. Of particular interest
is the way that <onexit> and <onevent> handlers interact
with transitions. Suppose the machine is in state S2 (which is not shown in the
diagram) and an event occurs which
triggers a transition to state S112 in Diagram 4. In this case, the machine
first leaves S2, executing S2's <onexit>handlers. It then executes any
<actions> in the selected
transitions. Then it enters S1, S11, and S112 executing their <onentry>
handlers in that order. Only when all these actions have been executed will the
machine check its queue for another event. Suppose that there is an
event in the queue and it triggers a transition from S112 to S12. Going to S12
entails leaving both S112 and S11,
so both their <onexit> handlers fire in that order, before the
executable content in the transition.
(Note that the <onexit> handlers fire in the reverse order of the
<onentry> handlers.) Since
S11 and S12 are both substates of S1, this transition does not entail leaving
S1 so its <onexit> handler
does not fire. After the transition's <actions>, S12's
<onentry> handler will fire. Furthermore,
the semantics of parallel states requires that entering S12 also involves entering
each of its concurrent substates
simultaneously. Therefore the <onentry> handlers for S121, S122,
and S123 will all fire after the one
for S12. Since entry into the parallel substates is simultaneous, however,
there is no guarantee on the order in which the three substate handlers fire.
Complex state configurations also interact with the selection of the transition
to execute. First off, note that even a simple state may contain multiple
transitions that match a given event. For example State S1 may contain
two transitions, T1 which is triggered by event E1 with guard Cond1,
and T2 which is also triggered by E1, but with a different guard expression Cond2.
If the machine is in S2 when event E1 is taken from the queue and
processed, it is possible that both Cond1 and Cond2 will evaluate to true.
In this case, we will say that both
T1 and T2 are enabled, but only one of them can be selected and executed.
In the case of a single state,
we will use document order as the tie-breaker, choosing whichever transition
occurs first in the definition of S1.
With complex states, the issue is more difficult. Returning to Diagram 4,
suppose that we are in the
complex configuration S1, S11, and
S112, when event E1 is processed. It is possible that all three states,
S1, S11, and S112, contain transitions that are enabled. In this case, we
start in the innermost state S112. If it has an enabled transition, we select it
(using document order as a tie-breaker if it has more than one.) If S112 does
not contain an enabled transition, we look in S11 and then in S1. Thus the most
narrowly scoped transition wins. The motivation for this choice
becomes clear when we remember that sequential substates are decompositions of
the parent state. Thus S112 is a refinement of S11 and S11 in turn is a
refinement of S1. The innermost state thus "knows the most" about
the situation so its transitions are preferred to those in outer states,
which can be treated as defaults or fallbacks.
In the case of concurrent substates, the event is processed by all concurrent states simultaneously and they select
their transitions independently. Thus if we are in S1, S12 and parallel
substates S121, S122, and S123, any
event will be processed by S121, S122, and S123 simultaneously, and they may all
select transitions. This makes most sense if all three states are themselves
complex and the event is triggering transitions among their
substates. If none of the three states handles the event, we move to S12 and
then to S1.
Although parallel substates run independently their operations can be
coordinated by means of Join states. The Join pseudo-state is has multiple incoming
transitions and one or more outgoing transition. The incoming transitions must be unconditional
(i.e., they cannot have <cond> or <event> properties.) The outgoing transitions
on the <join> may not have <event> triggers and at least one must lack a
<cond> guard condition. Thus when the <join> pseudo-state
is finally entered, there is always a transition that can be taken immediately. The <join>
pseudo-state is not entered until all its incoming transitions are enabled.
Thus the various threads of control wait in their current states
until they are all ready to enter the <join>, at which point they all enter simultaneously and
an outgoing transition is selected.
Now suppose we have two parallel states, S1 and S2, with sequential substates S11, S12, S13
and S21, S22 and S23, as shown in Diagram 5.
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<state>
<parallel>
<state id="S1">
<state id="S11">
<transition target="S12"/>
</state>
<state id="S12">
<transition target="S13"/>
</state>
<state id="S13"/>
</state>
<state id="S2">
<state id="S21">
<transition target="S22"/>
</state>
<state id="S22">
<transition target="S23"/>
</state>
<state id="S23"/>
</state>
</parallel>
</state>
</scxml>
G.6 Synchronizing And Concurrency
Given the basic Harel semantics S1 and S2 will function independently, so that S1
will move from S11 to S12 to S13 without regard to what S2 is doing, and vice-versa.
But now suppose that we want to ensure that S2 does not transition from S22 to S23
until S1 has left S11. Diagram 6 shows how we can do this using a <join>
state.
SCXML Equivalent
<?xml version="1.0" encoding="us-ascii"?>
<scxml version="1.0" xmlns="http://www.w3.org/2005/07/scxml">
<state>
<parallel>
<state id="S1">
<state id="S11">
<transition target next ="S12 synch1"/>
</state>
<state id="S12">
<transition target next="S13"/>
</state>
<state id="S13"/>
</state>
<state id="S2">
<state id="S21">
<transition target="S12"/>
</state>
<state id="S22>
<transition target="j1"/>
</state>
<state id="S23"/>
<join id="j1">
<transition target="S23"/>
</join>
</state>
</parallel>
</state>
</scxml>
We have inserted a <join> pseudo-state between S22 and S23,
with a conditionless incoming transition from S22 and a conditionless outgoing
transition to S23. (The <join> pseudo-state is represented as a vertical
bar with multiple incoming transitions and a single outgoing transition.)
Then we took the
transition leaving S11 and made it branch to include the <join> state as an
extra target. (In the diagram this is shown by inserting a 'fork' vertical bar, with a single
incoming transition and multiple outgoing transitions. In our SCXML notation, we use
multiple values in the "target" element). Now when the machine reaches S22, it will
wait until the <join> state is active (and therefore ready to
transition) before entering the <join> and transitioning to S23.
Similarly, when S1 is ready to leave S11, it will wait until S2 reaches S22 before
entering the <join> state. In either case,
the effect of the <join> state is to cause S1 and S2 wait for each other and
then to enter S12 and S23 simultaneously.
