Statecharts execution

Statechart semantics

The module interpreter contains an Interpreter class that interprets a statechart mainly following the SCXML 1.0 semantics. In particular, eventless transitions are processed before transitions containing events, internal events are consumed before external events, and the simulation follows a inner-first/source-state and run-to-completion semantics.

The main difference between SCXML and Sismic’s default interpreter resides in how multiple transitions can be triggered simultaneously. This may occur for transitions in orthogonal/parallel states, or when transitions declaring the same event have guards that are not mutually exclusive.

Simulating the simultaneous triggering of multiple transitions is problematic, since it implies to make a non-deterministic choice on the order in which the transitions must be processed, and on the order in which the source states must the exited and the target states must be entered. The UML 2.5 specification explicitly leaves this issue unresolved, thereby delegating the decision to tool developers:

“Due to the presence of orthogonal Regions, it is possible that multiple Transitions (in different Regions) can be triggered by the same Event occurrence. The order in which these Transitions are executed is left undefined.” — UML 2.5 Specification

The SCXML specification addresses the issue by using the document order (i.e., the order in which the transitions appear in the SCXML file) as the order in which (non-parallel) transitions should be processed.

“If multiple matching transitions are present, take the first in document order.” — SCXML Specification

From our point of view, this solution is not satisfactory. The execution should not depend on the (often arbitrary) order in which items happen to be declared in some document, in particular when there may be many different ways to construct or to import a statechart.

Another statechart tool does not even define any order on the transitions in such situations:

“Rhapsody detects such cases of nondeterminism during code generation and does not allow them. The motivation for this is that the generated code is intended to serve as a final implementation and for most embedded software systems such nondeterminism is not acceptable.” — The Rhapsody Semantics of Statecharts

We decide to follow Rhapsody and to raise an error (in fact, a NonDeterminismError) if such cases of nondeterminism occur during the execution. Notice that this only concerns multiple transitions in the same composite state, not in parallel states.

Note

Sismic allows to define priorities on transitions. This can be used to address some cases of nondeterminism. During execution, if a transition can be triggered, then transitions originating from the same state and whose priority is strictly lower than the selected one won’t be considered. Note that, as usual, transitions with no event are considered before transitions with event, regardless of the associated priorities.

When multiple transitions are triggered from within distinct parallel states, the situation is even more intricate. According to the Rhapsody implementation:

“The order of firing transitions of orthogonal components is not defined, and depends on an arbitrary traversal in the implementation. Also, the actions on the transitions of the orthogonal components are interleaved in an arbitrary way.” — The Rhapsody Semantics of Statecharts

SCXML circumvents this problem by relying again on the document order.

“enabledTransitions will contain multiple transitions only if a parallel state is active. In that case, we may have one transition selected for each of its children. […] If multiple states are active (i.e., we are in a parallel region), then there may be multiple transitions, one per active atomic state (though some states may not select a transition.) In this case, the transitions are taken in the document order of the atomic states that selected them.” — SCXML Specification

Again, Sismic does not agree with SCXML on this, and instead defines that multiple orthogonal/parallel transitions should be processed in a decreasing source state depth order. This is perfectly coherent with our aforementioned inner-first/source-state semantics, as “deeper” transitions are processed before “less nested” ones. In case of ties, the lexicographic order of the source state names will prevail.

Note that in an ideal world, orthogonal/parallel regions should be independent, implying that in principle such situations should not arise (”the designer does not rely on any particular order for event instances to be dispatched to the relevant orthogonal regions”, UML specification). In practice, however, it is often desirable to allow such situations.

See also

Other semantics can be quite easily implemented. For example, the extension sismic-semantics already provides support for outer-first/source-state semantics and priority to transitions with event. More information on Extensions for Sismic.

Using Interpreter

An Interpreter instance is constructed upon a Statechart instance and an optional callable that returns an Evaluator. This callable must accept an interpreter and an initial execution context as input (see Include code in statecharts). If not specified, a PythonEvaluator will be used. This default evaluator can parse and interpret Python code in statecharts.

Consider the following example:

from sismic.io import import_from_yaml
from sismic.interpreter import Interpreter

# Load statechart from yaml file
elevator = import_from_yaml(filepath='examples/elevator/elevator.yaml')

# Create an interpreter for this statechart
interpreter = Interpreter(elevator)

When an interpreter is built, the statechart is not yet in an initial configuration. To put the statechart in its initial configuration (and to further execute the statechart), call execute_once().

print('Before:', interpreter.configuration)

step = interpreter.execute_once()

print('After:', interpreter.configuration)
Before: []
After: ['active', 'floorListener', 'movingElevator', 'doorsOpen', 'floorSelecting']

The method execute_once() returns information about what happened during the execution, including the transitions that were processed, the event that was consumed and the sequences of entered and exited states (see Macro and micro steps and sismic.model.MacroStep).

for attribute in ['event', 'transitions', 'entered_states', 'exited_states', 'sent_events']:
    print('{}: {}'.format(attribute, getattr(step, attribute)))
event: None
transitions: []
entered_states: ['active', ...]
exited_states: []
sent_events: []

One can send events to the statechart using its sismic.interpreter.Interpreter.queue() method. This method accepts either an Event instance, or the name of an event. Multiple events (or names) can be provided at once.

interpreter.queue('click')
interpreter.execute_once()  # Process the "click" event

interpreter.queue('clack')  # An event name can be provided as well
interpreter.execute_once()  # Process the "clack" event

interpreter.queue('click', 'clack')
interpreter.execute_once()  # Process "click"
interpreter.execute_once()  # Process "clack"

For convenience, queue() returns the interpreter and thus can be chained:

interpreter.queue('click', 'clack', 'clock').execute_once()

Notice that execute_once() consumes at most one event at a time. In the above example, the clack event is not yet processed. This can be checked by looking at the external event queue of the interpreter.

for time, event in interpreter._external_queue:
    print(event.name)
clack
clock

Note

An interpreter has two event queues, one for external events (the ones that are added using queue()), and one for internal events (the ones that are sent from within the statechart). External events are stored in _external_queue while internal events are stored in _internal_queue. Internal events are always processed before external ones. To access the next event that will be processed by the interpreter, use the _select_event() method.

To process all events at once, one can repeatedly call execute_once() until it returns a None value, meaning that nothing happened during the last call. For instance:

while interpreter.execute_once():
  pass

For convenience, an interpreter has an execute() method that repeatedly call execute_once() and that returns a list of its output (a list of sismic.model.MacroStep).

from sismic.model import MacroStep

interpreter.queue('click', 'clack')

for step in interpreter.execute():
  assert isinstance(step, MacroStep)

Notice that a call to execute() first computes the list and then returns it, meaning that all the steps are already processed when the call returns. As a call to execute() could lead to an infinite execution (see for example simple/infinite.yaml), an additional parameter max_steps can be specified to limit the number of steps that are computed and executed by the method. By default, this parameter is set to -1, meaning there is no limit on the number of underlying calls to execute_once().

interpreter.queue('click', 'clack', 'clock')
assert len(interpreter.execute(max_steps=2)) <= 2

# 'clock' is not yet processed
assert len(interpreter.execute()) == 1

The statechart used for these examples did not react to click, clack and clock because none of these events are expected to be received by the statechart (or, in other words, the statechart was not written to react to these events).

For convenience, a Statechart has an events_for() method that returns the list of all possible events that are expected by this statechart.

print(elevator.events_for(interpreter.configuration))
['floorSelected']

The elevator statechart, the one used for this example, only reacts to floorSelected events. Moreover, it assumes that floorSelected events have an additional parameter named floor. These events are parametrized events, and their parameters be accessed by action code and guards in the statechart during execution.

For example, the floorSelecting state of the elevator example has a transition floorSelected / destination = event.floor that stores the value of the floor parameter into the destination variable.

To add parameters to an event, simply pass these parameters as named arguments to the queue() method of the interpreter.

print('Current floor is', interpreter.context['current'])

interpreter.queue('floorSelected', floor=1)
interpreter.execute()

print('Current floor is', interpreter.context['current'])
Current floor is 0
Current floor is 1

Notice how we can access the current values of internal variables by use of interpreter.context. This attribute is a mapping between internal variable names and their current value.

Macro and micro steps

An interpreter execute_once() (resp. execute()) method returns an instance of (resp. a list of) sismic.model.MacroStep. A macro step corresponds to the process of consuming an event, regardless of the number and the type (eventless or not) of triggered transitions. A macro step also includes every consecutive stabilization step (i.e., the steps that are needed to enter nested states, or to switch into the configuration of a history state).

A MacroStep exposes the consumed event if any, a (possibly empty) list transition of Transition instances, and two aggregated ordered sequences of state names, entered_states and exited_states. In addition, a MacroStep exposes a list sent_events of events that were fired by the statechart during the considered step. The order of states in those lists determines the order in which their on entry and on exit actions were processed. As transitions are atomically processed, this means that they could exit a state in entered_states that is entered before some state in exited_states is exited. The exact order in which states are exited and entered is indirectly available through the steps attribute that is a list of all the MicroStep that were executed. Each of them contains the states that were exited and entered during its execution, and the a list of events that were sent during the step.

A micro step is the smallest, atomic step that a statechart can execute. A MacroStep instance thus can be viewed (and is!) an aggregate of MicroStep instances.

This way, a complete run of a statechart can be summarized as an ordered list of MacroStep instances, and details can be obtained using the MicroStep list of a MacroStep.

Observing the execution

The interpreter is fully observable during its execution. It provides many methods and attributes that can be used to see what happens. In particular:

  • The execute_once() (resp. execute())

    method returns an instance of (resp. a list of) sismic.model.MacroStep.

  • The log_trace() function can be used to log all the steps that were processed during the

    execution of an interpreter. This methods takes an interpreter and returns a (dynamic) list of macro steps.

  • The list of active states can be retrieved using configuration.

  • The context of the execution is available using context

    (see Include code in statecharts).

  • It is possible to bind a callable that will be called each time an event is sent by the statechart using

    the bind() method of an interpreter (see Running multiple statecharts).

  • Meta-events are raised by the interpreter for specific events (e.g. a state is entered, a state is exited, etc.).

    Listeners can subscribe to these meta-events with attach.

Asynchronous execution

The calls to execute() or execute_once() are blocking calls, i.e. they are performed synchronously. To allow asynchronous execution of a statechart, one has, e.g., to run the interpreter in a separate thread or to continuously loop over these calls.

Module runner contains an AsyncRunner that provides basic support for continuous asynchronous execution of statecharts:

class sismic.runner.AsyncRunner(interpreter, interval=0.1, execute_all=False)

An asynchronous runner that repeatedly execute given interpreter.

The runner tries to call its execute method every interval seconds, assuming that a call to that method takes less time than interval. If not, subsequent call is queued and will occur as soon as possible with no delay. The runner stops as soon as the underlying interpreter reaches a final configuration.

The execution must be started with the start method, and can be (definitively) stopped with the stop method. An execution can be temporarily suspended using the pause and unpause methods. A call to wait blocks until the statechart reaches a final configuration.

The current state of a runner can be obtained using its running and paused properties.

While this runner can be used “as is”, it is designed to be subclassed and as such, proposes several hooks to control the execution and additional behaviours:

  • before_run: called (only once!) when the runner is started. By default, does nothing.

  • after_run: called (only once!) when the interpreter reaches a final configuration. configuration of the underlying interpreter is reached. By default, does nothing.

  • execute: called at each step of the run. By default, calls the execute_once method of the underlying interpreter and returns a list of macro steps.

  • before_execute: called right before the call to execute(). By default, does nothing.

  • after_execute: called right after the call to execute() with the returned value of execute(). By default, does nothing.

By default, this runner calls the interpreter’s execute_once method only once per cycle (meaning at least one macro step is processed during each cycle). If execute_all is set to True, then execute_once is repeatedly called until no macro step can be processed in the current cycle.

Parameters:
  • interpreter (Interpreter) – interpreter instance to run.

  • interval (float) – interval between two calls to execute

  • execute_all – Repeatedly call interpreter’s execute_once method at each step.

Anatomy of the interpreter

Note

This section explains which are the methods that are called during the execution of a statechart, and is mainly useful if you plan to extend or alter the semantics of the execution.

An Interpreter makes use of several private methods for its initialization and computations. These methods computes the transition(s) that should be processed, the resulting steps, etc. These methods can be overridden or combined to define variants of statechart semantics.

Interpreter._compute_steps()

Compute and returns the next steps based on current configuration and event queues.

Return type:

List[MicroStep]

Returns:

a possibly empty list of steps

Interpreter._select_event(*, consume=False)

Return the next event to process. Internal events have priority over external ones.

Parameters:

consume (bool) – Indicates whether event should be consumed, default to False.

Return type:

Optional[Event]

Returns:

An instance of Event or None if no event is available

Interpreter._select_transitions(event, states, *, eventless_first=True, inner_first=True)

Select and return the transitions that are triggered, based on given event (or None if no event can be consumed) and given list of states.

By default, this function prioritizes eventless transitions and follows inner-first/source state semantics.

Parameters:
  • event (Optional[Event]) – event to consider, possibly None.

  • states (Iterable[str]) – state names to consider.

  • eventless_first – True to prioritize eventless transitions.

  • inner_first – True to follow inner-first/source state semantics.

Return type:

List[Transition]

Returns:

list of triggered transitions.

Interpreter._sort_transitions(transitions)

Given a list of triggered transitions, return a list of transitions in an order that represents the order in which they have to be processed.

Parameters:

transitions (List[Transition]) – a list of Transition instances

Return type:

List[Transition]

Returns:

an ordered list of Transition instances

Raises:

ExecutionError – In case of non-determinism (NonDeterminismError) or conflicting transitions (ConflictingTransitionsError).

Interpreter._create_steps(event, transitions)

Return a (possibly empty) list of micro steps. Each micro step corresponds to the process of a transition matching given event.

Parameters:
Return type:

List[MicroStep]

Returns:

a list of micro steps.

Interpreter._create_stabilization_step(names)

Return a stabilization step, ie. a step that lead to a more stable situation for the current statechart. Stabilization means:

  • Enter the initial state of a compound state with no active child

  • Enter the memory of a history state

  • Enter the children of an orthogonal state with no active child

  • Empty active configuration if root’s child is a final state

Parameters:

names (Iterable[str]) – List of states to consider (usually, the active configuration)

Return type:

Optional[MicroStep]

Returns:

A MicroStep instance or None if this statechart can not be more stabilized

Interpreter._apply_step(step)

Apply given MicroStep on this statechart

Parameters:

step (MicroStep) – MicroStep instance

Return type:

MicroStep

Returns:

a new MicroStep, completed with sent events

These methods are all used (even indirectly) by execute_once.

See also

Consider looking at the source of execute_once to understand how these methods are related and organized.