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_csrr038.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 > 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 
Date:  June 1981 
Number:  Number 38 
Number of Pages:  23 
Identification Number:  CSRR038 
Institution:  University of Warwick 
Theses Department:  Department of Computer Science 
Status:  Not Peer Reviewed 
Publication Status:  Unpublished 
Access rights to Published version:  Open Access 
URI:  http://wrap.warwick.ac.uk/id/eprint/47222 
Actions (login required)
View Item 