\documentstyle[preprint,twoside,lcscover]{acm}

\include{texgrime}

\newcommand{\foldl}{{\tt foldl}}
\newcommand{\foldr}{{\tt foldr}}
\newcommand{\map}{{\tt map}}
\newcommand{\reduce}{{\tt reduce}}
\newcommand{\unfold}{{\tt unfold}}
\newcommand{\synthesize}{{\tt synthesize}}
\newcommand{\concat}{{\tt concat}}
\newcommand{\singlespacing}{}
\newcommand{\op}{$\oplus$}
\newcommand{\LEL}{$\cal L\!E$\ldb}
\newcommand{\LFL}{$\cal L\!F$\ldb}
\newcommand{\LEE}{$\cal L\!E$}
\newcommand{\LFF}{$\cal L\!F$}
\newcommand{\LE}[1]{$\cal L\!E$\ldb {#1}\rdb}
\newcommand{\LF}[1]{$\cal L\!F$\ldb {#1}\rdb}

\hyphenation{com-pre-hen-sion com-pre-hen-sions}

\begin{document}

\covertitle{Simplifying Parallel List Traversal}
\title{Simplifying Parallel List Traversal}

\coverauthor{Jan-Willem Maessen}
\coverdate{January 18, 1995}
\researchcredit{This research was supported in part by an NSF Graduate
Fellowship.  Funding for the Laboratory for Computer Science is
provided in part by the Advanced Research Projects Agency of the
Department of Defense under the Office of Naval Research contract
N00014-92-J-1310.}
\toappear{Submitted to FPCA '95}
\trnumber{Computation Structures Group Memo 370}

\author{Jan-Willem Maessen\thanks{Computations Structures Group, MIT
Laboratory for Computer Science (email: {\tt jmaessen@mit.edu}).  This
research was supported in part by an NSF Graduate Fellowship.  Funding
for the Laboratory for Computer Science is provided in part by the
Advanced Research Projects Agency of the Department of Defense under
the Office of Naval Research contract N00014-92-J-1310.}}

\bibliographystyle{plain}

\maketitle

\toappear{Submitted to FPCA '95}

\begin{abstract}

Computations described using Bird's constructive algebra of lists are
nicely amenable to parallel implementation.  Indeed, by using
higher-order functions, ordered list traversals such as \foldl\ and
\foldr\ can be expressed as unordered reductions.  Based on this
observation, a set of optimizations have been developed for list
traversals in the parallel Haskell (pH) compiler\cite{bib:phreport}.
These optimizations are inspired by, and partially subsume, earlier
work on the optimization of sequential list traversal.

\end{abstract}

\section{Introduction}

Lists are a basic computational ``glue'' in many functional languages.
They are easily expressed and understood by programmers, and offer a
compact notation for representing collections of data.  The functional
language {\em Haskell} \cite{bib:hreport} is no exception to this
rule, and in fact encourages or even requires the use of lists to
express certain sorts of computation.

Functional languages also encourage a compositional coding style.
This causes lists to be used extensively as intermediate data
structures.  For example (all code is in Haskell\cite{bib:hreport}):
\begin{center}  \tt
\begin{tabular}{l@{\ =\ }l}
any p   & or .~map p\\
or      & reduce (||) False
\end{tabular}
\end{center}
Here the function {\tt any} takes a list, maps {\tt p} across it to
produce a list of booleans, and then consumes that list by calling
the function {\tt or}.  

A simple set of transformations are needed which will combine the
generation, traversal, and consumption of a list.  One simple and
compact transformation which does the job is {\tt foldr/build}
optimization\cite{bib:shortcut}.  However, the transformation centers
around the \foldr\ function, which forces results to be combined in a
particular order.  In {\em parallel} Haskell,
this is a serious problem.  In particular, it rules out some important
optimizations of the following sort:
\begin{center}  \tt
\begin{tabular}{l@{\ $=$\ }l}
sum (a ++ b) & sum a + sum b
\end{tabular}
\end{center}
In a parallel language, the above rewriting will permit the
expressions {\tt sum a} and {\tt sum b} to be computed in parallel. 

This paper presents two closely related results.  First, a set of
local transformations are given which will eliminate intermediate
lists.  These transformations capture ordering constraints on list
traversals by using higher order functions, and do not commit to any
particular ordering if none is specified.  Second, a set of heuristics
are given for transforming the optimized computations into loops.
These heuristics are designed to detect and exploit ordering
constraints captured by the optimized list traversals.  In order to do
so, a method for generating lists systematically is introduced into
the language.

The optimizations have a number of useful features:
\begin{itemize}
\item They embody well-known techniques and theorems from the field of
constructive programming.
\item They can be used to describe computations on arbitrary data
types which are homomorphic to lists or bags.
\item Many of the standard list processing functions can be described
and optimised within this framework.  In particular, list
comprehensions are open to optimization if they are desugared using
the naive scheme shown in
Figure~\ref{fig:mapdesugar}\cite{bib:implcomp}.
\end{itemize}

\begin{figure*}[tb] \centering
\input{simple-desugar}
\label{fig:mapdesugar}
\caption{Desugaring rules for lists using \map\ and \concat }
\end{figure*}

\section{The Bird-Meertens Formalism---highlights}

The goal of the Bird-Meertens formalism is to provide an algebra with
which efficient algorithms can be derived from simple
specifications\cite{bib:algorithmics}.  The goals of such an endeavor are
quite broad---roughly speaking, they involve proving complex theorems
about this new algebra.  The goal of this compiler optimization is
much more modest---to consistently improve performance using a set of
simple constructive transformations.

\subsection{Traversal}

In functional languages, there are two commonly-used functions which
traverse lists---\foldl\ and \foldr .  They
have the following mathematical definitions:
\begin{eqnarray*}
\verb|foldr|\:\oplus z\:\verb|[| x_{1},x_{2},\ldots,x_{n} \verb|]|
   &=& x_{1}\oplus(x_{2}\oplus(\cdots(x_{n}\oplus z)))\\
\verb|foldl|\:\oplus z\:\verb|[| x_{1},x_{2},\ldots,x_{n} \verb|]|
   &=& (((z \oplus x_{1})\oplus x_{2})\oplus \cdots)\oplus x_{n}
\end{eqnarray*}
The parenthesization in the above definitions shows that \foldr\
traverses a list ``right to left'', while \foldl\ traverses the list
``left to right.''  These functions correspond respectively to
recursive or iterative list traversals.

The problem with these functions is their inherent ``handedness''.
The fold operations impose a particular ordering on the flow of data
in the computations they represent.  Folded computations must wait for
data to reach them along the ``spine'' of the list.  This problem is
most evident when the input can be broken up into pieces, say {\tt a}
and {\tt b}:
\begin{center}  \tt
\begin{tabular}{l@{\ =\ }l}
foldr f z (a ++ b)     &     foldr f (foldr f z b) a \\
foldl f z (a ++ b)     &     foldl f (foldl f z a) b
\end{tabular}
\end{center}
This ordering, while sometimes necessary, is often superfluous.  For
example, if we define the {\tt sum} of a list using \foldl\ or \foldr
, we will be unable to show that{\tt\ sum (a ++ b) }is equivalent
to{\tt\ sum a + sum b}.

What is needed is an operation which describes the traversal of lists
symmetrically.  Bird calls this operation reduction
\cite{bib:theory,bib:constructive}.  It has the following definition:
\begin{center} 
\begin{tabular}{l@{\ $=$\ }l}
  {\tt reduce (\op ) $z$ [$x_{1},x_{2},\ldots,x_{n}$]} & 
$x_{1}\oplus x_{2}\oplus \cdots x_{n}$\\
  {\tt reduce (\op ) $z$ []} & $z$
\end{tabular}
\end{center}
The obvious difference between this definition and the definitions of
\foldl\ or \foldr\ is the absence of parentheses, and the fact that
$z$ is used explicitly only to define the value of reduction on the
empty list.  For \reduce\ to be safe, \op\ and $z$ must satisfy the
following identities (for any value of $a$, $b$, or $c$ of the
appropriate type):
\begin{center}
\begin{tabular}{cl}
$a \oplus (b \oplus c) \equiv (a \oplus b) \oplus c$ & \op\ associative\\
$a \oplus z \equiv z \oplus a \equiv a$ & $z$ identity of \op
\end{tabular}
\end{center}
The above conditions mean that \op\ satisfies the requirements for the
binary operation of a monoid with an identity.  The conditions also
lead to a more rigorous definition of \reduce :
\begin{center}  \tt
\begin{tabular}{lcl}
reduce (\op ) z (a ++ b) & $=$ & reduce (\op ) z a \op\ \\
                         &&    reduce (\op ) z b\\
reduce (\op ) z [e]      & $=$ & e\\
reduce (\op ) z []       & $=$ & z
\end{tabular}
\end{center}
This definition uses the constructive view of lists: Every list is
either empty ({\tt []}), contains a single element {\tt e} ({\tt
[e]}), or can be built by appending two lists, {\tt a} and {\tt b}
({\tt (a ++ b)}).  

The advantage of \reduce\ is that it avoids overspecification.
In particular, if we are attempting to develop a parallel program, we
would like to write algorithms in such a way that there are no
spurious dependencies forcing our algorithm to be sequential.  We
write:
\begin{quote} \centering  \tt
sum = reduce (+) 0
\end{quote}
and quickly discover from the definition of \reduce\ that:
\begin{center}  \tt
\begin{tabular}{l@{\ $=$\ }l}
sum (a ++ b) & reduce (+) 0 (a ++ b) \\
             & reduce (+) 0 a + reduce (+) 0 b\\
             & sum a + sum b
\end{tabular}
\end{center}
For this reason, constructive approaches have been viewed by some as
the natural successor to data-parallel pro\-gram\-ming\cite{bib:parcon}.

\subsection{Homomorphisms and Monoids}

Unfortunately, using only \reduce\ it is impossible to express the
following idea:
\begin{center}  \tt
\begin{tabular}{l@{\ $=$\ }l}
length (a ++ b)     &     (length a) + (length b)
\end{tabular}
\end{center}
The problem is obvious when the types of the functions are examined:
\begin{quote} \centering 
\begin{verbatim}
reduce :: (a -> a -> a) -> a -> [a] -> a
length :: [a] -> Int
\end{verbatim}
\end{quote}
There needs to be some way of transforming individual elements of the
list into objects of the correct type, which can then be combined
using \reduce .  The operation which accomplishes this is
\map :
\begin{center}  \tt 
\begin{tabular}{l@{\ =\ }l}
map f (a ++ b)  & map f a ++ map f b\\
map f [e]       & [f e]\\
map f []        & []\\
\end{tabular}
\end{center}
Thus {\tt length} can be expressed in terms of \map\ and \reduce\ as
follows (here {\tt const} is the constant combinator which returns the
first of its two arguments):
\begin{center}  \tt
\begin{tabular}{l@{\ =\ }l}
length (a ++ b)     &      sum .~map (const 1)
\end{tabular}
\end{center}
This simply separates the definition of {\tt length} into two
pieces---a piece which replaces each list element by 1 (a map) and a
sum (reduction) of the resulting list.

Bird \cite{bib:constructive} notes that \map\ and \reduce\ can be used
in this way to express the homomorphism from the monoid of lists over
$\alpha$, {\tt $($[$\alpha$]$, $++$, $[]$, $(:[])$)$}, to an arbitrary
monoid $(\beta, \oplus, id_{\oplus}, i)$:
\begin{displaymath}
h\;xs = \verb|reduce| \oplus\;id_{\oplus}\:(\verb|map | i\;l)
\end{displaymath}
In effect, every append operation {\tt (++)} is replaced by \op, every
empty list {\tt []} by $id_{\oplus}$, and every unit operation {\tt
(:[])} by $i$.

This unconditional replacement gives rise to the {\em promotion rules}
for lists described by Bird \cite{bib:constructive}.  These rules push
calls to \map\ and \reduce\ inwards through \concat :
\begin{center}
\begin{tt}
\begin{tabular}{l@{\ $=$\ }l}
map g (concat $L$)              & concat (map (map g) $L$)\\
reduce \op\ z (concat $L$)      & reduce \op\ z \\
\multicolumn{1}{c}{}            & (map (reduce \op\ z) $L$)
\end{tabular}
\end{tt}
\end{center}

\subsection{Higher-order Homomorphism}

Having defined homomorphism in terms of \map\ and \reduce , the
typical approach (when using constructive techniques to derive an
algorithm) is to immediately translate reductions into folds using
either of the following (perfectly legal) definitions:
\begin{center}  \tt
\begin{tabular}{l@{\ =\ }l}
reduce f z     &        foldl f z \\
reduce f z     &        foldr f z
\end{tabular}
\end{center}
This defeats the purpose of introducing \reduce\ into a parallel
language, however.  Instead, it would be desirable if all three
methods of list traversal could be fit into a single framework based
on reduction.

The trick is to use higher-order functions to separate the behavior of
\foldl\ and \foldr\ into pieces.  There are three basic steps:
\begin{itemize}
\item Package up the computation which will be performed on a given
list element when data arrives along the spine of the traversal.  This
will transform each element of the list into a function.
\item Use a higher-order function to ``wire together'' the
functions along the spine.
\item Call the resulting function with the initial value of the traversal.
\end{itemize}
The first two steps correspond to mapping and reduction respectively.
The third step actually performs the computation which has
conceptually been set up by the first two steps.  The resulting
definitions of \foldl\ and \foldr\ look like this (the operator {\tt
(.)} is function composition, and {\tt flip} reverses the order of the
first two arguments of the given function):
\begin{quote} \centering 
\begin{verbatim}
foldr f i xs = reduce (.) id
                      (map f xs) 
                      i
foldl g j xs = reduce (flip (.)) id
                      (map (flip g) xs) 
                      j
\end{verbatim}
\end{quote}
It should come as no surprise that {\tt id} (the identity function) is
the identity of both monoids.  It is, of course, the identity of
function composition, but more fundamentally we expect it to represent
the idea that ``if there is no list element, no computation should be
performed.''

The structure of the above definitions for \foldl\ and \foldr\
suggests that a similar formulation for reduction might exist.  And
indeed it does:
\begin{center}\tt
\begin{tabbing}
reduce \op\ z xs  $=$ reduce \= (\verb-\-l r t -> (l z) \op\ (r z)) \+\\
                        id\\
                        (map const xs)\\
                        z
\end{tabbing}
\end{center}
This definition scatters the value of z across the reduction, where it
is generally simply dropped.  Only when an empty list is encountered
is this extra argument actually put to use.  Care must be taken,
however, since this means that the higher-order function now being
reduced is only correct when its third argument, {\tt t}, is {\tt z}.

The optimizations will therefore assume that all list consumption has
the following canonical form:
\begin{quote} \centering  \tt
(reduce $a$ id (map $u$ l)) $t$
\end{quote}
Here $a$ is a function of at least three arguments, $u$ a function of
at least two, and $t$ represents either the initial value of a fold or
the identity of a reduction.  For example, for {\tt foldr~f~z} {\tt
$a=$(.)}, {\tt $u=$f}, and {\tt $t=$z}.
This allows the optimizer to represent list traversal uniformly and
compactly.  

\subsection{Ordering Rules and Bags}

The \map\ operation is unaffected by the ordering of its input.
However, a reduction does carry some weak ordering information.  This
is because the operation passed to \reduce\ may not be commutative.
The most obvious example so far is \concat .  If we write {\tt concat
[[1,2],[3],[4,5]]}, we cannot tell which two lists are appended
together first; however, we do know that our answer will be {\tt
[1,2,3,4,5]} and not, say, {\tt [3,1,2,4,5]} or {\tt [4,5,3,1,2]}.
The order independence of \map\ and the order dependence of \reduce\
are used to derive the following rules:
\begin{center}
\begin{tt}
\begin{tabular}{l@{\ $=$\ }l}
map f (reverse $L$)             &       reverse (map f $L$)\\
reduce \op\ z (reverse $L$)     &       reduce (flip \op ) z $L$
\end{tabular}
\end{tt}
\end{center}

Often, an operation being reduced {\em is} commutative---or we as
programmers may be using lists as bags, meaning that we specifically
don't care about the ordering of elements.  For these instances, there
is an order-independent function called {\tt someOrder}.  This
function returns a permutation of the list provided to it.  In
general, it could be defined as the identity function.  When {\tt
someOrder} is encountered by the optimizer, assumptions about ordering
constraints on a canonical traversal are dropped; the optimizer then
tries to choose the best possible traversal direction for each sublist
of the list being traversed.  For example, assume the list {\tt
[1..5]} can be computed most efficiently forwards.  The optimizations
will reorder the list {\tt ([1..5]~++~reverse~[1..5])} if it is passed
to {\tt someOrder}.  Thus, a computation which would ordinary yield
the list {\tt [1,2,3,4,5,5,4,3,2,1]} after optimization will instead
yield the list {\tt [1,2,3,4,5,1,2,3,4,5]}.

\subsection{Generating Lists}

To entirely {eliminate} lists, and not simply optimize their
traversal, the generation of lists must be described as systematically
as the consumption.  List comprehensions are a partial solution, since
they describe the generation of new lists in terms of traversals over
existing lists.  Nevertheless, there are many cases where lists are
generated without reference to other lists---for example, Haskell
contains special syntax for arithmetic series expressed as lists: {\tt
[$k_{1}$,$k_{2}$..$k_{n}$]}.  In addition, because lists are a
full-fledged data structure in the language a partially-constructed
list (an ``accumulative result variable''\cite{bib:seasons}) can be
traversed by the computations which is constructing the list.  Doing
so will preclude eliminating the list, since it must be built once so
that the repeated traversals will behave as they were written.

\begin{figure*}[tb] \centering
\input{opt-rules}
\caption{\map /\reduce\ optimization rules}
\label{fig:optrules}
\end{figure*}

Instead, functions can be defined which generate lists systematically.
The list anamorphism \cite{bib:banana} generates lists one element at
a time, using a predicate to terminate generation, so that finite
lists can be created systematically.  This list anamorphism is visible
to the programmer as the \unfold\ function, which is defined as
follows:
\begin{quote} \centering 
\begin{verbatim}
unfold p f v = h v
         where h v | p v       = []
                   | otherwise = a:h b
                        where (a,b) = f v
\end{verbatim}
\end{quote}
The chief virtue of this function is that its structure is regular
enough to permit the use of heuristics which will generate different
code depending on how the resulting list is consumed.

\section{\map /\reduce\ optimization}

Having seen that traversals can be converted to canonical form, and
that maps and reductions can eliminate the intermediate lists in \map\
and \concat , it simply remains to combine everything to obtain a
simple set of optimizations.  The optimization rules, given in
Figure~\ref{fig:optrules}, are referred to as the \map /\reduce\
rules, since the last three arguments to \LFF\ represent
a canonical reduction being performed using \map\ and \reduce\ on the
expression in the double brackets.  The {\tt bothways}
operation represents a marker function which is applied to the value
of $a$ to express the fact that $a$ is free of ordering constraints.
This fact is exploited in rules which generate code to actually
perform the reduction (described in the next section).

This structure also permits the elimination of compile-time redexes
which would have been present if optimization simply used the
promotion rules directly.  In particular, all calls to $a$ are
performed at compile time---a safe bet, since $a$ has a regular
structure.  There is one danger in this: it is possible to
duplicate $t$.  Note, however, that this can only happen when $a$ is
created by a reduction---and $t$ is given a concrete name in this case.

In addition, the rules are carefully structured so that they deal
gracefully with nesting---that is, inner subexpressions are not
optimized until reductions have been eliminated in the enclosing
expression.  This permits \map /\reduce\ optimization to be performed
in one pass; however, functional arguments (all labeled $f$ in their
respective desugaring rules) may be re-optimized repeatedly if they
are applied repeatedly.  Right now a fairly simple heuristic is used
to control this behavior: if the function is bound to a name and then
used in a traversal it will be optimized once, separately, but will
not benefit from further \map /\reduce\ optimization if it happens to
return a nested list.  If the function is specified explicitly using a
lambda, on the other hand, it will be duplicated (and inlined) {\em ad
nauseam}.

Note that the rules for optimization only explicitly specify
re-traversal in three cases---for the three list consumers \foldl ,
\foldr\ and \reduce .  In the remaining cases, list syntax is actually
going to be generated.  This syntax would then be re-optimized unless
a second set of names is introduced for already-optimized list
operations.  However, it is possible to avoid re-traversing these
operations entirely by carefully traversing inner code as the result
is produced.  This leads to the following definition for $a_{list}$,
$u_{list}$ and $t_{list}$:
\begin{center}  \tt
\begin{tabular}{l@{\ $=$\ }l}
$a_{list}$      &       (.)\\
$u_{list}$      &       $(\lambda e t.\:$\LE{$e$}:$t)$\\
$t_{list}$      &       []
\end{tabular}
\end{center}
No formal termination proof for this optimization structure has yet
been undertaken; informally, \LEE\ always either encounters no list
and proceeds deeper, encounters a list which must actually be
constructed and proceeds deeper on each element of that list, or
encounters a list traversal and eliminates it, re-traversing with one
less level of list nesting (since Haskell is strongly typed and types
are finite, we will not cut our own throat in this instance).

\section{Code for Generation}


\begin{figure*}[tb] \centering
\begin{tabular}{c}
\hline\\
\begin{minipage}{5in}
\input{gen-rules}
\end{minipage}\\
\hline
\end{tabular}
\caption{Rules for efficiently traversing an existing list or {\tt unfold}}
\label{fig:genrules}
\end{figure*}

The extensive use of higher-order functions in canonicalized list
traversals immediately begs the question of efficiency.  Fortunately,
the reductions performed by the above rules alleviate most of these
concerns.  Reasonable code can thus be generated with the
following rules:
\begin{center}
\begin{tt}
\begin{tabbing}
mmmm\= \kill
\LF{\unfold\ $P$ $F$ $V$} \aut\ $=$\+\\
let h v acc \= | \LE{$P$} = acc\+\\
               | ot\= herwise = $(a$ $(u\:$e$)$ $($h v'$))$ acc\+\\
                        where (e,v') = \LE{$F$} v \- \- \\
in~~h \LE{$V$} $t$\-\\
{\rm Otherwise}\\
 \LF{$E$} \aut\ $=$\+\\
let \=  h []~~~~~acc = acc\+\\
        h (e:es) acc = $(a$ $(u\:$e$)$ $($h es$))$ acc\-\\
in~~h \LE{$E$} $t$
\end{tabbing}
\end{tt}
\end{center}
These definitions were obtained by recognizing that list traversal
must, as always, take place sequentially along the spine of the
provided list, and that \unfold\ similarly must wait for data to be
propagated from one iteration to the next.  The following sequential
traversal is then used:
\begin{quote} \centering\tt
(\verb-\-lst -> foldr ($a$.$u$) id lst $t$)
\end{quote}
By expanding the definition of \foldr\ above, the following code is
obtained for the lambda body:
\begin{quote} \centering \tt
\begin{tabbing}
let \=  h []~~~~~= id\+\\
        h (e:es) = $(a$ $(u\:$e$)$ $($h es$))$\-\\
in~~h lst $t$
\end{tabbing}
\end{quote}
The important observation which leads us to the code at the beginning
of the section is that both disjuncts in the definition of {\tt h}
will return a function.  In fact, because $a$ has a fixed definition,
it is open to $\eta$-abstraction---that is, no computation beyond
pattern matching will be necessary at run time to obtain the function
which is returned by {\tt h}.  This $\eta$-abstraction step yields the
expansion given at the beginning of the section.  The translation for
\unfold\ follows by observing the structural similarity of traversal
to generation, or analogously by observing that a catamorphism (\foldr
) can be combined with an anamorphism (\unfold )\cite{bib:banana}.

\subsection{Exploiting the regular structure of $a$}

The fact that the structure of $a$ is known permits a number of
important heuristics to be derived which will produce better code than
the naive translation given above.  Note that the structure of the
traversal function {\tt h} is mostly fixed in the expansion at the
beginning of the previous section; the only parts which vary are the
value of $t$ (which is outside {\tt h} itself) and the value of the
second clause of {\tt h}'s definition.  There are two basic forms
which this second clause can take (where $f$ and $g$ are arbitrary
functions):
\begin{center} \tt
\begin{tabular}{ll}
$f$ (h xs acc)  &       {\em proper recursive}\\
h xs ($g$ acc)  &       {\em iterative}
\end{tabular}
\end{center}
If there is a choice in the matter, the decision must be based on the
strictness of expression $g$.  If $g$ is strict, then the iterative
form should be chosen; this will permit the generation of a loop which
executes in unit space in the final code for {\tt h}.  If $g$ is not
strict, however, the proper recursive form should be used.  In this
way, {\tt h} as a whole can return a value before the recursive call
has terminated, and in a lazy language can avoid the recursive call
entirely.  The rules given in Figure~\ref{fig:genrules} will generate
the iterative form whenever possible.  These are (modulo some tweaking
to eliminate useless arguments) the rules which are actually used in
the pH compiler.

Note that the optimization rule for \concat\ given earlier
(Figure~\ref{fig:optrules}) specifies that the arguments to $u$ are
used to perform a recursive optimization.  Given this fact, how can
the strictness properties of such a function be determined?  Note that
the second argument to $u$ will in this case be passed straight to the
recursive optimization as the $t$ parameter of that optimization.  The
$t$ parameter to the optimization is never itself optimized (unless
the code is later re-optimized from the ground up by \LEE ).  As
a result, the recursive optimization can be performed with some dummy
second parameter {\tt d}.  We can then evaluate the strictness of the
resulting (concrete!) code with respect to {\tt d}.  Any further call
to $v$ in $\cal L\!D$ can then simply bind its argument to {\tt d} and
incorporate the already-generated code.

Note also that lists which already exist on the heap are not
explicitly re-created on the heap, but are instead passed to the
standard append operation {\tt (++)}.  When {\tt $t=$[]}, this
rewriting can be optimized to just \LE{$E$}, meaning that $E$ is not
copied.  In particular, this optimization means that the expression
{\tt a~++~b} optimizes to {\tt a~++~b} rather than {\tt a~++~(b~++~[])}.  


\section{Example}

%First, consider the function
%{\tt unlines}, which can be defined as follows in Haskell (this
%function occurs as an example in previous work\cite{bib:shortcut}):
%\begin{quote} \centering
%\begin{verbatim}
%unlines ls = concat (map (\l -> l ++ ['\n']) ls)
%\end{verbatim}
%\end{quote}
%Optimization begins when the unconsumed \concat\ is encountered.
%Applying the rule for \concat\ yields the following: 
%\begin{quote} \centering  \tt
%\begin{tabbing}
%unlines ls = \LFL\= (map \verb|(\l -> l ++ ['\n'])| ls\rdb\ \+\\
%        $a_{list}$
%        $(\lambda e.\:$\LF{$e$} $a_{list}$ $u_{list})$
%        $t_{list}$
%\end{tabbing}
%\end{quote}
%Applying the \map\ rule and simplifying the composition of the mapped
%functions yields the following:
%\begin{quote} \centering  \tt
%\begin{tabbing}
%unlines ls = \LFL\= ls\rdb $a_{list}$\+\\
%        $(\lambda e'.\:$\LFL e' \verb|++ ['\n']|\rdb\ $a_{list}$ $u_{list})$ \\
%        $t_{list}$
%\end{tabbing}
%\end{quote}
%Note the as-yet unoptimized body of the expression being mapped has
%found its way to a position where it will actually be optimized (since
%$u_{list}$ desugars its argument).
%
%At this point optimization has reached the unknown list {\tt ls}.  As
%a result, a traversal must be generated.  Remembering that $a_{list}$
%is {\tt (.)}, this will not require recourse to strictness.  The
%following code results:
%\begin{quote} \centering  \tt
%\begin{tabbing}
%un\= lines ls = h ls []\+\\
%  where \= h []~~~~~acc = acc\+\\
%           h (x:xs) acc = \LFL\=\verb|x ++ ['\n']|\rdb\+\\
%                                $a_{list}$ $u_{list}$ (h xs acc)
%\end{tabbing}
%\end{quote}
%The recursive optimization can now be performed.  Remembering that
%$a_{list}$ is simple composition, this yields the following code:
%\begin{quote} \centering  \tt
%\begin{tabbing}
%un\= lines ls = h ls []\+\\
%  where \= h []~~~~~acc = acc\+\\
%           h (x:xs) acc = \LFL\= x\rdb\ $a_{list}$ $u_{list}$ \+\\
%                          $($\LFL\=\verb|['\n']|\rdb\ $a_{list}$ $u_{list}$\+\\
%                                (h xs acc)$)$
%\end{tabbing}
%\end{quote}
%To save space, the innermost optimization will be evaluated first to obtain
%\verb|('\n':h xs acc)|; finishing off the optimization then results in
%the following:
%\begin{quote} \centering  \tt
%\begin{tabbing}
%un\= lines ls = h ls []\+\\
%  where \= h []~~~~~acc = acc\+\\
%           h (x:xs) acc = x ++ \verb|('\n':h xs acc)|
%\end{tabbing}
%\end{quote}
%It is possible to improve the traversal rules so that the constant
%argument {\tt acc} is eliminated from the above; alternatively, this
%optimization can be performed independently for the entire program.
%
%When optimized, the definition of {\tt unlines} yields good code, but
%is not notably more parallel than other optimization techniques (for
%example, it is nearly isomorphic to the optimized definition obtained
%in \cite{bib:shortcut}).  

Now that the description of the optimization rules is complete, an
example is certainly in order.  The following code (to sum the
elements of a list of lists) generates parallel code when optimized.
\begin{center}
\begin{verbatim}
llsum = sum . concat
\end{verbatim}
\end{center}
Inlining {\tt sum} and composition, the following definition is obtained:
\begin{center}
\begin{verbatim}
llsum xss = reduce (+) 0 (someOrder (concat xss))
\end{verbatim}
\end{center}
Useful optimization begins when the reduction is encountered (since 0
is a constant it is inlined on the fly for brevity):
\begin{center} \tt
\begin{tabbing}
llsum xss = \LEL\LFL\= someOrder (concat xss)\rdb\+\\
                        $(\lambda l\:r\:t.\:(l\:$0$)$ + $(r\:$0$))$
                        const 0\rdb
\end{tabbing}
\end{center}
Now optimization continues through the call to {\tt someOrder}:
\begin{center} \tt
\begin{tabbing}
llsum xss = \LEL\LFL\= concat xss\rdb\+\\
                        $($bothways $(\lambda l\:r\:t.\:(l\:$0$)$ + $(r\:$0$)))$\\
                        const 0\rdb
\end{tabbing}
\end{center}
And on to the \concat :
\begin{center} \tt
\begin{tabbing}
llsum xss = \LEL\LFL\= xss\rdb\+\\
                $(\lambda e.\:$\LFL\= e\rdb\+\\
                $($bothways $\ldots)$\\
                        const 0$)$\-\\
                $($bothways $(\lambda l\:r\:t.\:(l\:$0$)$ + $(r\:$0$)))$\\
                const 0\rdb
\end{tabbing}
\end{center}
Now in order to generate the loop over {\tt xss}, the innermost
optimization needs to be performed eagerly so that its strictness can
be determined.  To do so, use the dummy value {\tt d} for $t$; the
symbol {\tt e} is provided by the translation:
\begin{center} \tt
\begin{tabbing}
\LF{e} $($bothways $(\lambda l\:r\:t.\:(l\:$0$)$ + $(r\:$0$)))$
                        const 0 d
\end{tabbing}
\end{center}
Now, since addition is strict in both arguments, this inner traversal
can be performed iteratively as follows:
\begin{center} \tt
\begin{verbatim}
let h []     acc = acc
    h (e:es) acc = h es (acc + e)
in  h e d
\end{verbatim}
\end{center}
Since {\tt h} is strict in {\tt acc}, the original function was strict
in its last argument.  The following code for llsum therefore results:
\begin{center} \tt
\begin{tabbing}
ll\= sum xss =\+\\
  \LEL h'\=\ xss 0\+\\
                where \= h' []~~~~~acc' = acc'\+\\
                         h'\=\ (x:xs) acc' = h' xs (acc' + h x 0)\+\\
                           where \= h []~~~~~acc = acc\+\\
                                    h (e:es) acc = h es (acc + e)\rdb
\end{tabbing}
\end{center}
No further optimization is possible on the body, so the call to $\cal
L\!E$ will simply disappear.  

The important line in this definition is the second disjunct of {\tt
h'}.  In a system without a notion of reduction, the following code
will result for that line:
\begin{quote} \centering
\begin{verbatim}
h' (x:xs) acc' = h' xs (h x acc')
\end{verbatim}
\end{quote}
In the \map /\reduce\ system, the call {\tt h x 0} can proceed before
{\tt acc'} is available.  Thus, by executing the outer loop {\tt h'}
eagerly, the sublists can be computed independently; only the
computation of the final loop result need wait for the completion
of the inner loops.

\subsection{A note on efficiency}

The optimization rules given here certainly do not produce the best
{\em possible} code.  In particular, consider the following example:
\begin{quote} \centering
\begin{verbatim}
sort xs = reduce merge [] (map (:[]) xs)
\end{verbatim}
\end{quote}
This appears to implement mergesort---individual, sorted sublists are
merged together two by two to yield the final sorted result.  Note,
however, that the above produces the following code after
optimization:
\begin{quote} \centering
\begin{verbatim}
sort xs = h xs []
  where h []     acc = acc
        h (e:es) acc = h es (merge acc [e])
\end{verbatim}
\end{quote}
Inlining {\tt sort} at the points where it is used is likely to
improve matters somewhat (by merging sorted sublists in one go), but
the fact remains that the underlying algorithm is simple insertion
sort.  This turns out to be a fundamental limitation of the traversal
rules.  In general, to optimize a reduction something must be known
about the behavior of the function being reduced.  It is thus
extremely difficult to come up with rules analogous to those in
Figure~\ref{fig:genrules} which will produce good code both for
straight-through and divide-and-conquer algorithms without recourse to
some additional annotations.  It should be possible, however, to add
new functions representing, say, divide-and-conquer reduction.

More fundamentally, the optimizations cannot take a bad algorithm and
turn it into a good algorithm.  For example, asymptotic time behavior
ought to be much the same as it is when reduction is implemented using
a fold.  This also means that optimization will not make an inherently
parallel algorithm sequential.  

\section{Correctness and Referential Transparency}

One important problem has been glossed over in the discussion so
far---the correctness of the \reduce\ operator itself.  Early on it
was noted that the first two arguments to \reduce\ must be an
associative operator and its identity.  The compiler, however, has no
particular notion of an associative operator.  This means that it is
perfectly permissible to write the following two expressions (which
produce different results even though their arguments are
identical in a semantic sense):
\begin{quote} \centering
\begin{verbatim}
reduce (-) 0 [1..10]
reduce (-) 0 ([1..5]++[6..10])
\end{verbatim}
\end{quote}
Because of \map /\reduce\ optimization, reduction is very sensitive to
the {\em way} in which its arguments are computed.  This sensitivity
disappears when \reduce\ is used properly, but can potentially cause
hard-to-spot problems in incorrect code.

%It is possible to imagine putting the type system to work so that
%reduction is safe once again.  For example, Haskell's class system
%might be employed to declare that certain operators are associative
%and have a certain identity.  Such a declaration might take the
%following form:
%\begin{quote} \centering
%\begin{verbatim}
%class Monoid a where
%  join :: a -> a -> a
%  unit :: a
%\end{verbatim}
%\end{quote}
%While this adds useful structure to the language, and suggests
%extensions such as monoid comprehensions (in the spirit of monad
%comprehensions\cite{bib:compmonad}), it ignores the fact that there
%can be several monoids of a particular type.  For example, both
%$(+,0,id)$ and $(max,0,id)$ are monoids on the natural numbers.  In
%order to represent both of these monoids in the type class framework,
%new types and explicit conversion operations would need to be devised.
%Beyond this shortcoming, type classes simply centralize the
%bookkeeping of reduction without actively enforcing any of the
%necessary restrictions.

The {\tt someOrder} operation suffers the same referential opacity as
as \reduce .  One way to reason about the ordering of the argument to
{\tt someOrder} is to assume it is a function of some (unknown)
underlying state.  Such reasoning is not particularly useful, however,
since that state can only be manifested (through calls to {\tt
someOrder}) and not manipulated.

The pH compiler takes the position that \reduce\ and {\tt someOrder}
are not really functions at all---an eminently reasonable assertion,
since the optimization rules treat them quite differently from
fully-fledged functions.  Instead, the programmer treats them as
special syntax which happens to resemble function call.  From the
standpoint of the rest of the compiler, however, \reduce\ and
{\tt someOrder} can be treated just like ordinary functions.

\section{Applications}

The \map /\reduce\ mechanism is used to implement a number of
additional features in the pH language.  This section briefly examines
three such features: {\tt for} loops, array comprehensions, and open
lists.  All three were implemented as distinct mechanisms in the Id
language compiler\cite{bib:idreport,bib:idcomps}.  One of the chief
motivating factors behind the introduction of the \map /\reduce\
mechanism was to handle these three features in a single uniform
manner without sacrificing the efficiency of the original Id language
translations.  In doing so, much has been learned about the behavior
of reduction in the presence of higher-order functions and state.

\subsection{{\tt for} Loops}

The pH compiler contains several syntactic extensions to Haskell.  One
of these is the {\tt for} loop.  It is expressed as in
Id\cite{bib:idreport}, as a series of bindings which includes free
references to a set of $k$ {\em circulating variables} $c_{1}, c_{2},
\ldots c_{k}$ and which binds a corresponding set of {\em nextified
variables}, $n_{1}, n_{2}, \ldots n_{k}$.\footnote{Note that in Id,
$n_{i}$ is written as {\tt next} $c_{i}$.  This renders the rules
virtually unreadable; thus the choice of notation here.} A {\tt for}
loop over the list {\tt xs} is thus written:
\begin{quote} \centering 
\begin{tabbing}
{\tt l}\= {\tt e}\= {\tt t}\= \kill
{\tt let} \+ \+ \\
       {\em initial bindings for} $c_{1}, c_{2}, \ldots c_{k}$ \- \- \\
{\tt in} \+ \\
 {\tt for x <- xs do } \+ \+ \\
   {\em bindings, including ones for} $n_{1}, n_{2}, \ldots n_{k}$ \- \- \\
 {\tt finally f} $c_{1}, c_{2}, \ldots c_{k}$ \-
\end{tabbing}
\end{quote}
For example, to find the arithmetic mean of a list of numbers, the
following function can be used:
\begin{quote} \centering 
\begin{verbatim}
mean xs =
  let sum = 0
      len = 0
  in for x <- xs do
        next sum = sum + x
        next len = len + 1
     in sum / len
\end{verbatim}
\end{quote}
A continuation-passing expansion for loops can be defined using \foldr :
\begin{quote} \centering 
\begin{tabbing}
{\tt l}\= {\tt e}\= {\tt t}\= \kill
{\tt let} \+ \+ \\
       {\em initial bindings for} $c_{1}, c_{2}, \ldots c_{k}$ \- \- \\
{\tt in} \+ \\
        {\tt foldr }\= \verb|(\x |\= {\tt cont $c_{1}$ $c_{2}$ $\ldots c_{k}$ ->} \+ \+ \\
          {\tt le}\= {\tt t} \+ \\
            {\em bindings, including} $n_{1}, n_{2}, \ldots n_{k}$\- \\
          {\tt in cont $n_{1}$ $n_{2}$ $\ldots n_{k}$)} \- \\
        {\tt f}\\
        {\tt xs}\\
        $c_{1}$ $c_{2}$ $\ldots c_{k}$
\end{tabbing}
\end{quote}
This leads
to a more concise desugared definition for {\tt mean}:
\begin{quote} \centering 
\begin{verbatim}
mean xs =
  let sum = 0
      len = 0
  in foldr (\x cont sum len ->
                let next sum = sum + x
                    next len = len + 1
                in cont (next sum) (next len))
           (\sum len -> sum / len)
           xs sum len
\end{verbatim}
\end{quote}
By using inlining and $\eta$-abstracting all arguments which
correspond to circulating variables, completely iterative code is
generated.  Since the functions being folded require at least the $k$
arguments representing the circulating variables before performing any
computation, such an $\eta$-abstraction step is justified.  This
results in the following optimized code for {\tt mean}:
\begin{quote} \centering
\begin{verbatim}
mean xs =
  let sum = 0
      len = 0
  in  h xs sum len
        where h []     sum len = sum / len
              h (x:es) sum len = 
                let next sum = sum + x
                    next len = len + 1
                in h es (next sum) (next len))
\end{verbatim}
\end{quote}
In general, \map /\reduce\ optimization combined with constant
argument removal and $\eta$-reduction are powerful enough to handle a
large class of traversals involving higher-order functions---which in
turn permit an even larger class of list traversals to be captured
efficiently in the language.  This three-optimization chain is
important enough in the pH compiler that the optimizations have
been combined with \map / \reduce\ optimization into a single pass.

\subsection{Array comprehensions}

One of the chief complaints about Haskell from the Id community is
that Haskell's array system is bulky---in particular, a number of
array operations require a list of index/value pairs as an
argument.  For example, this expression creates a grade-school
multiplication table for pairs of integers between 0 and 10:
\begin{verbatim}
table = array b [ (i, a*b) | i@(a,b) <- range b ]
          where b = ((0,0),(10,10))
\end{verbatim}
In pH, this mechanism supplants Id's specialized array comprehensions
and accumulators.  Id array comprehensions make use of I-structures
(which must be explicitly written to at most once) to construct an
array in parallel with its use \cite{bib:idcomps}.  By defining a list
traversal which uses these same techniques, the full performance of Id
array comprehensions can be realized.  Thus, pH need not trade
syntactic compactness and elegance for performance.

The approach used is based on monadic state transformers
\cite{bib:statetrans}.  However, because an I-structure model is being
used, the results of a write operation will be visible throughout the
program.  This requires that the notion of a state transformer be
modified somewhat, but permits write operations to occur
simultaneously in several parts of the program without loss of safety.
The type {\tt IAT a b} is used to encapsulate the necessary state
transformations---a value of this type will partially fill an array
indexed by type {\tt a} with elements of type {\tt b}.  The following
functions are used for the definition of array
comprehensions\footnote{Ignoring the orthogonal problem of linearizing
array indices, which is treated explicitly in Haskell.}:
\begin{center} \tt
\begin{tabular}{l@{\ ::\ }l}
makeIAT  &  (a,a) -> IAT a b -> Array a b\\
storeIAT &  a -> b -> IAT a b \\
 \\
parIAT   &  IAT a b -> IAT a b -> IAT a b \\
noIAT    &  IAT a b
\end{tabular}
\end{center}
These give rise to the following definition for the function {\tt
array} (very similar to the one in \cite{bib:shortcut}):
\begin{quote} \centering
\begin{verbatim}
array bounds ivs = makeIAT bounds stores
  where 
    stores = reduce parIAT noIAT 
                (map (uncurry storeIAT) ivs)
\end{verbatim}
\end{quote}
The call to {\tt makeIAT} creates an array with the requested bounds
and performs the necessary stores into it.  These stores are specified
by the {\tt storeIAT} operation ({\tt uncurry} permits it to be used
on the index/value pairs {\tt ivs}).  The {\tt parIAT} operation
states that any pair of transformations may occur safely in parallel,
and the reduction thus states that all the stores may happen
simultaneously.  The identity transformation is {\tt noIAT}, or ``do
nothing''.  

Readers familiar with the implementation of state transformers will
recognize that they require the use of higher-order functions; these
higher-order functions make state available to component computations.
The same techniques of constant argument elimination and
$\eta$-abstraction which are used for {\tt for} loops are used to
eliminate extra functions and generate efficient code for arrays.

\subsection{Open Lists}

List comprehensions in Id make use of open lists to parallelize list
contruction.  Open lists are represented internally by data structures
which are isomorphic to lists, except that their tails are initially
empty and can later be filled in using I-structure operations.  This
permits lists to be constructed eagerly starting from the head and
working towards the tail.  It also permits sublists to be computed
independently and appended in unit time.  This eliminates the chief
bottleneck in parallel list creation---that sublists must wait for the
result to their right to be computed (or, if one is thinking lazily,
computation of each sublist must wait for the completion of the
sublist to its left).  More information on the open list technique has
appeared elsewhere\cite{bib:agna}.

Parallel state transformers can once again be used to implement open
lists in pH.  Here the state transformation is encapsulated in the
type {\tt OL a}, which represents a computation operating on open
lists with element type {\tt a}.  The following operations are
defined:
\begin{center} \tt
\begin{tabular}{l@{\ ::\ }l}
makeOL   & OL a -> [a] \\
unitOL   & a -> OL a \\
appendOL & OL a -> OL a -> OL a \\
emptyOL  & OL a \\
 \\
consOL   & a -> OL a -> OL a \\
snocOL   & OL a -> a -> OL a
\end{tabular}
\end{center}
In principle, an open list computation can thus be written as follows:
\begin{center} \tt
\begin{tabbing}
lst = makeOL (reduce \= appendOL emptyOL \+\\
                        (map unitOL {\em (list computation)}))
\end{tabbing}
\end{center}
There are a number of complications to this apparently simple scheme.
First, the use of open lists is {\em implicit} in the Id compiler for
efficiency reasons.  A partial solution to this problem is to re-cast
\map /\reduce\ optimization in terms of the open list operations, as
follows:
\begin{center}\tt
\begin{tabular}{l@{\ $=$\ }l}
$a_{list}$      &       appendOL \\
$u_{list}$      &       $(\lambda e.\:$unitOL \LE{$e$}$)$ \\
$t_{list}$      &       emptyOL
\end{tabular}
\end{center}
This means that uses of the \LFF\ optimization rule in the rules for
\LEE\ must now introduce a call to {\tt makeOL}.  For efficiency
reasons $a_{list}$ also needs to be written to incorporate the
following peephole optimizations (where the right hand forms allocate
half as much storage as the forms on the left):
\begin{center}\tt
\begin{tabular}{l@{\ $=$\ }l}
appendOL (unitOL x) ol  &       consOL x ol \\
appendOL ol (unitOL x)  &       snocOL ol x
\end{tabular}
\end{center}
The final, and most difficult, problem with open lists is the
frequency of copying.  In the traversal rules, the following rewriting
was given for a list which already exists on the heap:
\begin{center}\tt
\begin{tabular}{lr@{\ $=$\ }l}
\LF{$E$} &      $a$ $u_{list}$ $t$ &    \LE{$E$} ++ $t$
\end{tabular}
\end{center}
This permitted a copy operation to be omitted when {\tt $t=$[]}.
Unfortunately, preexisting lists and open lists have entirely
different types!  Consequently, more trickery is necessary to
efficiently compile open list computations.  At the time of writing
there is no clear, consistent solution to this problem beyond limiting
(in an {\em ad hoc} manner) the situations in which open lists are
introduced by the compiler.  The solution doubtless requires a deeper
understanding of the state transformations underlying the open list
mechanism. 

\subsection{Lifting}

There are many associative operations which might be usefully used for
list optimization, but which do not posess an identity.  For these
functions there is an operation called {\tt reduce1}.  Using the type
called {\tt Maybe}, these operations are explicitly lifted and an
ordinary reduction is performed as follows:
\begin{quote} \centering
\begin{verbatim}
data Maybe a = Nothing | Just a

reduce1 :: (a -> a -> a) -> [a] -> a
reduce1 f = unLift . reduce (lift f) Nothing
  where unLift (Just x) = x
        lift f Nothing y = y
        lift f x Nothing = x
        lift f (Just x) (Just y) = f x y
\end{verbatim}
\end{quote}
A similar technique can be used to define {\tt foldl1} and {\tt
foldr1}.  All of these definitions avoid explicitly destructuring the
list being traversed, but introduce additional data structures.
However, it is often easy to tell at compile time that the list being
traversed is non-empty.  Standard optimization techniques such as
peeling the initial loop iteration and eliminating circulating data
structures whose form is known can often produce excellent code for
traversals of non-empty lists.  However, performance is still poor
when the list being traversed is, for example, a list of
possibly-empty lists flattened using \concat .

\section{Limitations}

The optimizations described so far eliminate lists which are consumed
as soon as they are produced.  While this encompasses a useful class
of list operations and permits data structures (including, as we have
seen, arrays and open lists) to be expressed in terms of list
comprehensions, there are a number of common patterns of usage which
cannot be optimized at the moment.

\subsection{Producing a list from a list}

During the presentation of the optimization rules, only two
functions---\map\ and \concat ---have been used which given a list
will produce a list as a result.  These suffice to capture a large
range of list processing functions (those which can be expressed
entirely using list comprehensions).  There are important functions
which {\em cannot} be expressed in this manner, however.  One
significant example is the function {\tt init}, which returns all of
its argument except for the last element.  It can be written in two
different ways:
\begin{quote} \centering
\begin{verbatim}
init xs = unfold (emptytail xs) 
                 (\(x:xs) -> (x,xs)) xs
  where emptytail [_]   = True
        emptytail (_:_) = False
init xs = 
  fst . reduce1 (\(bl1,l1) (bl2,l2)->
                        (bl1++l1:bl2, l2)) xs
\end{verbatim}
\end{quote}
One workaround is to abstract such operations with respect to the
unit, append, and empty list elements.  This would require the
introduction of an operator analogous to {\tt
build}\cite{bib:shortcut}, and consequent modifications to the type
system.  In addition, uses of a {\tt build}-like operator cannot
benefit from the loop-generation optimizations of
Figure~\ref{fig:genrules}. 

\subsection{Multiple traversals}

Multiple traversals over the same argument list can in principle be
combined into a single traversal.  Other approaches to list
optimization\cite{bib:shortcut} can perform this optimization.  There
are several difficulties.  Two are evident from the following snippet
of code:
\begin{quote} \centering
\begin{verbatim}
let total = reduce (+) 0 xs
in  foldl (f total) i xs
\end{verbatim}
\end{quote}
First, while the list {\tt xs} is consumed twice, there is a potential
data dependency between the two traversals.  If such a dependency
exists, it will be more space-efficient to construct {\tt xs} in the
heap and traverse it twice than to merge the traversals so that the
result of the first iteration depends non-strictly on the result of
the final iteration.  Second, the list {\tt xs} is traversed in two
different ways---using \reduce\ and \foldl .  If the two traversals
can be merged safely, it is not clear that they can be merged {\em
efficiently}.  This problem becomes acute when one of the traversals
being combined makes use of higher-order functions (as with {\tt for}
loops, open lists, or array comprehensions).  By committing to a
sequential list traversal, previous approaches have avoided this
problem entirely.

\subsection{The {\tt zip} problem}

Equally difficult is producing a result by traversing two lists
simultaneously.  This is expressed using the function {\tt zip}, which
pairs corresponding elements of its two list arguments to yield a
single result.  Previous solutions to this problem \cite{bib:shortcut}
define either a ``left-handed'' or ``right-handed'' view of {\tt
zip}---that is, just one of the two arguments is systematically
consumed to produce the result.

The {\tt zip} problem may well be solvable in the \map /\reduce\
framework by inverting the direction of optimization---in other words,
proceed from the generation or use of a list outwards, combining \map\
and {\tt build}, until the resulting list is consumed by reduction,
folding, or {\tt zip}.  When both arguments to {\tt zip} have thus
been optimized, combine them (combining calls to \unfold\ should not
be difficult).  Such an approach would be very difficult to integrate
with any solution to the previous (multiple traversal) problem,
however.  In addition, it is unclear how \concat\ should be handled in
this framework.  Nonetheless, this technique merits further attention.

\section{Related Work}

The work on which this paper is based first began as an effort to
integrate list optimization with list comprehension desugaring.  This
effort is described in the author's M.~Eng.~thesis\cite{bib:mythesis}.
Its eventual separation into a separate compiler pass was due to
engineering problems (the code inliner worked only on desugared code).
Nonetheless, it has provided an opportunity to clean up the
transformations substantially and to better understand their behavior.
This has resulted in a number of improvements, the most obvious being
the the positioning of inner optimizations.

The transformations described in this thesis are (as noted previously)
based heavily on Gill, Launchbury, and Peyton-Jones's ``Short Cut to
Deforestation'' \cite{bib:shortcut}.  That work focuses heavily on the
interaction of the \foldr\ and {\tt build} operations, just as this
work centers around the use of \map , \reduce , and \unfold .  Both
share the view that lists play a pivotal role in functional programs,
and that it is therefore worth spending time and effort on
optimizations specifically geared towards them.  This work in turn has
its roots in work on
deforestation\cite{bib:deforest,bib:listless,bib:fusion}. 

A number of works on constructive programming proved indispensible in
fleshing out the theory behind \map\ and \reduce , and in providing
inspiration for the unification of reduction and folding.  Chief among
these are Meertens' seminal paper\cite{bib:algorithmics} and Bird's
lecture notes on constructive programming, which heavily emphasize the
use of the list monoid to express computation\cite{bib:theory,bib:constructive}.  The text by
Bird and Wadler\cite{bib:introfunc} provides a more pragmatic view of
the constructive style.  An amusingly-titled paper by Meijer, Fokkinga, and
Paterson\cite{bib:banana} explores general relationships between
algebraic types and the recursive functions used to traverse them; the
examples for lists are excellent, and the paper presents structures
for traversal which are not covered elsewhere, in particular
anamorphisms (such as \unfold ) and paramorphisms (the list
paramorphism can capture patterns of traversal similar to \map , but
where the resulting list will also depend on information carried
between iterations).  As noted earlier, \cite{bib:parcon} compares the
expressive power of the Bird-Meertens formalism favorably to other
models of parallel computation, suggesting that it is a fitting
generalization of data parallel techniques.

In spirit, using higher-order functions to ``plumb together'' related
computations has become an important part of every functional
programmer's bag of tools.  Such techniques permit details of state
and ordering to be reasoned about; this observations is at the heart
of monadic programming techniques\cite{bib:monads}.  One subgoal of
the current work is to form a functional view of imperative concepts
from dataflow languages, such as I- and M-
structures\cite{bib:idreport}, by adapting state
transformers\cite{bib:statetrans} to new patterns of usage.

The original motivation for the work presented here was to
transparently encapsulate the behavior of the list and array
comprehensions from Id\cite{bib:idreport}, which were designed and
implemented over the course of several years by a large group of
people (including Aditya, Nikhil, and Arvind) and are described in
documentation put together by Zhou\cite{bib:idcomps}.  The paper by
Heytens and Nikhil\cite{bib:agna} provided a springboard in its
discussion of open lists and comprehensions in a parallel environment.
The programming techniques described in this thesis are an integral
part of pH, and are described in the language report\cite{bib:phreport}.

\section*{Acknowledgements}

This work, and the entire pH effort in general, would never have been
possible without the generous cooperation of Len\-nart Augustsson, whose
{\tt hbcc} compiler supports the syntactic extensions of pH.
Additional thanks must be given to Arvind, who originally prompted
this work at the beginning of the pH effort, and who has kept things
heading in the right direction.  Finally, this work has benefited
greatly from comments and conversations with many people both at MIT
and elsewhere, whose ideas have suggested numerous improvements and
clarifications in the work leading to this paper.

\bibliography{refs}

\end{document}