About SAC

SAC (Single Assignment C) is a strict purely functional programming language whose design is focussed on the needs of numerical applications. Particular emphasis is laid on efficient support for array processing. Efficiency concerns are essentially twofold. On the one hand, efficiency in program development is to be improved by the opportunity to specify array operations on a high level of abstraction. On the other hand, efficiency in program execution, i.e. the runtime performance of programs both in time and memory consumption, is still to be achieved by sophisticated compilation schemes. Only as far as the latter succeeds, the high-level style of specifications can actually be called useful.

In order to facilitate the compilation to efficiently executable code, certain functional language features which are not considered essential for numerical applications, e.g. higher-order functions, polymorphism, or lazy evaluation, are not (yet) supported by SAC. These may be found in general-purpose functional languages, e.g. Haskell, Clean, Miranda, or ML.

In order to overcome the acceptance problems encountered by other functional or array based languages intended for numerical / array intensive applications, e.g. Sisal, Nesl, Nial, APL, J, or K, particular regard is paid to ease the transition from a C / Fortran like programming environment to SAC.

In more detail, the basic language design goals of SAC are

  • to provide a purely functional language with a syntax very similar to that of C in order to ease, for a large community of programmers, the transition from an imperative to a functional programming style;
  • to support multi-dimensional arrays as first class objects;
  • to allow the specification of shape- and dimension-invariant array operations;
  • to provide high-level array operations that liberate programming from tedious and error-prone specifications of starts, stops and strides for array traversals thereby improving code reusability and programming productivity, in general.
  • to incorporate a module system that allows for separate compilation, separate name spaces, and abstract data types, and, additionally, provides an interface to foreign languages in order to enable reuse of existing code;
  • to provide means for a smooth integration of states and state modifications into the functional paradigm based on uniqueness types;
  • to use the module system, the foreign language interface, and the integration of states in order to create a standard library which provides a functionality similar to that of the standard C libraries, e.g. powerful I/O facilities or mathematical functions;
  • to facilitate the compilation to host machine code which can be efficiently executed both in terms of time and space demand;
  • to facilitate the compilation for non-sequential program execution in multiprocessor environments.

About sac2c

The language implementation goals are rather simply explained: transform SAC high-level program specifications into efficiently executable machine code and achieve the utmost runtime performance possible. Among others, this may be done by

  • a mix of conventional optimizations, e.g. function inlining, constant folding, or loop invariant removal, which all benefit from referential transparency;
  • a rigorous shape inference scheme;
  • function specialization;
  • a folding scheme for high-level array operations that helps to avoid the creation of superfluous intermediate arrays;
  • a code generation scheme that takes the cache hierarchy into account;
  • implicit support for non-sequential program execution on multiprocessor systems.

However, C is used as an intermediate language in order to achieve portability among different target architectures and to reuse existing compiler technology for the generation of machine specific code.

The following graphic illustrates the major compilation phases of sac2c. Most of the intermediate phases operate on a code representation that is based on static single assignment form (SSA). To achieve this two additional phases called Fun2LaC and LaC2Fun transform intermediate SAC code into this convenient format and vice versa. For example, front-end representations of loops and if-clauses are transformed to what they actually represent: tail-end recursive functions and functional conditionals.

Compilation PhasesFig. 1: Compilation Phases of the sac2c compiler

Case Studies

Several case studies investigate the suitability of SAC for implementing numerical application programs is investigated with respect to both programming elegance and runtime performance of compiled code, in particular with respect to shared memory multiprocessors.

While most of our case studies can be found in the papers on applications, we have brought a few of them directly online: