Changeset 3628765

Timestamp:

Oct 4, 2017, 3:31:34 PM (7 years ago)

Author:

Thierry Delisle <tdelisle@…>

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:

dcfc4b3

Message:

More work on chapter 2 and 3

Location:

doc/proposals/concurrency

Files:

• text/basics.tex (modified) (4 diffs)
• text/cforall.tex (modified) (1 diff)
• version (modified) (1 diff)

doc/proposals/concurrency/text/basics.tex

@@ -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}.
 
-Here is an example of a solution to the fibonnaci problem using \CFA coroutines:
-\begin{cfacode}
-        coroutine Fibonacci {
-              int fn; // used for communication
-        };
-
-        void ?{}(Fibonacci & this) { // constructor
-              this.fn = 0;
-        }
-
-        // main automacically called on first resume
-        void main(Fibonacci & this) {
-                int fn1, fn2;           // retained between resumes
-                this.fn = 0;
-                fn1 = this.fn;
-                suspend(this);          // return to last resume
-
-                this.fn = 1;
+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.
+\begin{figure}
+\label{fig:fibonacci-c}
+\caption{Different implementations of a fibonacci sequence generator in C.}
+\begin{center}
+\begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
+\begin{ccode}[tabsize=2]
+//Using callbacks
+void fibonacci_func(
+        int n,
+        void (*callback)(int)
+) {
+        int first = 0;
+        int second = 1;
+        int next, i;
+        for(i = 0; i < n; i++)
+        {
+                if(i <= 1)
+                        next = i;
+                else {
+                        next = f1 + f2;
+                        f1 = f2;
+                        f2 = next;
+                }
+                callback(next);
+        }
+}
+\end{ccode}&\begin{ccode}[tabsize=2]
+//Using output array
+void fibonacci_array(
+        int n,
+        int * array
+) {
+        int f1 = 0; int f2 = 1;
+        int next, i;
+        for(i = 0; i < n; i++)
+        {
+                if(i <= 1)
+                        next = i;
+                else {
+                        next = f1 + f2;
+                        f1 = f2;
+                        f2 = next;
+                }
+                *array = next;
+                array++;
+        }
+}
+\end{ccode}&\begin{ccode}[tabsize=2]
+//Using external state
+typedef struct {
+        int f1, f2;
+} iterator_t;
+
+int fibonacci_state(
+        iterator_t * it
+) {
+        int f;
+        f = it->f1 + it->f2;
+        it->f2 = it->f1;
+        it->f1 = f;
+        return f;
+}
+
+
+
+
+
+
+\end{ccode}
+\end{tabular}
+\end{center}
+\end{figure}
+
+
+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.
+
+\begin{figure}
+\label{fig:fibonacci-cfa}
+\caption{Implementation of fibonacci using coroutines}
+\begin{cfacode}
+coroutine Fibonacci {
+        int fn; //used for communication
+};
+
+void ?{}(Fibonacci & this) { //constructor
+        this.fn = 0;
+}
+
+//main automacically called on first resume
+void main(Fibonacci & this) {
+        int fn1, fn2;           //retained between resumes
+        this.fn = 0;
+        fn1 = this.fn;
+        suspend(this);          //return to last resume
+
+        this.fn = 1;
+        fn2 = fn1;
+        fn1 = this.fn;
+        suspend(this);          //return to last resume
+
+        for ( ;; ) {
+                this.fn = fn1 + fn2;
                 fn2 = fn1;
                 fn1 = this.fn;
-                suspend(this);          // return to last resume
-
-                for ( ;; ) {
-                        this.fn = fn1 + fn2;
-                        fn2 = fn1;
-                        fn1 = this.fn;
-                        suspend(this);  // return to last resume
-                }
-        }
-
-        int next(Fibonacci & this) {
-                resume(this); // transfer to last suspend
-                return this.fn;
-        }
-
-        void main() { // regular program main
-                Fibonacci f1, f2;
-                for ( int i = 1; i <= 10; i += 1 ) {
-                        sout | next( f1 ) | next( f2 ) | endl;
-                }
-        }
-\end{cfacode}
+                suspend(this);  //return to last resume
+        }
+}
+
+int next(Fibonacci & this) {
+        resume(this); //transfer to last suspend
+        return this.fn;
+}
+
+void main() { //regular program main
+        Fibonacci f1, f2;
+        for ( int i = 1; i <= 10; i += 1 ) {
+                sout | next( f1 ) | next( f2 ) | endl;
+        }
+}
+\end{cfacode}
+\end{figure}
 
 \subsection{Construction}
@@ -82 +162 @@
 }
 \end{cfacode}
+
 The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
 
@@ -105 +186 @@
 
 \begin{cfacode}
-        struct Fibonacci {
-                int fn; //used for communication
-                coroutine c; //composition
-        };
-
-        void ?{}(Fibonacci & this) {
-                this.fn = 0;
-                (this.c){}; //Call constructor to initialize coroutine
-        }
-\end{cfacode}
-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.
+struct Fibonacci {
+        int fn; //used for communication
+        coroutine c; //composition
+};
+
+void ?{}(Fibonacci & this) {
+        this.fn = 0;
+        (this.c){}; //Call constructor to initialize coroutine
+}
+\end{cfacode}
+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.
+\begin{figure}
+\label{fig:fmt-line}
+\caption{Formatting text into lines of 5 blocks of 4 characters.}
+\begin{cfacode}[tabsize=3]
+//format characters into blocks of 4 and groups of 5 blocks per line
+coroutine Format {
+        char ch;                                                                        //used for communication
+        int g, b;                                                               //global because used in destructor
+};
+
+void  ?{}(Format & fmt) {
+        resume( fmt );                                                  //prime (start) coroutine
+}
+
+void ^?{}(Format & fmt) with fmt {
+        if ( fmt.g != 0 || fmt.b != 0 )
+        sout | endl;
+}
+
+void main(Format & fmt) with fmt {
+        for ( ;; ) {                                                    //for as many characters
+                for(g = 0; g < 5; g++) {                //groups of 5 blocks
+                        for(b = 0; b < 4; fb++) {       //blocks of 4 characters
+                                suspend();
+                                sout | ch;                                      //print character
+                        }
+                        sout | "  ";                                    //print block separator
+                }
+                sout | endl;                                            //print group separator
+        }
+}
+
+void prt(Format & fmt, char ch) {
+        fmt.ch = ch;
+        resume(fmt);
+}
+
+int main() {
+        Format fmt;
+        char ch;
+        Eof: for ( ;; ) {                                               //read until end of file
+                sin | ch;                                                       //read one character
+                if(eof(sin)) break Eof;                 //eof ?
+                prt(fmt, ch);                                           //push character for formatting
+        }
+}
+\end{cfacode}
+\end{figure}
+
 
 \subsection{Alternative: Reserved keyword}
@@ -121 +251 @@
 
 \begin{cfacode}
-        coroutine Fibonacci {
-                int fn; // used for communication
-        };
+coroutine Fibonacci {
+        int fn; //used for communication
+};
 \end{cfacode}
 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

@@ -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.
 
+\section{Parametric Polymorphism}
+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 :
+\begin{cfacode}
+//constraint type, 0 and +
+forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
+T sum(T a[ ], size_t size) {
+        T total = 0;                            //construct T from 0
+        for(size_t i = 0; i < size; i++)
+                total = total + a[i];   //select appropriate +
+        return total;
+}
+
+S sa[5];
+int i = sum(sa, 5);                             //use S's 0 construction and +
+\end{cfacode}
+
+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:
+\begin{cfacode}
+trait sumable( otype T ) {
+        void ?{}(T *, zero_t);          //constructor from 0 literal
+        T ?+?(T, T);                            //assortment of additions
+        T ?+=?(T *, T);
+        T ++?(T *);
+        T ?++(T *);
+};
+forall( otype T | sumable(T) )  //use trait
+T sum(T a[], size_t size);
+\end{cfacode}
+
+\section{with Clause/Statement}
+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).
+\begin{cfacode}
+struct S { int i, j; };
+int mem(S & this) with this             //with clause
+        i = 1;                                          //this->i
+        j = 2;                                          //this->j
+}
+int foo() {
+        struct S1 { ... } s1;
+        struct S2 { ... } s2;
+        with s1                                         //with statement
+        {
+                //access fields of s1
+                //without qualification
+                with s2                                 //nesting
+                {
+                        //access fields of s1 and s2
+                        //without qualification
+                }
+        }
+        with s1, s2                             //scopes open in parallel
+        {
+                //access fields of s1 and s2
+                //without qualification
+        }
+}
+\end{cfacode}
+
 For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.

doc/proposals/concurrency/version

@@ -1 @@
-0.10.33
+0.10.95