Browse Prior Art Database

A History of Data-Flow Languages

IP.com Disclosure Number: IPCOM000129831D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Oct-07

Publishing Venue

Software Patent Institute

Related People

PAUL G. WHITING: AUTHOR [+3]

Abstract

Data-flow refers both to a language-level paradigm of computation and to a family of processor architectures based on this paradigm. This article elaborates data-flow language issues and the evolution of data-flow languages. In considering limits to the expressive power of these languages, underlying architectural issues are of necessity discussed. Although the article attempts to present a complete history of data-flow languages, it concentrates on those languages that specifically belong to this class and have been implemented for a data-flow machine. In many cases, the distinctions between issues of language semantics and machine architecture are unclear. Usually we have found that this reflects the evolution of data-flow, and the close association between language and architecture development. In some sections of the article, it may appear that there is an imbalance in the amount of detail presented when compared with other sections. This imbalance is proportional to the publications and the amount of information readily available for the topics.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 3% of the total text.

Page 1 of 37

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

This record contains textual material that is copyright ©; 1994 by the Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Contact the IEEE Computer Society http://www.computer.org/ (714-821-8380) for copies of the complete work that was the source of this textual material and for all use beyond that as a record from the SPI Database.

A History of Data-Flow Languages

PAUL G. WHITING

ROBERT S.V. PASCOE

Data-flow refers both to a language-level paradigm of computation and to a family of processor architectures based on this paradigm. This article elaborates data-flow language issues and the evolution of data-flow languages. In considering limits to the expressive power of these languages, underlying architectural issues are of necessity discussed. Although the article attempts to present a complete history of data-flow languages, it concentrates on those languages that specifically belong to this class and have been implemented for a data-flow machine. In many cases, the distinctions between issues of language semantics and machine architecture are unclear. Usually we have found that this reflects the evolution of data-flow, and the close association between language and architecture development. In some sections of the article, it may appear that there is an imbalance in the amount of detail presented when compared with other sections. This imbalance is proportional to the publications and the amount of information readily available for the topics.

Data-flow languages derive from a base paradigm of the data-flow graph -- that is, the modeling of a program as a set of operator nodes interconnected by a set of data-carrying arcs. Under this paradigm there is no current operation, and each operator is free to execute when its data arrives. The interpretation of the language is naturally concurrent, and the concurrency is inherently fine-grained.

The data-flow model has the single-assignment property. Values are data tokens that are transported from their producing node to the node that consumes them; there is no concept of a variable with a state that can be arbitrarily updated at a later time. In data-flow, identifiers may be used to name these data tokens. Such identifiers are thus either undefined (not yet produced) or carry a single unique value; they cannot be updated.

For a counterpoint to data-flow, languages belonging to the class referred to as functional languages model programs as nested mathematical functions. In pure functional languages, identifiers denote subexpressions, and given that a sub-expression has a single unique value (which cannot be updated), these languages likewise share the single assignment property.

In examining the development of data-flow languages, a strong mutual influence between data- flow and functional languages appears. This is probably due to their contemporary development, the sharing of certain fundamen...