Visualizing the Flow in a Dataflow Language

2013 Oct 30

In a previous post I introduced a synchronous dataflow language I developed and provided a couple of simple example programs. In this post I would like to return to one of the examples, show a simple visualization of the flow of data through that example program and explain how the system would run that program.

The ABCs of Syncrounous Dataflow

In order to understand how the system works, let's return to a simple example:

(imports a b)
(export c)
(def c (+ a b))

This example shows the basics of input, processing and output of the dataflow system. The system evaluates a set of signals (In this example the signals are: a, b and c). Each signal obtains a new value at each time-step. The order the signals are evaluated in is determined by the dependencies between the signals, not the order in which they are listed in the source file. The following dependency graph shows the dependencies between signals in this simple example program:

Dataflow Graph

One way to understand what is going on is to think of entering formulas into cells in a spreadsheet. These formulas reference values in other cells, and some cells are given values directly as input. Signals in the dataflow system are similar to spreadsheet cells except that their values change over time and previous values of signals can be referenced in addition to current values.

One Step at a Time

The system executes programs as follows. At each time-step the following sequence happens:

  1. New values of imported signals and random signals are obtained.
  2. All defined signals are evaluated in an order determined from the dependency between the signals.
  3. If defined, an optional exit clause is checked to see if the system needs to shutdown.
  4. Updated values for exported signals are provided.

These steps repeat until an exit clause becomes true at step 3 or the system is shut down externally.

Previous Values

As mentioned above, previous values of signals can be referenced in addition to current values. This allows a program to do things like look at the difference of a signal's value, keep a running sum of a signal's value or apply a filter to a signal's value over a window of time.

The following example shows a couple examples of referencing previous values. c-smooth is a simple moving average of the last two (previous and current) values of c. c-sum is a running sum of the value of c.

(imports a b)
(exports c c-smooth c-sum)
(def c (+ a b))
(def c-smooth (/ (+ (pre c) c) 2))
(def c-sum (+ (seq 0 (pre c-sum)) c))

Two time related operators were used in this program that require a little explanation. pre references the previous value of a signal and takes an optional additional argument that specifies the number of time-steps back to reference. seq takes a list of expressions that are used once each at sequential time-steps to determine the value of the seq expression; the final expression is used continuously once reached. This allows the initial values of a signal to be bootstrapped at startup.

The dependency graph for this program shows references to previous values indicated by dashed arrows in addition to references to current values indicated by solid arrows. It is important to note that there can be self references and cycles to previous values since they are all available, however a self reference or cycle of current values is unsolvable.

Dataflow Graph with Delays

Hopefully this article has helped shed some light on how this dataflow system works.