Dataflow regions

Some parts of a controller have no modes at all. A siren that sounds whenever the alarm is armed and a door is open; a reading converted from one unit to another; a value that follows another one tick late. You could write each of these as a state with a self-loop, but the state adds nothing: the output is a formula over the inputs, in every tick. A dataflow region says exactly that. Instead of states and transitions it holds equations, and every equation is worked out again in every tick.

Equations instead of states

Write dataflow where you would write region, and put equations inside:

AlarmSimulation

Open in the playground

Diagram

Code

scchart Alarm {
  input bool armed, door, window
  output bool siren, ready

  dataflow {
    siren = armed && (door || window)
    ready = !door && !window
  }
}

Step

Tick 0 of 5

Inputs for tick 1

armed Boolean input: true while on. It keeps its value until you change it. door Boolean input: true while on. It keeps its value until you change it. window Boolean input: true while on. It keeps its value until you change it.

Timing diagram of Alarm

Tick	input bool armed	input bool door	input bool window	output bool siren	output bool ready

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 5 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 5 ticks:

1. armed = false, door = false, window = falseEquations run in every tick, the first one included. Everything is shut, so ready is true; the alarm is not armed, so siren is false.
2. door = trueThe door opens. ready drops to false in this same tick. siren stays false: the alarm is still not armed.
3. armed = trueArming with the door open: armed && (door || window) is true, so siren is true at once. There is no state to move to and no delay.
4. door = falseThe door shuts and both outputs follow immediately: siren false, ready true.
5. window = trueA window opens while armed: siren true, ready false, again in the tick the input changed.

Change an input and watch both outputs follow in the same tick: there are no states to move between.

Each line such as siren = armed && (door || window) is an equation: a variable on the left, any expression on the right. In every tick in which the region is active, the first tick included, KIELER evaluates every equation and assigns the result. Nothing triggers it and nothing delays it: siren is true in exactly the ticks in which the right-hand side is true.

If you know during actions, an equation behaves like immediate during do siren = armed && (door || window): it runs in every tick, the entry tick included. The dataflow form is shorter, and it reads as a description of wiring rather than as an action.

A few details:

• The braces can be left out: dataflow: followed by the equations, up to the next region or the end of the chart. (Ordinary regions have the same short form, region: followed by their states.)
• A dataflow region may start with declarations of its own (bool over, say, before the equations). They are locals of that region.
• The left-hand side must be a variable. A signal there is rejected with Non-variables cannot be used in an assignment.; use a bool output instead.
• KIELER draws a dataflow region as a circuit: inputs on the left, operators as boxes, outputs on the right, wires in between. The diagrams on this site use a simplified version of that drawing.

The order of the equations does not matter

Equations are not statements run from top to bottom. Here the first equation reads celsius, which the second one computes:

CelsiusSimulation

Open in the playground

Diagram

Code

scchart Celsius {
  input int fahrenheit
  output int celsius
  output bool freezing

  dataflow {
    freezing = celsius <= 0
    celsius = (fahrenheit - 32) * 5 / 9
  }
}

Step

Tick 0 of 4

Inputs for tick 1

fahrenheit

Timing diagram of Celsius

Tick	input int fahrenheit	output int celsius	output bool freezing

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks:

1. fahrenheit = 50freezing is written first but reads celsius, so KIELER computes celsius first: (50 − 32) * 5 / 9 = 10, and freezing is false. The order of the lines does not matter.
2. fahrenheit = 32celsius = 0, so freezing is true, both in this tick.
3. fahrenheit = 14(14 − 32) * 5 / 9 = −90 / 9 = −10: still freezing.
4. fahrenheit = 10068 * 5 / 9 = 340 / 9, and int division truncates: celsius = 37 (37.8 in real numbers).

freezing is written first but still sees this tick’s celsius.

KIELER turns every equation into a small region of its own, so the equations of a dataflow region run concurrently, like the regions of chapter 8, and the same rule decides their order: within a tick, a variable is written before anything reads it. So celsius is computed before freezing in every tick, and a chain of equations settles within one tick however you arrange the lines. (Tick 4 also shows that int arithmetic is C’s: 340 / 9 is 37, rounded towards zero.)

One equation per variable, and no instant feedback

Because equations are concurrent, the rules of chapter 12 apply to them. Two equations that both set the same variable, say open = door and open = window, are two concurrent writes that disagree, and KIELER rejects the chart. So does a set of equations that needs its own result in the same tick:

FeedbackChart

Open in the playground

Diagram

Code

scchart Feedback {
  input int I
  output int X, Y

  dataflow {
    X = Y + I
    Y = X
  }
}

KIELER rejects this chart

• Line 7, column 9X and Y depend on each other within one tick: each waits for the otherKIELER says: The SCG is NOT asc-schedulable!X is set on line 6 and read on line 7; Y is set on line 7 and read on line 6. Within a tick every write of a variable, and every emission of a signal, comes before it is read. Break the cycle with pre(X) (last tick's value), by making one side wait a tick, or by moving the logic into one region.About this message

X needs this tick’s Y, and Y needs this tick’s X: neither can go first.

Break the loop with a delay, so that one side uses the value from the previous tick (pre, more on it below). KIELER accepts this version:

FeedbackFixedSimulation

Open in the playground

Diagram

Code

scchart FeedbackFixed {
  input int I
  output int X, Y

  dataflow {
    X = pre(Y) + I
    Y = X
  }
}

Step

Tick 0 of 3

Inputs for tick 1

I

Timing diagram of FeedbackFixed

Tick	input int I	output int X	output int Y

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 3 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 3 ticks:

1. I = 1pre(Y) is 0 in the first tick, so X = 1 and Y = 1.
2. I = 1pre(Y) is last tick’s Y (1): X = 2, Y = 2. The loop is broken by the tick boundary, so it is fine.
3. I = 2X = 2 + 2 = 4, Y = 4: the chart adds up I tick after tick.

X = pre(Y) + I adds I to last tick’s Y: with I = 1, 1, 2 it gives X = 1, 2, 4.

Looking back: ->, fby and pre

Dataflow needs a way to talk about earlier ticks. Three operators provide it:

DelaysSimulation

Open in the playground

Diagram

Code

scchart Delays {
  input int level
  output int now, start, late, before

  dataflow {
    now = level
    start = 100 -> level
    late = 100 fby level
    before = pre(level)
  }
}

Step

Tick 0 of 4

Inputs for tick 1

level

Timing diagram of Delays

Tick	input int level	output int now	output int start	output int late	output int before

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks:

1. level = 5The first tick is special: start and late take their first operand, 100. pre(level) has no previous tick to look at, so before is 0, the default of int.
2. level = 6From now on -> gives its second operand as it is now: start = 6. fby gives its second operand as it was one tick ago: late = 5. before is also last tick’s level: 5.
3. level = 9now and start follow level (9); late and before are one tick behind (6).
4. level = 9level stays at 9, so after one more tick the delayed outputs catch up: everything is 9.

start and late begin at 100, before at 0. From tick 2, now and start show this tick’s level; late and before show last tick’s.

The chart’s equations are now = level, start = 100 -> level, late = 100 fby level and before = pre(level). Tick by tick:

Tick	level	now	start	late	before
1	5	5	100	100	0
2	6	6	6	5	5
3	9	9	9	6	6
4	9	9	9	9	9

• a -> b (read it “a, then b”) is a in the first tick and b in every later tick. It initialises.
• a fby b (“a, followed by b”) is a in the first tick and, in every later tick, the value b had in the previous tick. It delays by one tick and says what to show before there is a previous tick. a -> pre(b) means the same thing, and KIELER rewrites it to a fby b.
• pre(x) is the value x had at the end of the previous tick, as in chapter 11. In the first tick it is 0 (or false), whatever initial value x was declared with.

“The first tick” means the first tick of the state that contains the dataflow region. If that state is left and entered again, -> and fby start over and give their first operand once more.

With a delay in between, an equation may use its own earlier value. That is how counters and running totals are written:

// 0, 1, 2, 3, ...
ticks = 0 fby (ticks + 1)
// all coins so far
total = pre(total) + coin

KIELER also accepts an equation that reads its own variable with no delay at all, such as n = n + 1 (or n += 1). It treats it as an update of the old value, so n counts 1, 2, 3, … from tick 1. If you know Lustre or SCADE, where this would be a cycle, prefer the fby and pre forms: they say what you mean.

The precedence trap

These two equations look alike:

CountPrediction

Diagram

Code

scchart Count {
  output int wrong, right

  dataflow {
    wrong = 0 fby wrong + 1
    right = 0 fby (right + 1)
  }
}

Work out both counters after tick 3, run the chart, then open the explanation.

1. After tick 3, what is wrong?
2. After tick 3, what is right?

Run and check Plays the scenario on the diagram, then marks each answer.

Explanation

After tick 3, wrong is 3 and right is 2: wrong counts 1, 2, 3, … and right counts 0, 1, 2, … KIELER reads 0 fby wrong + 1 as (0 fby wrong) + 1, so the + 1 is added outside the delay, already in the first tick.

The difference is in how KIELER’s grammar reads the delay operators. The operands of ->, fby and sfby, and the three parts of the conditional c ? a : b, must each be an atom: a literal, a name, a call such as pre(x), or an expression in parentheses. So these operators bind more tightly than any arithmetic or comparison around them:

You write	KIELER reads
0 fby wrong + 1	(0 fby wrong) + 1
0 -> I + 100	(0 -> I) + 100: 100 in the first tick, I + 100 later
A > B ? A : B	A > (B ? A : B), which is 0 (false) whenever B is not 0

Put parentheses around every operand that is more than a single name or number: 0 fby (right + 1), 0 -> (I + 100), (A > B) ? A : B.

A delay whose type KIELER cannot work out

KIELER keeps the value of every -> and fby in a helper variable, and works out the helper’s type from the names and literals in the whole expression. If they mix bool and int, it gives up, and the generated C declares the helper with the type UNKNOWN:

MixedTypesChart

Open in the playground

Diagram

Code

scchart MixedTypes {
  input int level
  output bool high

  dataflow {
    high = false -> (level > 3)
  }
}

KIELER rejects this chart

• Line 6, column 12KIELER cannot give the -> expression a type: its values mix booleans, numbers or stringsKIELER says: Cannot serialize simulation interface. Unsupported type: UNKNOWNKIELER stores -> in a helper variable whose type comes from all the values and variables in the expression. Make them all one type, for example write level > 3 into a bool variable first and use that variable here.About this message

false is a bool, level an int: KIELER cannot type the helper of ->, and the simulation fails.

Compute the comparison into a bool variable of its own first (over = level > 3), then write high = false -> over.

Equations in sequence: ; and seq

Sometimes a value is easiest to compute in steps, each refining the last. End an equation with a semicolon, or with the keyword seq, and it runs before the equation that follows it, like a statement:

ClampSimulation

Open in the playground

Diagram

Code

scchart Clamp {
  input int raw
  output int level

  dataflow {
    level = raw;
    level = (level > 100) ? 100 : level;
    level = (level < 0) ? 0 : level
  }
}

Step

Tick 0 of 4

Inputs for tick 1

raw

Timing diagram of Clamp

Tick	input int raw	output int level

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks:

1. raw = 42The semicolons chain the three equations into one sequence, run top to bottom like statements: 42, still 42, still 42. level = 42.
2. raw = 250250, then the second line caps it at 100, then the third leaves 100 alone: level = 100.
3. raw = -7−7 passes the upper limit and the third line raises it to 0: level = 0.
4. raw = 100100 is not greater than 100, so it stays: level = 100.

The three equations form one sequence: copy the reading, cap it at 100, raise it to 0.

In a sequence a variable may be written several times and read in between. Without the semicolons the three lines would be three concurrent writes of level, and KIELER rejects that chart with the scheduling errors from above.

A semicolon is not a separator

In C a ; ends every statement. In a dataflow region it means “do this one first”. Between equations that share no variables it changes nothing, but every sequence adds a harmless warning such as

ValuedObject with name _Clamp_local_seq0 is contained in the model but not in VariableStore.

Leave the semicolons out unless you want the order.

Wiring up instances of other charts

A dataflow region can also connect copies of other charts, like chips on a circuit board. Here two half adders make a full adder, which adds three bits:

FullAdderSimulation

Open in the playground

Diagram

Code

scchart FullAdder {
  input bool a, b, carryIn
  output bool sum, carryOut
  ref HalfAdderCell h1, h2

  dataflow {
    h1 = {a, b}
    h2 = {h1.s, carryIn}
    sum = h2.s
    carryOut = h1.c || h2.c
  }
}

scchart HalfAdderCell {
  input bool x, y
  output bool s, c

  dataflow {
    s = x != y
    c = x && y
  }
}

Step

Tick 0 of 5

Inputs for tick 1

a Boolean input: true while on. It keeps its value until you change it. b Boolean input: true while on. It keeps its value until you change it. carryIn Boolean input: true while on. It keeps its value until you change it.

Timing diagram of FullAdder

Tick	input bool a	input bool b	input bool carryIn	output bool sum	output bool carryOut

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 5 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 5 ticks:

1. a = false, b = false, carryIn = false0 + 0 + 0: both half adders output false, so sum and carryOut are false.
2. a = true1 + 0 + 0 = 1: h1.s is true, h2 adds the carry 0 to it, so sum is true.
3. b = true1 + 1 + 0 = binary 10: h1.c is true, so carryOut is true and sum false. Both instances react in the tick the input changed.
4. carryIn = true1 + 1 + 1 = binary 11: sum and carryOut are both true.
5. a = false0 + 1 + 1 = binary 10: h1.s is true and h2 turns it, with the carry, into carryOut true and sum false.

h1 adds a and b, h2 adds the carry-in to h1’s sum, and either carry makes carryOut.

• ref HalfAdderCell h1, h2 declares two instances of the chart HalfAdderCell. Each runs its own copy of that chart, concurrently with everything else.
• h1.x = a sets one input of an instance. h1 = {a, b} sets its inputs in the order they are declared (x, then y); an _ in the list skips one. Inputs you never set stay at 0 or false.
• h1.s reads an output.

The chart to simulate must come first in the file, since KIELER simulates the first scchart, and the instance’s chart must be in the same file or imported (see Reusing charts). If an instance’s chart terminates, KIELER starts it again from its initial state one tick later.

Dataflow next to states

A state can contain dataflow regions and ordinary regions side by side. They are concurrent, so they communicate within the tick:

FridgeMonitorSimulation

Open in the playground

Diagram

Code

scchart FridgeMonitor {
  input int temperature
  output bool warm
  output bool alarm = false

  dataflow {
    warm = temperature > 5
  }

  region {
    initial state Normal
      if warm do alarm = true go to Alarm

    state Alarm
      if !warm do alarm = false go to Normal
  }
}

Step

Tick 0 of 4

Inputs for tick 1

temperature

Timing diagram of FridgeMonitor

Tick	input int temperature	output bool warm	output bool alarm	Active state of the chart

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 4 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 4 ticks:

1. temperature = 33 degrees: the equation makes warm false. The control-flow region enters Normal.
2. temperature = 7The equation and the region run concurrently, and the region reads warm only after the equation has written it. So warm becomes true and Normal → Alarm fires in the same tick: alarm = true.
3. temperature = 8Still warm: the chart stays in Alarm.
4. temperature = 4Back to 4 degrees: warm is false and Alarm → Normal fires in this tick, clearing alarm.

In tick 2 the equation sets warm and the region reacts to it in the same tick.

This split is often the clearest design: equations for the values that are always a formula of the inputs, states for the behaviour that has modes.

“Every tick, for ever” has a consequence: a dataflow region never finishes, so a superstate that contains one never takes its join to transition. The exception is dataflow once { ... }, whose equations run only in the tick its state is entered, after which the region terminates at once.

Three KIELER bugs to steer around

The delay operators have three bugs in KIELER. The first two give wrong results without any message, so it pays to know them.

sfby chains stop early. sfby (“sequential followed by”) with two operands behaves like ->. A chain a sfby b sfby c should give a, then b, then c, but KIELER never gets to c. With the equations two = 1 sfby level and chain = 1 sfby 2 sfby 3:

Tick	level	two	chain
1	10	1	1
2	20	20	2
3	30	30	2
4	40	40	2

Use -> instead of sfby, with two operands: in a chain a -> b -> c the middle operand is never used.

fby outside a dataflow region blocks termination. -> and fby also work in ordinary effects, such as immediate do a = 0 fby level go to End. But KIELER implements fby with a hidden helper region that never finishes, so a superstate that uses fby anywhere inside can never terminate. In this experiment two superstates are identical except for the operator:

FbyTerminationSimulation

Open in the playground

Diagram

Code

scchart FbyTermination {
  input int level
  output int a = 0, b = 0
  output bool doneA = false, doneB = false

  region WithFby {
    initial state CopyA {
      initial state Start
        immediate do a = 0 fby level go to End
      final state End
    }
    join to FinishedA

    state FinishedA {
      entry do doneA = true
    }
  }

  region WithArrow {
    initial state CopyB {
      initial state Start
        immediate do b = 0 -> level go to End
      final state End
    }
    join to FinishedB

    state FinishedB {
      entry do doneB = true
    }
  }
}

Step

Tick 0 of 2

Inputs for tick 1

level

Timing diagram of FbyTermination

Tick	input int level	output int a	output int b	output bool doneA	output bool doneB	Active state of region WithFby	Active state of the region of CopyA	Active state of region WithArrow	Active state of the region of CopyB

Click a tick to show it, or use the Left and Right arrow keys to go back and step.

Guided tour, 2 ticks Press Next to run tick 1, or Take over to set the inputs yourself.

Previous Next Take over

Guided tour, 2 ticks:

1. level = 5CopyA and CopyB both reach their final state End in tick 1. CopyB, which uses ->, terminates and its join to fires: doneB = true. CopyA, which uses fby, does not: doneA = false.
2. level = 6Nothing changes: KIELER’s helper region for fby never finishes, so CopyA’s join to can never fire.

Note: Because of this fby, CopyA never finishes: its join to never fires

• Note, line 9, column 26KIELER computes fby in a helper region of CopyA that has no final state, so CopyA cannot terminate. Use pre(...) or a variable updated on a transition instead, or leave CopyA with a normal transition.

CopyA and CopyB both reach their final state in tick 1. Only CopyB, which uses ->, terminates: doneB becomes true, doneA never does.

This site’s simulator reproduces the bug, so that it behaves like KIELER. Keep fby inside dataflow regions.

Mixed types in a delay fail, as shown above, with

Cannot serialize simulation interface. Unsupported type: UNKNOWN

Compiler messages explains it.

Try it

Did it change?

Make changed true in every tick in which level differs from its value in the previous tick, and false in the first tick, when there is no previous tick to compare with. Mind both the precedence trap and the type trap.

Open the starter in the playground

Show the starter chart

scchart Changed {
  input int level
  output bool changed

  dataflow {
    changed = false
  }
}

Show a solution

scchart Changed {
  input int level
  output bool changed
  bool differs

  dataflow {
    differs = level != pre(level)
    changed = false -> differs
  }
}

Open the solution in the playground

Running maximum

Make highest the largest level seen so far, this tick’s included. It must work for negative readings too, so it cannot start from 0. One equation is enough.

Open the starter in the playground

Show the starter chart

scchart Highest {
  input int level
  output int highest

  dataflow {
    highest = level
  }
}

Show a solution

scchart Highest {
  input int level
  output int highest

  dataflow {
    highest = level -> ((level > pre(highest)) ? level : pre(highest))
  }
}

Open the solution in the playground

Check your understanding

A chart declares input int I = 7 and the equation p = pre(I). In tick 1 the environment sets I to 5. What is p after tick 1?

A0B5C7DNothing: the chart is rejected because p has no value yet

Show the answer

Answer A: 0

In the first tick pre(I) is the default of the type, 0, whatever initial value I was declared with. From tick 2 it is the value I had at the end of the previous tick (here 5).

Which pair of equations does KIELER reject?

AX = Y + 1 and Y = pre(X)BX = I; followed by X = X * 2Cn = n + 1 on its ownDX = Y + 1 and Y = X

Show the answer

Answer D: X = Y + 1 and Y = X

X = Y + 1 and Y = X need each other’s value in the same tick: a causality cycle. With Y = pre(X) the delay breaks the cycle. The semicolon after X = I makes a sequence, so X is written twice, in order. n = n + 1 reads the value from before its own write and counts up.

Key ideas

• A dataflow region holds equations. Every equation is evaluated again in every tick the region is active, the first tick included.
• Equations run concurrently: their order does not matter, but each variable gets one equation, and equations may not need each other’s results in a loop within one tick (break it with pre or fby).
• a -> b initialises, a fby b delays by one tick with a start value, pre(x) delays and starts at 0 or false. Parenthesise their operands: they bind more tightly than arithmetic.
• An equation ending in ; or seq becomes a step of a sequence.
• ref Chart h declares an instance; set its inputs with h.x = ... or h = {...} and read h.y.
• Avoid sfby, and keep fby inside dataflow regions: KIELER gets both wrong.

Next, Time: clocks, timeouts and periods measured in real time.