Donald Bren School of Information and Computer Sciences

This report describes the meaning of various data flow operators in terms of relationships between the history of input lines and the history of output lines associated with an operator. Data flow programs are formed by interconnecting data flow operators, and by specifying the program input lines. The history of each line in a program is determined by the history of the input lines of the program. The semantics of a program are defined by a set of fixpoint equations determined by the data flow operators and their interconnections. The least fixpoint solution of such a system of equations is considered, and it is shown that all the operators and all programs under the Unraveling Interpreter are more defined than under the usual Queued Interpreter. However, if only physically meaningful (i.e. proper) inputs are considered then it is shown that both interpreters will arrive at the same least fixpoint solution. Since the Unraveling Interpreter is more defined than the Queued Interpreter, the dynamics of token generation under the Unraveling Interpreter, in general, exhibit more asynchrony than under the Queued Interpreter, even if the inputs to the program are restricted to be physically meangingful.