A Denotational Semantics for Dataflow with Firing
by Edward A. Lee
Technical Memorandum UCB/ERL M97/3
Electronics Research Laboratory, Berkeley, CA 94720
![[Postscript]](http://ptolemy.eecs.berkeley.edu/image/PS.gif)
![[PDF]](http://ptolemy.eecs.berkeley.edu/image/PDF.gif)
ABSTRACT
Formal semantics for the dataflow model of computation
have centered around the version of data
flow known as Kahn process networks. These process
networks, however, fail to capture an essential
principle of dataflow, proposed by Dennis and
used in almost all practical implementations of data
flow, that of an actor firing. An actor firing is
an indivisible quantum of computation. A set of firing
rules give preconditions for a firing, and the firing
consumes tokens from the input streams and produces
tokens on the output streams. These notions are missing
from Kahn's model, and therefore have not been thoroughly
studied in a formal setting. This paper bridges the gap,
showing that sequences of firings define a continuous Kahn
process as the least fixed point of an appropriately constructed
functional. The firing rules are sets of prefixes with certain
technical conditions to ensure determinacy.
These conditions results in firing rules that are more
general than the blocking reads of the Kahn-MacQueen implementation
of Kahn process networks, and result in a compositional dataflow model.
Send comments to Edward A. Lee at eal at eecs berkeley edu .
