Faustini, A. A. (1981) An operations semantics for pure dataflow. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)

Preview

Text WRAP_Faustini_cs-rr-038.pdf - Published Version Download (1142Kb) | Preview

Request Changes to record.

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:	Date Event June 1981 ["eprint_fieldopt_dates_date_type_available" not defined]
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