thesis/02-Background.tex

\chapter{Background}
\label{chapt:Background}

In this chapter, we introduce the statecharts syntax and semantics, while showing that in many cases, the semantics of statecharts are not very precisely defined. Next, we introduce Big-Step Modeling Languages (BSML), which is a framework for precisely describing the semantics of a family of DSLs, including (variants of) statecharts. We then look at what aspects of the BSML framework are applicable to statecharts, on which we will base our selection of aspects to implement.

% In background zou ik ook verder ingaan op de basis van Statechart execution, dus I/O traces van events, en dan verder inzoomen naar state traces en eventueel nog lager als je het al over steps wilt hebben. Daarnaast zou ik het ook hebben over de "interface" van een Statechart model, waarbij je ook mag vermelden dat de interactie met de buitenwereld niet altijd noodzakelijk met events gebeurt, maar ook door bv. function calls vanuit de actietaal in het model.

% - Reactive systems

\section{Statecharts}

Statecharts are a formalism for modeling \emph{reactive, discrete-event, autonomous, timed, complex} and \emph{concurrent} systems:
\begin{description}
\item[Reactive] A statechart may receive input at any point in time.
\item[Discrete-event] Input arrives in the form of events at discrete points in time, as opposed to continuously.
\item[Autonomous + timed] A statechart has an internal notion of time, and may spontaneously act as result of time having passed.
\item[Complex] Statecharts can model complex behavior in a compact, understandable way.
\item[Concurrent] Multiple types of behavior can simultaneously co-exist.
\end{description}
Implementing these types of systems in a procedural programming language using timers, threads, shared memory and locks is extremely difficult. As we will see, statecharts alleviate this difficulty by focusing on the \emph{what} instead of the \emph{how}.

\subsection{Flat statecharts}

Statecharts \cite{harel1987statecharts} are an extension of finite-state machines (FSM), primarily adding, \emph{hierarchy}, \emph{concurrency} and \emph{history}. 

% Unlinke FSM's, a statechart usually does not have an explict set of accepting states. A statechart may also produce output (like Mealy/Moore machines), and make more than one transition in response to an input.
For now, we explain the syntax and semantics of \emph{flat} statecharts.

\subsubsection{Syntax}
A flat statechart consists of:
\begin{itemize}
  \item A finite set of states $S$.
  \item An initial state $i \in S$, sometimes also called \emph{default state}.
  \item A set of input events $X$, internal events $Y$ and output events $Z$. An event $e \in X \cup Y \cup Z$ has:
  \begin{itemize}
    \item a \emph{unique name} within the statechart.
    \item Optional: a set of \emph{named parameters} that are assigned values upon event instantiation.
  \end{itemize} 
  \item A set of variables $V$, and for every variable $v \in V$, an initial value.
  \item A set of transitions $T$, where every transition has:
  \begin{itemize}
    \item A source state $s \in S$.
    \item A target state $t \in S$.
    \item Optional: An event trigger $e \in X \cup Y$, or a time duration after which to automatically enable the transition.
    \item Optional: A guard condition, a boolean expression, possibly reading variables and event parameters, that, if evaluating to false, disables the transition.
    \item Optional: A set of actions, executed when the transition fires. Possible actions include
    \begin{itemize}
      \item Raising an event $e \in Y \cup Z$.
      \item Assigning a new value to a variable $v \in V$.
    \end{itemize}
  \end{itemize}
\end{itemize}

The set of transitions that has a state as its source is referred to as that state's set of \emph{outgoing} transitions. Similarly, the set of transitions with the same state as a target is called that state's set of \emph{incoming} transitions.

% \subsubsection{Definitions}
% \begin{description}
%   \item []
% \end{description}

\subsubsection{Semantics}

During execution, the ``state'' of a statechart is defined by its set of current states, called the statechart's \emph{configuration}, and its variable values. For flat statecharts, the configuration always consists of a single state. The configuration changes when a transition fires: the transition's source state is removed from the configuration, and its target state is added. When a state is added to the configuration, we say that the state is \emph{entered}, and when removed, the state is \emph{exited}.

Similar to FSM's, statecharts only react when there is input (timed transitions are a special case of input, as we will see). In the general case for statecharts, input comes in the form of a set of simultaneous events. For a set of input events, a statechart may make any number of transitions, producing a set of output events and a new configuration, ready to react to a next set of input events. Often, we will only consider input consisting of a single event, like with FSM.

Figure \ref{fig:sc_flat1} shows a very simple statechart with initial state $A$. If from the initial state, the event $e$ is received, the statechart will \emph{enable} the transition from $A$ to $B$. The transition from $B$ to $C$ will not be enabled, because $B$ is not in the configuration. For input $e$, the set of enabled transitions thus consists only of a single transition, which is fired, changing the configuration from $\{A\}$ to $\{B\}$.

\begin{figure}
\centering
\includegraphics{sc_flat1}
\caption{Simple flat statechart}
\label{fig:sc_flat1}
\end{figure}

\subsubsection{Possible execution algorithms}

In the previous example, what happens if from initial state $A$, the input events $\{e, f\}$ are simultaneously received? One might say that, ``naturally'', in response to this set of input events, both transitions are made, resulting in the final configuration $\{C\}$. An execution algorithm producing this behavior may look as follows:

\begin{python}
def step(configuration, input_events):
  while True:
    enabled_transitions = determine_enabled_transitions(configuration, input_events)
    if len(enabled_transitions) == 0:
      break # done
    elif len(enabled_transitions) == 1:
      configuration = fire_transition(configuration, enabled_transitions[0])
    else:
      # ???
  return configuration

# example ``loop''
def statechart_loop():
  while True:
    input_events = wait_for_input()
    step(configuration, input_events)
\end{python}

%\subsubsection{Preventing endless steps}
This algorithm however, can lead to a never-ending ``step'', if the model contains a ``loop'' of transitions, re-entering a previous state. This is highly common in practice: Figure \ref{fig:light_onoff} shows a statechart implementing a light than can be switched on or off by pressing the same button. Our algorithm from above would endlessly oscillate between Off and On, never concluding the step. A proper semantics for this statechart would be for the button press event to be ``consumed'' when a transition is made. There are 2 ways to implement this in an algorithm:

\begin{figure}
\centering
\includegraphics{light_onoff}
\caption{Simple light switch statechart}
\label{fig:light_onoff}
\end{figure}

\begin{enumerate}
  \item We could \emph{clear the set of input events} after the first transition made
  \item We could allow our step-function to only \emph{execute a single transition}.
\end{enumerate}
Variant (1) would clear the \texttt{input\_events} list at the end of each loop iteration. Variant (2) would only keep the loop body.

The semantics of most statechart implementations behave along the lines of these variants. For instance, STATEMATE \cite{harel1996statemate} and YAKINDU \cite{yakindu} use (1). Simply allowing only a single transition to be made, can be quite restrictive though: Figure \ref{fig:checkpoint} shows a statechart with a sequence of algorithm steps. Some transitions have only a guard condition, which is allowed, and several have no event trigger or guard, which is also allowed. If we want to reach the Finish-state, any number of transitions should be allowed after receiving the ``start''-event. An alternative would be to implement the sequence of steps as a single transition.

\begin{figure}
\centering
\includegraphics[width=\textwidth]{checkpoint}
\caption{Sequence of algorithm steps modeled as a statechart}
\label{fig:checkpoint}
\end{figure}

\subsubsection{Internal events}

There are more semantic choices to be made when we introduce internal events.
% For the statecharts shown until now, both algorithm modifications would produce the same behavior, because transitions were only triggered by input events. This changes when we introduce transitions triggered by:
% \begin{itemize}
%   \item Internal events
%   \item Only a guard condition
%   \item Nothing (triggerless transitions, always enabled)
% \end{itemize}
% For modification (2), no internal event-triggered transitions could ever be made, as the only way for an internal event to be raised, would be if a transition had previously fired. This makes modification (2) seem absurd, but its implementation changes when we introduce orthogonal regions (which are also an important reason for using internal events), as we will see later.

\begin{figure}
\centering
\includegraphics{sc_flat2}
\caption{Flat statechart with internal events}
\label{fig:sc_flat2}
\end{figure}

Figure \ref{fig:sc_flat2} shows a flat statechart that responds to (input) event $e$ by raising (internal) event $f$. If only one transition is allowed to be made for every ``step'' (set of inputs), the statechart's final configuration is $\{B\}$, no matter the event semantics. If multiple subsequent transitions are allowed, the configuration at the end of the step could be:
\begin{itemize}
  \item $\{D\}$, if we decide event $f$ remains \emph{active throughout the remainder of the step}.

  This behavior is trivially implemented by appending internally raised events to the set of enabled events.
  \item $\{C\}$, if we decide event $f$ is \emph{allowed to trigger at most 1 transition} (the transition ``consuming'' it). This would prevent ``looping'' behavior, while still allowing responses to internal events.

  This could be implemented by enabling $f$ only in the loop iteration following the iteration in which it was raised. 

  % This behavior is implemented by maintaining a separate set of events that is only enabled for one loop iteration. Events raised during iteration $n$ become active in loop $(n + 1)$.
  \item $\{B\}$ (!): If we decide to treat internally raised events as input events for a later step.
\end{itemize}
Again, there is no ``right'' answer. Statechart dialects exist for each of these choices.


% As we will see, there exist statechart dialects implementing either one of these modifications. %Both modifications will never be implemented simultaneously, because modification (2) is so restrictive, that modification (1), implemented on top of it, will have no further influence on the semantics.

\subsubsection{Enter and exit actions}

\begin{figure}
\centering
\includegraphics{light_enterexit}
\caption{Light switch with enter and exit actions}
\label{fig:light_enterexit}
\end{figure}

% SIMON: niet helemaal syntactic sugar, in combinatie met history
\emph{Enter and exit actions} are additional syntax, part of most statechart dialects, and, until we introduce history-states, may be regarded as a form of \emph{syntactic sugar}: they increase the clarity of the language, but can be expressed in other constructs.

Enter- and exit actions are properties of a state. They are actions to be executed when the state is entered and exited, respectively. For any state, enter actions could also be appended to the actions of every incoming transition, and exit actions could be prepended to the actions of every outgoing transition.

Figure \ref{fig:light_enterexit} shows the same behavior as the light switch in Figure \ref{fig:light_onoff}, but with enter- and exit-actions. By putting the output events ``turn\_on'' and ``turn\_off'' as actions in the On-state, we cannot ``forget'' to turn the light off (e.g. when adding more outgoing transitions to the On-state), since it is automatically turned off when exiting that state, and the only way to turn it on, is to enter the On-state.


\subsubsection{Timed transitions}

A feature often included in statechart implementations, is that of \emph{timed transitions}. It allows transitions to be triggered by having spent a certain amount of time in a state.

Suppose we want to add a ``blinking'' state to our light controller from Figure \ref{fig:light_enterexit}, e.g. to serve for a bicycle light. Figure \ref{fig:light_blink_flat} shows the solution. 2 new states are added, together representing the ``blinking'' state. The 2 new states are alternated between ``spontaneously'' (without interaction through any button presses). Pressing the button again from any of the 2 states takes us back to the Off-state.

% \begin{figure}
% \centering
% \includegraphics{light_blinking_flat}
% \caption{}
% \label{fig:light_blinking_flat}
% \end{figure}

\begin{figure}
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=0.95\linewidth]{light_blink_flat}  
  \caption{Flat statechart}
  \label{fig:light_blink_flat}
\end{subfigure}%
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=0.95\linewidth]{light_hierarchy}  
  \caption{Hierarchical statechart (next section)}
  \label{fig:light_hierarchy}
\end{subfigure}
\caption{Light controller with blinking-state}
\end{figure}

Timed transitions seem to contradict our earlier statement that a statechart can only react to an input. This remains true, but the statechart will ask the caller (through a callback) of the step-function for a timer to be started, and to be sent a special \emph{input event} when its timeout passes. Likewise, the statechart may ask the caller to cancel an earlier timer, if the source state requesting the timer is exited before the timout has passed.

The ``caller'' here, is the integration of the statechart's execution into some platform. It is responsible for scheduling and canceling timers, but also for collecting and delivering input and output events.


% We'll look at one more example. Figure \ref{fig:sc_flat3} shows a statechart with a variable assignment action, a transition with only a guard, and a triggerless transition. For input event $e$, we may end up in state $B$ or $D$, depending on whether more than one transition can be made during a step. 
% \begin{figure}
% \centering
% \includegraphics{sc_flat3}
% \caption{}
% \label{fig:sc_flat3}
% \end{figure}


\subsubsection{Transition ambiguity}

Up until now, the set of enabled transitions, also called the set of \emph{transition candidates} consisted of at most 1 transition. When the set of candidates contains more than 1 transition, a single transition should be \emph{deterministically} chosen, and preferrably in a fashion that is transparent to the modeler.

Figure \ref{fig:sc_flat4} shows a statechart representing a button that causes an action to be performed when it is pushed 3 times. The statechart has an integer variable \texttt{x} that is initialized with value 0. After the button is pushed twice, the statechart having responded 2 times to the input event ``push'', a third push-event could be responded to with either the self-transition $A \rightarrow A$, or $A \rightarrow B$. In order to make the model behave correctly, the modeler could:
\begin{itemize}
  \item Narrow the circumstances under which $A$'s self-transition is enabled, by adding a guard \texttt{x < 2}.
  \item Assign a higher \emph{priority} to the transition from $A$ to $B$.
\end{itemize}
Even if the first strategy does not require an extension of the syntax or semantics, supporting explicit priorities for outgoing transitions of a state prevents non-determinism in the general case for flat statecharts. This would further alter our execution algorithm, allowing multiple candidates and always firing the candidate with the highest priority.


\begin{figure}
\centering
\includegraphics{sc_flat4}
\caption{Example statechart with ambiguous transitions in state $A$ if $x == 0$}
\label{fig:sc_flat4}
\end{figure}

\subsubsection{Conclusion}

We have introduced the features of flat statecharts. We have also seen that even for flat statecharts, the semantics are not always clear, and choices can be made in implementations. Now, we will introduce hierarchy, followed by orthogonality.

\subsection{Hierarchy}

By adding \emph{hierarchy} to FSM / flat statecharts, states can be \emph{clustered} into arbitrary hierarchical levels. Clustering allows expressing the same behavior with fewer transitions.
% Statecharts \cite{harel1987statecharts} are an extension of finite-state machines (FSM), primarily adding \emph{hierarchy} and \emph{concurrency}.

% A major problem with FSM is that the model can only be in a single state at a time, requiring all states and transitions between them to be explicitly represented. 

Figure \ref{fig:light_hierarchy} shows the behavior of our light controller from an earlier example, with the 2 blinking-states explictly clustered into a Blinking-state. By considering this state as a state on its own, this results in one fewer ``button\_press''-transition.

Figure \ref{fig:vcr_flat} shows the behavior of a video-cassette recorder (VCR) modeled as a flat statechart. The VCR has 5 states and can respond to 4 different commands (power, play\_pause, stop, record), and has 13 transitions. A hierarchical statechart modeling the same behavior is shown in Figure \ref{fig:vcr_hierarchy}. Paused, Playing and Recording are clustered into the Stoppable-state, and at a higher level, Stoppable and Stopped have been clustered into the On-state. All 4 power-event triggered transitions to the Standby-state have been replaced by a single transition from the On-state, just like the 3 stop-event triggered transitions.


\begin{figure}
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{vcr_flat}  
  \caption{Flat statechart}
  \label{fig:vcr_flat}
\end{subfigure}%
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=.9\linewidth]{vcr_hierarchy}  
  \caption{Statechart with hierarchy}
  \label{fig:vcr_hierarchy}
\end{subfigure}
\caption{The behavior of a VCR, modeled as a finite-state machine, and as a statechart}
\end{figure}

The meaning of a cluster, or \emph{composite state}, as we will call them, is an (exclusive-)OR-relation between its substates. For instance, the Stoppable-state represents Paused, Playing OR Recording. Other terms sometimes used for a composite state include \emph{Or-state} and \emph{region}.

State hierarchies are easier to comprehend, as higher-level states abstract the detail expressed by lower-level states. While modeling, \emph{clustering} is a \emph{bottom-up} operation, where detail is abstracted. \emph{Refinement} is a \emph{top-down} operation, where abstractions are given detail. An example of refinement would be adding substates for playback speed to the Playing-state in Figure \ref{fig:vcr_hierarchy}.

\subsubsection{Syntax}

A hierarchical statechart consists of the same elements as a flat statechart, but with the set of states forming a \emph{state tree}. The root of the tree is called the \emph{root state}, which usually implicit (not drawn) in the visual representation of a statechart. The leaf nodes of the state tree are sometimes referred to as \emph{basic states}. The non-leaf nodes are composite states. The root state is always a composite state. Figure \ref{fig:vcr_tree} shows the state tree of the hierarchical VCR statechart.


Instead of a single initial state at the level of the statechart, every composite state, including the root state, has an initial state, which must be a direct child. In Figure \ref{fig:light_hierarchy}, Blinking-Off is the default state of Blinking. In Figure \ref{fig:vcr_hierarchy}, Stopped is the default state of On. %The transition from Standby to On could alternatively have Stopped as its target, without changing the statechart's behavior. In the figure, Stoppable has Playing as its default state, but since all transitions to Stoppable point directly to its substates, the default state is not being ``used'' by any transition.

\begin{figure}
\centering
\includegraphics[]{vcr_tree}
\caption{State tree of VCR statechart}
\label{fig:vcr_tree}
\end{figure}

\subsubsection{Definitions}
\begin{description}
  \item[Set of ancestors] For every state, the set of ancestors includes the state's parent state, and the ancestors of the parent. The set of ancestors always includes the root state, except for the root state itself, whose set of ancestors is empty.
  \item[Set of descendants] For every state, the set of descendants consists of the direct children of the state, and the descendants of the children.
  \item[Transition arena] The arena of a transition is the composite state that is the lowest common ancestor (LCA) of its source and target states.
\end{description}

\subsubsection{Semantics}
The semantics of statechart execution do not drastically change with the introduction of hierarchical states. Transitions can still have any state as source, and any state as target. The set of basic states still sums up the different configurations that the statechart can be in, but a statechart's configuration will consist of multiple states now: a basic state, and its ancestors.

\subsubsection{Entering and exiting states}

When a transition is fired, several states may be exited, and several states may be entered, if the transition spans several hierarchical levels. The following hierarchical ``rules'' apply:

\begin{itemize}
\item Before a state is entered, all of its ancestors must be present in the configuration.
\item Before a state is exited, all of its descendants must be exited first.
\end{itemize}

This causes a child-to-parent ordering of exited states, and parent-to-child ordering of entered states. This ordering only affects the order in which enter- and exit-actions are performed.

In Figure \ref{fig:light_hierarchy}, with the transition On $\rightarrow$ Blinking, the On-state is exited, followed by entering the Blinking and Blink-On states, in that order. With the transition Blinking $\rightarrow$ Off, either the Blink-Off or Blink-On state is exited (depending on the configuration), followed by exiting the Blinking-state, and finally, the Off-state is entered.

Chapter \ref{chapt:Implementation} will show an implementation that calculates the sets of exited and entered states mostly statically.

% There aren't any semantical choices to be made here.

\subsubsection{Hierarchical priority}

In the section on flat statecharts, we explained how an explicit priority-ordering between the outgoing transitions of a state can prevent non-determinism. With hierarchy, there could be a similar ambiguity between the outgoing transitions of a state and the outgoing transitions of its ancestors, as they can be simultaneously enabled.

By always giving higher priority to transitions whose source is deeper or shallower in the state tree, this form of non-determinism is avoided: The combination of a hierarchical priority and an explict ``flat'' priority yields a total ordering of all the transitions in a statechart.

Giving a higher priority to transitions with shallower source states has the benefit that \emph{refinement} of a state cannot alter the behavior of a statechart at the existing level. Giving higher priority to deeper transitions allows refinement to override behavior.

STATEMATE \cite{harel1996statemate} gives higher priority to shallower transitions. Rhapsody \cite{harel2004rhapsody}, UML state machines and ROOM \cite{selic1996real} give higher priority to deeper transitions.

\subsection{History}\label{sec:history}

Another addition of statecharts to FSM is \emph{history}. History enables a statechart to ``remember'' the configuration of an Or-state when it was exited, in order to be able to restore it at a later point in time.

\subsubsection{Syntax}

History adds 2 new types of \emph{pseudo-states} to the state tree: \emph{shallow history} and \emph{deep history}. A history state always occurs as the child of an Or-state, that it records the history of, each time that state is exited.

A history state can be the target of a transition, but not the source. A transition targetting a history state indicates that it wants to restore the previously recorded configuration.

\subsubsection{Semantics}

Pseudo-states, like history states, exist in the syntax, but can never occur in the statechart's configuration. If the history state is the target of a transition, during execution of the transition, the previously recorded configuration of the history's parent state is entered.

When exiting an Or-state that has a history state as its direct child, the configuration of the Or-state must be recorded. A shallow history state records the configuration only at the level of the direct children of the Or-state it belongs to (= a single state). A deep history state records the configuration of all the descendants of the Or-state (= a set of states).


The statechart in Figure \ref{fig:history} has a history state. When the transition $C \rightarrow D$ is fired, the states $C$, $Y$ and $X$ are exited, in order. When $X$ is exited, the shallow history state in $X$ records the state $Y$ as its ``past configuration''. When the transition $D \rightarrow H$ is fired, state $X$ is entered, followed by state $Y$ (the recorded ``history value''), and $B$ (the default state of $Y$), resulting in the final configuration $\{X,Y,B\}$

If the shallow history state in Figure \ref{fig:history} were replaced by a deep history state, it would record  $\{Y,C\}$ as a history-value (instead of just $Y$), resulting in the final configuration $\{X,Y,C\}$
\begin{figure}
\centering
\includegraphics{history}
\caption{Statechart with a (shallow) history state}
\label{fig:history}
\end{figure}

When a history state is entered for which no history has yet been recorded, its parent is simply entered instead (and as a consequence, the parent's default states, recursively). As an alternative, some statechart implementations allow a pseudo-transition from a history state to a sibling of the history state, indicating that the sibling is the ``default'' state to enter, in case no history has been recorded yet.

It is clear that implementations are required to keep in memory a recorded configuration for every history state in the statechart. This is part of the statechart's ``state'', along with the statechart's configuration, and scheduled timers (for timed transitions).

\subsection{Orthogonality}

Another addition of statecharts to finite state machines is \emph{orthogonality}. Up until now, the statechart's configuration always consisted of a single basic state, and the ancestors of that state. Orthogonality allows statecharts to be simultaneously in multiple (basic) states that are not ancestors of each other, allowing modeling of independent features.

Suppose we add an onscreen settings menu to our VCR example. The menu can be accessed at any time. Modeling this behavior with a flat statechart, or even making use of composite states would lead to a \emph{blowup} of states, as every existing state must be duplicated for every possible state of the menu: menu shown/hidden, the item in the menu selected, etc. Figure \ref{fig:vcr_flat_explosion} shows a FSM/flat statechart with only the possibility of the menu being shown/hidden modeled, and the number of states and transitions has almost doubled.

The same behavior, modeled as a statechart with orthogonality is shown in Figure \ref{fig:vcr_ortho}: The On-state split up in 2 \emph{orthogonal regions}: PlayingRecording and Menu. The meaning of the On-state has become PlayingRecording AND Menu, as both sub-regions are active states at the same time. The On-state is called a \emph{parallel} state, or \emph{And-state}.

\subsubsection{Syntax}
Syntactically, orthogonality builds on hierarchy, only introducing a new type of state to the state tree: The \emph{parallel state}, or \emph{And-state}. Just like composite states, parallel states are always non-leaf nodes in the state tree. Figure \ref{fig:vcr_ortho_tree} shows the state tree of the orthogonal VCR statechart.

We will more often talk about \emph{orthogonal regions} than about And-states. Orthogonal regions are Or-states that have an And-state as their common parent. The And-state itself is often not explicitly mentioned, and sometimes the name of the And-state is not even drawn in the visual representation of the statechart. Orthogonal regions are usually drawn next to each other, separated by a dotted line.

Transitions are still allowed from any state, to any state, including between orthogonal regions (Figure \ref{fig:cross_ortho_trans}), although this is rarely encountered.

\begin{figure}
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=0.95\linewidth]{vcr_flat_explosion}  
  \caption{Finite-state machine}
  \label{fig:vcr_flat_explosion}
\end{subfigure}%
\begin{subfigure}[b]{.5\textwidth}
  \centering
  \includegraphics[width=0.95\linewidth]{vcr_ortho}  
  \caption{Statechart with hierarchy and orthogonal components}
  \label{fig:vcr_ortho}
\end{subfigure}
\caption{The behavior of menu-extended VCR}
\end{figure}

\begin{figure}
\centering
\includegraphics[]{vcr_ortho_tree}
\caption{State tree of menu-extended VCR statechart}
\label{fig:vcr_ortho_tree}
\end{figure}

\begin{figure}
\centering
\includegraphics[]{cross_ortho_trans}
\caption{Cross-orthogonal region transition}
\label{fig:cross_ortho_trans}
\end{figure}

\subsubsection{Semantics}

The ``invariant'' that must hold before and after firing a transition, is that, if an And-state is part of the statechart's configuration, all of its direct children must also be part of the statechart's configuration. This means that upon entering an And-state, all of its children are entered (after the And-state is entered), and when exiting an And-state, all of its children are exited (before exiting the And-state).

This makes determining the set of entered and exited states of a transition somewhat complex, but still free from any ambiguities. In principle, when firing a transition, all of the states in the configuration that are descendants of the transition's arena (lowest common Or-state ancestor) are exited. Usually transitions do not cross orthogonal regions. Figure \ref{fig:cross_ortho_trans} shows an uncommon example of a cross-orthogonal region transition:  The transition will cause the entire And-state to be exited and re-entered. If the configuration is $\{B, C, F\}$, the configuration becomes $\{A, D, E\}$.

Section \ref{sec:firing_transition} will explain our implementation with a complex transition as an example.

\subsubsection{Concurrent transitions}

Figure \ref{fig:sc_ortho1} shows a statechart with 2 orthogonal regions, both responding to an event $e$. There are several ways we can interpret the statechart's reaction to $e$, if we are in $\{A, D\}$:

\begin{figure}
\centering
\includegraphics[]{sc_ortho1}
\caption{Statechart with 2 orthogonal regions}
\label{fig:sc_ortho1}
\end{figure}

\begin{itemize}
\item One possible type of semantics would allow both regions to fire as many transitions as they can, $e$ remaining enabled throughout. This would result in the configuration $\{C, E\}$. With this type of semantics, what would be the order of the transitions fired?

\item For flat statecharts, we saw that it may be desirable to allow only 1 transition per input event, ``consuming'' the event, and avoiding endless steps. But would this result in the configuration $\{B, D\}$ or $\{A, E\}$?

\item Another type of semantics would be to allow at most one transition to be executed \emph{per orthogonal component}. This would result in the configuration $\{B, E\}$.
\end{itemize}

\subsubsection{Orthogonal region priority}

A partial answer to the above questions would be to explicitly assign priorities to orthogonal regions, similar to how we could assign explicit priorities to a state's outgoing transitions. The assigned priorities would then determine the order in which regions are allowed to make transitions.



\subsubsection{Interaction between orthogonal regions}

Unlike the orthogonality examples we have seen until now, there are typically some interactions between orthogonal regions. These can take the form of:
\begin{itemize}
  \item A transition in one region raising an event, a transition in another region responding to this event.
  \item A transition's guard condition in one region checking whether a state of another region is part of the configuration.
  \item A transition's actions assigning a new value to a variable, and this value being read by a transition (guard or actions) in another region.
\end{itemize}

\begin{figure}
\begin{subfigure}[b]{.33\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{sc_ortho_intevent}  
  \caption{Internal event}
  \label{fig:sc_ortho_intevent}
\end{subfigure}%
\begin{subfigure}[b]{.33\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{sc_ortho_instate}  
  \caption{``In state''-check}
  \label{fig:sc_ortho_instate}
\end{subfigure}%
\begin{subfigure}[b]{.33\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{sc_ortho_var}  
  \caption{Variables}
  \label{fig:sc_ortho_var}
\end{subfigure}
\caption{Different ways of communication between orthogonal regions}
\end{figure}


\subsection{Statechart interface}

During its execution, a statechart usually interacts with other parts of software. A statechart is controlled by the software that its delivers inputs, and a statechart can control software (or hardware) that responds to its outputs.

% Statecharts can be used to control other parts of software (and hardware), and are themselves controlled by software.

We have seen before that a statechart can only react if it receives an input event. However, during its reaction to an event, a statechart may receive inputs in other ways. We have also seen that a statechart may produce output events during its reactions, but this is also just one of the ways a statechart can produce output.

A statechart's interface may consist of sets of the following elements, usually explicitly declared:
\begin{itemize}
  \item Input/output events%, triggering reactions within the statechart.
  \item Input/output variables
  \item Synchronous functions%, called by the statechart, implemented outside of the statechart.
\end{itemize}

\subsubsection{Input/output events}
\emph{Input events} have already been covered, they are what causes a reaction of the statechart. \emph{Output events} are received by the environment the statechart interacts with, at the end of a statechart's reaction. They are useful for asynchronous outputs, as the receiver does not have to respond or acknowledge their reception.

\subsubsection{Input/output variables}
A statechart may also declare a number of \emph{input variables}, that it can read \emph{while reacting} to an input event. Input variables are useful when a changing value is of interest to the statechart, but the changing of the value itself does not require a reaction of the statechart (i.e. should not be an event): The statechart decides when to read the value. Likewise, \emph{output variables} can be useful when a statechart regularly updates some value, but the environment decides when to read the value.

\subsubsection{Synchronous functions}
With synchronous functions, a statechart can call a piece of code that is implemented outside of the statechart. Functions are called during the execution of a transition, and are blocking: the transition cannot complete before the function returns control to the statechart, possibly with a \emph{return value}. The statechart can use functions for querying information (input) or signaling (output), or both.

Because of their flexibility, synchronous functions are very useful for letting a statechart control another piece of software.

Synchronous functions can serve as a primitive for
\begin{itemize}
  \item Output events: if the function called queues a generated event and immediately returns control.
  \item Input/output variables: if the function called is a getter/setter.
\end{itemize}
although ``native'' variables may be more efficient than getters and setters.

\subsection{Execution traces}

In order to get insight in a statechart, for debugging, logging, profiling, ..., we may be interested in the history of a statechart's execution.

The execution of a statechart is a sequence of reactions to sets of input events. Every reaction may also contain a set of produced output events. The sequence of inputs and outputs is the \emph{I/O trace} of the statechart, and is the result of looking at a statechart as a \emph{black box}. We may also look closer to see what is happening \emph{inside the statechart}. The most obvious trace would be the sequence of transitions that were fired, from which we can restore a \emph{state trace}.


% - Explaining (harel) Statecharts
%     - hierarchical states CHECK
%     - orthogonal states
%     - broadcasting of events
%   - Definitions
%     - set of ancestors, descendants
%     - transition arena

% - Statechart interface:
%   - Events: in/out
%   - Variables: in/out
%   - Function calls from action language: out

% - Statechart execution:
%     I/O traces of events > state traces > steps


\section{Big-Step Modeling Languages}\label{sec:bsmls}

Big-Step Modeling Languages (BSML) \cite{sabzali2010deconstructing} are a family of modeling languages that may perform several transitions in response to an input. These languages were mapped onto a common syntax,
which is pretty much the syntax of statecharts. Within this common syntax, the semantics of languages in the BSML family are represented as a large feature diagram of semantic options, with at the highest level 8 orthogonal semantic aspects, i.e. independent categories of semantic choices to be made.

Because the family of BSML languages includes statecharts, (a subset of) the semantic aspects of BSML can serve as the basis for describing the possible semantics of statecharts accurately.

In this section, we will discuss the 8 semantic aspects of BSML, and for each of them, determine whether they are applicable to statecharts. Following the conventions from \cite{sabzali2010deconstructing}, we will use \textsc{Small Caps Font} for the names semantic options.

\subsection{Syntax}

The syntax of BSML, called the Composed Hierarchical Transition System (CHTS) syntax, is in many ways identical to the statechart-syntax discussed in the first half of this chapter. A model in BSML has a state tree of Or-, And- and basic-states, with transitions between any of the states. Transitions can have event triggers, guard conditions and actions. Actions are (1) variable assignments, and (2) the raising of internal and output events.

BSML syntax is more ``primitive'' than statecharts because it has \textbf{no explicit syntax for timed transitions, no enter- or exit-actions and no history}. It doesn't forbid these constructs, it is just that these constructs do not fundamentally touch on the semantic choices that can be made by a BSML language.

BSML also considers many syntactical features optional, such as variables, events, and explicit differentiation between input/internal/output events, but we assume a full-featured syntax.

\subsection{Fundamental semantics}

Before we explore the semantic options of BSML, we must first explain the ``fundamental'' semantics of BSML, i.e. the semantics that are always the same.

The execution of a BSML is a sequence of \emph{big-steps}. A big-step is a reaction to a set of input events. A big-step consists of a sequence of \emph{small-steps}. A small-step is a set (unordered) of transitions that were \emph{concurrently} fired. The meaning of ``concurrently'' here is highly specific, and unless Concurrency-semantics are used (discussed later), one may think of a small-step as a single transition.
Depending on the semantic options chosen, sequences of small-steps may also be grouped into \emph{combo-steps}. A big-step then consists of a sequence of combo steps. See Figure \ref{fig:big_step}.

\begin{figure}
\centering
\includegraphics{big_step}
\caption{Left: Big-step as a sequence of small-steps. Right: Big-step as a sequence of combo-steps.}
\label{fig:big_step}
\end{figure}

The semantic options of BSML only determine how a big-step is executed. BSML says nothing about the wider scope of an execution runtime, such as scheduling and queueing of input events, as is often done in statechart implementations.

\subsection{Big-Step Maximality}

The first semantic aspect is \emph{Big-Step Maximality}, which limits the transitions that can be fired together within a big-step. Options are:
\begin{description}
  \item[\textsc{Take Many}] No limitation: The big-step may consist of as many transitions as possible (other semantic aspects may still limit the number of transitions that \emph{can} be taken).

  Combined with orthogonality, this semantic option usually lets orthogonal regions take turns in trying to fire a transition. This behavior is called \emph{fairness}.

  A hazard of this semantic option is never-ending big-steps. Because of this, \textsc{Take Many} is usually combined with other semantic options limiting the number of transitions that can be made (such as Event Lifeline, see later).

  \item[\textsc{Take One}] No transitions with \emph{overlapping arenas} are allowed to be taken together within a big-step. The arena of a transition is the lowest common ancestor of source and target that is an Or-state. Arenas are overlapping if they are the same state, or if one is an ancestor of the other.

  For non-orthogonal statecharts (hierarchy allowed), this option means that only a single transition can be taken within a big-step. For orthogonal statecharts, this means that a transition can be taken within each orthogonal region (if both the source and destination of the transitions are in the same region).

  \item[\textsc{Syntactic}] No transitions with \emph{overlapping arenas and whose target states are marked as ``stable''} can be taken together in a big-step. This option requires additional syntax for marking states as ``stable''.

  This option is similar to \textsc{Take One}, but only transitions with a stable target state ``count'', and mark the transition's arena as ``used''.

  This option may also lead to never-ending big-steps, if a state in a region can be re-visited during a big-step without passing through a stable state.

  This option may be useful to model ``checkpoints'' in a sequence of algorithm steps as (non-stable) states (Figure \ref{fig:checkpoint}).
\end{description}

Ordering these options by the number of transitions allowed in a big-step, in \emph{any model}, would yield \textsc{Take Many} $\geq$ \textsc{Syntactic} $\geq$ \textsc{Take One}.

While executing a big-step, the ``limiting'' options (\textsc{Take One} and \textsc{Syntactic}) work by constraining the set of enabled transitions, based on transitions that were previously executed. A big-step ends when no more transitions can be executed.

\subsubsection{Example}
Figure \ref{fig:big_step_maximality} shows a statechart with 2 orthogonal regions. Suppose we are in configuration $\{A, D\}$ and some input is received (triggering a reaction in the statechart). The labels on the transitions are not event triggers, they are to refer to the transitions. None of the transitions have event triggers or guards, meaning that they are enabled whenever their source state is active. States $C$ and $E$ are marked stable, which only affects behavior when the \textsc{Syntactic} option is chosen. We also suppose the region on the left is always allowed to fire a transition first:

\begin{figure}
\centering
\includegraphics{big_step_maximality}
\caption{Example statechart for Big-Step Maximality}
\label{fig:big_step_maximality}
\end{figure}

\begin{itemize}
\item If we choose \textsc{Take Many} with fairness, the big-step would be the infinite sequence $[ \{t1\}, \{t3\}, \{t2\}, \{t4\}, \{t3\}, \{t4\}, ... ]$ because of the ``loop'' of transitions in the region on the right.

\item If we choose \textsc{Take One}, the big-step would be the sequence $[ \{t1\}, \{t3\} ]$, yielding the configuration $\{B, E\}$. Transitions $t2$ and $t4$ can no longer be fired, because their arenas overlap with those of $t1$ and $t3$, respectively.

\item If we choose \textsc{Syntactic}, the big-step would be $[ \{t1\}, \{t3\}, \{t2\} ]$, yielding the configuration $\{C, E\}$. The transition $t4$ can no longer be fired, because by executing $t3$, a stable state was entered, preventing its arena (the region on the right) from executing any more transitions.
\end{itemize}


\subsection{Combo-Step Maximality}

As we have seen, combo-steps are an additional grouping of small-steps within a big-step. Combo-steps by themselves serve little purpose, but other semantic options will give meaning to them.

The semantic aspect \emph{Combo-Step Maximality} is optional: if there is no need for combo-steps, no choice needs to be made here.

The options for this aspect limit the transitions that can be taken together in a combo-step, similar to the options for Big-Step Maximality:

\begin{description}
  \item[\textsc{Combo Take Many}] Exactly the same as \textsc{Take Many}.
  \item[\textsc{Combo Take One}] Exactly the same as \textsc{Take One}.
  \item[\textsc{Combo Syntactic}] Exactly the same as \textsc{Syntactic}, but instead a ``stable'' state here is marked as being ``combo-stable'', another additional syntactic construct.
\end{description}
Note that combining \textsc{Take Many} with \textsc{Combo Take One} is a way to introduce fairness to \textsc{Take Many}: A combo-step would end when every orthogonal region has had a chance to fire a transition, but at the level of the big-step, this would repeat itself until no more transitions are enabled. These two options are often combined in statechart implementations.

Note that combining \textsc{Take One} with any Combo-Step Maximality option would be quite useless, as the limitation of \textsc{Take One} would also apply within every combo-step, resulting in \textsc{Combo Take One}-semantics, and every big-step consisting of only a single combo-step.

\subsubsection{Example}

For the statechart in Figure \ref{fig:big_step_maximality}:

\begin{itemize}
  \item Choosing \textsc{Take Many} and \textsc{Combo Take One} would result in the endless big step $[ [\{t1\}, \{t3\}], [\{t2\}, \{t4\}], [\{t3\}], [\{t4\}], ... ]$.
  \item Choosing \textsc{Syntactic} and \textsc{Combo Take One} would result in the big step $[ [\{t1\}, \{t3\}], [\{t2\}] ]$.
\end{itemize}

In both these examples, the same transitions are taken as without combo-step semantics, and the same configuration results. However, other semantic options may refer to combo-steps, as we will now see.

\subsection{Event Lifeline}

Options for the \emph{Event lifeline} semantic aspect determine \emph{when} raised events in a big-step become present, and for \emph{how long}. As long as a raised event is present, it may enable transitions. Event Lifeline is therefore a way to control when, and for how long a raised event can trigger transitions.

Option are:
\begin{description}
\item [Present in Whole] A raised event is present throughout the entire big-step, even from before the point where it was raised. An event either is, or isn't present in a big-step. This option comes from synchronous programming languages such as Esterel.
\item [Present in Remainder] A raised event becomes present right after the small step in which it was raised, and remains present for the rest of the big-step.
\item [Present in Next Combo-Step] A raised event is present for the entirety of the next combo-step. This option (often combined with \textsc{Combo Take One}), and has the advantage of separating input events from internal events in separate ``rounds''.
\item [Present in Next Small-Step] A raised event is present only in the next small-step, allowing at most one transition to be made as a reaction to the event.
\item [Present in Same] A raised event is present in the same small step as where it was raised. This option is only useful in combination with Concurrency-semantics (allowing multiple transitions within a small step).
\end{description}
Figure \ref{fig:event_lifeline} visually shows the times and durations of the various options.

\begin{figure}
\centering
\includegraphics{event_lifeline}
\caption{Event lifeline options}
Figure taken from \cite{sabzali2010deconstructing}.
\label{fig:event_lifeline}
\end{figure}

Event Lifeline options can be separately applied to input events and internal events: For instance, we could choose \textsc{Present in Whole} for input events, and \textsc{Present in Next Combo-Step} for internal events, but often, the same option is chosen for both.

For input events, there is no difference between \textsc{Present in Whole} and \textsc{Present in Remainder}, and we often rename the options \textsc{Present in Next Combo-Step} and \textsc{Present in Next Small-Step} to \textsc{Present in First Combo-Step} and \textsc{Present in First Small Step}, respectively. \textsc{Present in Same} is not a valid option for input events.

The options \textsc{Present in Whole} and \textsc{Present in Remainder} are usually not combined with \textsc{Take Many}, because of the possibility of never-ending big-steps.

\textsc{Present in Next Combo-Step}  \textsc{Present in Next Small-Step} allows at most one transition to be made as a reaction to a raised event.

\subsubsection{Queueing of (internal) events}

Many statechart implementations queue input events, and send them to the statechart one by one. This type of queueing is compatible with BSML, but not a part of it: The statechart simply performs a big-step as a reaction to each input event.

However, there are also statechart implementations that queue internal events. The benefit is that only a single internal event is handled at a time. A statechart implementation may put internal events in the same event queue used for input events (e.g. Rhapsody \cite{harel2004rhapsody}), or maintain a separate, higher priority queue for them (e.g. YAKINDU \cite{yakindu} in event-driven mode). With the former, reactions to internal events may be interleaved with input events, while with the latter, the reaction to an input event is atomic, containing also the reactions to internal events.

BSML defines no semantic options for the queueing of internal events. We could define at least the following options to extend BSML:

\begin{description}
  \item [Queue] Internally raised events are added to the statechart's input event queue, and will therefore be reacted to in a later big-step.

  \item [Combo-Queue] Internally raised events are pushed to a special FIFO queue, only meant for input events, and a new combo-step is started for each popped event from the queue, with only that event being present, until the queue is empty.
\end{description}

\subsubsection{Example}
In the statechart in Figure \ref{fig:sc_event_lifeline}, suppose a big-step starts by firing the transition $t1$, raising the (internal) event $e$.

\begin{figure}
\centering
\includegraphics{sc_event_lifeline}
\caption{Example statechart for Event Lifeline}
\label{fig:sc_event_lifeline}
\end{figure}

\begin{itemize}
\item If we choose \textsc{Take Many} (with fairness) and \textsc{Present in Remainder}, the big-step is $[ \{t1\}, \{t3\}, \{t2\} ]$.
\item If we choose \textsc{Take Many} and \textsc{Present in Next Combo-Step} along with \textsc{Combo Take One}, the big-step is $[ [ \{t1\} ], [ \{t2\}, \{t3\} ] ]$.
\item If we choose \textsc{Take Many} (with fairness) and \textsc{Present in Next Small-Step}, the event $e$ can only trigger a single transition, and the big-step is $[ \{t1\}, \{t3\} ]$.
\end{itemize}


\subsubsection{External Events}

Event Lifeline also defines options (independent to the options listed above) determining how to distinguish input and output events from internal events. For statecharts, we assume this is done syntactically, so we aren't interested in any other options here.

\subsubsection{Interface Events}

Event Lifeline also defines options (independent to the options listed above) on interface events. Interface events are events used for communication between \emph{components} of a model. The components here are actually models on their own. For statecharts, there are no interface events: a statechart may send an event to another statechart, but such events are not treated different from output/input events.

\subsection{Memory Protocol}

For memory protocol, 2 independent semantic aspects exist: \emph{Enabledness Memory Protocol} and \emph{Assignment Memory Protocol}. Both have the same options, having effect on the values of variables that are read during guard condition evalution (enabledness) or during execution of a transition's actions (when assigning new values to variables), respectively. Usually the same option is chosen for both aspects.

The options are:

\begin{description}
  \item[Big Step] Values of variables are read as they were at the beginning of the big-step.

  \item[Combo Step] Values of variables are read as they were at the beginning of the combo-step.

  \item[Small Step] Values of variables are read as they were at the beginning of the small-step.
\end{description}

By choosing \textsc{Combo Step}, transitions within the same combo-step cannot see each other's effects on the statechart's variables. If also \textsc{Present in Next Combo Step} is chosen for Internal Event Lifeline, then transitions within a combo-step truly have no influence on each other, apart of course from the changes they make to the statechart's configuration.

Similarly, with \textsc{Big Step}, all transitions in a big-step cannot see each other's effects on the variables. This option is likely to be more useful when big-steps are small, e.g. when \textsc{Take One} is chosen.

Choosing \textsc{Small Step} causes the most actual version of variables' values to be read, effectively ``disabling'' the memory protocol.

\subsubsection{Example}

For the statechart in Figure \ref{fig:memory_protocol}, suppose we choose \textsc{Take Many} and \textsc{Combo Take One}. Transition $t1$ is the first one to execute in a big-step.

\begin{figure}
\centering
\includegraphics[]{memory_protocol}
\caption{Example statechart for Memory Protocol}
\label{fig:memory_protocol}
\end{figure}

\begin{itemize}
\item If we choose \textsc{Big Step}, then no other transition can fire. The big step is $[ [ \{t1\} ] ]$.
\item If we choose \textsc{Combo Step}, then the big step is $[ [ \{t1\} ], [ \{t2\}, \{t3\} ] ]$.
\item If we choose \textsc{Small Step}, then the big step is $[ [ \{t1\}, \{t3\} ], [ \{t2\} ] ]$.
\end{itemize}

\subsubsection{Interface Variables}

Just like interface events, some BSML languages feature interface variables for coummnication between \emph{components}. Statecharts do not have such ``components'', so we will not discuss semantic options for interface variables.

\subsection{Order Of Small-Steps}

The semantic aspect \emph{Order of Small-Steps} determines the order in which small-steps (transitions) are executed, if more than one of them can be executed, independently. For statecharts, this is when transitions are enabled in multiple orthogonal regions. Options are:

\begin{description}
  \item[None] Small-steps are unordered: an order is chosen non-deterministically.

  \item[Explicit Ordering] Introduces additional syntax for explitly ordering small-steps. In a statechart, this would be done by assigning a priority relationship between orthogonal regions at the same level.

  \item[Dataflow] Small-steps are ordered such that a transition assigning a value to a variable, happens before a transition reading that variable.

  Since a variable is used to communicate information from one small-step to another, this option should only be combined with \textsc{Small Step} for Memory Protocol semantics.
\end{description}

For statecharts, the non-determinism of \textsc{None} makes it an unsuitable option. Almost always, \textsc{Explicit Ordering} is used. \textsc{Dataflow} is an interesting option, but in many statecharts, may only yield a \emph{partial ordering} between orthogonal components. Since transitions in a statechart can also make synchronous calls during their execution, to functions implemented outside of the statechart, and perhaps an ordering is desired on these function calls, the statechart itself would contain not enough information to execute the transitions in their right order.

\subsubsection{Example}

In all previous examples, we assumed \textsc{Explicit} order of small-steps, giving higher priority to orthogonal regions from left to right.

\subsection{Priority}\label{sec:priority}

Highly related to the previous semantic aspect, \emph{Priority} deals with all other situations where multiple transitions could be selected for inclusion in a small-step. The options for this semantic aspect can be combined arbitrarily to make the model behave deterministically.

\begin{description}
  \item [Hierarchical] This is actually a \emph{collection} of semantic options that assign priority according to some hierarchical property of a transition. Most commonly, the nested depth of the source state of the transition determines its priority: The sub-options \textsc{Source-Parent} and \textsc{Source-Child} create a priority relationship between transitions whose sources are ancestors of one another, preferring ``parent'' (ancestor) or ``child'' (descendant), respectively.

  Other options mentioned in \cite{sabzali2010deconstructing} are \textsc{Arena-Parent} and \textsc{Arena-Child}, creating a priority relationship between transitions whose arena's are ancestors of each other.

  \item [Explicit Priority] Introduces additional syntax to explicitly order transitions. In statecharts, this option is often chosen to create an ordering between the outgoing transitions of a state.

  \item [Negation of Triggers] If 2 transitions respond to different events, and both events are present, one transition can be given a lower priority adding the \emph{negated event} of the other transition to its trigger.
\end{description}

\subsubsection{Relation to Order of Small-Steps}\label{sec:ooss_priority}

The semantic options \textsc{Hierarchical} and \textsc{Explicit Priority} create a \emph{partial ordering} between transitions. Order of Small-Steps also does this. (We will ignore \textsc{Negation of Triggers} here because it only creates an ordering in the special circumstances where more than one event is enabled simultaneously.)

In a statechart, transitions can only be simultaneously enabled in 3 ways:
\begin{enumerate}
  \item If they have the same source state.
  \item If one's source is an ancestor of the other's source.
  \item If one's source is orthogonal to other's source, i.e. the LCA of the sources is an And-state.
\end{enumerate}
Note how (1) was mentioned when discussing flat statecharts, (2) arises when we introduce hierarchy, and (3) arises when we introduce orthogonality.

\textsc{Explicit Priority} can create an ordering between transitions of type (1). The priority options \textsc{Source-Parent} and \textsc{Source-Child} create an ordering between transitions of type (2). Order of Small-Steps creates an ordering between transitions of type (3). 

An apparent difference between Order of Small-Steps and Priority, is that Order of Small-Steps defines an order on small-steps (executing all small steps), while Priority chooses a single transition among a set of candidates that cannot be executed together, because they disable each other. At least for statecharts, this distinction is not quite correct, because simultaneously enabled orthogonal transitions may still disable each other in unpredictable ways (due to action language code or the raising of events that are negated in other triggers). So while a priority relation is defined between orthogonal transitions, a statechart implementation cannot (fully) predict which subset of these transitions is going to fire. All it can do, is select 1 highest-priority enabled transition at a time, execute it, and repeat until no more transitions can be executed as part of the combo- or big-step. An ``order'' of small-steps arises in retrospect. A careful conclusion is that Order Of Small-Steps is really just a collection of Priority-options.

The partial orderings of Priority and Order of Small-Steps are statically known, and if the combination of them yields a total ordering on all sets of transitions that can be simultaneously enabled, then the statechart behaves deterministically. The set of \emph{all} transitions in the statechart may still be only partially ordered, but this is OK, as long as the transitions that are unordered with respect to each other cannot be enabled simultaneously.

\subsubsection{Example}
Figure \ref{fig:priority_example} shows a statechart whose transitions can all be simultanously enabled. The semantic options \textsc{Source-Parent}, \textsc{Explicit Ordering} of orthogonal regions and \textsc{Explicit Priority} of outgoing transitions of the same state yields a total ordering $t5 > t3 > t1 > t2 > t4$, meaning that if e.g. $t3$ can only fire if $t5$ is not enabled.% $t4$, the lowest-priority transition, can only fire if all other transitions are disabled, which wil be the case if, e.g. \textsc{Take One} is chosen and a transition in the orthogonal region on the left has already fired during the big-step.

In the previous (artificial) example, there was a total ordering on all transitions in the statechart. This is usually not the case: For instance, in the statechart in Figure \ref{fig:big_step_maximality}, there doesn't have to be an ordering between $t1$ and $t2$ or between $t3$ and $t4$, because they cannot be simultaneously enabled.

\begin{figure}
\centering
\begin{subfigure}[b]{.4\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{priority_example}  
  \caption{Statechart}
\end{subfigure}%
\begin{subfigure}[b]{.6\textwidth}
  \centering
  \includegraphics[width=0.9\linewidth]{priority_example2}  
  \caption{Orderings}
  Meaning of an arrow: ``has higher priority than''
\end{subfigure}
\caption{Example of partial orderings created by various priority semantical options}
\label{fig:priority_example}
\end{figure}

\subsection{Concurrency}

\emph{Concurrency} allows small-steps to consist of multiple transitions. Transitions within a small step logically happen concurrently, but implementations will typically execute them in some (non-deterministic) order.

\begin{description}
  \item [Single] Every small-step consists of 1 transition.
  \item [Many] A small step may consist of more than 1 transition.
\end{description}

If \textsc{Many} is chosen, additional options may be chosen for \emph{Small-Step Consistency} and \emph{Preemption}.

Small-step consistency options:
\begin{description}
  \item [Arena Orthogonal] Transitions can be taken together if their arenas do not overlap (similar to \textsc{Take One} for big-steps)
  \item [Source/Destination Orthogonal] Transitions can be taken together if their sources and destinations are respectively orthogonal, i.e. the lowest common ancestor of the sources and of the targets is an And-state.

  There are no existing BSML languages making use of this option, but it is mentioned in \cite{sabzali2010deconstructing} as ``interesting''.
\end{description}

Preemption options:
\begin{description}
  \item [Non-Preemptive] Transitions that are an \emph{interrupt} for one another can be taken together. One transition $t$ is an interrupt for another transition $t'$ if both transitions' sources are orthogonal to each other, and (a) the target of $t'$ is orthogonal to the source of $t$, but the target of $t$ is not orthogonal with the sources of either transition; or (b) the target of neither transition is orthogonal with the sources of the two transitions, but the target of $t$ is a descendant of the target of $t'$. Both cases are shown in Figure \ref{fig:interrupt}.

\begin{figure}
\centering
\begin{subfigure}[b]{.4\textwidth}
  \centering
  \includegraphics[width=1\linewidth]{interrupt1}  
  \caption{}
  % \label{fig:light_blink_flat}
\end{subfigure}%
\begin{subfigure}[b]{.4\textwidth}
  \centering
  \includegraphics[width=0.8\linewidth]{interrupt2}  
  \caption{}
  % \label{fig:light_hierarchy}
\end{subfigure}
\caption{Interrupting transitions}
\label{fig:interrupt}
Figure taken from \cite{sabzali2010deconstructing}
\end{figure}

  \item [Preemptive] Transitions that are an interrupt for one another cannot be taken together. No priority is assigned to the interrupting or the interruptee transition.
\end{description}

Note that, at least for statecharts, the semantics of \textsc{Many} in combination with \textsc{Arena Orthogonal} and \textsc{Preemptive} can also be achieved by choosing \textsc{Combo Take One} and the Memory Protocol option \textsc{Combo-Step}, if \textsc{Present in Same} is not used. It is only when the \textsc{Source/Destination Orthogonal} or \textsc{Non-Preemptive} semantic options are desired, that \textsc{Many} is required.

\subsection{Applicability to statecharts}

Of the semantic aspects seen, most are applicable to statecharts. We decided not to support the following options:

\begin{itemize}
  \item Event Lifeline: \textsc{Present in Whole}, \textsc{Present in Same}

  Both options can create \emph{non-causal} big-steps, i.e. big-steps containing transitions that were triggered by transitions executed \emph{after} them.  This may lead to transitions being fired because they enable \emph{each other}, instead of being fired as a direct or indirect result of the set of inputs. This can be counter-intuitive, and may also be complex to implement. \cite{sabzali2010deconstructing} states that static detection of the possibility of non-causal big-steps is undecidable for languages supporting variables, such as statecharts.

  \item Order of Small-Steps: \textsc{Dataflow}

  \textsc{Dataflow} is quite difficult to implement: it would require advanced static analysis of a transition's  actions, determining the variables read and written. As we will see, our action language has conditional branches, making this difficult. For the moment, this feature is skipped. Support may be added later on.

  \item Concurrency: \textsc{Many}

  Allowing concurrency adds little, because combo-steps can be used to hide the effects of ``concurrent'' transitions from one another. Concurrency would allow for the \textsc{Source/Destination Orthogonal} option, but the authors of \cite{sabzali2010deconstructing} were not aware of any languages using it. Concurrency would also allow for the \textsc{Non-Preemptive} option, but this may be difficult to implement, and confusingly go against other restrictions chosen on what transitions are allowed to fire together in a big/combo-step.
\end{itemize}
% Day & Atlee: Summary of semantic options

% Applicability to Statecharts (with examples)
% - Big/Combo step maximality: totally applicable
% - Input/Internal event lifeline:
%   - synchronous options (SAME, WHOLE): perhaps not applicable
%   - non-synchronous options (REMAINDER, NEXT SMALL/COMBO STEP): totally applicable
% - GC/RHS Memory protocol: totally applicable
% - Priority + OOSS: totally applicable
% - Interface variables/events: perhaps applicable, but unsupported in SCCD
% - Concurrency: perhaps partially applicable
%   - arena orthogonal, src/dst orthogonal could be implemented
%   - preemption options probably not applicable

% Simon: De 'meaningful semantic combinations' zou je op dezelfde hoogte moeten zetten als de 'applicability of semantic options to Statecharts' (onder sectie 3 hierboven).