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

aaron-thesisarm-ehcleanup-dtorsdeferred_resndemanglerjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerresolv-newwith_gc
Last change on this file since 3628765 was 3628765, checked in by Thierry Delisle <tdelisle@…>, 4 years ago

More work on chapter 2 and 3

  • Property mode set to 100644
File size: 8.1 KB
Line 
1% ======================================================================
2% ======================================================================
3\chapter{Cforall crash course}
4% ======================================================================
5% ======================================================================
6
7This thesis presents the design for a set of concurrency features in \CFA. Since it is a new dialect of C, the following is a quick introduction to the language, specifically tailored to the features needed to support concurrency.
8
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 received (e.g.: this), it does have some notion of objects\footnote{C defines the term objects as : [Where to I get the C11 reference manual?]}, most importantly construction and destruction of objects. Most of the following pieces of code can be found on the \CFA website \cite{www-cfa}
10
11\section{References}
12
13Like \CC, \CFA introduces references as an alternative to pointers. In regards to concurrency, the semantics difference between pointers and references are not particularly relevant but since this document uses mostly references here is a quick overview of the semantics :
14\begin{cfacode}
15int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
16&r1 = x,    &&r2 = r1,   &&&r3 = r2;
17***p3 = 3;                                                      //change x
18r3    = 3;                                                      //change x, ***r3
19**p3  = ...;                                            //change p1
20*p3   = ...;                                            //change p2
21int y, z, & ar[3] = {x, y, z};          //initialize array of references
22typeof( ar[1]) p;                                       //is int, i.e., the type of referenced object
23typeof(&ar[1]) q;                                       //is int &, i.e., the type of reference
24sizeof( ar[1]) == sizeof(int);          //is true, i.e., the size of referenced object
25sizeof(&ar[1]) == sizeof(int *);        //is true, i.e., the size of a reference
26\end{cfacode}
27The important thing to take away from this code snippet is that references offer a handle to an object much like pointers but which is automatically derefferenced when convinient.
28
29\section{Overloading}
30
31Another important feature of \CFA is function overloading as in Java and \CC, where routine with the same name are selected based on the numbers 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.
32\begin{cfacode}
33//selection based on type and number of parameters
34void f(void);                   //(1)
35void f(char);                   //(2)
36void f(int, double);    //(3)
37f();                                    //select (1)
38f('a');                                 //select (2)
39f(3, 5.2);                              //select (3)
40
41//selection based on  type and number of returns
42char   f(int);                  //(1)
43double f(int);                  //(2)
44char   c = f(3);                //select (1)
45double d = f(4);                //select (2)
46\end{cfacode}
47This 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}, routines main is an example that benefits from overloading.
48
49\section{Operators}
50Overloading 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 would be, like so :
51\begin{cfacode}
52int ++? (int op);                       //unary prefix increment
53int ?++ (int op);                       //unary postfix increment
54int ?+? (int op1, int op2);             //binary plus
55int ?<=?(int op1, int op2);             //binary less than
56int ?=? (int & op1, int op2);           //binary assignment
57int ?+=?(int & op1, int op2);           //binary plus-assignment
58
59struct S {int i, j;};
60S ?+?(S op1, S op2) {                           //add two structures
61        return (S){op1.i + op2.i, op1.j + op2.j};
62}
63S s1 = {1, 2}, s2 = {2, 3}, s3;
64s3 = s1 + s2;                                           //compute sum: s3 == {2, 5}
65\end{cfacode}
66While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors.
67
68\section{Constructors/Destructors}
69Object 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 :
70\begin{cfacode}
71struct S {
72        size_t size;
73        int * ia;
74};
75void ?{}(S & s, int asize) {    //constructor operator
76        s.size = asize;                         //initialize fields
77        s.ia = calloc(size, sizeof(S));
78}
79void ^?{}(S & s) {                              //destructor operator
80        free(ia);                                       //de-initialization fields
81}
82int main() {
83        S x = {10}, y = {100};          //implict calls: ?{}(x, 10), ?{}(y, 100)
84        ...                                                     //use x and y
85        ^x{}^y{};                            //explicit calls to de-initialize
86        x{20};  y{200};                         //explicit calls to reinitialize
87        ...                                                     //reuse x and y
88}                                                               //implict calls: ^?{}(y), ^?{}(x)
89\end{cfacode}
90The 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.
91\begin{cfacode}
92{
93        struct S s = {10};      //allocation, call constructor
94        ...
95}                                               //deallocation, call destructor
96struct S * s = new();   //allocation, call constructor
97...
98delete(s);                              //deallocation, call destructor
99\end{cfacode}
100Note 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.
101
102\section{Parametric Polymorphism}
103Routines in \CFA can also be reused for multiple types. This is done using the \code{forall} clause which gives \CFA it's name. \code{forall} clauses allow seperatly compiled routines to support generic usage over multiple types. For example, the following sum function will work for any type which support construction from 0 and addition :
104\begin{cfacode}
105//constraint type, 0 and +
106forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
107T sum(T a[ ], size_t size) {
108        T total = 0;                            //construct T from 0
109        for(size_t i = 0; i < size; i++)
110                total = total + a[i];   //select appropriate +
111        return total;
112}
113
114S sa[5];
115int i = sum(sa, 5);                             //use S's 0 construction and +
116\end{cfacode}
117
118Since writing constraints on types can become cumbersome for more constrained functions, \CFA also has the concept of traits. Traits are named collection of constraints which can be used both instead and in addition to regular constraints:
119\begin{cfacode}
120trait sumable( otype T ) {
121        void ?{}(T *, zero_t);          //constructor from 0 literal
122        T ?+?(T, T);                            //assortment of additions
123        T ?+=?(T *, T);
124        T ++?(T *);
125        T ?++(T *);
126};
127forall( otype T | sumable(T) )  //use trait
128T sum(T a[], size_t size);
129\end{cfacode}
130
131\section{with Clause/Statement}
132Since \CFA lacks the concept of a receiver, certain functions end-up needing to repeat variable names often, to solve this \CFA offers the \code{with} statement which opens an aggregate scope making its fields directly accessible (like Pascal).
133\begin{cfacode}
134struct S { int i, j; };
135int mem(S & this) with this             //with clause
136        i = 1;                                          //this->i
137        j = 2;                                          //this->j
138}
139int foo() {
140        struct S1 { ... } s1;
141        struct S2 { ... } s2;
142        with s1                                         //with statement
143        {
144                //access fields of s1
145                //without qualification
146                with s2                                 //nesting
147                {
148                        //access fields of s1 and s2
149                        //without qualification
150                }
151        }
152        with s1, s2                             //scopes open in parallel
153        {
154                //access fields of s1 and s2
155                //without qualification
156        }
157}
158\end{cfacode}
159
160For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
Note: See TracBrowser for help on using the repository browser.