4.3 Example Translation

We view a program in terms of the natural AST corresponding to the CFG of Section 4.1. In the AST, an application of one of the four basic operations is written as a function application node with the operation to be applied in the name attribute and a depth attribute that is 0. The children of the node are expression(s) for each of the arguments.

The following 3 rules can be used to eliminate all sequence comprehension constructs from the AST:

 

Rule 1

$\mbox{\tt (/}\ x_1 \ \mbox{\tt in}\ e_1 \ \mbox{\tt :}\ x_1 \ \mbox{\tt /)}\longrightarrow e_1$

Rule 2

Provided e₂ is an Id or Num, and $e_2 \neq x_1$,

$$\mbox{\tt (/}\ x_1 \ \mbox{\tt in}\ e_1 \ \mbox{\tt :}\ e_2 \ \mbox{\tt /)}$$

$$\ \ \ \ \ \longrightarrow\ \ \ \mbox{\tt dist}\mbox{\tt (}\ e_2, \mbox{\tt length}\mbox{\tt (}\ e_1\mbox{\tt ))}\$$

Rule 3

[Note: this is typeset differently in the PostScript version of this paper.]

$$\mbox{\tt (/}\ x_1 \ \mbox{\tt in}\ e_0 \ \mbox{\tt :}\$$

$$\mbox{\tt fn\_app}\mbox{\tt (}\ \mbox{\tt name} = f,$$

$$\mbox{\tt depth} = d,$$

$$\mbox{\tt args} = n,$$

$$e_1, \ldots, e_n \ \mbox{\tt )} \ \mbox{\tt /)}$$

$$\longrightarrow \mbox{\tt fn\_app}\mbox{\tt (}\ \mbox{\tt name} = f,$$

$$\mbox{\tt depth} = d+1,$$

$$\mbox{\tt args} = n,$$

$$\mbox{\tt (/}\ x_1 \ \mbox{\tt in}\ e_0 \ \mbox{\tt :}\ e_1 \ \mbox{\tt /)},$$

$$\ldots,$$

$$\mbox{\tt (/}\ x_1 \ \mbox{\tt in}\ e_0 \ \mbox{\tt :}\ e_n \ \mbox{\tt /)}\ \mbox{\tt )}$$

The resultant AST can be written out in as Fortran 90 with the depth attribute supplied as an extra argument to the basic functions (add, length, range, dist). Given an appropriate implementation of these basic four functions, the resultant program specifies fully parallel execution of each sequence comprehension construct, regardless of the degree of nesting and sequence sizes.

For example, using these rules, the program from Section 4.2 would be transformed as follows (using $f(\ldots)$ as a shorthand for $\mbox{\texttt{fn\_app}}(\mbox{\texttt{name}}=f,\ldots)$):

       A = range(depth=0, 3) 
       B = add(depth=1, A, A) 
       C = dist(depth=1,
                A,
                length(depth=1,
                       range(depth=1, A)))

Note that functions with $\mbox{\texttt{depth}}=0$ operate on scalar arguments, whereas functions with $\mbox{\texttt{depth}}=1$ operate on vector arguments.

The rules shown for this example are terminating and confluent. When the source language is more expressive and optimization becomes an issue, the rules used are not necessarily terminating, hence additional sequencing rules must be added to control rule application [10].

In the following sections, we shall show how KHEPERA can be used to implement translations, such as the one specified above, in an efficient manner.