Ignore:
Timestamp:
Oct 4, 2017, 3:31:34 PM (5 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
aaron-thesis, arm-eh, 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, resolv-new, with_gc
Children:
b7778c1
Parents:
dcfc4b3
Message:

More work on chapter 2 and 3

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/proposals/concurrency/text/basics.tex

    rdcfc4b3 r3628765  
    1919While 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}.
    2020
    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;
     21A 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
     29void 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
     50void 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
     71typedef struct {
     72        int f1, f2;
     73} iterator_t;
     74
     75int 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
     96Figure \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}
     102coroutine Fibonacci {
     103        int fn; //used for communication
     104};
     105
     106void ?{}(Fibonacci & this) { //constructor
     107        this.fn = 0;
     108}
     109
     110//main automacically called on first resume
     111void 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;
    39124                fn2 = fn1;
    40125                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
     130int next(Fibonacci & this) {
     131        resume(this); //transfer to last suspend
     132        return this.fn;
     133}
     134
     135void 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}
    63143
    64144\subsection{Construction}
     
    82162}
    83163\end{cfacode}
     164
    84165The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
    85166
     
    105186
    106187\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.
     188struct Fibonacci {
     189        int fn; //used for communication
     190        coroutine c; //composition
     191};
     192
     193void ?{}(Fibonacci & this) {
     194        this.fn = 0;
     195        (this.c){}; //Call constructor to initialize coroutine
     196}
     197\end{cfacode}
     198There 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
     204coroutine Format {
     205        char ch;                                                                        //used for communication
     206        int g, b;                                                               //global because used in destructor
     207};
     208
     209void  ?{}(Format & fmt) {
     210        resume( fmt );                                                  //prime (start) coroutine
     211}
     212
     213void ^?{}(Format & fmt) with fmt {
     214        if ( fmt.g != 0 || fmt.b != 0 )
     215        sout | endl;
     216}
     217
     218void 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
     231void prt(Format & fmt, char ch) {
     232        fmt.ch = ch;
     233        resume(fmt);
     234}
     235
     236int 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
    118248
    119249\subsection{Alternative: Reserved keyword}
     
    121251
    122252\begin{cfacode}
    123         coroutine Fibonacci {
    124                 int fn; // used for communication
    125         };
     253coroutine Fibonacci {
     254        int fn; //used for communication
     255};
    126256\end{cfacode}
    127257This 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.
Note: See TracChangeset for help on using the changeset viewer.