source: doc/theses/thierry_delisle_MMath/text/cforall.tex @ d6ad99e

% ======================================================================
% ======================================================================
\chapter{\CFA Overview}
% ======================================================================
% ======================================================================

The following is a quick introduction to the \CFA language, specifically tailored to the features needed to support concurrency.

\CFA is an extension of ISO-C and therefore supports all of the same paradigms as C. It is a non-object-oriented system-language, meaning most of the major abstractions have either no runtime overhead or can be opted out easily. Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code. The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C. Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (e.g., {\tt this}), it does have some notion of objects\footnote{C defines the term objects as : ``region of data storage in the execution environment, the contents of which can represent
values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects. Most of the following code examples can be found on the \CFA website~\cite{www-cfa}.

% ======================================================================
\section{References}

Like \CC, \CFA introduces rebind-able references providing multiple dereferencing as an alternative to pointers. In regards to concurrency, the semantic difference between pointers and references are not particularly relevant, but since this document uses mostly references, here is a quick overview of the semantics:
\begin{cfacode}
int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
        &r1 = x,    &&r2 = r1,   &&&r3 = r2;
***p3 = 3;                                                      //change x
r3    = 3;                                                      //change x, ***r3
**p3  = ...;                                            //change p1
*p3   = ...;                                            //change p2
int y, z, & ar[3] = {x, y, z};          //initialize array of references
typeof( ar[1]) p;                                       //is int, referenced object type
typeof(&ar[1]) q;                                       //is int &, reference type
sizeof( ar[1]) == sizeof(int);          //is true, referenced object size
sizeof(&ar[1]) == sizeof(int *);        //is true, reference size
\end{cfacode}
The important take away from this code example is that a reference offers a handle to an object, much like a pointer, but which is automatically dereferenced for convenience.

% ======================================================================
\section{Overloading}

Another important feature of \CFA is function overloading as in Java and \CC, where routines with the same name are selected based on the number and type of the arguments. As well, \CFA uses the return type as part of the selection criteria, as in Ada~\cite{Ada}. For routines with multiple parameters and returns, the selection is complex.
\begin{cfacode}
//selection based on type and number of parameters
void f(void);                   //(1)
void f(char);                   //(2)
void f(int, double);    //(3)
f();                                    //select (1)
f('a');                                 //select (2)
f(3, 5.2);                              //select (3)

//selection based on  type and number of returns
char   f(int);                  //(1)
double f(int);                  //(2)
char   c = f(3);                //select (1)
double d = f(4);                //select (2)
\end{cfacode}
This feature is particularly important for concurrency since the runtime system relies on creating different types to represent concurrency objects. Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent name clashes. As seen in chapter \ref{basics}, routine \code{main} is an example that benefits from overloading.

% ======================================================================
\section{Operators}
Overloading also extends to operators. The syntax for denoting operator-overloading is to name a routine with the symbol of the operator and question marks where the arguments of the operation appear, e.g.:
\begin{cfacode}
int ++? (int op);                       //unary prefix increment
int ?++ (int op);                       //unary postfix increment
int ?+? (int op1, int op2);             //binary plus
int ?<=?(int op1, int op2);             //binary less than
int ?=? (int & op1, int op2);           //binary assignment
int ?+=?(int & op1, int op2);           //binary plus-assignment

struct S {int i, j;};
S ?+?(S op1, S op2) {                           //add two structures
        return (S){op1.i + op2.i, op1.j + op2.j};
}
S s1 = {1, 2}, s2 = {2, 3}, s3;
s3 = s1 + s2;                                           //compute sum: s3 == {2, 5}
\end{cfacode}
While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors.

% ======================================================================
\section{Constructors/Destructors}
Object lifetime is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object lifetime as a means of synchronization and/or mutual exclusion. Since \CFA relies heavily on the lifetime of objects, constructors and destructors is a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors:
\begin{cfacode}
struct S {
        size_t size;
        int * ia;
};
void ?{}(S & s, int asize) {    //constructor operator
        s.size = asize;                         //initialize fields
        s.ia = calloc(size, sizeof(S));
}
void ^?{}(S & s) {                              //destructor operator
        free(ia);                                       //de-initialization fields
}
int main() {
        S x = {10}, y = {100};          //implicit calls: ?{}(x, 10), ?{}(y, 100)
        ...                                                     //use x and y
        ^x{};  ^y{};                            //explicit calls to de-initialize
        x{20};  y{200};                         //explicit calls to reinitialize
        ...                                                     //reuse x and y
}                                                               //implicit calls: ^?{}(y), ^?{}(x)
\end{cfacode}
The language guarantees that every object and all their fields are constructed. Like \CC, construction of an object is automatically done on allocation and destruction of the object is done on deallocation. Allocation and deallocation can occur on the stack or on the heap.
\begin{cfacode}
{
        struct S s = {10};      //allocation, call constructor
        ...
}                                               //deallocation, call destructor
struct S * s = new();   //allocation, call constructor
...
delete(s);                              //deallocation, call destructor
\end{cfacode}
Note that like \CC, \CFA introduces \code{new} and \code{delete}, which behave like \code{malloc} and \code{free} in addition to constructing and destructing objects, after calling \code{malloc} and before calling \code{free}, respectively.

% ======================================================================
\section{Parametric Polymorphism}
\label{s:ParametricPolymorphism}
Routines in \CFA can also be reused for multiple types. This capability is done using the \code{forall} clauses, which allow separately compiled routines to support generic usage over multiple types. For example, the following sum function works for any type that supports construction from 0 and addition:
\begin{cfacode}
//constraint type, 0 and +
forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
T sum(T a[ ], size_t size) {
        T total = 0;                            //construct T from 0
        for(size_t i = 0; i < size; i++)
                total = total + a[i];   //select appropriate +
        return total;
}

S sa[5];
int i = sum(sa, 5);                             //use S's 0 construction and +
\end{cfacode}

Since writing constraints on types can become cumbersome for more constrained functions, \CFA also has the concept of traits. Traits are named collection of constraints that can be used both instead and in addition to regular constraints:
\begin{cfacode}
trait summable( otype T ) {
        void ?{}(T *, zero_t);          //constructor from 0 literal
        T ?+?(T, T);                            //assortment of additions
        T ?+=?(T *, T);
        T ++?(T *);
        T ?++(T *);
};
forall( otype T | summable(T) ) //use trait
T sum(T a[], size_t size);
\end{cfacode}

Note that the type use for assertions can be either an \code{otype} or a \code{dtype}. Types declared as \code{otype} refer to ``complete'' objects, i.e., objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator. Using \code{dtype,} on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.

% ======================================================================
\section{with Clause/Statement}
Since \CFA lacks the concept of a receiver, certain functions end up needing to repeat variable names often. To remove this inconvenience, \CFA provides the \code{with} statement, which opens an aggregate scope making its fields directly accessible (like Pascal).
\begin{cfacode}
struct S { int i, j; };
int mem(S & this) with (this)           //with clause
        i = 1;                                                  //this->i
        j = 2;                                                  //this->j
}
int foo() {
        struct S1 { ... } s1;
        struct S2 { ... } s2;
        with (s1)                                               //with statement
        {
                //access fields of s1 without qualification
                with (s2)                                       //nesting
                {
                        //access fields of s1 and s2 without qualification
                }
        }
        with (s1, s2)                                   //scopes open in parallel
        {
                //access fields of s1 and s2 without qualification
        }
}
\end{cfacode}

For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.