Dataflow programming

Programming paradigms
Agent-oriented Automata-based Component-based Flow-based Pipelined Concatenative Concurrent computing Relativistic programming Data-driven Declarative (contrast: Imperative) Constraint Dataflow Cell-oriented (spreadsheets) Reactive Logic Abductive logic Answer set Constraint logic Functional logic Inductive logic Event-driven Service-oriented Time-driven Expression-oriented Feature-oriented Function-level (contrast: Value-level) Functional Generic Imperative (contrast: Declarative) Procedural Language-oriented Discipline-specific Domain-specific Grammar-oriented Dialecting Intentional Metaprogramming Automatic Reflective Attribute-oriented Template Policy-based Non-structured (contrast: Structured) Array Nondeterministic Parallel computing Process-oriented Programming in the large / small Semantic Structured (contrast: Non-structured) Modular (contrast: Monolithic) Object-oriented By separation of concerns: Aspect-oriented Role-oriented Subject-oriented Class-based Prototype-based Recursive Value-level (contrast: Function-level)
v · d · e

In computer programming, dataflow programming is a programming paradigm that models a program as a directed graph of the data flowing between operations, thus implementing dataflow principles and architecture. Dataflow programming languages share some features of functional languages, and were generally developed in order to bring some functional concepts to a language more suitable for numeric processing.

Properties of dataflow programming languages

Dataflow programming focuses on how things connect, unlike imperative programming, which focuses on how things happen. In imperative programming a program is modeled as a series of operations (things that "happen"), the flow of data between these operations is of secondary concern to the behavior of the operations themselves. However, dataflow programming models programs as a series of (sometimes interdependent) connections, with the operations between these connections being of secondary importance.

One of the key concepts in computer programming is the idea of "state", essentially a snapshot of the measure of various conditions in the system. Most programming languages require a considerable amount of state information in order to operate properly, information which is generally hidden from the programmer. For a real world example, consider a three-way light switch. Typically a switch turns on a light by moving it to the "on" position, but in a three-way case that may turn the light back off — the result is based on the state of the other switch, which is likely out of view.

In fact, the state is often hidden from the computer itself as well, which normally has no idea that this piece of information encodes state, while that is temporary and will soon be discarded. This is a serious problem, as the state information needs to be shared across multiple processors in parallel processing machines. Without knowing which state is important and which isn't, most languages force the programmer to add a considerable amount of extra code to indicate which data and parts of the code are important in this respect.

This code tends to be both expensive in terms of performance, as well as difficult to debug and often downright ugly; most programmers simply ignore the problem. Those that cannot must pay a heavy performance cost, which is paid even in the most common case when the program runs on one processor. Explicit parallelism is one of the main reasons for the poor performance of Enterprise Java Beans when building data-intensive, non-OLTP applications.

Dataflow languages promote the data to become the main concept behind any program. It may be considered odd that this is not always the case, as programs generally take in data, process it, and then feed it back out. This was especially true of older programs, and is well represented in the Unix operating system which pipes the data between small single-purpose tools. Programs in a dataflow language start with an input, perhaps the command line parameters, and illustrate how that data is used and modified. The data is now explicit, often illustrated physically on the screen as a line or pipe showing where the information flows.

Operations consist of "black boxes" with inputs and outputs, all of which are always explicitly defined. They run as soon as all of their inputs become valid, as opposed to when the program encounters them. Whereas a traditional program essentially consists of a series of statements saying "do this, now do this", a dataflow program is more like a series of workers on an assembly line, who will do their assigned task as soon as the materials arrive. This is why dataflow languages are inherently parallel; the operations have no hidden state to keep track of, and the operations are all "ready" at the same time.

Dataflow programs are generally represented very differently inside the computer as well. A traditional program is just what it seems, a series of instructions that run one after the other. A dataflow program might be implemented as a big hash table instead, with uniquely identified inputs as the keys, and pointers to the code as data. When any operation completes, the program scans down the list of operations until it finds the first operation where all of the inputs are currently valid, and runs it. When that operation finishes it will typically put data into one or more outputs, thereby making some other operation become valid.

For parallel operation only the list needs to be shared; the list itself is the state of the entire program. Thus the task of maintaining state is removed from the programmer and given to the language's runtime instead. On machines with a single processor core where an implementation designed for parallel operation would simply introduce overhead, this overhead can be removed completely by using a different runtime.

There are many hardware architectures oriented toward the efficient implementation of dataflow programming models. MIT's tagged token dataflow architecture was designed by Greg Papadopoulos.

Data flow has also been proposed as an abstraction for specifying the global behavior of distributed system components: in the live distributed objects programming model, distributed data flows are used to store and communicate state, and as such, they play the role analogous to variables, fields, and parameters in Java-like programming languages.

History

Dataflow languages were originally developed in order to make parallel programming easier. In Bert Sutherland's 1966 Ph.D. thesis, The On-line Graphical Specification of Computer Procedures,^[1] Sutherland created one of the first graphical dataflow programming frameworks. Subsequent dataflow languages were often developed at the large supercomputer labs. One of the most popular was SISAL, developed at Lawrence Livermore National Laboratory. SISAL looks like most statement-driven languages, but variables should be assigned once. This allows the compiler to easily identify the inputs and outputs. A number of offshoots of SISAL have been developed, including SAC, Single Assignment C, which tries to remain as close to the popular C programming language as possible.

A more radical concept is Prograph, in which programs are constructed as graphs onscreen, and variables are replaced entirely with lines linking inputs to outputs. Ironically, Prograph was originally written on the Macintosh, which remained single-processor until the introduction of the DayStar Genesis MP in 1996.

The most popular dataflow languages are more practical, the most famous being National Instruments LabVIEW. It was originally intended to make linking data between lab equipment easy for non-programmers, but has since become more general purpose. Another is VEE, optimized to use with data acquisition devices like digital voltmeters and oscilloscopes, and source devices like arbitrary waveform generators and power supplies.

Languages

• Agilent VEE
• AviSynth scripting language, for video processing
• Blitzprog concurrent data flow programming language
• BMDFM Binary Modular Dataflow Machine
• DUP dataflow-based coordination language for POSIX systems
• Hartmann pipelines
• JMax - the jMax visual programming environment for building interactive real-time music and multimedia applications
• LabVIEW / G
• LAU [French]
• Lily - Inspired by Max/MSP, but it runs in a browser. home page
• Lucid
• Lustre
• Max/Msp
• Microsoft Visual Programming Language - A component of Microsoft Robotics Studio designed for Robotics programming
• OpenWire - adds visual dataflow programming capabilities to Delphi via VCL or FireMonkey components and a graphical editor (homonymous binary protocol is unrelated)
• Oz now also distributed since 1.4.0
• Prograph
• Pure Data
• Quartz Composer - Designed by Apple; used for graphic animations and effects
• Show and Tell
• RVC-CAL
• Simulink
• SAC Single Assignment C
• SIGNAL (a dataflow-oriented synchronous language enabling multi-clock specifications)
• SISAL
• SPACE - AREVAs toolchain for the TELEPERM XS instrumentation and control system used in the nuclear industry
• Tersus - Visual progamming platform (open source)
• Verilog
• VHDL
• Vignette's VBIS language for business processes integration
• vvvv
• X10 (programming language)
• XEE (Starlight) XML Engineering Environment
• XProc

Application Programming Interfaces

• SystemC: Library for C++, mainly aimed at hardware design.
• "Pervasive DataRush": Java API for Dataflow programming
• ecto, C++ backend with graph construction/execution in python

External Links

• Handling huge loads without adding complexity The basic concepts of dataflow programming, Dr. Dobb's, Sept. 2011

See also

• Dataflow
• Actor model
• Digital signal processing
• Event-driven programming
• Flow-based programming
• Functional reactive programming
• Incremental computing
• Partitioned global address space
• Signal programming
• Stream processing
• Yahoo Pipes

References

1. ^ W.R. Sutherland (1966). The On-line Graphical Specification of Computer Procedures. MIT.