
The Library
An operations semantics for pure dataflow
Tools
Faustini, A. A. (1981) An operations semantics for pure dataflow. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
|
Text
WRAP_Faustini_cs-rr-038.pdf - Published Version Download (1142Kb) | Preview |
Abstract
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.
Item Type: | Report | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Divisions: | Faculty of Science, Engineering and Medicine > 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 | ||||
Dates: |
|
||||
Number: | Number 38 | ||||
Number of Pages: | 23 | ||||
DOI: | CS-RR-038 | ||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Computer Science | ||||
Status: | Not Peer Reviewed | ||||
Publication Status: | Unpublished | ||||
Access rights to Published version: | Open Access (Creative Commons) | ||||
Date of first compliant deposit: | 1 August 2016 | ||||
Date of first compliant Open Access: | 1 August 2016 |
Request changes or add full text files to a record
Repository staff actions (login required)
![]() |
View Item |
Downloads
Downloads per month over past year