TranslatingSCCDtoDEVS/paper/02-Background.tex

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

\section{Statecharts and Class Diagrams (SCCD)}
\subsection{The Statechart Formalism}
Statecharts, originally introduced by D. Harel (\ref{TODO}), are finite state machines extended with hierarchy and 
orthogonality (parallelism), allowing a complex system to be expressed in a more compact and elegant way.

In order to understand the basics of statecharts, it is useful to first look at higraphs. Higraphs, while normally used 
for formal mathematical specification, are also used as a basis for statecharts.

Statecharts can be represented as visual objects. While this thesis does not use a visual notation for the statecharts, 
it is usefull to understand the basics of statecharts. To understand the basics of statecharts, it is useful to first 
look at higraphs. Higraphs, while normally used for formal mathematical specification, are also used as a basis for 
statecharts. 

\subsubsection{Higraph}
A higraph combines notions from several topovisual formalisms.

Topovisual formalisms are a class of graphical representations to model and visualize the topological structure of systems. 
They primarily focus on depicting the spatial relationships and connectivity between various components or entities within 
a system. The shapes of the visual objects is not that important in these formalisms.

One of these topovisual formalisms is the formalism of graphs, and the second is the notion of Euler circles, which later 
evolved into Venn diagrams.

A graph, in its most basic form, is simply a set of points, or nodes, connected by edges or arcs. Its role is to represent 
a (single) set of elements S and some binary relation R on them. The precise meaning of the relation R is part of the 
application and has little to do with the mathematical properties of the graph itself. Certain restrictions on the relation 
R yield special classes of graphs that are of particular interest, such as ones that are connected, directed, acyclic, 
planar, or bipartite.

A somewhat less widely used extension of graphs is the formalism of hypergraphs. A hypergraph is a graph in which the 
relation being specified is not necessarily binary. Formally, an edge no longer connects a pair of nodes, but rather a 
subset thereof.
\\
\\
TODO: Euler circles or Venn diagram
\\
\\
These previous formalisms can be used to create the Highgraph construct. Venn diagrams are used to account for set 
inclusion and exclusion. Each set is called a blob and is denoted using a rectangle with rounded edges. The nesting of 
curves denotes set inclusion.





\subsubsection{Statecharts}
Statecharts are a higraph-based extension of standard state-transition diagrams, where the blobs represent states and 
arrows represent transitions. However, there are different kind of blobs and thus different kind of states. The 
different kind of states can be seen in Figure \ref{TODO}. The first blob, Figure \ref{TODO}, is called a BASIC-blob 
which is a state such that it has no sub-OR-blobs, sub-AND-blobs nor any sub-BASIC-blobs. OR-blobs are blobs that have 
one or more sub-OR-blobs. AND-blobs, Figure \ref{TODO}, have orthogonal components. Orthogonal components of a blob are 
normally drawn with a dashed line and denote concurrent operations. An example combining all these different kind of 
blobs can be seen in Figure \ref{TODO}. These blobs only introduce hierarchy in statecharts, the order to specify system 
dynamics in the diagrams are not yet specified. This is what transitions are used for. A transition is simply an arrow 
which indicates the system can change its current state from the source state of the transition to the destination state 
of the transition. Transitions are labeled as follows:
\begin{equation}
    e [c]/a
\end{equation}
This syntax denotes that the transition fires when event e occurs and condition c is true. The $/a$ usually means one of 
two different things, depending on the variant of statechart. In some definitions, $/a$ denotes that upon firing the 
transition, the a event is broadcast throughout the entire statechart, which may trigger more transitions. In the UML 
definition, $/a$ usually denotes a series of actions (such as computer code) to execute, upon firing the transition. The 
UML suggests the potential use of a function $GEN(e)$ , which can be one the many steps in a. This function is used to 
broadcast the event e. Most statechart variants combine these two aspects.

There are different kinds of transitions. First, there is the initial transition. It is the default transitions that 
fires upon entering any type of blob or the root. They force the diagram to be deterministic by denoting which is the 
current state upon entering an OR-blob. They are usually drawn as a small filled-in circle with the connected transition 
pointing towards a blob and may only be labeled with an action (no trigger event $e$).







\subsection{State Chart XML (SCXML)}
State Chart XML (SCXML) is a general-purpose event-based state machine language that combines concepts from CCXML and Harel 
State Tables. 

\subsubsection{Core constructs}

\paragraph{$<$scxml$>$}
The top-level wrapper element, which carries version information. It can consist of the following attributes:


















\subsection{Statecharts and Class Diagrams (SCCD)}
In this section the SCCD (a Statecharts and Class Diagrams hybrid) formalism and its SCCDXML representation, an extension 
of SCXML, is explained. SCCD facilitates the specification of complex timed, reactive, interactive discrete-event systems 
(e.g., complex user interfaces).

\subsubsection{The SCCD language}
The SCCD languages extends the SCXML, explained in subsection (TODO), by adding new features to its concrete syntax.

\paragraph{Top-level Elements}
The top-level element is a diagram. It has an input/output interface to communicate with its environment, it can optionally 
import library classes, and it holds a number of class definitions. One of these classes is the default, and is instantiated 
when the application is launched.

% TODO: Listing

Listing (TODO) shows the top-level diagram of an application. It imports a library class that is used to draw the graphical 
elements on the screen, one input port called "input" which receives events when the user interacts with the UI (for example, 
pressing a key), and four classes, explained in the following subsections.

\paragraph{Classes}
Classes are the main addition of the SCCD language. They model both structure and behaviour—structure in the form of 
attributes and relations with other classes, behaviour in the form of methods, which access and change the values of 
attributes of the class, and an SCXML model, which constitutes the "modal" part of the system, modelling the control flow 
of the class's behaviour. At runtime, a class can be instantiated, which creates an object. Objects are initialized according 
to the class's constructor, and can be deleted, invoking the class's destructor. The relationships modelled between classes 
are instantiated at runtime in the form of links. They serve as communication channels, over which objects can send and receive 
events.

% TODO: Listing

Listing 2 shows the definition of the "Ball" class. It defines a number of relations (discussed in the next paragraph), a 
constructor and destructor, a method that moves the ball to a new position, and an SCXML model that consists of four states. 
It can optionally also define private input ports and output ports. In this case, the ball defines a private input port, that 
allows the environment to send events that are only meant for a particular ball. For example, when the user left-clicks on a 
ball to select it, that event should only be sent to that specific instance.

\paragraph{Relationships}
Classes can have relationships with other classes. There are two types of relationships: associations and inheritance.

An association is defined between a source class and a target class, and has a name. It allows instances of the source class 
to send events to instances of the target class by referencing the association name. An association has a multiplicity, 
defined as a minimal cardinality $c_{min} \in \mathbb{N}$ and a maximal cardinality $c_{max} \in \mathbb{N}_{>0} \cup \{inf\}$. 
They control how many instances of the target class have to be minimally associated to each instance of the source class, and 
how many instances of the target class can be maximally associated to each instance of the source class, respectively. Each 
time an association is created, it results in a link between the source and target object. This link gets a unique identifier, 
allowing the source object to reference the target, for example to send events.

An inheritance relation results in the source of the relation to inherit all attributes and methods from the target of the 
relation. Specialisation of modal behaviour (i.e., (parts of) the SCXML model of the superclass) is currently not supported.

% TODO: Listing

Listing (TODO) shows the relationships of the "Window" class. It has an association to its parent, the main application. 
Exactly one instance of that link has to exist between each "Window" instance and the main application. It is additionally 
associated to a number of buttons and balls, and inherits from the library class "UIWidget", allowing it to be drawn on screen.

\paragraph{Events}
Events in SCCD are strings. They are accompanied by a number of parameter values: the sender is obliged to send the correct 
number of values, and the receiver declares the parameters when catching the event. Each parameter has a name, that can be used 
as a local variable in the action associated with the transition that catches the event.

With the addition of a public input/output interface using ports, as well as classes and associations, comes the need for 
scoping events. In traditional SCXML models, an event is sensed by the Statecharts model that generated it. SCCD adds the ability 
to transmit events to class instances and to output ports. In particular, the raise tag was extended with a scope attribute, that 
can take on the following values:
\begin{itemize}
    \item \textbf{local:} The event will only be visible for the sending instance.
    \item \textbf{broad:} The event is broadcast to all instances.
    \item \textbf{output:} The event is sent to an output port and is only valid in combination with the output attribute, which 
    specifies the name of the output port.
    \item \textbf{narrow:} The event is narrow-cast to specific instances only, and is only valid in combination with the target 
    attribute, which specifies the instance to send the event to. For example, an instance of the "Window" class can narrow-cast 
    an event by sending the event to a specific instance of the "Ball" class, identified by a unique link identifier.
    \item \textbf{cd:} The event is processed by the object manager. See the next section for more details.
\end{itemize}
% TODO: Listing 
Listing (TODO) presents a transition modelled on the "Button" class. It reacts to the user left-clicking the button (represented 
by an event sent on the button input port). The button reacts by notifying its parent that it was clicked.

\subsubsection{The Object Manager}
At runtime, a central entity called the object manager is responsible for creating, deleting, and starting class instances, as 
well as managing links (instances of associations) between class instances. It also checks whether no cardinalities are violated: 
when the user creates an association, it checks that the maximal cardinality is not violated, and when the user deletes an 
association, it check whether the minimal cardinality is not violated. As mentioned previously, instances can send events to the 
object manager using the "cd" scope. The object manager can thus be seen as an ever-present, globally accessible object instance, 
although it is implicitly defined in the runtime, instead of as a SCCD class.

When the application is started, the object manager creates an instance of the default class and starts its associated Statecharts 
model. From then on, instances can send several events to the object manager to control the set of currently executing objects. 
The object manager accepts four events. We list them below, including the parameters that have to be sent as part of the event:
\begin{itemize}
    \item \textbf{create\_instance(association name, class name, args*):}
    \item \textbf{delete\_instance(link\_ref):}
    \item \textbf{start\_instance(link\_ref):}
    \item \textbf{associate\_instance(source\_ref, association\_name, target\_ref):}
\end{itemize}

% TODO: Verder aanvullen

\subsubsection{The SCCD compiler}
The semantics of an SCCD model are loosely based on the agent model, where each instance of a class can be seen as an agent that 
communicates with other agents through its input/output interface, and its autonomous behaviour controlled by its Statecharts 
model. The compiler generates appropriate code that continuously executes the system by allowing each agent to execute a step, 
which optionally generates output that can be sensed by the other agents.

The compiler supports two programming languages, Javascript and Python, and options for the statecharts semantics. Supporting 
multiple languages is a major advantage, as one can imagine developing an application in SCCD and generating code for multiple 
languages from the same model. The generated code would exhibit identical behaviour for each implementation language, such as a 
web-based application (implemented in HTML/Javascript) and a desktop application (implemented in, for example, Python).

SCCD has one semantic definition. There are, however, many platforms on which the code generated from an SCCD model can be run. 
The runtime platform provides essential functions used by the runtime kernel, such as the queueing of events and the scheduling 
of (timed) events. Three runtime platforms are supported. A platform holds a list (or queue) of events, and they differ in the 
way they handle events generated during execution. The kernel attempts to run the SCCD model in real-time, meaning that the delay 
on timed transitions is intepreted as an amount of seconds. Raising of events and untimed transitions are executed as fast as 
possible. Figure (TODO) presents an overview of the three platforms, and how they handle events.

The most basic platform, available in most programming languages, is based on threads. Currently, the platform runs one thread, 
which manipulates a global event queue, made thread-safe by locks. Input from the environment is handled by obtaining this lock, 
which the kernel releases after every step of the execution algorithm. This allows external input to be interleaved with 
internally raised events. Running an application on this platform can interfere with other scheduling mechanisms, such as a UI 
module, however.

To overcome this interference problem, the event loop platform reuses the event queue managed by an existing UI platform, such 
as Tkinter. The UI platform provides functions for managing time-outs (for timed events), as well as pushing and popping items 
from the queue. This results in a seamless integration of both Statecharts events and external UI events, such as user clicks: 
the UI platform is now responsible for the correct interleaving.

The game loop platform facilitates integration with game engines (such as the open-source Unity engine), where objects are 
updated only at predefined points in time. In the "update" function, the kernel is responsible for checking the current time 
(as some time has passed since the last call to the "up-date" function), and process all the events generated by objects. This 
means that events generated in between two of these points are not processed immediately, but queued and their processing delayed 
until the next processing time.

\subsubsection{Semantics}
The Statecharts language has been around for a long time. In that time, its basic structures have almost not changed. In its 
original definition [(TODO)], Harel left many of the semantic choices undefined. Since then, many semantics have been defined, 
such as the one used in Statemate [(TODO)]. More recently, Esmaeilsabzali et al. [(TODO)] have performed a study of big-step 
modelling languages, such as Statecharts, and defined a set of semantic variation points, with which the different Statecharts 
execution semantics can be classified. Central to their discussion is the notion of a "big step". The execution of a Statecharts 
model is a sequence of big steps. A big step is a unit of interaction between a model and its environment. A big step takes input 
from the environment (at the beginning of the big step), and produces output to the environment (after the big step has taken 
place). Input cannot change during the big step. A big step consists of 0 or more small steps. A small step is an unordered set 
of 1 or more transition executions, but in our case, a small step always consists of exactly one transition execution. Small steps 
are grouped in so-called combo steps. A combo step is a maximal sequence of small steps, such that it only contains transitions 
that are orthogonal to each other.

The SCCD compiler allows to choose which semantics to use based on a number of semantic variation points. This gives modellers 
more control to fine-tune the application to their needs. The semantic variation points are:
\begin{itemize}
    \item \textbf{Big Step Maximality} specifies when a big step ends: either after one combo step executed (Take One), or when 
    no more combo steps can be executed (Take Many).
    \item \textbf{Internal Event Lifeline} specifies when an internally raised event becomes available: either in the next small 
    step (immediately), in the next combo step (which only makes sense in combination with the Take Many option), or the event is 
    queued and treated as an external event (making it available in the next big step).
    \item \textbf{Input Event Lifeline} specifies when an input event is available during a big step: either throughout the first 
    small step, the first combo step, or throughout the whole big step.
    \item \textbf{Priority} specifies what to do when two transitions are enabled at the same time, where the source state of one 
    of the transitions is the ancestor of the source state of the other transition. Either the transition of the ancestor gets 
    priority (Source-Parent), or the transition of the (indirect) child gets priority (Source-Child).
\end{itemize}


\section{DEVS Formalism}
The Discrete Event System Specification (DEVS)
formalism was first introduced by Zeigler (TODO) in 1976 to provide a rigourous common basis for discrete-event modelling and 
simulation. For the class of formalisms denoted as discrete-event (TODO), system models are described at an abstraction 
level where the time base is continuous (TODO), but during a bounded time-span, only a finite number of relevant events 
occur. These events can cause the state of the system to change. In between events, the state of the system does not 
change. This is unlike continuous models in which the state of the system may change continuously over time. As an 
extension of Finite State Automata, the DEVS (Discrete Event Systems) formalism captures concepts from Discrete Event 
simulation. As such it is a sound basis for meaningful model exchange in the Discrete Event realm. (TODO: citation)

The DEVS formalism fits the general structure of deterministic, causal systems in classical systems theory. DEVS allows 
for the description of system behaviour at two levels. At the lowest level, an atomic DEVS describes the autonomous 
behaviour of a discrete-event system as a sequence of deterministic transitions between sequential states as well as 
how it reacts to external input (events) and how it generates output (events). At the higher level, a coupled DEVS 
describes a system as a network of coupled components. The components can be atomic DEVS models or coupled DEVS in their 
own right. The connections denote how components influence each other. In particular, output events of one component 
can become, via a network connection, input events of another component. It is shown in [Zei84a] how the DEVS formalism 
is closed under coupling: for each coupled DEVS, a resultant atomic DEVS can be constructed. As such, any DEVS model, 
be it atomic or coupled, can be replaced by an equivalent atomic DEVS. The construction procedure of a resultant atomic 
DEVS is also the basis for the implementation of an abstract simulator or solver capable of simulating any DEVS model. 
As a coupled DEVS may have coupled DEVS components, hierarchical modelling is supported. In the following, the different 
aspects of the DEVS formalism are explained in more detail.

\subsection{The atomic DEVS Formalism}
The atomic DEVS formalism is a structure describing the different aspects of the discrete-event behaviour of a system:
\begin{equation}
    atomicDEVS \equiv \langle S, ta, \delta_{int}, X, \delta_{ext}, Y, \lambda \rangle
\end{equation}
The time base $T$ is continuous and is not mentioned explicitly
\begin{equation}
    T = \mathbb{R}
\end{equation}
The state set $S$ is the set of admissible sequential states: the DEVS dynamics consists of an ordered sequence of states
from $S$. Typically, $S$ will be a structured set (a product set)
\begin{equation}
    S = \times_{i=1}^{n} S_i.
\end{equation}
This formalizes multiple (n) concurrent parts of a system. It is noted how a structured state set is often synthesized
from the state sets of concurrent components in a coupled DEVS model. 

The time the system remains in a sequential state before making a transition to the next sequential state is modelled by 
the time advance function
\begin{equation}
    ta: S \rightarrow \mathbb{R}^+_{0, + \infty}.
\end{equation}
As time in the real world always advances, the image of $ta$ must be non-negative numbers. $ta = 0$ allows for the 
representation of instantaneous transitions: no time elapses before transition to a new state. Obviously, this is an 
abstraction of reality which may lead to simulation artifacts such as infinite instantaneous loops which do not correspond 
to real physical behaviour. If the system is to stay in an end-state $s$ forever, this is modelled by means of $ta(s) = +\infty$.

The internal transition function
\begin{equation}
    \delta_{int}: S \rightarrow S
\end{equation}
models the transition from one state to the next sequential state. $\delta_{int}$ describes the behaviour of a Finite State 
Automaton; $ta$ adds the progression of time.

It is possible to observe the system output. The output set $Y$ denotes the set of admissible outputs. Typically, $Y$ will be a 
structured set (a product set)
\begin{equation}
    Y = \times_{i=1}^l Y_i.
\end{equation}
This formalizes multiple ($l$) output ports. Each port is identified by its unique index $i$. In a user-oriented modelling 
language, the indices would be derived from unique port names. 

The output function
\begin{equation}
    \lambda : S \rightarrow Y \cup \{ \phi \}
\end{equation}
maps the internal state onto the output set. Output events are only generated by a DEVS model at the time of an internal 
transition. At that time, the state before the transition is used as input to $\lambda$. At all other times, the non-event 
$\phi$ is output. To describe the total state of the system at each point in time, the sequential state $s \in S$ is not 
sufficient. The elapsed time $e$ since the system made a transition to the current state $s$ needs also to be taken into 
account to construct the total state set
\begin{equation}
    Q = \{ (s,e) | s \in S,, 0 \leq e \leq ta(s)\}
\end{equation}
The elapsed time $e$ takes on values ranging from 0 (transition just made) to $ta(s)$ (about to make transition to the next
sequential state). Often, the time left $\sigma$ in a state is used:
\begin{equation}
    \sigma = ta(s) - e
\end{equation}
Up to now, only an autonomous system was described: the system receives no external inputs. Hence, the input set $X$ 
denoting all admissible input values is defined. Typically, $X$ will be a structured set (a product set)
\begin{equation}
    X = \times_{i=1}^m X_i
\end{equation}
This formalizes multiple ($m$) input ports. Each port is identified by its unique index $i$. As with the output set, 
port indices may denote names. 

The set $\Omega$ contains all admissible input segments $\omega$
\begin{equation}
    \omega : T \rightarrow X \cup \{ \phi \}
\end{equation}
In discrete-event system models, an input segment generates an input event different from the non-event $\phi$ only at a finite 
number of instants in a bounded time-interval. These external events, inputs $x$ from $X$, cause the system to interrupt its 
autonomous behaviour and react in a way prescribed by the external transition function
\begin{equation}
    \delta_{ext}: Q \times X \rightarrow S
\end{equation}
The reaction of the system to an external event depends on the sequential state the system is in, the particular input and 
the elapsed time. Thus, $\delta_{ext}$ allows for the description of a large class of behaviours typically found in 
discrete-event models (including synchronization, preemption, suspension and re-activation). When an input event $x$ to an 
atomic model is not listed in the $\delta_{ext}$ specification, the event is ignored.

% TODO: Example of traffic light/ Starts with "In Figure 1" ...

\subsection{The coupled DEVS Formalism} 
The coupled DEVS formalism describes a discrete-event system in terms of a network of coupled components.
\begin{equation}
    coupledDEVS \equiv \langle X_{self}, Y_{self}, D, \{M_i\}, \{I_i\}, \{Z_{i,j}\}, select \rangle
\end{equation}
The component $self$ denotes the coupled model itself. $X_{self}$ is the (possibly structured) set of allowed external inputs 
to the coupled model. $Y_{self}$ is the (possibly structured) set of allowed (external) outputs of the coupled model. $D$ is 
a set of unique component references (names). The coupled model itself is referred to by means of $self$, a unique reference 
not in $D$.

The set of components is
\begin{equation}
    \{M_i | i \in D\}.
\end{equation}
Each of the components must be an atomic DEVS
\begin{equation}
    M_i = \langle S_i, ta_i, \delta_{int, i}, X_i, \delta_{ext, i}, Y_i, \lambda_i \rangle , \forall i \in D.
\end{equation}
The set of influences of a component, the components influenced by $i \in D \cup \{self\}$, is $I_i$. The set of all influences 
describes the coupling network structure
\begin{equation}
    \{ I_i | i \in D \cup \{self\}\}.
\end{equation}
For modularity reasons, a component (including $self$) may not influence components outside its scope -the coupled model-, 
rather only other components of the coupled model, or the coupled model $self$:
\begin{equation}
    \forall i \in D \cup \{self\}: I_i \subseteq D \cup \{self\}.
\end{equation}
This is further restricted by the requirement that none of the components (including $self$) may influence themselves directly 
as this could cause an instantaneous dependency cycle (in case of a 0 time advance inside such a component) akin to an algebraic 
loop in continuous models:
\begin{equation}
    \forall i \in D \cup \{self\}: i \not \in I_i.
\end{equation}
Note how one can always encode a self-loop ($i \in I_i$) in the internal transition function.

To translate an output event of one component (such as a departure of a customer) to a corresponding input event (such as the 
arrival of a customer) in influencees of that component, output-to-input translation functions $Z_{i,j}$ are defined:
\begin{equation}
    \{ Z_{i,j} | i \in D \cup \{self\}, j \in I_i\}, \\
    Z_{self, j} : X_{self} \rightarrow X_j, \forall j \in D, \\
    Z_{i, self} : Y_i \rightarrow Y_{self}, \forall i \in D, \\
    Z_{i, j} : Y_i \rightarrow X_j, \forall i,j \in D.
\end{equation}
Together, $I_i$ and $Z_i,j$ completely specify the coupling (structure and behaviour).

As a result of coupling of concurrent components, multiple state transitions may occur at the same simulation time. This is 
an artifact of the discrete-event abstraction and may lead to behaviour not related to real-life phenomena. A logic-based 
foundation to study the semantics of these artifacts was introduced by Radiya and Sargent (TODO). In sequential simulation 
systems, such transition collisions are resolved by means of some form of selection of which of the components' transitions 
should be handled first. This corresponds to the introduction of priorities in some simulation languages. The coupled DEVS 
formalism explicitly represents a select function for tie-breaking between simultaneous events:
\begin{equation}
    select : 2^D \rightarrow D
\end{equation}
$select$ chooses a unique components from any non-empty subset E of D:
\begin{equation}
    select(E) \in E.
\end{equation}
The subset E corresponds to the set of all components having a state transition simultaneously.

\subsection{Closure of DEVS under coupling}
As mentioned before, it is possible to construct a resultant atomic DEVS model for each coupled DEVS. This closure under 
coupling of atomic DEVS models makes any coupled DEVS equivalent to an atomic DEVS. By induction, any hierarchically coupled 
DEVS can thus be flattened to an atomic DEVS. As a result, the requirement that each of the components of a coupled DEVS be 
an atomic DEVS can be relaxed to be atomic or coupled as the latter can always be replaced by an equivalent atomic DEVS.

The core of the closure procedure is the selection of the most imminent (i.e., soonest to occur) event from all the components' 
scheduled events (TODO). In case of simultaneous events, the select function is used. In the sequel, the resultant construction 
is described.

From the coupled DEVS
\begin{equation}
    \langle X_{self}, Y_{self}, D, \{M_i\}, \{I_i\}, \{Z_{i,j}\}, select \rangle
\end{equation}
with all components $M_i$ atomic DEVS models
\begin{equation}
    M_i = \langle S_i, ta_i, \delta_{int, i}, X_i, \delta_{ext, i}, Y_i, \lambda_i \rangle, \forall i \in D
\end{equation}
the atomic DEVS
\begin{equation}
    \langle S, ta, \delta_{int}, X, \delta_{ext}, Y, \lambda \rangle
\end{equation}
is constructed.

The resultant set of sequential states is the product of the total state sets of all the components
\begin{equation}
    S = \times_{i \in D} Q_i
\end{equation}
where
\begin{equation}
    Q_i = \{ (s_i, e_i) | s \in S_i, 0 \leq e_i \leq ta_i(s_i) \}, \forall i \in D.
\end{equation}
The time advance function $ta$
\begin{equation}
    ta : S \rightarrow \mathbb{R}^+_{0, + \infty}
\end{equation}
is constructed by selecting the most imminent event time, of all components. This means, finding the smallest time remaining 
until internal transition, of all the components
\begin{equation}
    ta(s) = \min \{\sigma_i = ta_i(s_i) - e_i | i \in D \}.
\end{equation}
A number of imminent components may be scheduled for a simultaneous internal transition. These components are collected in a 
set
\begin{equation}
    IMM(s) = \{i \in D | \sigma_i = ta(s)\}.
\end{equation}
From $IMM$, a set of elements of $D$, one component $i^*$ is chosen by means of the select tie-breaking function of the coupled 
model
\begin{equation}
    select : 2^D \rightarrow D \\
    IMM(s) \rightarrow i^*
\end{equation}
Output of the selected component is generated before it makes its internal transition. Note also how, as in a Moore machine, 
input does not directly influence output. In DEVS models, only an internal transition produces output. An input can only 
influence/generate output via an internal transition similar to the presence of memory in the form of integrating elements in 
continuous models. Allowing an external transition to produce output could lead to infinite instantaneous loops. This is equivalent 
to algebraic loops in continuous systems. The output of the component is translated into coupled model output by means of the 
coupling information
\begin{equation}
    \lambda(s) = Z_{i^*, self} (\lambda_{i^*}(s_{i^*})), \text{if} self \in I_{i^*}.
\end{equation}
If the output of $i^*$ is not connected to the output of the coupled model, the non-event $\phi$ can be generated as output of 
the coupled model. As $\phi$ literally stands for no event, the output can also be ignored without changing the meaning (but 
increasing performance of simulator implementations).

The internal transition function transforms the different parts of the total state as follows:
\begin{equation}
    \delta_{int}(s) = (..., (s'_j, e'_j),...), \text{where} \\
    (s'_j, e'_j) = (\delta_{int, j} (s_j), 0), \text{for} j = i^*, \\
                 = (\delta_{ext, j} (s_j, e_j + ta(s), Z_{i^*, j}))
                 % TODO: Verder doen
\end{equation}
The selected imminent component $i^*$ makes an internal transition to sequential state $\delta_{int, i^*} (s_i^*)$. Its elpased 
time is reset to 0. All the influencees of $i^*$ change their state due to an external transition prompted by an input which is 
the output-to-input translated output of $i^*$, with an elapsed time adjusted for the time advance $ta(s)$. The influencees' 
elapsed time is reset to 0. Note how $i^*$ is not allowed to be an influencee of $i^*$ in DEVS. The state of all other components 
is not affected and their elapsed time is merely adjusted for the time advance $ta(s)$.

The external transition function transforms the different parts of the total state as follows:
\begin{equation}
    \delta_{ext}(s,e,x) = (..., (s'_i, e'_i), ...)
    % TODO
\end{equation}
An incoming external event is routed, with an adjustment for elapsed time, to each of the components connected to the coupled 
model input (after the appropriate input-to-input translation). For all those components, the elapsed time is reset to 0. All 
other components are not affected and only the elapsed time is adjusted.

Some limitations of DEVS are that
\begin{itemize}
    \item a conflict due to simultaneous internal and external events is resolved by ignoring the internal event. It should be 
    possible to explicitly specify behaviour in case of conflicts;
    \item there is limited potential for parallel implementation;
    \item the select function is an artificial legacy of the semantics of traditional sequential simulators based on an event 
    list;
    \item it is not possible to describe variable structure.
\end{itemize}
Some of these are compensated for in parallel DEVS (TODO).

\subsection{Implementation of a DEVS Solver}
The algorithm in Figure (TODO) is based on the closure under coupling construction and can be used as a specification of a 
(possibly parallel) implementation of a DEVS solver or “abstract simulator” (TODO). In an atomic DEVS solver, the last event 
time $t_L$ as well as the local state $s$ are kept. In a coordinator, only the last event time $t_L$ is kept. The 
next-event-time $t_N$ is sent as output of either solver. It is possible to also keep $t_N$ in the solvers. This requires 
consistent (recursive) initialization of the $t_N$s. If kept, the $t_N$ allows one to check whether the solvers are 
appropriately synchronized. The operation of an abstract simulator involves handling four types of messages. The ($x, from, t$)
message carries external input information. The ($y, from, t$) message carries external output information. The ($*, from, t$) 
and ($done, from, t_N$) messages are used for scheduling (synchronizing) the abstract simulators. In these messages, $t$ is the 
simulation time and $t_N$ is the next-event-time. The ($*, from, t$) message indicates an internal event * is due.When a 
coordinator receives a ($*, from, t$) message, it selects an imminent component $i^*$ by means of the tie-breaking function 
select specified for the coupled model and routes the message to $i^*$. Selection is necessary as there may be more than one 
imminent component (with minimum next remaining time).

When an atomic simulator receives a ($*, from, t$) message, it generates an output message ($y, from, t$) based on the old state 
$s$. It then computes the new state by means of the internal transition function. Note how in DEVS, output messages are only 
produced while executing internal events. When a simulator outputs a ($y, from, t$) message, it is sent to its parent coordinator. 
The coordinator sends the output, after appropriate output-to-input translation, to each of the influencees of $i^*$ (if any). If 
the coupled model itself is an influencee of $i^*$, the output, after appropriate output-to-output translation, is sent to the the 
coupled model's parent coordinator.

% TODO: Figure 3 

When a coordinator receives an ($x, from, t$) message from its parent coordinator, it routes the message, after appropriate 
input-to-input translation, to each of the affected components.

When an atomic simulator receives an ($x, from, t$) message, it executes the external transition function of its associated atomic 
model.

After processing an ($x, from, t$) or ($y, from, t$) message, a simulator sends a ($done, from, t_N$) message to its parent 
coordinator to prepare a new schedule. When a coordinator has received ($done, from, t_N$) messages from all its components, 
it sets its next-event-time $t_N$ to the minimum $t_N$ of all its components and sends a ($done, from, t_N$) message to its parent 
coordinator. This process is recursively applied until the top-level coordinator or root coordinator receives a ($done, from, t_N$) 
message.


As the simulation procedure is synchronous, it does not support asynchronously arriving (real-time) external input. Rather, the 
environment or Experimental Frame should also be modelled as a DEVS component.

To run a simulation experiment, the initial conditions $t_L$ and $s$ must first be set in all simulators of the hierarchy. If $t_N$ 
s kept in the simulators, it must be recursively set too. Once the initial conditions are set, the main loop described in Figure 
(TODO) is executed.


\section{The pythonDEVS (pyDEVS) simulator}
In this chapter we first present an implementation of the classical formalism. An early prototype of a DEVS Modeling and Simulation 
Package is then introduced. The chapter then moves on to discuss a real-time execution framework. The motivation behind real-time 
DEVS execution is discussed as well as the implications of 0-time semantics.

\subsection{Design and implementation}
This version of the DEVS Modeling and Simulation Package has been implemented using Python, an interpreted, very high-level, 
object-oriented programming language. The package consists of two files, the first of which (DEVS.py) provides a class architecture 
that allows hierarchical DEVS models to be easily defined. The simulation engine (SE) itself is implemented in the second file 
(Simulator.py). Based on the DEVS simulator described in (TODO), it uses the same message- passing mechanism. A detailed description 
of both the model architecture and the SE follows.

\subsubsection{Model Architecture}
The model architecture implemented in DEVS.py is a canvas from which hierarchical DEVS models can be easily described. It consists 
of a number of classes arranged to capture the essence of hierarchical DEVS. A model is described in a dedicated file by deriving 
coupled and/or atomic- DEVS descriptive classes from this architecture. These atomic models are then arranged hierarchically through 
composition. Methods and attributes form the standard interface that allows an SE, such as the one described in the next sub-section, 
to interact with the instantiated DEVS model. Our main concern with the architecture are twofold: remain as consistent as possible 
with the original hierarchical DEVS definition, and maintain a flexible approach to DEVS so as to encourage model reusability 
through parameterization.

The class architecture is represented in Figure (TODO): BaseDEVS is the root class which provides basic functionalities common to both 
atomic and coupled models.

Two classes are inherited from BaseDEVS to deal with the specifics of atomic and coupled DEVS formalisms (Figure (TODO)). These three 
classes are all abstract in that they cannot be directly instantiated. Rather, a model is described by deriving descriptive classes 
from either the AtomicDEVS or the CoupledDEVS class. This provides them with a suitable constructor and overrides the default 
interface methods. Note that the constructors at every level of the class hierarchy have an active role. Hence, a descriptive class' 
constructor should always start by calling the parent class' constructor.

The constructor of the AtomicDEVS class merely initializes the myID attribute and provides a default initial value for the DEVS' 
total state, through the state and elapsed attributes. The remaining class definitions consist of default method declarations for 
the interface functions $\delta_{ext}$ (extTransition), $\delta_{int}$ (intTransition), $ta$ (timeAdvance) and $\lambda$ (outputFnc). 
These methods expect no parameter, and it is up to the modeler to be consistent with the corresponding functions' domain when overriding 
the methods. Except for outputFnc (which uses the poke method as described below), all the methods shall return a value compatible with 
the corresponding function range.

Since default values are provided for both attributes and methods, the minimal atomic-DEVS descriptive class is empty:

% TODO: code

This atomic-DEVS is passive. It remains in its default state forever. A more interesting example is a generator, which sends a message 
(the integer 1 in this case) through its unique output port at a constant time interval:

% TOOD: code

As mentioned above, the outputFnc returns no value; instead it relies on the poke method to send message (second parameter) through the 
OUT output port (first parameter). The companion method, peek, returns the message on the input port that is given as a unique parameter, 
and is used exclusively in the extTransition function. Both poke and peek methods are defined in the AtomicDEVS class, and should not be 
overridden.

The CoupledDEVS class only has one method to override, the tie-breaking select function. This takes a list of sub-models which are in 
conflict. The select function should return the sub-model instance from this list who's transition is to fire next. All a CoupledDEVS 
sub-models should be included by passing their instance variables to the addSubModel function.

Coupling of ports is performed through the connectPorts method. Its first parameter is the source port and the second parameter is the 
destination port. A coupling is rejected and an error message issued if the coupling is invalid.

The source and destination ports are instances of the class Port. This class defines channels where events may pass between DEVS models. 
These channels are defined in the Port's inLine and outLine attributes.

Consider the example of the situation illustrated in Figure (TODO). There exists a descriptive class SomeDEVS for a DEVS (either atomic 
or coupled) with an input and output port locally known as IN and OUT. We want to connect the input port to the output port of the 
SimpleGenerator atomic- DEVS described above: both DEVS must of course be children of the same coupled-DEVS for the coupling to be 
performed. The coupled-DEVS descriptive class is defined below.

% TODO: code

Note that the parameter to the constructor is used to parameterize the SimpleGenerator atomic- DEVS. As for atomic-DEVS, the constructor 
first calls the parent class' constructor. Note also that the coupled-DEVS itself has an output port. The first coupling is an internal 
coupling, while the second is an external output coupling. This is a complete definition for a coupled-DEVS descriptive class. The 
default select function is used.

Once all the descriptive classes in the hierarchical DEVS model have been defined, the whole model can be build by instantiating the 
root DEVS. This is possible since the hierarchical representation of the model is built by composition rather than aggregation.

As a final warning, note that recursive definitions are illegal, since they are incompatible with a tree structure. As a trivial example, 
a coupled-DEVS' descriptive class SomeCoupledDEVS cannot call in its constructor the addSubModel method with an instance of 
SomeCoupledDEVS. This is mentionned since such recursive constructs will not be detected.

\subsubsection{Simulation Engine}