% A TeX version of my  CCSC2005 Paper
\documentclass{article}
\usepackage{graphicx}
\usepackage{html}
\usepackage[margin=1in]{geometry}
\usepackage{fancyvrb}
\usepackage{multicol}
\usepackage{setspace}
%\doublespacing

%\usepackage{prelim2e}
%\usepackage[light,all]{draftcopy}
%\draftcopyName{Draft \today}{70}

\begin{document}
\include{body.tex}

\title{Array Algorithms}

\author{John E. Howland\\
Department of Computer Science\\
Trinity University\\
One Trinity Place\\
San Antonio, Texas  78212-7200\\
Voice:  (210) 999-7364\\
Fax:  (210) 999-7477\\
E-mail:  \htmladdnormallink{jhowland@Trinity.Edu}{mailto:jhowland@trinity.edu}\\
Web:  \htmladdnormallink{http://www.cs.trinity.edu/\~{}jhowland/}{http://www.cs.trinity.edu/~jhowland/}}
%\date{October 11, 2004}
\maketitle

\begin{abstract}
\noindent Array Algorithms are defined as functional algorithms
where each step of the algorithm results in a function
being applied to an array, producing an array result.  Array
algorithms are compared with
non-array algorithms.  A brief rationale for teaching array
algorithms is given together with an example which shows that array
algorithms sometimes lead to surprising results.
~\footnote{This paper is published in the
Journal of Computing Sciences in Colleges, Volume 20, Number 4, April 2005, Pages 229-235.
%Copyright \copyright 2005 by John E. Howland, all rights reserved.}
Copyright \copyright 2005 by the Consortium for Computing Sciences in Colleges.
Permission to copy without fee all or part of this material is granted provided
that the copies are not made or distributed for direct commercial advantage,
the CCSC copyright notice and the title of the publication and its date appear,
and notice is given that copying is by permission of the Consortium for
Computing Sciences in Colleges.  To copy otherwise, or to republish, requires
a fee and/or specific permission.}

\end{abstract}

\noindent Subject Areas:  Array Algorithms, Computer Science Education, Computer Science Curriculum.

\noindent Keywords:  Array Algorithms.

\section{Introduction}

In this paper, the term \emph{array algorithm} is used in a context which
goes beyond algorithms which use array data structures.  Array algorithms use arrays or lists
as their principal data structure and consist of operations which are applied to
arrays producing arrays as results.

Array algorithms, because they deal with data in aggregate, involve different
problem solving processes and require programming languages which easily support
operations on arrays.

Array algorithms have been widely discussed in the literature. A search of the ACM 
digital library for \emph{array algorithm} finds hundreds of citations
\cite{array:matroid,array:aggregates,array:real} \ldots which deal with array algorithms.
Almost all of these papers focus primarily on algorithms which use array
data structures rather than the sense in which we have defined array algorithms.
Metzger, Eisenberg and Peelle \cite{thinking:metzger,thinking:eisenberg,thinking:peelle} have
written on this subject, however their work was directed toward a specific programming
language (APL).

Array algorithms provide a different perspective on problem solving which often leads
to a different insight about the problem being solved.  For this reason,
it is important to include a treatment of array algorithms and array languages in
the undergraduate curriculum.  Computing Curricula 2001 Computer Science
\cite{cc2001:curricula} does not address array programming in the
sense of our definition.

However, because of changes in the design of processors which are now beginning
to be used and will be standard in most systems in the future, it is necessary to
consider program design techniques which will make efficient use of new processor
technology. Recent trends in processor design are following a new direction in order to
continue to follow Moore's Law (that computer processing power approximately
doubles every 18 months).  That new direction is processor designs
from companies such as IBM, Intel, AMD, and others, have multiple processors on
a single chip core rather than having designs of a single processor whose speed doubles
about every 18 months.  Recent multicore chip designs have individual processors which
are actually slower than current generation single processor
designs.  This means that in order to achieve faster computing on such processors,
processing must routinely be done in parallel.  Array algorithms have the potential
of being compiled to run in parallel for such processors.

\section{Array Algorithms}

In simple examples, the differences between array algorithms and non-array algorithms
are subtle.  For example, consider the algorithm which computes the average of a list
of numbers.  In C, this program \verb|ave.c| might be written as:

\begin{verbatim}
#include <stdio.h>
#include <stdlib.h>
int main (int argc, char *argv[])
{ int sum, count, n;
  count = 0;
  sum = 0;
  while (1 == scanf("%d\n", &n))
   { sum = sum + n;
     count++;
   }
  printf("%f", (float)sum / (float)count);
  exit(0);
}
\end{verbatim}

To run this program (after compiling) one could write

\begin{verbatim}
$ echo "1 2 3" | ave
2.000000
\end{verbatim}

An array program, written in the J programming language, a functional
array language, is expressed as:

\begin{verbatim}
$ echo "(+/ % #) 1 2 3" | jconsole
   (+/ % #) 1 2 3
2
\end{verbatim}

The C average program deals with elements of an array or list, without
explicitly storing them in an array, on an item by item basis, accumulating
the sum and count.  After processing all elements in the array, the average is formed
by dividing the sum by the count.
The J average program applies two functions (\verb|+/| ``sum'') and
(\verb|#| ``tally'') to the entire array and then computes the average by
dividing (\verb|%| ``divide'').  The J program uses a functional composition
rule \verb|(f g h) x = (f x) g (h x)| to accomplish this task.

\section{Languages Which Support Array Algorithms}

APL, J, Lisp, Scheme, and array classes for C++ and Java are examples
of languages which have the potential for expressing array algorithms.  

An array language should possess the following features for adequate
expression of array algorithms:

\begin{itemize}
\item create arrays of any type, rank, and size
\item function application on arrays producing array results
\item functions should be ``first class'' data, i.e. we should
be able to have arrays of functions and apply such function arrays
\item higher level functions i.e. apply functions to functions producing
functions as results
\end{itemize}

The J language  \cite{hui:dict} is used in this paper because of its simple syntax and
concise expression of array operations.  Any of the above mentioned
languages could be used, making the paper substantially longer.

\section{Polygon Clipping}

To illustrate a non-trivial array algorithm, consider the well known
algorithm for polygon clipping by Sutherland and Hodgman \cite{sutherland:pclip}.
Polygon clipping reduces a polygonal surface extending beyond the boundary of
some three-dimensional viewing volume to a surface which does not extend beyond
the boundary.  The Sutherland Hodgman algorithm is recursive, processing one line segment at a time
considering each endpoint.

We restrict ourselves to the two-dimensional
case of clipping a closed polygonal figure to a line.  The array algorithm
applies to three-dimensional data without changes to the J program.

Suppose we have the square:

\begin{verbatim}
   [ square =: 5 2 $ 0 0 100 0 100 100 0 100
  0   0
100   0
100 100
  0 100
\end{verbatim}

and the line (in homogeneous form) as illustrated in Figure \ref{fig:one}.

\begin{figure}{}
\centering
\includegraphics[totalheight=1.0in]{figure1.eps}
\caption{Clip a square to a line}
\label{fig:one}
\end{figure}

\begin{verbatim}
   [ line =: _1 1 50
_1 1 50
\end{verbatim}

The array algorithm for polygon clipping (expressed in J) is:

\begin{verbatim}
pclip =: 4 : 0
a =. (( {. $ r =. y.) , 2) $ 1 0
pic =. (r ,. 1) +/ . * x.
a =. 2 (<"1 (i =. (-. (* pic) = * 1 |. pic) # i. {. $ y.) ,. 1) } a
q =. |: ((_1 + $ x.) , $ pic) $ pic
q =. (((i { r) * i { 1 |. q) - (i { 1 |. r) * (i { q)) % (i { 1 |. q) - i { q
r =. (pic > 0) # r
a =. 0 (<"1 ((0 >: pic) # i. $ pic) ,. 0) } a
a =. (-. 0 = a) # a =. , a
r =. (/: /: a) { r , q
r , (-. (1 {. r) -: _1 {. r) # 1 {. r
)
\end{verbatim}

Applying \verb|pclip| we have:

\begin{verbatim}
   line pclip 0 1 2 3 0 { square
  0   0
 50   0
100  50
100 100
  0 100
  0   0
\end{verbatim}

which is illustrated in Figure \ref{fig:two}.  We can clip to the other side of the line by:

\begin{verbatim}
   (-line) pclip 0 1 2 3 0 { square
 50  0
100  0
100 50
 50  0
\end{verbatim}

The J expression of this algorithm is remarkably short, due in part to the
expressive power of J, but also to the array nature of the algorithm where
loops and iterations are contained within the functions which are applied
to arrays.  This is a recurring feature of array algorithms.
We explain the results formed in each of the ten lines of the program.

The first expression produces a table, named \verb|a|, which will be used
to code which side of the line/plane the points lie.  A copy of the original data
is also named (locally) \verb|r| for later use.  Initially, the algorithm assumes
that column 1 of \verb|a|
codes all of the points as being on the correct side of the clipping boundary
with a value of 1.  Later, points which are clipped will be coded with the
value 0 in column 1 and new intersection points which must be added will
be coded in column 2 with a value of 2.

\begin{verbatim}
   a =. (( {. $ r =. y.) , 2) $ 1 0
1 0
1 0
1 0
1 0
1 0
\end{verbatim}

The second line produces a vector of values which indicate which side of
the line/plane (a positive value indicates the correct side of the line/plane) by
computing a matrix product of the homogeneous representation of the points and the
line/plane.  This result is named (locally) \verb|pic|.

\begin{verbatim}
   pic =. (r ,. 1) +/ . * x.
50 _50 50 150 50
\end{verbatim}

The third line modifies column 2 of the table \verb|a| to indicate that the one
point, (100,0), which lies on the wrong side of the clipping line/plane must
be replaced by two points along the clipping boundary which are determined by
computing the intersection with the clipping boundary.

\begin{verbatim}
   a =. 2 (<"1 (i =. (-. (* pic) = * 1 |. pic) # i. {. $ y.) ,. 1) } a
1 2
1 2
1 0
1 0
1 0
\end{verbatim}

The fourth line builds a table, named \verb|q|, of two columns which consist of the
vector \verb|pic|.

\begin{verbatim}
   q =. |: ((_1 + $ x.) , $ pic) $ pic
 50  50
_50 _50
 50  50
150 150
 50  50
\end{verbatim}

The fifth line computes a table, named \verb|q|, of the intersection points with the clipping boundary
of all lines/planes which go outside the clipping boundary.

\begin{verbatim}
   q =. (((i { r) * i { 1 |. q) - (i { 1 |. r) * (i { q)) % (i { 1 |. q) - i { q
 50  0
100 50
\end{verbatim}

The sixth line computes a table, re-named \verb|r|, of the points which are on the
correct side of the clipping boundary.

\begin{verbatim}
   r =. (pic > 0) # r
  0   0
100 100
  0 100
  0   0
\end{verbatim}

The seventh line modifies the table, \verb|a|, to indicate, with a zero in column one,
which points are clipped from the original data.

\begin{verbatim}
   a =. 0 (<"1 ((0 >: pic) # i. $ pic) ,. 0) } a
1 2
0 2
1 0
1 0
1 0
\end{verbatim}

The eighth line produces a vector of the non-zero elements in \verb|a| in
row major order.  This array encodes with the value 1 the respective elements
of \verb|r| and uses the value 2 for the respective elements of \verb|q| which
are the newly computed boundary intersection points.  This vector is the mesh
vector for properly ordering the points not clipped and the boundary intersection
points.

\begin{verbatim}
   a =. (-. 0 = a) # a =. , a
1 2 2 1 1 1
\end{verbatim}

The ninth line uses the grade-up function (\verb|/:|) which produces a permutation
of the indices of an array which would sort the array in ascending order.
That applying grade-up twice produces the proper ordering of elements
taken from a table formed by combining the tables \verb|r| and \verb|q| is
a remarkable surprise.  The ninth line re-arranges
the elements in r and q by sorting a sort!

\begin{verbatim}
   (/: /: a) { r , q
  0   0
 50   0
100  50
100 100
  0 100
  0   0
\end{verbatim}

This algorithm assumes that we start with a closed polygon.  To ensure that
the algorithm produces a closed polygon, the last line closes the polygon
in the case where the first (and last) point is clipped.

\begin{verbatim}
   r , (-. (1 {. r) -: _1 {. r) # 1 {. r
  0   0
 50   0
100  50
100 100
  0 100
  0   0
\end{verbatim}

\begin{figure}{}
\centering
\includegraphics[totalheight=1.0in]{figure2.eps}
\caption{Square after clipping}
\label{fig:two}
\end{figure}

\section{Conclusions}

Array algorithms involve a way of thinking about arrays of
data and performing operations on the entire array.
Array algorithms may be easily parallelized because the array
item processing in each array operation is known to be independent
from the item processing in any other array operation in the algorithm
since the array operations are performed in sequence.

Also, the array thinking discipline leads to more general solutions
which may be used to solve other problems by changing the functions
being applied.  For example, (using J) the matrix product of \verb|a| and
\verb|b| is expressed as the J dot product \verb|a +/ . * b|.  Here we are talking
about summing (\verb|+/|) the products (\verb|*|) of rows of \verb|a|
and columns of \verb|b|. The dot product \verb|a *./ . = b| is useful
for finding matches of rows of a and columns of b.

Teaching students to develop array algorithms gives them another way of looking
at the problem solving process which sometimes gives new insight about the
problem being solved as well as often producing an algorithm which may be
easily parallelized.  Parallel algorithms will be routinely required to
achieve improved performance on new multicore processor designs.  Array
algorithms will play an important role in the development of parallel
software.

\begin{thebibliography}{99}
\raggedright

\bibitem{array:real} Bosse, Michael, ``Real-world Problem-solving, Pedagogy,
and Efficient Programming Algorithms in Computer Education'', ACM SIGCSE Bulletin,
32(4):66-69, December 2000.

\bibitem{cc2001:curricula} \emph{Computing Curricula 2001 Computer Science,
Final Report}, The Joint Task Force on Computing Curricula, IEEE Computer Society and
Association for Computing Machinery, IEEE Computer Society, December 2001.

\bibitem{thinking:eisenberg} Eisenberg, Murray, and Peelle, Howard,
``APL Thinking: Examples'', ACM SIGAPL, Proceedings of the International Conference:
APL in Transition, 17(4):433-440, January 1987.

\bibitem{thinking:peelle} Eisenberg, Murray, and Peelle, Howard,
``A Survey: APL Thinking'', ACM SIGAPL Quote Quad, 21(2):5-8, December 1990.

\bibitem{hui:dict} Hui, Roger K. W., Iverson, Kenneth E.,
\emph{J Dictionary}, J Software, Toronto, Canada, May 2001.

\bibitem{thinking:metzger} Metzger, Robert, ``APL thinking finding
array-oriented solutions'', ACM SIGAPL, Proceedings of the International Conference
on APL, 12(1):212-218, September 1981.

\bibitem{array:matroid} Stallmann, Matthias F. M., ``A One-way Array Algorithm
for Matroid Scheduling'', Proceedings of the third annual ACM symposium on Parallel
Algorithms and Architectures, Pages: 349-356, Hilton Head, South Carolina, 1991.

\bibitem{sutherland:pclip} Sutherland, Ivan and Hodgman, Gary, ``Re-entrant
Polygon Clipping'', Communications of the ACM, 17(1):32-42, January 1974.

\bibitem{array:aggregates} Zhao, Yihong, Deshpande, Prasad, Naughton, Jeffrey,
``An Array-based Algorithm for Simultaneous Multidimensional Aggregates'',
Proceedings of the 1997 ACM SIGMOD International Conference on Management of Data,
Pages: 159-170, Tucson, Arizona, 1997.

\end{thebibliography}
\end{document}
