10. More on Loops

In this section, we tackle some advanced aspects of looping. While we're going to do this in the context of parallel loops, for simplicity's sake, most of what we say will also apply to sequential, or iterative, looping, which we are saving for a later section. We have already seen two forms of range generators, and two forms of returns clauses. Sisal has more to offer in both of these areas. As in all languages, looping constructs can be nested to effectively any depth. Nested looping is one way to generate multidimensional arrays. There are also many ways to return values, both simple and compound, from loops. Here we will explore these topics in a bit more detail, since they add greatly to the power of the language in expressing algorithms and exploiting parallelism.

10.1 Range Generators

The possibilities for simple loop range generators extends to the combination of the two we have already seen. For simplicity, we will show examples of the three together before describing them.

        for i in 1, n

        for a in a_array

        for a in a_array at i

Here, we see the two familiar forms followed by a new hybrid form. The first one, as we have said, generates a set of independent values, all named i, from the inclusive range [1,n]. The second generates a set of independent values, all named a, from the aggregate named a_array. The third generates both the element a, from the aggregate a_array, and the index of a, i, in the index range of a_array. This last form may seem strange, but it is useful in situations where the index range of an array is not known ahead of time.

In addition to the above simple range generators, we can have compound or multidimensional ones, such as the following:

        for i in m, n cross j in p, q

        for a in a_array cross b in b_array

        for k in r, s dot m in x, y

        for c in c_array dot d in d_array

Here we have the first two forms of simple range generator combined into compound generators. The keywords "dot" and "cross" determine how the index or element value sets will be formed. In the first example, we have an index value set consisting of the cross product of the ranges from the two simple generators. In other words, every value of i in the range [m,n] will be paired with every value of j in the range [p,q]. In the second example, we have another cross product, with every element a from a_array paired with every element i from b_array.

In the dot-product range generators, we again have a pairing of values, but no value from either set is used more than once. In the third example, the first value of k will be r, and it will be paired with the first value of l, which will be x. The second values of k and l will be r+1 and x+1, respectively; this continues until the smaller-sized range is completely used up, at which point the loop's range is complete. Similarly, in the fourth example, the first value of c will be the first element of c_array, and it will be paired with the first element of d_array. In the case of arrays, when we use the term "first element" we mean the element with the lowest index.

These compound ranges are very powerful, and they can be extended effectively without limit. Semantically, compound ranges are equivalent to loop nests. The following two loops are equivalent in range and in the types of values they return:

for i in m, n cross j in p, q
   x := i + j
returns array of x
        value of sum x
end for

for i in m, n
   x_array, x_scalar := for j in p, q
                           x := i + j
                        returns array of x
                                value of sum x
                        end for
returns array of x_array
        value of sum x_scalar
end for

Each of the above two loops produces a two-dimensional array and a scalar. The index range of the arrays are [m, n] by [p, q], and the elements in corresponding positions of the arrays are identical.

Just to make certain all this is clear, we should consider a few more examples. The following loop sums all the elements of a two_dimensional array:

for i in 1, num_rows cross j in 1, num_columns
returns value of sum a[i,j]
end for

The next example returns the vector consisting of the major diagonal of a two_dimensional array:

for i in 1, num_rows dot j in 1, num_columns
returns array of a[i,j]
end for

The above example is a bit tricky. Since the array a may not be square (i.e., have the same number of rows as it does columns), the resulting vector will actually be the major diagonal of the largest square subarray of array a.

Here's another tricky example, the transposition of a rectangular array:

for j in 1, num_columns cross i in 1, num_rows
returns array of a[i,j]
end for

The above deserves careful study. It hasn't been emphasized yet, but the shape of an array returned by a loop nest is strictly determined by the order of the ranges of the loops as well as the ranges themselves. The array a, above, has shape [1, num_rows] by [1, num_columns], which is to say it has num_rows rows and num_columns columns. We want the resulting transposed array to have num_columns rows and num_rows columns, and to have as it's [i,j]-th element the [j,i]-th element of a. We must build the array in the shape we want, so we specify the outer loop to run over the desired index range for rows, and the inner loop to run over the that for columns. We then must be careful to access the elements of the original array, a, so as to avoid addressing outside of its index ranges. If we do all that correctly, the resulting value returned by the loop will be correctly transposed in size, shape, and element values. The reader should take the time firmly understand the above loop before proceeding with the next set of exercises.

10.2 Returns Clauses

We have also merely scratched the surface in the area of returns clauses. We have seen the use of the "array of" aggregation and the "value of sum" reduction. There are also "value of" and "stream of" aggregations, which we will not go into at this point, and reductions of the form "value of product", value of least", "value of greatest", and "value of catenate". The sum, product, least, and greatest reductions produce scalars, and operate on numeric and Boolean types. Here's an example of their use in a nonnumeric context:

for B_val in Boolean_array
returns value of sum B_val
        value of product B_val
end for

This loop's return clause performs the inclusive "or" and the "and" functions of the elements of Boolean_array. The reduction performs a Boolean summation, which returns true if any of its operands are true, and reduction performs a Boolean multiplication, returning true only if all its operands are true.

The catenate reduction produces a flattened aggregate. This latter point is nontrivial. If a two-level loop produces an array via the "array of" aggregation, it will be a two-dimensional array, with ranges corresponding to those of the loops. If, on the other hand, it returns "value of catenate", the resulting array will be one-dimensional, consisting of all the rows produced by the inner loop joined together into a larger vector. A few examples at this point would likely be helpful.

The following loop finds the largest and smallest elements of a three-dimensional array:

for a_two_d in a_three_d cross
    a_one_d in a_two_d cross
    a_elt in 1, a_one_d

returns value of least a_elt
        value of greatest a_elt
end for

The following loop flattens a three-dimensional array into a one_dimensional vector by concatenating all its rows together:

for row_plane in a_3d_array cross
    row in row_plane

returns value of catenate row
end for

The number of elements of the array resulting from the above loop will be the sum of the numbers of elements in each row of a_3d_array. The index range will begin at the index range of the first row and proceed upward from there.

10.3 Masked Returns Clauses

The returns clause is capable of aggregating and reducing values computed in its for-loop, and it can also exercise selection criteria in determining which values to so treat. This is accomplished with one or more "masks," which are simply predicates that can be applied to the loop-generated values before further action is taken on them by the returns clause. These masks take the form of the keywords "when" or "unless" followed by a logical expression. The truth value of the logical expression interacts with the chosen mask keyword to determine whether the loop-generated values will be among those returned. Here's an example of a masked loop:

for val in an_array
returns value of sum 1 when val > 0.0
end for

The above loop sums a set of integer ones corresponding to the positive elements of an_array. This is a simple way of counting the positive elements. Another common way to use masked returns clauses is in weeding out values from a set to be aggregated and returned, such as the following situation:

for i in 1, number_of_values
    new_val := deep_thought( value[i] )
returns array of new_val unless new_val > upper_val | new_val < lower_val
end for

The above loop returns an array of only those instances of new_val that fall within the desired range [lower_val, upper_val]. The array so generated will not have any empty elements; every element in its index range will have a corresponding legal value, but its index range will not necessarily be equal to that of the loop, so care must be taken in subsequent dealings with it.

The for-loop is incapable of doing the sorts of calculations that involve information moving between the instances of the loop's calculation, such as iterative convergence calculations. It is also incapable, as we now know it, of doing the more general form of looping across irregular index ranges or value sets. The first of these problems will be dealt with when we discuss the other form of Sisal loop statement, and the second when we deal with advanced looping concepts. For now, let us do a few exercises that will expose more of the power of Sisal loops.

Previous Section

Next Section

If you have any questions about this page, or want more information about the Sisal Language Project, contact:

John Feo at (510) 422-6389 or feo@diego.llnl.gov, or Tom DeBoni at (510) 423-3793 or deboni@llnl.gov.

The Sisal Language Project has been approved as a Designated Unclassified Subject Area (DUSA) K19222, as of 07 August, 1991.