SISAL: A Safe and Efficient Language for Numerical Calculations

The benefits of SISAL and a call for action.
Everything Is a Function Definition

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];
______________________

White Paper
Linux Management with Red Hat Satellite: Measuring Business Impact and ROI

Linux has become a key foundation for supporting today's rapidly growing IT environments. Linux is being used to deploy business applications and databases, trading on its reputation as a low-cost operating environment. For many IT organizations, Linux is a mainstay for deploying Web servers and has evolved from handling basic file, print, and utility workloads to running mission-critical applications and databases, physically, virtually, and in the cloud. As Linux grows in importance in terms of value to the business, managing Linux environments to high standards of service quality — availability, security, and performance — becomes an essential requirement for business success.

Learn More

Sponsored by Red Hat

White Paper
Private PaaS for the Agile Enterprise

If you already use virtualized infrastructure, you are well on your way to leveraging the power of the cloud. Virtualization offers the promise of limitless resources, but how do you manage that scalability when your DevOps team doesn’t scale? In today’s hypercompetitive markets, fast results can make a difference between leading the pack vs. obsolescence. Organizations need more benefits from cloud computing than just raw resources. They need agility, flexibility, convenience, ROI, and control.

Stackato private Platform-as-a-Service technology from ActiveState extends your private cloud infrastructure by creating a private PaaS to provide on-demand availability, flexibility, control, and ultimately, faster time-to-market for your enterprise.

Learn More

Sponsored by ActiveState