Topic 1: Synchronous Languages

Topic 1: Synchronous Languages Seyed Hosein Attarzadeh Niaki KTH

November 9, 2009

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

1 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

2 / 68

Real-Time and Reactive Systems Definition A reactive system is a system that maintains a permanent interaction with its environment.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

3 / 68

Real-Time and Reactive Systems Definition A reactive system is a system that maintains a permanent interaction with its environment.

Definition A real-time system is a reactive system that is in addition subject to externally defined timing constraints.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

3 / 68

Real-Time and Reactive Systems Definition A reactive system is a system that maintains a permanent interaction with its environment.

Definition A real-time system is a reactive system that is in addition subject to externally defined timing constraints. Safety is a crucial concern Logical correctness Temporal correctness

Low-level programming techniques are not acceptable. They make behavior understanding and analysis almost impracticable.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

3 / 68

Application areas 1

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

3

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above Low level signal processing in digital communication systems high throughput → handle algorithm and architecture in same framework

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

3

4

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above Low level signal processing in digital communication systems high throughput → handle algorithm and architecture in same framework Industrial process control in regulators supervised by interrupts and sequential tasks a tool allowing easy specification with correct implementation

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

3

4

5

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above Low level signal processing in digital communication systems high throughput → handle algorithm and architecture in same framework Industrial process control in regulators supervised by interrupts and sequential tasks a tool allowing easy specification with correct implementation Complex signal processing systems in radar and sonar computationally intensive → same as above + speed

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

3

4

5

6

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above Low level signal processing in digital communication systems high throughput → handle algorithm and architecture in same framework Industrial process control in regulators supervised by interrupts and sequential tasks a tool allowing easy specification with correct implementation Complex signal processing systems in radar and sonar computationally intensive → same as above + speed Complex Control-and-Monitoring systems in govern aircraft and transportation systems, hazardous plants heuristics of high computational complexity +distributed architecture

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Application areas 1

2

3

4

5

6

7

Pure task sequencers in command boards, computer integrated manufacturing high combinatorial complexity → convert specification to implementation Communication protocols in real-time LANs similar concerns as above Low level signal processing in digital communication systems high throughput → handle algorithm and architecture in same framework Industrial process control in regulators supervised by interrupts and sequential tasks a tool allowing easy specification with correct implementation Complex signal processing systems in radar and sonar computationally intensive → same as above + speed Complex Control-and-Monitoring systems in govern aircraft and transportation systems, hazardous plants heuristics of high computational complexity +distributed architecture C3 -systems(Command-Control-Communicate) in military systems, air traffic control moving subsystems → communication links are time variant

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

4 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important!

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important! 1

Use modular and formal techniques to specify, implement and verify. necessary to reflect conceptual architecture into programs themselves

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important! 1

Use modular and formal techniques to specify, implement and verify. necessary to reflect conceptual architecture into programs themselves

2

Encompass within a single framework all reactive aspects. may be relaxed with cleanly defined interfaces

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important! 1

Use modular and formal techniques to specify, implement and verify. necessary to reflect conceptual architecture into programs themselves

2

Encompass within a single framework all reactive aspects. may be relaxed with cleanly defined interfaces

3

Deal with distributed target architectures. because of performance requirements or geographical constraints

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important! 1

Use modular and formal techniques to specify, implement and verify. necessary to reflect conceptual architecture into programs themselves

2

Encompass within a single framework all reactive aspects. may be relaxed with cleanly defined interfaces

3

Deal with distributed target architectures. because of performance requirements or geographical constraints

4

Preserve determinism whenever possible. tools should not force indeterminism unless specifically required to

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Major Issues Systems naturally decompose into communicating concurrent components → communication, synchronization, and organization of dataflow is important! 1

Use modular and formal techniques to specify, implement and verify. necessary to reflect conceptual architecture into programs themselves

2

Encompass within a single framework all reactive aspects. may be relaxed with cleanly defined interfaces

3

Deal with distributed target architectures. because of performance requirements or geographical constraints

4

Preserve determinism whenever possible. tools should not force indeterminism unless specifically required to

5

Consider issue of speed. Efficient, Execution times should be predictable if possible

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

5 / 68

Real-Time Programming Techniques 1

Connect programs using OS communication primitives (+) presently lot of experience using this technique (-) no single object to study → no automatic behavior analysis, nondeterminism

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

6 / 68

Real-Time Programming Techniques 1

Connect programs using OS communication primitives (+) presently lot of experience using this technique (-) no single object to study → no automatic behavior analysis, nondeterminism

2

Using Finite-States Machines (+) deterministic, efficient, automatically analyzable (-) do not directly support hierarchy and concurrency, hard to understand when become large

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

6 / 68

Real-Time Programming Techniques 1

Connect programs using OS communication primitives (+) presently lot of experience using this technique (-) no single object to study → no automatic behavior analysis, nondeterminism

2

Using Finite-States Machines (+) deterministic, efficient, automatically analyzable (-) do not directly support hierarchy and concurrency, hard to understand when become large

3

Using Petri Nets (+) support concurrency (-) lack of modular structure, lack of determinism

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

6 / 68

Real-Time Programming Techniques 1

Connect programs using OS communication primitives (+) presently lot of experience using this technique (-) no single object to study → no automatic behavior analysis, nondeterminism

2

Using Finite-States Machines (+) deterministic, efficient, automatically analyzable (-) do not directly support hierarchy and concurrency, hard to understand when become large

3

Using Petri Nets (+) support concurrency (-) lack of modular structure, lack of determinism

4

Classical Concurrent Programming Languages (ADA) (+) support concurrency, support modularity (-) unpredictable communication

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

6 / 68

Synchronous Approach

makes deterministic hierarchical concurrent specification and programming possible leads to efficient and controllable object code makes it possible to use automatic verification tools by avoiding state space explosion

Main Simplification Sets of ideal systems compose very well into other ideal systems

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

7 / 68

Example 1: Clicking on a Mouse 1

state changes synchronous with inputs

2

output emission synchronous with state change

3

signal reception synchronous with signal emission (broadcast)

4

output behavior of MOUSE fixed with global interleaving of inputs

a discrete event system Only the global ordering makes sense, the interval between successive events does not need to be constant with respect to some externally given notion of absolute time. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

8 / 68

Example 2: A Digital Filter

yn = a1 yn−1 + a2 yn−2 + b0 un + b1 un−1 + b2 un−2 + vn The first three rules of previous example apply. But, not every global interleaving is allowed for inputs: to each sample of u must correspond a unique sample of v .

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

9 / 68

Synchronous Modeling Summary In an ideal real-time machine: Output is synchronous with input, internal actions are instantaneous, communications are performed via instantaneous broadcasting, The global interleaving of the external communications may be partially chosen by the environment (essential in behavior analysis).

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

10 / 68

Synchronous Modeling Summary In an ideal real-time machine: Output is synchronous with input, internal actions are instantaneous, communications are performed via instantaneous broadcasting, The global interleaving of the external communications may be partially chosen by the environment (essential in behavior analysis). There are two different (but equivalent) forms of synchronous modeling: 1

State based formalisms generalized by Statecharts, Also in CSML and Esterel. Suits problems where control flow is prevalent.

2

Multiple Clocked Recurrent Systems (MCRS’s) in Lustre and Signal. Suits problems where data flow is prevalent.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

10 / 68

Synchronous Modeling Summary In an ideal real-time machine: Output is synchronous with input, internal actions are instantaneous, communications are performed via instantaneous broadcasting, The global interleaving of the external communications may be partially chosen by the environment (essential in behavior analysis). There are two different (but equivalent) forms of synchronous modeling: 1

State based formalisms generalized by Statecharts, Also in CSML and Esterel. Suits problems where control flow is prevalent.

2

Multiple Clocked Recurrent Systems (MCRS’s) in Lustre and Signal. Suits problems where data flow is prevalent.

Formal models corresponding to these different frameworks can be shown equivalent.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

10 / 68

Synchronous Approach Considerations Solving Communication Equations in both approaches they may have: no solution: constraint contradiction, deadlock cycles infinitely many solutions: nondeterminism a single solution: proper candidate for proper execution

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

11 / 68

Synchronous Approach Considerations Solving Communication Equations in both approaches they may have: no solution: constraint contradiction, deadlock cycles infinitely many solutions: nondeterminism a single solution: proper candidate for proper execution Program Verification for liveness of safety properties, respect of total or partial specifications: using model checkers to compare infinite sequence of events of a program with a set of properties stated using a different formalism, providing user with a reduced program behaving like the original with a subset of signals, in MCRS formalisms, constraints or properties can be specified as further equations. Compiler is the verifier.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

11 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures The synchronous approach to asynchronous implementations: 1

When feasible strictly synchronous execution of synchronous systems are valid (VLSI)

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures The synchronous approach to asynchronous implementations: 1

When feasible strictly synchronous execution of synchronous systems are valid (VLSI)

2

Verification and proofs of correct synchronization and logic are available in synchronous approach

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures The synchronous approach to asynchronous implementations: 1

When feasible strictly synchronous execution of synchronous systems are valid (VLSI)

2

Verification and proofs of correct synchronization and logic are available in synchronous approach

3

A sequential execution scheme can be derived at compile time for any synchronous system.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures The synchronous approach to asynchronous implementations: 1

When feasible strictly synchronous execution of synchronous systems are valid (VLSI)

2

Verification and proofs of correct synchronization and logic are available in synchronous approach

3

A sequential execution scheme can be derived at compile time for any synchronous system.

4

The idealized strict synchronicity hypothesis can be relaxed to yield correct fully asynchronous executions.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Synchronous Models vs. Asynchronous Systems Actual machines for which the ideal synchronous model is valid exist. But: many machines supporting such application are actually asynchronous real-time systems are often implemented on distributed architectures The synchronous approach to asynchronous implementations: 1

When feasible strictly synchronous execution of synchronous systems are valid (VLSI)

2

Verification and proofs of correct synchronization and logic are available in synchronous approach

3

A sequential execution scheme can be derived at compile time for any synchronous system.

4

The idealized strict synchronicity hypothesis can be relaxed to yield correct fully asynchronous executions.

5

The formal verification tools based on the synchronous approach provide a way to validate asynchronous executions

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

12 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

13 / 68

Finite-State Machines states and events are a priori a rather natural medium for describing dynamic behavior of complex systems a basic fragment of such a description is state transition FSMs and their state diagrams collect such fragments into a whole

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

14 / 68

Finite-State Machines states and events are a priori a rather natural medium for describing dynamic behavior of complex systems a basic fragment of such a description is state transition FSMs and their state diagrams collect such fragments into a whole

Problem a complex system cannot be described in this naive fashion due to exponentially growing multitude of states. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

14 / 68

Rethinking State/Event Approach To be useful, a state/event approach must be: modular hierarchical well-structured should not require all state combinations to be represented explicitly should allow more general flexible statements such as 1

2

3

4

in all airborne states, when handle is pulled seat will be ejected (clustering into a superstate). gearbox change of state is independent of braking system (orthogonality ). when selection button is pressed, enter selection mode (general transitions). display-mode consists of time-display, date-display, and stopwatch display (refinement of states).

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

15 / 68

Introducing Statecharts

Statecharts constitute a visual formalism for describing state transitions in a modular fashion, enabling clustering, orthogonality (i.e., concurrency) and refinement, encouraging zoom capabilities.

In a Nutshell statecharts = state-diagrams + depth + orthogonality + broadcast-communication

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

16 / 68

State-Levels: Clustering and Refinement

clustering

Seyed Hosein Attarzadeh Niaki (KTH)

refinement

Topic 1: Synchronous Languages

November 9, 2009

17 / 68

State-Levels: Clustering and Refinement

clustering

refinement

default state

history

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

17 / 68

Contradiction and Non-determinism

Due to economical usage of arrows

Seyed Hosein Attarzadeh Niaki (KTH)

Due to the deep nature of diagrams

Topic 1: Synchronous Languages

November 9, 2009

18 / 68

Orthogonality: Independence and Concurrency

⇐⇒

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

19 / 68

Orthogonality: Independence and Concurrency

⇐⇒

An obvious application of orthogonality is in splitting a state in accordance with its physical subsystems.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

19 / 68

Delays and Timeouts

need to limit the system’s lingering in a state in general the syntax of the specification attached to a squiggle is ∆t1 < ∆t2 providing lower and upper bounds on the time in a state.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

20 / 68

Example: A Wrist Watch

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

21 / 68

Actions and Activities

statecharts represent control part of the system, which is about making time-dependent decisions influencing system behavior. missing is the ability to generate events and change the value of conditions. we reserve the word action for instantaneous happenings that take zero time. activities take non-zero amount of time.

with each activity X, we associate two special new actions start(X), stop(X), and a new condition active(X).

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

22 / 68

Example on Actions and Activities

Notice how concurrency is induced by the nested structure of states.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

23 / 68

Possible extensions

parameterized states overlapping states incorporating temporal logic recursive and probabilistic statecharts

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

24 / 68

Semantics of Statecharts providing formal semantics for statechart formalism is challenging due to introduction of depth and orthogonality. can be dealt by translation into ordinary automata.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

25 / 68

Semantics of Statecharts providing formal semantics for statechart formalism is challenging due to introduction of depth and orthogonality. can be dealt by translation into ordinary automata.

The more difficult problems arise with the introduction of events and conditions that are generated within statechart itself, and sensed in orthogonal components. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

25 / 68

Semantics of Statecharts - Non-determinism

statecharts employ a broadcast communication mechanism. cycles like this should be dealt accordingly (e.g., rendering as undefined).

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

26 / 68

Semantics of Statecharts - Non-determinism

statecharts employ a broadcast communication mechanism. cycles like this should be dealt accordingly (e.g., rendering as undefined).

the desire to allow simultaneous events can cause problems. do we end up in D if γ happens and we are in state A?

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

26 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

27 / 68

Underlying Model 1

Reactivity when activated with an input event, a reactive system reacts by producing an output event life of the system is divided into instances that are the moments it reacts

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

28 / 68

Underlying Model 1

Reactivity when activated with an input event, a reactive system reacts by producing an output event life of the system is divided into instances that are the moments it reacts

2

Atomicity of reactions the basic hypothesis of Esterel is the perfect synchronous hypothesis reactions are atomic, a reaction does not interfere with other reactions

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

28 / 68

Underlying Model 1

Reactivity when activated with an input event, a reactive system reacts by producing an output event life of the system is divided into instances that are the moments it reacts

2

Atomicity of reactions the basic hypothesis of Esterel is the perfect synchronous hypothesis reactions are atomic, a reaction does not interfere with other reactions

3

Instantaneous broadcast communication is done using broadcast mechanism communication is done over signals emission and reception of signals do not terminate the current instance

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

28 / 68

Underlying Model 1

Reactivity when activated with an input event, a reactive system reacts by producing an output event life of the system is divided into instances that are the moments it reacts

2

Atomicity of reactions the basic hypothesis of Esterel is the perfect synchronous hypothesis reactions are atomic, a reaction does not interfere with other reactions

3

Instantaneous broadcast communication is done using broadcast mechanism communication is done over signals emission and reception of signals do not terminate the current instance

4

Determinism Nondeterminism is completely thrown out of Esterel (?)

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

28 / 68

Programming Primitives The basic unit is a module which includes declarations and statements Declarations are done for types, constants, functions and procedures Statements can be primitive statements or derived statements. Primitive statements can be classical or temporal p;q Run p then q loop p end Run p; restart when it terminates p||q Start p and q together; terminate when both terminated run M Expand to code for module M emit S Make signal S present immediately present S then p else q end If signal S is present, perform p otherwise q do p watching S implements a watchdog await S Pause until S is present Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

29 / 68

Programming Style - Example 1 within a delay of one second, do an action once a button is pushed do await BUTTON; emit ACTION; watching SECOND also, an alarm must be emitted when the button is not pressed within the one second delay do await BUTTON; emit ACTION; watching SECOND timeout emit ALARM

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

30 / 68

Programming Style - Example 2

module Counter: input RST, CLICK; output VAL(Integer); var v : integer in do v := 0; every immediate CLICK do v := v+1; end watching RST; emit VAL(v); end

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

31 / 68

Programming Style - Example 2

module Counter: input RST, CLICK; output VAL(Integer); var v : integer in do v := 0; every immediate CLICK do v := v+1; end watching RST; emit VAL(v); end

Seyed Hosein Attarzadeh Niaki (KTH)

module Emission: input VAL(Integer); output NONE, SINGLE, MANY; await VAL; if ?VAL = 0 then emit NONE else if ?VAL = 1 then emit SINGLE else emit MANY end end

Topic 1: Synchronous Languages

November 9, 2009

31 / 68

Programming Style - Example 2 module Mouse: input CLICK, TOP; output NONE, SINGLE, MANY; signal RST, VAL(integer) in loop run Counter || await 5 TOP; emit RST; || run Emission end end

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

32 / 68

Problems in Esterel Instantaneous loops: their body does not allow termination of the current instance. loop x := x+1 end

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

33 / 68

Problems in Esterel Instantaneous loops: their body does not allow termination of the current instance. loop x := x+1 end Causality problems: akin to short-circuits in electronics or deadlocks in parallel programming. Lack of behavior: signal S in present S else emit S end end

Seyed Hosein Attarzadeh Niaki (KTH)

Multiple behaviors (nondeterministic): signal S1, S2 in present S1 else emit S2 end || present S2 else emit S1 end end

Topic 1: Synchronous Languages

November 9, 2009

33 / 68

Problems in Esterel Instantaneous loops: their body does not allow termination of the current instance. loop x := x+1 end Causality problems: akin to short-circuits in electronics or deadlocks in parallel programming. Lack of behavior: signal S in present S else emit S end end

Multiple behaviors (nondeterministic): signal S1, S2 in present S1 else emit S2 end || present S2 else emit S1 end end

valued signals: problems like positive feedback effect emit S(?S + 1) Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

33 / 68

Semantics of Esterel

Behavioral semantics is presented in the framework of structural operational semantics I /O1

I /O2

p1 −−−→ q1 p2 −−−→ q2 b1

Input/Output

Program −−−−−−−−→ NewProgram Terminated

b2

I /O1 ∪O2

p1 ||p2 −−−−−→ q1 ||q2 b1 andb2

only the programs without any solution (no behavior) are rejected.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

34 / 68

Semantics of Esterel

Behavioral semantics is presented in the framework of structural operational semantics I /O1

I /O2

p1 −−−→ q1 p2 −−−→ q2 b1

Input/Output

Program −−−−−−−−→ NewProgram Terminated

b2

I /O1 ∪O2

p1 ||p2 −−−−−→ q1 ||q2 b1 andb2

only the programs without any solution (no behavior) are rejected. Execution semantics rejects also nondeterministic programs provides an efficient implementation is based on a so-called potential function that syntactically forecast which signals may or may not be emitted inside the instant. used to order the processing of signals

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

34 / 68

Compiling Esterel Esterel V1, V2, V3 Esterel can easily generate finite state machines construction follows the execution semantics the execution rules provide a transition from a state, for each input event the key point is that there are finite number of such states in Esterel programs in the resulting automaton, both parallelism and local signal communication disappears it is efficient for sequential execution and predictable.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

35 / 68

Compiling Esterel Esterel V1, V2, V3 Esterel can easily generate finite state machines construction follows the execution semantics the execution rules provide a transition from a state, for each input event the key point is that there are finite number of such states in Esterel programs in the resulting automaton, both parallelism and local signal communication disappears it is efficient for sequential execution and predictable.

Esterel V4 exhaustive search of state space is impossible for many real applications newer versions are based on translating Esterel into digital logic executables simulate the netlist after topologically sorting the gates but logic networks are a poor match to imperative C and assembly code

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

35 / 68

Compiling Esterel Esterel V1, V2, V3 Esterel can easily generate finite state machines construction follows the execution semantics the execution rules provide a transition from a state, for each input event the key point is that there are finite number of such states in Esterel programs in the resulting automaton, both parallelism and local signal communication disappears it is efficient for sequential execution and predictable.

Esterel V4 exhaustive search of state space is impossible for many real applications newer versions are based on translating Esterel into digital logic executables simulate the netlist after topologically sorting the gates but logic networks are a poor match to imperative C and assembly code

Esterel V5 and newer compilers combine both methods Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

35 / 68

Verification

mainly based on techniques of validating the described automaton. when concerned about verification of a specific property, the model could be reduced in order to make it easily checkable e.g., is the elevator moving with open doors?

−→

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

36 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

37 / 68

The Data-flow approach reactive systems come from control science and electronics, where they use network of operators transforming flows of data in lower level boolean and transfer functions with block diagrams in higher level dynamical equations (i.e., differential equations) to capture the behavior

the data flow model has several advantages it is a functional model with its subsequent cleanness and it is free of side effects it is a parallel at fine-grain level. sequencing and synchronization constrains arise from data dependencies an operator net directly provides a decomposable hierarchical representation it leads very naturally to a hardware implementation

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

38 / 68

Synchronous Dataflow

a natural way to introduce time is relating flows to the rate of their arrivals X

= 2×Y +Z

−→

X (t) = 2Y (t) + Z (t)

W (t) = X (t) + 1 W = X +1 maximal reaction time of program must be measurable, which forbids dynamic creation of processes should be implemented using an extended finite automaton with bounded memory Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

39 / 68

Flows and Clocks in Lustre, any variable or expression denotes a flow composed of: a possibly infinite sequence of values of some type a clock, which represents a sequence of times

a flow takes the n-th value of its sequence at the n-th time of its clock any program has a cyclic behavior, which defines its basic clock a basic Lustre program is effectively an infinite loop

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

40 / 68

Flows and Clocks in Lustre, any variable or expression denotes a flow composed of: a possibly infinite sequence of values of some type a clock, which represents a sequence of times

a flow takes the n-th value of its sequence at the n-th time of its clock any program has a cyclic behavior, which defines its basic clock a basic Lustre program is effectively an infinite loop other slower clocks are derived from basic clock using boolean-valued flows basic time-scale C C time-scale C’ C’ time-scale

1 true 1 false

Seyed Hosein Attarzadeh Niaki (KTH)

2 false

3 true 2 true 1

4 true 3 false

Topic 1: Synchronous Languages

5 false

6 true 4 true 2

7 false

8 true 5 true

3

November 9, 2009

40 / 68

Variables, Equations, Expressions variables which do not correspond to inputs should be given only one definition in form of a equation X = E defines variable X as identical to expression X with same sequence of values and clock the substitution principle: X can be substituted to E anywhere in the program and conversely Lustre has only a few elementary data-types: boolean, integer, real, tuple. complex data-types can be imported from host language usual operators over basic types are available: and, or, div, mod, ≥, if then else, etc. functions can be imported from host language. these data operators operate only on operands sharing the same clock

As a consequence a Lustre program is written as a set of mathematical equations. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

41 / 68

Sequence Operators for any flow x, pre(x) (previous operator) is the the flow whose value at each step is the previous value of x and nil at the very first step. the − > operator (followed by operator) defines initial value. x− >y is equal to x in th first step and equal to y thereafter. when samples an expression according to a slower clock. if E is an expression and B is a boolean expression with the same clock, E when B is a flow whose clock is defined by B and is equal to sequence of values of E when B is true current interpolates an expression on the clock immediately faster than its own. B X Y=X when B Z=current Y

false x1 nil

Seyed Hosein Attarzadeh Niaki (KTH)

true x2 x2 x2

false x3 x2

true x4 x4 x4

false x5

false x6

x4

x4

Topic 1: Synchronous Languages

true x7 x7 x7

true x8 x8 x8

November 9, 2009

42 / 68

Assertions

assertions are generalized boolean equation which are assumed to be always true their primary usage is to instruct the compiler to optimize the code they can also be used in program verification examples: if we know two input events represented by variables x and y never occur at the same time: assert not(x and y);

Seyed Hosein Attarzadeh Niaki (KTH)

if event x never occurs twice at a row: assert (true -> not(x and pre(x))));

Topic 1: Synchronous Languages

November 9, 2009

43 / 68

Program Structure a Lustre system of equations can be represented graphically as a network of operators n = 0 -> pre(n) + 1;

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

44 / 68

Program Structure a Lustre system of equations can be represented graphically as a network of operators n = 0 -> pre(n) + 1; a subnetwork can be can be encapsulated as a reusable operator called node, which is basically a function of flows node COUNTER(val_init, val_incr: int; reset: bool) returns (n: int); let n = val_init -> if reset then val_init else pre(n) + val_incr; tel.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

44 / 68

Causality in Lustre Lustre forbids cyclic definitions, a variable may not instantaneously depend on itself. they can be interpreted as deadlocks.

Forbidden X = 3 * X + 1 Lustre also forbids false deadlocks

Forbidden X = if C then Y else Z; Y = if C then Z else X; the commercial scade tool forbids feeding back the output of a node to its inputs without using a pre operator Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

45 / 68

Clock Calculus

Problem in the second equations the operand combines flows of different clocks

Seyed Hosein Attarzadeh Niaki (KTH)

b = true -> not pre b; y = x + (x when b);

Topic 1: Synchronous Languages

November 9, 2009

46 / 68

Clock Calculus

Problem in the second equations the operand combines flows of different clocks

b = true -> not pre b; y = x + (x when b);

the clock calculus consists of associating a clock with each expression of the program, and of checking that any operator applies to appropriately clocked operands: primitive operators apply to operands of same clock the clock of the operand of a current operator is not the basic clock of the node it belongs to the clock of a node operands should obey the clock requirements stated in the node definition header

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

46 / 68

Lustre Compiler Lustre compiler generates pure sequential code. not possible to do from a concurrent program in a modular way

sample program

two candidates

node two_copies (a,b: int) returns (x,y: int); let x=a ; y=b end

x:=a; y:=b; or y:=b; x:=a;

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

47 / 68

Lustre Compiler Lustre compiler generates pure sequential code. not possible to do from a concurrent program in a modular way

sample program

two candidates

node two_copies (a,b: int) returns (x,y: int); let x=a ; y=b end

x:=a; y:=b; or y:=b; x:=a;

(x,y) = two copies(a,x); makes the first candidate invalid node expansion is done before code generation two approaches for the Lustre compiler single-loop code seems the natural way compile Lustre into automata is borrowed from Esterel. A set of state variables are chosen and sequential code leading to the next state is identified. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

47 / 68

Distributed Code Generation

the methods acts on intermediate automata representation OC and can be applied to other languages such as Esterel 1

the code of the automaton is replicated on each processor

2

on each replication, the instructions that do not concern that processor are deleted.

3

for any pair of processors, since we know the order of production and consumption, we add the related communication statements without introducing deadlocks. Communication is done using simple FIFOs and,

4

auxiliary “dummy” communications added for synchronization.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

48 / 68

Verification I Lustre can be considered as a subset of temporal logic. Express any temporal property as a boolean expression which is always true use assertion mechanism to express these properties in Lustre this approach is similar to model checking the abstraction graph could be used since it has a smaller size the following approach minimizes the program graph size even more

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

49 / 68

Verification II assumption dependent verification of programs

modular verification

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

50 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

51 / 68

Introducing Signal

in Signal, programming is performed via specification of constraints or relations on the involved signals the language handles sequences of data with implicit time called signals at each instance signals may be present or absent (denoted by ⊥) operators of Signal relate clocks as well as values of various signals involved in a dynamic system. hence, these languages are called multiclock languages the user is not allowed to manipulate the ⊥ symbol to to prevent him from manipulating the ambient sequence of reactions Signal is a modular programming language in the same sense as Lustre

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

52 / 68

Monochronous Signals Static monochronous operators are extensions to sequences of the classical arithmetic or logical operators (+, -, /, **, and, not, etc.) Y := U + V is coding of

Seyed Hosein Attarzadeh Niaki (KTH)

∀n > 0

yn = un + vn

Topic 1: Synchronous Languages

November 9, 2009

53 / 68

Monochronous Signals Static monochronous operators are extensions to sequences of the classical arithmetic or logical operators (+, -, /, **, and, not, etc.) Y := U + V is coding of

∀n > 0

yn = un + vn

Dynamic monochronous operator: the delay. Y := Z $1 is coding of

Seyed Hosein Attarzadeh Niaki (KTH)

∀n > 0

zn = yn−1

Topic 1: Synchronous Languages

November 9, 2009

53 / 68

Monochronous Signals Static monochronous operators are extensions to sequences of the classical arithmetic or logical operators (+, -, /, **, and, not, etc.) Y := U + V is coding of

∀n > 0

yn = un + vn

Dynamic monochronous operator: the delay. Y := Z $1 is coding of

∀n > 0

zn = yn−1

Composition of processes: the composition P1 | P2 is equal to the notion of conjunction of equations P1 and P2 in mathematics. vector signals are handled in Signal with the window operator (| VY := Y$1 window 2 | VU := U window 3 | Y := PROD {A, VY} + PROD {B, VU} |)

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

53 / 68

Polychronous Operators I The extraction: the Signal process Y := X when B is defined same as Lustre X: B: Y:

1 t 1

2 f ⊥

⊥ t ⊥

3 f ⊥

Seyed Hosein Attarzadeh Niaki (KTH)

4 t 4

⊥ f ⊥

5 ⊥ ⊥

6 f ⊥

9 t 9

... ... ...

Topic 1: Synchronous Languages

November 9, 2009

54 / 68

Polychronous Operators I The extraction: the Signal process Y := X when B is defined same as Lustre X: B: Y:

1 t 1

2 f ⊥

⊥ t ⊥

3 f ⊥

4 t 4

⊥ f ⊥

5 ⊥ ⊥

6 f ⊥

9 t 9

... ... ...

The deterministic merge: the Signal process Y := U default V defines Y by merging U and V, with priority to U when both present. U: V: Y:

1 ⊥ 1

2 ⊥ 2

⊥ 3 3

3 4 3

Seyed Hosein Attarzadeh Niaki (KTH)

4 10 4

⊥ 8 8

5 9 5

6 2 2

9 ⊥ 9

... ... ...

Topic 1: Synchronous Languages

November 9, 2009

54 / 68

Polychronous Operators II

The variation T := when B defines an event type signal which is present and true whenever B is present. Given any signal X, T := event B represents the clock of X constraints may be defined on the clocks of signals. e.g.: X ˆ= Y X and Y have the same clock X ˆ< Y X is no more frequent than Y (X ˆ= X when event Y) Y := X cell B is using a synchronized memory operator which delivers the present value of X, or the last received value if its operand is absent.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

55 / 68

The Mouse example process MOUSE = (integer DELTA) { ? event TICK, CLICK ! event SINGLE, DOUBLE } (| (| START := CLICK not in ]START, RELAX] | (| N := (#TICK in ]START, RELAX]) cell event N | ZN := N $1 % initial value 0 % | N ^= (CLICK default TICK) | RELAX := TICK when (ZN = (DELTA-1)) |) |) | (| DOUBLE_CLICK := ((not START) default (CLICK in ]START, RELAX]))cell RELAX | SINGLE := RELAX when (not DOUBLE-CLICK) | DOUBLE := RELAX when DOUBLE-CLICK |) |) where event START, RELAX;

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

56 / 68

Clock Calculus in Signal I

The goal of clock calculus in Signal is the the synthesis of constraints and, verification of their consistency (they admit a solution) verification of their completeness (only one solution) check all clocks can be defined in terms of a master clock (not necessarily the fastest)

in Signal, reactions are transition relations in general, so executing a reaction envolves solving the corresponding fixed point equation an abstraction technique is used for every statement

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

57 / 68

Clock Calculus in Signal II Z := X op Y Y := X$1 X := U when B

X := U default V P|Q

hZ = hX = hY (X,Y)→Z hX = hY hX = hU when B B→X U→X when B hX = hU ∨ hV U→X V→X when (hV − hV ) abstract(P)∪abstract(Q)

hX denotes the clock of signal X, defined by hX ≡ if X =⊥ then ⊥ else true “U→X when B” is interpreted as “X causally depends on U when X and U are present and B is true” U→X stands for U→X when true the resulting abstract domain involves Boolean and clock types plus directed graphs if he abstraction of the program has a unique, functional solution, then the original program does as well. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

58 / 68

Clock Calculus in Signal III clock calculus provides answers such as: does a program admit a behavior (no contradictions)? (| x := a when (a>0) | y := a when not(a>0) | z := x + y |)

Seyed Hosein Attarzadeh Niaki (KTH)

empty set assigned to the clocks, no execution!

Topic 1: Synchronous Languages

November 9, 2009

59 / 68

Clock Calculus in Signal III clock calculus provides answers such as: does a program admit a behavior (no contradictions)? (| x := a when (a>0) | y := a when not(a>0) | z := x + y |)

empty set assigned to the clocks, no execution!

if yes, is this behavior infinite (no deadlock)? (| x := a when (a>0) | z := x + a |)

Seyed Hosein Attarzadeh Niaki (KTH)

input a must always be positive, otherwise it is a deadlock!

Topic 1: Synchronous Languages

November 9, 2009

59 / 68

Clock Calculus in Signal III clock calculus provides answers such as: does a program admit a behavior (no contradictions)? (| x := a when (a>0) | y := a when not(a>0) | z := x + y |)

empty set assigned to the clocks, no execution!

if yes, is this behavior infinite (no deadlock)? (| x := a when (a>0) | z := x + a |)

input a must always be positive, otherwise it is a deadlock!

is the program deterministic (a function)? (| x := (x \$ 0) + 1 | y := x when c |) Seyed Hosein Attarzadeh Niaki (KTH)

leaves clocks x and c unrelated. x is a counter which is not synchronized! Topic 1: Synchronous Languages

November 9, 2009

59 / 68

Signal’s Compiler the compiler builds a hierarchy of clocks (forest) according to their interdependencies. the conditional dependency graph is connected to the forest to form a conditional hierarchical graph. the graph is rewritten using Signal syntax with clocks as boolean Signal expressions the rewritten process which is called the solved form of the program, is equivalent to the original with clock and dependency calculus solved. a simulated real-time monitor (test-bench) provides input to a program and the (program,monitor) could be solved again to produce a single tree from which sequential C code can be generated.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

60 / 68

Parallel Code Generation - Order Enhancement

P=(| y:=g(b) | x:=f(a)|) Q=(| a:=h(y) |)

Seyed Hosein Attarzadeh Niaki (KTH)

Possible Deadlock!

Topic 1: Synchronous Languages

P|Q

November 9, 2009

61 / 68

Parallel Code Generation - Order Enhancement

P=(| y:=g(b) | x:=f(a)|) Q=(| a:=h(y) |)

Possible Deadlock! P|Q

restructuring R=(| a:=h(y) | y:=g(b) |) S=(| x:=f(a) |)

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

61 / 68

More on Timing in Signal

data dependent up-sampling is a notable feature of Signal while programming in Signal, it is useful to follow the current style: specify local timing constraints involving very few different clocks and let the compiler do the rest this is different from Lustre’s style, where the programmer must have a global view of timing the language itself can be used as a partial proof system by embedding the timing constraints inside the language it usually turns out that the specification of a system is also its programming

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

62 / 68

Outline

1

The Synchronous Approach to Reactive and Real-Time Systems

2

Statecharts Formalism

3

Esterel Language

4

Lustre Language

5

Signal Language

6

Challenges

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

63 / 68

Architecture Modeling synchronous languages are excellent for functional specification of embedded systems embedded systems are frequently deployed on architectures that do not comply with the execution model of synchrony assuming the typical bus + serial communication, the bus and serial lines may not comply with the synchronous model A/D and D/A converters, by definition, lie beyond the scope of synchronous model

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

64 / 68

Beyond Synchrony I GALS architectures are considered nowadays for building hardware

Assumption the architecture obeys the model of a network of synchronous modules interconnected by point to point wires, one per signal; lossless and order preserving, but different wires are not synchronized

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

65 / 68

Beyond Synchrony I GALS architectures are considered nowadays for building hardware

Assumption the architecture obeys the model of a network of synchronous modules interconnected by point to point wires, one per signal; lossless and order preserving, but different wires are not synchronized Lustre and Signal programs can be mapped to asynchronous network of dataflow actors. for Lustre:

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

65 / 68

Beyond Synchrony II as for the Signal, additional signaling is needed since it is not possible to distinguish between no-token and late-token situation.

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

66 / 68

From Programs to Components and Systems

Building systems from components is accepted as the today-and-tomorrow solution for constructing and maintaining large complex systems. To achieve this, languages must support: genericity and inheritance (in particular behavioral inheritance) interfaces and abstractions implementations, separate compilation, and imports multifaceted notations, like UML dynamicity. Dynamic creation/deletion of instances in large systems is an important feature but dangerous for critical embedded systems

Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

67 / 68

References A. Benveniste and G. Berry. The synchronous approach to reactive and real-time systems. Proceedings of the IEEE, 79(9):1270–1282, 1991. A. Benveniste, P. Caspi, S.A. Edwards, N. Halbwachs, P. Le Guernic, and R. de Simone. The synchronous languages 12 years later. Proceedings of the IEEE, 91(1):64–83, 2003. F. Boussinot and R. de Simone. The ESTEREL language. Proceedings of the IEEE, 79(9):1293–1304, 1991. N. Halbwachs, P. Caspi, P. Raymond, and D. Pilaud. The synchronous data flow programming language LUSTRE. Proceedings of the IEEE, 79(9):1305–1320, 1991. Nicolas Halbwachs. Synchronous programming of reactive systems. In Computer Aided Verification, pages 1–16. 1998. David Harel. Statecharts: a visual formalism for complex systems. Science of Computer Programming, 8(3):231–274, June 1987. P. LeGuernic, T. Gautier, M. Le Borgne, and C. Le Maire. Programming real-time applications with SIGNAL. Proceedings of the IEEE, 79(9):1321–1336, 1991. Seyed Hosein Attarzadeh Niaki (KTH)

Topic 1: Synchronous Languages

November 9, 2009

68 / 68