-
Notifications
You must be signed in to change notification settings - Fork 29
Scion Semantics
The Statecharts semantics implemented by SCION is based on the paper "Big-Step Semantics", by Shahram Esmaeilsabzali, Nancy A. Day, Joanne M. Atlee, and Jianwei Niu. This work attempts to categorize the semantic aspects of a number of Statecharts variants, and describe the space of possible semantic options for each of these aspects. SCION chooses a particular configuration of the available options for each of these semantic aspects. This document provides a summary description of each of these semantic aspects, as well as the semantic choice selected by SCION, and for comparison, where possible, the choice made by the "Algorithm for SCXML Interpretation" described in the SCXML draft specification. This document is not meant to stand on its own, but rather assumes the reader has read "Big-Step Semantics", which fully describes all semantic aspects and their associated options.
This document is fairly technical and abstract, and it is primarily intended as a reference. For a more readable and higher-level overview of the similarities and differences between SCION and SCXML semantics, see [SCION vs. SCXML Comparison].
Description: Given a set of enabled transitions, this semantic aspect specifies how many transition occurrences can appear in a small-step.
Choices:
- Only a single transition can be enabled in a small-step.
- Multiple transitions can be enabled in a small-step
SCXML: Multiple
SCION : Same as SCXML
Description: In what order are selected transitions executed?
Choices:
- No order is specified
- Order is based on dependency order between variables ("dataflow" order)
- Order is explicitly defined
SCXML: Explicitly defined, based on document order (which defines a total ordering on execution order of states and transitions).
SCION : Same as SCXML
Description: This defines what happens when you have a transition originating in a descendant of an orthogonal state, and targeting a descendant of the same orthogonal state, in a different orthogonal component.
Choices:
- Arena Orthogonal : Two transition occurrences are included in the same small-step only if their arenas are orthogonal, where the arena of a transition is the smallest (lowest in the hierarchy of the composition tree) Or-state that is the (grand)parent of the source and destination control states of the transition.
- Source/Destination orthogonal: A small-step is consistent if for any of its two distinct transition occurrences, their sources and destinations are pairwise orthogonal.
SCXML: Undefined in SCXML semantics.
SCION: Arena Orthogonal
Description: This describes the following conditions (see Figure 9 in "Big-Step Semantics"):
- either the destination of one of the transitions is orthogonal with the source of the other, and the destination of the other transition is not orthogonal with the sources of either transition; we call the latter transition to be an interrupt for the former transition; or
- the destination of neither transition is orthogonal with the sources of the two transitions, but their destinations are ancestrally related; we call the transition that has a destination that is (grand)child of the other an interrupt for the other.
Choices:
- Preemptive, meaning that a transition does not permit a small-step to include two such transitions
- Non-preemptive otherwise
SCXML: Non-preemptive, in a very specific way: it will select transitions based on document order, until it reaches a transition that preempts later transitions, in which case it will not select them.
SCION: Non-preemptive
Description: Specifies when the sequence of small-steps of a big-step ends (i.e., when the model becomes stable, and is ready to sense the environment for new inputs).
Choices:
- Syntactic: a special syntax is used that specifies the states where the system should stop
- Implicit, of which there are two varieties
- Take-One: The system should incrementally take one transition in each big-step, until it reaches a point where it has no longer selected any transitions.
- Take-Many: The system should take multiple transitions in each big-step, until it reaches a point where it no longer has any transitions selected.
SCXML: Take-Many
SCION: Same as SCXML
Description: How to obtain the value of a variable when it is accessed in a variable condition or in the right-hand-side of an assignment.
Choices:
- Big-step, where variables stay the same throughout the big step, and are updated at the end of the big-step
- Small-step, where variables can be updated in each small-step.
SCXML: Changes detected immediately, after evaluation of or after !JavaScript assignment statement finishes executing.
SCION : Small-step
Description: When can a generated event in a model be sensed by the event triggers of the transitions in its big-step?
Choices:
- Whole: a generated event is considered present from the beginning of the current big-step, regardless of the small-step in which it has been generated, and persists until the end of the big-step
- Remainder: a generated event is considered present in the intermediate snapshot after the small-step that generates it, and persists during the remainder of the big-step
- Next small-step: a generated event is present only for the next small-step
- Same: a generated event is present during the current small-step
SCXML: Event can be sensed in the next small-step. Exactly one event can be sensed at a time. If multiple internal events are sent in the same small-step, then those events are added to a queue of events, and they will be dequeued one at a time, such that each subsequent small-step will sense the event at the head of the queue.
SCION: Next small-step
Description: When can the system receive interface events (external events)?
Choices:
- Strong Synchronous: An interface event is either present throughout a big-step from the beginning, or is absent throughout the big-step.
- Weak Synchronous: An interface event need not be present from the beginning of a big-step. If an interface event is generated by a sending component, the receiving components would receive the event during the current big-step.
- Asynchronous: An interface event will be sensed in the big-step after the big-step in which it is generated.
SCXML: Asynchronous
SCION : Same
Description: How to choose from a set of selected transitions?
Choices:
- Basis:
- Source: Priority is based on the transition source state.
- Destination: Priority is based on the transition destination state.
- Arena: Priority is based on transition arena.
- Scheme:
- Parent: If the basis is higher in the state hierarchy, it has higher priority.
- Child: If the basis is lower in the state hierarchy, it has higher priority.
SCXML: Uses a specific algorithm: sorts states in document order, then selects transitions by hierarchy of source state (inner-first priority). If multiple selected transitions on the source state, then document order is used.
SCION: First, uses Source-Child priority; if there are still conflicts, then uses document order where lower document order has higher priority.
Like the "Algorithm for SCXML Interpretation" described in the SCXML specification, these semantic choices are realized in a general step algorithm. Where possible, the pseudocode is annotated to indicate where specific semantic choices have been made.
Pseudocode for SCION step algorithm
SCION provides implementations of this step algorithm in CoffeeScript and Python.