Parallel Functional Programming with Arrays

We present an algebraic theory of arrays for data-parallel functionalprogramming. Non-nested arrays simplify the mapping problem toregular architectures, avoid nested list representations and prevent theoccurrence of an explosive number of algebraic laws. The MOA formal-ism describes arrays in a dimension-independent algebra. A new styleof functional programming is described with MOA operators, allowingrecursion equations to describe the meaning as well as the structure ofalgorithms for mesh- or hypercube-connected multiprocessors. 1 Introduction In a recent study, Marino and Succi [19] have enumerated requirements foruseful parallel data structures. Data structures should:match existing and future computer architectures;allow for ecient parallel implementations;be formally de ned in an applicative language;allow the de nition of complex objects in a constructive way. Work supported by an NSERC operating granty G. Hains, Universite de Montreal, Informatique et Recherche Operationnelle, casepostale 6128,succursale A, Montreal, Quebec, Canada H3C 3J7, hains@iro.umontreal.ca. L.M.R.Mullin, Computer Science and Electrical Engineering, University of Vermont, Burlington,Vermont, 05405 USA lenore@newton.uvm.edu