Sisal [41] is a strongly typed, applicative, single assignment language in use on a variety of parallel processors, including conventional multiprocessors, vector machines and data-flow machines. The language features include dynamic array structures, and a comprehensive set of built-in operators for them. Streams are provided for pipelined parallelism. Sisal has a parallel loop construct, with associated reduction and masking operators. A sequential loop form expresses loops with data dependencies between iterations. The programmability advantages offered by these features lead to higher performance since the resulting code is much easier to analyze for data dependencies and therefore more amenable to optimization, vectorization and parallelization. Sisal 1.2 has been in use since 1984; Sisal 2.0, a new language definition, is currently under development.
A number of projects have dealt with the translation of functional languages for multiprocessor systems. For instance, at the University of Manchester, efforts have led to the development of a Sisal 1.2 compiler for the Manchester Dataflow Machine [58]. In the Netherlands, DTN (Dataflow Technology Netherlands) has produced a compiler which accepts a subset of C and targets its object code to a network of NEC data-flow chips [99]. Also, the MIT team has designed the Id compiler for the Monsoon data-flow architecture [5]. However, it should be noted that these projects usually involve a target architecture specially designed to execute functional programs (in this case data-flow graphs). Other approaches have attempted targeting off-the-shelf multiprocessors. For instance, two projects, initiated at the Colorado State University, dealt with the compilation of Sisal for (at first) conventional multiprocessors, leading to the development of the very efficient Optimizing Sisal Compiler (OSC).
Sisal research has internationally demonstrated the effectiveness of the language and its implementation on a wide variety of applications and machines. OSC and other tools are freely available (for a wide range of machines) from Lawrence Livermore National Laboratory. Recent Sisal compiler developments for the CRAY, Sequent, Alliant, Encore, and other shared memory machines have resulted in Sisal applications that run faster than Fortran equivalents compiled using automatic parallelization and vectorizing tools. Success has been most evident with scientific applications, which exhibit a regularity of data and program structure most readily analyzed by the automatic parallelization techniques used in implementing Sisal. However, non-numeric algorithms have been implemented, for example, a compiler [105] and the travelling salesman problem [95].
Various characteristics of Sisal 1.2 contribute to its success. Its parallel iterative expressions, with powerful array manipulation and reduction operators, facilitate expression of structure parallel algorithms. It has its origins in languages for data flow machines; it is determinate, its semantics are predominantly strict, and it is straightforward to derive a data flow graph which exposes the maximum parallelism in the algorithm for exploitation by appropriate analyses. It is a first-order language (without higher-order functions), allowing such analyses to be more pervasive than in, for example, languages which place greater emphasis on higher order functionality [77][98][62].
The latter point needs elaboration. General functional programming research has shown that considerable power of expressiveness and abstraction is offered by higher order functions, polymorphism, overloading and type inference. Noting this, the recent proposals for Sisal 2.0 language development [16] suggest inclusion (in a limited form) of such features. Important issues thus raised are the expressiveness and soundness of these proposals, especially in the context of the powerful array operations characteristic of Sisal.
Vital to the success of many existing functional language (including Sisal) implementations are sophisticated compile-time analyses for copy optimization, aiding effective storage utilization. This approach is, however, very much compiler-dependent, and allows no program specification of storage constraints. Recent work on linear type systems [100], and linear abstract data types [101], shows promise of assisting control of storage use in functional languages, but without greatly compromising the higher level of abstraction offered by these languages.
Implementation issues are also important: can current high levels of effectiveness of Sisal implementation on parallel machines be maintained in the presence of (even limited) higher-order functionality, extensive overloading and polymorphism?