SINGLE ASSIGNMENT C
TUTORIAL
VERSION 1.2
SvenBodo Scholz Stephan Herhut
Frank Penczek Clemens Grelck
Artem Shinkarov
March 24, 2017
Contents:
 I Trails Covering the Basics of SaC
 II Trails Covering More Advanced Features of SaC
Part I Trails Covering the Basics of SaC
Chapter 1 Running the first program
The following instructions will help you write your first SaC program.
1.1 A Checklist
To successfully write and run your first SaC program, you will need:

•
An ANSI C compiler, such as gcc. Though not needed directly, the SaC compiler relies on it.

•
The SaC compiler sac2c. It can be downloaded at http://www.sachome.org; see instructions in the Download section.

•
The SaC standard library can be downloaded from GitHub http://www.github.com/SacBase/stdlibcore. The process of installation is described in README.md file of the stdlib repository.

•
Your favorite text editor, such as vi or emacs.
1.2 Create your first SaC Source File
Start your editor and type the following program:
As you can see, it has a strong resemblance to C. The major difference are the module use declarations at the beginning of the program. For now, it suffices to keep in mind, that these two use declarations for most experiments will do the job.
In order to proceed, save this program into a file named world.sac.
1.3 Compile the Source File and Run the Program
The SaC compiler invocation is similar to the standard invocation of C compilers. A typical shell session for compiling world.sac could be:
The compilation process consists of two steps. First, the SaC compiler generates a C file, which then is compiled into target code by utilizing the system’s C compiler. If no target file name is specified, the intermediate C file is named a.out.c so that the subsequent invocation of the C compiler creates an executable named a.out.
In the same way the default target name a.out is borrowed from standard C compilers, the o option for specifying target names is adopted as well. For example, sac2c o world world.sac results in files world.c and world.
Note here, that the compiled program, depending on the operating system, is linked either statically or dynamically. However, it does not require any further linking or interpretation.
Chapter 2 Array Programming Basics
This trail gives an introduction to the basic concepts of array programming in SaC. It consists of two lessons: Arrays as Data and ShapeInvariant Programming. In the former lesson, the major differences between arrays in SaC and arrays in more mainstream languages are explained. The lesson ShapeInvariant Programming gives an introduction into the most important array operations available in SaC. Based on these operations, several small examples demonstrate how more complex array operations can be constructed by simply combining the basic ones.
2.1 Lesson 1: Arrays as Data
In SaC, arrays are the only data structures available. Even scalar values are considered arrays. Each array is represented by two vectors, a socalled shape vector and a data vector. An array’s shape vector defines its shape, i.e. its extent within each axis, and its dimensionality (or rank), which is given implicitly by the shape vector’s length.
The section on Defining Arrays explains how arrays of various dimensionality can be defined in SaC, and how they can be generated via nesting. Furthermore, some elementary notation such as scalars, vectors, and matrices is defined.
The section on Arrays and Variables discusses the purely functional array model used in SaC.
2.1.1 Defining Arrays
In this section, several means for specifying arrays are explained.
In principle, all arrays in SaC can be defined by using the reshape operation. reshape expects two operands, a shape vector and a data vector, both of which are specified as comma separated lists of numbers enclosed in square brackets.
To get started, try the following program:
It prints three arrays:

•
an array of dimensionality 1 with 5 elements [1,2,3,4,5]

•
an array of dimensionality 2 with 3 rows and 2 columns, and

•
a 3dimensional array with 3 elements in the leftmost axis, 2 elements in the middle axis, and one element in the rightmost axis.
Note here, that the function print can be applied to arbitrary arrays. Besides printing its argument’s dimensionality and shape, i.e. its shape vector, a more intuitive representation of the array’s data vector is shown. However, as the terminal allows for 2 dimensions only, arrays of higher dimensionality are interpreted as nestings of 2dimensional arrays. Therefore, the 3dimensional array is printed as a 2dimensional array of vectors.
Exercise 1.
In all these examples, the product of the shape vector matches the length of the data vector. What do you expect to happen, if this condition does not hold?
For reasons of convenience, we use the following terminology:
 scalar

always denotes an array of dimensionality 0,
 vector

always denotes an array of dimensionality 1, and
 matrix

always denotes an array of dimensionality 2.
As all arrays can be defined in terms of reshape, the following program as well is perfectly legal:
The most interesting aspect of this program is the array defined in line 7. The empty shape vector makes it a 0dimensional array, i.e. a scalar. The data vector carries the scalar’s value, which, in this example, is 1.
Exercise 2.
The arguments of reshape are vectors, i.e. arrays of dimensionality 1. Can they be specified by e expressions themselves?
The reshape notation is relatively clumsy, in particular, when being used for scalars. Therefore, scalars and vectors can alternatively be specified by shortcut notations as well.
For experimenting with these, try the following:
From these examples, we can see that scalars can be used in the same way as in most programming languages, and that the notation used for the parameters of reshape in the examples above in fact is a standard abbreviation of SaC. The example in line 8 shows that nestings of arrays are implicitly eliminated, i.e. the resulting array is identical to:
reshape([3,2], [1,2,3,4,5,6]).
For this reason, array nestings in SaC always have to be homogeneous, i.e. the inner array components have to have identical shapes.
Furthermore, a new function is introduced: genarray. It expects two arguments, a shape vector that defines the shape of the result and a default element to be inserted at each position of the result. As shown in the example of line 10, the individual array elements can be nonscalar arrays as well, which implicitly extends the dimensionality of the result array.
Exercise 3.
Given the language constructs introduced so far, can you define an array that would print as
Dimension: 3 Shape : < 5, 2, 2> < 0 0 > < 0 0 > < 1 0 > < 0 0 > < 0 1 > < 0 0 > < 0 0 > < 1 0 > < 0 0 > < 0 1 >
but whose definition does not contain the symbol ‘1’ more than once?
2.1.2 Arrays and Variables
This section explains why in SaC arrays are data and not containers for values as found in most other languages.
So far, all examples were expression based, i.e. we did not use any variables. Traditionally, there are two different ways of introducing variables. In conventional (imperative) languages such as C, variables denote memory locations which hold values that may change during computation. In functional languages, similar to mathematics, variables are considered place holders for values. As a consequence, a variable’s value can never change. Although this difference may seem rather subtle at first glance, it has quite some effects when operations on large data structures (in our case: large arrays) are involved.
Let’s have a look at an example:
The function modarray expects three arguments: an array to be “modified”, an index that indicates the exact position within the array to be “modified”, and the value that is to be inserted at the specified position. As we would expect, the resulting array b is almost identical to a, only the very first element has changed into 9.
Note here, that indexing in SaC always starts with index !
Referring to the container / place holder discussion, the crucial question is: does the variable a denote a container, whose value is changed by modarray? If this would be the case, a and b would share the same container, and every access to a after line 9 would yield [9,2,3,4]. If a in fact is a place holder, it will always denote the array [1,2,3,4], no matter what functions have obtained a as an argument.
To answer this question, you may simply shift the first call of print two lines down. As you can see, in SaC, variables are indeed place holders.
A note for efficiency freaks: You may wonder whether this implies that modarray always copies the entire array. In fact, it only copies a if the placeholder property would be violated otherwise.
As a result of this placeholder property, it is guaranteed that no function call can affect the value of its arguments. In other words, the underlying concept guarantees, that all functions are “pure”. Although this helps in avoiding nasty errors due to nonintended sideeffects, it sometimes seems to be an annoyance to always invent new variable names, in particular, if arrays are to be modified successively.
To cope with this problem, in SaC, variables do have a socalled scope, i.e. each variable definition is associated with a welldefined portion of program code where its definition is valid. In a sequence of variable definitions, the scope of a variable starts with the lefthand side of the subsequent variable definition and either reaches down to the end of the function, or, provided at least one further definition of a variable with the same name exists, to the righthand side of the next such definition. This measure allows us to reuse variable names. A slight modification of our example demonstrates the effect of variable scopes in SaC:
Here, the use of a on the righthand side of line 9 still refers to the definition of line 6, whereas the use in line 11 refers to the definition in line 10.
The definition in line 13 shows, how variable scopes can be used to specify code that looks very much “imperative”. However, you should always keep in mind, that in SaC, the placeholder property always holds!
Exercise 4.
What result do you expect from the following SaC program?
2.2 Lesson 2: ShapeInvariant Programming
The term shapeinvariant programming refers to a programming style where all array operations are defined in terms of operations that are applied to entire arrays rather than to individual array elements. In order to realize such a programming style, it is an essential prerequisite to be able to apply functions to arbitrarily shaped arguments. In SaC, this is the case.
All builtin array operations as well as all array operations supplied by the standard library can be applied to arguments of arbitrary shapes. However, most of the operations that require more than one argument do have certain restrictions with respect to which array shapes can be combined as valid arguments. If an operation is applied to a set of arguments whose shapes constitute an illegal combination, usually, a type error message is given. In cases where this cannot be decided statically, the compiler may accept such a kind of domain error and produce a runtime error instead.
This lesson consists of three parts: The section on Standard Array Operations introduces the most important standard array operations provided by the current SaC compiler release^{1}^{1}As of this writing, the latest SaC compiler release is version 1.2.. The next section explains Axis Control Notation, a powerful but simple way of manipulating the focus of array operations with respect to individual axes of argument arrays. With the axiscontrol notation, the basic operations often can easily be combined into rather complex operations as demonstrated in the section on Putting it all Together.
2.2.1 Standard Array Operations
In the sequel, several toy examples demonstrate the functionality of the most basic array operations that come as part of the current SaC release. Their design is inspired by those available in APL. However, several aspects — in particular regarding the treatment of special cases in APL — have been adjusted to allow for a more favourable compilation in SaC that yields better runtime performance.
A note for language design freaks: You may have your own ideas on what primitive array operations should be available and how the precise semantics of these should look like. Therefore, it should be mentioned here, that all array operations introduced in the remainder of this section are not hardwired into the language, but they are defined in the module Array from the standard library. This is to say that the advanced SaC programmer may write his own set of standard array operations.
The individual parts of this section are all organized according to the following scheme: first, a semiformal introduction to the functionality of individual operations is given. Then, several examples shed some more light on the exact semantics of each operation by varying the argumentshape constellations and by exploring “borderline cases” with respect to domain restrictions if these do exist‘.
Basic Operations
The most basic operations are very close to the model of arrays in SaC. They comprise functions for inspecting, creating, and modifying an array’s shape and content. If not stated otherwise, they are applicable to arbitrarily shaped arguments of builtin element type. Note here, that some of them have been introduced in earlier lessons already.
 dim(a)

returns the (scalar) dimensionality of the argument array a.
Domain restrictions: none.  shape(a)

returns the shape vector of the argument array a.
Domain restrictions: none.  a[iv]

constitutes a shortcut notation for sel(iv, a). It selects the array element of a at index position iv. As a may be of any shape, the index position is given as an index vector. The dimensionality of the result is identical to the dimensionality of a minus the length of iv. Accordingly, its shape is derived from the last components of the shape of a.
Domain restrictions:
–
dim(iv) == 1

–
shape(iv)[[0]] <= dim(a)

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{shape}\text{(}\text{iv}\text{)[[0]]}\}:\text{iv}\text{[[}\text{i}\text{]]}\text{}\text{}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$.

–
 a[iv]=expr

is a shortcut notation for an assignment of the form a = modarray(a, iv, expr). The result of this application is a new array which is almost identical to a. Only the element (subarray) at index position iv is different; it is replaced by expr.
Domain restrictions:
–
dim(iv) == 1

–
shape(iv)[[0]] <= dim(a)

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{shape}\text{(}\text{iv}\text{)[[0]]}\}:\text{iv}\text{[[}\text{i}\text{]]}\text{}\text{}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
shape(expr) == shape(a[iv]).

–
 reshape(shp, expr)

computes an array with shape vector shp and data vector identical to that of expr.
Domain restrictions:
–
dim(shp) == 1

–
$\prod _{i=0}^{\text{shape}\text{(}\text{shp}\text{)[[0]]1}}\text{shp}\text{[[}\text{i}\text{]]}=\prod _{i=0}^{\text{dim}\text{(}\text{expr}\text{)1}}\text{shape}\text{(}\text{expr}\text{)[[}\text{i}\text{]]}$.

–
 genarray(shp, expr)

generates an array of shape shp, whose elements are all identical to expr.
Domain restrictions: dim(shp) == 1.
Although these operations are fairly selfexplaining or known from Lesson 2.1 on Arrays as Data, let us have a look at a few example applications:
The different selections in lines 1113 show how the dimensionality of the selected element increases as the length of the index vector decreases. If the index vector degenerates into an empty vector, the entire array is selected. Similarly, the applications of modarray in lines 1520 demonstrate the successive replacement of individual elements, rows, or the entire array.
Lines 2227 are meant to draw the reader’s attention to the fact that there exists an unlimited number of distinct empty arrays in SaC!
Exercise 5.
Assuming mat to be defined as in the previous example, what results do you expect from the following expressions:

•
([3,0,5], [])[[]]?

•
([3,0,5], [])[[1]]?

•
([3,0,5], [])[[1,0]]?

•
mat[reshape([2,0], [])]?
Elementwise Extensions
Most of the operations that can be found as standard operations on scalars in other languages are applicable to entire arrays in SaC. Their semantics are simply elementwise extensions of the wellknown scalar operations. The binary operations in general do have some domain restrictions. First, the element types of both arguments do have to be identical. Furthermore, either one of the arguments has to be a scalar value, or both arguments have to have identical shapes. In the former case, the value of the scalar argument is combined with each element of the (potentially nonscalar) other argument, which dictates the shape of the result. The latter case results in an array of the same shape as both arguments are, with the values being computed from the corresponding elements of the argument arrays.
In detail, the following operations are available:
 arithmetic operations

including addition (${e}_{1}$ + ${e}_{2}$), subtraction (${e}_{1}$  ${e}_{2}$), negation (${e}_{1}$), multiplication (${e}_{1}$ * ${e}_{2}$), and division (${e}_{1}$ / ${e}_{2}$). Furthermore, a modulo operation (${e}_{1}$ % ${e}_{2}$) is supported on integer numbers.
Domain restrictions: the element types of ${e}_{1}$ and ${e}_{2}$ have to be of the same numerical type.  logical operations

including conjunction (${e}_{1}$ && ${e}_{2}$), disjunction (${e}_{1}$  ${e}_{2}$), and negation (!${e}_{1}$).
Domain restrictions: the element types have to be Boolean.  relational operations

including lessthan (${e}_{1}$ < ${e}_{2}$), lessorequal (${e}_{1}$ <= ${e}_{2}$), equal (${e}_{1}$ == ${e}_{2}$), notequal (${e}_{1}$ != ${e}_{2}$), greaterorequal (${e}_{1}$ >= ${e}_{2}$), and greaterthan (${e}_{1}$ > $e2$).
Domain restrictions: the element types of ${e}_{1}$ and ${e}_{2}$ have to be of the same type.  max (${e}_{1}$, ${e}_{2}$), min (${e}_{1}$, ${e}_{2}$)

compute the elementwise maximum and minimum, respectively.
Domain restrictions: the element types of ${e}_{1}$ and ${e}_{2}$ have to be of the same type.  where (p, ${e}_{1}$, ${e}_{2}$)

is an elementwise extension of a conditional. It expects $p$, ${e}_{1}$, and ${e}_{2}$ either to have identical shapes or to be scalar. If at least one of the three arrays is nonscalar, that shape serves as shape of the result, whose values are taken from ${e}_{1}$ or ${e}_{2}$ depending on the value (s) of $p$.
Domain restrictions:
–
the element type of $p$ has to be boolean

–
the element types of ${e}_{1}$ and ${e}_{2}$ have to be identical

–
$\exists \text{shp}:((\text{shape}\text{(}\text{p}\text{)}\text{}\text{==}\text{}\text{shp}\vee \text{shape}\text{(}\text{p}\text{)}\text{}\text{==}\text{}\text{[]})\wedge (\text{shape}\text{(}\text{e\_1}\text{)}\text{}\text{==}\text{}\text{shp}\vee \text{shape}\text{(}\text{e\_1}\text{)}\text{}\text{==}\text{}\text{[]})\wedge (\text{shape}\text{(}\text{e\_2}\text{)}\text{}\text{==}\text{}\text{shp}\vee \text{shape}\text{(}\text{e\_2}\text{)}\text{}\text{==}\text{}\text{[]}))$.

–
Again, these operations are fairly selfexplanatory. Nevertheless, we present a few examples:
The most interesting part of this example is the definition of the matrix mat2 in line 11. The even numbers from the matrix mat are taken as they are, whereas the odd numbers are negated. Note here, that all sub expressions in predicate position are in fact nonscalar arrays: (mat \% 2) denotes a matrix of zeros and ones and (mat \% 2) == denotes a matrix of boolean values.
Exercise 6.
What results do you expect from the following expressions:

•
min(reshape([3,0,5], []), 42)?

•
reshape([3,0,5], []) + reshape([3,0,5], [])?

•
reshape([1,1], [1]) + reshape([1], [1])?
Restructuring Operations
The operations to be introduced here do not compute new values at all. Instead, they are meant to create slightly differently structured arrays from existing ones. Therefore, they are applicable to arrays of all builtin element types.
 take(sv, a)

takes as many elements from the array a as indicated by the shape vector sv. Each element of sv corresponds to one axis of a starting from the leftmost one. For positive components of sv, the elements are taken from the “beginning”, i.e. starting with index 0, otherwise they are taken from the “end” including the maximum legal index of the corresponding axis. All axes of a where there exists no corresponding element in sv are taken entirely.
Domain restrictions:
–
dim(sv) == 1

–
shape(sv)[[0]] <= dim(a)

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{shape}\text{(}\text{sv}\text{)[[0]]}\}:\text{sv}\text{[[}\text{i}\text{]]}\text{}\text{=}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
 drop(sv, a)

drops as many elements from the array a as indicated by the shape vector sv. Each element of sv corresponds to one axis of a starting from the leftmost one. For positive components of sv, the elements are dropped from the “beginning”, i.e. starting with index 0, otherwise they are dropped from the “end” starting from the maximum legal index of the corresponding axis. All axes of a where there exists no corresponding element in sv are left untouched.
Domain restrictions:
–
dim(sv)= 1

–
shape(sv)[[0]] <= dim(a)

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{shape}\text{(}\text{sv}\text{)[[0]]}\}:\text{sv}\text{[[}\text{i}\text{]]}\text{}\text{=}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
 tile(sv, ov, a)

takes a tile of shape sv from a starting at the index specified by the offset vector ov. For axes where no values of sv or ov are specified these are assumed to be identical to the extent of a along that axis or 0, respectively.
Domain restrictions:
–
dim(sv) == dim(ov) == 1

–
shape(sv)[[0]] <= dim(a)

–
shape(ov)[[0]] <= dim(a)

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{shape}\text{(}\text{ov}\text{)[[0]]}\}:\text{ov}\text{[[}\text{i}\text{]]}\text{}\text{=}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
$\forall \text{i}\in \{0,\mathrm{\dots},\text{min}\text{(}\text{shape}\text{(}\text{ov}\text{)[[0]],}\text{}\text{shape}\text{(}\text{sv}\text{)[[0]])}\}:\text{ov}\text{[[}\text{i}\text{]]}\text{}\text{+}\text{}\text{sv}\text{[[}\text{i}\text{]]}\text{}\text{=}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
$\forall \text{i}\in \{\text{min}\text{(}\text{shape}\text{(}\text{ov}\text{)[[0]],}\text{}\text{shape}\text{(}\text{sv}\text{)[[0]])},\mathrm{\dots},\text{shape}\text{(}\text{sv}\text{)[[0]]}\}:\text{sv}\text{[[}\text{i}\text{]]}\text{}\text{=}\text{}\text{shape}\text{(}\text{a}\text{)[[}\text{i}\text{]]}$

–
 ${e}_{1}$ ++ ${e}_{2}$

concatenates arrays ${e}_{1}$ and ${e}_{2}$ with respect to the leftmost axis. As in SaC all arrays are homogeneous, this requires all but the leftmost axis to be of identical extent.
Domain restrictions:
–
${e}_{1}$ and ${e}_{2}$ have to be of identical element type

–
drop(1, shape(${e}_{1}$)) == drop(1, shape(${e}_{2}$)).

–
 rotate(ov, a)

rotates the array a with respect to those axes specified by the offset vector ov. Starting from the leftmost axis, the elements of ov specify by how many positions the elements are rotated towards increasing indices (positive values) or towards decreasing indices (negative values). Domain restrictions:

–
dim(ov) == 1

–
shape(ov)[[0]] <= dim(a)

–
 shift(ov, expr, a)

shifts the array a with respect to those axes specified by the offset vector ov. The element positions that become “void” are filled by the (scalar) default element expr. Again, depending on the sign of the values of ov the elements are either shifted towards increasing or decreasing indices.
Domain restrictions:
–
dim(ov) == 1

–
shape(ov)[[0]] <= dim(a)

–
shape(expr)[[0]] == []

–
A few examples:
The applications of take in lines 1113 demonstrate, how the dimensionality of mat remains unaffected by the length of the first argument. Only the shape of the result and the “side” from which the elements are taken is defined by it.
The applications in lines 1517 demonstrate how empty arrays are dealt with in the individual argument positions. In particular from the example in line 17 it can be seen how well the concept of having an unlimited number of different empty arrays available fits nicely into the overall framework.
The remaining examples are rather straightforward. The only aspect of interest here may be the “overflows” in the rotation and shift parameters in lines 24 and 28, respectively.
Exercise 7.
Which of the following expressions can be reformulated in terms of take, ++, and the basic operations defined in the previous parts?

•
drop (v, a)?

•
tile (v, o, a)?

•
shift ([n], e, a)?

•
shift ([m,n], e, a)?

•
rotate ([n], a)?

•
rotate ([m,n], a)?
Can we define the general versions of shift and rotate as well?
Reduction Operations
The library of standard array operations that comes with the current SaC release also contains a set of functions that fold all (scalar) elements of an array into a single one. The most common ones of these are described here.
 sum(a)

sums up all elements of the array a. If a is an empty array, is returned.
Domain restrictions: the element type has to be numerical.  prod(a)

multiplies all elements of the array a. If a is an empty array, 1 is returned.
Domain restrictions: the element type has to be numerical.  all(a)

yields true, iff all elements of a are true. If a is an empty array, true is returned.
Domain restrictions: the element type has to be boolean.  any(a)

yields true, iff at least one element of a is true. If a is an empty array, false is returned.
Domain restrictions: the element type has to be boolean.  maxval(a)

computes the maximum value of a. If a is an empty array, the minimal number of the according element type is returned.
Domain restrictions: the element type has to be numerical.  minval(a)

computes the minimum value of a. If a is an empty array, the maximal number of the according element type is returned.
Domain restrictions: the element type has to be numerical.
A few examples:
Most of these examples, again, are fairly self explanatory. However, you may get an idea of the specificational advantages of shapeinvariant programming when having a closer look at lines 12 and 13. They demonstrate the rather intuitive style of program specifications that results from it.
Exercise 8.
All operations introduced in this part apply to all elements of the array they are applied to. Given the array operations introduced so far, can you specify rowwise or columnwise summations for matrices? Try to specify these operations for a 2 by 3 matrix first.
2.2.2 Axis Control Notation
As can be seen from Exercise 8, without further language support, it is rather difficult to apply an array operation to certain axes of an array only. This section introduces two language constructs of SaC which, when taken together, can be used to that effect. While Generalized Selections are convenient for separating individual axes of an array, Set Notations allow to recombine such axes into a result array after applying arbitrary operations to them. However, as the two constructs in principle are orthogonal, we introduce them separately before showing how they can be combined into an instrument for Axis Control.
Generalized Selections
The selection operation introduced in Section 2.2.1 does not only allow scalar elements but entire subarrays of an array to be selected. However, the selection of (nonscalar) subarrays always assumes the given indices to refer to the leftmost axes, i.e. all elements with respect to the rightmost axes are actually selected. So far, a selection of arbitrary axes is not possible. As an example usecase consider the selection of rows and columns of a matrix. While the former can be done easily, the latter requires the array to be transposed first.
To avoid clumsy notations, SaC provides special syntactical support for selecting arbitrary subarrays called Generalized Selections. The basic idea is to indicate the axes whose elements are to be selected entirely by using dotsymbols instead of numerical values within the index vectors of a selection operation.
Note here, that vectors containing dotsymbols are not first class citizens of the language, i.e. they can exclusively be specified within selection operations directly!
There are two kinds of dotsymbols, singledots which refer to a single axis and tripledots which refer to as many axes as they are left unspecified within a selection. In order to avoid ambiguities, a maximum of one tripledot symbol per selection expression is allowed.
A few examples:
The examples in lines 1113 demonstrate different versions for selecting the second row of the matrix mat. However, as the rightmost axis is to be selected, a dotfree version (cf. line 11) suffices for this task. The selection of the second column of mat is shown in lines 15 and 16.
line 18 demonstrates that the tripledot notation can also be successfully applied if no axis can be matched at all.
The difference between the singledot and the tripledot notation is shown in lines 23 and 24. While the selection in line 23 is identical to arr3d[[.,1,.]], the one in line 24 is identical to arr3d[[.,.,1]].
Only in cases where the number of singledots plus the number of numerical indices exceeds the number of axes available, an error message will be generated.
Exercise 9.
How can a selection of all elements of mat be specified using generalized selections? Try to find all 9 possible solutions!
Exercise 10.
Referring to Exercise 5, can this new notation be used for selecting “over” empty axis? For example, can you specify a selection vector $\u27e8\text{vec}\u27e9$, so that reshape([3,0,5], [])[vec] == reshape ([3,0], []) holds?
Set Notation
The means for composing arrays that have been described so far are rather restricted. Apart from elementwise definitions all other operations treat all elements uniformly. As a consequence, it is difficult to define arrays whose elements differ depending on their position within the array. The socalled set notation facilitates such position dependent array definitions. Essentially, it consists of a mapping from index vectors to elements, taking the general form
$$\u27e8\text{index\_vector}\u27e9\text{>}\u27e8\text{expression}\u27e9$$ 
where $\u27e8\text{index\_vector}\u27e9$ either is a variable or a vector of variables and $\u27e8\text{expression}\u27e9$ is a SaC expression that refers to the index vector or its components and defines the individual array elements. The range of indices this mapping operation is applied to usually can be determined by the expression given and, thus, it is not specified explicitly.
A note for language design freaks: You may wonder why we restrict the expressiveness of the set notation by relying on compiler driven range detection rather than an explicit range specification. The reason for this decision is the observation that in many situations the capabilities of the set notation suffice whereas an explicit specification of ranges would obfuscate the code. Furthermore, as you will see in Chapter 4, SaC provides a more versatile language construct for defining arrays. However, the expressiveness of that construct comes for quite some specificational overhead.
Let us have a look at some examples:
The set notation in line 8 defines a vector whose components at position [i] are vectors that are computed from adding a multiple of 1 to the vector vect. The legal range of i is derived from the selection vect[[i]] yielding in fact a matrix with shape [10,10]. An explicit elementwise increment operation is specified in line 11. Since the operation does not need to refer to individual axes a variable iv is used for the entire index vector rather than having variables for individual index components. Line 14 shows how the matrix can be transposed, and line 17 changes all nondiagonal elements to .
Exercise 11.
Which of these operations can be expressed in terms of the array operations defined so far?
Exercise 12.
What results do you expect if mat is an empty matrix, e.g. reshape([10,0], [])?
As we can see from the set notation in line 8, nonscalar expressions within the set notation per default constitute the inner axes of the result array. This can be changed by using ‘.’ symbols for indicating those axes that should constitute the result axis.
A few examples:
These examples show how the result of evaluating the expression on the right of the arrow can be directed into any axes of the overall result array. As can be seen in line 17, the axes of the expressions can even be put into nonadjacent axes of the result.
Exercise 13.
The ‘.’ symbol in the set notation allows us to direct a computation to any axes of the result. This is identical to first putting the result into the innermost axes and then transposing the result. Can you come up with a general scheme that translates set notations containing ‘.’ symbols into set notations that do without?
Axis Control
Although generalized selections and the set notation per se can be useful, their real potential shows when they are used in combination. Together, they constitute means to control the axes a given operation is applied to. The basic idea is to use generalized selections to extract the axes of interest, apply the desired operation to the extracted subarrays and then recombine the results to the overall array.
For example, we can now easily sum up the individual rows or columns of a matrix:
Reduction operations, in general, are prone to axis control, as they often need to be applied to certain particular axes rather than entire arrays. Other popular examples are the maximum (maxval) and minimum (minval) operations:
In line 8, we directly generate a 3 dimensional array from the vector vect. Lines 11, 14, and 17 compute maxima within different slices of that array. max_inner_vects is a matrix containing the maxima within the innermost vectors, i.e. the 3dimensional array is considered a matrix of vectors whose maximum values are computed. For max_inner_arrays, the array is considered a vector of matrices; it contains the maximum values of these subarrays. The last example demonstrates, that outer dimensions can be considered for reduction as well.
Further demand for axis control arises in the context of array operations that are dedicated to one fixed axis (usually the outermost one) and that need to be applied to another one. Examples for this situation are the concatenation operation (++) and reverse:
Line 11 shows a standard application of the concatenation of two arrays. It affects the outermost axis only, resulting in an array of shape [8, 0, 0]. The two subsequent lines show, how to apply concatenation to other axis. Essentially, the selections on the right hand sides select the sub expressions to be concatenated and the surrounding set notation glues the concatenated subarrays back together again.
The examples in lines 1517 show the same exercise for the operation reverse which reverses the order of the elements within an array with respect to the outermost axis.
Exercise 14.
The operation take is defined in a way that ensures inner axes to be taken completely in case the take vector does not provide enough entities for all axes. How can take be applied to an array so that the outermost axis remains untouched and the selections are applied to inner axes, starting at the second one? (You may assume, that the take vector has fewer elements than the array axes!) Can you specify a term that — according to a take vector of length 1 — takes from the innermost axis only?
Exercise 15.
Can you merge two vectors of identical length elementwise? Extend your solution in a way that permits merging $n$dimensional arrays on the outermost axis.
2.2.3 Putting it all Together
The array operations presented so far constitute a substantial subset of the functionality that is provided by array programming languages such as APL. When orchestrated properly, these suffice to express rather complex array operations very concisely. In the sequel, we present two examples that make use of this combined expressive power: matrix product and relaxation.
Matrix Product
The matrix product of two matrices $A$ and $B$ (denoted by $A\odot B$) is defined as follows:
Provided $A$ has as many columns as $B$ has rows, the result of $A\odot B$ has as many rows as $A$ and as many columns as $B$. Each element ${(A\odot B)}_{i,j}$ is defined as the scalar product of the $i$th row of $A$ and the $j$th column of $B$, i.e. we have ${(A\odot B)}_{i,j}={\sum}_{k}{A}_{i,k}*{B}_{k,j}$.
This definition can directly be translated into the following SaC code:
After defining two matrices id and mat in lines6 and 8, respectively, the matrix product id $\odot $ mat is specified in line 12. id[[i,.]] selects the ith row of id and mat[[.,j]] refers to the jth column of mat. The index ranges for i and j are deduced from the accesses into id and mat, respectively. A variable $k$ as used in the mathematical specification is not required as we can make use of the array operations * and sum.
Relaxation
Numerical approximations to the solution of partial differential equations are often made by applying socalled relaxation methods. These require large arrays to be iteratively modified by socalled stencil operations until a certain convergence criterion is met. Fig. 2.1 illustrates such a stencil operation.
A stencil operation recomputes all elements of an array by computing a weighted sum of all neighbor elements. The weights that are used solely depend on the positions relative to the element to be computed rather than the position in the result array. Therefore, we can conveniently specify these weights by a single matrix of weights as shown on the left side of Fig. 2.1.
In this example, only 4 direct neighbor elements and the old value itself are taken into account for computing a new value. (Hence its name: 5pointstencil operation). As can be seen from the weights, a new value is computed from old ones by adding an eightth each of the values of the upper, lower, left, and right neighbors to half of the old value.
As demonstrated on the right side of Fig. 2.1 our example assumes socalled cyclic boundary conditions. This means that the missing neighbor elements at the boundaries of the matrix are taken from the opposite sides as indicated by the elliptic curves.
In the sequel, we concentrate on the specification of a single relaxation step, i.e. on one recomputation of the entire array. This can be specified as a single line of SaC code:
Line 6 defines the array of weights as given on the left side of Fig. 2.1. Our example array is initialized in lines 8–9. The relaxation step is specified in line 12. At its core, all elements are recomputed by operations on the entire array rather than individual elements. This is achieved by applying rotate for each legal index position iv into the array of weights weights. Since the expression {iv > weights[iv] * rotate(iv1, mat)} computes a 3 by 3 array of matrices; the reduction operation sum needs to be directed towards the outer two axes of that expression only. This is achieved through axis control using a selection index [\dots,i,j] within a set notation over i and j.
Exercise 16.
Another variant of relaxation problems requires the boundary elements to have a fixed value. Can you modify the above solution in a way that causes all boundary elements to be 0? [Hint: You may consider the boundary elements to actually be located outside the matrix]
Chapter 3 Basic Program Structure
This trail gives a brief introduction into the main language constructs most of which have been adopted from standard C. We assume some familiarity with standard C and, therefore, only give a quick overview and highlight the differences between SaC and C.
3.1 Lesson 3: Functions and their Types
3.1.1 Function Definitions
Like in other modern programming languages functions constitute the main form of structuring programs in SaC. SaC functions very much resemble their C counterparts. The most prominent difference is that SaC functions can have multiple return values, as illustrated in the following example.
A function with multiple return values, like divmod in the above example, has a commaseparated list of return types in front of the function name and the returnstatement likewise contains a commaseparated list of expressions. Obviously both lists must coincide in length to make up a wellformed program. Functions with multiple return values cannot appear in expression positions in SaC, but their results need to be directly assigned to identifiers as illustrated above.
Exercise 17.
Extend the above example program to compute the greatest common denominator of two numbers using Euclid’s algorithm. In particular, use the function divmod.
Exercise 18.
What happens, if you use the same variable name for both results of divmod?
3.1.2 Builtin Types
SaC supports all basic types of standard C such as int, float, double, char etc.
A note for bit freaks: All basic types are mapped onetoone to their C counterparts and, hence, the same rules apply to them in SaC as in C. As a consequence of this, the concrete bit widths used for representation and, hence, the range of values for integer types are platformdependent. Although this may be considered undesirable we find it acceptable from a compatibilitywithC perspective.
In addition to the Cinhereted types, SaC supports three more basic types: the boolean type bool and the integer type byte, both signed and unsigned. Although these are internally mapped to the same C type, on the level of SaC, there is a strict separation between them. Neither can be used in places where the other is expected. This separation also applies to the standard C types which rules out tacit coercions as one would find them in C or Java.
A note for language design freaks: The reader may wonder why we enforced this strict separation. The reason is twofold: First, it prevents from accidental coercions and second, it makes typeinference more accessible for the user in the absence of explicit type declarations. Just imagine an overloading of a function foo for integer and double arguments which would yield different results depending on the type of argument. If we had implicit coercions in place it would be completely unclear how the result of foo(0) would be computed!
As a consequence of this strict separation, programmers need to apply some rigor when it comes to specifying constant values. They have to be attributed with the appropriate suffixes to indicate the desired runtime representation. Note here, that we adopted the suffixes and default rules from C. Here a few examples:
Exercise 19.
How can you modify the above program in a way that allows the programmer by a simple define to switch the argument type of foo between float and double and all the calls to foo accordingly?
[Hint: Use the C preprocessor to make the necessary modifications]
3.1.3 Subtyping
For each basic type there is an entire hierarchy of array types that specify the shape of an array (remember that any expression in SaC denotes an array) at different levels of accurateness. Using type int as a running example, int itself denotes an integer array with rank zero, the empty vector [] as shape vector and a single element, in other words the equivalent of a scalar value. Then, there are (real) array types denoting arrays of rank greater than zero, e.g. int[4] denotes a 4element vector while int[10,20] denotes a 10 by 20 element matrix.
Whereas all these types specify exact shapes, SaC also features types that solely denote the rank of some array, but leave the concrete shape open, e.g. int[.] describes the type of all integer vectors (of any length) and int[.,.] is the type of all integer matrices. In order to support rankinvariant programming, SaC, furthermore, has types that not only abstract from concrete shapes but even from concrete ranks. These are int[*] which is the type of all integer arrays of any rank and shape, including rankzero arrays (usually referred to as scalars) and int[+], the type of all “true” integer arrays, i.e. arrays of rank greater than zero.
SaC defines a subtype relationship between array types in the obvious way. Figure 3.1 shows this relationship for arrays of integer elements in a graphical form.
Whenever two types are in subtype relationship they are connected by a line. For example, int[+] is a subtype of int[*], int[.] and int[.,.] are both subtypes of int[+] and int[12] and int[42] are subtypes of int[.]. As we can see, the subtyping hierarchy of SaC has exactly four levels.
3.1.4 Function Overloading
The real power of subtyping unfolds when it is combined with function overloading. It allows programmers to specify multiple functions of the same name, as long as they differ in the types or their arguments. Which definition is chosen for any given application of such a function depends on the type of the actual arguments. This combines a high degree of code reuse with the ability to later add special definitions for a few special cases.
A note for OOfreaks: This can be seen as a more general form of inheritance. If you restrict overloading to one argument only, say the first one, it equates to inheritance in OO languages. However, the overloading of SaC is much more powerful. Not only does it support inheritance on all arguments but it also supports overloading across different types. These features render several of the wellknown OO programming pattern such as the visitor pattern superfluous in SaC. Instead, the desired overloading can be specified directly.
Here, an example for elementtype overloading:
When utilising the overloading on our hierarchy of array types we can even achieve a pattern matching like programming style as demonstrated in the next example. Here, we have three instances of the function quicksort, one for vectors of any length, one for vectors of length one and one for empty vectors. The latter two boil down to the identity function. As a result we can safely access the first element of the argument vector v in the general instance because any argument vector is guaranteed to have at least two elements.
Exercise 20.
In a C program, functions like + can be applied to arbitrary combinations of integer and double arguments. Try to mimic that behaviour in SaC by defining a function cPlus and by overloading it appropriately.
Exercise 21.
In OO languages inheritance cannot always be statically resolved. This leads to what is referred to as dynamic dispatch, i.e. the disambiguation of function calls at runtime. Is that required in SaC too? If so, can you come up with an example program that demonstrates this?
3.2 Lesson 4: Function Bodies
3.2.1 Variable Declarations
Local variables within bodies of SaC functions are typically not declared (in contrast to C), but the SaC compiler infers proper types for local variables or yields an appropriate error message. Nevertheless, it is syntactically legal to add explicit variable declarations in SaC in exactly the same way as in C.
There is one difference to C, however: While C allows local variable declarations at the beginning of each code block and in the latest C99 standard instructions and declarations can even be interleaved, SaC only supports variable declarations on the level of function bodies, and they must precede any instruction.
Exercise 22.
Rewrite your solution to computing the greatest common denominator of two numbers from the previous exercise such that each subexpression is assigned to an identifier, i.e. flatten any nested expression. Then add explicit variable declarations for each local variable used.
Exercise 23.
The previous exercise only used scalar types, more precisely int. What happens if you replace int in all variable declarations by its supertype int[*]?
3.2.2 Assignments
As we have already seen in the previous trails, SaC allows for Cstyle assignments to variables. In contrast to C, assignments cannot be placed within expression positions and the commaoperator of C is not supported. However, the combinations of operators and assignment are the same in SaC as in C
Note that despite the term “Single Assignment” in the name of SaC, the language actually supports repeated assignment of values to the same variable as in the above example. This seeming contradiction can be explained as follows: Each assignment opens up a new scope of an identifier bound to some value. Accordingly, the second assignmnent to a in the above example opens up a new scope for a new identifier a that only coincidentally carries the same name as the identifier introduced in the code line before. However, because these two variables do carry the same name, the second assignment shadows the scope of the first assignment meaning that no access to the first a is possible any more.
Another aspect to notice here is that these operatorassignment combinations in SaC can be used on arbitrary types. Line 17 is an example for this flexibility. The variable v is of type int[5] and thus += works on vectors. The way this works is that all these operator assignment cases are considered syntactic sugar for assignements with function applications on the righ hand side.
This syntacticsugar trick also enables very Clike notations when denoting applications of the function modarray. Line 19 shows an example.
Exercise 24.
Starting from the code in Listing 25, what happens when you combine the above shortcut notations? Try operator assignments such as v[0]++ or m[0][0] = 42;.
Can you define a function f that makes the following operator assignment legal SaC code: v[1], m[1] +=f();?
3.2.3 Conditionals
In SaC, we support three forms of conditionals:

•
branching with consequence only (ifthen),

•
branching with consequence and alternative (ifthenelse) and

•
conditional expressions.
All three forms use a syntax that is identical to that of C, as the following listing illustrates. Similarity with C extends to the use of curly brackets to build blocks of multiple statements and their potential absence if the condition covers a single statement only
As in C all forms of conditionals can be nested in any way, and the dangling else ambiguity is resolved as in C proper.
A small difference to standard C is that the predicate expression of any conditional must be of type bool. There is no implicit treatment of integer values as predicates. Another subtle difference to C stems from the functional nature of SaC: a variable defined only in one branch of a conditional, will cause the SaC compiler to raise an error because the value may be undefined.
The switchstatement of C is currently not supported by SaC. This is not so much motivated by conceptual concerns, but rather by pragmatic considerations like the ratio between expressiveness gained and implementation effort caused.
3.2.4 Loops
SaC supports all three loop constructs of standard C: while, do and for with the familiar syntax, as illustrated by the following code fragment.
In analogy to conditionals, the loop predicate expression must be of type bool. Note that SaC does even support the comma operator in forloops (though not in general terms as pointed out before).
These Cstyle loop constructs can make code look very imperative. Despite these syntactic similarities, always bear in mind that SaC loops are (only) syntactic sugar for equivalent tailend recursive functions. While the functional semantics almost completely coincides with the pragmatic expectations of a C programmer, some subtle issues may arise concerning the definedness of variables. For example, the SaC compiler would complain about the above example saying that the variable b in the whileloop may be used uninitialised if it is not defined before. This is because the compiler assumes that the body of a whileloop may not be executed at all. Of course, you may know better, but the SaC compiler at the moment makes no particular effort to prove this fact when it analyses the definedness of variables.
3.2.5 Explicit Control Flow Manipulation
The control flow manipulation statements of C, i.e. goto, break and continue, as well as labels are not supported by SaC. This is due to the fact that SaC is indeed a functional language and as such there is actually no control flow, even though the Clike syntax suggests one.
3.3 Lesson 5: Advanced Topics
3.3.1 Userdefined Types
SaC allows programmers to define their own types using a syntax that is identical to C.
Following the keyword typedef we have the defining type followed by the defined type name. Note that in contrast to C, defining type and defined type are not considered synonyms. Types like double[2] and complex are distinguished properly and a function that expects a value of type double[2] as an argument will not accept a value of type complex instead.
SaC requires explicit type casts to change the type of a value from the defining type to the defined type or vice versa as in the following example.
Note that for the time being any defining type in a type definition must exactly specify some shape; the various less specific types are not supported. While this looks incomplete at first glance, it is noteworthy that such type definitions would immediately lead to arrays of nonuniform shape, e.g. a matrix whose rows have different length. There is no doubt that this would be an extremely powerful extension to the homogeneously shaped arrays that SaC supports today, but it would likewise require a nontrivial extension of the code generator and runtime system that we leave for future research.
3.3.2 Type Conversions
SaC uses Clike cast expressions to change the type of an expression whenever the data representation remains unaffected, i.e. between userdefined types and their defining types or vice versa. In contrast to C, SaC does not use cast expressions to actually change data representations, e.g. when converting from an integer type to a floating point type, between floating point types of different precision or between integer types of different bit width. For all these purposes SaC uses dedicated conversion functions to express the fact that such conversions actually require an operation performed at runtime rather than just changing the type interpretation of a value.
These conversion functions are named tobool and tochar for converting into nonnumerical values. For all numerical types these functions are named “to” plus an optional “u” for unsigned integer types followed by the first letter of the type name (“ll” in the case of long long int). The following example illustrates type conversions in SaC.
Chapter 4 WithLoops
This trail aims at providing a handson introduction to the key language construct of SaC: the withloop. It constitutes the generalisation of the setexpression as introduced in the lesson 2.2 on ShapeInvariant Programming and can be seen as a shapeinvariant form of the mapreduce template or the array comprehensions found in other functional languages. However, in contrast to these, the withloop was carefully designed to enable radical code optimisations as well as compilation into highperformance, concurrently executable code.
A note for language design freaks: In fact, almost all array operations introduced in earlier trails are defined by withloops within the standard library. This design combines two major advantages: • better performance, as the conformity enables optimisations to be more generally applicable, and • increased flexibility, as the user can modify the definition of all standard operations.
The introduction of withloops comes in a single lesson which stepwise introduces all features and variants of withloops in SaC.
4.1 Lesson 6: withloop Basics
4.1.1 Basic Components
Generally, withloops are composed of three different components:

•
sets of index vectors (referred to as generatorranges),

•
functions that map index vectors to arbitrary values (generatorexpressions), and

•
combining operations (withloop operators) that take such values and construct arrays from them.
In its simplest form, a withloop contains one component of each kind. It then maps the function defined by the generatorexpression to all index vectors from the generatorrange in a dataparallel fashion. This leads to a set of indexvaluepairs which are combined into a result array by means of the given withloop operator. Let’s have a look at a simple example:
Here, the withloop in lines 6–8 computes the vector [42, 42, 42, 42, 42, 0, 0]. The generatorrange is specified by the code snippet in round brackets in line 7: ([0] <= iv < [5]). It denotes the set of vectors $\{\text{[0],}\text{}\text{[1],}\text{}\text{\u2026,}\text{}\text{[4]}\}$. The generatorexpression here is the constant 42. Hence, the mapping function ${f}_{\text{map}}$ maps any index vector iv into 42, i.e. we have ${f}_{\text{map}}\text{(}\text{iv}\text{)}\text{}\text{=}\text{}\text{42}$. Finally, the withloop operation is specified as genarray([7], 0). This operation computes an array of shape [7] where:
$$\text{a}\text{[}\text{iv}\text{]}=\{\begin{array}{cc}{f}_{\text{map}}\text{(}\text{iv}\text{)}\hfill & \text{iv}\in \{\text{[0],}\text{}\text{[1],}\text{}\text{\u2026,}\text{}\text{[4]}\}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$ 
Generatorranges and generatorexpressions always occur in pairs. Jointly they form a syntactical unit, which we referto as generator. As we will see later, withloops can contain arbitrary numbers of generators. They are enclosed in curly brackets.
Exercise 25.
What result do you expect if we eliminate the generator from the above example?
What results do you expect if we modify the generatorrange in the above example into:

•
([2] <= iv < [3])?

•
([0] <= iv < [8])?

•
([6] <= iv < [5])?

•
([8] <= iv < [5])?

•
([6] <= iv < [0])?
[Hint: You should compile these examples with the option check c being enabled]
4.1.2 Generator Ranges
SaC offers quite some flexibility when it comes to specifying generator ranges. First of all, the use of index vectors in the bounds enables the convenient specification of $n$dimensional index ranges. Let us look at a few examples for the 2dimensional case:
As we can see from the first withloop in lines 6–8, a vector of scalar indices can be used where we previously used the variable iv to denote the entire index vector. In cases where the dimensionality of the withloop is statically fixed, this sometimes comes in handy. However, if we want to adopt a more generic, shapeinvariant programming style, it becomes mandatory to use vectors for the index variable as well as for the bounds.
Note here, that the ability to use vectors rather than componentised indices and bounds is absolutely crucial here! It constitutes the enabling factor for specifying withloops in a shapeinvariant style as the length of those vectors may remain unknown until runtime. It is this particular feature that sets the withloops apart from most conventional language constructs for dataparallel array operations.
The withloop in lines 12–14 demonstrates a typical case where the dimensionality of the resulting array is solely determined by a vector (here shp). A slightly more elegant way for the most frequent case is the use of a syntactical shortcut supported by SaC. The symbol “.” can be used in the position for the lower and upper bound, denoting the lowest legal index and the highest legal index into the array to be created, respectively. This is examplified in the withloop in lines 17–19. Note here, that this generatorrange does not cover the entire legal index space of the resulting array! As the “.” always represents legal indices, we have to make sure that we use <= on both sides if we want to cover the entire range. The example presented here, excludes the extreme cases and, thus, covers all inner elements of the resulting array only.
Exercise 26.
What happens if the length of the vectors within the generatorrange or the shape expression in the genarrayoperation do not match? [Hint: You should compile these example with the option check c being enabled]
The withloop in lines 22–24 demonstrates how both, a vector version of the index vector and scalarised versions can be made available for the generatorexpression. It also examplifies that a mix of the .symbol and explicit expressions can be used for the bounds.
The remaining two withloops demonstrate the ability to specify rectangular grids of indices. The vector that follows the keyword step specifies the stride of the reoccurence pattern per axis. As a consequence, the withloop in lines 27–29 computes an array whose every fourth column is 42 starting with the very first one.
The use of the vector after the keyword width enables the programmer to denote more than one index per stepping period. The withloop in lines 27–29 computes a matrix where $1\times 2$ blocks of the value 42 are placed in the upper left corner of each $2\times 4$ grid of the resulting array.
Exercise 27.
Can you achieve the same result array as the last withloop of the above examples without using the step/width facility? [Hint: The solution may be surprisingly short!]
4.1.3 Generator Expressions
As we have seen in the previous sections, each generator expression implicitly defines a mapping function from indices to expressions. The parameters of these functions are derived from the index variables introduced in the associated generator range specifications. More complex generator expressions can be specified by assignment blocks that can be inserted between a generator range and the associated generator expression. Here a few examples:
The first withloop in lines 6–10 shows a typical scenario. The function divmod returns two values rather than just one. Rather than defining an explicit mapping function that passes on the desired return value, we can specify this selection directly.
The withloop in lines 13–15 demonstrates how nontrivial expressions can be used even without necessitating the introduction of an assignment block.
The scope of variables that are defined in such an assignment block is strictly local to that block. Such a variable can neither be referenced within other generators of the same withloop nor outside of the withloop. Note, however, that withloops can be arbitrarily nested. An example for such a nesting is shown in the withloop in lines 18–25 of the examples above.
Exercise 28.
What do you expect to happen, if a variable that is defined in such an assignment block has the same name as the index variable? Where is the “modified” version observable?
Why can the variable mval in the example above be safely replaced by i?
4.1.4 Reductions and further withloop Operations
Besides the genarray withloop operator described so far, SaC supports a few more. These are:

•
a modarray operator which “modifies” an existing array, and

•
two fold operators that enable the specification of reduction operations
The modarray variant is very similar to the genarray variant. The only difference is that neither the shape of the result nor a default element for unspecified index positions are explicit. Both of these are taken from a specified array that serves as a template. The second withloop in lines 11–13 of the example below demonstrates this. Here, a new array b is computed from the array a by negating each second element of a. As in lesson 2.1 on arrays as data, printing a in line 15 shows that in fact two different arrays have been created.
The two final examples demonstrate how reduction operations can be specified in SaC. The first variant (lines 17–19) is the standard variant for reductions. It requires the specification of a folding function (* in this case) and of a neutral element (1 here). As with the earlier variants, all index vectors from the generator range are mapped according to the generator expression. Subsequently all computed values are folded using the specified folding function. Note here, that no particular folding order is guaranteed! In order to obtain deterministic results on a multicore machine this requires the specified folding operation to be both, associative and commutative.
The final withloop in lines 22–24 is a slight variant of the fold version. It stems from the observation that some reductions can be shortcut when a certain fixpoint value has been met. In the given example of multiplication this is the value . Whether the underlying implementation makes use of this extra information or not is not specified. The computational result of both, the fold and the foldfix variant are the same, provided that the specified fixpoint value in fact constitutes one for the specified folding operation.
Chapter 5 Working with Modules
This chapter explains the basic principles of using modules in SaC. Prior to modules, a short introduction into SaC name spaces is given.
5.1 Name Spaces
In general, name spaces are used to extend the set of possible identifiers and thus inhibit potential name clashes. SaC supports multiple name spaces, although these are not explicitly defined by the programmer. Instead, every module and program has its own name space. The name space of a module is denoted by its name, a program uses main as its name space identifier. As an example of using name spaces consider Listing 34.
Instead of an import statement, a qualified function name is used. A qualified identifier always consists of a name space identifier, followed by a double colon and the unqualified identifier, in this case a function identifier. Besides of functions, fully qualified names may as well be used for types and global objects.
As it would be bothering to precede each identifier with the name space it belongs to, SaC supports multiple ways to automatically decide the right name space and generate a fully qualified identifier implicitly (or internally).
5.2 Use Statements
To simplify the use of identifiers from other modules, SaC allows us to specify a search space whose identifiers can be used in an unqualified fashion. By default, this search space contains all identifiers from the current name space. To add a complete name space to the current search space, you may use the statement use $\alpha $: all; where $\alpha $ gives the name of a name space. Using this technique, the hello world example can as well be expressed as follows:
However, an identifier is not allowed to have multiple occurrences within the search space as far as types and global objects are concerned. For function symbols the same holds modulo overloading based on parameter types.
To further avoid name clashes, SaC supports a more specific way to define search spaces. Instead of the keyword all, a comma separated list of identifiers can be given. The following version of hello world uses a more specific use statement:
In this example, only printf is made available to the search space and can thus be used without explicitly specifying its name space. In some occasions it can be useful to add all identifiers except a given set to the search space. Consider a module FastIO reimplementing all functions of StdIO. To use FastIO except the printf function, but StdIO::printf one might write:
This adds all identifiers from FastIO to the current search space except FastIO::printf. This allows the function printf to be imported from module StdIO.
5.3 Import statement
So far, we added identifiers to the search space of the SaC compiler to avoid explicitly specifying their name spaces each time they are referenced. As function signatures have to differ in number of arguments or their types, the use statement prevents overloading of functions by shape across module boundaries. In fact, SaC only supports overloading by shape within a single name space. Otherwise, the meaning of a fully qualified identifier could differ when being used in different scopes. To nonetheless allow for successive overloading in separate modules, SaC provides a mechanism for cloning functions using the import statement.
In this example, the statement import StdIO: {printf} creates a (conceptual) copy of the function printf in the current name space main. Consider a module foo containing a function int[*] bar(int[*]). This function can now be overloaded as follows:
Within the name space main there are two instances of bar, the one imported from foo and the one defined within main itself. Keep in mind, that there is a conceptual copy in main, so both are defined in main and so overloading can take place.
Be careful when importing types, as an imported type is regarded as different to its origin type by the type system as they were defined in different name spaces. However, you might still exchanges values between both types by means of a cast expression.
5.4 Putting It Together
Both types of module statements can be mixed in any possible way, as long as no name clash is introduced by them. Always keep in mind that an import statement adds all identifiers to the current name space and thus to the current search space, as well. The following example creates a name clash by using and importing the same identifier:
Here, printf is imported to the current name space, so there is an identifier main::printf, which is part of the compiler search space. Furthermore, the use statement adds the complete name space of module StdIO to the current name space, especially the identifier StdIO::printf. Thus there are two identifiers with the same unqualified name within the search space. To solve this, a restriction to the use statement can be used.
In this example, the identifier StdIO::printf is no longer added to the compiler search space and thus no name clash originates.
5.5 Implementing Modules
A SaC module implementation essentially looks just like a program, being a collection of type, global object and function definitions. Unlike a program, a module starts with the key word module followed by the module name, i.e. the name space, and a semicolon.
The more interesting aspect of a module (name space) is the question which symbols (types, global objects and functions) are made available outside the module and which are merely accessible internally within the module itself. Two kinds of statements using the key words provide and export provide finegrained control over the availability of symbols outside the current module. By default any symbol defined in a module is only accessible in the module itself. Using the provide statement all or selected symbols can be made available to be “used” by other modules or programs. With the export statement symbols are made available for either use or import by other modules or programs. The syntax of provide and export statements is very similar to that of the corresponding use and import statements. Either all symbols are provided/exported uniformly, or a specific list of symbols is concerned, or all but a given list of symbols.
Chapter 6 Case Studies
This trail will illustrate how to use SaC for realworld applications. The following exercises make use of the techniques introduced in this tutorial so far. Working through this trail shall give you some more handson experience with the language itself and at the same time show you how to employ SaC to solve your everyday problems in an efficient way.
6.1 Lesson 7: Image Processing
Digital image processing spans across a vast area of applications. Ranging from digital photography over astronomy to surgeryassisting medical imaging, most applications still share as their underlying theory some sort of basic signal processing on twodimensional (and potentially higherdimensional) signals. It is common to work with discretised signals, i.e. an approximation of the originally analogue, continuous version of the signal.
In this exercise we will focus on two basic image filters on static, twodimensional, 8bit grayscale images with a resolution of ${x}_{\text{max}}\times {y}_{\text{max}}$, such that an image is a 2D function
$S:\mathbb{N}\times \mathbb{N}$  $\to $  $\mathbb{N}$  
$S(x,y)$  $=$  $$ 
where $\forall x,y:0\le {v}_{xy}\le 255$. Informally speaking, the parameters $x$ and $y$ determine the position within the image and ${v}_{xy}$ determines the grayscale value of the pixel at this position.
A common technique to modify an image is to apply a filter of desired properties to it. In many cases, an image filter $F$ again is a two dimensional signal as the one described above. The application of a filter to an image is expressed by the 2D (discrete) convolution $F\otimes S$ of these two signals:
$F(x,y)\otimes S(x,y)$  $=$  $\sum _{j=\mathrm{\infty}}^{\mathrm{\infty}}}{\displaystyle \sum _{k=\mathrm{\infty}}^{\mathrm{\infty}}}F(j,k)S(xj,yk)$ 
With this simple form of filtering, a wealth of image modifications are expressible. Depending on the choice of the filter mask we can achieve effects such as smoothing, sharpening, edge detection, embossing and many more.
In SaC we can represent these signals as 2D arrays where $x$ and $y$ are the column and row indices and each element corresponds to one pixel. The application of a filter to an image may then be expressed using a stencil operation as it was introduced in an earlier part of this tutorial (Section 2.2): The filter mask is positioned with its center point over each pixel of the original image. At each position, the pixel value of the image and its corresponding value of the filter mask are multiplied. The pixel value at the same position in the result image is determined by the sum of these products (weighed sum).
Exercise 29.
The Sobel operator is an edgedetection filter that computes the gradient image from an input signal. The filtering process consists of three steps: In the first step, horizontal edges are detected, in the second step vertical edges are detected, and in the final step, both subresults are combined to the resulting gradient image. The first two steps are in fact two independent operations, each of which requires its own individual filter mask:
${F}_{x}=\left(\begin{array}{ccc}\hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 0\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$  ${F}_{y}=\left(\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 1\hfill \end{array}\right)$ 
Applying these two masks to an input image $S$ yields two subresults, one highlighting horizontal edges (${S}_{x}={F}_{x}\otimes S$), the other highlighting vertical edges (${S}_{y}={F}_{y}\otimes S$). We compute the final gradient image by adding the two subresults ${S}_{xy}={S}_{x}+{S}_{y}$. As ${S}_{xy}$ may contain elements with a value greater than $255$, we need to cap each pixel value at the maximum allowed value of $255$. See Fig. 6.1 for an example of how an image and its gradient image may look like.
Quite the opposite to edge detection, a smoothing or blurring filter is used to make edges appear less prominent. Commonly applied filters of such kind are the $3\times 3$ and $25\times 25$ Gaussian blurring stencils:
${G}_{9}={\displaystyle \frac{1}{15}}\cdot \left(\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 1\hfill \\ \hfill 2\hfill & \hfill 3\hfill & \hfill 2\hfill \\ \hfill 1\hfill & \hfill 2\hfill & \hfill 1\hfill \end{array}\right)$  ${G}_{25}={\displaystyle \frac{1}{331}}\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 4\hfill & \hfill 7\hfill & \hfill 4\hfill & \hfill 1\hfill \\ \hfill 4\hfill & \hfill 20\hfill & \hfill 33\hfill & \hfill 20\hfill & \hfill 4\hfill \\ \hfill 7\hfill & \hfill 33\hfill & \hfill 55\hfill & \hfill 33\hfill & \hfill 7\hfill \\ \hfill 4\hfill & \hfill 20\hfill & \hfill 33\hfill & \hfill 20\hfill & \hfill 4\hfill \\ \hfill 1\hfill & \hfill 4\hfill & \hfill 7\hfill & \hfill 4\hfill & \hfill 1\hfill \end{array}\right)$ 
Write a program that applies these operators to a given image and outputs the result for later use:

•
Write a function apply that takes an image and a filter mask as input and returns the convolution of the two. Use either withloops or axiscontrol notation to achieve this. Take care of boundary conditions when implementing the convolution.

•
Write a function sobel that takes an image as input and applies ${F}_{x}$ and ${F}_{y}$ to the image. Furthermore, add ${S}_{x}$ and ${S}_{y}$ with capping so that this function returns the final result of the Sobel operation.

•
Write functions gauss9 and gauss25 that take an image as input and apply ${G}_{9}$ and ${G}_{25}$ to the image.

•
Write a main function that reads in an image from stdin, calls sobel, gaussBlur9 and gaussBlur25 on this image and then write the results back to stdout.
You may want to use the following skeleton for your program:
Compile your source code with and without the option t mt_pth option for multithreaded execution and experiment with various thread counts. On faster machines it might be necessary to apply the filter multiple times (copy and paste line 55 a couple of times) to see measurable speedups.
NB: The Fibre format encodes, in addition to the raw data, shape information. By using FibreScanIntArray this program is able process 2D images of any size and it is not fixed to statically known input sizes.
6.2 Lesson 8: Computing Mandelbrot Images
Exercise 30.
This exercise is about creating a basic implementation for computing mandelbrot images.

1.
To get started, you may want to use the files mandelbrot_start.sac and Fractal_tier1.sac which, in essence, contain the IOcode for visualising the mandelbrot pictures. A first running version can be obtained by implementing the missing function bodies in Fractal_tier1_empty.sac:

–
escapeTime which implements the iteration on arrays of complex numbers, and

–
genComplexArray which computes a twodimensional array of complex numbers that represent a descritisation of ${\u2102}^{2}$.

–

2.
Waiting for the final picture can be rather unpleasant if it is not clear whether the chosen fraction of ${\u2102}^{2}$ yields an interesting picture and the iteration limit is high. therefore, as a first extension, try to modify the main function in mandelbrot_start.sac so that it computes the mandelbrot picture with increasing resolution without changing the overall size of the picture.
Compute resolutions [5,5], [10,10],…, [320,320] and display them consecutively in a [320,320] display by replicating the found values accordingly.
Hint: define a function stretchRgb which takes an array of type color[.,.] and an integer stretching factor stretch and replicates each element of the array into a square of shape [stretch, stretch].

3.
The function intArrayToMonochrome maps all escape values into a color by means of a clut. Can you express this operation without a withloop?
Hint: You may find inspiration in one of the earlier tasks!

4.
Try using the compiler option t mt_pth to experiment with multicore machines!

5.
Try using the compiler option t cuda to experiment with graphics cards!

6.
Try using the compiler option b11:cyc to inspect the highlevel, optimised intermediate code.
Exercise 31.
In this exercise, we improve the way the colours are chosen in order to obtain smoother transitions. We will use a common approach referred to as normalized iteration counts. A normalized iteration count for a point in the complex plane $z$ is computed by using the iteration count $t$ and the value at that position ${z}_{t}$ during the final iteration. Using these two values, the normalized iteration count is defined as ${t}_{n}:=(t+1){\mathrm{log}}_{2}({\mathrm{log}}_{2}({z}_{t}))$ for those values that escape and as $0$ otherwise.

1.
The module Fractal_tier2.sac contains stubs for the missing functionality required in this exercise:

–
normalizedIterationCount which implements the normalisation of iteration counts by taking the final computed value into account.
Hint: The function escapeTime only computes the number of iterations before the value at a given position escapes. To normalize these, the final value at that position is required, as well. For this, we have provided a function escapeValue.

–
doubleArrayToRGB maps the normalized iteration counts, which are double values, to an RGB colourtriple. To derive an RGB value, first scale all values such that they are in the interval $$. This value can then be used as the hue in the HSB model.
Hint: The module Color8 defines a function Hsb2Rgb that converts a HSB color description into its corresponding RGB representation.

–
Exercise 32.
In this exercise, we apply the filters from the previous case study to the mandelbrot pictures. As before, we have provided stubs for the missing functionality. For this exercise these can be found in the file Stencil_tier3.sac.

1.
Implement the functions apply, sobelEdges, gaussBlur and gaussBlur25 as described in the previous case study.

2.
The three filters described above only operate on a single channel, e.g. a grayscale image. To lift these to colour images, implement a corresponding function for each filter that applies the filter to each colour separately.
Part II Trails Covering More Advanced Features of SaC
Chapter 7 Treasures in the Standard Library
This trail gives the reader a tour through the main components of the standard library. For the time being, it is merely a collection of points of interest. We hope that this will evolve over time.
So far, we only have one lesson on benchmarking in SaC.
7.1 Lesson: Benchmarking SaC Programs
Following the case studies in the previous section, the question arises what the best technique for benchmarking SaC programs might be. The easiest way, of course, is by utilising the Unix time (or timex) command when starting the to be benchmarked program on the command line of the system shell. The disadvantage of this technique is that the whole program is benchmarked, and run time spent in setup or shutdown parts of the code is indistinguishable from time spent in the more relevant parts of a program.
For many program codes exposing in one way or another an iterative nature, this is often still the technique of choice. One simply measures whole program runtime for x iterations and for y iterations and then derives the average time per iteration by dividing the difference in runtimes by the difference in iterations computed. Under the (likely) assumption that setup and shutdown overhead is constant in the number of iterations, this technique allows for simple and still realistic benchmarking without augmenting the source code for benchmarking.
If the above technique for one or another reason is insufficient, the SaC standard library provides access to the system real time clock via the classes RTClock and RTimer. The code example below illustrates how this works.
First, we make all symbols from the name spaces RTClock and RTimer available to our program via the use statements in lines 1 and 2. Access to the real time clock is indirect through the creation of one or more real clock timers. Such a timer comes into existance through execution of the createRTimer function. Timers can (repeatedly) be started and stopped using the functions startRTimer and stopRTimer, respectively. If a timer is started and stopped multiple times, elapsed times are accumulated. Where this is not desirable, a real clock timer can be reset using the resetRTimer function. While the real timers keep their information in an opaque format, two functions support the conversion of timer information into standard SaC values. The function getRTimerInts yields two integer values, specifying elapsed seconds and nanoseconds, respectively; the function getRTimerDbl yields elapsed time in seconds as a double precision floating point value.
Note that starting an already running timer has no effect. Likewise stopping a nonrunning timer has no effect either. Enquiring the state of a running timer yields the timer’s value when it was started. Last not least, a timer should be removed when it is no longer used or needed by calling the destroyRTimer function.
Benchmarking functional programs through starting, stopping and enquiring timers is not without a conceptual problem: In the absence of any data dependency between the starting and the stopping of the timer on the one side and the relevant computation to be benchmarked on the other side, the compiler is free to change the order of these three parts of the computation. And, an aggressively optimising compiler like sac2c may actually do this, which, of course, would render the timing completely useless. To safely prevent the compiler from changing the order of computations, we need to apply a little trick:
Somewhere in the definition of the doRelevantComputation you need to touch the real time clock as shown above. And, you must not declare the work function as an inline function.
Why this helps warrants further explanation; it is deeply connected to the SaC I/O concept, which is based on a variant of uniqueness typing.
Chapter 8 User Defined Types
In this trail covers the definition and use of userdefined types in SaC.
Chapter 9 Dealing with I/O and State in General
SaC supports states through objects that are passed implicitly around. This allows the programmer to specify stateful expressions as sequences while maintaining the sideeffect free functional semantics of the SaC language. The underlying idea is called global objects and will be discussed through out this chapter.
9.1 Lesson: States and Objects — the basics
In most languages, classes are based on special record types containing instance variables and methods. In SaC, classes are based on modules, as they serve the same need: A module pairs functions and types to a group. Instead of instance variables, classes in SaC have a special class type that builds up an instance of a class. As this type always is implicit, direct access to it is only possible from within the same namespace. The following example shows the class Counter:
A class file starts with the class keyword, followed by the name of the class. Another keyword unique to classes is classtype. The statement in line 3 defines int[] as the classtype of class Counter. All functions within the class expect an instance of Counter, e.g. a int[] value, as their argument. By using the SaC call by reference technique, these functions are able to destructively modify an instance and thus its state.
The function increment increments the value of Counter instance c and returns the new, modified version. A special function is create_Counter as it can be used as a constructor function for class Counter. The counterpart is the destructor function destroy_Counter. All class implementations must at least have one constructor function and a destructor function. However, the destructor function can be empty like in the example above.
9.1.1 Extending Classes
Like modules, it is possible to extend classes by new functions. However, a class can only be the derivative of one single other class. There is no support for multiple derivation. Furthermore, there is no possibility to extend the class type — extension is limited to functions. The following listing shows how to extend our Counter example to a new class capable of decrementing its value:
The keyword extends in line 1 signals that the class DecCounter is derived from Counter. Furthermore, there is no class type definition as the class type is as well derived from class Counter. However, the class type can be accessed as if it had been defined within the current class.
9.1.2 States using Classes
9.1.3 Global Objects
9.2 Lesson: Nondeterminism through Shared State in WihthLoops
Chapter 10 Interfacing with Other Languages
This trail explains on how to use SaC libraries from other languages and how to integrate foreign libraries into SaC programs.
So far, we have four lessons. One that explains how to utilise C functions and libraries in SaC and three more lessons that explain how to call SaC from the languages C, C++, and Fortran, respectively.
10.1 Lesson: Calling C from SaC
10.1.1 Using C in the Small
To make use of an external C function from within SaC, a prototype of the function must be defined in SaC. This is done by prefixing the function definition by the keyword extern and leaving out the function body. Assume having a function adding two integers specified in C as follows:
Save the listing to file addfun.c and compile it by gcc c addfun.c supposed you are using the GNU compiler collection. This will generate a single addfun.o file. This can now be used from within SaC:
The keyword external directs the SaC compiler to assume an external definition of function add. The special directive #pragma external ”addfun.o” makes the SaC linking process add addfun.o to the executable or module created.
Save the listing above to a file addfun.sac and compile it by using sac2c o addfun addfun.sac. The resulting executable will contain both, the SaC and C part of the program above.
10.1.2 Stateful C functions
dudu
10.1.3 Using pragma directives
dada