Stepping is arguably one of the most important operations for model execution, and model debugging specifically. Each formalism, however, has a diferent set of supported stepping operations (e.g., big step, combo step, and small step). Furthermore, many tools provide a diferent terminology for these diferent steps (e.g., small step, micro step, and epsilon step). As such, the exact semantics of stepping is unknown to the modellers, and might even difer between diferent tools. Additionally, tool developers have no framework to check whether they have implemented all useful stepping operations for their formalism. In this paper, we define a hierarchical terminology of stepping operations to provide a generalized vocabulary for both users and developers of debuggers. We distinguish four “levels” of stepping operations, related to the available knowledge in the execution trace. From a high to low level of abstraction, we term them simulation stepping, black-box stepping, white-box stepping, and implementation stepping. After introducing the framework and terminology, we apply it to a number of already existing debuggers for a large variety of formalisms.
Stepping through the execution of a program is arguably one of the most essential debugging operations a developer has available. Instead of observing the efects caused by the full execution of the program, stepping operations provide a way of controlling the execution manually. This serves diferent purposes: developers can get a view into the evolution of the execution state step-by-step, or even into how the evolution of the state is implemented in the simulator/executor. Stepping is thus a way of understanding the execution of a program, by exposing certain details of the execution algorithm and state information to the user.
Given its importance in the programming domain, stepping has frequently been ported to the (executable) model debugging domain as well. In this case, modellers can freely step through the execution of an executable model, as was the case with programs.
Many such executable modelling languages, or formalisms, exist,
each with their own set of tools to design, simulate, execute, and
debug. When it comes to stepping, formalisms (and their related
tools) may ofer a set of stepping operations at diferent level of
detail. For example, in program code debugging, a step into ofers a
view into the function called at the current line, while a step over
jumps over the line and shows the result of calling the function
at the current line. In other formalisms, the distinction is often
made between a big step and a small step. For example, in the DEVS
debugger presented in [
In contrast to most operational programming languages, which are line-based, models have a widely varying structure. Some models are similarly line-based (e.g., an explicitly modelled action language), whereas other are graph based (e.g., Petrinets) or a combination of multiple (e.g., Statecharts). The vocabularies used therefore difer from formalism to formalism, and even from debugger to debugger for the same formalism. We consider three potential issues due to this disparity in terminology. First, it makes it dificult for users of a tool to intuitively grasp the semantics of a given stepping operation in a tool for a given formalism. Second, tool developers cannot easily assess the completeness of the provided stepping operations, with respect to the level of detail that is being ofered by these stepping operations. Third, developers of a new language would benefit from a unified terminology to use as a prescription for the definition of the language’s semantics specification. This would further benefit the area of language design, and, more specifically, the modular design of language fragments.
In this paper, we define a hierarchical terminology of stepping semantics to provide a generalized vocabulary for both users and developers of debuggers. We distinguish four “levels” of stepping operations, related to the available knowledge in the execution trace. From a high to low level of abstraction, we term them simulation stepping, black-box stepping, white-box stepping, and implementation stepping. This leads to a framework, allowing to reason about debuggers for any type of formalism.
Structure. Section 2 introduces the language DEVS and its debugger, to serve as a running example. Section 3 explains our approach, which considers stepping at diferent levels based on the information exposed to the user. Section 4 applies our approach on a number of representative formalisms by categorizing their stepping operations using our vocabulary. Section 5 discusses the relevance of our framework to several areas of research. Section 6 discusses related work, and Section 7 concludes.
As a running example for this paper, we present the Discrete Event
System Specification (DEVS) formalism [
DEVS, and in particular Parallel DEVS [
M =< X , Y , S, δint , δex t , δconf , λ, ta, qinit >
where the input set X denotes the set of admissible input events
of the model. The output set Y denotes the set of admissible
output events of the model. The state set S is the set of sequential
states of the model. The internal transition function δint : S → S
defines the next sequential state, depending on the current state.
The output function λ : S → Y b defines the bag of output events
to be raised for a given sequential state, upon triggering the
internal transition function. The external transition function δex t :
Q × X b → S with Q = {(s, e)|s ∈ S, 0 ≤ e ≤ ta(s)} gets called
whenever an external input (∈ X ) is received. The time advance
function ta : S → R0+,+∞ defines the simulation time the system
remains in the current state before triggering its internal transition
function. The confluent transition function δconf : S × X b → S is
called if both an internal and external transition collide at the same
simulation time, replacing both functions. The initial total state
qinit = (s0, e0) ∈ Q defines the initial state of the model ( s0), and
how long the model has already been in this state (e0) [
A network of atomic DEVS models is called a coupled DEVS model. The output of one atomic DEVS model can be connected to the input of other atomic DEVS models using “channels”. For each channel, a transfer function can be defined to translate output to input events. Parallel DEVS is closed under coupling, which means that coupled models can be nested to arbitrary depth.
An abstract simulator for Parallel DEVS, which computes the
next state of the system (a “step”) until its end condition is satisfied,
is described in [
We previously presented a debugger for Parallel DEVS [
To demonstrate the diferent levels of granularity at which bugs can be found, we consider an example system: a trafic light. To keep it simple, we consider only two requirements: (1) the trafic light should continuously cycle between the three lights in this order: green, yellow, red, green, yellow, red, . . . , (2) the trafic light should stay green for 57 seconds, stay yellow for 3 seconds, and stay red for 60 seconds.
Our system consists of one atomic model, defined in Equation 1.
Light = ⟨Xl, Yl, Sl, δint,l, δext,l, δconf,l, λl, tal, qinit,l⟩ (1) Xl = {} Yl = {display_red, display_дreen, display_yellow }
Sl = {red, дreen, yellow } δint, l = {дreen → yellow, yellow → red, red → дreen} δext, l = {} δconf, l = {} λl = {дreen → [display_дreen], yellow → [display_yellow], red → [display_red]} tal = {дreen → 57, red → 60, yellow → 3} qinit, l = {red, 60}
We assume that a test suite is also constructed that checks for the satisfaction of both requirements. When executing the test suite, a failure is noticed, thereby meaning that at least one of the requirements is not satisfied. This will form the starting point of our debugging eforts. 3
We now present our hierarchical stepping operations and the
proposed unified vocabulary, applied to the running example. It is
based on an analysis of the diferent levels of traces in a simulation
or execution run, where each level increases the amount of detail
ofered to the user of the debugger. As presented in [
Depending on the debugger, diferent levels of detail can be offered. We argue that there are four such levels, and we claim that they are hierarchical, as shown in Figure 1. Intuitively, when switching to a lower level, more information is exposed to the user. The ifrst level is the requirements level, which determines which requirement is not satisfied. An arbitrary number of input/output traces exist that can lead to the requirement failing; at the input/output (second) level, the externally observable behaviour of the model that lead to the requirement not being satisfied is exposed. Similar observations hold for lower levels of abstraction. At the state trace (third) level, which shows the trace of internal (globally consistent) states that lead to the faulty input/output trace. At the implementation (fourth) level, the outcome of the intermediate (i.e., non-stable) simulator states that lead to the faulty state trace is exposed. All four levels are related to the execution trace, presenting to the user diferent levels of detail. 3.1
At the top-most level (the requirement level), the corresponding step is the simulation step. This step simulates the whole system and reports back the result: either the requirement is satisfied or it is not. As a debugging operation, it merely signals which requirement was not satisfied. While it is not a traditional debugging operation, as it is exactly the same as ordinary simulation, it is important to include it here at the root of our hierarchy. A single simulation step takes the model to its final state, defined using a termination condition (e.g., after 1000 seconds of simulated time).
Running Example. In the context of our running example, simulation stepping for the two test cases made for validating the requirements signals that requirement 2 is violated: the trafic light does not display the correct colour for a long enough period of time. At this level, we have no further insights in the model; we will have to go to a lower level of abstraction. 3.2
One level down from the simulation step is the black-box step. Since generally the validation of the requirements is based on some type of query over the input/output trace, this step makes use of the input/output trace generated during the simulation in which the requirement was not satisfied. It provides a view on the externally observable behaviour: a trace of the input and output of the model under study. These steps are “black-box”, in the sense that they consider the model as a black box that accepts input and produces output. Our framework is agnostic to the type of trace: it could be discrete (a finite number of events in any finite time interval) or continuous (an infinite number of events in any finite time interval). In our example, we focus on discrete traces.
A single black-box step takes the model from one externally observable event to another. This means that we extend the set of reachable configurations to those points in time where an input or output event occurs. All intermediate configurations are unreachable and might not even exist.
Running Example. In the context of our running example, blackbox stepping would give us the trace shown in Figure 2. As can be seen, this simple model has no input events, but has several output events. From these outputs, it is clear that the requirements are indeed not satisfied, as, for example, the time between the display_green and display_yellow is not equal to 57. To attempt to ifnd the cause, we will have to observe the state of the model. 3.3
One level down from the black-box step is the white-box step. This step makes use of all the knowledge from the black-box step, but additionally includes information on the internal state of the model. The internal state–consisting of variable values, instruction pointer, internal configuration, . . . , depending on the formalism–can evolve autonomously (without an input event driving the state change) and does not necessarily lead to an output event. But the internal state trace leading up to behaviour visible in the input/output trace is important towards finding the source of a failure. A single whitebox step takes the model from one globally consistent state to another. This means that we further extend the set of reachable configuration with the point in time where a state change occurs, even if the state changes to itself. All intermediate configurations are unreachable and might not even exist.
Running Example. In the context of our running example, whitebox stepping gives us the trace shown in Figure 3. There are no additional points in simulated time that we can step to, but we gain insight into the state evolution of the model. In this case, we see that the state and events are desynchronized: the event display_green is shown right before the state changes to yellow. This gives an additional direction for our search, but it does not pinpoint the error in the model yet. For that, we will have to dig deeper. 3.4
One level down from the white-box step is the implementation step. This step makes use of all the knowledge from the white-box step, but additionally includes information about the execution order within the simulator. State changes are always the result of some (complex) processing steps within the simulator. These steps expose implementation details of the simulator used, which are usually shielded: models specify what a system does, not how it does it. As input state
Red Yellow
Green output state
Red Yellow
Green a result, an implementation step can expose non-reachable (globally inconsistent) states in a set of “phases” the simulator goes through to compute the next reachable state. For example, in the context of DEVS, implementation steps are at the level of computing output functions and performing transitions. One implementation step might thus cause the execution of the output functions, and the next implementation step might compute the internal transitions.
Running Example. In the context of our running example, implementation stepping gives us the trace shown in Figure 4. As can be seen, the information is exactly the same as before, but now the “instantaneous” jumps between stable states get broken down in the various implementation steps that were necessary. By looking at the sequence of these calls, as well as the arguments passed, we notice that for each transition, the output function is invoked before the transition itself. Given this knowledge, which is part of the DEVS execution semantics, our defect becomes clear: when transitioning to the green state, the output function is invoked on the red state (with λ(red) = show_red). This is an often made mistake when modelling with DEVS; it can easily be fixed by updating the output function to the one shown in Equation 2.
λ = {red → [display_дreen], дreen → [display_yellow], yellow → [display_red]} (2) Rerunning the test suite shows that the model satisfies both requirements now. 4
To demonstrate the usefulness of our vocabulary as a framework for classifying debugging operations, we apply it to a number of representative formalisms. The goal is to show that we can apply the framework to formalisms with widely difering semantics. Each formalism is presented in turn, with some motivation for its inclusion, and then its stepping semantics is discussed. The “simulation step” is the same for all formalisms (i.e., run the simulation from beginning to end) and is therefore not discussed.
Causal Block Diagrams (CBD) [
Statecharts (SCs) [
Action Language (AL) [
Petri Nets (PN) [
This section discusses the relevance of this contribution to several areas where it can be useful: analyzing the completeness of tools, modularly building hybrid languages, and the development of domain-specific languages. 5.1
For tool developers, and in particular developers of model debuggers, there currently is no way of analyzing whether the set of operations the tool provides is complete, in the sense that all useful operations are implemented. Our vocabulary can act as a framework for these developers, with which they can decide at which level debugging support is ofered. While from the user’s point of view it is ideal to have debugging support at all the levels we defined, this might not be feasible or even desirable for practical reasons (e.g., too low level of abstraction), as well as for the protection of intellectual property (e.g., do not reveal simulation algorithm). But even then, our vocabulary allows reasoning about such concerns and make an informed decision at which level(s) stepping operations are provided. 5.2
An interesting application of our vocabulary is the design of hybrid
languages. Such languages are often the result of composing both
the syntax and semantics of two existing languages. These
compositions are often either parallel (i.e., two simulation algorithms are
interleaved), or hierarchical (i.e., the simulation algorithm of the
“child” formalism is called at certain points in the simulation
algorithm of the “parent” formalism). Languages such as BCOoL [
Defining debuggers for new domain-specific languages is now mostly done ad-hoc, and is based on the knowledge of the language designer. For a user of these languages, it is not necessarily clear from the onset what each stepping operation performs if no common vocabulary is used. Our vocabulary can therefore be used as an “interface” between the language designer and the language user to avoid misunderstandings and improve the usability of the language and its tools. For the language designer, it becomes possible to approach the design of stepping operations from the bottom up, instead of top-down as we presented in this paper. Since the language designer has control over the simulation algorithm, it might be easier to view the implementation trace as the source of all information. Subsequent higher levels of traces (the state trace, input/output trace, and simulation trace) can then be obtained by successively filtering the traces. This can aid the language developer to more intuitively define stepping semantics at each level. 6
The step operation has its roots in code debugging [
white-box steps in our vocabulary. Certain debuggers also ofer stepping support at the assembly instruction level, which in our vocabulary is classified as an implementation step.
Most model debuggers ofer a stepping operation. For example,
Vangheluwe et al. [
big step and small step operation
for the Causal Block Diagrams formalism, based on the simulation
algorithm presented earlier in this paper. They do not consider
input/output steps, however. Van Mierlo defines debugging support
for a large set of formalisms [
In other work, the notion of a simulator “step” is important as
well, either to classify language variants based on how they
implement a hierarchy of steps, or to analyze simulation algorithms and
possibly combine them at diferent levels of steps. Esmaeilsabzali
et al. [
This paper defines a vocabulary to classify stepping operations at diferent levels of granularity. We distinguish between simulation, black-box, white-box, and implementation steps. These correspond to the level at which information is presented to the user: respectively at the requirement, input/output trace, state trace, and implementation trace level. We apply this vocabulary on a running example in the DEVS formalism and then generalize to a set of semantically varying formalisms, demonstrating its wide applicability. In future work, this vocabulary can be refined and used as a basis for building new debugging techniques and tools for (domain-specific) formalisms, and used as a basis for other, related research areas such as modular language design.
This work was partly funded by a PhD fellowship from the Research Foundation - Flanders (FWO). This research was partially supported by Flanders Make vzw, the strategic research centre for the manufacturing industry.