Changeset 3f7e12cb for doc/proposals/concurrency/text/cforall.tex
- Timestamp:
- Nov 8, 2017, 5:43:33 PM (8 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
- Children:
- 954908d
- Parents:
- 78315272 (diff), e35f30a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - File:
-
- 1 edited
-
doc/proposals/concurrency/text/cforall.tex (modified) (2 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/text/cforall.tex
r78315272 r3f7e12cb 1 1 % ====================================================================== 2 2 % ====================================================================== 3 \chapter{Cforall crash course}3 \chapter{Cforall Overview} 4 4 % ====================================================================== 5 5 % ====================================================================== 6 6 7 As mentionned in the introduction, the document presents the design for the concurrency features in \CFA. Since it is a new language here is a quick review of the languagespecifically tailored to the features needed to support concurrency.7 The following is a quick introduction to the \CFA language, specifically tailored to the features needed to support concurrency. 8 8 9 \CFA is a extension of ISO C and therefore supports much of the same paradigms as C. It is a non-object oriented system level language, meaning it has very most of the major abstractions have either no runtime cost or can be opt-out easily. Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over assembly. The vast majority of the code produced by a \CFA compiler respects memory-layouts and calling-conventions laid out by C. However, while \CFA is not an object-oriented language according to a strict definition. It does have some notion of objects, most importantly construction and destruction of objects. Most of the following pieces of code can be found as is on the \CFA website : \cite{www-cfa} 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 10 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} 10 11 11 12 \section{References} 12 13 13 Like \CC, \CFA introduces re ferences as an alternative to pointers. In regards to concurrency, the semantics difference between pointers and references aren't particularly relevant but since this document uses mostly references here is a quick overview of the semantics:14 Like \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: 14 15 \begin{cfacode} 15 16 int x, *p1 = &x, **p2 = &p1, ***p3 = &p2, 16 &r1 = x, &&r2 = r1, &&&r3 = r2; 17 ***p3 = 3; // change x 18 r3 = 3; // change x, ***r3 19 **p3 = ...; // change p1 20 &r3 = ...; // change r1, (&*)**r3 21 *p3 = ...; // change p2 22 &&r3 = ...; // change r2, (&(&*)*)*r3 23 &&&r3 = p3; // change r3 to p3, (&(&(&*)*)*)r3 24 int y, z, & ar[3] = { x, y, z }; // initialize array of references 25 &ar[1] = &z; // change reference array element 26 typeof( ar[1] ) p; // is int, i.e., the type of referenced object 27 typeof( &ar[1] ) q; // is int &, i.e., the type of reference 28 sizeof( ar[1] ) == sizeof( int ); // is true, i.e., the size of referenced object 29 sizeof( &ar[1] ) == sizeof( int *); // is true, i.e., the size of a reference 17 &r1 = x, &&r2 = r1, &&&r3 = r2; 18 ***p3 = 3; //change x 19 r3 = 3; //change x, ***r3 20 **p3 = ...; //change p1 21 *p3 = ...; //change p2 22 int y, z, & ar[3] = {x, y, z}; //initialize array of references 23 typeof( ar[1]) p; //is int, i.e., the type of referenced object 24 typeof(&ar[1]) q; //is int &, i.e., the type of reference 25 sizeof( ar[1]) == sizeof(int); //is true, i.e., the size of referenced object 26 sizeof(&ar[1]) == sizeof(int *); //is true, i.e., the size of a reference 30 27 \end{cfacode} 31 The important t hing 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 The 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. 32 29 33 30 \section{Overloading} 34 31 35 Another important feature \CFA has in common with \CC is function overloading :32 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. 36 33 \begin{cfacode} 37 // 38 void f( void ); //(1)39 void f( char ); //(2)40 void f( int, double ); //(3)41 f(); //select (1)42 f( 'a' ); //select (2)43 f( 3, 5.2 ); //select (3)34 //selection based on type and number of parameters 35 void f(void); //(1) 36 void f(char); //(2) 37 void f(int, double); //(3) 38 f(); //select (1) 39 f('a'); //select (2) 40 f(3, 5.2); //select (3) 44 41 45 // selection based on type and number of returns 46 char f( int ); // (1) 47 double f( int ); // (2) 48 [ int, double ] f( int ); // (3) 49 char c = f( 3 ); // select (1) 50 double d = f( 4 ); // select (2) 51 [ int, double ] t = f( 5 ); // select (3) 42 //selection based on type and number of returns 43 char f(int); //(1) 44 double f(int); //(2) 45 char c = f(3); //select (1) 46 double d = f(4); //select (2) 52 47 \end{cfacode} 53 This feature is particularly important for concurrency since the runtime system relies on creating different types do represent concurrency objects. Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent clashes. As seen in chapter \ref{basics}, the main is an example of routine that benefits from overloading when concurrency in introduced.48 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. 54 49 55 50 \section{Operators} 56 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 would be, like so:51 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 occur, e.g.: 57 52 \begin{cfacode} 58 int ++? ( int op ); //unary prefix increment59 int ?++ ( int op ); //unary postfix increment60 int ?+? ( int op1, int op2 ); //binary plus61 int ?<=?( int op1, int op2 ); //binary less than62 int ?=? ( int & op1, int op2 ); //binary assignment63 int ?+=?( int & op1, int op2 ); //binary plus-assignment53 int ++? (int op); //unary prefix increment 54 int ?++ (int op); //unary postfix increment 55 int ?+? (int op1, int op2); //binary plus 56 int ?<=?(int op1, int op2); //binary less than 57 int ?=? (int & op1, int op2); //binary assignment 58 int ?+=?(int & op1, int op2); //binary plus-assignment 64 59 65 struct S { int i, j;};66 S ?+?( S op1, S op2 ) { //add two structures67 return (S){ op1.i + op2.i, op1.j + op2.j};60 struct S {int i, j;}; 61 S ?+?(S op1, S op2) { //add two structures 62 return (S){op1.i + op2.i, op1.j + op2.j}; 68 63 } 69 S s1 = { 1, 2 }, s2 = { 2, 3}, s3;70 s3 = s1 + s2; // compute sum: s3 == { 2, 5}64 S s1 = {1, 2}, s2 = {2, 3}, s3; 65 s3 = s1 + s2; //compute sum: s3 == {2, 5} 71 66 \end{cfacode} 72 73 Since concurrency does not use operator overloading, this feature is more important as an introduction for the syntax of constructors. 67 While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors. 74 68 75 69 \section{Constructors/Destructors} 76 \CFA uses the following syntax for constructors and destructors :70 Object 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 : 77 71 \begin{cfacode} 78 72 struct S { … … 80 74 int * ia; 81 75 }; 82 void ?{}( S & s, int asize ) with s { //constructor operator83 s ize = asize; //initialize fields84 ia = calloc( size, sizeof( S ));76 void ?{}(S & s, int asize) { //constructor operator 77 s.size = asize; //initialize fields 78 s.ia = calloc(size, sizeof(S)); 85 79 } 86 void ^?{}( S & s ) with s { //destructor operator87 free( ia ); //de-initialization fields80 void ^?{}(S & s) { //destructor operator 81 free(ia); //de-initialization fields 88 82 } 89 83 int main() { 90 S x = { 10 }, y = { 100 }; // implict calls: ?{}( x, 10 ), ?{}( y, 100)91 ... //use x and y92 ^x{}; ^y{}; // 93 x{ 20 }; y{ 200 }; //explicit calls to reinitialize94 ... //reuse x and y95 } // implict calls: ^?{}( y ), ^?{}( x)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) 96 90 \end{cfacode} 97 The language guarantees that every object and all their fields are constructed. Like \CC construction is automatically done on declaration and destruction done when the declared variables reach the end of its scope. 91 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. 92 \begin{cfacode} 93 { 94 struct S s = {10}; //allocation, call constructor 95 ... 96 } //deallocation, call destructor 97 struct S * s = new(); //allocation, call constructor 98 ... 99 delete(s); //deallocation, call destructor 100 \end{cfacode} 101 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. 98 102 99 For more information see \cite{cforall-ug,rob-thesis,www-cfa}. 103 \section{Parametric Polymorphism} 104 Routines 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 : 105 \begin{cfacode} 106 //constraint type, 0 and + 107 forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); }) 108 T 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; 113 } 114 115 S sa[5]; 116 int i = sum(sa, 5); //use S's 0 construction and + 117 \end{cfacode} 118 119 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: 120 \begin{cfacode} 121 trait 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 *); 127 }; 128 forall( otype T | sumable(T) ) //use trait 129 T sum(T a[], size_t size); 130 \end{cfacode} 131 132 \section{with Clause/Statement} 133 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). 134 \begin{cfacode} 135 struct S { int i, j; }; 136 int mem(S & this) with (this) //with clause 137 i = 1; //this->i 138 j = 2; //this->j 139 } 140 int 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 } 158 } 159 \end{cfacode} 160 161 For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
Note:
See TracChangeset
for help on using the changeset viewer.
