*Parallel
Processing Letters* **12**(2), pp 249-266, 2002.
(This article is a revised version of a paper presented at the 3rd International Workshop on
Constructive Methods for Parallel Programming (CMPP 2002).)

**Abstract**

We discuss a language-based cost model for array programs build on the
notions of work complexity and parallel depth. The programs operate over
data structures comprising nested arrays and recursive product-sum types.
In a purely functional setting, such programs can be implemented by way of
the *flattening transformation* that converts codes over nested arrays
into vectorised code over flat arrays. Flat arrays lend themselves to a
particularly efficient implementation on standard hardware, but the overall
efficiency of the approach depends on the flattening transformation
preserving the asymptotic complexity of the nested array code. Blelloch has
characterised a class of first-order array programs, called
*contained*
programs, for which flattening preserves the asymptotic depth complexity.
However, his result is restricted to programs processing only arrays and
tuples. In the present paper, we extend Blelloch's result to array programs
processing data structures containing arrays as well as arbitrary recursive
product-sum types. Moreover, we replace the notion of containment by the
more general concept of *fold* programs.

The original article:
doi:10.1142/S0129626402000951

Pre-print PostScript version (18 pages)

This page is part of Manuel Chakravarty's WWW-stuff.