SCCharts - Language and Interactive Incremental Compilation E-Book

Christian Motika

• Herausgeber: Books on Demand
• Kategorie: Wissenschaft und neue Technologien
• Serie: Kiel Computer Science Series
• Sprache: Englisch

Seitenzahl: 508

Veröffentlichungsjahr: 2018

Beschreibung

Safety-critical systems are a subclass of reactive systems, a dominating class of computer systems. Such systems control airbags in cars, flaps of aircrafts, or pace makers. Software for these systems must be reliable. Hence, a language and tooling is needed that allows to build and maintain reliable software models. Furthermore, a reliable compiler is required to obtain decent machine-understandable and executable code from highly abstract models. This thesis presents SCCharts, a Statecharts-based visual and synchronous modeling language for specifying and designing safety-critical software systems and for deriving their implementations. http://www.sccharts.com

Leseprobe

Dissertation

zur Erlangung des akademischen Grades

Doktor der Ingenieurwissenschaften

(Dr.-Ing.)

der Technischen Fakultät

der Christian-Albrechts-Universität zu Kiel

eingereicht im Jahr 2016

About this Series

The Kiel Computer Science Series (KCSS) covers dissertations, habilitation theses, lecture notes, textbooks, surveys, collections, handbooks, etc. written at the Department of Computer Science at the Christian-Albrechts-Universität zu Kiel. It was initiated in 2011 to support authors in the dissemination of their work in electronic and printed form, without restricting their rights to their work. The series provides a unified appearance and aims at high-quality typography. The KCSS is an open access series; all series titles are electronically available free of charge at the department’s website. In addition, authors are encouraged to make printed copies available at a reasonable price, typically with a print-on-demand service.

Please visit http://www.informatik.uni-kiel.de/kcss for more information, for instructions how to publish in the KCSS, and for access to all existing publications.

1. Gutachter:

Prof. Dr. Reinhard von Hanxleden Kiel University, Kiel, Germany

2. Gutachter:

Prof. Florence Maraninchi VERIMAG Institute, Grenoble, France

Datum der mündlichen Prüfung: 21. April 2017

Zusammenfassung

Sicherheitskritische Systeme sind eine Unterklasse von reaktiven Systemen, welche heutzutage eine der wichtigsten und größten Klasse von Computersystemen darstellt. Solche Systeme kontrollieren die Airbags unserer Autos, die Landeklappen eines Passagierflugzeugs, Kernkraftwerke oder Herzschrittmacher. Software für solche Systeme muß absolut zuverlässig sein. Daher werden Computersprachen und Werkzeuge benötigt, die es erlauben, zuverlässige Softwaremodelle zu erstellen und zu warten. Weiterhin braucht es zuverlässige Kompiler, die aus solchen abstrakten Modellen korrekten maschinenlesbaren und ausführbaren Code erzeugen.

Mit SCCharts präsentiert diese Arbeit eine zustandsmaschinenbasierte und synchrone Modellierungssprache für den Entwurf und zur Implementierung sicherheitskritischer Systeme. Es wird betrachtet, warum sich dafür eine kontrollflußorientierte und synchrone Sprache besonders gut eignet und welche Wahl inkrementeller Sprachbestandteile die Lernkurve senken können. Die Arbeit zeigt, wie ein als SLIC bezeichneter, interaktiver, inkrementeller und auf Modelltransformationen basierender Kompilierungsansatz sowohl dem Modellierer dabei helfen kann, zuverlässige Modelle zu erstellen, als auch den Werkzeugentwickler darin unterstützt, einen zuverlässigen Kompiler bereit zu stellen. Es wird ein auf SLIC basierender SCCharts Kompiler inklusive seiner high-level Modelltransformationen vorgestellt. Weiterhin wird der vorgestellte Ansatz mit Hilfe der beispielhaft umgesetzten KIELER SCCharts Sprach- und Werkzeugimplementierung auf seine Praktikabilität hin überprüft.

Abstract

Safety-critical systems are a subclass of reactive systems, a dominating class of computer systems these days. Such systems control the airbags in our cars, the flaps of an aircraft, nuclear power plants or pace makers. Software for these systems must be reliable. Hence, a language and tooling is needed that allows to build and maintain reliable software models. Furthermore, a reliable compiler is required to obtain decent machine-understandable and executable code from highly abstract models.

This thesis presents SCCharts, a Statecharts-based visual and synchronous modeling language for specifying and designing safety-critical systems and for deriving their implementations. It elaborates on why a control-flow oriented and synchronous language is desirable and how incremental language features are chosen to flatten learning curve. It presents an interactive incremental model transformation based compilation approach termed SLIC. It shows how SLIC helps in supporting both, the modeler and the tool smith for building reliable models and maintaining a reliable compiler, respectively. A SLIC-based compiler for SCCharts including its high-level model transformations is presented. Furthermore, practicality aspects of the KIELER SCCharts language and tooling implementation complete the considerations to validate the proposed approach.

Contents

Introduction

1.1 Contributions of this Thesis

1.2 Related Publications

1.2.1 Major Publications

1.2.2 Other Publications

1.2.3 Supervised Theses

1.3 Outline

Background and Related Work

2.1 Synchronous Languages

2.2 Statecharts

2.2.1 Argos

2.3 SyncCharts

2.3.1 The

hello world

of synchronous programming (ABRO)

2.3.2 Advanced SyncCharts Features

2.4 Other Statechart Dialects

2.4.1 SCADE State Machines

2.4.2 UML Statecharts

2.4.3 Stateflow

2.4.4 Modechart

2.5 Code Generation from Statecharts

2.6 Sequential Constructiveness

2.6.1 Synchronous Programming Classes

2.7 The Sequentially Constructive Graph (SCG)

2.7.1 Explicit Data Dependencies

2.7.2 Abstract Syntax

2.7.3 Example

2.8 Model-Based Compilation and Compiler Infrastructure

The SCCharts Language

3.1 Basic Concepts

3.1.1 General Structure

3.1.2 Termination

3.1.3 Synchronous Signals

3.1.4 Declarations

3.1.5 Instantaneous Communication and Preemption

3.1.6 Transitions

3.1.7 Actions

3.2 Visual Syntax and Semantics

3.2.1 Termination Transitions

3.2.2 Transition Priorities

3.2.3 Weak Abort Transitions

3.2.4 Entry Actions

3.2.5 Exit Actions

3.2.6 During Actions

3.2.7 Initializations

3.2.8 Connectors

3.2.9 Suspensions

3.2.10 Count Delays

3.2.11 The Pre Operator

3.2.12 History Transitions

3.2.13 Complex Final States

3.2.14 Static Variables

3.2.15 Deferred Transitions

3.3 The Textual Syntax: SCT

3.3.1 Grammar

3.3.2 Identifier Name vs. Label

3.3.3 Priorities

3.3.4 Host Code

3.3.5 Other Elements

3.4 Abstract Syntax

3.4.1 States and Regions

3.4.2 Transitions

3.4.3 Actions

3.4.4 Expressions

3.4.5 Syntax Validation

Interactive Incremental Compilation

4.1 Single-Pass Language-Driven Incremental Compilation (SLIC)

4.1.1 SLIC Foundations

4.1.2 Deriving a SLIC Schedule

4.1.3 SLIC Key Questions

4.1.4 SLIC Order for SCCharts Compilation

4.1.5 SLIC Language and Sublanguage

4.1.6 SLIC Design Challenges

4.2 Interactive Compilation

4.2.1 Traditional User Story

4.2.2 Interactive User Story

4.2.3 Element Tracing

4.3 Interactive Incremental SCCharts Compilation

Compiling SCCharts

5.0.1 High-Level Compilation Overview

5.0.2 Low-Level Compilation Overview

5.1 SyncCharts Compilation

5.2 High-Level Compilation

5.2.1 Compiling ALDO to Core SCCharts

5.2.2 Compiling ALDO to SCG

5.2.3 Transformation Dependencies

5.2.4 Connector

5.2.5 Entry Action

5.2.6 Exit Action

5.2.7 Initialization

5.2.8 Abort

5.2.9 Complex Final State

5.2.10 During Action

5.2.11 Signal

5.2.12 Pre

5.2.13 Suspend

5.2.14 Count Delay

5.2.15 History

5.2.16 Static Variables

5.2.17 Deferred

5.2.18 Weak Suspend

5.2.19 Normalization

5.2.20 Constructing the SCG

5.3 Pseudocode for High-Level Transformations

5.3.1 Connector

5.3.2 Entry Action

5.3.3 Exit Action

5.3.4 Initialization

5.3.5 Abort

5.3.6 Complex Final State

5.3.7 During Action

5.3.8 Signal

5.3.9 Pre

5.3.10 Suspend

5.3.11 Count Delay

5.3.12 History

5.3.13 Static Variables

5.3.14 Deferred

5.3.15 Weak Suspend

5.3.16 Normalization

5.4 Priority-Based Low-Level Compilation

5.4.1 S

5.4.2 S Code Generation

5.4.3 SJL/SCL Code Generation

5.5 Circuit-Based Low-Level Compilation

5.5.1 S Code Generation

5.5.2 Java/C Code Generation

5.6 Compilation Design Choices

5.6.1 Circuit vs. Priority

5.6.2 RISC vs. CISC

5.6.3 Defaults for KIELER SCCharts Compiler Implementation

5.7 SCCharts Targets

5.7.1 Software

5.7.2 Hardware

SCCharts Tooling

6.1 Related Tools

6.1.1 Ptolemy

6.1.2 SCADE

6.1.3 Esterel Studio

6.1.4 Berry Esterel v5.92 Compiler and Simulator

6.1.5 The Columbia Esterel Compiler (CEC)

6.2 Eclipse

6.2.1 Eclipse Plugins

6.3 The KIELER Simulation Infrastructure

6.3.1 KIELER Execution Manager (KIEM)

6.3.2 Data Table

6.3.3 Synchronous Signals View

6.3.4 Benchmark Component

6.4 SCCharts Editor Implementation

6.4.1 KIELER ThinKCharts Editor

6.4.2 The Yakindu SCCharts Editor

6.4.3 The SCCharts Textual Editor

6.4.4 Graphical vs. Textual vs.

Textical

Modeling

6.5 Interactive SLIC Compiler Implementation

6.5.1 KIELER Compiler (KiCo) Implementation

6.5.2 KiCo 1.0 Prototype

6.5.3 Disadvantage of KiCo 1.0

6.5.4 The KiCo 2.0 Advanced Prototype

6.5.5 SLIC Implementation Notes

6.5.6 Interactive Compilation GUI: KiCo.UI

6.5.7 Command Line and Online Compilation

6.6 Automatic Validation

6.6.1 Regression Tests

6.6.2 KIEM JUnit Test Runner

6.6.3 Esterel Input Output Trace (ESO) File Creation

6.6.4 Benchmark Regression Tests

Practicality & Validation: The Model Railway Demonstrator

7.1 Introduction

7.2 SCCharts Model Railway Project

7.2.1 SCCharts Topology Scenario

7.2.2 Complex System Modeling with SCCharts

7.2.3 SCCharts Compilation Performance

7.3 SCCharts Survey

7.3.1 SCCharts vs. Other Languages

Related Projects

8.1 Ptolemy and KIELER

8.1.1 Ptolemy

8.1.2 KIELER leveraging Ptolemy (KlePto)

8.2 KIELER Esterel Integration

8.2.1 Esterel

8.2.2 Meta Model

8.2.3 Simulation and Debugging

8.2.4 Sequentially Constructive Esterel (SCEst)

8.3 Esterel to SyncCharts Transformation

8.4 Synchronous Java (Light)

8.4.1 Coroutines and Deterministic Concurrency

8.4.2 Synchronous C

8.4.3 Synchronous Java — Concept and Realization

Conclusion and Future Work

9.1 Conclusion

9.1.1 Reliable Modeling

9.1.2 Reliable Compilation

9.1.3 Practicality

9.2 Future Work

9.2.1 SCCharts

9.2.2 SCEst and Esterel

9.2.3 Related Projects

Abbreviations

API

Application Programming Interface

ASCII

American Standard Code for Information Interchange

CEC

Columbia Esterel Compiler

CFG

Control-Flow Graph

CISC

Complex Instruction Set Computer

COTS

Commercial Off-The-Shelf

CPU

Central Processor Unit

CT

Continuous Time

DE

Discrete Events

DSL

Domain-Specific Language

ELK

Eclipse Layout Kernel

EMF

Eclipse Modeling Framework

ESO

Esterel Input Output Trace

FPGA

Field Programmable Gate Array

FSM

Finite-State-Machine

GMF

Graphical Modeling Framework

GUI

Graphical User Interface

HDL

Hardware Description Language

HTTP

Hypertext Transfer Protocol

HW

Hardware

ID

Identifier

IDE

Integrated Development Environment

I/O

Input/Output

ISA

Instruction Service Architecture

ISE

Integrated Synthesis Environment

IUR

Initialize-Update-Read

JSON

JavaScript Object Notation

JVM

Java Virtual Machine

KCSS

Kiel Computer Science Series

KEP

Kiel Esterel Processor

KiCo

KIELER Compiler

KIEL

Kiel Integrated Environment for Layout

KIELER

Kiel Integrated Environment for Layout Eclipse Rich Client

KIEM

KIELER Execution Manager

KITS

KIELER Textual SyncCharts

KlePto

KIELER leveraging Ptolemy

KlePto

KIELER leveraging Ptolemy

KLighD

KIELER Lightweight Diagrams

LED

Light-Emitting Diode

M2M

Model-to-Model

MDE

Model Driven Engineering

MDSD

Model Driven Software Development

MoC

Model of Computation

MOML

Modeling Markup Language

NXT

NeXT Generation

OS

Operating System

PC

Personal Computer

PHP

PHP Hypertext Preprocessor

PN

Process Networks

RAM

Random Access Memory

RISC

Reduced Instruction Set Computer

RTL

Real-Time Logic

SC

Synchronous C

SCADE

Safety Critical Application Development Environment

SCCharts

Sequentially Constructive Statecharts

SCEst

Sequentially Constructive Esterel

SCG

Sequentially Constructive Graph

SCL

Lightweight Synchronous C

SCT

SCCharts Textual Language

SDF

Synchronous Data-Flow

SJ

Synchronous Java

SJL

Lightweight Synchronous Java

SLIC

Single-Pass Language-Driven Incremental Compilation

SR

Synchronous Reactive

SSA

Static Single Assignment

SSM

Safe State Machines

STG

State Transition Graph

SW

Software

TCP

Transmission Control Protocol

UI

User Interface

UML

Unified Modeling Language

URI

Uniform Resource Identifier

USB

Universal Serial Bus

VHDL

Very High Speed Integrated Circuit Hardware Description

Language

WCRT

Worst Case Reaction Time

WTO

Write Things Once

WWW

World Wide Web

WYSIWYG

What You See Is What You Get

XML

Extensible Markup Language

List of Figures

1.0.1 Computer system classes

1.0.2 Reactive system cyclic control loop

2.1.1 Synchrony Hypothesis

2.1.2 A Statecharts example

2.2.1 Argos example

2.3.1 SyncCharts notation and example

2.3.2 A Reactive Cell of SyncCharts

2.3.3 Statechart semantic problem example

2.4.1 A simple SCADE automaton

2.4.2 UML Statecharts

2.4.3 Stateflow example

2.6.1 Advantages and limits of SCChart’s sequentially constructive semantics

a Concurrent causality

b Sequential causality

2.6.2 Synchronous program classes

2.7.1 Elements of an SCG

2.7.2 Different types of SCG dependencies

2.7.3 SCG meta model

2.7.4 SCG for the AO example

3.0.1 KIELER SCCharts textical modeling tool

3.1.1 ALDO SCCharts example

3.2.1 Overview of the SCCharts visual syntax

3.2.2 Hiding complexity using extended SCCharts features

a ALDO Extended SCChart

b ALDO Core SCChart

3.2.3 Transition priorities as a tie breaker

3.2.4 Weak abort transitions triggered from the inside

3.2.5 Causally wrong use of a strong aborts

3.2.6 Weak abort or termination do not induce any further constraints

3.2.7 Visibility pitfall when replacing during actions

3.2.8 Example use-case of count delay

3.2.9 Example use-case of history transition

3.2.10 Example use-case of complex final state

3.2.11 Example use-case for static keyword

3.2.12 Example use-case of deferred transition

3.3.1 Host code usage suggestion example

3.4.1 SCCharts meta model (simplified)

4.0.1 High-level interactive model-based compilation user story in KIELER tool

4.1.1 Single-Pass Language-Driven Incremental Compilation as an incremental model-based compilation strategy

4.1.2 Example SLIC features

4.1.3 Example SLIC transformations

4.1.4 Example SLIC schedule

4.1.5 SCCharts transformation dependency details

4.1.6 SCCharts transformation dependencies

4.1.7 SCCharts transformation dependencies without groups

4.2.1 Traditional vs. interactive model-based compilation user story

a Traditional compilation

b Interactive compilation

4.2.2 Element tracing with Single-Pass Language-Driven Incremental Compilation (SLIC) and usage

a Building tracing tree for model elements

b Utilizing tracing tree by convergecasting information

4.2.3 SLIC concept mapped onto KIELER SCCharts tool

5.0.1 SCCharts compilation tree (from [MSvH14])

5.0.2 Five patterns for Normalized (Core) SCCharts and their direct mapping to SCG elements

5.1.1 The SyncCharts-S compiler of KIELER 0.8.0 release

a SyncCharts-S compiler

b SyncCharts compiler transformations

5.1.2 SCCharts compilation tree

5.2.1 KiCo compiler selection for ALDO

5.2.2 High-level compilation from Extended to Core ALDO I/II

5.2.3 High-level compilation from Extended to Core ALDO II/II

5.2.4 High-level compilation from Normalized to SCG ALDO

a Normalized SCChart

b Sequentially Constructive Graph (SCG)

5.2.5 KiCo compiler selection showing all high-level transformations

5.2.6 Statecharts feature transformations

5.2.7 Connector feature expansion transformation

5.2.8 Entry feature expansion transformation

5.2.9 Entry action combined with a strong abort

5.2.10 Exit feature expansion transformation

5.2.11 Exit action combined with a strong abort

5.2.12 Initialization feature expansion transformation

5.2.13 Initialization combined with existing entry action

5.2.14 Simple abort example

5.2.15 Weak abort of cyclic action — before transformation

5.2.16 Weak abort of cyclic action — after transformation (wrong)

5.2.17 Weak abort of cyclic action — after correct transformation

5.2.18 Abort: Ease down-stream compilation

5.2.19 Abort transformation for delayed weak aborts

5.2.20 Abort transformation for delayed weak aborts (similar example)

5.2.21 Abort transformation termination elimination

5.2.22 Abort transformation — further optimizations (I/II)

5.2.23 Abort transformation — further optimizations (II/II)

5.2.24 General case: Abort transformation (WTO)

5.2.26 Abort transformation: Dealing with the (dynamic) transient forking state

5.2.27 Abort: Further ease down-stream compilation and reduce complexity

5.2.28 Abort (non-WTO): Mixing immediate and delayed aborts should not lead to an earlier termination

5.2.29 Abort (non-WTO): Mixing delayed strong aborts with other transformation types should not lead to priority inversion.

5.2.30 Abort (non-WTO): A final state but no termination should not lead to an undesired leaving of a state

5.2.31 General case: Abort transformation (non-WTO)

5.2.32 Enhanced abort transformation with correctly omitted control region (non-WTO)

5.2.33 Nested abort example (original and non-WTO)

5.2.34 Abort feature expansion transformation with connectors

5.2.35 Scheduling problem for self-loops

5.2.36 Complex final state feature expansion transformation

5.2.37 Complex final state feature expansion transformation for two complex final states

5.2.38 Complex final state feature expansion transformation in the hierarchical case

5.2.39 Complex final state feature expansion transformation optimizing regions with final states only

5.2.40 Complex final states in the root state

5.2.41 During action feature expansion transformation

5.2.42 During action examples with termination

5.2.43 During action examples with termination

5.2.44 Simple during transformation and advanced during transformation

5.2.45 During action should continue as long as state S1 is active and not aborted

5.2.46 Simple during action original vs. new transformation

5.2.47 SyncCharts feature transformations

5.2.48 Signal feature expansion transformation

5.2.49 Valued signal feature expansion transformation

5.2.50 Pre operator feature expansion transformation, wrong (b), correct (c), and alternative (d)

5.2.51 Pre operator for states with a termination transition

5.2.52 Nested pre operator feature expansion transformation

5.2.53 Pre operator feature expansion with signals

5.2.54 Pre operator feature expansion with valued signals

5.2.55 Suspend feature expansion transformation

5.2.56 First proposed count delay transformation

5.2.57 Current count delay feature expansion transformation

5.2.58 Count delay combined with suspend feature expansion

5.2.59 Count delay feature with during action

5.2.60 SCADE / QUARTZ / Esterel v7 feature transformations

5.2.61 History feature expansion transformation

5.2.62 Deep history feature expansion transformation

5.2.63 Mixed deep history and shallow history features

5.2.64 Static feature expansion transformation

5.2.65 Deferred feature expansion transformation

5.2.66 Shallow deferred feature expansion transformation

5.2.67 Deep deferred feature expansion transformation

5.2.68 Weak suspend expansion transformation

5.2.70 Weak suspend expansion and scoping

5.2.71 Weak suspend and hierarchy

5.2.72 Normalization transformations

5.2.73 Five allowed patterns for Normalized (Core) SCCharts

5.2.74 Sandwich SCCharts example and S code generation

5.2.75 Trigger/effect normalization transformation examples

5.2.76 Surface/depth normalization transformation and optimization

5.2.77 Apparent priority inversion when normalizing SCCharts

5.2.78 AO example as Extended SCChart, Normalized SCChart and SCG

a AO example as Extended SCChart

b Mapping between Normalized SCCharts pattern constructs and SCG elements

5.4.1 S intermediate language in the context of SCCharts and SyncCharts SW compilation

5.4.2 SCCharts compilation tree (cf. Figure 5.0.1 on page 114): Priority low-level synthesis part

5.4.3 S intermediate language example

5.4.4 S intermediate language meta model

5.4.5 Simulation with the SCCharts compiler predecessor

5.4.6 Priority-based code generation from S

5.5.1 SCCharts compilation tree: Circuit-based low-level synthesis part

5.5.2 Circuit-based code generation from S

5.5.3 Sequentialized SCG examples

a Sequentialized SCG for AO

b Sequentialized SCG for ALDO

5.6.2 Circuit vs. priority SCCharts compilation: Code size

5.6.3 Comparison of Extended SCCharts (CISC) with equivalent Core SCCharts (RISC)

5.6.4 Comparison of C code synthesis paths for SCCharts

5.7.1 SCCharts SW and HW targets

5.7.2 Ardoino microcontroller platform

5.7.4 Targeting the Arduino platform from KIELER

5.7.5 The SCCharts-Arduino demonstrator: ABROINO

5.7.6 SCCharts to Esterel during CEC simulation

5.7.7 Running SCCharts on FPGAs: The ISE tool

5.7.8 AO SCChart visualized as HW circuit inside the KIELER SCCharts tool during simulation

5.7.9 Simulation and visualization of SCCharts compiled to electrical HW circuits

6.1.1 Ptolemy graphical model editor “Vergil”

6.1.2 Simulating a Ptolemy model

6.1.3 ABRO synchronous state machine within the SCADE suite and its model simulation GUI

6.1.4 Esterel Studio GUI

6.1.5 Esterel v5.92 simulator running ALDO

a Tick 0

b Tick 1

c Tick 2

d Tick 3

6.2.1 Eclipse IDE with editors and views

6.2.2 Eclipse extension point mechanism

6.3.1 GUI of the KIELER simulation infrastructure while simulating the ALDO SCCharts model

6.3.2 Schematic overview of KIEM

6.3.3 GUI for input/output and debugging: KIELER Data Table and Synchronous Signals view

6.3.4 Benchmarking user story for SCCharts

6.4.1 GMF dashboard for graphical editor generation

6.4.2 Evolution of KIELER SCCharts editor

a KIEL tool (SyncCharts)

b ThinKCharts editor (SyncCharts)

c Yakindu SCCharts editor

d Xtext and KLighD-based SCCharts editor (current)

6.4.3 KIELER ThinKCharts editor

6.4.4 Yakindu statecharts tools overview

6.4.5 KIELER SCCharts modeling tool implementation

6.5.1 KiCo 1.0 prototype implementation overview

6.5.2 KiCo 1.0 advanced selection algorithm example

6.5.3 KiCo 2.0 advanced prototype implementation overview

6.5.4 KiCo 2.0 advanced selection algorithm example

6.5.5 Example of final SLIC order for processing transformations in a compilation run

6.5.6 The graphical user interface plugin infrastructure of KiCo

6.5.7 Different compiler selection views for the user and the developer of KiCo

6.5.8 KiCo server infrastructure

6.5.9 KiCo server GUI

6.5.10 KiCo command line usage

6.5.11 KiCo online compiler

6.6.1 KIEM JUnit integration running regression tests

6.6.2 KIEM JUnit integration schematics

6.6.3 Creating ESO files manually (left) or automatically (right)

6.6.4 KIEM JUnit integration schematics enhanced with benchmarking

6.6.5 Benchmark output during SCCharts regression tests

6.6.6 KIEM schedule for SCCharts regression tests

7.0.1 Model railway demonstrator

7.1.1 Conceptional view to the communication of the 4th generation compared to the 3th generation

7.1.2 SCCharts controller topology scenario

7.2.1 SCCharts train controller vs. Harel Wristwatch

a Harel’s Wristwatch example

b Top layer of SCCharts train controller

7.2.2 SCCharts SLIC-based compilation approach turns out to be practically usable

a Hiding complexity by using Extended SCCharts features

b Tickets as opened and closed in the bug tracker

7.2.3 Performance of SCCharts SLIC-based compiler

7.2.4 Performance of SCCharts SLIC-based compiler

7.3.1 The SCCharts language compared to other languages

8.1.1 Ptolemy actor model example

8.1.2 A hierarchical and heterogeneous Ptolemy model

8.1.3 SCChart (left) and an automatically generated Ptolemy model (right)

8.1.4 Generated Ptolemy model with optimized inputs and outputs

8.1.5 Traffic Light model automatically generated by KIELER leveraging Ptolemy (KlePto)

8.1.6 Transformation and execution scheme of the Ptolemy-based SyncCharts/SCCharts KlePto simulation

8.1.7 New immediate transitions in Ptolemy

8.2.1 Eclipse EMF Esterel meta model (simplified)

8.2.2 External compiler integeration and simulation visualization concept

8.2.4 External (blackbox) compiler integeration and simulation visualization concept

8.2.5 The KIELER Esterel simulator with visualization is running ALDO by leveraging the CEC

8.2.6 ALDO simulation with KIELER SCEst compiler integration as a CEC alternative

8.2.7 Size and speed comparison of compilation with SCEst and the CEC

8.3.1 Interactive transformations for visual models

8.4.1 Comparison of Lightweight Synchronous Java (SJL) and coroutine thread concepts

8.4.2 SCChart of SJL example

8.4.3 State diagram of an SJL program’s life cycle

8.4.4 Worst-case runtimes, SJL vs. Synchronous Java (SJ) vs. standard Java threads

9.1.1 SCCharts reliable modeling and compilation

Listings

3.3.1 ALDO example as SCCharts Textual Language (SCT)

3.3.2 SCCharts feature overview visualized in Figure 3.2.1 as its textual SCT equivalent

3.3.3 SCT Xtext based grammar excerpt

5.1.1 SyncChartsSSimulationDataComponent.java: Snippet of simulation component applying “SyncCharts extended” feature transformations before calling the SyncCharts to S core compiler Synccharts2S

5.2.1 A snippet from SyncCharts2S compiler, handling transformation for the depth of a state

5.4.1 S intermediate language Xtext grammar

5.7.1 Arduino code generated from AO SCCharts example

8.2.1 ALDO example as an Esterel program

8.2.2 Esterel source-to-source visualization transformation for a statement P

8.2.3 Simple Esterel IO.strl example before simulation visualization transformation

8.2.4 Transformed version IO.simviz.strl after applying the visualization transformation to IO.strl

8.4.1 tick() method of SJL example from Figure 8.4.2

List of Tables

2.6.1 SCCharts transition trigger and effect examples

4.2.1 Comparing transitional and interactive model-based compilation user stories

5.1.1 Advantages and drawbacks of SyncCharts/SCCharts compilers

5.2.1 During actions in root state

5.6.1 Design choices for SCCharts compilation

5.7.1 Advantages of using SCCharts for modeling Arduino software vs. programming the C-like code directly

5.7.2 Comparing the predecessor SCL2VHDL with the current SCG2Circuit SCCharts circuit project

6.1.1 Ptolemy Vergil vs. KIELER Execution Manager (KIEM) simulation features

6.4.1 Graphical vs. Textual vs. Combined Textical Modeling

6.6.1 Semantic vs. syntactic validation

8.4.1 Similarities and differences of coroutines and SJL cooperative thread scheduling

Chapter 1

Introduction

Nowadays, computer systems are present all around. There are different classes [PBEB07] of computer systems which often overlap and are hard to differentiate. Figure 1.0.1 illustrates these classes and gives examples.

PCs already can be found on many desks and are used to program and run simulations, calculations, and to store or query data. Such systems are termed transformational systems.

Transformational systems get some inputs from an environment which is a user or another program. From these inputs, the transformational system computes its outputs by applying a computation function to the inputs.

Figure 1.0.1. Computer system classes (based on [PBEB07])

Transformational systems typically do not run continuously. They also have no time constraints imposed by the environment. Examples for such systems are calculators or weather simulations.

1.0.1 Definition (Environment). An environment of a system is the source of inputs and/or the target of outputs of a system.

A system interacts with its environment using its system interface.

1.0.2 Definition (System Interface). A system interface is the part of internal state variables that are manipulatable and/or visible from the outside (environment). Manipulatable state variables are called inputs, visible state variables are called outputs.

To ease programming of a computer, abstraction layers were invented, namely the Instruction Service Architecture (ISA) and operating systems (OS) [Tan09]. These abstraction layers made programs independent from a concrete hardware. Computer programs were also written in higherlevel programming languages instead of using non-portable and hardly maintainable assembly code. Using programming languages has the benefit of portability and maintainability. However, this comes with a drawback: Since computers only understand low-level assembly code, a program written in a higher-level programming language has to be translated into a computer-understandable machine language. Hardware and OS-specific compilers [ASU07] were needed for this task and these compiles also have to be maintained.

Operating systems are an example of a different class of systems that became common: Interactive systems. They typically handle multiple executing programs at the same time and manage resources. Simultaneously, they often allow interaction with the user, i. e., their environment.

Like transformational systems, interactive systems compute a function, have inputs and outputs and do not have any time constraints imposed by the environment. However, they typically are non-terminating and continuously interact with their environment. Examples are flight booking systems, database systems in general, or operation systems.

Figure 1.0.2. Reactive system cyclic control loop and synchronous tick abstraction (figure based on [MvH14])

Computers have spread in all manners of daily life. Today, computers control traffic lights, they control electronic toothbrushes, they even control our refrigerator and smart homes. A computer may not always be visible in the sense of a typical desktop PC or laptop. Still, a microprocessor is present to do computational tasks which are often control tasks.

Reactive Systems: Reactive systems [HP85] are today’s largest class of computer systems. According to Berry [Ber15], 98% of all manufactured CPUs are not built into a conventional PC but run in (often embedded) reactive systems. Such systems compute functions and have inputs and outputs. Like interactive systems, reactive systems also continuously interact with their environment. However, in contrast to interactive systems, reactive systems have to fulfill their computations in a certain amount of time which is typically imposed by the environment. Reactive systems often not only interact with but also control their environment or at least parts of it by their computed outputs. Inputs for a reactive system typically are sensor information. Examples for reactive systems are temperature regulators but also traffic light controllers, airbag controllers, pace makers, flight controllers, dome light controllers in cars, or electrical toothbrushes.

Key properties of reactive systems are: 1. Reactive systems compute a function, 2. reactive systems run continuously, and 3. reactive systems control their environment by their reaction. Reactive systems often have time constraints derived from the dynamics/physics of their controlled environment.

Figure 1.0.2 visualizes the control loop of a reactive system. In a cyclic fashion it reads inputs from the environment, computes a reaction by the given inputs, and writes the reaction, i. e., the outputs to the environment. The reactive system reacts with computed outputs, i. e., the reaction, to given inputs. Adapting the synchronous approach [BCE+03], we call one reaction computation a tick which is an abstraction of physical time and hence logically assumed to be computed in zero time (cf. Section 2.1 on page →).

1.0.3 Definition (Tick). A tick is one reaction computation of a reactive system based on inputs and a potential internal state.

Embedded Systems: Embedded systems are a subclass of reactive systems that have been in use since the 1970s [LS11]. A simplified but common definition is that embedded systems are computers that are not perceived as such. More specifically, these are systems that are tightly embedded into their environment in order to control it. Typically, these systems have lots of interfacing with sensors and actuators of their environment and must work under harsh conditions such as dust, bad weather, under water, or extreme temperatures. Examples for these systems are temperature regulators, many controllers in cars, or mars robots.

Real-Time Systems: Real-time systems are another subclass of reactive systems. Real-time systems often are embedded systems, i. e., they are embedded into their environment. A correct real-time system must 1. compute the correct value and 2. additionally meet its timing requirements. Examples for real-time systems are traffic light controllers, airbag controllers, or flight controllers.

Safety-Critical Systems: Safety-critical systems are reactive systems that control environments whose overall correct behavior is crucial. The failure of such a system or parts of it typically means extreme danger to human lives or the environment. It is essential that these systems do not fail and guarantee safety. Hence, many real-time and embedded systems also are safety-critical systems. Examples for safety-critical systems are airbag controllers, pace makers, or flight controllers.

Safety-Critical System Development: Since computers are mostly programmed in higher-level programming languages, compilers are around to translate the human readable computer language into bytes that a microprocessor is able to execute.

Especially when it comes to safety-critical systems, it must be ensured that there are no errors in computer software that could lead to system failure. This typically means that safety and liveness properties must be ensured. Safety properties specify that nothing bad ever happens, e. g., failure states are unreachable. Liveness properties specify that something good eventually happens, e. g., a sent communication message is eventually received. [Lyn96, p. →]

Liveness properties for synchronous systems often become (inverted) safety properties because something good must happen in bounded time. This is much stricter than eventually and hence it is observable and decidable whether something good has happened or not happened before a concrete point in time. Model checking helps to verify that safety properties hold.

This is the reason why software or at least critical parts of software for safety-critical systems is often model checked [BBF+01]. Verification of properties using model checking or similar techniques is time consuming and requires significant effort. Hence, validation and well-organized careful testing using simulations is often the only practical alternative in reality for most parts of a system.

Most reactive systems are still programmed in C today [Rus10, p. →]. In order to be able to verify or validate safety and/or liveness properties, usually a model of the software or at least from certain software parts is required.

Modeling is a process of gaining a deeper understanding of a system through imitation. [LS11]

Speaking about models of a software systems, the above statement also holds in the following sense: In order to define safety or liveness properties usually only certain aspects of software, e. g., invariants, loop bounds, or value ranges are considered. As a result of focusing on certain parts, one automatically abstracts from other parts of software like interface code, glue code, low-level driver parts, or network communication. Summarizing, a software model emphasizes certain aspects or parts of software only. Principally, there are two scenarios for retrieving a software model:

Extracting a model afterwards from software [CDH

+

00] or from parts of a software implemented in a programming language. This is out of the scope of this thesis.

Starting with a model in the first place and deriving software code from the model using code generation techniques.

The general process of starting from models in the first place when designing and implementing systems is also termed Model Driven Engineering (MDE) or more specifically w.r.t. engineering/developing software components, Model Driven Software Development (MDSD).

MDSD has the advantage that the software development for a safetycritical system can start at a very high abstraction level which is also very close to the (control) problem that the software is supposed to solve in the end. The higher the abstraction level of a model, the more it is usually understandable also for non-computer scientists such as engineers or domain experts. Additionally, the model for the software is already available at the beginning of the development process and certain (safety) properties can already be checked to be met by the model.

Computer simulations [Fis95] are an established means to analyze the behavior of a system. There are basically two categories of computer simulations: On the one hand one wants to be able to predict and better understand physical systems and train humans to better interact with them (e. g., weather forecasts or flight simulators). On the other hand one aspires to emulate computer systems themselves prior to their physical integration in order to increase safety and cost effectiveness (e. g., airbag controller or mars robot). Software models can also be used for a simulation in order to gain a deeper understanding of the dynamics of the software. Additionally, software simulations of a reactive system can be combined with a co-simulation of a model of the controlled environment that will be used to embed the reactive system later on.

States and Deterministic Concurrency: Reactive systems often not only consider inputs from an environment but have also an internal state that impacts on the computed reaction. Such system states should be expressed in a modeling language that is designed for reactive systems.

Additionally, reactive systems typically fulfill more than one concurrent task. E. g., a mars robot moves forwards while concurrently searching for obstacles to avoid getting stuck or an electrical tooth brush is concurrently observing its on/off button state and additionally a timer to stop brushing. A modeler should be able to express this inherent system concurrency also directly in the software model they build.

Reactive and especially safety-critical systems are expected to work reliably. One important factor for a reliable system is determinism. I. e., a system in any defined and reachable internal state S should always react to the same inputs I with the same outputs O and by changing to the same possibly other internal state S'. Specifying and implementing deterministic concurrency is a hard task as shown for threads by Lee [Lee06]. A modeling language for reactive and safety-critical systems should also be able to maintain determinism for specified concurrency.

Motivation: As discussed before, reactive systems require implementations with a deterministic behavior even if concurrency is involved as it is often the case. Since synchronous languages [BCE+03] cope very well with specifying and implementing deterministic concurrency, it seems reasonable to apply the main concepts from synchronous languages such as the separation of timing and functionality. Using a synchronous language for specifying and implementing software for reactive systems, one advantage is to be able to check such a program against system properties (cf. Section 1.0.3).

Since reactive systems often involve states, a statechart-based [Har87] synchronous language, where the modeler is able to reflect system states directly with states of the modeling language, is reasonable. An advantage of a graphical modeling language is that models can even be read and understood by non-computer scientists such as domain experts. SyncCharts [And96] is one major representative of a synchronous and graphical statechart dialect.

Typically, synchronous languages have a common drawback. This is a steep learning curve especially for the majority of programmers that are used to imperative languages such as C or Java. These imperative languages naturally allow to specify sequential parts such as :

In contrast, synchronous languages tend to restrict the usage of variables/signals in the sense that for each tick a consistent value must exist. E. g., the code above would often be conservatively rejected because done would not be allowed to have both values false and true in one and the same tick. Sequential constructiveness [vHMA+13c] overcomes this typical drawback by allowing multiple value assignments to a variable per tick if these are ordered sequentially (non-concurrent). This seems naturally more appealing and intuitive for programmers that have experience in classical imperative languages and to still preserves the deterministic nature of synchronous languages.

For the above reasons, a statechart dialect such as SyncCharts is a reasonable choice for modeling reactive systems. However, a sequential constructive semantics is preferable in order 1. to accept more models, 2. to lower the learning curve, and 3. to be more intuitive for the majority of imperative language programmers.

Reactive systems often are safety-critical systems that require reliable software. Hence, reliable models need be build in the first place. A modeling environment, i. e., the tooling, should support the modeler in (a) building reliable models

by providing abstraction mechanisms,

by supporting the modeler to understand the language, its features, and whole models,

by providing a simulation for analyzing, understanding, and validating dynamic behavior,

by offering optimizations to make models more compact and more readable, and

by supporting fine-tuning to optimize the speed or size of the final code.

Such a tool chain must also be practically usable. Additionally, a compiler for a modeling language which targets safety-critical systems needs to (b) be reliable itself:

It should be well-structured,

it should be easy to understand every single part of it,

it should be extensible such that new functionality can be added easily, and

it should be maintainable such that parts that break can be fixed in isolation, i. e., without breaking other parts.

Any new modeling, tooling, and compilation concepts that lead towards (a) a reliable tool chain and (b) a reliable compiler should be evaluated for a concrete modeling language. This language should include well known and common features in order to validate the practicality and the reasonableness of the overall approach.

1.1 Contributions of this Thesis

The major contributions of this thesis are threefold:

A novel synchronous statechart dialect termed

SCCharts

which for the first time leverages the sequentially constructive semantics and all of its benefits in a ready-to-use modeling language (cf.

Chapter 3

). SCCharts focus the development of safety-critical systems, since this primary usecase was considered when the language and its features were designed.

A novel interactive incremental compilation strategy based on model transformations termed

Single-Pass Language-Driven Incremental Compilation (SLIC)

(cf.

Chapter 4

). SLIC is specifically designed to facilitate building reliable compilers and models as required in the context of safety-critical system development.

An application of SLIC for compiling SCCharts language features. These language features are common and well known from other synchronous languages. SLIC-based model transformations were defined and are studied in this thesis by giving relevant examples and pseudocode (cf.

Chapter 5

).

The KIELER SCCharts tool (cf. Chapter 6) is implemented in order to validate the SCCharts language, the SLIC approach, and the proposed model transformations. The language, a generic interactive incremental compiler, and the model transformations are parts of this implementation. To show the practicality of the proposed approach, the reference implementation for the SCCharts modeling tools and compiler were used and validated in the context of medium-sized, real world safety-critical systems (cf. Chapter 7). Related projects (cf. Chapter 8) deal for example with integrating other synchronous languages such as Esterel into the KIELER SCCharts tools for validation purposes or with providing a Java-based runtime for a software-targeted compilation path of SCCharts.

1.2 Related Publications

The following publications contain parts of this thesis. A brief summary of each publication and its relation to this thesis is given. Additionally, a list of student theses advised by the author is given. The publications are sorted by importance w. r. t. this thesis.

1.2.1 Major Publications

The following listed publications are stronger connected to this thesis.

[MSvH14] Christian Motika, Steven Smyth, and Reinhard von Hanxleden. Compiling SCCharts— A Case-Study on Interactive Model-Based Compilation.

In Proceedings of the 6th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2014), volume 8802 of LNCS, page 443–462, Corfu, Greece, October 2014

This paper introduces the novel interactive incremental model-based compilation approach termed SLIC. It further exemplifies SLIC for the use-case of incrementally compiling SCCharts. This paper summarizes the main results of this thesis that are discussed here in Chapter 4 and Chapter 5.

[vHDM+14] Reinhard von Hanxleden, Björn Duderstadt, Christian Motika, Steven Smyth, Michael Mendler, Joaquín Aguado, Stephen Mercer, and Owen O’Brien. SCCharts: Sequentially Constructive Statecharts for Safety-Critical Applications. In Proc. ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI’14), Edinburgh, UK, June 2014

This paper introduces the SCCharts language and its incremental features (cf. Chapter 3). It further summarizes the circuit-based and the priority-based low-level compilation paths for SCCharts (cf. Chapter 5).

[vHDM+13c] Reinhard von Hanxleden, Björn Duderstadt, Christian Motika, Steven Smyth, Michael Mendler, Joaquín Aguado, Stephen Mercer, and Owen O’Brien. SCCharts: Sequentially Constructive Statecharts for Safety-Critical Applications. Technical Report 1311, Kiel University, Department of Computer Science, December 2013

This technical report gives details on categorization of SCCharts features. It further explains how these features are incrementally compiled. This is described as an application of model transformations which are presented by examples. These transformations, in some cases an updated version, are discussed here in Chapter 5.

[SMSR+15] Steven Smyth, Christian Motika, Alexander Schulz-Rosengarten, Nis Boerge Wechselberg, Carsten Sprung, and Reinhard von Hanxleden. SCCharts: The Railway Project Report. Technical Report 1510, Kiel University, Department of Computer Science, August 2015

This technical report is a publication of the experiences when trying to solve realistic medium-sized real world problems with SCCharts and its tool chain. Results of this model railway practical student course are presented in Section 7.2 on page →.

[RSM+16] Francesca Rybicki, Steven Smyth, Christian Motika, Alexander Schulz-Rosengarten, and Reinhard von Hanxleden. Interactive modelbased compilation continued — interactive incremental hardware synthesis for SCCharts. In Proceedings of the 7th International Symposium on Leveraging Applications of Formal Methods, Verification and Validation (ISoLA 2016), LNCS, Corfu, Greece, October 2016.

This paper reports on how to leverage the interactive incremental SLIC compilation for hardware synthesis. The interactive incremental synthesis of electrical circuits from SCCharts is part of the discussion in Section 5.7.2 on page → about reasonable targets. It further validates that the SLIC approach is not limited to software code generation.

[MvHH12] Christian Motika, Reinhard von Hanxleden, and Mirko Heinold. Synchronous Java: Light-Weight, Deterministic Concurrency and Preemption in Java. Technical Report 1213, Kiel University, Department of Computer Science, October 2012

[MvHH13] Christian Motika, Reinhard von Hanxleden, and Mirko Heinold. Programming Deterministice Reactive Systems with Synchronous Java (Invited Paper). In Proceedings of the 9th Workshop on Software Technologies for Future Embedded and Ubiquitous Systems (SEUS 2013), IEEE Proceedings, Paderborn, Germany, 17/18 June 2013

[MvH14] Christian Motika and Reinhard von Hanxleden. Light-weight Synchronous Java (SJL) — An Approach for Programming Deterministic Reactive Systems with Java. Journal of Computing, Special Issue on Software Technologies for Embedded and Ubiquitous Systems, 97(3):281–307, 2014

These three papers present Synchronous Java (SJ) and its lightweight successor SJL, which both bring language concepts and constructs well known from synchronous programming to Java. This can help achieving deterministic concurrent Java programs either as a target for code generation or as a language for programming deterministic (embedded) Java software directly. Synchronous Java is discussed in Section 8.4 on page → as a software target for the priority-based SCCharts compilation path (cf. Section 5.4 on page →).

1.2.2 Other Publications

The following listed publications are also partially connected to this thesis.

[vHMA+13c] Reinhard von Hanxleden, Michael Mendler, Joaquín Aguado, Björn Duderstadt, Insa Fuhrmann, Christian Motika, Stephen Mercer, Owen O’Brien, and Partha Roop. Sequentially Constructive Concurrency–A Conservative Extension of the Synchronous Model of Computation. Technical Report 1308, Kiel University, Department of Computer Science, August 2013

[vHMA+13a] Reinhard von Hanxleden, Michael Mendler, Joaquín Aguado, Björn Duderstadt, Insa Fuhrmann, Christian Motika, Stephen Mercer, and Owen O’Brien. Sequentially Constructive Concurrency–A Conservative Extension of the Synchronous Model of Computation. In Proc. Design, Automation and Test in Europe Conference (DATE’13), page 581-586, Grenoble, France, March 2013

[vHMA+14] Reinhard von Hanxleden, Michael Mendler, Joaquín Aguado, Björn Duderstadt, Insa Fuhrmann, Christian Motika, Stephen Mercer, Owen O’Brien, and Partha Roop. Sequentially Constructive Concurrency–A Conservative Extension of the Synchronous Model of Computation. ACM Transactions on Embedded Computing Systems, Special Issue on Applications of Concurrency to System Design, 13(4s):144:1–144:26, July 2014

The above three papers introduce the sequentially constructive model of computation and compare it to other synchronous models of computation. It is the semantical foundation of SCCharts (cf. Section 2.6 on page →).

[SSM+13] Miro Spönemann, Christoph Daniel Schulze, Christian Motika, Christian Schneider, and Reinhard von Hanxleden. KIELER: Building on Automatic Layout for Pragmatics-Aware Modeling (Showpiece). In Proceedings of the IEEE Symposium on Visual Languages and Human-Centric Computing (VL/HCC’13), San Jose, CA, USA, September 2013

This paper focuses advantages of textical modeling, i. e., textual modeling combined with a graphical view by utilizing automatic layout as a keyenabler. This kind of modeling is also proposed for modeling SCCharts (cf. Section 6.4.4 on page →) and an integral part of the interactive compilation user story (cf. Section 4.2 on page →).

[MFvH10] Christian Motika, Hauke Fuhrmann, and Reinhard von Hanxleden. Semantics and Execution of Domain-Specific Models. In 2nd Workshop Methodische Entwicklung von Modellierungswerkzeugen (MEMWe 2010) INFORMATIK 2010, GI-Edition - Lecture Notes in Informatics (LNI), page 891-896, Leipzig, Germany, September 2010

This paper reports on the results of my diploma thesis [Mot09]. This work dealt with defining semantics for high-level modeling languages based on model transformations and about using the Ptolemy tool to practically realize this for arbitrary semantics (KlePto). It further described how this technique can be leveraged to execute models. The simulation infrastructure discussed in Section 6.3 on page → and more specifically the Execution Manager discussed in Section 6.3.1 on page → are strongly rooted in that work. Also the extensions of the KlePto project described in Section 8.1.2 on page → are based on that work.

[MFvHL12] Christian Motika, Hauke Fuhrmann, Reinhard von Hanxleden, and Edward A. Lee. Executing Domain-Specific Models in Eclipse. Technical Report 1214, Kiel University, Department of Computer Science, October 2012

This paper reports on extensions to the Execution Manger and the KlePto project. Sections 6.3.1 and 8.1.2 summarize these extensions.

[RSM+15] Karsten Rathlev, Steven Smyth, Christian Motika, Reinhard von Hanxleden, and Michael Mendler. SCEst: Sequentially Constructive Esterel. In Proceedings of the 13th ACM-IEEE International Conference on Formal Methods and Models for System Design (MEMOCODE’15), Austin, TX, USA, September 2015

The paper on SCEst describes a conservative semantical extension of classical Esterel in the sense of the sequentially constructive model of computation. SCEst is addressed briefly in Section 8.2.4 on page → mainly as an alternative Esterel compiler for validation purposes.

[vHLMF12a] Reinhard von Hanxleden, Edward A. Lee, Christian Motika, and Hauke Fuhrmann. Multi-View Modeling and Pragmatics in 2020 — Position Paper on Designing Complex Cyber-Physical Systems. In Pre-Proceedings of the 17th International Monterey Workshop on Development, Operation and Management of Large-Scale Complex IT Systems, Oxford, UK, 19–21 March 2012

This paper conjectures about modeling in a few years from now, incorporating all known current state of the art techniques such as auto layout, model transformations, or visualizations of particular artifacts in transient views. These ideas in general have influenced the tooling of SCCharts as discussed in Chapter 6.

[RMvH11] Ulf Rüegg, Christian Motika, and Reinhard von Hanxleden. Interactive Transformations for Visual Models. In 3rd Workshop Methodische Entwicklung von Modellierungswerkzeugen (MEMWe 2011) at conference INFORMATIK 2011, GI-Edition - Lecture Notes in Informatics (LNI), Berlin, Germany, October 2011

This paper reports on interactively transforming Esterel models to Sync-Charts, the predecessor of SCCharts. The idea of utilizing interactive model transformations as used for compiling SCCharts (cf. Section 4.3 on page →) was partly inspired by this contribution. The Esterel tooling (cf. Section 8.2 on page →) is partly based on the implementation of this work. Results of this contribution are summarized in Section 8.3 on page →.

1.2.3 Supervised Theses

Additionally, this thesis is based on parts of the following student theses supervised by the author:

[Ryb16] Francesca Rybicki, Interactive Incremental Hardware Synthesis for SCCharts, March 2016

This thesis deals with leveraging the interactive incremental SLIC approach for synthesizing hardware circuits (cf. Section 5.7.2 on page →).

[Nas15] Stanislav Nasin, Transformation from SCCharts to Esterel, October 2015

The topic of this thesis was to try transforming graphical SCCharts to textual Esterel programs (cf. Section 5.7.2 on page →).

[Pei15] Lars Peiler, Modeling Simulations of Autonomous, Safety-Critical Systems, September 2015

In this thesis, SCCharts was evaluated as a language for building environment simulations.

[And15] Lewe Andersen, Quadrocopter Flight Control Design using SCCharts, September 2015

This thesis successfully utilized SCCharts for building a flight controller for a quadrocopter.

[Mac15] Felix Machaczek, Collision Avoidance of Safety-Critical Real-Time Systems, September 2015

The contribution of this thesis was a collision avoidance algorithm implemented in SCCharts for the quadrocopter project.

[Wec15] Nis Wechselberg, Model Railway 4.0 - A Demonstrator for Interactive Timing Analysis, March 2015

The topic of this thesis was to realize the renewal proposal (cf. Figure 7.1.1 on page →) for the model railway demonstrator that is also used to validate the practicality of the SCCharts tooling.

[Rat15] Karsten Rathlev, From Esterel to SCL, March 2015

This thesis implemented the SCEst compiler by re-using large parts of the low-level SCCharts compilation chain (cf. Section 8.2.4 on page →).

[SR14] Alexander Schulz-Rosengarten, Framework zum Tracing von EMF-Modelltransformationen, March 2014

This theses deals with the tracing of model transformations as it can be used together with SLIC (cf. Section 4.2.3 on page →).

[Joh13] Gunnar Johannsen, Hardwaresynthese aus SCCharts, October 2013

This thesis firstly evaluates how to synthesize hardware circuits from SCCharts and execute these on FPGAs (cf. Section 5.7.2 on page →).

[Smy13] Steven Smyth, Code Generation for Sequential Constructiveness, July 2013

This thesis studied the low-level circuit-based compilation path and provided an implementation (cf. Section 5.5 on page →) that is still used as an integral part of the SCCharts compiler.

[Har13] Wahbi Haribi, A SyncChart-Editor based on Yakindu, March 2013

The first Eclipse-based prototype SCCharts editor was the result of this thesis (cf. Section 6.4.2 on page →).

[Dud12] Björn Duderstadt, A Statechart Dialect With Sequential Constructiveness, December 2012

This thesis studied and implemented parts of an industrial prototype for the SCCharts language including parts of a first sample compilation path.

[Rue11] Ulf Rüegg, Interactive Transformations for Visual Models, March 2011

The topic of this thesis was to interactively, stepwisely transform Esterel programs into graphical SyncCharts (cf. Section 8.3 on page →).

[Car10] John Carstens, Datenvisualisierung in grafischen Modellen, September 2010

This thesis studied practical possibilities to visualize data in graphical models.

[Hei10] Mirko Heinold, Synchronous Java, September 2010

In this thesis, a first prototype of Synchronous Java was developed.

[Klo10] Paul Klose, Beispiel Management in KIELER, September 2010

This thesis contributed an example management for our Eclipse-based SCCharts tooling.

[Ame10] Torsten Amende, Synthese von SC-Code aus SyncCharts, May 2010

Part of this thesis was an implementation of the first priority-based compilation path for SyncCharts, the predecessor of SCCharts (cf. Section 5.4.2 on page →).

[Han10] Sören Hansen, Configuration and Automated Execution in the KIELER Execution Manager, March 2010

This thesis contributed extensions for the simulation infrastructure used in our Eclipse-based SCCharts tooling.

1.3 Outline

Chapter 1.3 introduces into synchronous programming. It outlines similar synchronous languages, related work, the sequentially constructive model of computation (MoC), and the intermediate control-flow graph representation (SCG) used for compiling SCCharts. Chapter 3 introduces the SCCharts language, its features, and its semantics. It presents the visual syntax as well as a textual one. An abstract syntax is finally introduced, which is the basis for the model transformation-based compilation approach. Chapter 4 introduces the Single-Pass Language-Driven Incremental Compilation (SLIC) approach that is based on model transformations. It compares the traditional and the interactive compilation user story including a brief summary of element tracing benefits for the SLIC approach. Chapter 5 gives details on the concrete SCCharts compilation process including the highlevel model transformations for eliminating extended SCCharts features. Various examples are discussed and pseudocode for these transformations is given. It further illustrates design choices also for the low-level priority and circuit-based synthesis. Chapter 6 introduces the KIELER SCCharts implementation and its tooling that is used to study the language, the SLIC concepts, and the concrete model transformations. Chapter 7 reports on how SCCharts have been used in practice to validate the language and the compiler. A model railway demonstrator is introduced, which is a reactive embedded real-time system. A survey evaluation based on a student project which had the topic to build an SCCharts-based multi-train controller concludes the evaluation of practicality aspects. Chapter 8 summarizes other closely related projects that influenced the work on SCCharts and its KIELER implementation. Chapter 9 concludes and gives outlook on future work for SCCharts and SLIC-based interactive incremental compilation.

Chapter 2

Background and Related Work

2.1 Synchronous Languages

This chapter presents the basics on synchronous programming and synchronous languages [BCE+03] in general which influenced the work on SCCharts. It also introduces the sequentially constructive MoC and a control-flow representation named SCG that is used as an intermediate representation to compile SCCharts.

Synchrony Hypothesis: All synchronous languages are based on the synchrony hypothesis [BC84] which assumes that a reactive system computes its reactions conceptually infinitely fast. Under this assumption, reaction intervals become single instances in time. These instances are called ticks as defined in Section 1.0.2 on page →.

In short, the synchrony hypothesis states the following:

Time is divided into discrete ticks.

There is a zero computation time for a reaction, i. e., outputs are present instantly together with the inputs for each tick.

The rationale for this hypothesis is discussed in the following paragraphs.

Ticks: As shown in the lower part of Figure 2.1.1, physical time is divided into logical ticks. Hence, a tick logically is a point in time and time logically advances only from one tick to the next tick. The synchrony hypothesis states that inputs and outputs are present at the same point in time (tick) because of zero computation time. Of course this is not a practical assumption for the real system. In reality, outputs have to be computed first to become available as shown in the upper part of Figure 1.0.2 on page →. Computation time is not zero in reality. Thus, the logical point in time is stretched as shown in Figure 2.1.1 to become a time interval. A tick is often also referred to as a reaction cycle.

Figure 2.1.1. Synchrony Hypothesis: Discrete ticks and conceptually zero computation time illustration (figure based on [LM01])

The logical concept of synchrony is mapped into reality by requiring that all computed outputs, i. e., the reaction, is available strictly before the next tick. Based on this assumption, the interval time may be abstracted to represent a single point in time whenever the inputs and their computed reaction-outputs become available. This simplification is a key benefit for synchronous programs and it makes them far more easy to verify or validate.

The separation of functionality and timing is most significant for making good abstractions from the actual target hardware. This abstraction can be done because the assumption for any target hardware is that one tick can be computed in time before the next tick. In order to achieve regular clocked ticks, “in time” means that a bound on reaction computation time must be found that holds for every single tick. In Figure 2.1.1, this bound is denoted as the Worst Case Reaction Time (WCRT). The actual reaction computation of tick n, i.e., react(n), is always less or equal to this bound. The WCRT can be derived by looking at the longest path of transitions (cf. Figure 2.1.1) which could be taken to compute a reaction.

The purpose of WCRT analysis is to find this bound or verify that a bound holds. Thus, on the one hand, this bound imposes constraints on the minimal tick time, i. e., it sets an upper bound how frequent a reactive system can compute consecutive reactions. On the other hand, if there are physical time constraints of the controlled environment, e. g., for an engine control, then this may limit the WCRT and has to be considered in the system implementation step or even already at design time. Timing analysis therefore is crucial for developing synchronous reactive programs. It is studied in various recent projects [MvHT09, FBSvH14].

Synchronous Languages: SyncCharts [And96] is a graphical statechart dialect with a synchronous semantics. It is introduced in more detail in Section 2.3. Esterel [Ber02] is a control-flow oriented textual synchronous language that has been already used for developing embedded hardware and software utilized in a commercial tool called Esterel Studio1. Esterel can be seen as a textual variant of SyncCharts. It is discussed in Section 8.2 on page →.

There are similar textual synchronous languages which focus dataflow semantics such as Lustre [CPHP87] or Lucy-n [MPP10]. Safety Critical Application Development Environment (SCADE)2 is a textual and graphical synchronous language, which was based on Lustre but was extended to express control-flow as well as data-flow. It is successfully used, e. g., in avionics industry and its qualified code generator satisfies highest safety standards like DO-178B level A. It is a commercially used synchronous language and tool suite for developing safety-critical systems.

Figure 2.1.2. A Statecharts example from David Harel [Har87]

2.2 Statecharts

Statecharts [Har87] were invented by David Harel in 1987. Basically, Statecharts are Mealy machines [Mea55] with hierarchy, orthogonality, and broadcast-communication. Figure 2.1.2 shows an example Statechart.

Hierarchy: A state may contain further behavior inside, which is expressed as an inner Statechart itself.

Orthogonality: Orthogonality is expressed as a dashed line that separates concurrent Statecharts.

Broadcast: Broadcast (communication) events that may occur inside parts of the Statechart are visible inside their entire scope.

In contrast to SCCharts, Statecharts do not have a synchronous semantics. Additionally, Statecharts allow inter-level transitions, which are forbidden for SCCharts in favor of a clear semantics.

Figure 2.2.1. Argos parallel composition example of two-bit counter (left), its semantics (middle), and encapsulation (right) of communication signal b (from [MR01])

The Statecharts semantics and its STATEMATE tool implementation is intensely studied by Harel and Naamad [HN96].

2.2.1 Argos

Argos3 [Mar92] is a synchronous language is an considered one of the major predecessors of SyncCharts. Hence, Argos plays an historically important role also for SCCharts.

Argos basically consists of operators which allow hierarchical and parallel composition of mealy machines. Argos models can appear in a graphical syntax like Statecharts (cf. Figure 2.2.1). In contrast to Statecharts, Argos models do not have inter-level transitions and also other Statecharts features are missing. Some of these missing features could be described by combining primitive Argos operators. This is quite similar to SCCharts, which also are based on a small set of core features, while Extended SCCharts features are defined as a combination of these core features.

Figure 2.2.1 shows an Argos two-bit counter example for the parallel composition of two boolean mealy machines (left) and its semantics (middle). In Argos, parallel composition is used to describe the composition of independent concurrent parts which does not involve any implicit synchronization as this is the case for SCCharts.

When concurrently being in states A1 and B1, and the input a is present but b is not, then the transition from A1 to A0 is taken which emits b. But the concurrent part will remain in state B1 and not react to this emission b as it would be the case for SyncCharts and SCCharts.

Note that Argos is also capable of specifying instantaneous communication by using encapsulation of dedicated synchronization signals. This is done on the right side of Figure 2.2.1 for the communication signal b where certain transitions have been removed. Only those transitions are left for which the synchronization described in the encapsulation applies to. Details on Argos can be found elsewhere [Mar92, MR01].

2.3 SyncCharts

SyncCharts [And96] were invented by Charles André in 1996. SyncCharts are basically Statecharts with a synchronous semantics. SyncCharts often are seen as a graphical variant of Esterel. This is quite a good approximation because of an extremely similar set of language features [PTvH06] and the same MoC.

SyncCharts can be seen as a predecessor of SCCharts. SCCharts borrow most of their visual syntax from SyncCharts and extend their semantics. Hence, every valid SyncChart is a valid SCChart with the same4 meaning.

SyncCharts were previously integrated into KIELER with different compiler implementations which also served as a basis for ideas of todays SCCharts interactive incremental compiler. The syntactical and semantical details of SyncCharts are introduced using the ABRO example.

(a) SyncCharts FSM notation

(b) ABRO SyncChart

(c) ABRO SCChart

Figure 2.3.1. SyncCharts notation and example from Charles André (from [And03])

2.3.1 ABRO

SyncCharts consist of states, initial and final states, transitions, signals (events), hierarchy, concurrency, and modularity. An example SyncChart, the ABRO hello world of synchronous programming is shown in Figure 2.3.1b next to some self-explaining basic concrete syntax excerpt of SyncCharts (cf. Figure 2.3.1a). Figure 2.3.1c