Group:
object-oriented programming
Topic:
automated tests of specifications and designs
Topic:
data-driven design
Topic:
data flow machines
Topic:
flow diagrams and flow charts
Topic:
graphs
Topic:
I/O streams
Topic:
message queues for communication
Topic:
processing a sequence
Topic:
Unix pipes
| |
Summary
Programs for data flow machines consist of graphs connecting function nodes. So instead of memory cells, the nodes are processors acting on data channels. These nodes can be described in an applicative form. The restriction is that each node has no side effects or state variables. Any variables are assigned only once.
Some function nodes which may be provided are: n-way input or n-way output, arithmetic calculators, conditional gates, merge switchers, presence indicators, loops and control signals for synchronization. Computation occurs when inputs and outputs are ready.
SYNCHRO programs data flow networks graphically. Hehner & Silverberg describes a node's behavior as a grammar.
Advantages--Data is emphasized instead of computation. The program is built from a few basic node types. Data flow functions are sub-graphs of the program. (cbb 5/80)
Subtopic: data flow model 
| Quote: the data flow model replaces a memory cell with a processor that transforms input messages to output messages [»wegnP_1979b]
| | Quote: a data flow language does not have side effects [»ackeWB_1979]
| | Quote: a sub-graph becomes a function by naming it; the crossed data paths become its inputs and outputs [»kosiPR9_1973, OK]
| | Quote: applicative languages are natural for data flow computation because all processing is operators applied to values [»ackeWB_1979]
| | Quote: a data-driven program is like a data-flow network with processing elements and data queues [»dennPJ_1980]
| | Quote: start StreamBit with a reference program defining the task by its bit-level dataflow; then sketch a template for an efficient implementation [»solaA6_2005]
|
Subtopic: programming as data flow
| Quote: programming traditionally uses two kinds of data flow -- expression nesting and variable assignment and reference; leads to side-effects and multi-value wrappers [»edwaJ10_2005]
|
Subtopic: write-once variables
| Quote: a node in Lustre is a function of typed input flows; defined by a system of equations and local flows; exactly one definition for each output or local flow [»benvA1_2003]
| | QuoteRef: chamDD_1971 ;;263 each variable assigned only once. when parts are defined expression is computed by a free processor
| | Quote: restarts and scheduling is easy with data flow because variable usage is unique; determines ordering [»hamiM3_1976, OK]
|
Subtopic: value flows
| Quote: treat control variables as a flow of values, one per clock tick; system of equations or dataflow network; each variable defined exactly once [»benvA1_2003]
| | Quote: flows can follow slower clocks; e.g., 'x when c' is x's values when c is true; most flow operators use the same clock [»benvA1_2003]
| | Quote: Lustre extends the usual operators to operate pointwise on flows of values
| | Quote: for any flow x, pre(x) is the previous value; a- >x is initially a then x; e.g., count of rising edges [»benvA1_2003]
| | Quote: flow operators deactivated if an operand clock is false [»benvA1_2003]
| | Quote: Lustre controls program activation by clocks
| | Quote: if activation condition is false, a flow node's value is either frozen or a default value; deactivation by clocks too restrictive [»benvA1_2003]
| | Quote: Lustre scheduling by topological sort; disallows syntactically cyclic definitions [»benvA1_2003]
| | Quote: Scade requires a pre operator for feedback values; enables separate compilation; i.e., execution order within a node is independent of the node's caller
|
Subtopic: data flow operators
| Quote: data flow control operators include n-way links, gates, and merge switchers [»dennJB_1974, OK]
| | QuoteRef: kosiPR9_1973 ;;89 DFPL no control flow, no assignment not even variables and memory as basic concepts % is mainly data movement not operations
| | QuoteRef: kosiPR9_1973 ;;94 FORK passes one input to n outputs, passes done when receives all done
| | QuoteRef: kosiPR9_1973 ;;94 GATED PRESENCE (GPR) data input sent to output, data at gate input will output true or false on sense output if data exists at data input, passes back done
| | QuoteRef: kosiPR9_1973 ;;94 LOOP (used a lot) data passed from initial path to output path, on control signal saves and returns done, on feedback input saves and returns done, on output done gives feedback if control was true else passes done to initial path
| | QuoteRef: kosiPR9_1973 ;;91 function executes when appropriate inputs have PRESENCE and outputs have DONE
| | QuoteRef: kosiPR9_1973 ;;90 in a data flow language, memory is only needed for database and to simplify the programming job
|
Subtopic: futures
| Quote: use futures for concurrent return values, event objects, and macro-dataflow programming; wait until value is assigned; assign-once [»chriTW2_2002]
|
Subtopic: dataflow processing
| Quote: SYNCRO for non-linear leveled data flow networks; pictorial representation [»demaT3_1984]
| | Quote: given a name, SYNCRO gets a process and all its ports; can connect ports as desired in data flow, command drawing [»demaT3_1984]
| | Quote: dataflow input to a port from another process, a device icon, a literal, or empty (an immediate end)
| | Quote: dataflow output to another process, a device icon, or empty (discarded data) [»demaT3_1984]
|
Subtopic: concurrent data
| Quote: concurrent data is wait-free if any process can complete in a finite number of steps; e.g., compare&swap but not test&set; reduce to consensus [»herlM1_1991]
|
Subtopic: grammar dataflows
Quote: program as an acyclic communication graph of grammars; output of one grammar is the input of another
[»hehnEC3_1983]
|
Related Topics
Group: object-oriented programming (26 topics, 822 quotes)
Topic: automated tests of specifications and designs (12 items)
Topic: data-driven design (41 items)
Topic: data flow machines (14 items)
Topic: flow diagrams and flow charts (21 items)
Topic: graphs (18 items)
Topic: I/O streams (17 items)
Topic: message queues for communication (36 items)
Topic: processing a sequence (17 items)
Topic: Unix pipes
(10 items)
|
