SISAL: A Safe and Efficient Language for Numerical Calculations

Back in the misty, early days of computing, famed computer scientist John Backus invented a programming language called Fortran. Given his other accomplishments, most computer scientists have probably forgiven him for this. After all, how was he to know that his invention would grow into a Frankenstein, sweeping away all attempts to replace it with more pleasant and useful tools?

Later, Backus became interested in functional languages. The best way to explain what a functional language does is to show you one that isn't. Let's look at the following C code:

int increment_me(int deposit){
  static int balance = 0;
  balance = balance + deposit;
  if (balance < 0) {
    fprintf(stderr,"Balance negative!\n");
  }
  return(balance);
}

This C function keeps track of your bank balance by adding deposits to your account and subtracting withdrawals (negative deposits). It also gives a warning if you overdraw your account. Your balance is initially assumed to be zero. Subsequent calls add to or subtract from this balance. In addition, a warning is given if you reach a negative balance.

Increment_me is a function in the C language sense, but it is not a function in the mathematical sense. A mathematical function, like sine or logarithm, gives the same answer to a particular question each time you ask it. For instance, the sine of 90 degrees is always one. In contrast, increment_me stores your current balance internally, which means that the result returned from calling it depends on the results of previous calls.

It is easy to turn increment_me into a true mathematical function by rewriting it as follows:

int increment_me(int deposit, int balance){
  balance = balance + deposit;
  if (balance < 0) {
    fprintf(stderr,"Balance negative!\n");
  }
  return(balance);
}

You, rather than increment_me, have to keep track of your bank balance in this version, but at least this C function is now also a mathematical function—it always gives the same answer to a particular question!

What are the advantages of the functional structure of this routine? Suppose increment_me is part of a complex accounting system, keeping track of many different balances. In this case, storing a single balance inside the C function would not get the job done since the function would only work for that particular account. Furthermore, if some other aspect of the accounting system needed to access your balance, it could not do it in the original version of increment_me, since the balance is buried in the function.

What is the downside of the new version of increment_me? Suppose increment_me were ten levels down in a stack of C function calls. Then, it would be a considerable nuisance to transfer the balance in which you are interested downward through this stack. One might be tempted to use the C language global-variable capability instead:

global int balance;int increment_me(int deposit)
{
  balance = balance + deposit;
  if (balance < 0) {
    fprintf(stderr,"Balance negative!\n");
  }
  return(balance);
}

This way, anyone anywhere in the system could insert the balance for a particular account in the global variable balance and initiate the cascade of calls that eventually results in increment_me being called and the balance being incremented.

What is wrong with this way of doing things? Non-locality. If something goes wrong, do you blame it on a bug in our humble function, or is the error somewhere else in the system? If you have ever dealt with this kind of a program, you know that it can be very difficult to debug.

Functional programs avoid these problems by following three rules:

Such functions are said to be free of side effects. Functional languages are languages that enforce these restrictions. Examples of partially functional languages are the venerable Lisp language and its derivatives such as Scheme, and the language ML. Haskell and the original version of Lisp are purely functional.

The advent of parallel computers introduced a whole new set of problems to the world of computing, the main one being how to divide up a task so that multiple processors can make progress on it simultaneously. Attempts to devise automatic parallelizing compilers for ordinary languages have met with mixed success. The objective is to define sub-tasks so that the flow of data between them is minimized since typically the communication bandwidth between individual processors in a parallel computer is limited. This is difficult in ordinary languages since the flow of data is immensely complicated by the existence of global variables and side effects—witness our third example of increment_me.

Enter a team of computer scientists led by James McGraw of Lawrence Livermore National Laboratory. In 1985 they invented a functional language called SISAL for the specific purpose of parallelizing scientific numerical calculations. The functional nature of the language allowed the compiler to trace the flow of data through the program, and therefore, to make intelligent decisions as to how to split up the work between processors in parallel computers.

Functional behavior on the procedure level, as in our procedure for incrementing or decrementing one's bank balance, was still insufficient for their purposes. In order to obtain sufficiently fine-grained information about data flow, they needed to make every program statement functional in a mathematical sense. To understand the implications of this requirement, notice that commonly used programming statements of the form:

a = a + 1

would be illegal in such a language since in mathematics a variable such as a cannot be both the input and output in an explicit function definition. One would have to write instead:

b = a + 1.