for initial
i := array_liml(A);
tmp := A[i];
running_sum := tmp
while i < array_limh(A) repeat
i := old i + 1;
tmp := A[i];
running_sum := old running_sum + tmp
returns value of running_sum
array of running_sum
end for
In this example we first see the loop keywords "for initial" which
identify it as a sequential loop, and which open what we call the "initial
clause" of the loop. This clause contains the initial definitions of the
loop-carried values, "i", and "running_sum", which
implement the data dependencies between the contiguous body instances.Like the body of a for-loop, the initial clause of a for-initial loop can also contain the definitions of loop-local names, which are temporary identifiers used subsequently in the calculation but not passed between loop bodies; this is the purpose of "tmp". Next, we see the iteration termination test. This is a predicate, evaluating to a Boolean value, which uses either the "while" or "until" keyword to specify how the test is to be applied. The termination test can be at either the top or the bottom of the loop body; in this case it is at the top, and we refer to this form of loop as "top-tested." If it were at the bottom of the loop body, we would call it a "bottom-tested loop", and the keyword "repeat" would still be used to demarcate the top of the loop body.
The body of this loop shows the use of the keyword "old" to specify data passed in from previous bodies. In fact, it is more technically correct to call them "scopes" than "bodies", but the effect is the same. The statement "i := old i + 1" specifies that the value named "i" from the previous scope (i.e. "old i") is to be incremented by one and assigned the name "i" in this scope. While this may look like a violation of the single-assignment rule, it actually is not; the values named "i" and "old i" are two different entities, having independent existences, except for the value of the former being determined by the latter. The same thing holds for "running_sum", and we refer collectively to all of the instances of "i", "old i", "running_sum", and "old running_sum" as the "loop-carried values 'i' and 'running_sum'", respectively.
So, the way the values are passed between the loop bodies is like this. The first time the statement "i := old i + 1" in loop body is executed, the meaning of "old i" is that value of "i" defined in the initial clause of the loop. Subsequent to this, it means that value of "i" defined in the most recent body before the current one. The ordering of the loop bodies' execution is totally determined by the effects of the termination test and the loop-carried values. Notice that the identifier "tmp" does not appear with the modifier keyword "old"; this is because its value is not passed between loop bodies, but is calculated anew in each body. This "loop-local" identifier is similar to those temporaries that are defined in the bodies of parallel for-loops, in that each instance of it is independent of all the others, and we simply allow the reuse of its name for the convenience of the programmer.
At the end of the body we see the returns clause, just like that of the for- loop. It can contain the same aggregation and reduction operations, which can operate on any or all of the loop-carried values; they can also contain the same Boolean masks, using the keywords "when" or "unless", to allow operation on subsets of the instances of any or all of the loop- carried values. The loop above returns both a value and an array; it adds up all the elements of the array "A", aggregates all the running subtotals into an array, and returns the total and the array of subtotals.
for initial
i := array_liml(A) - 1;
tmp := 0;
running_sum := tmp
while i < array_limh(A) & array_size(A) ~= 0 repeat
i := old i + 1;
tmp := A[i];
running_sum := old running_sum + tmp
returns value of running_sum
array of running_sum
end for
In the above version of the loop, we use the initial-clause to set up for the
actual loop body, defining the first value of the loop index, "i" as
one less than the lower bound of the array, and the value of
"running_sum" as zero. Then, the loop body uses a value for
"i" that is legal within the array, if the termination test allows
the body to execute. The returns clause in this version will return zero and
an array containing the single element zero, if the loop body does not
execute. The previous version would have failed with a run-time error, if
this had occurred. We also see, in the second version, that the termination
test is altered, to allow for the array "A" to be empty and to have
a lower bound that is greater than its upper bound by more than one. Recall
that an empty array can have any bounds as long as the lower bound is greater
than its upper bound; it is possible that an algorithmically-generated array
might have bounds of, say [-5, 0 ], due to unexpected behavior of the code
the generates it. The addition of the array-size primitive protects the loop
against this possibility.
for initial
i := array_liml(A) - 1;
tmp := 0;
running_sum := tmp;
running_sum_array := array []
while i < array_limh(A) & array_size(A) ~= 0 repeat
i := old i + 1;
tmp := A[i];
running_sum := old running_sum + tmp;
running_sum_array := array_addh(old running_sum_array, running_sum)
returns value of running_sum
value of running_sum_array
end for
Here we have added another loop-carried value, "running_sum_array",
which is initialized to an empty array in the initial clause and returned in
the returns clause. In the body, we see it is operated on by the Sisal
primitive "array_addh"; this primitive extends the array given as
its first argument, at the upper end of its index range, by one element whose
value is the second argument. This affects both the contents of the array and
its index bounds, and is a very handy primitive to have in such a case as
this. Note that in the returns clause, the second value being returned is now
generated by a "value-of" operation, rather than by an operation. Since the
array we wish to return was created in the initial-clause and is being
incrementally filled by the loop body, we simply return the "last" version of
it generated by the loop as a whole. While the incremental expansion of this
array as the loopexecutes would normally be a source of inefficiency, the
Optimzing Sisal Compiler is able to optimize such programs so that the
structure is built in place quite efficiently.As one might expect by now, there is also a primitive to extend an array at the bottom end of its index range, as well as primitives to change one or more elements of an array, to shrink arrays at either end, and primitives to adjust the index range of arrays. These are specified in the following table, along with all the other array operations we have already seen; in the table, "A" is an array, "v" is a value of the proper type for elements of "A", and "low" and "high" are integers:
array primitive effect
========================================================
array_size(A) get number of elements
array_limh(A) get upper bound
array_liml(A) get lower bound
array_addh(A,v) extend at high end
array_addl(A,v) extend at low end
array_remh(A) remove at high end
array_reml(A) remove at low end
array_adjust(A,low,high) set both bounds
array_setl(A,low) set lower bound
A[ i : v ] change value at index i to v
A[ i: u, v, w ] change values at indices
i, i+1, and i+2 to
u, v, and w, respectively
A[ i: u; j: v ] change values at indices i and j
to u and v, respectively
The above primitives allow us to operate on arrays in useful ways, and are
most often used in sequential loops, such as we have been discussing.
However, they can also occur in other code, such as let-in statements, and it
bears emphasizing that the arrays they produce are different values from
those they operate on. In other words, we could have the following code:
let A := array [ 1: 5, 10, 15, 20, 25];
B := array_addl(A, -5);
C := array_addh(A, 30);
D := array_reml(A);
E := array_adjust(A, 3, 4);
F := A[ 1: -5; 3: -15, -20 ]
in A, B, C, D, E, F
end let
The above let-in statement returns the following values:
array [ 1: 5, 10, 15, 20, 25] % The array A
array [ 0: -5, 5, 10, 15, 20, 25 ] % B = A with new first element and
% lower bound
array [ 1: 5, 10, 15, 20, 25, 30 ] % C = A with new last element and
% upper bound
array [ 2: 10, 15, 20, 25 ] % D = A minus first element, with new
% lower bound
array [ 3: 15, 20 ] % E = A minus several elements, with
% new bounds
array [ 1: -5, 10, -15, -20, 25 ] % F = A with several elements changed
Note that none of the operations on "A" changes its value; Rather,
they produce new values of array types whose elements and index ranges are
related to those of their argument array.
for initial
val := initial_value
while {test(val)} repeat
val := f(old val)
returns val
end for
the value associated with the name "val" changes its name to
"old val" right after "test(val)" is executed, and the
named "val" becomes undefined at the same time. Note that the
test can contain references to "val" but not "old val",
since the latter is not defined the first time the test is encountered.
This form of loop is called a "top-tested loop."If a test which refers to both names is desired, it must be placed at the bottom of the loop body, as in the following example:
for initial
val := initial_value
repeat
val := f(old val)
while {test(val, old val)}
returns val
end for
The first time "test(val, old val)" is executed, both names are
defined, since the former was just calculated and the latter was calculated
in the initial clause. Immediately after the test, the value named
"val" changes its name to "old val" and the value
"val" becomes undefined at the same time. This form of loop is
called a "bottom-tested loop."Next are a few exercises intended to cement the concepts discussed above.
The Sisal Language Project has been approved as a Designated Unclassified Subject Area (DUSA) K19222, as of 07 August, 1991.
LLNL Disclaimer
UCRL-MI-122601