Changeset 3628765 for doc/proposals


Ignore:
Timestamp:
Oct 4, 2017, 3:31:34 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, 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

Location:
doc/proposals/concurrency
Files:
3 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.
  • doc/proposals/concurrency/text/cforall.tex

    rdcfc4b3 r3628765  
    100100Note 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.
    101101
     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
    102160For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
  • doc/proposals/concurrency/version

    rdcfc4b3 r3628765  
    1 0.10.33
     10.10.95
Note: See TracChangeset for help on using the changeset viewer.