Mathematical semantics and data flow programming

Abstract

A Data Flow program [1,2] is a flowchart like network of operators which compute concurrently, dependent only on the availability of the data which flow along the paths. Each operator has only a local effect, transforming input data to output data. Although operators may exhibit memory and thus not be functional from an input to an output, all operators are functions from input sequences to output sequences. This plus the strong locality of effect allows mathematization of semantics more readily than traditional programming languages which are burdened with omnipresent storage and occasional GOTO's. This paper proves the semantic behavior of some elementary Data Flow programs and proves that certain optimization tr ansformations preserve other behaviors.