research-article

Open access

From Lustre to Graphical Models and SCCharts

Authors:

Lena Grimm,

Steven Smyth,

Alexander Schulz-Rosengarten,

Reinhard von Hanxleden,

Marc PouzetAuthors Info & Claims

ACM Transactions on Embedded Computing Systems, Volume 23, Issue 5

Article No.: 66, Pages 1 - 28

https://doi.org/10.1145/3544973

Published: 14 August 2024 Publication History

PDF eReader

Abstract

We introduce a systematic approach for automatically creating a visual diagram, akin to the graphical Safety Critical Application Development Environment (SCADE) model, from a Lustre program. This not only saves tedious manual drawing effort but also enables modeling software to automatically provide the developer with different meaningful views for the same program. We also extend the Sequentially Constructive Charts (SCCharts) language with data-flow constructs that adhere to the Lustre semantics, which permits a translation from Lustre to graphical SCCharts. This allows using the SCCharts code generation, simulation, and visualization tooling also for Lustre programs, in addition to the already existing Lustre compilation techniques. Furthermore, we investigate how the sequentially constructive model of computation, used in SCCharts and other synchronous languages, can be used to conservatively extend Lustre. We have implemented and validated this work with the Eclipse-based open-source Kiel Integrated Environment for Layout Eclipse Rich Client (KIELER) framework.

1 Introduction

Traditionally, languages tend to fall into either the textual category, as is the case for most programming languages (C, Java, Python, ...), or the graphical category, as is the case for most modeling languages (UML, Simulink, Labview, ...). However, some languages already illustrate that these categories may well relate to each other. The Safety Critical Application Development Environment (SCADE) [1] is a modeling tool with a graphical syntax, but it also employs a textual language, referred to as Scade, which is semantically close to Lustre [2]. Similarly, the synchronous state-oriented language Sequentially Constructive Charts (SCCharts) [3] is primarily considered a graphical language, using a Statechart syntax, but since its beginning graphical SCCharts are synthesized automatically from a textual source.

We here explore, for the specific case of Lustre-like languages (elaborated further in Section 2), how we can make the best use of both textual and graphical representations when designing (complex) systems. We do so irrespective of the question of whether we consider this activity as “programming” or “modeling” [4], and we will use both terms in the following.

Compared to the process of typing in a textual program, possibly using a modern IDE with code completion, and so on, the creation of graphical models can be a rather time-consuming affair. Typically, graphical elements are dragged from a palette to a canvas, and the user can spend significant time on positioning elements, possibly moving other elements around to make room first. As models evolve, readability tends to suffer, unless users keep investing significant time just to keep things readable [5]. As a case in point, some SCADE users do not use the graphical editor for modeling, but instead use the textual Scade language that is behind the graphical interface of Safety Critical Application Development Environment (SCADE). However, for such textually written models, no graphical representation is available so far; SCADE translates graphical models into Scade, but there is no translation the other way. However, in particular for communication and documentation purposes, graphical models are appealing and useful. Arguably, this is why graphical languages have arisen in the first place, after textual languages have already been around for a long time.

In this article, we investigate how to go the other way, from textual synchronous data-flow to a graphical representation. In that we broadly follow the modeling pragmatics approach proposed by Fuhrmann et al. [6]. The main idea there is to separate a (textual) model from a (graphical) view of that model, and to automatically synthesize a view from the model. In fact, once such an automatic generation of a graphical view is possible, it is just a small step to synthesize different graphical views for one and the same model. As a perhaps somewhat extreme but hopefully illustrative comparison, the usual way of constructing graphical models may be likened to the work of a mechanical typesetter, who works directly on the appearance of a printed document (the “view”). In comparison, the modeling pragmatic way is more like working on a source that contains all the information (the “model”), as, for example, a tex-source file, from which a tool (e.g., LaTex) automatically constructs a printable document, whose exact appearance can vary, as governed e.g. by the style file provided by a publisher. Compared to the traditional way of graphical modeling, the modeling pragmatics approach has the obvious advantages of efficient textual editing, such as powerful IDE operations, revision control, and so on. In addition, one is liberated from having to work with just one fixed, hand-crafted graphical representation. Figure 1 illustrates this approach, synthesizing two views with different strategies for handling delay references, as detailed later.

Fig. 1.

Thus, put simply, the original question that motivated the work presented here was how to get from textual synchronous data-/control-flow (“Lustre”) to graphical representations (“SCADE”). While the basic concept to do so appears fairly straightforward, there are various options, as illustrated in this article. In the course of answering this original, pragmatics-oriented question, building on the concepts and diagramming infrastructure for the SCCharts language, it turned out that there were interesting semantic questions as well, which this article will also report on. Put briefly, the first semantic question is how to map Lustre to valid, semantically equivalent SCChart models. That is, we aimed to synthesize not just possibly somewhat abstract/informal diagrams, such as could be drawn up by a programmer for documentation purposes, to be used along the original code. We also wish to synthesize models that fully capture the textual source.

An advantage of using SCCharts is that a modeling/compilation framework that supports it is openly available, the Kiel Integrated Environment for Layout Eclipse Rich Client (KIELER). However, beyond that practical consideration, SCCharts are an interesting target in that they originally come from a control/state oriented modeling world, as opposed to Lustre, which has its origins in data-flow. Thus, when exploring a mapping from Lustre to SCCharts, we also touch on the broader question of how data-flow maps into control-flow, since the SCCharts compilation is based on control-flow. We do not aim to provide a general answer here, but, as illustrated in this article, at least in our setting such a transformation seems possible without significant cost. We see this as an indication that these worlds are not as separate as they sometimes are perceived.

Finally, the choice of SCCharts as a target leads to another question, raised by the underlying models of computation. SCCharts share with Lustre the basic synchronous principle that divides computation into discrete reactions/ticks and has a deterministic, concurrent semantics by abstracting from reaction time. The classic synchronous model of computation, also employed by Lustre, assumes that shared data have a unique value per tick. This simplifies semantic reasoning, and is a prerequisite, for example, for hardware synthesis. However, especially for programmers used to imperative languages, this requirement may be overly restrictive. This has motivated the sequentially constructivemodel of computation (SC MoC), which is employed by SCCharts. That MoC takes sequential scheduling information into account and gives a—still deterministic—semantics to programs that would be rejected as “not causal” under the classic synchronous MoC. Thus, when constructing a mapping from Lustre to SCCharts, the second semantic question is how the SC MoC may extend the class of valid Lustre programs.

Contributions and Outline

•

We contribute a synthesis strategy to generate graphical representations for Lustre-like programs using a block diagram notation as in SCADE (Section 2). Specifically, we present a method to construct data-flow graphs for individual Lustre nodes (Section 2.1), we discuss how to extend this to hierarchical networks of nodes leading to the synthesis of actor networks (Section 2.2), and we explain how to incorporate graphical states (Section 2.3).

•

We extended SCCharts with a data-flow component that allows seamless modeling of hybrid control-flow and data-flow models. We also present a transformation from Lustre to Sequentially Constructive Charts (SCCHARTs) that preserves the semantics of a Lustre program This transformation enables us to use the SCCharts diagram synthesis for generating the SCADE-like diagrams for Lustre (Section 3).

•

We investigate how the Sequentially Constructive (SC) Model of Computation (MoC) conservatively extends the semantics of Lustre and allows accepting a greater class of deterministic programs (Section 4). We cover how sequentiality can be exploited for data-flow (Section 4.1), for control flow (Section 4.2), and in the context of concurrency (Section 4.3).

We evaluate our transformation approach in Section 5 and briefly discuss related work in Section 6, including a discussion of how this article expands an earlier report at FDL’20 [7]. In Section 7, we conclude and give an outlook on future work.

2 From KIELER Lustre to Graphical Models

A visual syntax for programs provides many benefits. They give an overview of the program, data dependencies can be extracted, and also during simulation the current state of the program can be integrated in the visualization of the program itself. However, as argued in Section 1, the manual creation and restructuring of those diagrams may become cumbersome and time-consuming. In this section, we present an approach for extracting a graphical SCADE-like diagram from a Lustre program.

Since the original Lustre proposal [2], a number of language variants have been developed, which sometimes makes it difficult to discern what language one is specifically referring to. In this article, we study a synchronous language, henceforth referred to as KIELER Lustre (KLUSTRE), named after the modeling environment in which it is now realized. While we performed the specific work presented in this article with the KLUSTRE language, we argue that the principles presented here apply to Lustre-like languages in general.

KLUSTRE mixes Lustre-like data-flow and a rich set of control-flow structures like hierarchical automata, and in that is fairly close to Heptagon [8].¹ Specifically, KLUSTRE includes

•

the core of Lustre V6 such as pre, -\(\gt\), fby, general point wise applications, and clock operations such as when and current [9];

•

control-flow constructs with automata, borrowed from Scade 6 [1], where transitions can be either weak or strong aborts and they can restart or reset the behavior of the target state;

•

in the context of states, the operations pre and last, where pre refers to the previous value of a variable within the environment of the state it is used and last refers to the last computed value across states.

Type declarations, external nodes, static parameters, arrays, and higher-order functions like map or red are not supported, but should be relatively straightforward to add, building on existing work. Also, there is no clock calculus required (but it could be added), as detailed later in Section 3.4.

Thus, when the distinction is not important, we may still refer to just “Lustre.”

2.1 From Lustre Nodes to Data-flow Graphs

The main entity in the Lustre language are nodes. Each node defines its inputs and its outputs through the interface. Consider the following node:

\begin{equation*} {\mathsf{node}\ \text{exampleNode}\ (i:\mathsf{bool})\ \mathsf{ returns}\ (\text{o:}\mathsf{bool});} \end{equation*}

node exampleNode (i:bool) returns (o:bool);

exampleNode receives a Boolean input i and returns a Boolean output o. Its behavior is defined in the subsequent body through equations. For each output or local variable, an equation is needed that specifies its value.

Now, to retrieve the graphical model there are three steps that need to be performed. We here concentrate on the pure data-flow core of Lustre; the extension to states is covered in Section 2.3.

2.1.1 Step 1, Create Expression Trees.

The retrieval of the Abstract Syntax Tree (AST) of a Lustre program is the entry point for a graphical representation. Starting at this Abstract Syntax Tree (AST), the first step toward a graphical model is performed—the extraction of an expression tree for each equation. Each equation defines the value for one variable, hence an expression tree always corresponds to one variable. Figure 2(a) shows examples of the expression trees for the variables cond and inc.

Fig. 2.

2.1.2 Step 2, Construct Dependency Graph.

In Lustre, each variable needs to be written before it is read. An exception is made for variables read within a delayed operator such as pre or fby. They refer to the value of the previous tick and are thus read before they are written [10], which also implies that they may require a register. In a valid Lustre program there is always a topological sorting of the equations constrained by variable dependencies, as shown in Figure 2(b). The dotted arrows indicate that the variable at the source is required for the destination of the arrow. Note that such dependencies are only relevant within a tick. That is, dependency cycles are resolved by a pre or fby operator. Following this dependency information, a general dependency graph for the variables on the left side of the equation can be established. Figure 2(c) gives an example. The variable preV is read twice, so there are two dependency edges from the equation defining preV to the other equations. This dependency graph now defines the ordering in which the different expression trees are processed in the next step.

2.1.3 Step 3, Connect Expression Trees.

The last step connects the independent expression trees according to the dependencies. The flow of the data in an expression tree is bottom to top, so an edge states the lower node as source and the top node as destination. If a variable occurs non-delayed in one of the leaves of an expression tree, then this leaf is replaced by linking to the root of the expression tree this variable is referring to. Processing starts with the variable at the root of the dependency tree, Figure 2(d) shows the resulting graph. The variable cond is used in the equation init = 0 -\(\gt\) cond. Therefore, the expression tree defining the value for cond is put in place of the actual reference to cond in the second argument of the -\(\gt\) operator. The label cond connected with a dotted line emphasizes this position. Inputs are an exception to this rule as they can be read without being written to explicitly. They remain as a leaf. Multiple reads to the same variable result in multiple edges to the expression tree of the read variable. Therefore, the root of the expression tree for the third equation in Figure 2(b) is connected to the else position from the first equation and the second argument of the addition in the second equation. Figure 2(d) shows the resulting graph after processing all equations.

Output variables are explicitly labeled, so the root of the just processed expression tree is connected with another node for the output variable. In Figure 2(d) the only output is init, thus the root -\(\gt\) is also connected to a node init.

Since delayed operators do not introduce dependency edges in Step 2, it is possible that a variable is read before a corresponding expression tree for this variable is created. For local variables there can be two different strategies for visualization, with or without cycles, as illustrated in the two generated views in Figure 1. First, different labels for the read and the write of a variable could be introduced. Alternatively, those read positions could be later connected with the position they are written to. This allows for two different visualization strategies as shown in Figure 3. Figure 3(a) introduces two labels, one for the read and one for the write of the variable C. In Figure 3(b), however, there is a cycle that does not explicitly label the read of the variable C. There are advantages and disadvantages for both approaches, such as possibly very long edges in the approach allowing cycles. Therefore, we leave it up to the user to chose from these two strategies.

Fig. 3.

2.2 From Node Collections to Actor Networks

In Lustre, nodes conceptually represent actors [12, 13]. Their interaction can be nicely visualized with actor networks, where edges represent data flow connections between nodes. This is illustrated in Figure 4 with UMS_verify, a classic example by Halbwachs et al. [11]. The program describes a U-Turn Management System including several safety properties such as, e.g., no_collision.

Fig. 4.

Figure 4(a) shows the Lustre code for the top-level node, which has inputs on_A, on_B, and so on, and an output property. The automatically extracted actor network, shown in Figure 4(b), illustrates the involved data flow with edges, conceptually flowing from left to right, with inputs aligned on the left and output shown on the right. The diagram also illustrates the local variables grant_access, grant_exit, and so on, as labeled edges. Inner nodes, as, for example, UMS, are shown as nodes with labeled ports that illustrate their inputs and outputs. One may use such a diagram to, e.g., get an overview of where outputs of a node are used. For example, by following the wires connected to the grant_access output of the UMS1 node, one can see quickly that it affects the safety properties no_collision and no_derail, and thus also property, which is the conjunction of all safety properties. Of course, the textual source contains that information as well, but to retrieve it one has to scan all safety properties for the occurrence of grant_access. For a rather small example such as this, which has been condensed for expository reasons, that might still be feasible, but for larger examples, having to scan through the whole scope of a variable to find out its uses quickly becomes tedious and error-prone.

In our tool, the user can explore this network by asking the tool to expand individual nodes (in our implementation by double-clicking). This causes the node to expand in place, which we consider advantageous compared to the usual way of launching a separate window, because it preserves the context. This is again made possible by automatic layout, which performs the necessary adjustments to the wiring and node positioning of the context. As illustrated in Figure 4(c), this in-place expansion can be done recursively. Note that that view has been configured differently than Figure 4(b) by having local variables right-aligned with the output. There are several other options available to fine-tune the diagram, e.g., by also labeling wires by the expressions they represent.

2.3 Visualizing Control-flow/states

KLUSTRE includes automata, which can be defined wherever an equation could stand. Those automata can include states, and each state may define equations that are executed when this state is active. Figure 5 shows an example definition of an automaton and two possible views with collapsed and expanded inner behavior.

Fig. 5.

The transitions in these automata have two parameters that define their behavior. One parameter defines the exit strategy of the source state and the other parameter defines how to enter the target state. The exit strategy is defined by either unless or until. The unless keyword defines a strong termination at the source state, thus the behavior of the target state is executed. The until keyword, however, defines a weak termination. The source state may execute the behavior and in the following tick, the target state executes. The second parameter defining the entering strategy can either be restart or resume. The keyword restart resets the internal variables of the target state and resume realizes a history transition, restoring the previous state.

These states can also be processed into a graph model. The definition of an automaton already introduces a hierarchical node, akin to superstates in Statecharts [14]. The behavior of the automaton is then added within this node. This way the data-flow and the control-flow parts are also visually separated.

2.4 Automatic Layout

We now basically defined a graph that holds information about the data-flow and the control-flow of a given KLUSTRE program. A non-trivial question, studied by a whole community of researchers on graph drawing, is how to turn such a graph into a visual representation. Even though the field of graph drawing goes back a long time and some libraries, such as GraphViz and yEd, are already widely used, the problem still appears hard enough such that very few visual modeling tools provide automatic layout functionality. Typically, tools leave that task entirely to the user instead, which can be rather time consuming and often leads to less-than-perfect results [5]. This differs, e.g., from the CAD/EDA community, where it is standard to synthesize layouts from textual descriptions. In fact, this may also be the reason why so far there are so few serious efforts to synthesize visual models from textual descriptions. However, as we also hope to illustrate here, today it is indeed practical to automatically construct visual models of the type we want.

In addition to the usual requirements and aesthetics criteria—no overlapping nodes, short edges, few crossings, and so on—employed in graph drawing, we typically have a preferred reading direction. In data-flow diagrams, we usually want inputs on the left and outputs on the right. In state diagrams, we prefer initial states on the left and final states on the right. One class of graph drawing algorithms that are guided by such a reading direction is the layered approach, pioneered by Sugiyama et al. [15] and provided, for example, by GraphViz dot.² However, data-flow diagrams, unlike state diagrams, typically induce port constraints in that nodes (actors) often prescribe where they connect to which input/output data-flow edges. This imposes non-trivial further requirements on the layouting algorithm [16].

2.5 Implementation in KIELER

We have prototyped the diagram synthesis in the Kiel Integrated Environment for Layout Eclipse Rich Client (KIELER) IDE. This was originally developed for the modeling of SCCHARTs and by now supports several other languages, such as Esterel and Lustre. A main objective for KIELER was to synthesize views automatically from textual code, as illustrated in Figure 7(a). The Lustre program is parsed using Xtext³ and a synthesis creates a graph model from the AST of the program. The graph model synthesized from KLUSTRE is rendered with the Kieler Lightweight Diagrams (KLIGHD) framework [17]. As illustrated later in Figures 17(c)–17(f), the styling/skinning of the graph can be defined separately. Thus, with KLIGHD, the resulting diagram may “look and feel” like SCADE, SCCharts, Ptolemy or some other visual language.

Fig. 6.

Fig. 7.

Fig. 8.

Fig. 9.

Fig. 10.

Fig. 11.

Fig. 12.

Fig. 13.

Fig. 14.

Fig. 15.

Fig. 16.

Fig. 17.

The automatic layout in KIELER is realized through the Eclipse Layout Kernel (ELK),⁴ which provides a wide range of layout algorithms. All the SCCharts shown here are synthesized automatically within KIELER using ELK and KLIGHD. For data-flow and state diagrams, we use the ELK Layered algorithm, which also considers the aforementioned port constraints. For placing concurrent regions within a superstate, we use a rectpacking algorithm [18].

3 From Lustre to SCCharts

The infrastructure provided by KIELER including KLIGHD and ELK is already used for a pragmatic approach to modeling SCCHARTs [6]. SCCHARTs extend the conservative Model of Computation (MoC) with sequential constructiveness. Features available are generally separated into those that are just syntactic sugar and can be replaced with other constructs of the same language, and those features that are core and are further used downwards the compile chain. The KIELER Compiler (KiCo) handles this step-wise compilation and allows for easy extension and restructuring [19]. We now want to realize the approach for retrieving the graphical model of a Lustre program through the usage of KIELER and SCCHARTs. We present a transformation from Lustre to SCCHARTs that preserves the original behavior of the Lustre program. Section 4 then elaborates the possibilities of the sequential constructive extension of SCCharts on Lustre.

After focussing on the pragmatics of how to visualize Lustre programs in the previous section, we now consider the first semantic question raised in the introduction, namely, how to synthesize valid, behaviorally equivalent SCCharts from Lustre. As one motivation, such a translation allows not only to visualize a textual Lustre program, but it can also be compiled into code and be simulated, as shown in Figure 7(a).

3.1 The Synchronous Model of Computation

Lustre and SCCharts are both synchronous languages. Thus their MoCs share some core characteristics. For example, both divide computations in discrete ticks, and the computation of each tick happens conceptually instantaneously, making outputs synchronous with their inputs. A key benefit of this synchrony hypothesis is that it facilitates deterministic concurrency by defining behavior independent of run-time timing issues and unpredictable scheduling decisions. This differs, for example, from traditional Statecharts that are generally subject to race conditions.

However, SCCharts, unlike Lustre, employ the SC MoC [20], which conservatively extends the classic synchronous MoC. Being conservative here means that programs that are valid under the classic synchronous MoC are also valid under the SC MoC; however, there are also programs that would be rejected under classic synchrony but that have a well-defined, deterministic semantics under the SC MoC (see also Section 4). This implies that the Lustre programs may all be expressed using SCCharts, which is the relevant direction for the proposed visualization approach.

Note that the transformation from SCCharts back to Lustre is also possible, but the approach needs to be combined with Static Single Assignment (SSA) [21] and is not included here. Figure 6 illustrates possible transformation directions. Non-valid Lustre programs can either become sequentially constructive programs or also non-valid SCCHARTs due to their Sequentially Constructive (SC) MoC.

3.2 Adding Data-flow to SCCharts

Data-flow in Lustre is defined in a declarative style as a set of concurrent equations that are evaluated each tick, each defining a stream. In principle, the original SCCharts [22] are already expressive enough to capture this. However, the SCCHARTs language was originally focused on control-flow. Thus, to close the conceptual gap to Lustre, we here extend SCCharts with (unclocked) data-flow.

In the original SCCharts, concurrency is achieved through superstates that contain an arbitrary number of regions that are concurrently active until they reach a final state or the enclosing superstate is left. We incorporate data-flow into SCCharts by providing data-flow regions, which can co-exist with the usual (control-flow) regions. Each data-flow region contains a set of data-flow equations, which are evaluated concurrently, just as in Lustre. Data-flow regions are an extended SCChart feature, meaning that they are transformed away through a model-to-model transformation that creates an SCChart without data-flow regions. The transformation generates one control-flow region per data-flow equation, as illustrated in Figure 7(b) and actually as in the transformation of SCCharts during actions. Each region has an initial state (bold outline), which is left immediately (indicated by the dashed transition) and unconditionally with a transition that, as its effect, evaluates the corresponding data-flow equation and that leads to another state where control rests until the end of the tick. In subsequent ticks, that other state is left through the non-immediate (solid) transition that leads back to the original state, from where immediately the next transition/equation evaluation occurs. There are no final states so the execution does not terminate.

Such a transformation is easily implemented using the integrated, modular KiCo compiler [19], which can handle arbitrary model-to-model transformations and is also used for SCCharts in general. The already existing compilation approaches for SCCharts can be used as usual once the dataflow regions are resolved, which is shown in detail in Section 5.1. The compilation infrastructure handles all the necessary mapping and house keeping to achieve code synthesis and simulation, which is illustrated in Figure 7. Clearly, this approach may create many control flow regions, which may induce significant overhead if compiled naively. However, this allows using the standard SCChart machinery for scheduling equations (assignments) in the right order. Furthermore, since the generated regions are all of the same, simple format, as detailed above, it is quite straightforward to eliminate the region overhead in subsequent optimizations, as also illustrated in Section 5.1.

This establishes the general SCCHARTs data-flow on the principles introduced in Lustre. Moreover, the diagram generation strategy introduced in Section 2 is applied for this extended feature. Therefore, this transformation offers a convenient way of recovering the SCADE diagram of Lustre through SCCHARTs and the semantic differences of both languages can be further investigated. In the following, we look at more specific language features that cannot be translated directly.

3.3 From Lustre to SCCharts

For the transformation from Lustre to SCCHARTs, we want to achieve two main objectives. First, the semantics of the original Lustre program shall be preserved in the synthesized SCCharts. Second, the resulting SCCHARTs model is supposed to recover the diagram representing the Lustre program, i.e., it should resemble a SCADE diagram from which it might be derived. Since not all of the operations possible in Lustre are directly supported in SCCHARTs, the transformation we present is guided by these two objectives. The newly added data-flow regions presented in Section 3.2 may contain equations just like in Lustre. Therefore, the Lustre equations directly find a fitting counter-part in SCCHARTs. Figure 8 visualizes the mapping from Lustre model elements to SCCHARTs model elements. Each node in Lustre corresponds to an SCCharts. The inputs and outputs of a node are inputs and outputs of the SCCharts. The SCCharts contains one data-flow region that defines the same equations that Lustre does. Variable definitions in Lustre are attached to the SCCHARTs data-flow region. This leaves the recovery of the model to the behavior of the equations. Most of the operations available in Lustre can be mapped one-to-one to operations in SCCHARTs data-flow. Table 1 shows a selection of different operator types, their syntax in KLUSTRE and SCADE and the rendering of the same operator for SCCHARTs.

Table 1.

A few Lustre operators do not exist in SCCHARTs so far, but they can be recovered fairly easily. For example, the implication x =\(\gt\) y can be expressed as not x or y. As already mentioned for the data-flow in SCCHARTs, KiCo transforms extended features to model elements that are included in the core set of SCCHARTs operations. The same strategy can be applied for the operations missing in SCCHARTs. We have extended the syntax of the SCCHARTs language to support the usage of these operations. A dedicated processor then takes care of transforming those operations to supported SCCharts operations. The behavior of this processor and how it translates the different operators is explained next.

3.4 Streams Versus Variables

Our translation from Lustre to SCCharts basically maps streams to variables. This is in line with Kahn et al. [23, 24], and such a mapping is also part of a traditional Lustre compiler that translates Lustre to, e.g., C code. We do this mapping at a somewhat higher level, where the result becomes visible at the SCChart modeling level.

Streams in Lustre are clocked, meaning that they carry a value in a tick iff a corresponding clock is true in that tick. Thus, clocks are also streams, of Boolean type. Per default, each node has a base clock and each of its streams are clocked by it. If we refer to stream x, then we mean x as defined in the current tick, and the compiler must guarantee that x carries a value whenever it is referenced. More generally, Lustre programs must be clock-consistent, typically meaning that streams can be combined using data operators only if they operate on the same clock.

Variables in SCCharts behave as in, e.g., C or Java, in that they basically refer to memory cells. This implies that they always carry a value, and that they persist from one tick to the next. Thus, if we refer to some variable x, then we retrieve the value that was written to x last, which may be in the current tick or in some previous tick. Thus, unlike with streams, there is no clock consistency requirement when operating on variables.

Note that while variables in SCCharts are semantically assumed to persist across ticks, we consider it a code generation issue whether such variables are actually implemented as “state variables” or whether they may be, e.g., allocated on a stack in case they are not read anymore in future ticks.

One question that arises is whether a Lustre program to be translated to SCCharts should still be checked for clock consistency. As explained above, there is no such clock consistency requirement in SCChart and thus, our current translation does not perform clock consistency checks. However, if so desired, one may still do clock consistency checking, using e.g. a standard Lustre compiler. Note that dropping the requirement of clock consistency does not mean that all Lustre programs are accepted. For example, if streams cyclically refer to each other, as in x = y ... y = x, then the SCCharts compiler will still reject this.

Likewise, if one would want to preserve the run-time concept of clocked streams that are either present or absent, one could do so by adding Boolean variables that represent clocks. This is already possible at the application level, but if considered necessary at some point, one might also extend the compilation process to generate such variables automatically.

3.5 Clock Operators

As Lustre operates on clocked streams, it provides several functions that operate on clocks. We here discuss two of these operators, when and current.

3.5.1 Downsampling—When.

In case the evaluation of an expression e does not have side effects, the Lustre assignment x = e when c only evaluates e when c is true. Moreover, x is only defined in those ticks where c holds true. So clocking introduces two main ideas: absence of values and conditioned evaluation of expressions. This concept of clocks is also used to gain a mechanism for expressing control in data-flow. However, there is no presence or absence check of a value in Lustre, other than the clocking itself. During code generation of Lustre, those clocks are translated to conditionals [2, 10].

In SCCHARTs the clocking can be emulated within a conditioned evaluation for the corresponding expression. Only in those instances when the clock (implemented as a Boolean variable) is true, the value for x needs to be computed. We express this with a simplified variant of the ternary operator, without an explicit else branch: the assignment x = e when c is translated to x = c ? e, which in turn gets translated into if (c) x = e. In the case of nested downsamplings, the condition c must be the conjunction of all downsampling clocks. This directly reflects the Lustre code generation [10]. Therefore, we can reuse this SCCHARTs operator for the transformation and the behavior of when. In the transformation of data-flow to control-flow in the SCCHARTs compilation chain, this reduced operator is realized as a trigger for the transition containing the assignment in the parallel region. In Figure 9 the visualization of the when operator and its transformation to control-flow is shown.

3.5.2 Upsampling—Current.

If the clock of a stream x is false, then current x stands for the last known value of x. The variables of SCCHARTs naturally support this through their persistence across ticks. Thus, each occurrence of current x in KLUSTRE is simply replaced by x in SCCharts. KLUSTRE does not support the merge operator, but this could be realized using the ternary operator: an expression merge a (true -> b1) (false-> b2), where a runs on the clock clk, could be expressed by if clk then current b1 else current b2.

3.5.3 Clocks and Registers.

Each operator individually now realizes the same behavior as in Lustre. Especially the clocking, however, has an effect on the behavior of other operations. Combining when with the pre operation behaves differently in SCCHARTs than originally in Lustre. The pre operation is stateful. The value is defined by the value of the variable in the previous tick. In combination with clocks this refers to the value in the tick this variable was defined last. Note that this only refers to plain data-flow. In the context of states, the pre value is also linked to the corresponding state. The keyword last is used there to refer to the actually previous value, thus the value the variable was computed last [25].

We can use the persistence of variables beyond ticks, together with the concept of sequential constructiveness (see also Section 4.1), to transform pre away before the target code generation. Figure 10 shows the behavior of the pre transformation in KIELER. Two new variables are introduced: the variable _reg_x holds the value of the variable at the end of the current tick, and _pre_x holds the value of the variable at the end of the previous tick. The variable _pre_x can thus be used for accessing the previous value for the variable. Due to the during action, the updating of those variables occurs each tick, so each tick the variable containing the previous value is updated. In the context of an automaton, this transformation needs to add this register variable to the parent state, thus creating the state context for pre. For the use of last operation, no special transformation operations are needed. In combination with clocks, however, this update needs to be guarded by the conjunction of all hierarchically higher clocks up to the baseclock, similar to the case of downsampling covered in Section 3.5.1. In Lustre this is not a problem, because the transformation of pre is also done during code generation and can simply be put within the conditional of the corresponding clock. This also yields a solution approach for SCCHARTs. The transformation optionally allows defining a trigger for the update.

Table 2 shows an example of a clocked pre operation. The stream of x is clocked to the clock clk, and then the pre operation is applied once and twice. In the version of pre that does not guard the update, applying the pre operation twice would yield a wrong result in the fourth tick. Applying pre introduces a nil value. In the variant without the conditioned update for the pre operation, the value 1 would be computed for the fourth instance. However, since it is the second tick for the clocked stream, it should still be nil. Realizing the transformation using a trigger that is constructed through the conjunction of all hierarchical higher clocks works properly.

Table 2.

	Name	Stream of values
	x	1	2	3	4	5
	clk	true	false	false	true	true
	x1 = x when clk	1	1	1	4	5
Lustre	pre(x1)	nil			1	4
	pre(pre(x1))	nil			nil	1
SCCharts	pre(x1)	nil	1	1	1	4
(unclocked pre)	pre(pre(x1))	nil	nil	1	1	1
SCCharts	pre(x1)	nil	nil	nil	1	4
(clocked pre)	pre(pre(x1))	nil	nil	nil	nil	1

Table 2. Example for a Clocked Stream in Combination with the pre Operation

Those changes are now sufficient for the SCCHARTs program to obtain the same behavior as the Lustre program.

4 Sequentially Constructive Lustre

As explained in the introduction, the translation of Lustre to SCCharts also raises the question of how the SC MoC that underlies SCCharts may open the door toward accepting more Lustre programs than under the standard assumption of just one value per variable (stream) per tick. Through the transformation of Lustre to SCCHARTs, a greater class of programs can be accepted, which gives the programmer more freedom in modeling. We extend the classical set of viable programs in a conservative manner. Valid Lustre programs keep their semantics, but some Lustre programs that would be rejected, for example, those with recursive definitions or multiple writers, can be accepted under the SC semantics if they are deterministic and SC admissible [26].

4.1 Sequentiality in Data-flow

In original Lustre, every equation holds globally (w.r.t. clocks) and defines the current value of a variable. Consequently, recursive definitions that rely on the current value of variables to define its current value are rejected. With the notion of sequentiality in the SC MoC, this classical view of a globally consistent value is relaxed.

4.1.1 Sequentiality Within Assignments.

Under sequential constructiveness, x = e is not considered to be an equation, but an assignment. Furthermore, sequences of such assignments are considered to be sequentially ordered.

Assignments that read the current value of the variable they assign are not rejected but simply overwrite the value in the sense of imperative programming. This is based on the argument that in an assignment x = e, there is a clear sequential ordering between evaluating expression e and assigning the value to x. There is no concurrency involved that may give rise to race conditions; thus determinism, which is the overall goal of the synchronous MoC, is not compromised. The following example of a simple counter illustrates this notion of sequentiality. The equation x = 0 -\(\gt\) x + 1 in SCCHARTs initializes x with zero. In subsequent ticks it reads the value of x that is currently held in memory, and sequentially afterwards, increments the value by one. This behavior can be realized without explicitly using the pre operator.

However, one must be aware that the substitution principle, which means that we can replace the right hand side of an equation by its left hand side and which applies for original Lustre, does not apply anymore when sequential scheduling information gets lost. For example, splitting x = 0 -\(\gt\) x + 1 into x = 0 -\(\gt\) y and y = x + 1 would not be schedulable anymore, because both equations are considered concurrent and depend on each other. The single-equation version inherently implies a read-write ordering, and for the two-equation version this information is lost. Thus, it may be a matter of preference whether one actually wants to program in a style that takes advantage of sequentiality or not. Programmers used to the imperative programming paradigm are generally aware that, e.g., x = y; y = z is not necessarily equivalent to x = z; y = z, because the same y may have different values. In imperative programming, y = z is not an equation that universally holds (as it is in Lustre), but an operation, which has an effect only for subsequent statements, not for previous statements. Then again, note that the SC MoC is a strict, conservative extension of the usual synchronous MoC, thus one may still restrict oneself to Lustre programs that do not exploit sequentiality and where thus the substitution principle still applies.

4.1.2 Sequentiality Across Assignments—The seq Operator.

In imperative programming, there is not only a natural, sequential order between evaluating a right-hand side of an assignment and assigning the result to the left-hand side, but there is also an order implied in which assignments are written down in the program text. We already took advantage of this order in the transformation of the pre operator shown in Figure 10. The during action _pre_x = _reg_x; _reg_x = x works, because the assignment to _pre_x is scheduled before the assignment to _reg_x, even though _reg_x is then read before it is written, in opposition to the write-before-read scheduling required under classical synchronous programming.

Esterel makes this explicit by referring to the semicolon as a sequence operator. In the SC MoC, the semicolon also works as a sequence operator, but in an even stronger, prescriptive sense that tells the compiler to schedule one statement before the other, overruling any data dependencies that may exist between them. For Lustre-like languages there has been some work on allowing variables to be modified in-place for memory optimizations [8]. However, the sequence operator proposed here allows for sequentiality within one tick. In SCCharts, during actions, which get transformed to concurrent regions with one state with one self transition that performs the action, are just one example of this prescriptive interpretation of the semicolon.

We propose to add the same operation of prescriptive sequentiality to KLUSTRE equations. Again, we still want to be conservative in that valid Lustre programs are valid KLUSTRE program with the same semantics. Thus, per default, equations are still interpreted as concurrent equations to be scheduled according to the write-before-read principle, irrespective of the order in which the equations appear in a node. However, in addition to that default semantics, we propose to add an operator that tells the compiler to schedule equations not according to write-before-read, but instead in the order in which they are written in the program.

To be clear, we do not argue here that the declarative approach of Lustre-like languages should be replaced in any way, as that approach clearly has demonstrated its value. If one wants to keep using standard Lustre as is, then one may well do so by simply not using the sequential feature proposed here. However, if one already has an imperative algorithm in mind to solve a certain problem, then one may prefer to express it directly instead of trying to encode it in Lustre and hoping that the compiler will generate the code we had in mind. What we demonstrate here is that it is possible to augment the existing languages with the option to express imperative parts as well, without breaking parts written in “standard” Lustre.

It would seem natural to again use the semicolon to express this imperative-style sequentiality. Unfortunately, the semicolon is already used in classic Lustre as a statement delimiter. We therefore chose, at least for now, to introduce a new keyword seq instead of changing the meaning of the semicolon. However, we are aware that this may seem rather awkward, and technically it would not pose any difficulty to interpret the semicolon as sequence operator as well.

Figure 11(a) shows the sequentially ordered assignments of the aforementioned pre transformation using the seq operator. First, the pre value of x is requested from the x memory location, meaning the last valid value of x is stored, even across tick boundaries. Then, after the stored value is no longer needed, the register is overwritten sequentially with the current value of x. In the visual representation in Figure 11(b), the sequential ordering is depicted as red, dashed edge, indicating that _reg_x is only set after its stored value is no longer needed. Similarly, if one has multiple accesses to pre x as in Figure 11(c), then the sequential assignment is scheduled accordingly, which is visualized in Figure 11(d).

4.1.3 Example: Computing the GCD with Euclid.

In the following, we look at how the different languages can be used to realize the Euclidean algorithm to compute the greatest common divisor (GCD) of two numbers. Figure 12(a) shows the general imperative algorithm.

In classical Lustre, this can be expressed as a node with two inputs and one output, as depicted in Figure 12(b). The input values from the initial tick are read and saved in local variables. Those local variables are then used in subsequent ticks to perform one iteration of the Euclidean algorithm. Therefore, the initial tick sets the local variables a and b to ib and ia mod ib to save the initial input values that are worked with in subsequent ticks. The output variable o holds the result for the common greatest divisor but as long as the result is still calculated, it is set to \(-1\). Realizing this program in KLUSTRE, we can easily apply the imperative programming style from Figure 12(a) using the seq operator. The input and output variables remain the same. However, the initialization of the local variables for the first tick can be encapsulated within their declaration. This reduces the complexity of the equations itself and allows the direct application of the imperative coding style. No pre-operations are needed and each equation is performed sequentially after one another. The last equation is an exception, since the seq operator is not needed here. In Figure 12(c) the KLUSTRE code is given. Moreover, in Figure 12(d) the visualization of these equations in KIELER is shown. The sequentiality is illustrated through the dotted red lines as already shown in Figure 11(d).

4.2 Sequentiality in Control-flow

In Heptagon/Scade 6, if there is a transition from some state A to some other state B, then A and B cannot be active in the same tick. If the transition is taken, then either A is still executed (weak abort) and B is not entered yet (deferred entry, indicated with a blue circle), or A is not executed anymore (strong abort, indicated with a red circle) but B is entered (non-deferred entry). This design choice eliminates write-write conflicts in case A and B write to the same variable. However, under the SC MoC, we consider A to be sequentially ordered before B, thus giving a clear, deterministic semantics even if both A and B are executed in the same tick. Moreover, sequentiality could further extend the features provided in the current state machine scope. Immediate transitions are a way to express a sequence of states whose behavior is executed following this order. Figure 13 shows an example in SCCHARTs. Each tick, the output variable O is initialized with 5 and subsequently incremented with 10 and X.

Furthermore, the SC MoC considers strong/weak aborts to be sequentially ordered before/after the state they abort. Thus, for example, it is legal for the trigger of a strong abort to depend on a variable that is written (in case the abort does not take place) in the potentially aborted state. For example, in Figure 14, out is first set to 15 in state A, then A is weakly aborted, since out \(\gt\) 10 holds, and finally out is set to 5 in B.

4.3 Concurrency

As explained in Section 3.2, we map Lustre data-flow equations to concurrent SCChart regions that each handle one equation. Unlike Lustre, the SC MoC allows multiple concurrent definitions for the same variable, as long as they can be scheduled according to the Initialize-Update-Read Protocol (IURP). For a detailed treatment of the Initialize-Update-Read Protocol (IURP), we refer elsewhere [20]. Briefly, for each variable within each concurrent scope, there may be one initialization (absolute write), followed by an arbitrary number of confluent updates (relative writes), followed by an arbitrary number of reads. An update of a variable x is a write that depends on the current value of x via some combination function, e.g., addition in x += e, where the value of e must not depend on x. Unlike Esterel, we do not require the combination function to be commutative, thus also the subtraction could be a viable combination function. Our compilers conservatively require that updates use the same combination function, even though that would not be strictly necessary for confluence; e.g., additions and subtractions would also be confluent. This is akin to the combination functions of Esterel, except that we allow combining them with initialization. An initialization is a write that is not an update.

As example, consider the KLUSTRE program in Figure 15. The binary conditional operator, called set operator (x = c ? e), is a short-hand form of the common ternary conditional operator. If the condition is true, then the variable value is updated to the new value. Otherwise, it keeps the stored value, which is possible because of the SC variable persistence. As any program that has one variable appear multiple times at the left-hand side of an equation, this would not be considered to be a valid Lustre program. However, even though we have different concurrent assignments to x, the KLustre compiler can accept this, and the scheduler will order the assignments according to the underlying Initialize-Update-Read Protocol (IURP). In this example, the assignment in line 1 is an initialization, and the assignments in lines 2 and 3 are both updates, in this case using addition as combination function. Thus, x is first assigned the value 5, and then 1 and 5 may be added, providing the corresponding inputs b, respectively, c are set.

In a second example, which again would not be considered valid Lustre, consider variable x used in lines 1–4 in the KLUSTRE code in Figure 16(a). The IURP applied to x requires that the initialization of x in line 2 must be scheduled first, followed by the updates in lines 1 and 3 in any order, followed by the read in line 4. Similarly, the write of y (line 5) must be scheduled before the reads (lines 1 and 3). The resulting dependency graph is acyclic, thus the KLUSTRE program is schedulable and valid. A possible resulting C code is shown in Figure 16(b). However, if ordered manually, as discussed in Section 4.1, enforcing an imperative style seen in Figure 16(c), the ordering must be respected and the resulting C code looks pretty much like the KLUSTRE input code. The visualization of the model, including the sequential constraints, can be seen in Figure 16(d).

5 Assessment

The generation of code from Lustre-like languages is already a well-studied subject, with numerous compilers available including the qualified code generator of SCADE, and it was not a primary objective of this work to add yet another code synthesis approach. However, since we now have a path from KLUSTRE to SCCharts, for which there are also several code generators available, it is a natural question to ask how the end results compare.

Note that we consider the question of whether function calls are macro-like expanded, as is typically the case in Esterel, or implemented with standard function calls, as usually done by Lustre compilers, to be an orthogonal question to the language discussion presented here. For example, SCCharts modules have traditionally been expanded statically, but now can be compiled to functions as well [27].

Similarly, we see the language additions proposed here to be largely independent of the question of whether instantaneous feedback is forbidden (as in Lustre) or may be permitted as long as the program is still “constructive” (as in Esterel and SCCharts).

5.1 Code Generation

We now examine the whole synthesis chain from a Lustre example through SCCharts to C code.

Figure 17(a) shows the Lustre code of the counting node, originally presented by Colaco et al. [25]. The corresponding Scade diagram is depicted in Figure 17(a). The KIELER IDE allows editing the Lustre source code with common editing features, such as highlighting and code completion. While editing in the textual editor, a diagram as the one shown in Figure 17(c) is (re-)synthesized automatically whenever the text file is saved. Similar to Scade, both equations are depicted in the graphical representation. However, the diagram synthesis can be configured interactively to display several variations to fit the modeler’s needs. For example, the whole diagram can be skinned to get a Scade look-and-feel; see Figure 17(d). The disconnected components can also be ordered sequentially, as in Figure 17(e). The sequential ordering is indicated by the red dashed hyperedge, because v, written in the first equation (the first line of the Lustre node), is read in the second one, even though their order is reversed in the textual representation of the node. Since v is not visible from outside the node, its graphical input/output representation can be omitted altogether, corresponding to the Lustre substitution principle; see Figure 17(f).

The KIELER Compiler (KiCo) included in KIELER is configured as depicted in Figure 18(a) for the evaluation. First, the Lustre program is compiled into an SCCharts model. Possible graphical representation of the generated SCChart are shown in Figures 17(c)–17(f). The data-flow representation of SCCharts is translated into its semantically equivalent control-flow oriented counter-part, shown in Figure 18(b). From here, we can use any SCCharts compilation strategy. The main alternatives are the netlist approach, which can be used for synthesizing software or hardware; the priority-based approach, which does not allow hardware synthesis but accepts more programs, e.g., those with instantaneous loops [22]; and the state-based approach, which has a focus on readability and self-documentation [28]. We here employ the netlist-based strategy and illustrate that the resulting code contains little overhead compared to the input equations, even if compiled via a compilation approach that supports control-flow-oriented constructs expressed as netlist.

Fig. 18.

The compilation approach generates a netlist with guarded basic blocks from the control-flow graph of the program. The overhead that might be introduced due to the transformation of data-flow in control-flow can be reduced in stateless models. Figure 18(e) shows the sequentialized result of the compilation after standard optimization techniques, such as copy propagation [29], have been applied. From here, guards that guard states that are evaluated in every tick form persistent state patterns, which always evaluate to true: The guard is true in the first tick (_GO) or if it was true in the previous tick. The final optimized version is depicted in Figure 18(c).

The C code of the counting node example generated by KiCo is listed in Figure 18(d). Code from the immediate environment, such as the reset function and the _GO signal, which signals a program start, are omitted here. Hence, the generated logic function directly resembles the data-flow of the node. This example demonstrates that the generated code can be still compact and readable even if SCCharts data-flow equations are translated into a statechart, then into a control-flow graph and finally into imperative code.

Note that saving the previous value of o is embedded in the code, because pre is an extended feature of SCCharts and not part of the underlying expression language as already stated earlier. The register retrieval and save can be observed in Lines 3 and 8 of Figure 18(d). However, since sequential constructiveness inherently stores the immediate previous value, the modeler can omit the pre operator altogether. In this case, the marked parts in the listing will not be generated. The resulting code is semantically identical but does not require the register save.

As mentioned earlier, we consider the question where to store (stateless) variables orthogonal. In the example, all variables are stored in the TickData struct even if they are not referenced in the next tick, e.g., the local iop variable. In the case of the netlist-based approach this is also true for the guard variables of the netlist. Hence, the simulator has access to all intermediate values and can highlight active wires and display current values, similar to the way it is depicted in Figure 7(a). Standard and semantic optimizations, such as the persistent state optimization, are done on SCCharts level [30]. However, technically it is also possible to simply store stateless variables on the stack for potential efficiency reasons.

5.2 Quantitative Assessment

To evaluate the performance of the generated code, we performed benchmarks on over 50 Lustre programs. Most programs are small and use only a single language feature, since these programs are used for continuous integration testing of the KIELER compiler. However, these benchmarks also include some programs taken from the publicly available Lustre examples repository,⁶ excluding programs that are not syntactically compatible to KLUSTRE. We simulated these programs using predefined execution traces and measured the computation time for each tick in nanoseconds.⁷ As a point of reference, we performed the same simulations using code generated by the publicly available V6 Lustre compiler by Verimag.⁸ We used this to check for functional equivalence and to perform a quantitative comparison. There are also other Lustre compilers such as Heptagon and KCG [1] that would be worthwhile to investigate and compare. However, both compilers support different syntactic dialects of Lustre that are currently not compatible with KLUSTRE.

Table 3 shows results of the benchmarks for some selected programs. For slightly larger programs, such as heater_ctrl, UMS_verify and stopwatch, the average computation time using SCCharts generated code did not exceed those of the Lustre compiler. However, for most of the other programs, which are quite small with less than 10 lines of Lustre source code, the results varied greatly. The reason is the fast computation time between 100 and 200 ns due to the small size of the actual logic, which was probably heavily affected by the OS and measuring inaccuracy when accessing the system’s clock. However, the average over the deviation of the average reaction time of all programs is about \(-3\)%, and about half of the programs have a higher average reaction time using Lustre generated code. Hence, we can say that on average the SCCharts code generation did not perform worse compared to the Lustre V6 compiler.

Table 3.

Program	Lines of code			Object code size (O0/O2) [kiBi]		Avg. Reaction Time [ns]
Program	Lustre Source	SCCharts C	Lustre C	SCCharts	Lustre	SCCharts	Lustre
heater_ctrl	83	170	343	4.7/3.1	6.9/4.7	527	813
UMS_verify	76	273	265	4.5/3.4	7.2/5.4	673	703
stopwatch	26	105	281	2.4/1.8	4.2/3.6	309	516
counting	6	46	119	1.7/1.5	3.1/2.5	149	273
implies	4	32	32	1.6/1.4	1.3/1.2	166	161

Table 3. Selected Results of the Conducted Benchmarks Presenting the Lines of Code in the Source Program and Generated C Code (Ignoring Comments), the Size of the Compiled Object Code (Both Unoptimized and Optimized), and the Average Time to Compute a Reaction During Simulation Using Unoptimized Code (to Prevent Optimizations from Interfering with Time Measurement)

Separate results are listed for code generated using the SCCharts and Lustre compiler.

Table 3 additionally presents the code size of the source program, the generated C code, and the compiled object code for both compilers. The selected results reflect the general trend in the entire program set that the code generation of SCCharts produces fairly compact code. However, the implies program, which compiles into the simple Boolean expression O = !A|| B for both compilers, shows that both compilers produce a certain overhead to run the actual logic. The netlist approach of the SCCharts compiler, however, scales better when comparing the relation between source code and generated code on all listed programs. While this is also true for UMS_verify, the SCCharts compiler produces slightly more C code than Lustre for this model. The reason is the use of referenced nodes. The current SCCharts compiler with the netlist approach statically expands each node instantiation, similar to function inlining, and produced a single tick function. In contrast to that, the Lustre compiler generates functions for each node and then invokes these with a context for each instance of that node. Clearly, static expansion scales worse in terms of code size if there are many instances of few large nodes. This effect is already noticeable in the code size of UMS_verify.

Alternatively, SCCharts can also generate modular code where multiple tick functions are synthesized to enable reuse of the logic for different instances inside the SCChart. However, this limits the options of the compiler to schedule the program, because modules are invoked atomically. For example, back and forth communication with such a module and its environment cannot easily resolved by interleaving. This is an issue of black box versus white box scheduling, also discussed when SCCharts were extended toward object orientation [31]. A compromise for this issue is gray box scheduling [32], which separates modules into schedulable yet maximal parts. In the context of SCCharts, we consider the development of a modular code generation future work.

In conclusion, we interpret these results so far to indicate that the translation from Lustre to SCCharts does not necessarily impose a significant performance penalty, at least compared to existing compilation approaches in the Lustre V6 compiler and language.

6 Related Work

This article introduced an approach for enhancing the modeling experience of Lustre programs with visual diagrams, inspired by SCADE. Dormoy covers the graphical SCADE language [33]. As explained, we basically reverse the synthesis direction compared to the SCADE tool in that we automatically extract visual diagrams from a textual Lustre source.

Graphical data-flow is used in various domains and tools beyond SCADE. Simulink,⁹ Labview,¹⁰ and Ptolemy¹¹ also use a notion of block diagram for their diagrams. Besides their different underlying MoC, they all represent actor-oriented data-flow. Each uses a graphical editing approach, and the user can modify the diagram via drag and drop of the components. Ptolemy offers the possibility of an automatic layout, also harnessing ELK. However, the initial model requires manual graphical editing.

The approach of automatic diagram generation for programs with a textual syntax has been investigated for other languages before. Prochnow et al. introduced an automatic Esterel to SyncCharts/Safe State Machine Transformation [34]. Moreover, they elaborated on the differences between visual and textual editing in practical use. Especially in terms of comprehensiveness and editing speed each has advantages and disadvantages. The motivation was similar to transforming Lustre to SCCHARTs—the benefits of both alternatives are combined.

The basic idea of automatically generated diagrams follows the principle of Model-driven Visualization (MDV) introduced by Bull et al. [35]. This automatic generation allows for multiple views on the same model. Schneider et al. elaborated more on this by introducing a meta-model and an infrastructure for automatic layout. The developed infrastructure is the KLIGHD framework that we use for the graphical view generation in the Lustre context.

The synchronous language Esterel was also extended in a conservative manner. A sequentially constructive approach was introduced by Rathlev et al. creating the language SCEst [36]. SCEst also overcomes some restrictions implied by the classical synchronous MoC without losing determinacy.

An abbreviated, earlier report on this work was presented at FDL’20 [7]. Key additions to that work include the coverage of actor networks (Section 2.2), an extended discussion of sequentiality in data-flow specifically including the seq-operator (Section 4.1), and the quantitative assessment (Section 5.2). Further additions include the operator mappings (Section 3.3) and the discussion of the pre operator in clocked streams (Section 3.5).

7 Conclusion and Future Work

In this article, we presented, to our knowledge for the first time, a generic approach for synthesizing graphical diagrams from a variant of textual Lustre. The original goal was driven by modeling pragmatics, based on the observation that graphical languages, including SCADE, have their merits for visualization and documentation, however, their practical usage can be rather tedious. Thus, by automating the process of generating customizable graphical views from textual Lustre, made possible by state-of-the-art layouting algorithms, we believe to have made a step toward having the best of both the textual and the graphical worlds.

Beyond that original goal, we also addressed two questions that concern semantics, irrespective of textual/graphical syntax. First, we made a link from Lustre to SCCharts, basically by extending SCCharts with data-flow and by mapping clocked streams to variables. Second, we investigated how the SC MoC that underlies SCCharts gives meaning to Lustre programs that classically would be rejected, by harnessing sequential scheduling information.

We have implemented these concepts in the open source KIELER tool, for a specific variant of Lustre, termed KLUSTRE. With that, a programmer may now write Lustre code as usual, alongside an automatically synthesized visualization that is updated on the fly (and without significant delay) whenever the code is saved. That visualization is in fact a valid SCChart model, meaning that it can be simulated and compiled into software and hardware. Preliminary experiments indicate that the code synthesized from Lustre via SCCharts is of reasonable quality, but further evaluations of that would be needed.

Moreover, there are different programming languages that are variants of or inspired by Lustre. We chose to build our own subset of supported Lustre features, but there are also other Lustre-alike languages that could be used. Support for Scade, the internal language used in SCADE, would allow for direct diagram comparison and maybe automatic diagram generation in SCADE [25]. The language supported by the Heptagon compiler could also offer a nice entry for evaluation results. Unlike the Lustre V6 compiler, it also supports automata. It was already considered to create efficient code [8], thus it is especially interesting for comparison with the SCCHARTs code generation.

Finally, we feel that the relationship between the classical synchronous MoC and the SC MoC in the context of Lustre-like languages would merit further investigation. This should include a formal treatment, building, for example, on the work by Aguado et al. [37].

Footnotes

http://heptagon.gforge.inria.fr/.

https://graphviz.org.

https://www.eclipse.org/Xtext.

⁴

https://www.eclipse.org/elk.

⁵

During this work, we noticed that the SCADE diagram from the original paper [25] was inconsistent with the Lustre code in that the addition operator was missing. Graphical inconsistencies such as these are another argument for synthesizing diagrams automatically. Additionally, in the original counting node [25] the type of o is bool, which is inconsistent with its assigned value. Here, we use a fixed version.

⁶

https://github.com/jahierwan/lustre-examples.

⁷

The benchmarks were conducted on an Ubuntu 20.04 system with an Intel Core i5-7300U CPU and 16 GB RAM. For the C compilation, we used the GCC compiler without optimization (O0).

⁸

http://www-verimag.imag.fr/Lustre-V6.html.

⁹

https://de.mathworks.com/products/simulink.html.

¹⁰

http://www.ni.com/getting-started/labview-basics/.

¹¹

http://ptolemy.berkeley.edu/ptolemyII/.

References

[1]

Jean-Louis Colaço, Bruno Pagano, and Marc Pouzet. 2017. SCADE 6: A formal language for embedded critical software development (invited paper). In Proceedings of the 11th International Symposium on Theoretical Aspects of Software Engineering (TASE’17). 1–11.

Abstract

1 Introduction

Contributions and Outline

2 From KIELER Lustre to Graphical Models

2.1 From Lustre Nodes to Data-flow Graphs

2.1.1 Step 1, Create Expression Trees.

2.1.2 Step 2, Construct Dependency Graph.

2.1.3 Step 3, Connect Expression Trees.

2.2 From Node Collections to Actor Networks

2.3 Visualizing Control-flow/states

2.4 Automatic Layout

2.5 Implementation in KIELER

3 From Lustre to SCCharts

3.1 The Synchronous Model of Computation

3.2 Adding Data-flow to SCCharts

3.3 From Lustre to SCCharts

3.4 Streams Versus Variables

3.5 Clock Operators

3.5.1 Downsampling—When.

3.5.2 Upsampling—Current.

3.5.3 Clocks and Registers.

4 Sequentially Constructive Lustre

4.1 Sequentiality in Data-flow

4.1.1 Sequentiality Within Assignments.

4.1.2 Sequentiality Across Assignments—The seq Operator.

4.1.3 Example: Computing the GCD with Euclid.

4.2 Sequentiality in Control-flow

4.3 Concurrency

5 Assessment

5.1 Code Generation

5.2 Quantitative Assessment

6 Related Work

7 Conclusion and Future Work

Footnotes

References

Cited By

Index Terms

Recommendations

SCCharts: sequentially constructive statecharts for safety-critical applications: HW/SW-synthesis for a conservative extension of synchronous statecharts

SCCharts: sequentially constructive statecharts for safety-critical applications: HW/SW-synthesis for a conservative extension of synchronous statecharts

Toward Object-oriented Modeling in SCCharts

Comments

Information

Published In

Publisher

Journal Family

Publication History

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations