paper.tex

%-----------------------------------------------------------------------------
%
%               Template for sigplanconf LaTeX Class
%
% Name:         sigplanconf-template.tex
%
% Purpose:      A template for sigplanconf.cls, which is a LaTeX 2e class
%               file for SIGPLAN conference proceedings.
%
% Guide:        Refer to "Author's Guide to the ACM SIGPLAN Class,"
%               sigplanconf-guide.pdf
%
% Author:       Paul C. Anagnostopoulos
%               Windfall Software
%               978 371-2316
%               paul@windfall.com
%
% Created:      15 February 2005
%
%-----------------------------------------------------------------------------


\documentclass[preprint]{sigplanconf}

% The following \documentclass options may be useful:

% preprint      Remove this option only once the paper is in final form.
% 10pt          To set in 10-point type instead of 9-point.
% 11pt          To set in 11-point type instead of 9-point.
% authoryear    To obtain author/year citation style instead of numeric.

\usepackage{amsmath}
\usepackage{longtable}
\usepackage{stmaryrd}
\usepackage[mathletters]{ucs}
\usepackage[utf8x]{inputenc}
\usepackage{fancyvrb}

\begin{document}

\special{papersize=8.5in,11in}
\setlength{\pdfpageheight}{\paperheight}
\setlength{\pdfpagewidth}{\paperwidth}

\conferenceinfo{CONF 'yy}{Month d--d, 20yy, City, ST, Country} 
\copyrightyear{20yy} 
\copyrightdata{978-1-nnnn-nnnn-n/yy/mm} 
\doi{nnnnnnn.nnnnnnn}

% Uncomment one of the following two, if you are not going for the 
% traditional copyright transfer agreement.

%\exclusivelicense                % ACM gets exclusive license to publish, 
                                  % you retain copyright

%\permissiontopublish             % ACM gets nonexclusive license to publish
                                  % (paid open-access papers, 
                                  % short abstracts)

\titlebanner{banner above paper title}        % These are ignored unless
\preprintfooter{short description of paper}   % 'preprint' option specified.

\title{Relating two Abstractions for Formal Array Languages}
%\subtitle{Subtitle Text, if any}

\authorinfo{Josef Svenningsson}
           {Department of Computer Science of Engineering\\Chalmers University of Technology}
           {josef.svenningsson@chalmers.se}
\authorinfo{Lenore M. Mullin}
           {Emeritus Professor\\Department of Computer Science\\
University at Albany, SUNY}
           {lenore@albany.edu}

\maketitle

\begin{abstract}
The aim of this paper is to rectify some of the fragmentation
within the high-performance array programming community. We look at two
formalisms for functional, high-performance array computations:
Mathematics of Arrays and Pull arrays, two seemingly different formalisms
that share many principles and properties.   This paper is meant to
identify the striking similarities between the two  and to act as a guide  to enable research communications.


\end{abstract}

% \category{CR-number}{subcategory}{third-level}

% general terms are not compulsory anymore, 
% you may leave them out
%\terms
%term1, term2

%\keywords
%Arrays

\section{Introduction}

Computing with arrays has been a constantly important paradigm in the
history of computing. For this reason we have seen a plethora of
formalisms and languages being developed to aid theoreticians and
developers to produce more suitable abstractions and faster programs.
Examples include FORTRAN, APL and Matlab but the list goes on and on.
Having many different options to choose from can be a good thing but
it can also lead to a balkanization of the community. When researchers
dedicated to different formalisms can no longer talk to each other,  it
inhibits collaborations and limits the impact of innovation.

In this paper we aim to rectify some of the fragmentation of the
high-performance array programming community by relating two
particular formalisms: Mathematics of Arrays and Pull arrays. On the
surface they appear rather different but at their core they share many
principles and properties which we will examine in this paper. In
particular we will highlight the following points:
\begin{itemize}
\item We give an introduction to both MoA (section \ref{sec:moa}) and Pull
  arrays (section \ref{sec:pull}).
\item The two formalisms are compared with respect to types (section
  \ref{sec:types}), fusion/\(\psi\)-reduction (section
  \ref{sec:normalization}), 
  how they deal with higher dimensions (section \ref{sec:highdim})
  and notation (section \ref{sec:notation}).
\end{itemize}

We would like to stress that we are not looking to declare a
winner. Instead our intention is that this paper can serve as a help
for the two communities to be able to learn about each others work.

\section{Overview of MoA}
\label{sec:moa}
\input{intromoa}
\section{Overview of Pull arrays}
\label{sec:pull}

The functional programming community has recently gained an increased
interest in high performance parallel array programming
\cite{keller2010regular,Axelsson:2010:Feldspar,Mainland:2010:Nikola,Svensson:2011:Obsidian,Claessen:2012:Expressive,Ankner:2013:AnEDSL,lippmeier2011efficient}. One
of the central abstractions in this line of work is \emph{pull
 arrays}, also know as delayed arrays. The can be defined as follows
(we use Haskell \cite{marlow2010haskell} to demonstrate functions
programs).

\begin{small}
\begin{Verbatim}
data Pull a = Pull { ixf    :: (Int -> a)
                   , length :: Int
                   }
\end{Verbatim}
\end{small}

Arrays are represented as functions from index to element. We refer to
this function as an \emph{index function}. Additionally arrays also
have a length.

This representation has several advantages:
\begin{itemize}
\item \emph{Parallelism}. Since each element is computed
  independently, they can easily be computed in parallel.
\item \emph{Fusion}. When functions on pull arrays are composed, the intermediate
  arrays can be automatically removed. 
\item \emph{Compositionality}. Pull arrays provide a wealth of
  compositional and highly reusable combinators. These can be composed
  together to write high-level programs which typically are easier to
  understand than monolithic array processing code.
\end{itemize}

Figure \ref{fig:pullex} shows some examples of functions on Pull
arrays. Things to note are that most functions are polymorphic; they
can operate on arrays of any type of element.

\begin{figure}
\begin{small}
\begin{Verbatim}
map :: (a -> b) -> Pull a -> Pull b
map f (Pull ixf l) = Pull (f . ixf) l

zipWith :: (a -> b -> c)
        -> Pull a -> Pull b -> Pull c
zipWith f (Pull ixf1 l1) (Pull ixf2 l2)
  = Pull (\i -> f (ixf1 i) (ixf2 i)) (min l1 l2)

take :: Int -> Pull a -> Pull a
take n (Pull ixf l) = Pull ixf (min n l)

drop :: Int -> Pull a -> Pull a
drop n (Pull ixf l)
  = Pull (\i -> ixf (i + n)) (max (l - n) 0)

rotate :: Int -> Pull a -> Pull a
rotate k (Pull ixf l)
  = Pull (\i -> ixf ((i + k) `mod` l)) l

reverse :: Pull a -> Pull a
reverse (Pull ixf l) = Pull (\i -> ixf (l - i - 1) l

enumFromTo :: Int -> Int -> Pull Int
enumFromTo f t = Pull (\i -> i + f) (t - f + 1)
\end{Verbatim}
\end{small}
\caption{Example functions on pull arrays}
\label{fig:pullex}
\end{figure}

\subsection{Fusion}

As mentioned, one of the most important advantages of Pull arrays is
that they support
fusion\cite{gill1993short,axelsson2010feldspar,keller2010regular}. Fusion
is a program transformation which removes intermediate data structures.
Fusion supersedes transformations such
as loop fusion in optimizing compilers for imperative languages.  Pull
arrays make it particularly simple to achieve fusion. It simply
amounts to inlining the definitions of functions.

As an example of fusion consider the example from the section which
was used to illustrate $\psi$-reductions. Here is how it is written
using Pull arrays for the one-dimensional case:\\
{\small
\verb!zipWith (*) (take 2 (reverse a)) (drop 1 (reverse a))!}.\\
Conceptually there are many intermediate arrays here, but they will be
removed by fusion. Fusion will proceed by inlining the definition
of the functions as follows:

\begin{small}
\begin{Verbatim}
zipWith (*) (take 2 (reverse a))
            (drop 1 (reverse a))
  => { arr }
zipWith (*) (take 2 (reverse (Pull ixf l))
            (drop 2 (reverse (Pull ixf l)))
  => { reverse * 2 }
zipWith (*) (take 2 (Pull (\i -> ixf (l - i - 1)) l))
            (drop 1 (Pull (\i -> ixf (l - i - 1)) l))
  => { take , drop }
zipWith (*) (Pull (\i -> ixf (l - i - 1)) (min 2 l))
            (Pull (\i -> ixf (l - i)) (max (l - 1) 0))
  => { zipWith }
Pull (\i -> ixf (l - i - 1) * ixf (l - i))
  (min (min 2 l) (max (l - 1) 0))
\end{Verbatim}
\end{small}

The result is a single Pull array, the intermediate array has been
removed. The result is the same in MoA, modulo syntax and the fact
that we here use a one-dimensional array of unknown size.

The correctness of fusion relies crucially on the language being
\emph{pure}. If side effects were allowed in the indexing function
fusion would not be correct.

Fusion effectively makes Pull arrays \emph{virtual} in that they will
not be represented in memory. All intermediate arrays will be
removed. But sometimes it is important to keep an array in memory
\footnote{Example: Indexing a column of a huge transposed array that has a few rows and many columns. In this case, non-materialization
may have long strides causing many cache misses and page faults.}, 
not least to produce the final result. For this reason, Pull arrays
provide a function, variously known as \verb!force!, \verb!memorize!
  or \verb!store!. We will refer to it as \verb!store! here. The
  functional semantics of \verb!store! is the identity function,
  i.e. it simply returns the same array as it was given. However, as a
  side effect it stores the array to memory.

A subtle point about \verb!store! is that the language is still pure
with this function. The reason is that there is no way to observe from
within the language whether an array is stored to memory or
not. Therefore, the side-effect of \verb!store! cannot affect the
value of a computation.

\subsection{Implementing Fusion}

There are two different ways of implementing Pull arrays in the
literature. The simplest one comes from using Pull arrays in an
embedded language, i.e. when the array language is implemented as a
library in another host language. Examples of such languages are
Pan\cite{elliott2003compiling}, Feldspar\cite{Axelsson:2010:Feldspar},
Obsidian\cite{Svensson:2011:Obsidian} and
Nikola\cite{Mainland:2010:Nikola}. By using the technique of
implementing Pull arrays as \emph{shallow embeddings} on top of a
\emph{deeply embedded} code language, fusion comes completely for free
\cite{svenningsson2013combining}.
In the array library Repa\cite{keller2010regular}, compiler supported
rewrite rules are used to implement fusion \cite{jones2001playing}.


\subsection{Higher dimensions}

The first uses of Pull arrays used a fixed number of dimensions,
typically either one or two. However, the Repa library introduced a
new expressive notion of higher dimensionality for Push arrays
\cite{keller2010regular}. The number of dimensions of an array, referred
to as the \emph{shape}, are determined statically in the type
system. The advantage of having the shape as part of the type is that
any program which produces arrays with ill-defined shapes can be ruled
out. A potential downside is that enforcing shapes in the type system might
be overly constraining and exclude useful programs. A key innovation in
Repa is the notion of \emph{shape polymorphism} which makes it
possible to write functions which accepts arrays of any shape. Below
shows the definition of the type of shapes. It is a variation on how
it is represented in Feldspar.

\begin{small}
\begin{Verbatim}
data Z
data i :. sh

data Shape sh where
  Z :: Shape Z
  (:.) :: Shape tail -> Int -> Shape (tail :. Int)
\end{Verbatim}
\end{small}

The first two data declarations introduces new types, \verb!Z! and
\verb!:.!, without any constructors. They are used to create
snoc-lists on the type level, the definition of \verb!Shape!.  The
type \verb!Shape! is a recursive data type with two constructors. The
first constructor \verb!Z! indicates that the shape has zero
dimensions.  The second constructor \verb!:.! adds one dimension to
another shape, and stores how many elements there are in that
dimension. The type \verb!Shape! has a type parameter which is a snoc
list with one element for each dimension.

Below we show how higher dimensional Pull arrays can be defined using
the \verb!Shape! type. We also show some functions adapted for the new
representation. Note the shape polymorphism in the definitions of
\verb!map! and \verb!zipWith!. They can work with arrays of any
shapes, as long as they are the same shape.  The function
\verb!reverse! is particularly noteworthy because the type reflects
that the input and output arrays need to have at least one dimension.

\begin{small}
\begin{Verbatim}
data Pull sh a = Pull (Shape sh -> a) (Shape sh)

map :: (a -> b) -> Pull sh a -> Pull sh a
map f (Pull ixf sh) = Pull (f . ixf) sh

zipWith :: (a -> b -> b) -> 
           Pull sh a -> Pull sh b -> Pull sh c
zipWith f (Pull ixf1 sh1) (Pull ixf2 sh2)
  = Pull (\sh -> f (ixf1 sh) (ixf2 sh2))

reverse :: Pull (sh :. Data Length) a ->
           Pull (sh :. Data Length) a
reverse (Pull ixf sh@(_ :. l)) =
 Pull (\(sh' :. i) -> ixf (sh' :. (l - i - 1))) sh
\end{Verbatim}
\end{small}


\section{Comparison}

In this section we relate MoA and Pull arrays. 

An initial observation is that MoA and Pull arrays were developed for
different purposes and that can be seen already by looking at the
notation. Mathematics of Arrays has first and foremost been used for
calculating array programs by hand. This is reflected in the short
names and succinct notation which works very well when doing
pencil-and-paper proofs.

Pull arrays on the other hand were conceived in the context of a
typed functional language. The notation is completely inherited from
the syntax of Haskell \cite{marlow2010haskell}.

\subsection{Types}
\label{sec:types}

When it comes to types MoA keeps things very simple. There is just one
type, arrays.  Scalars are arrays;  their shape is the empty vector. 

% I've removed this statement because \rho is not defined in the paper
%% Consequently, we have the identity given any array, $\xi$
%% \[( \iota (\rho \xi)  )\psi \xi \equiv \xi\]
%% That is, given an array's shape, all indices can be generated to index the entire array.
% scalars are arrays from an MoA and Psi Calculus perspective. 

Pull arrays inherits the type discipline from the language they are
implemented in. When used in Haskell it means that they have a rich
type system to utilize. First and foremost, Pull arrays are
parametric, meaning that they can carry elements of any type. In
particular the elements can be Pull arrays as another way of
representing higher dimensional arrays. This representation is seldom
used as it has poor performance.

\subsection{DNF, \(\psi\)-reductions and fusion}
\label{sec:normalization}

The correspondence between MoA and Pull arrays is most clear when
considering Denotational Normal Form (DNF), \(\psi\)-reductions and
fusion. Both formalisms define operations on arrays by how to index
into the array. In MoA, the indexing function \(\psi\) is used,
whereas for Pull arrays operations are defined as functions from index
to the element at that index. These two forms are equivalent.

Pull arrays are always kept in the form of an indexing function and a
length. This representation is preserved for all operations. In MoA,
arrays are treated as abstract during derivations. After calculations,
\(\psi\)-reductions are performed to bring the expression into
Denotational Normal Form. DNF is equivalent to Pull arrays, it shows
how to compute an element from an array directly from an index.

The process of applying \(\psi\)-reductions corresponds to performing
fusion on Pull arrays. In both cases operations are inlined until
there is a single expression for computing an element from an array
given an index.

Pull arrays use the function \verb!store! to prevent fusion and store
an array in memory. MoA deals with memory differently. All arrays
which are supposed to be allocated in memory are given a separate
definition.

The last step in calculating a program in MoA is to derive an
Operational Normal Form which is explicit about how the array is laid
out in memory. Pull arrays do not have anything corresponding to
ONF. Instead, the decision of how the array is laid out is done by the
compiler, which uses a pre-defined convention.

\subsection{Higher dimensions}
\label{sec:highdim}

Shapes in Pull arrays are represented by a completely different type,
whereas in MoA shapes are simply arrays. Representing shapes as arrays
is challenging in a typed language such as Haskell because it leads to
a form of infinite recursion and while there are a number of ways to
break the recursion we have yet to find a way that does so and retains
the efficiency and simplicity of Pull arrays.

Apart from the differences in the type system, MoA and Pull arrays
treat shapes relatively similar. The type of shapes in Pull arrays can
be seen as just another representation of arrays, one where the length
is part of the type.

\subsection{Functions}
\label{sec:notation}

Figure \ref{fig:rosetta} gives a translation between function names
used in MoA and Pull arrays. The intention of this figure is to work
as a Rosetta stone, helping to translate from one formalism to the
other.

As can be seen in the figure, not all operations in MoA have a
corresponding function in the Pull array literature. Some of these
functions are missing because Pull arrays do not have a notion
corresponding to ONF in MoA. In particular, the function $rav$ is used
in ONF to decide on the particular layout of the array, and this step
is implicit for Pull arrays. However, $\Omega$ is a good candidate to
transfer to the formalism of Pull arrays.

The difference between ψ in MoA and \verb!index! i Pull arrays is that
ψ can be used with partial indexes, a central notion in MoA. Pull
arrays solve this problem in a more roundabout way, using a notion of
\emph{slices} \cite{keller2010regular}. We leave out the explanation
of slices for reasons of space.

\begin{figure}
\begin{center}
\begin{tabular}{|@{}l|l@{}|}
\hline
MoA & Feldspar
\\
\hline
δ & \verb!dim . extent!
\\
ρ & \verb!extent!
\\
ιξⁿ & \verb!enumFromTo!
\\
ψ & generalized \verb!index!
\\
rav & -- No corresponding function
\\
γ & \verb!toIndex!
\\
γ' & \verb!fromIndex!
\\
$s \: \hat{ρ} \: ξ$ & \verb!reshape!
\\
π x & \verb!product!
\\
τ & \verb!size!
\\
++ & ++
\\
ξ₁ f ξ₂ & \verb!zipWith f! ξ₁ ξ₁
\\
σ f ξ & \verb!map f! ξ
\\
ξ f σ & \verb!map f! ξ
\\
$\bigtriangleup$ & \verb!take!
\\
$\bigtriangledown$ & \verb!drop!
\\
$op^{red}$ & \verb!fold op!
\\
Φ & \verb!reverse!
\\
Θ & \verb!rotate!
\\
$\varobslash$ & generalized \verb!transpose!
\\
$f Ω_d ξ$ & -- No corresponding function
\\
\hline
\end{tabular}
\end{center}
\caption{A correspondence between functions in MoA and Pull arrays}
\label{fig:rosetta}
\end{figure}

\section{Conclusion and Future work}

Mathematics of Arrays and Pull arrays are a lot more closely related
than what they first might appear. In this paper we have outlined the
relationship between fusion and \(\psi\)-reduction, Pull arrays and
Denotational Normal Form, and the various types of operations used.
Our hope is that this paper will help researchers from both
communities interact and learn from each other.

We have identified a few points where MoA and Pull arrays can learn
from each other. The treatment of higher dimensions in MoA is in
general more thorough than Pull arrays. There are operations like
$\Omega$ which haven't appeared in the literature on Pull arrays but
which would provide a very useful addition.

Pull arrays has a dual representation: Push arrays
\cite{Claessen:2012:Expressive}. It can deal with some of the
shortcomings of Pull arrays, in particular more efficient
concatenation and sharing of computations between array elements. It
would be interesting to see how the ideas of Push array carries over
to MoA.

%% \acks

%% Acknowledgments.

% We recommend abbrvnat bibliography style.

\bibliographystyle{abbrvnat}
\bibliography{bibliography,hpf,paper1,workshop}

% The bibliography should be embedded for final submission.

%% \begin{thebibliography}{}
%% \softraggedright

%% \bibitem[Smith et~al.(2009)Smith, Jones]{smith02}
%% P. Q. Smith, and X. Y. Jones. ...reference text...

%% \end{thebibliography}


\end{document}