Stream Calculus

Stream Calculus

Parallel Array Processing

Pi calculus can be transformed from lambda calculus by replacing a variable constructor with stream constructor. But the language and protocol for accessing this stream can vary for different backends with respect to design requirements.

Stream calculus provides different disciplines for accessing underlying streams used in Pi calculus. For example: 1) linear types, or streams with constant direction without rollbacks, where each element of the stream is accessed once; 2) random access arrays; 3) GPU sources; 4) runtime typed channels; 5) effect and coeffect streams (processes as streams). Such stream calculuses could be possible in GPU languages (e.g. Futhark) and AVX intrinsics languages (e.g. Julia). We could treat stream calculus as memory representation with different access protocols.

One type of disciplines is stream calculus. While Pi calculus could be viewed as lambda calculus where function arguments are channels or streams, stream calculus defines set of constructions over these streams. This calculus is needed to provide different forms of vectorization that can be used on GPU and AVX hardware.

Language Axioms

Inductive StreamCalculus := | Map | Fold | Scan | Iota | SLoop | Transpose | Rotate | SSplit | Concat | Zip | Reduce | StreamMap | StreamMapPer | StreamRed | StreamSeq | Partition | Reshape | Shape | Rearrange | Copy | For | While.