An operations semantics for pure dataflow
Faustini, A. A. (1981) An operations semantics for pure dataflow. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
WRAP_Faustini_cs-rr-038.pdf - Published Version
Download (1142Kb) | Preview
We prove the equivalence between an operational and an extensional semantics for pure dataflow.
The term pure dataflow refers to dataflow nets in which the nodes are functional (i.e. the output history is a function of the input history only) and the arcs are unbounded fifo queues.
Gilles Kahn gave a method for the representation of a pure dataflow net as a set of equations; one equation for each arc in the net. We present a complete proof that the operational behaviour of a pure dataflow net is exactly described by the least fixed point solution to its associated set of equations. Our model is completely general since our nodes have the universality property, in that, for any continuous history function there exists a node that will compute it. Moreover since our nets are not built from a set of sequential primitive nodes the model is not in the communicating sequential processes framework. On the contrary our nets have the abstraction property in that any net can be collapsed into a node.
The above proof gives complementary ways of viewing pure dataflow nets, that is, as either sets of equations or as graphs. It moreover gives rise to an elegant equational dataflow language. Pure dataflow then takes on an important role since it is a correct implementation for such a functional programming language; nodes being implementation of continuous history functions; arcs and datons being implementations of histories; and nets being mechanisms for computing the solutions to sets of equations.
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software|
|Divisions:||Faculty of Science > Computer Science|
|Library of Congress Subject Headings (LCSH):||Data flow computing|
|Series Name:||Theory of Computation Report|
|Publisher:||University of Warwick. Department of Computer Science|
|Official Date:||June 1981|
|Number of Pages:||23|
|Institution:||University of Warwick|
|Theses Department:||Department of Computer Science|
|Status:||Not Peer Reviewed|
|Access rights to Published version:||Open Access|
Actions (login required)
Downloads per month over past year