<figure><img src="image_1.png" /></figure>

HAL
open science

ARRAY DOMAINS

Gaétan Hains, John Mullins

► To cite this version:

Gaétan Hains, John Mullins. ARRAY DOMAINS. 1994. hal-05037973

HAL Id: hal-05037973

https://hal.science/hal-05037973v1

Preprint submitted on 17 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
ARRAY DOMAINS *

GAÉTAN HAINS AND JOHN MULLINS †

**Abstract.** An order-theoretic definition of multi-dimensional arrays is presented. The notion of nested arrays is related to the reflexivity of array domains. Useful families of continuous transformations are defined and found to contain a common generalisation of the transpose and indexing transforms. Array domains provide a denotational framework for the recursive definition of array operations and their parallel implementation. Another outcome of this formalism is the definition of a criterion for selecting data-parallel language primitives: continuous array transforms whose *localisation* is efficient.

**Key Words.** Semantic domains, multi-dimensional arrays, data-parallel functional programming.

# 1. Introduction.
Arrays have been an important data structure for a very long time, especially in scientific computing. They are central to languages like Fortran, APL, and more recently Nial [1] and J [11]. With massively parallel architectures, their importance is growing as they become the principal vehicle for expressing data geometry in a form usable by the parallel system for resource-allocation. A new role for arrays in recent data-parallel languages such as Fortran 90 [14] and High Performance Fortran (HPF) [7] is to support the expression of constraints on the complex and machine-dependent resource allocation problem.

There is an ongoing effort in several research groups to integrate arrays in func-
tional languages, but to our knowledge their denotational semantics has not been
studied for its own sake. As a result there is confusion about which array constructors
and operators should be part of a functional parallel language. We do not pretend to
solve this difficult question, but rather to improve the theoretical tools for its study.

Most language designers seem to take one of the following attitudes:

* *Arrays are just computable functions.* In this case they have no specific meaning or implementation.

* *Arrays are sets of mutable variables.* Here they are often statically allocated, which ensures physical locality of contiguous elements, but have no specific meaning as collections.

* *Arrays are a non-elementary data type.* Where they may have a specific implementation through libraries, or above other data types but because of this, the correspondence between indices and memory locations is weak. Their meaning is however clearly defined as a specific data type.

Our approach is inspired by the first two: *arrays are functions whose domains are initial rectangles in a fixed index space*. The correspondence with physical memory will thus be strong and we compensate the lack of an abstract data type by the integration of arrays into semantic domains. We will define a notion of continuity close to functional continuity but specific to array operators, and show that it supports the specification of data-parallelism. This work may lead to systematic design methods for data-parallel languages and libraries.

<footnote>* Work supported by grants from NSERC and FCAR.</footnote>

<footnote>† G. Hains, Département d'informatique et recherche opérationnelle, Université de Montréal, Montréal, Québec, H3C 3J7, Canada, hains@iro.umontreal.ca, and J. Mullins, Département d'informatique, Université d'Ottawa, Ottawa, Ontario, K1N 6N5, Canada, mullins@csi.uottawa.ca</footnote>
The fixpoint method has been applied by Banger ([2] and chapter 12 of [19]) who has found several *categorical data types* (CDTs) for arrays, each one home to a useful class of array functions. CDTs have very clear advantages with respect to software engineering but each one is by design limited in the communication patterns it describes. Array domains relax this constraint at the cost of losing the algebraic properties of CDTs (such as universality). The CDT construction takes fixpoints of polynomial functors, and as a result of our function-space (exponential) definitions it is not immediately applicable to arrays as they are defined here. The two approaches are thus complementary and their integration should yield useful methods.

The sequence of topics discussed below loosely follows that of Gunter and Scott's survey [8]. Some of our proofs could have been written more abstractly, but elementary arguments are given almost everywhere for the sake of clarity. The article may be read without an advanced knowledge of domain theory and is mostly self-contained.

**2. Indices.** A commonly accepted definition of an array is a map whose domain is a finite cartesian product of basic finite domains. The elements of its domain are called *indices*. Most often the basic domains are totally ordered so that the array corresponds to a rectangular box in $\mathbb{N}^n$. Array domains build on this view with the provision of having infinite arrays and arrays of infinite dimension as limits.

**2.1. Definitions.** The following definitions of domain theory will be needed. They which can be found in [8]. A subset of a poset is *directed* if any pair of its elements has an upper bound in the set. A poset which has a least element $\perp$ is *complete* (is a *cpo*) if every directed subset of it has a least upper bound (or *supremum*). An element $x$ of a cpo is *compact* if whenever a directed set $M$ covers $x$ ($\bigvee M \ge x$) then $M$ contains an upper bound for $x$. $K(D)$ will denote the set of compacts in a cpo $D$. A cpo $D$ is *algebraic* if for any $x \in D$, the compact lower bounds of $x$ constitute a directed set whose supremum is $x$ ($x$ is generated by its compact lower bounds). A *domain* is an algebraic cpo with countably many compacts.

The set of *indices* is $I = \bar{\omega}^\omega$ where $\bar{\omega} = \{0 < 1 < 2 < \dots < \omega\}$, $\omega$ is $\bar{\omega} - \{\omega\}$ and $\omega_+$ is $\omega - \{0\}$. The *dimension* of an index $\vec{i} \in I$ is

$$ \dim \vec{i} = \max\{n \in \omega \mid \vec{i}(n) > 0\} + 1 $$

and by convention $\dim 0^\omega = 1$. An index of finite dimension corresponds to a word $\alpha$ on $\bar{\omega}$ followed by $0^\omega$. We will write $\alpha$ instead of $\alpha 0^\omega$ in that case. For example $310^\omega$ has dimension 2 and is written $31$ while $1^\omega$ has dimension $\omega$. An index $\vec{i}$ of dimension $n$ represents a point in the positive quadrant of $\mathbb{Z}^n$, and a point in every array of dimension at least $n$ whose $n$ first axes are not shorter than $\vec{i}$. This illustrates two properties of indices and of our forthcoming definition of arrays:

1. Choice of $\omega$ instead of the $\mathbb{Z}$ of the theory of systolic arrays [18]. Translations are in our opinion, external to a theory of arrays. Our arrays will all have the same origin. Negative lengths are thus not required. Moreover, this theory does not aim (for the moment) at applications of linear algebra but of domain theory. It therefore begins from a poset and not a ring.

2. Unlimited dimensions. We avoid to fix in advance the dimension of arrays (as when finite-dimensional linear algebra is the theoretical background). The index 31 thus represents both a point in $\mathbb{Z}^2$ and the point $310^n$ in $\mathbb{Z}^{n+2}$. This has the following operational consequence: the embedding of 31 in a
5-dimensional space has no “cost”, contrarily to what would happen if our indices were (finite) words. Each index would then reside in a space of fixed dimension: the set of indices of its length. In the index poset, one may move from 31 to 31001 “in one step”, since 31 = 31000 and not in four as in:

$$31 \to 310 \to 3100 \to 31000 \to 31001.$$

Indices are ordered pointwise:

$$\vec{i} \le \vec{i}' \text{ if } \forall n \in \omega, \vec{i}(n) \le \vec{i}'(n)$$

and not lexicographically. It follows that $(I, \leq)$ is a poset where $\perp = 0^\omega$, and for example $01 < 11 < 111$. Note that indices will not be considered as continuous functions $\omega \to \bar{\omega}$, although $\bar{\omega}$ is a complete partial order (cpo). Such a definition would require a value at infinity for each $\vec{i}$, a meaningless concept for arrays: it is useful to let the number of dimensions be unlimited but not to have an “axis at infinity”. On the other hand, infinite arrays are the result of infinite computations and it is natural to account for them.

**2.2. Domain structure.** This subsection is devoted to the key properties of $I$: it is a domain whose compacts are the indices at finite distance from the origin.

**LEMMA 2.1.** [product cpos, (theorem 4.7 in [13])] For $S$ a set and $O$ a cpo, the set $O^S$ of functions $S \to O$ ordered pointwise is a cpo.

Lemma 2.1 with $S = \omega$ and $O = \bar{\omega}$ shows that $I$ is a cpo. Other consequences of 2.1 will be used repeatedly in the rest of the article. They all follow from the fact that the order on $O^S$ is $\prod_{s \in S} \leq_O$ for arbitrary cpos $O, O'$ and a set $S$, and are given here without proof:

1. $M \subseteq O^S$ is directed if and only if all of its projections $M(s) = \{m(s) \mid m \in M.\}, s \in S$, are directed in $O$.

2. For $M \subseteq O^S$ directed and $s \in S$, $(\bigvee M)(s) = \bigvee(M(s))$: the supremum operator commutes with projection.

3. $f: O^S \to O'^S$ is monotone (resp. continuous) if and only if all of its projections $f_s: O \to O'$ are monotone (resp. continuous). Monotonicity and continuity are defined in section 5.

By definition, an index $\vec{i}$ is compact if, whenever $M$ is a directed set and $\vec{i} \le \bigvee M$ then $\exists \vec{j} \in M. \vec{i} \le \vec{j}$. But by the properties of product cpos this property is equivalent to the conjunction of all its projections; namely, $\vec{i}$ is compact if for all $n \in \omega$, any directed set in $\bar{\omega}$ which covers $\vec{i}(n)$ contains an upper bound $j$ for $\vec{i}(n)$. But in $\bar{\omega}$ this is only true when $\vec{i}(n) < \omega$. It therefore follows that compacts have compact (finite) values in $\bar{\omega}$ and have finite dimension as shown in the following lemma.

**LEMMA 2.2.** $\vec{i} \in K(I) \Rightarrow \vec{i} \in \omega^*.$

*Proof.* It must be shown that if $\exists n. \vec{i}(n) = \omega$ or if $\dim \vec{i} = \omega$ then $\vec{i}$ is not compact. Assume $\vec{i}(n) = \omega$ and let $M = \{\vec{j}_k \mid k \in \omega\}$ where $\vec{j}_k = k^\omega$. Then $M$ is directed and $\bigvee M = \omega^\omega$ so $\vec{i}$ is bounded above by $\bigvee M$. However for every $k$, $\vec{i}(n) = \omega > \vec{j}_k(n)$ so $\vec{i} \not\le \vec{j}_k$. Therefore $\vec{i}$ is not compact.

Secondly, let $\dim i = \omega$ and let $M = \{\vec{j}_k \mid k \in \omega\}$ where $\vec{j}_k = (\vec{i}(0)+1) \dots (\vec{i}(k)+1)$. Then $M$ is directed and for all $n$, $\bigvee M(n) = \vec{i}(n) + 1$ so $\vec{i} \le \bigvee M$. However

$$\forall \vec{j}_k \in M. \exists n > k. \vec{i}(n) \ge 1$$
since $\vec{i}$ has infinite dimension. It follows that

$$ \forall \vec{j}_k \in M. \exists n. \vec{j}_k(n) = 0 < 1 \le \vec{i}(n) $$

and so $\vec{i} \le \vec{j}_k$. □

The converse is also true: indices with finite values and finite dimension are compact. This result is a special case of the well-known fact that the compacts of a function space are the finite functions with compact values.

**PROPOSITION 2.3.** $K(I) = \omega^*$

*Proof.* By the lemma, it is sufficient to prove that all $\vec{i} \in \omega^*$ are compact. So let $M \subseteq I$ be directed, $\vec{i} = i_0i_1...i_n \in \omega^*$ and $\vec{i} \le \bigvee M$. Then considering the $k$th projection of $\vec{i}$ and of $M$, for $k \le n$, $i_k$ is a compact of $\bar{\omega}$ and therefore $\exists \vec{j}_k \in M. i_k \le \vec{j}_k(k)$. But $M$, being directed, is closed for finite suprema so $\vec{j} = \bigvee_{k=0}^n \vec{j}_k \in M$ and by construction $\vec{i} \le \vec{j}$. □

It remains to verify that the compacts generate all of $I$.

**PROPOSITION 2.4.** *I is a domain.*

*Proof.* First of all $K(I) = \omega^*$, so the compacts are denumerable. It remains to prove that $I$ is algebraic. Namely, that for all $\vec{i} \in I$, $M_{\vec{i}} = \{\vec{j} \in K(I) | \vec{j} \le \vec{i}\}$ is directed and $\vec{i} = \bigvee M_{\vec{i}}$.

Let then $\vec{i} \in I$ and $M_{\vec{i}} = \{\vec{j} \in \omega^* | \vec{j} \le \vec{i}\}$. Any finite part of $M_{\vec{i}}$ is also a finite part $\{\vec{j}_0, ..., \vec{j}_r\}$ of $\omega^n$ for $n = \max_{k \le r} \dim \vec{j}_k$ (by adding trailing strings of 0s where necessary). By definition,

$$ \forall m \le n. \forall k \le r. \vec{j}_k(m) \le \vec{i}(m) $$

and therefore $\forall m \le n. \bigvee_{k=0}^r j_k(m) \le \vec{i}(m)$. It follows that the index

$$ \vec{j} = (\bigvee_{k \le r} j_k(0)) (\bigvee_{k \le r} j_k(1)) \dots (\bigvee_{k \le r} j_k(n)) $$

is a lower bound for $\vec{i}$, and moreover $\vec{j}$ is a compact (finite-dimensional with finite values). Since $\vec{j}$ is an upper bound for $\{\vec{j}_0, ..., \vec{j}_r\}$ and since $\vec{j} \in M_{\vec{i}}$ we conclude that $M_{\vec{i}}$ is directed.

Next, the proof that $\bigvee M_{\vec{i}} = \vec{i}$. Let $n \in \omega$ be arbitrary.

$$ \begin{aligned} \bigvee M_{\vec{i}}(n) &= \bigvee \{\vec{j}(n) \mid \vec{j} \in \omega^* \wedge \vec{j} \le \vec{i}\} \\ &= \bigvee \{\vec{j}(n) \mid \vec{j} \in \omega^*, \wedge \forall r \in \operatorname{dom} \vec{j}. \vec{j}(r) \le \vec{i}(r) \wedge \vec{j}(r) < \omega\} \\ &= \bigvee \{\vec{j}(n) \mid \vec{j} \in \omega^*, \wedge \forall r \in \operatorname{dom} \vec{i}. \vec{j}(r) \le \vec{i}(r) \wedge \vec{j}(r) < \omega\} \\ &= \bigvee \{m \mid m \le \vec{i}(n) \wedge m < \omega\} \quad \text{because } \forall m. \exists \vec{j}. m = \vec{j}(n). \\ &= \bigvee \{m \mid m \le \vec{i}(n)\} \quad \text{because } \bar{\omega} \text{ is complete.} \\ &= \vec{i}(n). \end{aligned} $$

<figure><img src="image_2.png" /></figure>

□

The fact that $I$ is a domain will improve the expressive power of recursive definitions on arrays.

**2.3. Rectangles.** An *ideal* in a poset is a non-empty set $S$ which is directed and downward closed:

$$ 1. x, y \in S \Rightarrow \exists z \in S. z \ge x, z \ge y $$
<figure><img src="image_3.png" /><figcaption>FIG. 1. The principal ideal $\langle 321 \rangle$ in $I$.</figcaption></figure>

$$2. x \in S \Rightarrow \langle x \rangle = \{x' | x' \le x\} \subseteq S.$$

It is *principal*, generated by the element $x$ if it is itself of the form $\langle x \rangle$. The ideals of a cpo are not always principal. For example, the subset $\omega$ is an ideal in $\bar{\omega}$ but is not $\langle \omega \rangle$ (the principal ideal generated by the top element) which equals all of $\bar{\omega}$. Since we are interested in the initial rectangles of $I$, and will consider the principal ideals $\langle \vec{i} \rangle$ in $I$. Figure 1 illustrates one of them. Not all ideals are finite sets or have finite dimension. For example:

$$\langle \omega \rangle = \langle \omega 0^\omega \rangle = \{n 0^\omega | n \in \omega\}$$

is infinite and

$$\langle 1^\omega \rangle = \{\vec{i} \in I | \forall n. \vec{i}(n) \in \{0, 1\}\}$$

contains indices of all dimensions. Every ideal in $I$ has a supremum (by definition it is directed and $I$ is a domain), and those which contain their supremum are the principal ideals or initial rectangles.

The set of principal ideals of $I$, ordered by inclusion is isomorphic to $(I, \le)$ through the obvious correspondence. The union of ideals corresponds to the supremum of generators. The top ideal $I$ is $\langle \omega^\omega \rangle$ and the bottom $\{0\}$ is $\langle 0 \rangle$.

### 3. Arrays.

**3.1. Definitions.** Let $D$ be a domain. The set of *arrays* with elements from $D$ is

$$D^{\square} = \{t : I \to D \mid \exists \vec{i} \in I. t^{-1}(D - \{\perp\}) = \langle \vec{i} \rangle \text{ or } t = \perp^I\}$$

where $\perp^I$ is the constant function of value $\perp_D$. In other words, an array is a partial function whose domain is either empty or is a principal ideal. For $t \in D^{\square}$, we write

$$\mathrm{dom} \ t = t^{-1}(D - \{\perp\})$$
so $\mathrm{dom} \perp^I = \emptyset$ and $\mathrm{dom} t = \langle \vec{i} \rangle = \langle \vee \mathrm{dom} t \rangle$ otherwise. The shape of array $t$, which we write $\rho t$ for historical reasons, is the index whose entries are the lengths of $t$'s domain along each axis:

$$ \rho t = \vec{\rho} \in I \\ \text{where } \vec{\rho}(n) = \begin{cases} \vec{i}(n) + 1, & \forall n \in \mathrm{dom} \vec{i} \\ \vec{i}(n) & \text{elsewhere} \end{cases} $$

where, by convention $\omega + 1 = \omega$ and $\rho \perp^I = 0 = \perp_I$. For example the domain of an array of shape 432 is the ideal $\langle 321 \rangle$. The dimension of an array is that of its shape:

$$ \dim t = \dim(\rho t) = \dim \vee \mathrm{dom} t. $$

A finite array is one whose shape is a compact, i.e. such that

$$ \dim t < \omega \text{ and } \forall n. (\rho t)n < \omega. $$

Like indices, arrays are ordered pointwise:

$$ t \le t' \text{ iff } \forall \vec{i} \in I. t \vec{i} \le t' \vec{i}. $$

As in all array formalisms, shapes carry some of the structure.

**PROPOSITION 3.1.** $t \le t' \Rightarrow \mathrm{dom} t \subseteq \mathrm{dom} t'$.

*Proof.* By contradiction. Let $\vec{i} \in \mathrm{dom} t - \mathrm{dom} t'$. Then by definition $\vec{i} \neq \perp$ and $t' \vec{i} = \perp$. Therefore $t' \vec{i} > t' \vec{i}$ and so $t' \vec{i} \not\le t' \vec{i}$. □

**COROLLARY 3.2.**

$$ t \le t' \Rightarrow \rho t \le \rho t'. $$

The shape operation $\rho: D^\square \to I$ is thus a cpo homomorphism (or monotone function) from arrays to indices. It is not an isomorphism: it is not injective, and because indices with intermediate 0 values like 502 are not in its image, it is not surjective either.

There is an equally simple but useful projection property. Let $\vec{i} \in I$ be fixed. Then

$$ (1) \qquad \forall t, t' \in D^\square. t \le t' \Rightarrow t \vec{i} \le t' \vec{i}. $$

So the $\vec{i}$-projection of $D^\square$ is monotone. Let us now make two remarks about $D^\square$. *Continuity*.

As with indices, the continuity of arrays as functions is of no interest (in fact they are not increasing and so can't be continuous). They are defined from a domain to another domain, but only treated as functions from a set to a domain.

*Content lists.*

In [10] finite arrays were defined as a subset of $I \times D^*$. The first element of a pair was the shape, and the second a content list. To follow convention, the content list was in lexicographic order, which had the disadvantage of inducing unnatural definitions for objects like the diagonal or a matrix. In the domain-theoretic approach, arrays may be infinite along any dimension, so the meaning of a content list would depend on a generalised diagonal scan (like the usual encoding of $\omega^2$ into $\omega$, generalised to $\omega^*)$ instead of lexicographic ordering. Such an encoding is generalised by the order on $I$.
**3.2. Completeness.** The following result is the preservation of cpos by array construction.

**PROPOSITION 3.3.** If $D$ is a cpo then so is $D^\square$.

*Proof.* By lemma 2.1, $D^I$ is a cpo and therefore $D^\square$ is a poset: a sub-poset of $D^I$. However the supremum of two arrays is not their supremum as functions, which might not be rectangular. The bottom element of $D^\square$ is the empty array $\perp^I$. To show completeness, let $T$ be a directed set of arrays. By the completeness of $D^I$, there is a supremum $\bigvee T \in D^I$ and $\bigvee T\vec{i} = \bigvee \{t\vec{i} | t \in T\}$ for all $\vec{i}$. We must show that $\bigvee T$ is an array. Let us consider its null values.

$$ \begin{align*} \bigvee T\vec{i} = \perp &\iff \bigvee \{t\vec{i} | t \in T\} = \perp \\ &\iff \forall t \in T. t\vec{i} = \perp \\ &\iff \forall t \in T. \vec{i} \notin \text{dom } t. \end{align*} $$

and so

$$ \bigvee T\vec{i} \neq \perp \iff \exists t \in T. \vec{i} \in \text{dom } t $$

i.e. $\text{dom } \bigvee T = \bigcup_{t \in T} \text{dom } t$. But all $t$ are arrays, and because of the isomorphism between $I$ and principal ideals, the union of domains corresponds to a union in $I$. Since $I$ is complete, it follows that the union is also a principal ideal. Moreover

$$ (2) \qquad \rho \bigvee T = \bigvee_{t \in T} \rho t. $$

<figure><img src="image_4.png" /></figure>

**3.3. Algebraicity.** As can be expected from a similar result on function spaces, the compact arrays are those with finite shapes (domains) and compact values.

**PROPOSITION 3.4.** $K(D^\square) = \{t : I \to K(D) \mid \rho t \in \omega^*\}$.

*Proof.* First prove the inclusion $\supseteq$.

Let $t_0$ be such that $\text{dom } t_0 = \langle i_1 \dots i_d \rangle$, all $i_j$ are finite and all $t_0\vec{i}$ are compact. Let $T$ be a directed set of arrays over $D$, and $t_0 \le \bigvee T$. It must be shown that $\exists t' \in T. t_0 \le t'$. Consider a fixed $\vec{i}_0$ in the domain of $t_0$. Then $\{t\vec{i}_0 | t \in T\}$ is directed as a consequence of equation 1 and since values come from a domain it follows that $\exists d \in \{t\vec{i}_0 | t \in T\}$. $t_0\vec{i}_0 \le d$, i.e. $\exists t_{\vec{i}_0} \in T. t_0\vec{i}_0 \le t_{\vec{i}_0}$. The set of all $t_{\vec{i}}$ is a finite subset of $T$, and since $T$ is directed there is an upper bound for it in $T$:

$$ \exists t' \in T. \forall \vec{i} \in \text{dom } t_0. t_{\vec{i}}\vec{i} \le t'\vec{i}. $$

This holds for every $\vec{i}$ in the domain of $t_0$, so

$$ \forall \vec{i} \in \text{dom } t_0. t_0\vec{i} \le t_{\vec{i}}\vec{i} \le t'\vec{i}. $$

It follows directly that $t_0 \le t' \in T$, which proves $t \in K(D^\square)$.

Conversely, let $t \in K(D^\square)$. It must be shown that its values and shape are compact. The compact shapes are $K(I) = \omega^*$. If $\rho t \notin K(I)$ then there exists a directed family of shapes which has $\rho t$ as supremum but none of which is an upper bound for $\rho t$. Equivalently, there is a directed family of rectangular sets which has $\text{dom } t$ as union but none of which contains $\text{dom } t$. Restricting $t$ to these domains yields a directed family of arrays which have $t$ as supremum ($t$ restricted to its own
domain) but none of which is an upper bound for $t$ (upper bounds have also shapes which are upper bounds): contradicting the fact that $t$ is compact.

Secondly, let us assume that $t$ has a non-compact value for a certain $\vec{i} \in \text{dom } t$. Then there must exist a directed set $M \subseteq D$ which has $t\vec{i}$ as supremum but such that no $d \in M$ is an upper bound for $t\vec{i}$. Substituting each $d$ in $t$ at position $\vec{i}$ yields $\{t[\vec{i} := d] | d \in M\}$ a directed set in $D^\square$, whose supremum is $t = t[\vec{i} := t\vec{i}]$ but which does not contain an upper bound for $t$ (upper bounds have upper bounds as values for every index). Again, this contradicts the fact that $t$ is compact. □

The most important property of the array construction is that it preserves domains.

**THEOREM 3.5.** If $D$ is a domain then so is $D^\square$.

*Proof.* By proposition 3.3 it is sufficient to prove that the compact arrays are countable and that $D^\square$ is algebraic.

1. By 3.4, the set of compact arrays is $\{t : I \to K(D) | \rho t \in \omega^*\}$. Since $D$ is a domain, its compacts are countable. For any $\vec{\rho} \in \omega^*$, the corresponding ideal $\langle t_{\vec{\rho}} \rangle$ is finite and so the compact arrays whose shape is $\vec{\rho}$ are in bijection with a finite cartesian product of the countable set $K(D)$. It follows that the compact arrays of shape $\vec{\rho}$ are countable. Since $\omega^*$ is countable, the whole set of compact arrays is therefore in bijection with a countable list of countable sets. It is therefore countable.

2. For every array $t$, the set $\{t' \in K(D^\square) | t' \le t\}$ is directed and has $t$ as supremum.

(a) Let $t', t'' \in K(D^\square)$ and $t', t'' \le t$. Consider any index $\vec{i}$ in $\text{dom } t' \cap \text{dom } t''$. Then $t'\vec{i}$ and $t''\vec{i}$ are two compacts of $D$, both lower bounds of $t\vec{i}$. Because $D$ is algebraic, the set of compact lower bounds of $t\vec{i}$ is directed so there exists a compact value $d_\vec{i}$ such that

$$t'\vec{i} \le d_\vec{i} \le t\vec{i} \quad \wedge \quad t''\vec{i} \le d_\vec{i} \le t\vec{i}$$

Define now $t'''$ an array of compact shape $\rho t''' = \rho t' \lor \rho t''$. Over $\text{dom } t' \cap \text{dom } t''$ let $t'''\vec{i} = d_\vec{i}$, over $\text{dom } t' - \text{dom } t''$ let $t''' = t'$ and symmetrically for $\text{dom } t'' - \text{dom } t'$. Over $\text{dom } t - (\text{dom } t' \cup \text{dom } t'')$ let the value of $t'''\vec{i}$ be any<fnref n="1" /> element of $\{d \in K(D) | \perp < d \le t(\vec{i})\}$. By construction $t'''$ is compact, is a lower bound for $t$ and an upper bound for both $t'$ and $t''$. Figure 2 illustrates this part of the proof.

(b) The set $T = \{t' \in K(D^\square) | t' \le t\}$ has $t$ as supremum if and only if this property is satisfied by the $\vec{i}$-th projection for every $\vec{i}$. When $\vec{i} \notin \text{dom } t$, all $t' \in T$ must satisfy $t'\vec{i} = \perp$, so $\bigvee T(\vec{i}) = \perp$. When $\vec{i} \in \text{dom } t$, the $\vec{i}$-th projection $T\vec{i}$ of $T$ is the set of compact lower bounds for $t\vec{i}$ (a consequence of the elementary of properties of product posets). Since $D$ is algebraic, it follows that $T\vec{i}$ is directed and has $t\vec{i}$ for its supremum: $\bigvee(T\vec{i}) = t\vec{i}$. We have shown that $(\bigvee T)\vec{i} = t\vec{i}$ for all $\vec{i}$, and conclude that $\bigvee T = t$.

<figure><img src="image_5.png" /></figure>

□

The concepts defined so far allow the recursive definition of functions on arrays (because $D^\square$ is a cpo) and reasoning about the computability of those functions (because $D^\square$ is a domain). The first step in that direction will be the study of continuous

<footnote n="1">¹ This proof is not constructive but could be made so, given a construction of the compacts of $D$.</footnote>
<figure><img src="image_6.png" /><figcaption>FIG. 2. Construction of a larger compact lower bound $t'''$ from two compact lower bounds $t'$ and $t''$.</figcaption></figure>

functions on $D^\square$ (section 5). Section 8 will also lay the foundations for the study of parallel evaluation of array functions.

**4. Nested arrays and recursively defined domains.** The treatment of nested data structures, and particularly nested arrays, is a central issue for researchers interested in data-parallel programming. In his trend-setting book [5] Blelloch devotes one third of his theoretical discussion of “languages and compilers” to “flattening nested parallelism”. As data structures are used to trigger parallel evaluation or process creation, nesting places contradictory requirements on data-parallel languages. Namely, programmers desire nested structures to represent more complex objects, while the placement problem is easier to solve in the absence of nesting which causes process creation and weakens the effectiveness of global allocation strategies.

Flat data-parallel languages like Reform Prolog [3] and data-parallel ML [9] prohibit nested process creation and so favour portability and efficiency at the expense of expressibility. At the other extreme are CMLisp [20] — based on arbitrarily nested finite maps or xappings —, More’s array theory [15, 16] and Jenkin’s programming language Nial [1] — both based on arbitrarily nested arrays —. As an intermediate solution, Banger’s construction of arrays as a categorical data type [2] takes a more structured view of nested arrays: each nesting depth delimits a new type.

The present construction of $D^\square$ is motivated by the need to specify arrays, recursively or not, without having to define the multidimensional ones as nested one-dimensional arrays (as in the work of Jeuring [12] for example). Its main practical advantage is the coverage of a wider family of “good” functions based on spatially uniform recurrences. So-called wavefront data dependencies occur in continuous functions on $D^\square$ but are not morphisms on Jeuring’s or Banger’s arrays. This flexibility comes at a cost: we allow infinite arrays which are not limits of finite ones. For example any map $I \to (D - \{\perp\})$ is an array of domain $\langle\omega^\omega\rangle$. As a result, as soon as the base set $D$ contains two elements, $D^\square$ is uncountable. There is therefore no hope of solving a domain equation like

$$X \cong X^\square + E.$$

As a result, there is no domain containing all finitely nested arrays. It may be possible
<figure><img src="image_7.png" /><figcaption>FIG. 3. A continuous function $f: D^{\square} \to E^{\square}$</figcaption></figure>

to restrict $D^{\square}$ to contain only countably many infinite arrays (when $D$ is countable) but the present definition is simpler, and the rest of the article is limited to flat arrays.

**5. Continuous array functions.** Let $D$ and $E$ be two domains. A monotone or increasing function $f: D \to E$ is one such that $x \le y \Rightarrow fx \le fy$. We will call $f$ total if $x > \perp \Rightarrow fx > \perp$. A continuous function (figure 3) $f \in [A \to B]$ is a monotone function such that for any directed $M \subseteq D$, $f \vee M = \vee fM$.

**5.1. Pointwise extensions.** The embedding of $D$ into $D^{\square}$ is the strict, continuous and injective function $\iota_D: D \to D^{\square}$ which sends $d$ to $\{0 \mapsto d\}$. For $f: D \to E$ the pointwise extension of $f$ is the function

$$f^*: D^I \to E^I: t \mapsto f \circ t$$

It is easily verified that $f^* \circ \iota_D = \iota_E \circ f$.

**LEMMA 5.1.** Given two domains $D, E$ and $f: D \to E$, $f^* \in [D^{\square} \to E^{\square}]$ if and only if

1. $f$ is continuous and

2. $f$ is total or $f$ is the constant $\perp$ function $K_{\perp}$.

*Proof.* If $f$ is not continuous, then there is a directed set in $D$ whose limit does not commute with $f$. Injecting this directed with $\iota_D$ yields a directed set in $D^{\square}$, whose limit does not commute with $f^*$, which is thus shown to be discontinuous.

If $f$ is not total, then there is a $d \in D - \{\perp\}$ such that $fd = \perp$. Assuming $f \neq K_{\perp}$, there is also a $d' \in D$ such that $fd' \neq \perp$. Constructing the array $t = \{0 \mapsto d, 1 \mapsto d'\}$, it follows that $f^*t = \{0 \mapsto \perp, 1 \mapsto fd' > \perp\}$ is not an array. This shows that $f^*$ is not an array function when the second condition is false.

Assume now that $f^* \in [D^{\square} \to E^{\square}]$ and that $D_0 \subseteq D$ is directed. Then $f$'s
continuity may be verified as follows:

$$
\begin{align*}
& f^* \iota_D \bigvee_{d \in D_0} d = f^* \bigvee_{d \in D_0} \iota_D d \quad (\iota \text{ is continuous}) \\
\iff & f^* \iota \bigvee d = \bigvee f^* \iota d \quad (f \text{ is continuous}) \\
\iff & f^* \iota \bigvee d = \bigvee \iota(fd) \quad (f^* \iota = \iota f) \\
\iff & f^* \iota \bigvee d = \iota \bigvee (fd) \quad (\iota \text{ is continuous}) \\
\iff & \iota(f \bigvee d) = \iota \bigvee (fd) \quad (f^* \iota = \iota f) \\
\iff & f \bigvee d = \bigvee (fd) \quad (\iota \text{ is injective.})
\end{align*}
$$

Secondly, if $f$ is not total and does not equal $K_\perp$ then, as was done above, an array
could be constructed whose value by $f^*$ is not an array. It follows that $f$ is either
constant null or total. □

From now on the mention of $f^*$ will implicitly mean that $f$ is continuous and total.
Pointwise extensions constitute the *simplest* continuous array functions but they are
not characterised as *universal* since the construction of $D^\square$ is not algebraic.

**5.2. Algorithms and parallelism.** Let us temporarily consider the limit $\bigvee_{n \in \omega} f^n \perp$
as a sequential algorithm for computing the least fixed point **fix** *f* of *f* ∈ [*D* → *D*].
There is an obvious “data-parallel” algorithm $\bigvee_{n \in \omega} f^{*n} \perp I$ for computing **fix** *f*^* in
*D*^*. It is data-parallel in the sense that its evaluation can be viewed either as a se-
quence of parallel applications of *f*^* (global or macroscopic view) or an array (indexed
by *I*) filled by copies of the above sequential algorithm (local or microscopic view).
By construction, $\rho(\mathbf{fix} \, f^*) \in \{0, \omega^\omega\}$ and so the fixpoint of a pointwise extension is
either empty or infinite with all of its entries equal.

Pointwise extensions clearly illustrate the relationship between parallel evaluation
and array domains. This aspect of our theory is what distinguishes it from most
algebraic descriptions of parallel data structures: it is less abstract but involves a
more concrete representation through the sharing of *I* by all arrays and all array
domains.

**5.3. Continuity and shapes.** Continuity has a continuous effect on shapes.
Every continuous $f \in [D^\square \to E^\square]$ determines a continuous function $f_\rho \in [D^\square \to I]$
defined by $f_\rho = \rho \circ f$.

PROPOSITION 5.2. If $f \in [D^\square \to E^\square]$ then $f_\rho$ is continuous.

*Proof.* It is sufficient to show that $\rho$ is continuous. This is true because dom
is continuous from $D^\square$ into the principal ideals of $I$. This last property is show as
follows.

If $t \subseteq D^\square$ is directed, then $\{ \text{dom } t \mid t \in T \}$ is also directed. Next, for any $\vec{i}$,
$(\bigvee_{t \in T} t) \vec{i} = \perp$ if and only if $\forall t \in T. \, t \vec{i} = \perp$. Therefore

$$
\begin{align*}
\{\vec{i} \mid \forall t \in T. \, t \vec{i} = \perp\} &= \{\vec{i} \mid (\bigvee_{t \in T} t) \vec{i} = \perp\} \\
\Rightarrow \quad \bigcap_{t \in T} (I - \text{dom } t) &= \{\vec{i} \mid (\bigvee_{t \in T} t) \vec{i} = \perp\} \\
\Rightarrow \quad I - \bigcup_{t \in T} \text{dom } t &= I - \text{dom } \bigvee_{t \in T} t \\
\Rightarrow \quad \bigcup_{t \in T} \text{dom } t &= \text{dom } \bigvee_{t \in T} t \\
\iff \quad \bigvee_{t \in T} \rho t &= \rho \bigvee_{t \in T} t.
\end{align*}
$$

<figure><img src="image_8.png" /></figure>

In particular $\rho = \text{Id}_\rho$ is continuous.
**5.4. Continuity on $D^I$.** A simple method for defining a continuous array transformation is to find a continuous transformation on $D^I$ and ensure that it preserves rectangular shapes.

**LEMMA 5.3.** Let $f$ be such that

H1: $f \in [D^I \to E^I]$ and

H2: $f(D^\square) \subseteq E^\square$.

Then $f \in [D^\square \to E^\square]$.

*Proof.* The monotonicity of $f$ on $D^I$ implies the same property on $D^\square$. Let also $T \subseteq D^\square$ be directed. Then $T$ is also directed in $D^I$ because $\leq_{D^\square} \subseteq \leq_{D^I}$. By H1, $f \vee T = \vee_{t \in T}(ft)$ and by completeness of $D^\square$ it also follows that $\vee T \in D^\square$. We conclude by H2 that $\vee T \in E^\square$ and by the definition of continuity $\vee ft \in E^\square$. □

Because $f \in [D^\square \to E^\square]$ may behave arbitrarily on $D^I - D^\square$, the converse property is false. However, given H1, $f \in [D^\square \to E^\square]$ is equivalent to H2.

**LEMMA 5.4.** *A continuous function transformation $f \in [D^I \to E^I]$ is a continuous array transformation if and only if it preserves arrays.*

*Proof.* It is already known that $f(D^\square) \subseteq E^\square$ implies $f \in [D^\square \to E^\square]$. By definition $f \in [D^\square \to E^\square]$ implies $f(D^\square) \subseteq E^\square$. □

The lemma is useful in defining continuous functions, because of the ease of verifying H1 independently of shapes (pointwise continuity is sufficient).

**6. More continuous functions.** The use of continuous array functions for parallel functional programming is motivated as follows:

1. Because $D^\square$ is a cpo, recursive programs yield unique and well-defined fixpoints.

2. Because $D^\square$ is algebraic, recursive definitions preserve computability under reasonable assumptions.

3. The geometry of $I$, hence of $D^\square$, places the communication structure of recursively-defined functions in the context of mesh-connected graphs.

This section introduces array functions which are known to be useful in array-based languages, and proves their continuity. Two facts will help simplify the otherwise ad-hoc proofs. Firstly, lemma 5.4. Secondly, as in any domain, it will be sufficient to define a continuous array function over its compacts [8]. The remainder of the section avoids quoting this explicitly.

**6.1. Indexing.** The indexing operator generalises the classical matrix indexing operation whereby $A[i, j]$ is a scalar and $A[i]$ is a row. The definition below is equivalent to that found in L.M.R.Mullin's *Mathematics of arrays* or MOA formalism. In MOA [17] all array functions are constructed from the indexing operator $\psi$ which accesses array parts, the encoding operator $\gamma$ which maps all indices less than a given shape to linear addresses in lexicographic order, and its inverse $\gamma'$.

The indexing operator is typed $\psi: \omega^* \to D^\square \to D^\square$ and for the purpose of its first argument, $\omega^*$ is understood as the set of finite words on $\omega$ (and not $K(I)$ where trailing 0s are discarded by convention). In other words $\psi 1 \neq \psi 10 \neq \psi 100$. As a consequence the length $|\vec{v}|$ of $\vec{v} \in \omega^*$ is well defined and so is the concatenation of $\vec{v}$ on the left of any $\vec{i} \in I$.

The value of $\psi \vec{v} t$ is defined as follows:

$$ (3) \qquad \psi \vec{v} t = \{ \vec{i} \mapsto t(\vec{v} \cdot \vec{i}) \mid \vec{i} \in I \} $$
where $\cdot$ denotes concatenation of indices. The effect of $\psi$ can be illustrated by the following example. Assume that figure 1 represents an identity array

$$t = \{\vec{i} \mapsto \vec{i} \mid \vec{i} \in \langle 321 \rangle\}.$$

Then $\psi 2t$ is by definition that subarray of $t$ whose values have 2 as prefix:

$$\psi 2t = \{0 \mapsto 2, 1 \mapsto 21, 2 \mapsto 22, 01 \mapsto 201, 11 \mapsto 211, 21 \mapsto 221\}.$$

It follows from (3) that $\psi \vec{v} t = \perp^I$ when $\vec{v} \notin \text{dom } t$ and also that $\psi$ is a (dual) concatenation morphism for its index argument:

**PROPOSITION 6.1.** $\psi(\vec{v} \cdot \vec{w}) = (\psi \vec{w}) \circ (\psi \vec{v})$.

It is also continuous on its array argument.

**PROPOSITION 6.2.** $\forall \vec{v} \in \omega^*$. $\psi \vec{v} \in [D^\square \to D^\square]$.

*Proof.* To verify that $\psi \vec{v} t$ is an array when $t \in D^\square$, i.e. H2, observe that

$$\text{dom}(\psi \vec{v} t) = \{\vec{i} \in I \mid \vec{v} \cdot \vec{i} \in \text{dom } t\} = \{\vec{i} \in I \mid \vec{v} \cdot \vec{i} \le \vec{i}_t\}$$

for a certain $\vec{i}_t$, i.e. the domain of $\psi \vec{v} t$ is a right-residue of $\text{dom } t$ by $\vec{v}$. Also, $\vec{i} \in \text{dom } (\psi \vec{v} t)$ if and only if $\vec{v} \le \vec{i}_t$ and $\vec{i} \le \vec{i}_t \setminus \vec{v}$, where $\setminus$ is the right residue (of concatenation). As a result the domain is a principal ideal. The shape of $\psi \vec{v} t$ is a final segment of $\rho t$:

$$\rho(\psi \vec{v} t) = \begin{cases} (\rho t | \vec{v}) \dots (\rho t (\dim t)) & \text{if } \vec{v} \in \text{dom } t \text{ (so that } |\vec{v}| \le \dim t) \\ 0 & \text{otherwise.} \end{cases}$$

It is easily verified from (3) that $\psi \vec{v}$ is monotone. To conclude that $\psi \vec{v} \in [D^\square \to D^\square]$, it remains to show that it preserves limits. Let $T$ be a directed set in $D^I$. Then

$$\begin{aligned} \psi \vec{v}(\bigvee T) &= \{\vec{i} \mapsto (\bigvee T)(\vec{v} \cdot \vec{i}) \mid \vec{i} \in I\} \\ &= \{\vec{i} \mapsto \bigvee_{t \in T} t(\vec{v} \cdot \vec{i}) \mid \vec{i} \in I\} \\ &= \bigvee_{t \in T} \{\vec{i} \mapsto t(\vec{v} \cdot \vec{i}) \mid \vec{i} \in I\} \\ &= \bigvee_{t \in T}(\psi \vec{v} t) \end{aligned}$$

<figure><img src="image_9.png" /></figure>

Remark: $\psi$ cannot be continuous on its first argument, since for $t$ fixed and $\vec{i}$ increasing, $\psi \vec{i} t$ is eventually $\perp^I$ when $\vec{i}$ escapes from $\text{dom } t$. Hence $\psi$ is not even monotone on its first argument.

**6.2. The generalised transpose and index transformations.** Let $\pi : \omega \to \omega$ be a bijection, to be regarded as a permutation of the axes. Its action on $I$ is defined by $\hat{\pi} : \vec{i} \mapsto \vec{i} \circ \pi^{-1}$. For example, if $\pi 0 = 1$, $\pi 1 = 2$, $\pi 2 = 0$ and $\pi n = n$ elsewhere, then

$$\hat{\pi}321 = \hat{\pi}\{0 \mapsto 3, 1 \mapsto 2, 2 \mapsto 1\} = \{0 \mapsto 3, 1 \mapsto 2, 2 \mapsto 1\} \circ \pi^{-1} = 132.$$

The *generalised transpose* defined by $\pi$ is the array transformation $T_{\hat{\pi}} : D^\square \to D^\square$ such that

$$(4) \qquad T_{\hat{\pi}} t \vec{i} = t(\hat{\pi} \vec{i}) = t(\vec{i} \circ \pi^{-1}).$$

For example the usual matrix transpose is built from the transposition $0 \leftrightarrow 1$. To verify that $T_{\hat{\pi}} t$ is a well defined array let $\text{dom } t = \langle \vec{i}_t \rangle$ and consider the fact that

$$(5) \qquad \vec{i} \circ \pi^{-1} \in \text{dom } t \iff \vec{i} \circ \pi^{-1} \le \vec{i}_t \iff \vec{i} \le \vec{i}_t \circ \pi$$
which holds because $\hat{\pi}$ and its inverse are monotone on $I$. As a result, dom $\mathcal{T}_{\hat{\pi}} = \langle \vec{i}_t \circ \pi \rangle$. We now show that $\mathcal{T}_{\hat{\pi}}$ is continuous as a function $D^I \to D^I$, which will imply that $\mathcal{T}_{\hat{\pi}} \in [D^\square \to D^\square]$. Let $T \subseteq D^I$ be a directed set. Then

$$ (6) \qquad \begin{aligned} & \forall \vec{i} \in I. \quad (\bigvee T)(\hat{\pi}\vec{i}) &= \bigvee_{t \in T}(t(\hat{\pi}\vec{i})) \quad \text{def. of } \bigvee \text{ on functions.} \\ & \Rightarrow \forall \vec{i} \in I. \quad (\mathcal{T}_{\hat{\pi}} \bigvee T)\vec{i} &= \bigvee_{t \in T}((\mathcal{T}_{\hat{\pi}}t)\vec{i}) \quad \text{def. of } \mathcal{T}_{\hat{\pi}}. \\ & \Rightarrow \forall \vec{i} \in I. \quad (\mathcal{T}_{\hat{\pi}} \bigvee T)\vec{i} &= (\bigvee_{t \in T} \mathcal{T}_{\hat{\pi}}t)\vec{i} \quad \text{def. of } \bigvee \text{ on functions.} \\ & \Rightarrow \mathcal{T}_{\hat{\pi}}(\bigvee T) &= \bigvee_{t \in T} \mathcal{T}_{\hat{\pi}}t. \end{aligned} $$

The generalised transpose is a special case of a more general operator. Suppose that a transformation $\sigma: I \to I$ is given to be extended into an array transformation by the same construction as (4):

$$ (7) \qquad \mathcal{T}_{\sigma}: D^I \to D^I: t \mapsto t \circ \sigma. $$

Let us formulate the exact conditions on $\sigma$ for $\mathcal{T}_{\sigma} \in [D^\square \to D^\square]$. Firstly, the continuity of $\mathcal{T}_{\sigma}$ on $D^I$ is proved for any $\sigma$ by replacing $\hat{\pi}$ with $\sigma$ in the inference (6) using only properties of function spaces. Consequently $\mathcal{T}_{\sigma}$ will be a continuous array transformation if and only if it preserves arrays (section 5). Now preservation of rectangular domains is equivalent to

$$ (8) \qquad \forall \vec{i}_t. \exists \vec{j}. \quad \sigma^{-1} \langle \vec{i}_t \rangle = \langle \vec{j} \rangle. $$

A first necessary condition on $\sigma$ is monotonicity.

**LEMMA 6.3.** If $\mathcal{T}_{\sigma}(D^{\square}) \subseteq D^{\square}$ then $\sigma$ is monotone.

*Proof.* Let $\vec{k}$ be any index and let $\vec{i}_t = \sigma\vec{k}$. Choose $\vec{k}' \le \vec{k}$ arbitrarily. By (8) the inverse image of $\langle \vec{i}_t \rangle$ is a rectangle, which will be denoted by $\langle \vec{j} \rangle$. Since $\sigma\vec{k} \in \langle \vec{i}_t \rangle$, $\vec{k} \in \langle \vec{j} \rangle$ from which $\vec{k}' \le \vec{j}$ follows. Therefore $\vec{k}'$ is in the inverse image of $\langle \vec{i}_t \rangle$ i.e. $\sigma\vec{k}' \le \vec{i}_t = \sigma\vec{k}$, which shows that $\sigma$ is monotone. $\square$

The remaining condition is weaker than being a homeomorphism 2 like $\hat{\pi}$. In general, $\sigma$ can be non-surjective or non-injective but it must have directed inverse images.

**LEMMA 6.4.** If $\mathcal{T}_{\sigma}(D^{\square}) \subseteq D^{\square}$ then $\forall \vec{i} \in \sigma(I)$. $\sigma^{-1}\vec{i}$ is a directed set.

*Proof.* Let $\vec{i}$ be an arbitrary index. By (8), there exists a $\vec{j}$ such that $\sigma^{-1}\langle \vec{i} \rangle = \langle \vec{j} \rangle$. Let now $\vec{j}_1, \vec{j}_2 \in \sigma^{-1}\vec{i} \subseteq \sigma^{-1}\langle \vec{i} \rangle$. Then $\vec{j}$ is an upper bound for both $\vec{j}_1$ and $\vec{j}_2$ so that by monotonicity of $\sigma$ (lemma 6.3)

$$ \vec{i} = \sigma\vec{j}_i \le \sigma\vec{j} \qquad j \in \{1, 2\}. $$

But since $\vec{j} \in \langle \vec{j} \rangle = \sigma^{-1}\langle \vec{i} \rangle$ we have $\sigma\vec{j} \le \vec{i}$. Therefore $\sigma\vec{j} = \vec{i}$ i.e. $\vec{j} \in \sigma^{-1}\vec{i}$. It was thus shown that any two $\vec{j}_i$ in the inverse image of $\vec{i}$ have a common upper bound $\vec{j}$ also in the inverse image of $\vec{i}$. $\square$

A direct consequence of this lemma is that when $\mathcal{T}_{\sigma}$ preserves arrays, $\bigvee \sigma^{-1}\vec{i}$ exists for any $\vec{i}$. Let us call this function the pseudo-inverse $\sigma^*$ of $\sigma$, discarding its trivial values $\bigvee \emptyset = \bot_I = 0$ for $\vec{i} \notin \sigma(I)$:

$$ \sigma^* : \sigma(I) \to I : \vec{i} \mapsto \bigvee \sigma^{-1}\vec{i} $$

<footnote n="2">2 continuous bijection with continuous inverse</footnote>
Lemma 6.4 therefore states that $\sigma^*$ is a total function when $\mathcal{T}_\sigma(D^\square) \subseteq D^\square$. Clearly, the $\vec{j}$ of (8) is $\sigma^*\vec{i}_t$ and this fact can be restated as

$$ (9) \qquad \forall \vec{i}. \sigma^{-1}\langle\vec{i}\rangle = \langle\sigma^*\vec{i}\rangle. $$

If $\sigma$ is bijective then the pseudo-inverse is just the functional inverse, and for example $\hat{\pi}^* = \hat{\pi}^{-1}$. As seen earlier, both $\hat{\pi}$ and its (pseudo-)inverse are monotone. This is generally true of array-preserving index transformations and of their pseudo-inverses.

**PROPOSITION 6.5.** If $\mathcal{T}_\sigma(D^\square) \subseteq D^\square$ then $\sigma^*$ is monotone.

*Proof.*

$$ \begin{align} \vec{i} \le \vec{i}' \nonumber \\ \Rightarrow \quad & \langle \vec{i} \rangle \subseteq \langle \vec{i}' \rangle \nonumber \\ \Rightarrow \quad & \sigma^{-1} \langle \vec{i} \rangle \subseteq \sigma^{-1} \langle \vec{i}' \rangle \nonumber \\ \Rightarrow \quad & \langle \sigma^* \vec{i} \rangle \subseteq \langle \sigma^* \vec{i}' \rangle \tag{9} \\ \Rightarrow \quad & \sigma^* \vec{i} \in \langle \sigma^* \vec{i}' \rangle \nonumber \\ \Rightarrow \quad & \sigma^* \vec{i} \le \sigma^* \vec{i}' \nonumber \end{align} $$

<figure><img src="image_10.png" /></figure>

In summary, (9) is sufficient for $\mathcal{T}_\sigma$ to preserve arrays.

**THEOREM 6.6.** The extension $\mathcal{T}_\sigma$ of $\sigma: I \to I$ defined by (7) is a continuous array transformation if and only if $\forall \vec{i} \in \sigma(I), \sigma^{-1}\vec{i}$ is directed and $\sigma^{-1}$ satisfies (9).

*Proof.* As was shown above, the two conditions are necessary. Conversely, (9) is stronger than (8). It implies that $\sigma^{-1}$ preserves principal ideals. $\square$

As an example of a non-injective $\sigma$ which generates a continuous $\mathcal{T}_\sigma$, consider the projection of all indices onto the first axis:

$$ \sigma_0 : \vec{i} \mapsto \vec{i}(0). $$

The image of $\sigma_0$ consists in all indices of the form $n = n0^\omega$ for $n \in \bar{\omega}$. Also

$$ \begin{align*} \sigma_0^{-1} \langle n \rangle &= \bigcup_{k \le n} \{ \vec{i} \in I \mid \vec{i}(0) = k \} \\ &= \langle n \bar{\omega}^\omega \rangle = \langle \bigvee n I \rangle = \langle \bigvee \sigma_0^{-1} n \rangle = \langle \sigma_0^* n \rangle \end{align*} $$

so $\sigma_0$ satisfies (9).

A non-surjective example we have already encountered is $\psi\vec{v} = \mathcal{T}_{\sigma_{\vec{v}}}$ where $\sigma_{\vec{v}}\vec{i} = \vec{v} \cdot \vec{i}$ (3). It was independently verified that $\psi\vec{v}$ is continuous and preserves arrays. It is somewhat surprising that array indexing and transpose are two instances of the same abstract operation. But within the context of array domains this unified view follows from the elementary arguments made in this section.

**6.3. Axis partitioning.** An orthogonal partition of $I$ or *axis partition* is a sequence of pairs $P = \{(b_n, s_n)\}_{n \in \omega}$ where $b_n \in \bar{\omega} - \{0\}$ and

$$ s_n : \bar{\omega} \to \{i \in \omega \mid i < b_n\} $$

is continuous and surjective. The pair $(b_n, s_n)$ separates the $n^{th}$ axis (the $n^{th}$ copy of $\bar{\omega}$ in $I = \bar{\omega}^\omega$) into the blocks $s_n^{-1}(i)$ for $i < b_n$. In other words $P$ partitions the
<figure><img src="image_11.png" /><figcaption>FIG. 4. The action of $\mathcal{P}_2$ on a two-dimensional array t of finite shape. Dotted lines outline the blocks of $\mathcal{P}_2$, solid lines outline the domain of t.</figcaption></figure>

$n^{th}$ axis into $\tilde{\omega}/(\ker s_n)$. Because all $s_n$ are continuous and surjective, the product projection

$$s = \prod_{n \in \omega} s_n : I \to \prod_{n \in \omega} \{i \in \omega \mid i < b_n\}$$

is also continuous and surjective. It partitions the set $I$ into $\prod_{n \in \omega}$ blocks as

$$I/(\ker \prod_n s_n) = I/(\prod_n \ker s_n) = (\prod_n \tilde{\omega})/(\prod_n \ker s_n) = \prod_n (\tilde{\omega}/\ker s_n).$$

Figure 4 illustrates a partition $P_2$ for which $b_0 = \omega$, $b_1 = 4$ and $b_{n+2} = 1$. Define now how an axis partition $P$ determines a map $\mathcal{P}: D^{\square} \to D^{\square\square}$. Consider $s_n^{-1}(i)$ a block along the $n^{th}$ axis. Because $s_n$ is monotone,

$$j_1 \le j_2 \le j_3 \text{ and } j_1, j_3 \in s_n^{-1}(i) \Rightarrow j_2 \in s_n^{-1}(i).$$

The blocks are therefore segments. Because $s_n$ is surjective, $s_n^{-1}(i) \neq \emptyset$ and because $\tilde{\omega}$ is well-founded it follows that $\bigwedge s_n^{-1}(i) \in s_n^{-1}(i)$. The continuity of $s_n$ implies

$$s \bigvee s_n^{-1}(i) = \bigvee_{j \in s_n^{-1}(i)} s_n(j) = \bigvee_{j \in s_n^{-1}(i)} i = i$$

where the second equality holds because $s_n^{-1}(i) \neq \emptyset$. Therefore $\bigvee s_n^{-1}(i) \in s_n^{-1}(i)$ and the $i^{th}$ block along the $n^{th}$ axis is the segment

$$\{\bigwedge s_n^{-1}(i), \dots, \bigvee s_n^{-1}(i)\}.$$

As an ordered set, $s_n^{-1}(i)$ is therefore equivalent to the initial segment

$$\langle (\bigvee s_n^{-1}(i)) - (\bigwedge s_n^{-1}(i)) + 1 \rangle$$
in $\tilde{\omega}$. It follows from the above remarks that the block $s^{-1}\vec{i}$ of $I$ / ker $s$ is homeomorphic (by translation back to the origin) to the following principal ideal in $I$:

$$ \prod_{n \in \omega} \left\langle \left( \bigvee s_n^{-1} \vec{i}(n) \right) - \left( \bigwedge s_n^{-1} \vec{i}(n) \right) + 1 \right\rangle $$

which will be written $s^{-1}\vec{i}$. The above expression uses the fact that the indices $\prod_{n \in \omega} \bigvee s_n^{-1}\vec{i}(n)$ and $\prod_{n \in \omega} \bigwedge s_n^{-1}\vec{i}(n)$ in $I$ are respectively the upper and lower corners of block $s^{-1}\vec{i}$. As a result, each block corresponds to a principal ideal and can be used to define an array.

Take $t \in D^{\square}$ and let us define $\mathcal{P}t$ as an element of $(D^I)^I$:

$$ (10) \qquad (\mathcal{P}t)_{\vec{i}\vec{j}} = \begin{cases} t(\vec{j} + \bigwedge s^{-1}\vec{i}) & \text{if } \vec{j} \in \overline{s^{-1}\vec{i}} \\ \perp & \text{elsewhere} \end{cases} $$

where the addition of indices is pointwise. The resulting function is a continuous array transformation.

**PROPOSITION 6.7.** $\mathcal{P} \in [D^{\square} \to D^{\square\square}]$.

*Proof.* By its definition (10),

$$ \mathrm{dom}(\mathcal{P}\vec{i}) = \mathrm{dom}(\psi(\bigwedge s^{-1}\vec{i})t) \cap \overline{s^{-1}\vec{i}} $$

which is a principal ideal (generated by the infimum of both ideals' suprema). Hence $\mathcal{P}t \in (D^{\square})^I$.

Let us now determine the domain of $\mathcal{P}\vec{i}$ when $t \in D^{\square}$. By (10), $\mathcal{P}\vec{i} \neq \perp^I$ exactly when $\bigwedge s^{-1}\vec{i} \le \bigwedge \mathrm{dom} t$ i.e. when

$$ \exists \vec{j} \in s^{-1}\vec{i}, \vec{j} \le \bigwedge \mathrm{dom} t $$

because $\bigwedge s^{-1}\vec{i} \in s^{-1}\vec{i}$. So $\mathcal{P}\vec{i} \neq \perp^I$ exactly when $\vec{i} \le s \lor \mathrm{dom} t$ because $s$ is monotone. As a result, $\mathrm{dom}(\mathcal{P}t) = \langle s \lor \mathrm{dom} t \rangle$ and so $\mathcal{P}t$ is an array.

It remains to show that $\mathcal{P}$ is continuous as a function from $D^I$ to $(D^I)^I$. Let $T \subseteq D^I$ be directed and assume that $\vec{j} \in s^{-1}\vec{i}$. Then

$$ \begin{align*} \mathcal{P}(\bigvee T)_{\vec{i}\vec{j}} &= (\bigvee T)(\vec{j} + \bigwedge s^{-1}\vec{i}) \\ &= \bigvee_{t \in T} t(\vec{j} + \bigwedge s^{-1}\vec{i}) \quad \text{supremum of functions} \\ &= \bigvee_{t \in T}(\mathcal{P}t_{\vec{i}\vec{j}}) \end{align*} $$

<figure><img src="image_12.png" /></figure>

Figure 5 summarises the continuous functions discussed so far.

**7. Fixpoints and recursion.** As seen in the last section, proofs of continuity are ad-hoc and somewhat tedious. Nevertheless, the definition of continuous array transformers constitutes the basis for recursive definitions in a style almost identical to what is done on (initial) data types like lists and trees. Once the continuous functions have been laboriously constructed, they may be used in recursive definitions without any constraint. Let us illustrate this style of programming with a few examples.
<table><caption>FIG. 5. Some continuous functions</caption><thead><tr><th>Name</th><th>Continuous function</th><th>Condition</th></tr></thead><tbody><tr><td>pointwise extension</td><td>f*: [D<sup>□</sup> &rarr; E<sup>□</sup>]<br/>f*<sub>t</sub> = f &circ; t</td><td>f &isin; [D &rarr; E] and f is either total or &perp;.</td></tr><tr><td>function transformer</td><td>f: [D<sup>□</sup> &rarr; E<sup>□</sup>]</td><td>f: [D<sup>I</sup> &rarr; E<sup>I</sup>] and f(D<sup>□</sup>) &sube; E<sup>□</sup>.</td></tr><tr><td>indexing</td><td>&psi;: &omega;* &rarr; [D<sup>□</sup> &rarr; D<sup>□</sup>]<br/>&psi;&vec;v<sub>t</sub> = t &circ; (&vec;v;&middot;)</td><td>none</td></tr><tr><td>index transformation</td><td>T<sub>&sigma;</sub>: [D<sup>□</sup> &rarr; D<sup>□</sup>]<br/>T<sub>&sigma;</sub>t = t &circ; &sigma;</td><td>&sigma;<sup>-1</sup><sub>i</sub> is directed and<br/>&sigma;<sup>-1</sup><sub>i</sub> &lang; i&lang; = &lang;&sigma;*i&lang; = &lang;V&sigma;<sup>-1</sup><sub>i</sub>&lang;</td></tr><tr><td>axis partition</td><td>P<sub>P</sub>: [D<sup>□</sup> &rarr; D<sup>□□</sup>]<br/>P<sub>P</sub>t&vec;i&j = t(&vec;j + A s<sup>-1</sup><sub>i</sub>)</td><td>P = {(b<sub>n</sub>, s<sub>n</sub>)<sub>n&isin;&omega;</sub>, b<sub>n</sub> &isin; &omega;&#773; - {0}}<br/>s<sub>n</sub>: [&omega;&#773; &rarr; {i &isin; &omega; | i &lt; b<sub>n</sub>}] surjective<br/>&vec;i &isin; s<sup>-1</sup><sub>i</sub></td></tr></tbody></table>

**7.1. Indexing: localised array access.** Our first example is a “feasible” realisation of the indexing function $\psi$. Let $\psi_0$ be a restricted form of the $\psi$ operator (3):

$$ \begin{aligned} \psi_0 & : \quad \omega \rightarrow [D^{\square} \rightarrow D^{\square}] \\ \psi_0 nt & = \{\vec{i} \mapsto t(n \cdot \vec{i}) \mid \vec{i} \in I\} \end{aligned} $$

As was shown earlier, $\psi\vec{v}$ can be expressed as an index transformation: more precisely a shift by $\vec{v}$, and $\psi_0 n$ only requires to shift $I$ by the 1-dimensional index $n$. Although a detailed explanation is beyond the scope of this article, it should be clear that a parallel evaluation of $\psi_0$ requires only local communications under reasonable assumptions about array layout. Now because of proposition 6.1, $\psi_0$ is sufficient to realise $\psi$ by a recursive definition on the list $\vec{v}$ as follows:

$$ \psi \vec{v} t = \begin{cases} \text{if } \vec{v} = \epsilon \text{ then } t \\ \text{else } (\psi(\text{tail } \vec{v}) t)(\psi_0(\text{head } \vec{v}) t) \end{cases} $$

The recursive evaluation of $\psi$ is thus realised by a sequence of evaluations of $\psi_0$, which has a more economical (and possibly portable) implementation.

**7.2. Index transformation: a systolic algorithm.** This example describes the specification of a systolic algorithm as a recursive program on arrays. The algorithm creates so-called wavefront data-dependencies and is taken from chapter 7 of [18]. It computes the longest common subsequence of two sequences. In the simplified form given here, a dynamic programming table $t$ is constructed which contains at point $ij$ the length of the longest common subsequence of the prefixes of respective lengths $i$ and $j$. The input sequences are stored in arrays $A$ and $B$ of respective
shapes $n+1$ and $m+1$, where $m \le n$. The input sequences are given by $A1, \dots, An$ and $B1, \dots, Bm$ while $A0$ and $B0$ are meaningless. The result of the computation is an array $t$ of integers of shape $(n+1)(m+1)$ whose content is defined recursively by:

$$ (11) \quad t(i, j) = \begin{cases} \text{if } j = 0 \text{ then } 0 \\ \text{else if } i = 0 \text{ then } 0 \\ \text{else } \max\{t(i-1)j, ti(j-1), t(i-1)(j-1) + [Ai = Bj]\} \end{cases} $$

where [...] denotes the integer corresponding to the boolean value of the predicate. The value $tij$ is the length of the longest subsequence common to $A1, \dots, Ai$ and $B1, \dots, Bj$.

Programming equation (11) as the fixpoint of a recurrence on continuous functions requires pointwise extensions of total functions and index translations to access previous sub-arrays. Let $\sigma_i: I \to I$ decrement the value of its argument along the first axis (without affecting $\vec{i}$ if $\vec{i} \ne 0 = 0$), $\sigma_j$ be defined likewise along the second axis and $\sigma_{ij} = \sigma_i \circ \sigma_j$. By the results seen earlier, $T_{\sigma_i}$, $T_{\sigma_j}$ and $T_{\sigma_{ij}}$ are all continuous. Given a total ternary max function on $N_{\perp}$, $\max^*$ is continuous on arrays, and similarly for pointwise addition of components $+^*$. Another continuous function needed here is the tensor product $\otimes_{\bullet}: [(D^{\square})^2 \to D^{\square}]$ defined with a binary scalar operation $\bullet$ such that $\rho(t_1 \otimes_{\bullet} t_2) = (\rho t_1)(\rho t_2)$ and for $\vec{i} \in \text{dom } t_1, \vec{j} \in \text{dom } t_2$,

$$ \psi(\vec{i}\vec{j})(t_1 \otimes_{\bullet} t_2) = (\psi \vec{i} t_1) \bullet (\psi \vec{j} t_2). $$

Its proof of continuity depends on the $\bullet$ being total and follows the outline of the corresponding proof for pointwise extensions.

The continuous array transformation which corresponds to the last branch of (11) is

$$ t \mapsto \max^*\{T_{\sigma_i}t, T_{\sigma_j}t, (T_{\sigma_{ij}}t) +^* [A \otimes B]^*\} $$

and the rest of (11) can be realised by a pointwise extension of the conditional. The result is a recursive definition of array $t$ as a function of $A$ and $B$.

**7.3. Axis partition: array reduction.** Our next example constitutes a recursive algorithm for array reduction, whose structure follows a given axis partition. Suppose $P_k = \{(b_n, s_n)\}_{n \in \omega}$ is an axis partition with infinitely many blocks of size $k$ along each axis: $b_n = \omega$ and for example $s_n = i \mod k$ for $i < \omega$ and $s_n\omega = \omega$. Then $P_k$ partitions a $d$-dimensional arrays into finite blocks of shape $k^d$. Suppose a binary associative-commutative operation $\bullet: D^2 \to D$ is given (for example scalar addition), to form the basis of a recursive definition of the reduction $R_{\bullet}$ of (finite) arrays with $\bullet$. First take a finite algorithm $\hat{R}_{\bullet}$ which reduces arrays of shape $k^d$. For example if $k = d = 2$ and $\bullet = +$ then $\hat{R}_{\bullet}$ could be $t \mapsto (t0) + (t1) + (t01) + (t11)$. By the definition

$$ R_{\bullet}t = \begin{cases} \text{if } \rho t = 1 \text{ then } t0 \\ \text{else } R_{\bullet}(\hat{R}_{\bullet}^*(P_k t)) \end{cases} $$

we obtain an algorithm for reduction which repeatedly reduces local (and finite) blocks of scalars. The value of $R_{\bullet}t$ at index 0 is the reduction of $t$'s image by $\bullet$. Again, although this notion will not be formalised in this article, finding a parallel implementation of $P_k$ provides a parallel algorithm for $R_{\bullet}$.
**8. Localisation and parallel evaluation.** This section introduces a notion of localisation and uses it to outline the implementation of array transforms by arrays of scalar functions.

**8.1. Localisation and globalisation.** Given an array transformer $f$, the localisation combinator $\text{loc}$ takes $f$ to an array of array functionals. Each functional $\text{loc} f \vec{i}$ is equivalent to the effect of $f$ at a given location $\vec{i}$, i.e. $\text{loc} f \vec{i} : t \mapsto f t \vec{i}$. It is convenient to use informal typed $\lambda$-notation to denote such operators:

$$ (12) \qquad \text{loc} = \lambda f : (D^{\square} \to D^{\square}). \lambda \vec{i} : I. \lambda t : D^{\square}. f t \vec{i} $$

By definition, $\text{loc} f : (D^{\square} \to D)^I$, but is easily verified that its domain is a principal ideal. Moreover, being built from composition, projection and abstraction, $\text{loc}$ preserves continuity and is continuous. Since it also preserves arrays, lemma 5.3 implies that

LEMMA 8.1. $\text{loc} : [[D^{\square} \to D^{\square}] \to [D^{\square} \to D]^{\square}]$.

Given an array of functions (in particular functionals like the values of $\text{loc} f$), it is possible to apply it to a scalar and obtain an array of values. This operation is called *globalisation* and is defined as follows. For $f : [D \to E]^{\square}$ the globalisation of $f$ is

$$ f_* = \lambda d : D. \lambda \vec{i} : I. f \vec{i} d. $$

The type of $f_*$ is $[D \to E^{\square}]$. Again, because $f_*$ is defined through continuous operations of the $\lambda$-calculus, it is continuous, and because of lemma 5.3 it is a continuous array operation:

LEMMA 8.2. $*_ : [[D \to E]^{\square} \to [D \to E^{\square}]]$.

As its name indicates, globalisation is the inverse of localisation:

LEMMA 8.3. For $f : [D^{\square} \to D^{\square}]$, and $F : [D^{\square} \to D]^{\square}$, $(\text{loc} f)_* = f$ and $\text{loc} F_* = F$.

*Proof.* By direct application of the definitions. $\square$

The existence of a continuous inverse shows that localisation preserves all the information contained in an array transformer $f$. This fact is no surprise: $\text{loc}$ simply reverses the role of the array $t$ and of the index $\vec{i}$, the latter being applied to the former. The notion of localisation has an obvious application to parallel processing as we now explain. Given $\text{loc} f$, the effect of $f$ on array $t$, can be computed by applying $(\text{loc} f)_*$ to $t$, an intrinsically parallel operation because the work is described separately for each $\vec{i}$. If the computation of $\text{loc} f \vec{i} t$ depends on the complete array $t$, then nothing is gained by localisation. But many useful array operations $f$ exhibit *locality*: $\text{loc} f \vec{i} t$ depends on a small set of values in the image of $t$. As a result such operations have efficient parallel implementations described by their localisations. These notions will now be illustrated by considering the array transformers of table 5.

**8.2. Pointwise extensions: maximal locality.** A pointwise extension $f^* : [D^{\square} \to D^{\square}]$ generates a pointwise localisation:

$$ \text{loc} f^* = \lambda t. f \circ t = f \circ $$

The computation of $\text{loc} f^* \vec{i} t$ is thus pointwise and requires no communication.
<figure><img src="image_13.png" /><figcaption>FIG. 6. Communication structure of $\text{loc } T_\sigma$.</figcaption></figure>

**8.3. Index transformations: explicit get function.** By definition of the in-dexing operator $\psi$, it follows that

$$ \text{loc}(\psi\vec{v})\vec{i} = \lambda t \cdot t(\vec{v} \cdot \vec{i}) $$

and if $\vec{v}$ is limited to a single integer $n \in \omega$, as seen in the example about $\psi_0$ then

$$ \text{loc}(\psi_0 n)\vec{i} = \lambda t \cdot t(n \cdot \vec{i}). $$

Thus $\text{loc}(\psi\vec{v})$ requires only for each index location to fetch one value, whose position in the argument array is given by $\lambda\vec{i}$. Localising $\psi_0 n$ is even more economical because the translation is simpler. Realising $\psi$ by $\psi_0$ is thus justified by this remark: $\psi$ can be defined by a library, while $\psi_0$ is more economically ported across various parallel architectures.

The general index transformation $T_\sigma$ also has a simple localisation:

$$ \text{loc } T_\sigma \vec{i} = \lambda t \cdot t(\sigma \vec{i}). $$

At one location $\vec{i}$, $\text{loc } T_\sigma$ preapplies $\sigma$ before applying $t$. Because $\sigma$ is a function, the value at that location thus only depends on one value. The fetching function $\sigma$ corresponds to what is sometimes called a remote evaluation call or **get** in parallel languages. On the other hand, the message sending operation **send** is known to be more elementary (from the point of view of hardware) and its use in $\text{loc } T_\sigma$ is defined by a relation $\sigma^{-1}$. Figure 6 illustrates this aspect of $T_\sigma$. The message complexity of $\text{loc } T_\sigma$'s implementation therefore depends crucially on the “granularity” of $\text{ker } \sigma$.

**8.4. Partition-reduction: explicit send function.** Let us now analyse the localisation of our reduction example based on axis partition. This program iterates $\hat{R}_\bullet \circ P_k$, where $P_k$ partitions arrays into blocks of length $k$ along each axis, and $\hat{R}_\bullet$ reduces such blocks. To make things concrete, take $\bullet = +$, and write $\Sigma = \hat{R}_\bullet$. Then

$$ \Sigma^* \circ P_k : [N_{\perp}^{\square} \to N_{\perp}^{\square}] $$

where $N$ is a set of numbers. By applying the definitions of $\text{loc}$, $\Sigma$ and $P_k$ it follows that

$$ \text{loc}(\Sigma^* \circ P_k) = \lambda t \cdot \sum_{\vec{j} \in s^{-1}\vec{i}} t(\vec{j} + \Lambda s^{-1}\vec{i}) $$
which shows explicitly that the localised operation only requires a block of values from $t$, identified by $s^{-1}$. Computing $s^{-1}$ corresponds to a `get` operation, but the function $s$ itself can be realised by the more efficient `send` operations. Contrarily to `loc $T_\sigma$, loc $(\Sigma^* \circ P_k)$` requires no inversion of its index dependence function. It is lower-level in that sense.

In the context of data-parallel languages and execution models, array transformers are called *macroscopic* and their localisation is *microscopic* [6]. Among (many!) other tasks, compilers for parallel languages with arrays must realise `loc`. The above examples should convince the reader of the importance of choosing the basic array transforms to balance efficiency, generality and portability. Through the geometric nature of the index domain $I$, array domains provide a machine-independent context for this kind of reasoning.

**9. Computability in array domains.** The algebraicity of domains is a prerequisite for any discussion of computable functions on them. However it is not sufficient: there are domains $D, E$ such that the cpo $[D \to E]$ is not a domain. A sufficient condition is to modify the completeness axiom and require *bounded completeness*. The poset $D$ is called *bounded complete* if it has a least element $\perp_D$ and if every bounded subset of $D$ has a least upper bound.

In order to define the effective presentation of a domain, the following notion of normal subset is required. Let $D$ be a poset. $N \subseteq D$ is called normal in $D$, which is written $N \triangleleft D$, if for any $x \in D$, $N \cap \langle x \rangle$ is directed. Normal posets are closely related to all aspects of computability in domains, and the definition of an effective presentation is centered on their decidability.

**THEOREM 9.1 (GUNTER AND SCOTT 3.4).** If $D, E$ are bounded complete domains then $[D \to E]$ is also a bounded complete domain. Moreover, if $D$ and $E$ have effective presentations then so does $[D \to E]$.

Let $D$ be a domain and $d : \omega \to K(D)$ a surjection. Then $d$ is an *effective presentation* of $D$ if

1. $\{(m, n) \mid dm \le dn\}$ is decidable and

2. For any finite $u \subseteq \omega$ it is decidable whether $\{dn \mid n \in u\} \triangleleft K(D)$.

Computable functions must be continuous, and are defined through compact generators. For $(D, d)$ and $(E, e)$ effectively presented domains, $f \in [D \to E]$ is *computable* (with respect to $d$ and $e$) if for all $n \in \omega$, $\{(n, m) \mid em \le f(dn)\}$ is recursively enumerable.

The above-defined standard notions are directly applicable to $I$ which is found to be both bounded complete and effectively presented. On the other hand, array domain construction does not preserve bounded completeness:

Take for example $D = \mathbb{N}_\perp$, the flat domain of natural numbers. It is easily verified that $D$ is bounded complete and the following counter-example shows that $D^\square$ is not bounded complete. Let $t_1 = \{0 \mapsto 5, 1 \mapsto 5\}$, $t_2 = \{0 \mapsto 5, 01 \mapsto 5\}$ and $s_n = \{0 \mapsto 5, 1 \mapsto 5, 01 \mapsto 5, 11 \mapsto n\}$ for $n \in \omega$. Then $\{t_1, t_2\}$ is bounded by $s_5$ but has no least upper bound. Indeed, all $s_n$ are upper bounds for $\{t_1, t_2\}$ and they are all pairwise orthogonal.

As a consequence, theorem 9.1 does not apply to the cpos $[D^\square \to E]$ and $[D \to E^\square]$. Moreover, only the first part of an effective presentation for $D^\square$ is easily constructed. The construction of a normality checking algorithm for finite sets in $K(D^\square)$ would require an unknown method for the globalisation of local decisions about $\triangleleft$.
As a result, the formal study of computability on array domains remains unexplored, although all continuous functions studied here appear to be efficiently computable.

In fact it is not clear whether $D^\square$ is effectively presentable, because although compact arrays are finite functions, they are not *monotone* and so aren't part of $K([I \to D])$, which is known to be an effective domain when $D$ is effective.

**10. Conclusion.** Array domains and continuous array transformations provide a foundation for the study of functional programs on arrays, their computability and parallel evaluation. The work presented here suggests a crude but formal criterion to guide the design of data-parallel languages: their libraries should contain computable continuous functions whose parallel evaluation is efficient.

Apart from domain-theoretic computability, two important issues have been left open here: how to relate array domains with array CDTs and the description of nested arrays. Both suggest the same theoretical problem: defining $D^\square$ as a fixpoint and studying the categorical properties of the array domain functor.

**Acknowledgements.** This work grew out of the search for an operational semantics in which to reason about the implementation of MOA. We therefore owe its motivation to Lenore Mullin who proposed the notion of a functional formalism representing both the structure and value of programs on arrays. The work of David Skillicorn and Colin Banger on CDTs was also influential.

## REFERENCES

[1] BANGER, BARNARD, CARMICHAEL, CORDY, GRAHAM, JENKINS, AND MAHON, *The T'Nial report*, tech. rep., Queen's University, Computing and Information Science, 1989.

[2] C. BANGER, *Construction of Multidimensional Arrays as Categorical Data Types*, PhD thesis, Queen's University, Kingston, Ontario, November 1993.

[3] J. BEVEMYR, T. LINDGREN, AND H. MILLROTH, *Exploiting recursion-parallelism in Prolog*, in PARLE'93, Parallel Architectures and Languages Europe, A. Bode, M. Reeve, and G. Wolf, eds., no. 694 in Lecture Notes in Computer Science, Munich, June 1993, Springer.

[4] R. S. BIRD, *Lectures on constructive functional programming*, in Constructive Methods in Computing Science, M. Broy, ed., no. 55 in NATO ASI, Marktoberdorf, BRD, 1989, Springer.

[5] G. E. BLELLOCH, *Vector Models for Data-Parallel Computing*, MIT Press, 1990.

[6] L. BOUGÉ, *Le modèle de programmation à parallélisme de données: une perspective sémantique.*, RAIRO Technique et Science Informatiques, 12 (1993). Numéro spécial sur les langages à parallélisme de données.

[7] H. P. F. FORUM, *High performance Fortran language specification, version 1.0*, Scientific Programming, 2 (1993). Preprint, 1993.5.3.

[8] C. A. GUNTER AND D. S. SCOTT, *Semantic domains*, in Handbook of Theoretical Computer Science, J. V. Leeuwen, ed., North-Holland, MIT-Press, 1990. Two volumes.

[9] G. HAINS AND C. FOISY, *The data-parallel categorical abstract machine*, in PARLE'93, Parallel Architectures and Languages Europe, A. Bode, M. Reeve, and G. Wolf, eds., no. 694 in Lecture Notes in Computer Science, Munich, June 1993, Springer.

[10] G. HAINS AND L. M. R. MULLIN, *Parallel functional programming with arrays*, The Computer Journal, 36 (1993).

[11] K. IVERSON, *A functional array language*, in ATABLE-92 Second international workshop on array structures, G. Hains and L. Mullin, eds., Montréal, 1992. Publication no. 841 DIRO, Département d'Informatique et de Recherche Opérationnelle, Université de Montréal.

[12] J. JEURING, *A hierarchy of algorithms for pattern matching on matrices*. CWI, Centrum voor Wiskunde en Informatica, Amsterdam, November 1990.

[13] J. LOECKX AND K. SIEBER, *The Foundations of Program Verification*, Wiley-Teubner Series in Computer Science, John Wiley and Sons, 1984.

[14] M. METCALF AND J. REID, *Fortran 90 Explained*, Oxford University Press, 1990.
[15] T. MORE, *Notes on the axioms for a theory of arrays*, Tech. Rep. 320-3017, IBM Philadelphia Scientific Center, May 1973.

[16] —, *Notes on the development of a theory of arrays*, Tech. Rep. 320-3016, IBM Philadelphia Scientific Center, May 1973.

[17] L. M. R. MULLIN, *A Mathematics of Arrays*, doctoral dissertation, Syracuse University, Syracuse, N.Y., December 1988.

[18] P. QUINTON AND Y. ROBERT, *Algorithmes et architectures systoliques*, Masson, 1989.

[19] D. B. SKILLICORN, *A Model for Practical Parallelism*, International Series on Parallel Computation, Cambridge University Press, 1994. To appear.

[20] G. STEELE AND W. HILLIS, *Connection Machine Lisp: A Fine Grained Parallel Symbolic Processing Language*, in ACM Conf. on Lisp and Funct. Progr., Cambridge MA, 1986, pp. 276-297.