2.2. Recursive Functions for Parallelization

In functional languages, such as ML and Haskell, iterative computations on data collections are expressed using the recursive functions on recursive data structures. So we aim at extracting data parallelism from these recursive functions. But recursive functions are not always suitable for parallelization. Hence, we restrict the scope of the recursive functions for parallelization.

At first, we assume that the recursive functions have a tuple value as their actual parameter, where the first element of the tuple is of recursive type. We name the first element the recursive parameter and the second element the accumulation parameter. The recursive parameter is distributed for data parallel computation. The accumulation parameter is used to propagate values to recursive computations on connected elements[11]. The proper form of the recursive functions for parallelization is formally defined as follows.

Definition 1   Recursive Functions for Parallelization
The programs to be parallelized are those that can be turned into the following form :

$$\begin{array}{lll} f & (\kappa_1(p_1,x_{11},\ldots,x_{1l_1})... ...\langle f~(x_{nj},e_{nj})\rangle^{l_n}_{j=1}] \\ \end{array}$$

where

• $E_i[~]$ denotes an expression context and $E_i$ and $e_{ij}$ contain no occurrence of $f$ and $x_{ik}$.
• $\langle f~(x_{ij},e_{ij})\rangle^{l_i}_{j=1}$ are $l_i$ holes being filled with recursive calls $f~(x_{ij},e_{ij})$, where $l_i$ is the number of recursive fields for data constructor $\kappa_i$. $\Box$

In Definition 1, $\kappa_i(p_i,x_{i1},\ldots,x_{il_i})$'s are data constructor patterns and they are matched to the recursive parameter. $p_i$ is a pattern matched to non-recursive field of the recursive parameter and variable patterns $x_{ij}$'s are matched to recursive fields of the recursive parameter. In function bodies, all recursive calls use $x_{ij}$'s as the first element of their actual parameter and every $x_{ij}$ is used as the first element of actual parameters of recursive calls only once. Functions of this form apply the same function to all recursive parts of the recursive data structure. This property is suitable for data parallel execution. In case that $x_{ij}$'s are used in other computations, we can use tupling transformation to fulfill our condition.

inorder program is an example which satisfies Definition 1. Labels are omitted. In the second function body, variables lt and rt which are matched to recursive fields of the recursive parameter are used as the first parameter of recursive calls only. Therefore the same function inorder is applied to every recursive element of a given tree.