SISAL: A Safe and Efficient Language for Numerical Calculations

The benefits of SISAL and a call for action.

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?

Functional Languages

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:

  1. Functions do not remember anything about previous invocations.

  2. Functions do not change their calling arguments.

  3. Functions do not access global variables.

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.

SISAL and Parallel Computing at LLNL

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.
The implication is that variables can have a value assigned to them once and only once. That's why the language is called SISAL, the Streams and Iteration in a Single Assignment Language. The bit about “single assignment” refers to the above characteristic of the language. The obvious challenge is how to do iteration in such a language. “Streams” refers to an abstraction that was meant to be used in the language for input-output processes, but this was never developed.

______________________

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