%!TEX root = ../Main.tex

\section{Related Work}
\label{s:Related}

Our work sits between the fields of array fusion and compilation of data flow languages. As mentioned in \S\ref{s:DataFlowLanguages} the Flow Fusion API from Figure~\ref{f:SeriesOperators} defines a domain specific, first order, non-recursive, synchronous, finite, data flow language for writing array programs. This language is a fragment of a more general data flow language such as Lustre~\cite{Caspi:Lustre} or Lucid Synchrone~\cite{Pouzet:lucid-synchrone}, and our rate types are similar to the clock types of Lucid, and Kahn networks~\cite{Caspi:kahn-networks}. 

The full data flow languages are intended primarily for implementing embedded control systems, writing signal processing circuits as code. In this context, support for infinite streams is essential, as the input signal must be processed indefinitely. Clock typing systems for these languages ensure \emph{causality} and \emph{syncronicity} in the presence of recursive data flows and infinite streams. Causality ensures the system has a well defined notion of time, and syncronicity ensures that it can be evaluated without needing unbounded buffers of intermediate signal data. In contrast, as we deal only with acyclic graphs our programs are automatically causal, and the finiteness of arrays eliminates the need for unbounded buffering.

The idea of representing a loop as an \emph{anatomy} of @start@, @body@, @inner@ and @end@ fields as in our @Procedure@ language of Figure~\ref{f:Procedure} appears in Shivers's work \cite{Shivers:anatomy-of-a-loop} as well as Waters's work on series expressions~\cite{Waters:series-expressions}. Shivers's work focuses on taming the vagarities of variable scoping in Common LISP loop generation macros~\cite{Steele:lisp}. He gives an eight-field loop anatomy and scoping rules for the source language in terms of this anatomy. The source code using these macro packages is more loopish in nature than our functional code using @map@, @fold@, @pack@ and so on. In the former, one writes @loop@ to introduce a new one, and then adds modifiers to specify what results should be computed. 

The work most closely related to ours is Waters's series expression framework~\cite{Waters:series-expressions}. In its essence, the paper you are reading straps a cut down clock calculus to a functionally flavoured version of Waters's compilation method, and bakes it into a GHC plugin. Waters's work does not use explicit clock or rate typing information, and his compilation method generates Pascal code with @goto@ statements and fresh labels. Full featured clock typing systems like \cite{Caspi:functional-extension-to-lustre} (1995) and \cite{Caspi:kahn-networks} (1996) did not appear until after Waters completed his line of work on series expressions \cite{Waters:series-expressions} (1991). 

In place of a rate or clock typing system, Waters's framework uses \emph{the online criteria}, which is one of four restrictions he gives that govern whether an \emph{optimizable series expression} can be fused. The others are 1) series expressions are not subjected to any conditional or looping control flow (discussed in \S\ref{s:Normalizing}); 2) the program is statically analysable (meaning compound operators are inlined or otherwise visible to the compiler (\S\ref{s:rate-inference}), and 3) series are not consumed in a random access manner (\S\ref{s:VectorsAndSeries}). 

The online criteria says that every non directed cycle in the data flow graph must consume and produce its elements in lockstep. Using rate typing we rephrase this by saying every series in the cycle must have the same rate. As we have a non-recursive @Process@ language, the only way to make a cycle in the graph would be to use an operator with multiple inputs, but the only one is @map2@ whose type requires its input and output series to have the same rate.

Finally, the fact that short cut fusion cannot deal with branching data flows stems from a deeper problem: no sequential evaluator can perform a lazy @unzip@-like operation in a space efficient way. Given @unzip x = (map fst x, map snd x)@, while computing the elements of the first component of the result, we cannot reclaim the space for the input @x@ elements because we will need those again to compute the second component of the result. Ideally, we would alternate between the two components, pulling one element from each side after the other, but lazy evaluation does not do this.

Hughes gives an informal proof of the above fact in \cite{Hughes:thesis} (1983), where a ``sequential evaluator'' is defined as one that, once the evaluator has begun to reduce an expression $E$, it will only reduce $E$ and other expressions that $E$ demands until $E$ has been completely reduced. From this fact we infer that no system based on partial evaluation of purely functional code can fuse branching data flows when the underling language has a sequential semantics (as does GHC Core). Our flow fusion system steps around this problem by splitting the functional array operators into imperative code, and then interleaving the various components. We perform the job of a concurrent scheduler at compile time.
