This paper introduces a new approach to compiling array algorithms in
functional languages. We are specifically aiming at an efficient
implementation of irregular array algorithms that are hard to implement in
conventional array languages such as Fortran. We optimise the storage
layout of arrays containing complex data structures and reduce the runtime
of functions operating on these arrays by means of equational program
transformations. In particular, this paper discusses a novel form of
combinator loop fusion, which by removing intermediate structures optimises
the use of the memory hierarchy.
We identify a combinator named loopP that provides a general scheme for
iterating over an array and that in conjunction with an array constructor
replicateP is sufficient to express a wide range of array algorithms.
On this basis, we define equational transformation rules that combine
traversals of loopP and replicateP as well as sequences of
applications of loopP into a single loopP traversal.
Our approach naturally generalises to a parallel implementation and includes
facilities for optimising load balancing and communication. A prototype
implementation based on the rewrite rule pragma of the Glasgow Haskell
Compiler is significantly faster than standard Haskell arrays and approaches
the speed of hand coded C for simple examples.
