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{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}

\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{Title Text}
\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@cs.albany.edu}

\maketitle

\begin{abstract}
This is the text of the abstract.
\end{abstract}

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

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

\keywords
keyword1, keyword2

\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 theoriticians 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 the \emph{pull
  array}, also know as delayed array. The can be defined as follows
(we use Haskell \cite{marlow2010haskell} to demonstrate functions
programs).

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

Arrays are represented as functions from index to element. We refer to
this function as an \emph{index function}. Additionally arrays also
has 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}

\begin{figure}
\begin{verbatim}
-- Mapping a function over an array
map :: (a -> b) -> Pull a -> Pull b
map f (Pull ixf l) = Pull (f . ixf) l

-- Apply a binary operation itemwise on two arrays
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)

-- Takes the n first elements of an array
take :: Int -> Pull a -> Pull a
take n (Pull ixf l) = Pull ixf (min n l)

-- Drops the n first elements of an array
drop :: Int -> Pull a -> Pull a
drop n (Pull ixf l)
  = Pull (\i -> ixf (i + n)) (max (l - n) 0)

-- Rotate an array k steps to the left
rotate :: Int -> Pull a -> Pull a
rotate k (Pull ixf l)
  = Pull (\i -> ixf ((i + k) `mod` l)) l
\end{verbatim}
\caption{Example functions on pull arrays}
\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
and is a decendant of deforestation
\cite{wadler1990deforestation}. Fusion supercedes 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
\verb!map (*2) (map (*5) arr)!, where each element of the array
\verb!arr! is first multiplied by five and then again by
two. Conceptually, there is an intermediate array created after the
first \verb!map! but thanks to fusion it will be removed. Fusion will proceed
as follows:

\begin{verbatim}
map (*2) (map (*5) arr)
=> { arr }
map (*2) (map (*5) (Pull ixf l)
=> { map }
map (*2) (Pull ((*5) . ixf) l)
=> { map }
Pull ((*2) . (*5) . ixf) l)
\end{verbatim}

The result is a single Pull array, the intermediate array has been removed.

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

There are two different ways of implementing Pull arrays in the
literature. The simplest one comes from using Pull arrays in an
embedded langauge, 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}.

Fusion is a powerful optimization which allows programming on a high
level by composing functions without paying an performance penalty.

Fusion effectively makes Pull arrays \emph{virtual} in that they will
not be represented in memory. All intermediate arrays will be
remove. But sometimes it is important to keep an array in memory, 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{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 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 on \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{verbatim}
data Z
data i :. sh

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

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.

\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))
\end{verbatim}


\section{Comparison}

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

* Only one element type in MoA
* Not much in the way of types in MoA

* Shapes are arrays in MoA whereas they are a different type with Pull arrays

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

The similarity between MoA and Pull arrays is most clear when
considering Operatonal Normal Form (ONF). Recall that ONF means that 


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

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

\begin{tabular}{|@{}l|l@{}|}
\hline
MoA & Feldspar
\\
\hline
δ & dim . extent
\\
ρ & extent
\\
ιξⁿ & -- generalized enumFromTo
\\
ψ & index
\\
rav & -- flattens to a one-dimensional array
\\
γ & toIndex
\\
γ' & fromIndex
\\
$s \: \hat{ρ} \: ξ$ & reshape
\\
π x & product
\\
τ & size
\\
++ & ++
\\
ξ₁ f ξ₂ & zipWith f ξ₁ ξ₁
\\
σ f ξ & map f ξ
\\
ξ f σ & map f ξ
\\
$\bigtriangleup$ & take
\\
$\bigtriangledown$ & drop
\\
$op^{red}$ & fold
\\
Φ & reverse
\\
Θ & rotate
\\
$\varobslash$ & -- generalized transpose
\\
$f Ω_d ξ$ & -- Apply $f$ along the dimension $d$ of $ξ$
\\
\hline
\end{tabular}

\subsection{Example programs}

\section{Related work}

\section{Future work}

\section{Conclusion}

\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}