SISAL: A Safe and Efficient Language for Numerical Calculations

The single assignment nature of SISAL makes its use very different from commonly used languages such as C and Fortran. It also gives SISAL a steep, though short, learning curve, especially for those used to conventional programming techniques.

The key is to stop thinking in terms of a computer as a set of memory cells alterable at will by a sequence of instructions. Instead, think of SISAL as a nested sequence of mathematical definitions. One example is familiar to C programmers. A normal if statement in C might run something like this:

if (i > 0) {  a = i;
}
else {
  a = -i;
}

We recognize this as assigning the absolute value of i to a. However, an alternate form of the C language if statement is the assigned if, which accomplishes the same thing:

a = if i > 0 ? i : -i;

This is much closer to the spirit of the corresponding SISAL statement:

a := if (i > 0) then i else -i end if;

Returning to the two types of C language ifs, notice that the first form is subject to a possible error which, though it is syntactically correct, is probably not what you want to do; just drop the else {a = -i;} clause! This is still legal C, but it leaves the variable a undefined when i <= 0. Such an error is simply not possible in SISAL, or in the second type of C language if, because all possibilities must be considered for the statement to be syntactically correct.

The assigned if in C is quite limited in power. For instance, if several assignments need to be done, then several assigned ifs need to be created, and the logical test is repeated for each assignment. In SISAL one simply does the following:

a, b, c := if (i > 0) then             expression for a,
             expression for b,
             expression for c
           else
             alternate expression for a,
             alternate expression for b,
             alternate expression for c
           end if;

Alternatively, if it takes more than a simple expression to compute a result, then something like the following construct may be used:

a := if (i > 0) then       let
         x = ...;
         y = ...;
       in
         if (x > y) then x else y end if
       end let
     else
       ...
     end if;

The let...in...end let construct allows us to replace a simple expression with an arbitrarily complex calculation.

How do we get around the single assignment provision in iteration? Let's first see what the problem is. A loop in C that computes the cumulative sum of the array a might take the form:

b[0] = a[0];i = 1;
while (i < n) {
  b[i] = b[i - 1] + a[i - 1];
  i = i + 1;
}

Note the presence of our now-banished friend i = i + 1. All loops in C and similar languages have some construct like this, whether it is implicit or explicit. However, as we have noted, such a construct is illegal in SISAL. In addition, the array b is assigned to n times, which also violates the single assignment nature of SISAL. In SISAL we do the following:

b := for initial       i := 0;
       bvalue := a[0];
     while (i < n - 1) repeat
       i := old i + 1;
       bvalue := old bvalue + a[i];
     returns
       array of bvalue
     end for;

The for initial clause is executed once, setting up the initial definitions of i and bvalue. Then the loop is begun. Each time the loop hits the while statement, the variable i is renamed old i and bvalue is renamed old bvalue, leaving the names i and bvalue unassigned and ready to be reused. Finally, after the looping is finished, the returns clause gathers up the values of bvalue, including that from the for initial clause, and returns them as an array. While this way of doing loops is really a bit of a slight-of-hand for a single assignment language, it again satisfies the goal of keeping data dependencies explicit. The existence of an old clause clearly indicates that values produced in a loop depend on values generated in the previous iteration of the loop.

An alternate looping construct is available if computations in later iterations do not depend on results from earlier iterations. For instance, to multiply every third element of an array a by -1, SISAL does the following:

newa := for i in 0:n - 1          a1 := if (mod(i,3) = 0) then
                  -a[i]
                else
                  a[i]
                end if;
        returns
          array of a1
        end for;

If a loop can be cast in this form, it makes parallelization trivial since each branch of the loop can be executed by a different processor with no intercommunication between processors.

A complete SISAL function takes the form:

function fun_name(argument_list returns return_list)  expression, expression, ...
end function

The argument list specifies the names and types of all arguments. For instance, an argument list containing two integers named i and j followed by a real array named a would be specified i, j: integer; a: array[real];. A return list consisting of two real arrays would look like array[real], array[real]. The expression can be simple or complex, involving let, for, if or other statements. The number of expressions in the body of the function must match the number of returned values.

In addition to the basic types boolean, character, integer, real and double_real, there are compound types array, stream (like an array, but elements accessed sequentially), record (like a C structure) and union. Each of the compound types can, with minor restriction, consist of either simple or compound types. For instance, a two-dimensional array in SISAL is simply an array of arrays.

All variables are dynamically allocated, and variable types are determined from context. User-defined types are declared with statements like:

type oner = array[real];type complex = record[u: real_part; v: imag_part];
type complex_array = array[complex];