Changeset 3628765 for doc/proposals/concurrency/text
- Timestamp:
- Oct 4, 2017, 3:31:34 PM (7 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:
- b7778c1
- Parents:
- dcfc4b35
- Location:
- doc/proposals/concurrency/text
- Files:
-
- 2 edited
-
basics.tex (modified) (4 diffs)
-
cforall.tex (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
doc/proposals/concurrency/text/basics.tex
rdcfc4b35 r3628765 19 19 While the main focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are actually a significant building block of a concurrency system. Coroutines need to deal with context-switchs and other context-management operations. Therefore, this proposal includes coroutines both as an intermediate step for the implementation of threads, and a first class feature of \CFA. Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant. The core \acrshort{api} of coroutines revolve around two features: independent call stacks and \code{suspend}/\code{resume}. 20 20 21 Here is an example of a solution to the fibonnaci problem using \CFA coroutines: 22 \begin{cfacode} 23 coroutine Fibonacci { 24 int fn; // used for communication 25 }; 26 27 void ?{}(Fibonacci & this) { // constructor 28 this.fn = 0; 29 } 30 31 // main automacically called on first resume 32 void main(Fibonacci & this) { 33 int fn1, fn2; // retained between resumes 34 this.fn = 0; 35 fn1 = this.fn; 36 suspend(this); // return to last resume 37 38 this.fn = 1; 21 A good example of a problem made easier with coroutines is genereting the fibonacci sequence. This problem comes with the challenge of decoupling how a sequence is generated and how it is used. Figure \ref{fig:fibonacci-c} shows conventional approaches to writing generators in C. All three of these approach suffer from strong coupling. The left and center approaches require that the generator have knowledge of how the sequence will be used, while the rightmost approach requires to user to hold internal state between calls on behalf of th sequence generator and makes it much harder to handle corner cases like the Fibonacci seed. 22 \begin{figure} 23 \label{fig:fibonacci-c} 24 \caption{Different implementations of a fibonacci sequence generator in C.} 25 \begin{center} 26 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c} 27 \begin{ccode}[tabsize=2] 28 //Using callbacks 29 void fibonacci_func( 30 int n, 31 void (*callback)(int) 32 ) { 33 int first = 0; 34 int second = 1; 35 int next, i; 36 for(i = 0; i < n; i++) 37 { 38 if(i <= 1) 39 next = i; 40 else { 41 next = f1 + f2; 42 f1 = f2; 43 f2 = next; 44 } 45 callback(next); 46 } 47 } 48 \end{ccode}&\begin{ccode}[tabsize=2] 49 //Using output array 50 void fibonacci_array( 51 int n, 52 int * array 53 ) { 54 int f1 = 0; int f2 = 1; 55 int next, i; 56 for(i = 0; i < n; i++) 57 { 58 if(i <= 1) 59 next = i; 60 else { 61 next = f1 + f2; 62 f1 = f2; 63 f2 = next; 64 } 65 *array = next; 66 array++; 67 } 68 } 69 \end{ccode}&\begin{ccode}[tabsize=2] 70 //Using external state 71 typedef struct { 72 int f1, f2; 73 } iterator_t; 74 75 int fibonacci_state( 76 iterator_t * it 77 ) { 78 int f; 79 f = it->f1 + it->f2; 80 it->f2 = it->f1; 81 it->f1 = f; 82 return f; 83 } 84 85 86 87 88 89 90 \end{ccode} 91 \end{tabular} 92 \end{center} 93 \end{figure} 94 95 96 Figure \ref{fig:fibonacci-cfa} is an example of a solution to the fibonnaci problem using \CFA coroutines, using the coroutine stack to hold sufficient state for the generation. This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used. Indeed, this version is a easy to use as the \code{fibonacci_state} solution, while the imlpementation is very similar to the \code{fibonacci_func} example. 97 98 \begin{figure} 99 \label{fig:fibonacci-cfa} 100 \caption{Implementation of fibonacci using coroutines} 101 \begin{cfacode} 102 coroutine Fibonacci { 103 int fn; //used for communication 104 }; 105 106 void ?{}(Fibonacci & this) { //constructor 107 this.fn = 0; 108 } 109 110 //main automacically called on first resume 111 void main(Fibonacci & this) { 112 int fn1, fn2; //retained between resumes 113 this.fn = 0; 114 fn1 = this.fn; 115 suspend(this); //return to last resume 116 117 this.fn = 1; 118 fn2 = fn1; 119 fn1 = this.fn; 120 suspend(this); //return to last resume 121 122 for ( ;; ) { 123 this.fn = fn1 + fn2; 39 124 fn2 = fn1; 40 125 fn1 = this.fn; 41 suspend(this); // return to last resume 42 43 for ( ;; ) { 44 this.fn = fn1 + fn2; 45 fn2 = fn1; 46 fn1 = this.fn; 47 suspend(this); // return to last resume 48 } 49 } 50 51 int next(Fibonacci & this) { 52 resume(this); // transfer to last suspend 53 return this.fn; 54 } 55 56 void main() { // regular program main 57 Fibonacci f1, f2; 58 for ( int i = 1; i <= 10; i += 1 ) { 59 sout | next( f1 ) | next( f2 ) | endl; 60 } 61 } 62 \end{cfacode} 126 suspend(this); //return to last resume 127 } 128 } 129 130 int next(Fibonacci & this) { 131 resume(this); //transfer to last suspend 132 return this.fn; 133 } 134 135 void main() { //regular program main 136 Fibonacci f1, f2; 137 for ( int i = 1; i <= 10; i += 1 ) { 138 sout | next( f1 ) | next( f2 ) | endl; 139 } 140 } 141 \end{cfacode} 142 \end{figure} 63 143 64 144 \subsection{Construction} … … 82 162 } 83 163 \end{cfacode} 164 84 165 The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information: 85 166 … … 105 186 106 187 \begin{cfacode} 107 struct Fibonacci { 108 int fn; //used for communication 109 coroutine c; //composition 110 }; 111 112 void ?{}(Fibonacci & this) { 113 this.fn = 0; 114 (this.c){}; //Call constructor to initialize coroutine 115 } 116 \end{cfacode} 117 There are two downsides to this approach. The first, which is relatively minor, is that the coroutine handle needs to be made aware of the main routine pointer. This requirement means the coroutine data must be made larger to store a value that is actually a compile time constant (address of the main routine). The second problem, which is both subtle and significant, is that now users can get the initialisation order of coroutines wrong. Indeed, every field of a \CFA struct is constructed but in declaration order, unless users explicitly write otherwise. This semantics means that users who forget to initialize the coroutine handle may resume the coroutine with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem. 188 struct Fibonacci { 189 int fn; //used for communication 190 coroutine c; //composition 191 }; 192 193 void ?{}(Fibonacci & this) { 194 this.fn = 0; 195 (this.c){}; //Call constructor to initialize coroutine 196 } 197 \end{cfacode} 198 There are two downsides to this approach. The first, which is relatively minor, made aware of the main routine pointer. This information must either be store in the coroutine runtime data or in its static type structure. When using composition, all coroutine handles have the same static type structure which means the pointer to the main needs to be part of the runtime data. This requirement means the coroutine data must be made larger to store a value that is actually a compile time constant (address of the main routine). The second problem, which is both subtle and significant, is that now users can get the initialisation order of coroutines wrong. Indeed, every field of a \CFA struct is constructed but in declaration order, unless users explicitly write otherwise. This semantics means that users who forget to initialize the coroutine handle may resume the coroutine with an uninitilized object. For coroutines, this is unlikely to be a problem, for threads however, this is a significant problem. Figure \ref{fig:fmt-line} shows the \code{Format} coroutine which rearranges text in order to group characters into blocks of fixed size. This is a good example where the control flow is made much simpler from being able to resume the coroutine from the constructor and highlights the idea that interesting control flow can occor in the constructor. 199 \begin{figure} 200 \label{fig:fmt-line} 201 \caption{Formatting text into lines of 5 blocks of 4 characters.} 202 \begin{cfacode}[tabsize=3] 203 //format characters into blocks of 4 and groups of 5 blocks per line 204 coroutine Format { 205 char ch; //used for communication 206 int g, b; //global because used in destructor 207 }; 208 209 void ?{}(Format & fmt) { 210 resume( fmt ); //prime (start) coroutine 211 } 212 213 void ^?{}(Format & fmt) with fmt { 214 if ( fmt.g != 0 || fmt.b != 0 ) 215 sout | endl; 216 } 217 218 void main(Format & fmt) with fmt { 219 for ( ;; ) { //for as many characters 220 for(g = 0; g < 5; g++) { //groups of 5 blocks 221 for(b = 0; b < 4; fb++) { //blocks of 4 characters 222 suspend(); 223 sout | ch; //print character 224 } 225 sout | " "; //print block separator 226 } 227 sout | endl; //print group separator 228 } 229 } 230 231 void prt(Format & fmt, char ch) { 232 fmt.ch = ch; 233 resume(fmt); 234 } 235 236 int main() { 237 Format fmt; 238 char ch; 239 Eof: for ( ;; ) { //read until end of file 240 sin | ch; //read one character 241 if(eof(sin)) break Eof; //eof ? 242 prt(fmt, ch); //push character for formatting 243 } 244 } 245 \end{cfacode} 246 \end{figure} 247 118 248 119 249 \subsection{Alternative: Reserved keyword} … … 121 251 122 252 \begin{cfacode} 123 124 int fn; //used for communication125 253 coroutine Fibonacci { 254 int fn; //used for communication 255 }; 126 256 \end{cfacode} 127 257 This mean the compiler can solve problems by injecting code where needed. The downside of this approach is that it makes coroutine a special case in the language. Users who would want to extend coroutines or build their own for various reasons can only do so in ways offered by the language. Furthermore, implementing coroutines without language supports also displays the power of the programming language used. While this is ultimately the option used for idiomatic \CFA code, coroutines and threads can both be constructed by users without using the language support. The reserved keywords are only present to improve ease of use for the common cases. -
doc/proposals/concurrency/text/cforall.tex
rdcfc4b35 r3628765 100 100 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. 101 101 102 \section{Parametric Polymorphism} 103 Routines 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 + 106 forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); }) 107 T 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 114 S sa[5]; 115 int i = sum(sa, 5); //use S's 0 construction and + 116 \end{cfacode} 117 118 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 which can be used both instead and in addition to regular constraints: 119 \begin{cfacode} 120 trait 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 }; 127 forall( otype T | sumable(T) ) //use trait 128 T sum(T a[], size_t size); 129 \end{cfacode} 130 131 \section{with Clause/Statement} 132 Since \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} 134 struct S { int i, j; }; 135 int mem(S & this) with this //with clause 136 i = 1; //this->i 137 j = 2; //this->j 138 } 139 int 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 102 160 For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
Note: See TracChangeset
for help on using the changeset viewer.
