4.3. Analysis of Parallelism

In this section, we formally define colors using static slicing. Before this, we assume that recursive calls are always used in the form of $pat=f(x,e)$ in assignments of let statements. We can satisfy this condition without any loss of generality because $f(x,e)$ can be transformed to ${\tt let}~temp = f(x,e)~{\tt in}~temp~{\tt end}$.

Given a function $f$ of Definition 1 and the static slicing function ${\mathit SS_f}$, colors of all the subexpressions in the function body can be defined as follows. And, having the static slicing function ${\mathit SS_f}$ computed, color of each subexpression can be directly analyzed from this definition.

Definition 3   Formal Definition of Colors
Given a function definition  ${\mathit f}~pat_{1}~{\tt =}~e_1~\vert \hspace*{-1.01mm} \vert \hspace*{-1.01m... ...} \vert \hspace*{-1.01mm} \vert \hspace*{-1.01mm} \vert~pat_{n}~{\tt =}~e_n$ and a static slicing function $SS_f$, let

$$\begin{array}{lll} L :~\mbox{the set of labels of subexpress... ...ults} = {\mathit RecResults} - {\mathit RedResults} \end{array}$$

then the set of labels belonging to each color can be defined as follows.

$$\begin{array}{lll} {\mathit White}= {\mathit ApUse}^\prime \... ...thit ApUse} - {\mathit Yellow}- {\mathit Green}.\\ \end{array}$$

ApLabels is the set of labels attached to the accumulation parameters of recursive calls. Whenever an expression $e$ uses any value of the accumulation parameters, labels in ApLabels are included in the static slice for $e$. ApUse is the set of such expressions. ${\mathit ApUse}^\prime$ is the set of expressions which do not use any value of the accumulation parameters. RecResults is the set of labels of variable patterns to which results of recursive calls are assigned. RecResults is divided into RedResults and BlackResults, where RedResults are labels of variable patterns which use no accumulation parameter, and BlackResults are labels of variable patterns which use some accumulation parameters.

Using above sets, the set of subexpressions which belong to each color can be directly computed. ${\mathit White}$, ${\mathit Red}$ and ${\mathit Blue}$ expressions do not use the value of the accumulation parameters. So, their labels are included in ${\mathit ApUse}^\prime$. ${\mathit Yellow}$, ${\mathit Green}$ and ${\mathit Black}$ expressions can use the value of the accumulation parameters. So, their labels are included in ${\mathit ApUse}$.

Figure 5 is the result of coloring analysis of the inorder program. Analyzed colors are attached to every subexpression, where W, R, B, Y, G and Bk represent ${\mathit White}$, ${\mathit Red}$, ${\mathit Blue}$, ${\mathit Yellow}$, ${\mathit Green}$, and ${\mathit Black}$ respectively. In the program, t1 and t2 are ${\mathit Black}$ results because value of the accumulation parameter n is used to compute the first result. And s1 and s2 are ${\mathit Red}$ results because n is not used to compute the size of the tree. Since subexpression ((1:W+n:Y):Y+s1:B):Y evaluates the accumulation parameter of the second recursion using the accumulation parameter n, it is a ${\mathit Yellow}$ expression and must be computed along recursive calls. Expression ((s1:R+s2:R):R+1:W):R uses ${\mathit Red}$ results and is used to evaluate ${\mathit Red}$ results. So it belongs to ${\mathit Red}$ and values from the expression must be computed along the return of recursive calls. In the result part of let expression, though (n:G+s1:B):G uses an accumulation parameter and a ${\mathit Red}$ result, its value is not used to compute any accumulation parameter or ${\mathit Red}$ result. So, values of (n:G+s1:B):G can be computed using map skeleton after ${\mathit Yellow}$ and ${\mathit Red}$ expressions are evaluated.

Figure 5: Colors of Subexpressions in inorder Program