source: doc/proposals/concurrency/text/cforall.tex @ b9d0fb6

Last change on this file since b9d0fb6 was a2ea829, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

updated first 3 chapters

  • Property mode set to 100644
File size: 8.1 KB
1% ======================================================================
2% ======================================================================
3\chapter{Cforall Overview}
4% ======================================================================
5% ======================================================================
7The following is a quick introduction to the \CFA language, specifically tailored to the features needed to support concurrency.
9\CFA is a 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 opt-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., 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
10values''\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}
14Like \CC, \CFA introduces rebindable references providing multiple dereferecing 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:
16int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
17        &r1 = x,    &&r2 = r1,   &&&r3 = r2;
18***p3 = 3;                                                      //change x
19r3    = 3;                                                      //change x, ***r3
20**p3  = ...;                                            //change p1
21*p3   = ...;                                            //change p2
22int y, z, & ar[3] = {x, y, z};          //initialize array of references
23typeof( ar[1]) p;                                       //is int, i.e., the type of referenced object
24typeof(&ar[1]) q;                                       //is int &, i.e., the type of reference
25sizeof( ar[1]) == sizeof(int);          //is true, i.e., the size of referenced object
26sizeof(&ar[1]) == sizeof(int *);        //is true, i.e., the size of a reference
28The important take away from this code example is that references offer a handle to an object, much like pointers, but which is automatically dereferenced for convinience.
32Another 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.
34//selection based on type and number of parameters
35void f(void);                   //(1)
36void f(char);                   //(2)
37void f(int, double);    //(3)
38f();                                    //select (1)
39f('a');                                 //select (2)
40f(3, 5.2);                              //select (3)
42//selection based on  type and number of returns
43char   f(int);                  //(1)
44double f(int);                  //(2)
45char   c = f(3);                //select (1)
46double d = f(4);                //select (2)
48This 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.
51Overloading 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 occur, e.g.:
53int ++? (int op);                       //unary prefix increment
54int ?++ (int op);                       //unary postfix increment
55int ?+? (int op1, int op2);             //binary plus
56int ?<=?(int op1, int op2);             //binary less than
57int ?=? (int & op1, int op2);           //binary assignment
58int ?+=?(int & op1, int op2);           //binary plus-assignment
60struct S {int i, j;};
61S ?+?(S op1, S op2) {                           //add two structures
62        return (S){op1.i + op2.i, op1.j + op2.j};
64S s1 = {1, 2}, s2 = {2, 3}, s3;
65s3 = s1 + s2;                                           //compute sum: s3 == {2, 5}
67While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors.
70Object life-time is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object life-time as a mean of synchronization and/or mutual exclusion. Since \CFA relies heavily on the life time of objects, constructors and destructors are a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors :
72struct S {
73        size_t size;
74        int * ia;
76void ?{}(S & s, int asize) {    //constructor operator
77        s.size = asize;                         //initialize fields
78        s.ia = calloc(size, sizeof(S));
80void ^?{}(S & s) {                              //destructor operator
81        free(ia);                                       //de-initialization fields
83int main() {
84        S x = {10}, y = {100};          //implict calls: ?{}(x, 10), ?{}(y, 100)
85        ...                                                     //use x and y
86        ^x{}^y{};                            //explicit calls to de-initialize
87        x{20};  y{200};                         //explicit calls to reinitialize
88        ...                                                     //reuse x and y
89}                                                               //implict calls: ^?{}(y), ^?{}(x)
91The 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.
94        struct S s = {10};      //allocation, call constructor
95        ...
96}                                               //deallocation, call destructor
97struct S * s = new();   //allocation, call constructor
99delete(s);                              //deallocation, call destructor
101Note 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.
103\section{Parametric Polymorphism}
104Routines in \CFA can also be reused for multiple types. This capability is done using the \code{forall} clause which gives \CFA its name. \code{forall} clauses 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 :
106//constraint type, 0 and +
107forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
108T sum(T a[ ], size_t size) {
109        T total = 0;                            //construct T from 0
110        for(size_t i = 0; i < size; i++)
111                total = total + a[i];   //select appropriate +
112        return total;
115S sa[5];
116int i = sum(sa, 5);                             //use S's 0 construction and +
119Since 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:
121trait sumable( otype T ) {
122        void ?{}(T *, zero_t);          //constructor from 0 literal
123        T ?+?(T, T);                            //assortment of additions
124        T ?+=?(T *, T);
125        T ++?(T *);
126        T ?++(T *);
128forall( otype T | sumable(T) )  //use trait
129T sum(T a[], size_t size);
132\section{with Clause/Statement}
133Since \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).
135struct S { int i, j; };
136int mem(S & this) with (this)           //with clause
137        i = 1;                                          //this->i
138        j = 2;                                          //this->j
140int foo() {
141        struct S1 { ... } s1;
142        struct S2 { ... } s2;
143        with (s1)                                       //with statement
144        {
145                //access fields of s1
146                //without qualification
147                with (s2)                                       //nesting
148                {
149                        //access fields of s1 and s2
150                        //without qualification
151                }
152        }
153        with (s1, s2)                           //scopes open in parallel
154        {
155                //access fields of s1 and s2
156                //without qualification
157        }
161For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
Note: See TracBrowser for help on using the repository browser.