Changes in / [2ae16219:b2da0574]


Ignore:
Files:
235 added
122 deleted
16 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/lstlang.sty

    r2ae16219 rb2da0574  
    88%% Created On       : Sat May 13 16:34:42 2017
    99%% Last Modified By : Peter A. Buhr
    10 %% Last Modified On : Fri Apr  6 23:44:50 2018
    11 %% Update Count     : 20
     10%% Last Modified On : Fri Mar 16 22:18:12 2018
     11%% Update Count     : 16
    1212%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1313
    … …  
    112112\lstdefinelanguage{CFA}[ANSI]{C}{
    113113        morekeywords={
    114                 _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
    115                 auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
    116                 coroutine, disable, dtype, enable, __extension__, exception, fallthrough, fallthru, finally,
    117                 __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
    118                 inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
    119                 otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
    120                 _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
    121                 virtual, __volatile, __volatile__, waitfor, when, with, zero_t,
    122     },
     114                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, _At, __attribute,
     115                __attribute__, auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__,
     116                __const, __const__, disable, dtype, enable, __extension__, fallthrough, fallthru,
     117                finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t,
     118                otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof,
     119                __typeof__, virtual, with, zero_t},
     120        morekeywords=[2]{
     121                _Atomic, coroutine, is_coroutine, is_monitor, is_thread, monitor, mutex, nomutex, or,
     122                resume, suspend, thread, _Thread_local, waitfor, when, yield},
    123123        moredirectives={defined,include_next}%
    124124}

  • doc/papers/concurrency/Makefile

    r2ae16219 rb2da0574  
    33Build = build
    44Figures = figures
    5 Macros = ../AMA/AMA-stix/ama
     5Macros = AMA/AMA-stix/ama
    66TeXLIB = .:annex:../../LaTeXmacros:${Macros}:${Build}:../../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    … …  
    7979
    8080WileyNJD-AMA.bst:
    81         ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst .
     81        ln -fs AMA/AMA-stix/ama/WileyNJD-AMA.bst .
    8282
    8383%.tex : %.fig

  • doc/papers/concurrency/Paper.tex

    r2ae16219 rb2da0574  
    1212
    1313% Latex packages used in the document.
    14 
    1514\usepackage{epic,eepic}
    1615\usepackage{xspace}
    … …  
    1817\usepackage{upquote}                                            % switch curled `'" to straight
    1918\usepackage{listings}                                           % format program code
    20 \usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt]{subfig}
     19\usepackage[labelformat=simple]{subfig}
    2120\renewcommand{\thesubfigure}{(\alph{subfigure})}
    2221\usepackage{siunitx}
    2322\sisetup{ binary-units=true }
     23%\input{style}                                                          % bespoke macros used in the document
    2424
    2525\hypersetup{breaklinks=true}
    … …  
    3131\renewcommand{\linenumberfont}{\scriptsize\sffamily}
    3232
    33 \renewcommand{\textfraction}{0.0}       % the entire page maybe devoted to floats with no text on the page at all
    34 
    35 \lefthyphenmin=3                                                        % hyphen only after 4 characters
    36 \righthyphenmin=3
     33\lefthyphenmin=4                                                        % hyphen only after 4 characters
     34\righthyphenmin=4
    3735
    3836%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    9795% Latin abbreviation
    9896\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
    99 \@ifundefined{eg}{
    10097\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
    10198\newcommand*{\eg}{%
    … …  
    103100                {\@ifnextchar{:}{\EG}%
    104101                        {\EG,\xspace}}%
    105 }}{}%
    106 \@ifundefined{ie}{
     102}%
    107103\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
    108104\newcommand*{\ie}{%
    … …  
    110106                {\@ifnextchar{:}{\IE}%
    111107                        {\IE,\xspace}}%
    112 }}{}%
    113 \@ifundefined{etc}{
     108}%
    114109\newcommand{\ETC}{\abbrevFont{etc}}
    115110\newcommand*{\etc}{%
    116111        \@ifnextchar{.}{\ETC}%
    117112        {\ETC.\xspace}%
    118 }}{}%
    119 \@ifundefined{etal}{
     113}%
    120114\newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
    121 \newcommand*{\etal}{%
     115\renewcommand*{\etal}{%
    122116        \@ifnextchar{.}{\protect\ETAL}%
    123117                {\protect\ETAL.\xspace}%
    124 }}{}%
    125 \@ifundefined{viz}{
     118}%
    126119\newcommand{\VIZ}{\abbrevFont{viz}}
    127120\newcommand*{\viz}{%
    128121        \@ifnextchar{.}{\VIZ}%
    129122                {\VIZ.\xspace}%
    130 }}{}%
     123}%
    131124\makeatother
    132125
    … …  
    141134\lstdefinelanguage{CFA}[ANSI]{C}{
    142135        morekeywords={
    143                 _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
    144                 auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
    145                 coroutine, disable, dtype, enable, __extension__, exception, fallthrough, fallthru, finally,
    146                 __float80, float80, __float128, float128, forall, ftype, _Generic, _Imaginary, __imag, __imag__,
    147                 inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
    148                 otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, thread,
    149                 _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
    150                 virtual, __volatile, __volatile__, waitfor, when, with, zero_t},
     136                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, _At, __attribute,
     137                __attribute__, auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__,
     138                __const, __const__, disable, dtype, enable, exception, __extension__, fallthrough, fallthru,
     139                finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t,
     140                otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof,
     141                __typeof__, virtual, with, zero_t},
     142        morekeywords=[2]{
     143                _Atomic, coroutine, is_coroutine, is_monitor, is_thread, monitor, mutex, nomutex, or,
     144                resume, suspend, thread, _Thread_local, waitfor, when, yield},
    151145        moredirectives={defined,include_next}%
    152146}
    … …  
    218212\authormark{Thierry Delisle \textsc{et al}}
    219213
    220 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
     214\address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
    221215
    222216\corres{*Peter A. Buhr, \email{pabuhr{\char`\@}uwaterloo.ca}}
    223 \presentaddress{Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
     217\presentaddress{David R. Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, N2L 3G1, Canada}
    224218
    225219
    … …  
    235229}%
    236230
    237 \keywords{concurrency, parallelism, coroutines, threads, monitors, runtime, C, Cforall}
     231\keywords{concurrency, runtime, coroutines, threads, C, Cforall}
    238232
    239233
    … …  
    249243% ======================================================================
    250244
    251 This paper provides a minimal concurrency \newterm{Abstract Program Interface} (API) that is simple, efficient and can be used to build other concurrency features.
     245This paper provides a minimal concurrency \newterm{API} that is simple, efficient and can be used to build other concurrency features.
    252246While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
    253247An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
    … …  
    255249Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}.
    256250
    257 This paper used the following terminology.
     251The terminology used in this paper is as follows.
    258252A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state.
    259 Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe communication and access to shared data.
    260 % Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, \etc) concurrent threads are introduced.
     253Multiple simultaneous threads gives rise to \newterm{concurrency}, which requires locking to ensure safe access to shared data.
     254% Correspondingly, concurrency is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced.
    261255\newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety.
    262256\newterm{Parallelism} is running multiple threads simultaneously.
    … …  
    265259
    266260Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism.
    267 While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite[\S~2]{Buhr05a}.
    268 Concurrency tools handle synchronization and mutual exclusion, while parallelism tools handle performance, cost and resource utilization.
     261While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}.
     262Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost and resource utilization.
    269263
    270264The proposed concurrency API is implemented in a dialect of C, called \CFA.
    … …  
    283277Like C, the basics of \CFA revolve around structures and routines, which are thin abstractions over machine code.
    284278The vast majority of the code produced by the \CFA translator respects memory layouts and calling conventions laid out by C.
    285 Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (\eg {\tt 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
     279Interestingly, while \CFA is not an object-oriented language, lacking the concept of a receiver (e.g., {\tt 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
    286280values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects.
    287281Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
    … …  
    335329\subsection{Operators}
    336330Overloading also extends to operators.
    337 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 appear, \eg:
     331The 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 appear, e.g.:
    338332\begin{cfa}
    339333int ++? (int op);                       $\C{// unary prefix increment}$
    … …  
    426420
    427421Note that the type use for assertions can be either an @otype@ or a @dtype@.
    428 Types declared as @otype@ refer to ``complete'' objects, \ie objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
     422Types declared as @otype@ refer to ``complete'' objects, i.e., objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
    429423Using @dtype@, on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.
    430424
    … …  
    464458% ======================================================================
    465459% ======================================================================
    466 
     460Before any detailed discussion of the concurrency and parallelism in \CFA, it is important to describe the basics of concurrency and how they are expressed in \CFA user code.
     461
     462\section{Basics of concurrency}
    467463At its core, concurrency is based on having multiple call-stacks and scheduling among threads of execution executing on these stacks.
    468 Multiple call stacks (or contexts) and a single thread of execution does \emph{not} imply concurrency.
    469 Execution with a single thread and multiple stacks where the thread is deterministically self-scheduling across the stacks is called \newterm{coroutining};
    470 execution with a single thread and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency~\cite[\S~3]{Buhr05a}.
    471 Therefore, a minimal concurrency system can be achieved using coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always defer to an oracle for where to context-switch next.
    472 
     464Concurrency without parallelism only requires having multiple call stacks (or contexts) for a single thread of execution.
     465
     466Execution with a single thread and multiple stacks where the thread is self-scheduling deterministically across the stacks is called coroutining.
     467Execution with a single and multiple stacks but where the thread is scheduled by an oracle (non-deterministic from the thread's perspective) across the stacks is called concurrency.
     468
     469Therefore, a minimal concurrency system can be achieved by creating coroutines (see Section \ref{coroutine}), which instead of context-switching among each other, always ask an oracle where to context-switch next.
    473470While coroutines can execute on the caller's stack-frame, stack-full coroutines allow full generality and are sufficient as the basis for concurrency.
    474471The aforementioned oracle is a scheduler and the whole system now follows a cooperative threading-model (a.k.a., non-preemptive scheduling).
    … …  
    483480
    484481
    485 \subsection{\protect\CFA's Thread Building Blocks}
     482\section{\protect\CFA's Thread Building Blocks}
    486483
    487484One of the important features that are missing in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional.
    … …  
    493490
    494491
    495 \subsection{Coroutines: A Stepping Stone}\label{coroutine}
    496 
    497 While the focus of this proposal is concurrency and parallelism, it is important to address coroutines, which are a significant building block of a concurrency system.
    498 \newterm{Coroutine}s are generalized routines with points where execution is suspended and resumed at a later time.
    499 Suspend/resume is a context switche and coroutines have other context-management operations.
    500 Many design challenges of threads are partially present in designing coroutines, which makes the design effort relevant.
    501 The core \textbf{api} of coroutines has two features: independent call-stacks and @suspend@/@resume@.
    502 
    503 A coroutine handles the class of problems that need to retain state between calls (\eg plugin, device driver, finite-state machine).
    504 For example, a problem made easier with coroutines is unbounded generators, \eg generating an infinite sequence of Fibonacci numbers:
    505 \begin{displaymath}
    506 f(n) = \left \{
    507 \begin{array}{ll}
    508 0                               & n = 0         \\
    509 1                               & n = 1         \\
    510 f(n-1) + f(n-2) & n \ge 2       \\
    511 \end{array}
    512 \right.
    513 \end{displaymath}
    514 Figure~\ref{f:C-fibonacci} shows conventional approaches for writing a Fibonacci generator in C.
    515 
    516 Figure~\ref{f:GlobalVariables} illustrates the following problems:
    517 unencapsulated global variables necessary to retain state between calls;
    518 only one fibonacci generator can run at a time;
    519 execution state must be explicitly retained.
    520 Figure~\ref{f:ExternalState} addresses these issues:
    521 unencapsulated program global variables become encapsulated structure variables;
    522 multiple fibonacci generators can run at a time by declaring multiple fibonacci objects;
    523 explicit execution state is removed by precomputing the first two Fibonacci numbers and returning $f(n-2)$.
     492\section{Coroutines: A Stepping Stone}\label{coroutine}
     493
     494While 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. \textbf{Coroutine}s are generalized routines which have predefined points where execution is suspended and can be resumed at a later time.
     495Therefore, they need to deal with context switches and other context-management operations.
     496This proposal includes coroutines both as an intermediate step for the implementation of threads, and a first-class feature of \CFA.
     497Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant.
     498The core \textbf{api} of coroutines revolves around two features: independent call-stacks and @suspend@/@resume@.
    524499
    525500\begin{figure}
    526 \centering
    527 \newbox\myboxA
    528 \begin{lrbox}{\myboxA}
    529 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    530 `int f1, f2, state = 1;`   // single global variables
    531 int fib() {
    532         int fn;
    533         `switch ( state )` {  // explicit execution state
    534           case 1: fn = 0;  f1 = fn;  state = 2;  break;
    535           case 2: fn = 1;  f2 = f1;  f1 = fn;  state = 3;  break;
    536           case 3: fn = f1 + f2;  f2 = f1;  f1 = fn;  break;
    537         }
    538         return fn;
     501\begin{center}
     502\begin{tabular}{@{}lll@{}}
     503\multicolumn{1}{c}{\textbf{callback}} & \multicolumn{1}{c}{\textbf{output array}} & \multicolumn{1}{c}{\textbf{external state}} \\
     504\begin{cfa}
     505void fib_func(
     506        int n, void (* callback)( int )
     507) {
     508        int fn, f1 = 0, f2 = 1;
     509        for ( int i = 0; i < n; i++ ) {
     510                callback( f1 );
     511                fn = f1 + f2;
     512                f1 = f2;  f2 = fn;
     513        }
    539514}
    540515int main() {
    541 
    542         for ( int i = 0; i < 10; i += 1 ) {
    543                 printf( "%d\n", fib() );
    544         }
    545 }
    546 \end{lstlisting}
    547 \end{lrbox}
    548 
    549 \newbox\myboxB
    550 \begin{lrbox}{\myboxB}
    551 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    552 #define FIB_INIT `{ 0, 1 }`
    553 typedef struct { int f2, f1; } Fib;
    554 int fib( Fib * f ) {
    555 
    556         int ret = f->f2;
    557         int fn = f->f1 + f->f2;
    558         f->f2 = f->f1; f->f1 = fn;
    559 
     516        void print_fib( int n ) {
     517                printf( "%d\n", n );
     518        }
     519        fib_func( 10, print_fib );
     520}
     521
     522\end{cfa}
     523&
     524\begin{cfa}
     525void fib_array(
     526        int n, int * array
     527) {
     528        int fn, f1 = 0, f2 = 1;
     529        for ( int i = 0; i < n; i++ ) {
     530                array[i] = f1;
     531                fn = f1 + f2;
     532                f1 = f2;  f2 = fn;
     533        }
     534}
     535int main() {
     536        int a[10];
     537        fib_array( 10, a );
     538        for ( int i = 0; i < 10; i++ ) {
     539                printf( "%d\n", a[i] );
     540        }
     541}
     542\end{cfa}
     543&
     544\begin{cfa}
     545
     546typedef struct { int f1, f2; } Fib;
     547int fib_state(
     548        Fib * fib
     549) {
     550        int ret = fib->f1;
     551        int fn = fib->f1 + fib->f2;
     552        fib->f2 = fib->f1; fib->f1 = fn;
    560553        return ret;
    561554}
    562555int main() {
    563         Fib f1 = FIB_INIT, f2 = FIB_INIT;
    564         for ( int i = 0; i < 10; i += 1 ) {
    565                 printf( "%d %d\n", fib( &f1 ), fib( &f2 ) );
    566         }
    567 }
    568 \end{lstlisting}
    569 \end{lrbox}
    570 
    571 \subfloat[3 States: global variables]{\label{f:GlobalVariables}\usebox\myboxA}
    572 \qquad
    573 \subfloat[1 State: external variables]{\label{f:ExternalState}\usebox\myboxB}
    574 \caption{C Fibonacci Implementations}
    575 \label{f:C-fibonacci}
    576 
    577 \bigskip
    578 
    579 \newbox\myboxA
    580 \begin{lrbox}{\myboxA}
    581 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    582 `coroutine` Fib { int fn; };
    583 void main( Fib & f ) with( f ) {
    584         int f1, f2;
    585         fn = 0;  f1 = fn;  `suspend()`;
    586         fn = 1;  f2 = f1;  f1 = fn;  `suspend()`;
    587         for ( ;; ) {
    588                 fn = f1 + f2;  f2 = f1;  f1 = fn;  `suspend()`;
    589         }
    590 }
    591 int next( Fib & fib ) with( fib ) {
    592         `resume( fib );`
    593         return fn;
    594 }
    595 int main() {
    596         Fib f1, f2;
    597         for ( int i = 1; i <= 10; i += 1 ) {
    598                 sout | next( f1 ) | next( f2 ) | endl;
    599         }
    600 }
    601 \end{lstlisting}
    602 \end{lrbox}
    603 \newbox\myboxB
    604 \begin{lrbox}{\myboxB}
    605 \begin{lstlisting}[aboveskip=0pt,belowskip=0pt]
    606 `coroutine` Fib { int ret; };
    607 void main( Fib & f ) with( f ) {
    608         int fn, f1 = 1, f2 = 0;
    609         for ( ;; ) {
    610                 ret = f2;
    611 
    612                 fn = f1 + f2;  f2 = f1;  f1 = fn; `suspend();`
    613         }
    614 }
    615 int next( Fib & fib ) with( fib ) {
    616         `resume( fib );`
    617         return ret;
    618 }
    619 
    620 
    621 
    622 
    623 
    624 
    625 \end{lstlisting}
    626 \end{lrbox}
    627 \subfloat[3 States, internal variables]{\label{f:Coroutine3States}\usebox\myboxA}
    628 \qquad
    629 \subfloat[1 State, internal variables]{\label{f:Coroutine1State}\usebox\myboxB}
    630 \caption{\CFA Coroutine Fibonacci Implementations}
    631 \label{f:fibonacci-cfa}
     556        Fib fib = { 0, 1 };
     557
     558        for ( int i = 0; i < 10; i++ ) {
     559                printf( "%d\n", fib_state( &fib ) );
     560        }
     561}
     562\end{cfa}
     563\end{tabular}
     564\end{center}
     565\caption{Fibonacci Implementations in C}
     566\label{lst:fib-c}
    632567\end{figure}
    633568
    634 Figure~\ref{f:Coroutine3States} creates a @coroutine@ type, which provides communication for multiple interface functions, and the \newterm{coroutine main}, which runs on the coroutine stack.
    635 \begin{cfa}
    636 `coroutine C { char c; int i; _Bool s; };`      $\C{// used for communication}$
    637 void ?{}( C & c ) { s = false; }                        $\C{// constructor}$
    638 void main( C & cor ) with( cor ) {                      $\C{// actual coroutine}$
    639         while ( ! s ) // process c
    640         if ( v == ... ) s = false;
    641 }
    642 // interface functions
    643 char cont( C & cor, char ch ) { c = ch; resume( cor ); return c; }
    644 _Bool stop( C & cor, int v ) { s = true; i = v; resume( cor ); return s; }
    645 \end{cfa}
    646 
    647 encapsulates the Fibonacci state in the  shows is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
     569A good example of a problem made easier with coroutines is generators, e.g., generating the Fibonacci sequence.
     570This problem comes with the challenge of decoupling how a sequence is generated and how it is used.
     571Listing \ref{lst:fibonacci-c} shows conventional approaches to writing generators in C.
     572All three of these approach suffer from strong coupling.
     573The left and centre approaches require that the generator have knowledge of how the sequence is used, while the rightmost approach requires holding internal state between calls on behalf of the generator and makes it much harder to handle corner cases like the Fibonacci seed.
     574
     575Listing \ref{lst:fibonacci-cfa} is an example of a solution to the Fibonacci problem using \CFA coroutines, where the coroutine stack holds sufficient state for the next generation.
    648576This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used.
    649577Indeed, this version is as easy to use as the @fibonacci_state@ solution, while the implementation is very similar to the @fibonacci_func@ example.
    650578
    651 Figure~\ref{f:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
     579\begin{figure}
     580\begin{cfa}
     581coroutine Fibonacci { int fn; };                                $\C{// used for communication}$
     582
     583void ?{}( Fibonacci & fib ) with( fib ) { fn = 0; } $\C{// constructor}$
     584
     585void main( Fibonacci & fib ) with( fib ) {              $\C{// main called on first resume}$
     586        int fn1, fn2;                                                           $\C{// retained between resumes}$
     587        fn = 0;  fn1 = fn;                                                      $\C{// 1st case}$
     588        suspend();                                                                      $\C{// restart last resume}$
     589        fn = 1;  fn2 = fn1;  fn1 = fn;                          $\C{// 2nd case}$
     590        suspend();                                                                      $\C{// restart last resume}$
     591        for ( ;; ) {
     592                fn = fn1 + fn2; fn2 = fn1;  fn1 = fn;   $\C{// general case}$
     593                suspend();                                                              $\C{// restart last resume}$
     594        }
     595}
     596int next( Fibonacci & fib ) with( fib ) {
     597        resume( fib );                                                          $\C{// restart last suspend}$
     598        return fn;
     599}
     600int main() {
     601        Fibonacci f1, f2;
     602        for ( int i = 1; i <= 10; i++ ) {
     603                sout | next( f1 ) | next( f2 ) | endl;
     604        }
     605}
     606\end{cfa}
     607\caption{Coroutine Fibonacci }
     608\label{lst:fibonacci-cfa}
     609\end{figure}
     610
     611Listing \ref{lst:fmt-line} shows the @Format@ coroutine for restructuring text into groups of character blocks of fixed size.
    652612The example takes advantage of resuming coroutines in the constructor to simplify the code and highlights the idea that interesting control flow can occur in the constructor.
    653613
    654614\begin{figure}
    655 \centering
    656 \begin{cfa}
    657 `coroutine` Format {
    658         char ch;                                                                $\C{// used for communication}$
    659         int g, b;                                                               $\C{// global because used in destructor}$
     615\begin{cfa}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
     616// format characters into blocks of 4 and groups of 5 blocks per line
     617coroutine Format {
     618        char ch;                                                                        // used for communication
     619        int g, b;                                                               // global because used in destructor
    660620};
    661 void ?{}( Format & fmt ) { `resume( fmt );` } $\C{// prime (start) coroutine}$
    662 void ^?{}( Format & fmt ) with( fmt ) { if ( g != 0 || b != 0 ) sout | endl; }
    663 void main( Format & fmt ) with( fmt ) {
    664         for ( ;; ) {                                                    $\C{// for as many characters}$
    665                 for ( g = 0; g < 5; g += 1 ) {          $\C{// groups of 5 blocks}$
    666                         for ( b = 0; b < 4; b += 1 ) {  $\C{// blocks of 4 characters}$
    667                                 `suspend();`
    668                                 sout | ch;                                      $\C{// print character}$
     621
     622void  ?{}(Format& fmt) {
     623        resume( fmt );                                                  // prime (start) coroutine
     624}
     625
     626void ^?{}(Format& fmt) with fmt {
     627        if ( fmt.g != 0 || fmt.b != 0 )
     628        sout | endl;
     629}
     630
     631void main(Format& fmt) with fmt {
     632        for ( ;; ) {                                                    // for as many characters
     633                for(g = 0; g < 5; g++) {                // groups of 5 blocks
     634                        for(b = 0; b < 4; fb++) {       // blocks of 4 characters
     635                                suspend();
     636                                sout | ch;                                      // print character
    669637                        }
    670                         sout | "  ";                                    $\C{// print block separator}$
     638                        sout | "  ";                                    // print block separator
    671639                }
    672                 sout | endl;                                            $\C{// print group separator}$
    673         }
    674 }
    675 void prt( Format & fmt, char ch ) {
     640                sout | endl;                                            // print group separator
     641        }
     642}
     643
     644void prt(Format & fmt, char ch) {
    676645        fmt.ch = ch;
    677         `resume( fmt );`
    678 }
     646        resume(fmt);
     647}
     648
    679649int main() {
    680650        Format fmt;
    681651        char ch;
    682         for ( ;; ) {                                                    $\C{// read until end of file}$
    683                 sin | ch;                                                       $\C{// read one character}$
    684           if ( eof( sin ) ) break;                              $\C{// eof ?}$
    685                 prt( fmt, ch );                                         $\C{// push character for formatting}$
    686         }
    687 }
    688 \end{cfa}
    689 \caption{Formatting text into lines of 5 blocks of 4 characters.}
    690 \label{f:fmt-line}
     652        Eof: for ( ;; ) {                                               // read until end of file
     653                sin | ch;                                                       // read one character
     654                if(eof(sin)) break Eof;                 // eof ?
     655                prt(fmt, ch);                                           // push character for formatting
     656        }
     657}
     658\end{cfa}
    691659\end{figure}
    692660
    693 \begin{figure}
    694 \centering
    695 \lstset{language=CFA,escapechar={},moredelim=**[is][\protect\color{red}]{`}{`}}
    696 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}}
    697 \begin{cfa}
    698 `coroutine` Prod {
    699         Cons & c;
    700         int N, money, receipt;
    701 };
    702 void main( Prod & prod ) with( prod ) {
    703         // 1st resume starts here
    704         for ( int i = 0; i < N; i += 1 ) {
    705                 int p1 = random( 100 ), p2 = random( 100 );
    706                 sout | p1 | " " | p2 | endl;
    707                 int status = delivery( c, p1, p2 );
    708                 sout | " $" | money | endl | status | endl;
    709                 receipt += 1;
    710         }
    711         stop( c );
    712         sout | "prod stops" | endl;
    713 }
    714 int payment( Prod & prod, int money ) {
    715         prod.money = money;
    716         `resume( prod );`
    717         return prod.receipt;
    718 }
    719 void start( Prod & prod, int N, Cons &c ) {
    720         &prod.c = &c;
    721         prod.[N, receipt] = [N, 0];
    722         `resume( prod );`
    723 }
    724 int main() {
    725         Prod prod;
    726         Cons cons = { prod };
    727         srandom( getpid() );
    728         start( prod, 5, cons );
    729 }
    730 \end{cfa}
    731 &
    732 \begin{cfa}
    733 `coroutine` Cons {
    734         Prod & p;
    735         int p1, p2, status;
    736         _Bool done;
    737 };
    738 void ?{}( Cons & cons, Prod & p ) {
    739         &cons.p = &p;
    740         cons.[status, done ] = [0, false];
    741 }
    742 void ^?{}( Cons & cons ) {}
    743 void main( Cons & cons ) with( cons ) {
    744         // 1st resume starts here
    745         int money = 1, receipt;
    746         for ( ; ! done; ) {
    747                 sout | p1 | " " | p2 | endl | " $" | money | endl;
    748                 status += 1;
    749                 receipt = payment( p, money );
    750                 sout | " #" | receipt | endl;
    751                 money += 1;
    752         }
    753         sout | "cons stops" | endl;
    754 }
    755 int delivery( Cons & cons, int p1, int p2 ) {
    756         cons.[p1, p2] = [p1, p2];
    757         `resume( cons );`
    758         return cons.status;
    759 }
    760 void stop( Cons & cons ) {
    761         cons.done = true;
    762         `resume( cons );`
    763 }
    764 
    765 \end{cfa}
    766 \end{tabular}
    767 \caption{Producer / consumer: resume-resume cycle, bi-directional communication}
    768 \label{f:ProdCons}
    769 \end{figure}
    770 
    771 
    772 \subsubsection{Construction}
    773 
     661\subsection{Construction}
    774662One important design challenge for implementing coroutines and threads (shown in section \ref{threads}) is that the runtime system needs to run code after the user-constructor runs to connect the fully constructed object into the system.
    775663In the case of coroutines, this challenge is simpler since there is no non-determinism from preemption or scheduling.
    … …  
    814702}
    815703\end{cfa}
    816 The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; \ie the stack-based thunk being destroyed before it can be used.
     704The problem in this example is a storage management issue, the function pointer @_thunk0@ is only valid until the end of the block, which limits the viable solutions because storing the function pointer for too long causes undefined behaviour; i.e., the stack-based thunk being destroyed before it can be used.
    817705This challenge is an extension of challenges that come with second-class routines.
    818706Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope.
    819707The case of coroutines and threads is simply an extension of this problem to multiple call stacks.
    820708
    821 
    822 \subsubsection{Alternative: Composition}
    823 
     709\subsection{Alternative: Composition}
    824710One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
    825711
    … …  
    845731This opens the door for user errors and requires extra runtime storage to pass at runtime information that can be known statically.
    846732
    847 
    848 \subsubsection{Alternative: Reserved keyword}
    849 
     733\subsection{Alternative: Reserved keyword}
    850734The next alternative is to use language support to annotate coroutines as follows:
     735
    851736\begin{cfa}
    852737coroutine Fibonacci {
    … …  
    861746The reserved keywords are only present to improve ease of use for the common cases.
    862747
    863 
    864 \subsubsection{Alternative: Lambda Objects}
     748\subsection{Alternative: Lambda Objects}
    865749
    866750For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
    … …  
    892776As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity.
    893777
    894 
    895 \subsubsection{Alternative: Trait-Based Coroutines}
     778\subsection{Alternative: Trait-Based Coroutines}
    896779
    897780Finally, the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines.
    … …  
    938821The combination of these two approaches allows users new to coroutining and concurrency to have an easy and concise specification, while more advanced users have tighter control on memory layout and initialization.
    939822
    940 \subsection{Thread Interface}\label{threads}
     823\section{Thread Interface}\label{threads}
    941824The basic building blocks of multithreading in \CFA are \textbf{cfathread}.
    942825Both user and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism.
    … …  
    1046929\end{cfa}
    1047930
    1048 However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, \ie they are always destroyed in the opposite order of construction because of C scoping rules.
     931However, one of the drawbacks of this approach is that threads always form a tree where nodes must always outlive their children, i.e., they are always destroyed in the opposite order of construction because of C scoping rules.
    1049932This restriction is relaxed by using dynamic allocation, so threads can outlive the scope in which they are created, much like dynamically allocating memory lets objects outlive the scope in which they are created.
    1050933
    … …  
    1087970Since many of these challenges appear with the use of mutable shared state, some languages and libraries simply disallow mutable shared state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}).
    1088971In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms closely relate to networking concepts (channels~\cite{CSP,Go} for example).
    1089 However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (\ie message passing versus routine calls).
     972However, in languages that use routine calls as their core abstraction mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine calls).
    1090973This distinction in turn means that, in order to be effective, programmers need to learn two sets of design patterns.
    1091974While this distinction can be hidden away in library code, effective use of the library still has to take both paradigms into account.
    … …  
    1101984One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared-memory systems, is the \emph{monitor}.
    1102985Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}.
    1103 Many programming languages---\eg Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
     986Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs.
    1104987In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors.
    1105988For these reasons, this project proposes monitors as the core concurrency construct.
    1106989
    1107 
    1108 \subsection{Basics}
    1109 
     990\section{Basics}
    1110991Non-determinism requires concurrent systems to offer support for mutual-exclusion and synchronization.
    1111992Mutual-exclusion is the concept that only a fixed number of threads can access a critical section at any given time, where a critical section is a group of instructions on an associated portion of data that requires the restricted access.
    1112993On the other hand, synchronization enforces relative ordering of execution and synchronization tools provide numerous mechanisms to establish timing relationships among threads.
    1113994
    1114 
    1115 \subsubsection{Mutual-Exclusion}
    1116 
     995\subsection{Mutual-Exclusion}
    1117996As mentioned above, mutual-exclusion is the guarantee that only a fix number of threads can enter a critical section at once.
    1118997However, many solutions exist for mutual exclusion, which vary in terms of performance, flexibility and ease of use.
    1119998Methods range from low-level locks, which are fast and flexible but require significant attention to be correct, to  higher-level concurrency techniques, which sacrifice some performance in order to improve ease of use.
    1120 Ease of use comes by either guaranteeing some problems cannot occur (\eg being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
    1121 For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (\eg reading/writing large types atomically).
     999Ease of use comes by either guaranteeing some problems cannot occur (e.g., being deadlock free) or by offering a more explicit coupling between data and corresponding critical section.
     1000For example, the \CC @std::atomic<T>@ offers an easy way to express mutual-exclusion on a restricted set of operations (e.g., reading/writing large types atomically).
    11221001Another challenge with low-level locks is composability.
    11231002Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
    11241003Easing composability is another feature higher-level mutual-exclusion mechanisms often offer.
    11251004
    1126 
    1127 \subsubsection{Synchronization}
    1128 
     1005\subsection{Synchronization}
    11291006As with mutual-exclusion, low-level synchronization primitives often offer good performance and good flexibility at the cost of ease of use.
    1130 Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (\eg message passing) or offering a simpler solution to otherwise involved challenges.
     1007Again, higher-level mechanisms often simplify usage by adding either better coupling between synchronization and data (e.g., message passing) or offering a simpler solution to otherwise involved challenges.
    11311008As mentioned above, synchronization can be expressed as guaranteeing that event \textit{X} always happens before \textit{Y}.
    11321009Most of the time, synchronization happens within a critical section, where threads must acquire mutual-exclusion in a certain order.
    … …  
    11391016Algorithms that use flag variables to detect barging threads are said to be using barging avoidance, while algorithms that baton-pass locks~\cite{Andrews89} between threads instead of releasing the locks are said to be using barging prevention.
    11401017
    1141 
    11421018% ======================================================================
    11431019% ======================================================================
    … …  
    11731049Another aspect to consider is when a monitor acquires its mutual exclusion.
    11741050For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry.
    1175 Passthrough can occur for generic helper routines (@swap@, @sort@, \etc) or specific helper routines like the following to implement an atomic counter:
     1051Passthrough can occur for generic helper routines (@swap@, @sort@, etc.) or specific helper routines like the following to implement an atomic counter:
    11761052
    11771053\begin{cfa}
    … …  
    13311207
    13321208The call semantics discussed above have one software engineering issue: only a routine can acquire the mutual-exclusion of a set of monitor. \CFA offers the @mutex@ statement to work around the need for unnecessary names, avoiding a major software engineering problem~\cite{2FTwoHardThings}.
    1333 Table \ref{f:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
     1209Table \ref{lst:mutex-stmt} shows an example of the @mutex@ statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
    13341210Beyond naming, the @mutex@ statement has no semantic difference from a routine call with @mutex@ parameters.
    13351211
    … …  
    13611237\end{center}
    13621238\caption{Regular call semantics vs. \protect\lstinline|mutex| statement}
    1363 \label{f:mutex-stmt}
     1239\label{lst:mutex-stmt}
    13641240\end{table}
    13651241
    … …  
    14101286In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronization.
    14111287With monitors, this capability is generally achieved with internal or external scheduling as in~\cite{Hoare74}.
    1412 With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (\ie with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (\ie without access to the shared state).
     1288With \textbf{scheduling} loosely defined as deciding which thread acquires the critical section next, \textbf{internal scheduling} means making the decision from inside the critical section (i.e., with access to the shared state), while \textbf{external scheduling} means making the decision when entering the critical section (i.e., without access to the shared state).
    14131289Since internal scheduling within a single monitor is mostly a solved problem, this paper concentrates on extending internal scheduling to multiple monitors.
    14141290Indeed, like the \textbf{bulk-acq} semantics, internal scheduling extends to multiple monitors in a way that is natural to the user but requires additional complexity on the implementation side.
    … …  
    14371313There are two details to note here.
    14381314First, @signal@ is a delayed operation; it only unblocks the waiting thread when it reaches the end of the critical section.
    1439 This semantics is needed to respect mutual-exclusion, \ie the signaller and signalled thread cannot be in the monitor simultaneously.
     1315This semantics is needed to respect mutual-exclusion, i.e., the signaller and signalled thread cannot be in the monitor simultaneously.
    14401316The alternative is to return immediately after the call to @signal@, which is significantly more restrictive.
    14411317Second, in \CFA, while it is common to store a @condition@ as a field of the monitor, a @condition@ variable can be stored/created independently of a monitor.
    … …  
    15551431
    15561432A larger example is presented to show complex issues for \textbf{bulk-acq} and its implementation options are analyzed.
    1557 Figure~\ref{f:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{f:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{f:int-bulk-cfa}.
    1558 For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, \eg @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
     1433Listing \ref{lst:int-bulk-cfa} shows an example where \textbf{bulk-acq} adds a significant layer of complexity to the internal signalling semantics, and listing \ref{lst:int-bulk-cfa} shows the corresponding \CFA code to implement the cfa-code in listing \ref{lst:int-bulk-cfa}.
     1434For the purpose of translating the given cfa-code into \CFA-code, any method of introducing a monitor is acceptable, e.g., @mutex@ parameters, global variables, pointer parameters, or using locals with the @mutex@ statement.
    15591435
    15601436\begin{figure}
    … …  
    15861462\end{cfa}
    15871463\end{multicols}
    1588 \begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={f:int-bulk-cfa}]
     1464\begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={lst:int-bulk-cfa}]
    15891465\end{cfa}
    15901466\begin{center}
    … …  
    16221498\end{cfa}
    16231499\end{multicols}
    1624 \begin{cfa}[caption={Equivalent \CFA code for listing \ref{f:int-bulk-cfa}},label={f:int-bulk-cfa}]
     1500\begin{cfa}[caption={Equivalent \CFA code for listing \ref{lst:int-bulk-cfa}},label={lst:int-bulk-cfa}]
    16251501\end{cfa}
    16261502\begin{multicols}{2}
    … …  
    16471523\end{cfa}
    16481524\end{multicols}
    1649 \begin{cfa}[caption={Figure~\ref{f:int-bulk-cfa}, with delayed signalling comments},label={f:int-secret}]
     1525\begin{cfa}[caption={Listing \ref{lst:int-bulk-cfa}, with delayed signalling comments},label={lst:int-secret}]
    16501526\end{cfa}
    16511527\end{figure}
    16521528
    1653 The complexity begins at code sections 4 and 8 in listing \ref{f:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
     1529The complexity begins at code sections 4 and 8 in listing \ref{lst:int-bulk-cfa}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
    16541530The root of the problem is that \textbf{bulk-acq} is used in a context where one of the monitors is already acquired, which is why it is important to define the behaviour of the previous cfa-code.
    1655 When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{f:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
     1531When the signaller thread reaches the location where it should ``release @A & B@'' (listing \ref{lst:int-bulk-cfa} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor @B@ to the waiting thread.
    16561532This ownership transfer is required in order to prevent barging into @B@ by another thread, since both the signalling and signalled threads still need monitor @A@.
    16571533There are three options:
    … …  
    16621538This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from multiple objects to a single group of objects, effectively making the existing single-monitor semantic viable by simply changing monitors to monitor groups.
    16631539This solution releases the monitors once every monitor in a group can be released.
    1664 However, since some monitors are never released (\eg the monitor of a thread), this interpretation means a group might never be released.
     1540However, since some monitors are never released (e.g., the monitor of a thread), this interpretation means a group might never be released.
    16651541A more interesting interpretation is to transfer the group until all its monitors are released, which means the group is not passed further and a thread can retain its locks.
    16661542
    1667 However, listing \ref{f:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
    1668 Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
     1543However, listing \ref{lst:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
     1544Listing \ref{lst:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
    16691545Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
    1670 Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
     1546Depending on the order of signals (listing \ref{lst:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    16711547
    16721548\paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
    … …  
    16751551
    16761552Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order.
    1677 However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
     1553However, regardless of the answer, users can move line \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{lst:dependency}.
    16781554
    16791555In both cases, the threads need to be able to distinguish, on a per monitor basis, which ones need to be released and which ones need to be transferred, which means knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
    … …  
    17101586\end{cfa}
    17111587\end{multicols}
    1712 \begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
     1588\begin{cfa}[caption={Pseudo-code for the three thread example.},label={lst:dependency}]
    17131589\end{cfa}
    17141590\begin{center}
    17151591\input{dependency}
    17161592\end{center}
    1717 \caption{Dependency graph of the statements in listing \ref{f:dependency}}
     1593\caption{Dependency graph of the statements in listing \ref{lst:dependency}}
    17181594\label{fig:dependency}
    17191595\end{figure}
    17201596
    1721 In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
     1597In listing \ref{lst:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
    17221598If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
    17231599Dynamically finding the correct order is therefore the second possible solution.
    17241600The problem is effectively resolving a dependency graph of ownership requirements.
    17251601Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
    1726 This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
     1602This complexity can be seen in listing \ref{lst:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
    17271603Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
    17281604\begin{figure}
    … …  
    17501626\end{cfa}
    17511627\end{multicols}
    1752 \begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
     1628\begin{cfa}[caption={Extension to three monitors of listing \ref{lst:int-bulk-cfa}},label={lst:explosion}]
    17531629\end{cfa}
    17541630\end{figure}
    17551631
    1756 Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
     1632Given the three threads example in listing \ref{lst:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (e.g., $\alpha1$ must happen before $\alpha2$).
    17571633The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
    17581634Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
    … …  
    17601636\subsubsection{Partial Signalling} \label{partial-sig}
    17611637Finally, the solution that is chosen for \CFA is to use partial signalling.
    1762 Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
     1638Again using listing \ref{lst:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
    17631639Only when it reaches line \ref{line:lastRelease} does it actually wake up the waiting thread.
    17641640This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
    … …  
    17661642Furthermore, after being fully implemented, this solution does not appear to have any significant downsides.
    17671643
    1768 Using partial signalling, listing \ref{f:dependency} can be solved easily:
     1644Using partial signalling, listing \ref{lst:dependency} can be solved easily:
    17691645\begin{itemize}
    17701646        \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
    … …  
    19311807This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    19321808Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
    1933 External scheduling can generally be done either in terms of control flow (\eg Ada with @accept@, \uC with @_Accept@) or in terms of data (\eg Go with channels).
     1809External scheduling can generally be done either in terms of control flow (e.g., Ada with @accept@, \uC with @_Accept@) or in terms of data (e.g., Go with channels).
    19341810Of course, both of these paradigms have their own strengths and weaknesses, but for this project, control-flow semantics was chosen to stay consistent with the rest of the languages semantics.
    19351811Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
    … …  
    19971873
    19981874There are other alternatives to these pictures, but in the case of the left picture, implementing a fast accept check is relatively easy.
    1999 Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (\eg 128) of mutex members.
     1875Restricted to a fixed number of mutex members, N, the accept check reduces to updating a bitmask when the acceptor queue changes, a check that executes in a single instruction even with a fairly large number (e.g., 128) of mutex members.
    20001876This approach requires a unique dense ordering of routines with an upper-bound and that ordering must be consistent across translation units.
    20011877For OO languages these constraints are common, since objects only offer adding member routines consistently across translation units via inheritance.
    … …  
    20071883Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
    20081884Storing an array of accepted function pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
    2009 Furthermore, supporting nested external scheduling (\eg listing \ref{f:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
     1885Furthermore, supporting nested external scheduling (e.g., listing \ref{lst:nest-ext}) may now require additional searches for the @waitfor@ statement to check if a routine is already queued.
    20101886
    20111887\begin{figure}
    2012 \begin{cfa}[caption={Example of nested external scheduling},label={f:nest-ext}]
     1888\begin{cfa}[caption={Example of nested external scheduling},label={lst:nest-ext}]
    20131889monitor M {};
    20141890void foo( M & mutex a ) {}
    … …  
    21151991While the set of monitors can be any list of expressions, the function name is more restricted because the compiler validates at compile time the validity of the function type and the parameters used with the @waitfor@ statement.
    21161992It checks that the set of monitors passed in matches the requirements for a function call.
    2117 Figure~\ref{f:waitfor} shows various usages of the waitfor statement and which are acceptable.
     1993Listing \ref{lst:waitfor} shows various usages of the waitfor statement and which are acceptable.
    21181994The choice of the function type is made ignoring any non-@mutex@ parameter.
    21191995One limitation of the current implementation is that it does not handle overloading, but overloading is possible.
    21201996\begin{figure}
    2121 \begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={f:waitfor}]
     1997\begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={lst:waitfor}]
    21221998monitor A{};
    21231999monitor B{};
    … …  
    21562032A @waitfor@ chain can also be followed by a @timeout@, to signify an upper bound on the wait, or an @else@, to signify that the call should be non-blocking, which checks for a matching function call already arrived and otherwise continues.
    21572033Any and all of these clauses can be preceded by a @when@ condition to dynamically toggle the accept clauses on or off based on some current state.
    2158 Figure~\ref{f:waitfor2} demonstrates several complex masks and some incorrect ones.
     2034Listing \ref{lst:waitfor2} demonstrates several complex masks and some incorrect ones.
    21592035
    21602036\begin{figure}
    … …  
    22062082\end{cfa}
    22072083\caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement}
    2208 \label{f:waitfor2}
     2084\label{lst:waitfor2}
    22092085\end{figure}
    22102086
    … …  
    22202096However, a more expressive approach is to flip ordering of execution when waiting for the destructor, meaning that waiting for the destructor allows the destructor to run after the current @mutex@ routine, similarly to how a condition is signalled.
    22212097\begin{figure}
    2222 \begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={f:dtor-order}]
     2098\begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={lst:dtor-order}]
    22232099monitor Executer {};
    22242100struct  Action;
    … …  
    22362112\end{cfa}
    22372113\end{figure}
    2238 For example, listing \ref{f:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
     2114For example, listing \ref{lst:dtor-order} shows an example of an executor with an infinite loop, which waits for the destructor to break out of this loop.
    22392115Switching the semantic meaning introduces an idiomatic way to terminate a task and/or wait for its termination via destruction.
    22402116
    … …  
    22522128In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism.
    22532129Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization.
    2254 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, \etc.
     2130The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, etc.
    22552131However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one.
    22562132There are several alternatives to solve these issues that all have strengths and weaknesses.
    … …  
    22902166While the choice between the three paradigms listed above may have significant performance implications, it is difficult to pin down the performance implications of choosing a model at the language level.
    22912167Indeed, in many situations one of these paradigms may show better performance but it all strongly depends on the workload.
    2292 Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (\ie no thread stack per job).
     2168Having a large amount of mostly independent units of work to execute almost guarantees equivalent performance across paradigms and that the \textbf{pool}-based system has the best efficiency thanks to the lower memory overhead (i.e., no thread stack per job).
    22932169However, interactions among jobs can easily exacerbate contention.
    22942170User-level threads allow fine-grain context switching, which results in better resource utilization, but a context switch is more expensive and the extra control means users need to tweak more variables to get the desired performance.
    … …  
    23422218
    23432219The first step towards the monitor implementation is simple @mutex@ routines.
    2344 In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{f:entry1}.
     2220In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{lst:entry1}.
    23452221The entry/exit procedures do not have to be extended to support multiple monitors.
    23462222Indeed it is sufficient to enter/leave monitors one-by-one as long as the order is correct to prevent deadlock~\cite{Havender68}.
    … …  
    23702246\end{cfa}
    23712247\end{multicols}
    2372 \begin{cfa}[caption={Initial entry and exit routine for monitors},label={f:entry1}]
     2248\begin{cfa}[caption={Initial entry and exit routine for monitors},label={lst:entry1}]
    23732249\end{cfa}
    23742250\end{figure}
    … …  
    23802256First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
    23812257Therefore, the main question is how to support @dtype@ polymorphism.
    2382 It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, \ie acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
     2258It is important to present the difference between the two acquiring options: \textbf{callsite-locking} and entry-point locking, i.e., acquiring the monitors before making a mutex routine-call or as the first operation of the mutex routine-call.
    23832259For example:
    23842260\begin{table}
    … …  
    24372313\end{table}
    24382314
    2439 Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, \eg:
     2315Note the @mutex@ keyword relies on the type system, which means that in cases where a generic monitor-routine is desired, writing the mutex routine is possible with the proper trait, e.g.:
    24402316\begin{cfa}
    24412317// Incorrect: T may not be monitor
    … …  
    24502326Both entry point and \textbf{callsite-locking} are feasible implementations.
    24512327The current \CFA implementation uses entry-point locking because it requires less work when using \textbf{raii}, effectively transferring the burden of implementation to object construction/destruction.
    2452 It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, \ie the function body.
     2328It is harder to use \textbf{raii} for call-site locking, as it does not necessarily have an existing scope that matches exactly the scope of the mutual exclusion, i.e., the function body.
    24532329For example, the monitor call can appear in the middle of an expression.
    24542330Furthermore, entry-point locking requires less code generation since any useful routine is called multiple times but there is only one entry point for many call sites.
    … …  
    24832359Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
    24842360Normally, coroutines also create their own stack to run on, however, in the case of the coroutines used for processors, these coroutines run directly on the \textbf{kthread} stack, effectively stealing the processor stack.
    2485 The exception to this rule is the Main Processor, \ie the initial \textbf{kthread} that is given to any program.
     2361The exception to this rule is the Main Processor, i.e., the initial \textbf{kthread} that is given to any program.
    24862362In order to respect C user expectations, the stack of the initial kernel thread, the main stack of the program, is used by the main user thread rather than the main processor, which can grow very large.
    24872363
    … …  
    25142390When the preemption system receives a change in preemption, it inserts the time in a sorted order and sets a kernel timer for the closest one, effectively stepping through preemption events on each signal sent by the timer.
    25152391These timers use the Linux signal {\tt SIGALRM}, which is delivered to the process rather than the kernel-thread.
    2516 This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, \ie:
     2392This results in an implementation problem, because when delivering signals to a process, the kernel can deliver the signal to any kernel thread for which the signal is not blocked, i.e.:
    25172393\begin{quote}
    25182394A process-directed signal may be delivered to any one of the threads that does not currently have the signal blocked.
    … …  
    25302406However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks.
    25312407For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption.
    2532 One final detail about the alarm thread is how to wake it when additional communication is required (\eg on thread termination).
     2408One final detail about the alarm thread is how to wake it when additional communication is required (e.g., on thread termination).
    25332409This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@.
    25342410Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
    … …  
    25692445\end{figure}
    25702446
    2571 This picture and the proper entry and leave algorithms (see listing \ref{f:entry2}) is the fundamental implementation of internal scheduling.
     2447This picture and the proper entry and leave algorithms (see listing \ref{lst:entry2}) is the fundamental implementation of internal scheduling.
    25722448Note that when a thread is moved from the condition to the AS-stack, it is conceptually split into N pieces, where N is the number of monitors specified in the parameter list.
    25732449The thread is woken up when all the pieces have popped from the AS-stacks and made active.
    … …  
    26022478\end{cfa}
    26032479\end{multicols}
    2604 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={f:entry2}]
     2480\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={lst:entry2}]
    26052481\end{cfa}
    26062482\end{figure}
    26072483
    2608 The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{f:entry2}.
     2484The solution discussed in \ref{intsched} can be seen in the exit routine of listing \ref{lst:entry2}.
    26092485Basically, the solution boils down to having a separate data structure for the condition queue and the AS-stack, and unconditionally transferring ownership of the monitors but only unblocking the thread when the last monitor has transferred ownership.
    26102486This solution is deadlock safe as well as preventing any potential barging.
    … …  
    26222498The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors.
    26232499The @condition node@ is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each @condition criterion@ is moved to the AS-stack.
    2624 Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{f:entry2}.
     2500Once all the criteria have been popped from their respective AS-stacks, the thread is woken up, which is what is shown in listing \ref{lst:entry2}.
    26252501
    26262502% ======================================================================
    … …  
    26302506% ======================================================================
    26312507Similarly to internal scheduling, external scheduling for multiple monitors relies on the idea that waiting-thread queues are no longer specific to a single monitor, as mentioned in section \ref{extsched}.
    2632 For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (\ie no signal statement uses multiple conditions).
     2508For internal scheduling, these queues are part of condition variables, which are still unique for a given scheduling operation (i.e., no signal statement uses multiple conditions).
    26332509However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements.
    26342510This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired.
    … …  
    26572533Note that if a thread has acquired two monitors but executes a @waitfor@ with only one monitor as a parameter, setting the mask of acceptable routines to both monitors will not cause any problems since the extra monitor will not change ownership regardless.
    26582534This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement.
    2659         \item The entry/exit routines need to be updated as shown in listing \ref{f:entry3}.
     2535        \item The entry/exit routines need to be updated as shown in listing \ref{lst:entry3}.
    26602536\end{itemize}
    26612537
    … …  
    26652541Indeed, when waiting for the destructors, storage is needed for the waiting context and the lifetime of said storage needs to outlive the waiting operation it is needed for.
    26662542For regular @waitfor@ statements, the call stack of the routine itself matches this requirement but it is no longer the case when waiting for the destructor since it is pushed on to the AS-stack for later.
    2667 The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{f:entry-dtor}
     2543The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
    26682544
    26692545\begin{figure}
    … …  
    26992575\end{cfa}
    27002576\end{multicols}
    2701 \begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={f:entry3}]
     2577\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={lst:entry3}]
    27022578\end{cfa}
    27032579\end{figure}
    … …  
    27452621\end{cfa}
    27462622\end{multicols}
    2747 \begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={f:entry-dtor}]
     2623\begin{cfa}[caption={Pseudo code for the \protect\lstinline|waitfor| routine and the \protect\lstinline|mutex| entry routine for destructors},label={lst:entry-dtor}]
    27482624\end{cfa}
    27492625\end{figure}
    … …  
    27612637For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine:
    27622638\begin{figure}
    2763 \begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={f:engine-v1}]
     2639\begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={lst:engine-v1}]
    27642640// Visualization declaration
    27652641thread Renderer {} renderer;
    … …  
    27932669Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner:
    27942670\begin{figure}
    2795 \begin{cfa}[caption={Same toy simulator with proper termination condition.},label={f:engine-v2}]
     2671\begin{cfa}[caption={Same toy simulator with proper termination condition.},label={lst:engine-v2}]
    27962672// Visualization declaration
    27972673thread Renderer {} renderer;
    … …  
    28422718}
    28432719\end{cfa}
    2844 This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, \ie no preemption.
    2845 However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{f:fiber-uthread}
     2720This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, i.e., no preemption.
     2721However, once clusters are fully implemented, it will be possible to create fibers and \textbf{uthread} in the same system, as in listing \ref{lst:fiber-uthread}
    28462722\begin{figure}
    28472723\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
    2848 \begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={f:fiber-uthread}]
     2724\begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={lst:fiber-uthread}]
    28492725// Cluster forward declaration
    28502726struct cluster;
    … …  
    29552831Yielding causes the thread to context-switch to the scheduler and back, more precisely: from the \textbf{uthread} to the \textbf{kthread} then from the \textbf{kthread} back to the same \textbf{uthread} (or a different one in the general case).
    29562832In order to make the comparison fair, coroutines also execute a 2-step context-switch by resuming another coroutine which does nothing but suspending in a tight loop, which is a resume/suspend cycle instead of a yield.
    2957 Figure~\ref{f:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
     2833Listing \ref{lst:ctx-switch} shows the code for coroutines and threads with the results in table \ref{tab:ctx-switch}.
    29582834All omitted tests are functionally identical to one of these tests.
    29592835The difference between coroutines and threads can be attributed to the cost of scheduling.
    … …  
    29982874\end{cfa}
    29992875\end{multicols}
    3000 \begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={f:ctx-switch}]
     2876\begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={lst:ctx-switch}]
    30012877\end{cfa}
    30022878\end{figure}
    … …  
    30262902The next interesting benchmark is to measure the overhead to enter/leave a critical-section.
    30272903For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine.
    3028 Figure~\ref{f:mutex} shows the code for \CFA.
     2904Listing \ref{lst:mutex} shows the code for \CFA.
    30292905To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a @pthread_mutex@ lock is also measured.
    30302906The results can be shown in table \ref{tab:mutex}.
    30312907
    30322908\begin{figure}
    3033 \begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={f:mutex}]
     2909\begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={lst:mutex}]
    30342910monitor M {};
    30352911void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
    … …  
    30722948\subsection{Internal Scheduling}
    30732949The internal-scheduling benchmark measures the cost of waiting on and signalling a condition variable.
    3074 Figure~\ref{f:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
     2950Listing \ref{lst:int-sched} shows the code for \CFA, with results table \ref{tab:int-sched}.
    30752951As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    30762952
    30772953\begin{figure}
    3078 \begin{cfa}[caption={Benchmark code for internal scheduling},label={f:int-sched}]
     2954\begin{cfa}[caption={Benchmark code for internal scheduling},label={lst:int-sched}]
    30792955volatile int go = 0;
    30802956condition c;
    … …  
    31313007\subsection{External Scheduling}
    31323008The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC).
    3133 Figure~\ref{f:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
     3009Listing \ref{lst:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
    31343010As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    31353011
    31363012\begin{figure}
    3137 \begin{cfa}[caption={Benchmark code for external scheduling},label={f:ext-sched}]
     3013\begin{cfa}[caption={Benchmark code for external scheduling},label={lst:ext-sched}]
    31383014volatile int go = 0;
    31393015monitor M {};
    … …  
    31853061\end{table}
    31863062
    3187 
    31883063\subsection{Object Creation}
    31893064Finally, the last benchmark measures the cost of creation for concurrent objects.
    3190 Figure~\ref{f:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
     3065Listing \ref{lst:creation} shows the code for @pthread@s and \CFA threads, with results shown in table \ref{tab:creation}.
    31913066As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    31923067The only note here is that the call stacks of \CFA coroutines are lazily created, therefore without priming the coroutine, the creation cost is very low.
    … …  
    32323107\end{center}
    32333108\caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation}
    3234 \label{f:creation}
     3109\label{lst:creation}
    32353110\end{figure}
    32363111
    … …  
    32943169While most of the parallelism tools are aimed at data parallelism and control-flow parallelism, many modern workloads are not bound on computation but on IO operations, a common case being web servers and XaaS (anything as a service).
    32953170These types of workloads often require significant engineering around amortizing costs of blocking IO operations.
    3296 At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (\eg network operations) and registering for notifications instead of waiting for requests to complete.
     3171At its core, non-blocking I/O is an operating system level feature that allows queuing IO operations (e.g., network operations) and registering for notifications instead of waiting for requests to complete.
    32973172In this context, the role of the language makes Non-Blocking IO easily available and with low overhead.
    32983173The current trend is to use asynchronous programming using tools like callbacks and/or futures and promises, which can be seen in frameworks like Node.js~\cite{NodeJs} for JavaScript, Spring MVC~\cite{SpringMVC} for Java and Django~\cite{Django} for Python.
    … …  
    33093184This type of parallelism can be achieved both at the language level and at the library level.
    33103185The canonical example of implicit parallelism is parallel for loops, which are the simplest example of a divide and conquer algorithms~\cite{uC++book}.
    3311 Table \ref{f:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
     3186Table \ref{lst:parfor} shows three different code examples that accomplish point-wise sums of large arrays.
    33123187Note that none of these examples explicitly declare any concurrency or parallelism objects.
    33133188
    … …  
    33923267\end{center}
    33933268\caption{For loop to sum numbers: Sequential, using library parallelism and language parallelism.}
    3394 \label{f:parfor}
     3269\label{lst:parfor}
    33953270\end{table}
    33963271

  • doc/papers/general/Makefile

    r2ae16219 rb2da0574  
    33Build = build
    44Figures = figures
    5 Macros = ../AMA/AMA-stix/ama
     5Macros = AMA/AMA-stix/ama
    66TeXLIB = .:${Macros}:${Build}:../../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    … …  
    7373
    7474WileyNJD-AMA.bst:
    75         ln -fs ../AMA/AMA-stix/ama/WileyNJD-AMA.bst .
     75        ln -fs AMA/AMA-stix/ama/WileyNJD-AMA.bst .
    7676
    7777${GRAPHS} : timing.gp timing.dat

  • doc/papers/general/Paper.tex

    r2ae16219 rb2da0574  
    1 \documentclass[AMA,STIX1COL,STIXSMALL]{WileyNJD-v2}
     1\documentclass[AMA,STIX1COL]{WileyNJD-v2}
     2
    23\articletype{RESEARCH ARTICLE}%
    34
    … …  
    8586% Latin abbreviation
    8687\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
    87 \@ifundefined{eg}{
    8888\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
    8989\newcommand*{\eg}{%
    … …  
    9191                {\@ifnextchar{:}{\EG}%
    9292                        {\EG,\xspace}}%
    93 }}{}%
    94 \@ifundefined{ie}{
     93}%
    9594\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
    9695\newcommand*{\ie}{%
    … …  
    9897                {\@ifnextchar{:}{\IE}%
    9998                        {\IE,\xspace}}%
    100 }}{}%
    101 \@ifundefined{etc}{
     99}%
    102100\newcommand{\ETC}{\abbrevFont{etc}}
    103101\newcommand*{\etc}{%
    104102        \@ifnextchar{.}{\ETC}%
    105103        {\ETC.\xspace}%
    106 }}{}%
    107 \@ifundefined{etal}{
     104}%
    108105\newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
    109 \newcommand*{\etal}{%
     106\renewcommand*{\etal}{%
    110107        \@ifnextchar{.}{\protect\ETAL}%
    111108                {\protect\ETAL.\xspace}%
    112 }}{}%
    113 \@ifundefined{viz}{
     109}%
    114110\newcommand{\VIZ}{\abbrevFont{viz}}
    115111\newcommand*{\viz}{%
    116112        \@ifnextchar{.}{\VIZ}%
    117113                {\VIZ.\xspace}%
    118 }}{}%
     114}%
    119115\makeatother
    120116
    … …  
    178174\author[1]{Robert Schluntz}
    179175\author[1]{Peter A. Buhr*}
    180 \authormark{MOSS \textsc{et al}}
     176\authormark{Aaron Moss \textsc{et al}}
    181177
    182178\address[1]{\orgdiv{David R. Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Ontario}, \country{Canada}}}
    … …  
    20472043\subsection{Integral Suffixes}
    20482044
    2049 New integral suffixes @hh@ (half of half of @int@) for @char@, @h@ (half of @int@) for @short@, and @z@ for @size_t@, and length suffixes for 8, 16, 32, 64, and 128 bit integers.
    2050 %Additional integral suffixes are added to cover all the integral types and lengths.
     2045Additional integral suffixes are added to cover all the integral types and lengths.
    20512046\begin{cquote}
    20522047\lstDeleteShortInline@%
    … …  
    20542049\begin{cfa}
    2055205020_`hh`     // signed char
    2056 21_`hh`u    // unsigned char
     205121_`hhu`   // unsigned char
    2057205222_`h`       // signed short int
    2058 23_u`h`     // unsigned short int
    2059 24`z`       // size_t
     205323_`uh`     // unsigned short int
     205424_`z`       // size_t
    20602055\end{cfa}
    20612056&
    20622057\begin{cfa}
    2063205820_`L8`      // int8_t
    2064 21_u`l8`     // uint8_t
     205921_`ul8`     // uint8_t
    2065206022_`l16`     // int16_t
    2066 23_u`l16`   // uint16_t
     206123_`ul16`   // uint16_t
    2067206224_`l32`     // int32_t
    20682063\end{cfa}
    20692064&
    20702065\begin{cfa}
    2071 25_u`l32`      // uint32_t
     206625_`ul32`      // uint32_t
    2072206726_`l64`        // int64_t
    2073 27_`l64`u      // uint64_t
     206827_`l64u`      // uint64_t
    2074206926_`L128`     // int128
    2075 27_`L128`u   // unsigned int128
     207027_`L128u`   // unsigned int128
    20762071\end{cfa}
    20772072\end{tabular}
    … …  
    21202115\multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{postfix function}}        & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{constant}}      & \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{variable/expression}}   & \multicolumn{1}{c}{\textbf{postfix pointer}}  \\
    21212116\begin{cfa}
    2122 int |?`h|( int s );
    2123 int |?`h|( double s );
    2124 int |?`m|( char c );
    2125 int |?`m|( const char * s );
    2126 int |?`t|( int a, int b, int c );
    2127 \end{cfa}
    2128 &
    2129 \begin{cfa}
    2130 0 |`h|;
    2131 3.5|`h|;
    2132 '1'|`m|;
    2133 "123" "456"|`m|;
    2134 [1,2,3]|`t|;
     2117int ?`h( int s );
     2118int ?`h( double s );
     2119int ?`m( char c );
     2120int ?`m( const char * s );
     2121int ?`t( int a, int b, int c );
     2122\end{cfa}
     2123&
     2124\begin{cfa}
     21250 `h;
     21263.5`h;
     2127'1'`m;
     2128"123" "456"`m;
     2129[1,2,3]`t;
    21352130\end{cfa}
    21362131&
    21372132\begin{cfa}
    21382133int i = 7;
    2139 i|`h|;
    2140 (i + 3)|`h|;
    2141 (i + 3.5)|`h|;
    2142 
    2143 \end{cfa}
    2144 &
    2145 \begin{cfa}
    2146 int (* |?`p|)( int i );
    2147 |?`p| = |?`h|;
    2148 3|`p|;
    2149 i|`p|;
    2150 (i + 3)|`p|;
     2134i`h;
     2135(i + 3)`h;
     2136(i + 3.5)`h;
     2137
     2138\end{cfa}
     2139&
     2140\begin{cfa}
     2141int (* ?`p)( int i );
     2142?`p = ?`h;
     21433`p;
     2144i`p;
     2145(i + 3)`p;
    21512146\end{cfa}
    21522147\end{tabular}

  • doc/refrat/keywords.tex

    r2ae16219 rb2da0574  
    1111%% Created On       : Sun Aug  6 08:17:27 2017
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Fri Apr  6 15:16:11 2018
    14 %% Update Count     : 7
     13%% Last Modified On : Wed Aug 30 22:10:10 2017
     14%% Update Count     : 5
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616\begin{tabular}{@{}llllll@{}}
    1717\begin{tabular}{@{}l@{}}
     18©_At©                   \\
    1819©catch©                 \\
    1920©catchResume©   \\
    2021©choose©                \\
    2122©coroutine©             \\
    22 ©disable©               \\
    2323\end{tabular}
    2424&
    2525\begin{tabular}{@{}l@{}}
     26©disable©               \\
    2627©dtype©                 \\
    2728©enable©                \\
    28 ©exception©             \\
    2929©fallthrough©   \\
    3030©fallthru©              \\
    … …  
    3535©forall©                \\
    3636©ftype©                 \\
     37©lvalue©                \\
    3738©monitor©               \\
    38 ©mutex©                 \\
    3939\end{tabular}
    4040&
    4141\begin{tabular}{@{}l@{}}
     42©mutex©                 \\
    4243©one_t©                 \\
    4344©otype©                 \\
    4445©throw©                 \\
    4546©throwResume©   \\
    46 ©trait©                 \\
    4747\end{tabular}
    4848&
    4949\begin{tabular}{@{}l@{}}
     50©trait©                 \\
    5051©try©                   \\
    5152©ttype©                 \\
    5253©virtual©               \\
    5354©waitfor©               \\
    54 ©when©                  \\
    5555\end{tabular}
    5656&
    5757\begin{tabular}{@{}l@{}}
     58©when©                  \\
    5859©with©                  \\
    5960©zero_t©                \\
    60                                 \\
    6161                                \\
    6262                                \\

  • doc/user/user.tex

    r2ae16219 rb2da0574  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Sat Apr 14 19:04:30 2018
    14 %% Update Count     : 3318
     13%% Last Modified On : Tue Feb 13 08:31:21 2018
     14%% Update Count     : 3161
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    283283
    284284double key = 5.0, vals[10] = { /* 10 sorted floating values */ };
    285 double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      §\C{// search sorted array}§
     285double * val = (double *)bsearch( &key, vals, 10, sizeof(vals[0]), comp );      $\C{// search sorted array}$
    286286\end{lstlisting}
    287287which can be augmented simply with a polymorphic, type-safe, \CFA-overloaded wrappers:
    … …  
    292292
    293293forall( otype T | { int ?<?( T, T ); } ) unsigned int bsearch( T key, const T * arr, size_t size ) {
    294         T * result = bsearch( key, arr, size ); §\C{// call first version}§
    295         return result ? result - arr : size; }  §\C{// pointer subtraction includes sizeof(T)}§
    296 
    297 double * val = bsearch( 5.0, vals, 10 );        §\C{// selection based on return type}§
     294        T * result = bsearch( key, arr, size ); $\C{// call first version}$
     295        return result ? result - arr : size; }  $\C{// pointer subtraction includes sizeof(T)}$
     296
     297double * val = bsearch( 5.0, vals, 10 );        $\C{// selection based on return type}$
    298298int posn = bsearch( 5.0, vals, 10 );
    299299\end{lstlisting}
    … …  
    353353The 1999 C standard plus GNU extensions.
    354354\item
    355 \Indexc[deletekeywords=inline]{-fgnu89-inline}\index{compilation option!-fgnu89-inline@{\lstinline[deletekeywords=inline]@-fgnu89-inline@}}
     355\Indexc[deletekeywords=inline]{-fgnu89-inline}\index{compilation option!-fgnu89-inline@{\lstinline[deletekeywords=inline]$-fgnu89-inline$}}
    356356Use the traditional GNU semantics for inline routines in C99 mode, which allows inline routines in header files.
    357357\end{description}
    … …  
    506506
    507507C, \CC, and Java (and many other programming languages) have no exponentiation operator\index{exponentiation!operator}\index{operator!exponentiation}, \ie $x^y$, and instead use a routine, like \Indexc{pow}, to perform the exponentiation operation.
    508 \CFA extends the basic operators with the exponentiation operator ©?\?©\index{?\\?@\lstinline@?\?@} and ©?\=?©\index{?\\=?@\lstinline@?\=?@}, as in, ©x \ y© and ©x \= y©, which means $x^y$ and $x \leftarrow x^y$.
     508\CFA extends the basic operators with the exponentiation operator ©?\?©\index{?\\?@\lstinline$?\?$} and ©?\=?©\index{?\\=?@\lstinline$?\=?$}, as in, ©x \ y© and ©x \= y©, which means $x^y$ and $x \leftarrow x^y$.
    509509The priority of the exponentiation operator is between the cast and multiplicative operators, so that ©w * (int)x \ (int)y * z© is parenthesized as ©((w * (((int)x) \ ((int)y))) * z)©.
    510510
    … …  
    524524
    525525
    526 \section{\texorpdfstring{Labelled \protect\lstinline@continue@ / \protect\lstinline@break@}{Labelled continue / break}}
     526\section{\texorpdfstring{Labelled \LstKeywordStyle{continue} / \LstKeywordStyle{break}}{Labelled continue / break}}
    527527
    528528While C provides ©continue© and ©break© statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
    529529Unfortunately, this restriction forces programmers to use \Indexc{goto} to achieve the equivalent control-flow for more than one level of nesting.
    530 To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@\lstinline@continue@!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@\lstinline@break@!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85}, as in Java.
     530To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@\lstinline $continue$!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@\lstinline $break$!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85}, as in Java.
    531531For both ©continue© and ©break©, the target label must be directly associated with a ©for©, ©while© or ©do© statement;
    532532for ©break©, the target label can also be associated with a ©switch©, ©if© or compound (©{}©) statement.
    … …  
    613613\end{figure}
    614614
    615 Both labelled ©continue© and ©break© are a ©goto©\index{goto@\lstinline@goto@!restricted} restricted in the following ways:
     615Both labelled ©continue© and ©break© are a ©goto©\index{goto@\lstinline $goto$!restricted} restricted in the following ways:
    616616\begin{itemize}
    617617\item
    … …  
    629629
    630630
    631 \section{\texorpdfstring{\protect\lstinline@switch@ Statement}{switch Statement}}
     631\section{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}}
    632632
    633633C allows a number of questionable forms for the ©switch© statement:
    … …  
    834834
    835835
    836 \section{\texorpdfstring{\protect\lstinline@case@ Clause}{case Clause}}
     836\section{\texorpdfstring{\LstKeywordStyle{case} Clause}{case Clause}}
    837837
    838838C restricts the ©case© clause of a ©switch© statement to a single value.
    … …  
    871871\end{tabular}
    872872\end{cquote}
    873 In addition, subranges are allowed to specify case values.\footnote{
    874 gcc has the same mechanism but awkward syntax, \lstinline@2 ...42@, because a space is required after a number, otherwise the period is a decimal point.}
     873In addition, two forms of subranges are allowed to specify case values: a new \CFA form and an existing GNU C form.\footnote{
     874The GNU C form \emph{requires} spaces around the ellipse.}
     875\begin{cquote}
     876\begin{tabular}{@{}l@{\hspace{3em}}l@{\hspace{2em}}l@{}}
     877\multicolumn{1}{c@{\hspace{3em}}}{\textbf{\CFA}}        & \multicolumn{1}{c@{\hspace{2em}}}{\textbf{GNU C}}     \\
    875878\begin{cfa}
    876879switch ( i ) {
    877   case ®1~5:®                                   §\C{// 1, 2, 3, 4, 5}§
     880  case ®1~5:®
    878881        ...
    879   case ®10~15:®                                 §\C{// 10, 11, 12, 13, 14, 15}§
     882  case ®10~15:®
    880883        ...
    881884}
    882885\end{cfa}
     886&
     887\begin{cfa}
     888switch ( i )
     889  case ®1 ... 5®:
     890        ...
     891  case ®10 ... 15®:
     892        ...
     893}
     894\end{cfa}
     895&
     896\begin{cfa}
     897
     898// 1, 2, 3, 4, 5
     899
     900// 10, 11, 12, 13, 14, 15
     901
     902
     903\end{cfa}
     904\end{tabular}
     905\end{cquote}
    883906Lists of subranges are also allowed.
    884907\begin{cfa}
    … …  
    887910
    888911
    889 \section{\texorpdfstring{\protect\lstinline@with@ Statement}{with Statement}}
    890 \label{s:WithStatement}
    891 
    892 Grouping heterogeneous data into \newterm{aggregate}s (structure/union) is a common programming practice, and an aggregate can be further organized into more complex structures, such as arrays and containers:
    893 \begin{cfa}
    894 struct S {                                                                      §\C{// aggregate}§
    895         char c;                                                                 §\C{// fields}§
    896         int i;
    897         double d;
    898 };
    899 S s, as[10];
    900 \end{cfa}
    901 However, functions manipulating aggregates must repeat the aggregate name to access its containing fields:
    902 \begin{cfa}
    903 void f( S s ) {
    904         `s.`c; `s.`i; `s.`d;                                    §\C{// access containing fields}§
    905 }
    906 \end{cfa}
    907 which extends to multiple levels of qualification for nested aggregates.
    908 A similar situation occurs in object-oriented programming, \eg \CC:
    909 \begin{C++}
    910 struct S {
    911         char c;                                                                 §\C{// fields}§
    912         int i;
    913         double d;
    914         void f() {                                                              §\C{// implicit ``this'' aggregate}§
    915                 `this->`c; `this->`i; `this->`d;        §\C{// access containing fields}§
    916         }
    917 }
    918 \end{C++}
    919 Object-oriented nesting of member functions in a \lstinline[language=C++]@class/struct@ allows eliding \lstinline[language=C++]$this->$ because of lexical scoping.
    920 However, for other aggregate parameters, qualification is necessary:
    921 \begin{cfa}
    922 struct T { double m, n; };
    923 int S::f( T & t ) {                                                     §\C{// multiple aggregate parameters}§
    924         c; i; d;                                                                §\C{\color{red}// this--{\textgreater}.c, this--{\textgreater}.i, this--{\textgreater}.d}§
    925         `t.`m; `t.`n;                                                   §\C{// must qualify}§
    926 }
    927 \end{cfa}
    928 
    929 To simplify the programmer experience, \CFA provides a @with@ statement (see Pascal~\cite[\S~4.F]{Pascal}) to elide aggregate qualification to fields by opening a scope containing the field identifiers.
    930 Hence, the qualified fields become variables with the side-effect that it is easier to optimizing field references in a block.
    931 \begin{cfa}
    932 void f( S & this ) `with ( this )` {            §\C{// with statement}§
    933         c; i; d;                                                                §\C{\color{red}// this.c, this.i, this.d}§
    934 }
    935 \end{cfa}
    936 with the generality of opening multiple aggregate-parameters:
    937 \begin{cfa}
    938 void f( S & s, T & t ) `with ( s, t )` {                §\C{// multiple aggregate parameters}§
    939         c; i; d;                                                                §\C{\color{red}// s.c, s.i, s.d}§
    940         m; n;                                                                   §\C{\color{red}// t.m, t.n}§
    941 }
    942 \end{cfa}
    943 
    944 In detail, the @with@ statement has the form:
    945 \begin{cfa}
    946 §\emph{with-statement}§:
    947         'with' '(' §\emph{expression-list}§ ')' §\emph{compound-statement}§
    948 \end{cfa}
    949 and may appear as the body of a function or nested within a function body.
    950 Each expression in the expression-list provides a type and object.
    951 The type must be an aggregate type.
    952 (Enumerations are already opened.)
    953 The object is the implicit qualifier for the open structure-fields.
    954 
    955 All expressions in the expression list are open in parallel within the compound statement.
    956 This semantic is different from Pascal, which nests the openings from left to right.
    957 The difference between parallel and nesting occurs for fields with the same name and type:
    958 \begin{cfa}
    959 struct S { int `i`; int j; double m; } s, w;
    960 struct T { int `i`; int k; int m; } t, w;
    961 with ( s, t ) {
    962         j + k;                                                                  §\C{// unambiguous, s.j + t.k}§
    963         m = 5.0;                                                                §\C{// unambiguous, t.m = 5.0}§
    964         m = 1;                                                                  §\C{// unambiguous, s.m = 1}§
    965         int a = m;                                                              §\C{// unambiguous, a = s.i }§
    966         double b = m;                                                   §\C{// unambiguous, b = t.m}§
    967         int c = s.i + t.i;                                              §\C{// unambiguous, qualification}§
    968         (double)m;                                                              §\C{// unambiguous, cast}§
    969 }
    970 \end{cfa}
    971 For parallel semantics, both @s.i@ and @t.i@ are visible, so @i@ is ambiguous without qualification;
    972 for nested semantics, @t.i@ hides @s.i@, so @i@ implies @t.i@.
    973 \CFA's ability to overload variables means fields with the same name but different types are automatically disambiguated, eliminating most qualification when opening multiple aggregates.
    974 Qualification or a cast is used to disambiguate.
    975 
    976 There is an interesting problem between parameters and the function-body @with@, \eg:
    977 \begin{cfa}
    978 void ?{}( S & s, int i ) with ( s ) {           §\C{// constructor}§
    979         `s.i = i;`  j = 3;  m = 5.5;                    §\C{// initialize fields}§
    980 }
    981 \end{cfa}
    982 Here, the assignment @s.i = i@ means @s.i = s.i@, which is meaningless, and there is no mechanism to qualify the parameter @i@, making the assignment impossible using the function-body @with@.
    983 To solve this problem, parameters are treated like an initialized aggregate:
    984 \begin{cfa}
    985 struct Params {
    986         S & s;
    987         int i;
    988 } params;
    989 \end{cfa}
    990 and implicitly opened \emph{after} a function-body open, to give them higher priority:
    991 \begin{cfa}
    992 void ?{}( S & s, int `i` ) with ( s ) `with( §\emph{\color{red}params}§ )` {
    993         s.i = `i`; j = 3; m = 5.5;
    994 }
    995 \end{cfa}
    996 Finally, a cast may be used to disambiguate among overload variables in a @with@ expression:
    997 \begin{cfa}
    998 with ( w ) { ... }                                                      §\C{// ambiguous, same name and no context}§
    999 with ( (S)w ) { ... }                                           §\C{// unambiguous, cast}§
    1000 \end{cfa}
    1001 and @with@ expressions may be complex expressions with type reference (see Section~\ref{s:References}) to aggregate:
    1002 % \begin{cfa}
    1003 % struct S { int i, j; } sv;
    1004 % with ( sv ) {                                                         §\C{// implicit reference}§
    1005 %       S & sr = sv;
    1006 %       with ( sr ) {                                                   §\C{// explicit reference}§
    1007 %               S * sp = &sv;
    1008 %               with ( *sp ) {                                          §\C{// computed reference}§
    1009 %                       i = 3; j = 4;                                   §\C{\color{red}// sp--{\textgreater}i, sp--{\textgreater}j}§
    1010 %               }
    1011 %               i = 2; j = 3;                                           §\C{\color{red}// sr.i, sr.j}§
    1012 %       }
    1013 %       i = 1; j = 2;                                                   §\C{\color{red}// sv.i, sv.j}§
    1014 % }
    1015 % \end{cfa}
     912\section{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}
     913\label{s:WithClauseStatement}
    1016914
    1017915In \Index{object-oriented} programming, there is an implicit first parameter, often names \textbf{©self©} or \textbf{©this©}, which is elided.
    … …  
    1037935\CFA provides a ©with© clause/statement (see Pascal~\cite[\S~4.F]{Pascal}) to elided the "©this.©" by opening a scope containing field identifiers, changing the qualified fields into variables and giving an opportunity for optimizing qualified references.
    1038936\begin{cfa}
    1039 int mem( S & this ) ®with( this )® { §\C{// with clause}§
     937int mem( S & this ) ®with this® { §\C{// with clause}§
    1040938        i = 1;                                          §\C{\color{red}// this.i}§
    1041939        j = 2;                                          §\C{\color{red}// this.j}§
    … …  
    1045943\begin{cfa}
    1046944struct T { double m, n; };
    1047 int mem2( S & this1, T & this2 ) ®with( this1, this2 )® {
     945int mem2( S & this1, T & this2 ) ®with this1, this2® {
    1048946        i = 1; j = 2;
    1049947        m = 1.0; n = 2.0;
    … …  
    1056954        struct S1 { ... } s1;
    1057955        struct S2 { ... } s2;
    1058         ®with( s1 )® {                          §\C{// with statement}§
     956        ®with s1® {                                     §\C{// with statement}§
    1059957                // access fields of s1 without qualification
    1060958                ®with s2® {                             §\C{// nesting}§
    … …  
    1073971struct S { int i; int j; double m; } a, c;
    1074972struct T { int i; int k; int m } b, c;
    1075 with( a, b )
    1076 {
    1077 }
    1078 \end{cfa}
    1079 
    1080 \begin{comment}
     973®with a, b® {
     974        j + k;                                          §\C{// unambiguous, unique names define unique types}§
     975        i;                                                      §\C{// ambiguous, same name and type}§
     976        a.i + b.i;                                      §\C{// unambiguous, qualification defines unique names}§
     977        m;                                                      §\C{// ambiguous, same name and no context to define unique type}§
     978        m = 5.0;                                        §\C{// unambiguous, same name and context defines unique type}§
     979        m = 1;                                          §\C{// unambiguous, same name and context defines unique type}§
     980}
     981®with c® { ... }                                §\C{// ambiguous, same name and no context}§
     982®with (S)c® { ... }                             §\C{// unambiguous, same name and cast defines unique type}§
     983\end{cfa}
     984
    1081985The components in the "with" clause
    1082986
    … …  
    11031007the "with" to be implemented because I hate having to type all those object
    11041008names for fields. It's a great way to drive people away from the language.
    1105 \end{comment}
    11061009
    11071010
    … …  
    16921595
    16931596\item
    1694 lvalue to reference conversion: \lstinline[deletekeywords=lvalue]@lvalue-type cv1 T@ converts to ©cv2 T &©, which allows implicitly converting variables to references.
     1597lvalue to reference conversion: \lstinline[deletekeywords=lvalue]$lvalue-type cv1 T$ converts to ©cv2 T &©, which allows implicitly converting variables to references.
    16951598\begin{cfa}
    16961599int x, &r = ®x®, f( int & p ); // lvalue variable (int) convert to reference (int &)
    … …  
    64586361
    64596362
    6460 \section{Time}
    6461 \label{s:TimeLib}
    6462 
    6463 
    6464 %\subsection{\texorpdfstring{\protect\lstinline@Duration@}{Duration}}
    6465 \subsection{\texorpdfstring{\LstKeywordStyle{\textmd{Duration}}}{Duration}}
    6466 \label{s:Duration}
    6467 
    6468 \leavevmode
    6469 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6470 struct Duration {
    6471         int64_t tv;                                                     §\C{// nanoseconds}§
    6472 };
    6473 
    6474 void ?{}( Duration & dur );
    6475 void ?{}( Duration & dur, zero_t );
    6476 
    6477 Duration ?=?( Duration & dur, zero_t );
    6478 
    6479 Duration +?( Duration rhs );
    6480 Duration ?+?( Duration & lhs, Duration rhs );
    6481 Duration ?+=?( Duration & lhs, Duration rhs );
    6482 
    6483 Duration -?( Duration rhs );
    6484 Duration ?-?( Duration & lhs, Duration rhs );
    6485 Duration ?-=?( Duration & lhs, Duration rhs );
    6486 
    6487 Duration ?*?( Duration lhs, int64_t rhs );
    6488 Duration ?*?( int64_t lhs, Duration rhs );
    6489 Duration ?*=?( Duration & lhs, int64_t rhs );
    6490 
    6491 int64_t ?/?( Duration lhs, Duration rhs );
    6492 Duration ?/?( Duration lhs, int64_t rhs );
    6493 Duration ?/=?( Duration & lhs, int64_t rhs );
    6494 double div( Duration lhs, Duration rhs );
    6495 
    6496 Duration ?%?( Duration lhs, Duration rhs );
    6497 Duration ?%=?( Duration & lhs, Duration rhs );
    6498 
    6499 _Bool ?==?( Duration lhs, Duration rhs );
    6500 _Bool ?!=?( Duration lhs, Duration rhs );
    6501 _Bool ?<? ( Duration lhs, Duration rhs );
    6502 _Bool ?<=?( Duration lhs, Duration rhs );
    6503 _Bool ?>? ( Duration lhs, Duration rhs );
    6504 _Bool ?>=?( Duration lhs, Duration rhs );
    6505 
    6506 _Bool ?==?( Duration lhs, zero_t );
    6507 _Bool ?!=?( Duration lhs, zero_t );
    6508 _Bool ?<? ( Duration lhs, zero_t );
    6509 _Bool ?<=?( Duration lhs, zero_t );
    6510 _Bool ?>? ( Duration lhs, zero_t );
    6511 _Bool ?>=?( Duration lhs, zero_t );
    6512 
    6513 Duration abs( Duration rhs );
    6514 
    6515 forall( dtype ostype | ostream( ostype ) ) ostype & ?|?( ostype & os, Duration dur );
    6516 
    6517 Duration ?`ns( int64_t nsec );
    6518 Duration ?`us( int64_t usec );
    6519 Duration ?`ms( int64_t msec );
    6520 Duration ?`s( int64_t sec );
    6521 Duration ?`s( double sec );
    6522 Duration ?`m( int64_t min );
    6523 Duration ?`m( double min );
    6524 Duration ?`h( int64_t hours );
    6525 Duration ?`h( double hours );
    6526 Duration ?`d( int64_t days );
    6527 Duration ?`d( double days );
    6528 Duration ?`w( int64_t weeks );
    6529 Duration ?`w( double weeks );
    6530 
    6531 int64_t ?`ns( Duration dur );
    6532 int64_t ?`us( Duration dur );
    6533 int64_t ?`ms( Duration dur );
    6534 int64_t ?`s( Duration dur );
    6535 int64_t ?`m( Duration dur );
    6536 int64_t ?`h( Duration dur );
    6537 int64_t ?`d( Duration dur );
    6538 int64_t ?`w( Duration dur );
    6539 \end{cfa}
    6540 
    6541 
    6542 %\subsection{\texorpdfstring{\protect\lstinline@\timeval@}{timeval}}
    6543 \subsection{\texorpdfstring{\LstKeywordStyle{\textmd{timeval}}}{timeval}}
    6544 \label{s:timeval}
    6545 
    6546 \leavevmode
    6547 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6548 void ?{}( timeval & t );
    6549 void ?{}( timeval & t, time_t sec, suseconds_t usec );
    6550 void ?{}( timeval & t, time_t sec );
    6551 void ?{}( timeval & t, zero_t );
    6552 void ?{}( timeval & t, Time time );
    6553 
    6554 timeval ?=?( timeval & t, zero_t );
    6555 timeval ?+?( timeval & lhs, timeval rhs );
    6556 timeval ?-?( timeval & lhs, timeval rhs );
    6557 _Bool ?==?( timeval lhs, timeval rhs );
    6558 _Bool ?!=?( timeval lhs, timeval rhs );
    6559 \end{cfa}
    6560 
    6561 
    6562 \subsection{\texorpdfstring{\protect\lstinline@timespec@}{timespec}}
    6563 \label{s:timespec}
    6564 
    6565 \leavevmode
    6566 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6567 void ?{}( timespec & t );
    6568 void ?{}( timespec & t, time_t sec, __syscall_slong_t nsec );
    6569 void ?{}( timespec & t, time_t sec );
    6570 void ?{}( timespec & t, zero_t );
    6571 void ?{}( timespec & t, Time time );
    6572 
    6573 timespec ?=?( timespec & t, zero_t );
    6574 timespec ?+?( timespec & lhs, timespec rhs );
    6575 timespec ?-?( timespec & lhs, timespec rhs );
    6576 _Bool ?==?( timespec lhs, timespec rhs );
    6577 _Bool ?!=?( timespec lhs, timespec rhs );
    6578 \end{cfa}
    6579 
    6580 
    6581 \subsection{\texorpdfstring{\protect\lstinline@itimerval@}{itimerval}}
    6582 \label{s:itimerval}
    6583 
    6584 \leavevmode
    6585 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6586 void ?{}( itimerval & itv, Duration alarm );
    6587 void ?{}( itimerval & itv, Duration alarm, Duration interval );
    6588 \end{cfa}
    6589 
    6590 
    6591 \subsection{\texorpdfstring{\protect\lstinline@Time@}{Time}}
    6592 \label{s:Time}
    6593 
    6594 \leavevmode
    6595 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6596 struct Time {
    6597         uint64_t tv;                                            §\C{// nanoseconds since UNIX epoch}§
    6598 };
    6599 
    6600 void ?{}( Time & time );
    6601 void ?{}( Time & time, zero_t );
    6602 void ?{}( Time & time, int year, int month = 0, int day = 0, int hour = 0, int min = 0, int sec = 0, int nsec = 0 );
    6603 Time ?=?( Time & time, zero_t );
    6604 
    6605 void ?{}( Time & time, timeval t );
    6606 Time ?=?( Time & time, timeval t );
    6607 
    6608 void ?{}( Time & time, timespec t );
    6609 Time ?=?( Time & time, timespec t );
    6610 
    6611 Time ?+?( Time & lhs, Duration rhs ) { return (Time)@{ lhs.tv + rhs.tv }; }
    6612 Time ?+?( Duration lhs, Time rhs ) { return rhs + lhs; }
    6613 Time ?+=?( Time & lhs, Duration rhs ) { lhs = lhs + rhs; return lhs; }
    6614 
    6615 Duration ?-?( Time lhs, Time rhs ) { return (Duration)@{ lhs.tv - rhs.tv }; }
    6616 Time ?-?( Time lhs, Duration rhs ) { return (Time)@{ lhs.tv - rhs.tv }; }
    6617 Time ?-=?( Time & lhs, Duration rhs ) { lhs = lhs - rhs; return lhs; }
    6618 _Bool ?==?( Time lhs, Time rhs ) { return lhs.tv == rhs.tv; }
    6619 _Bool ?!=?( Time lhs, Time rhs ) { return lhs.tv != rhs.tv; }
    6620 _Bool ?<?( Time lhs, Time rhs ) { return lhs.tv < rhs.tv; }
    6621 _Bool ?<=?( Time lhs, Time rhs ) { return lhs.tv <= rhs.tv; }
    6622 _Bool ?>?( Time lhs, Time rhs ) { return lhs.tv > rhs.tv; }
    6623 _Bool ?>=?( Time lhs, Time rhs ) { return lhs.tv >= rhs.tv; }
    6624 
    6625 forall( dtype ostype | ostream( ostype ) ) ostype & ?|?( ostype & os, Time time );
    6626 
    6627 char * yy_mm_dd( Time time, char * buf );
    6628 char * ?`ymd( Time time, char * buf ) { // short form
    6629         return yy_mm_dd( time, buf );
    6630 } // ymd
    6631 
    6632 char * mm_dd_yy( Time time, char * buf );
    6633 char * ?`mdy( Time time, char * buf ) { // short form
    6634         return mm_dd_yy( time, buf );
    6635 } // mdy
    6636 
    6637 char * dd_mm_yy( Time time, char * buf );
    6638 char * ?`dmy( Time time, char * buf ) { // short form
    6639         return dd_mm_yy( time, buf );;
    6640 } // dmy
    6641 
    6642 size_t strftime( char * buf, size_t size, const char * fmt, Time time );
    6643 \end{cfa}
    6644 
    6645 
    6646 \section{Clock}
    6647 
    6648 \subsection{C time}
    6649 \label{s:Ctime}
    6650 
    6651 \leavevmode
    6652 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6653 char * ctime( time_t tp );
    6654 char * ctime_r( time_t tp, char * buf );
    6655 tm * gmtime( time_t tp );
    6656 tm * gmtime_r( time_t tp, tm * result );
    6657 tm * localtime( time_t tp );
    6658 tm * localtime_r( time_t tp, tm * result );
    6659 \end{cfa}
    6660 
    6661 
    6662 %\subsection{\texorpdfstring{\protect\lstinline@Clock@}{Clock}}
    6663 \subsection{\texorpdfstring{\LstKeywordStyle{\textmd{Clock}}}{Clock}}
    6664 \label{s:Clock}
    6665 
    6666 \leavevmode
    6667 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
    6668 struct Clock {
    6669         Duration offset;                                        §\C{// for virtual clock: contains offset from real-time}§
    6670         int clocktype;                                          §\C{// implementation only -1 (virtual), CLOCK\_REALTIME}§
    6671 };
    6672 
    6673 void resetClock( Clock & clk );
    6674 void resetClock( Clock & clk, Duration adj );
    6675 void ?{}( Clock & clk );
    6676 void ?{}( Clock & clk, Duration adj );
    6677 Duration getRes();
    6678 Time getTimeNsec();                                             §\C{// with nanoseconds}§
    6679 Time getTime();                                                 §\C{// without nanoseconds}§
    6680 Time getTime( Clock & clk );
    6681 Time ?()( Clock & clk );
    6682 timeval getTime( Clock & clk );
    6683 tm getTime( Clock & clk );
    6684 \end{cfa}
    6685 
    6686 
    66876363\section{Multi-precision Integers}
    66886364\label{s:MultiPrecisionIntegers}
    … …  
    69826658\end{cfa}
    69836659
     6660
    69846661\bibliographystyle{plain}
    69856662\bibliography{pl}

  • src/Common/SemanticError.cc

    r2ae16219 rb2da0574  
    6868}
    6969
    70 void SemanticWarningImpl( CodeLocation location, Warning warning, const char * const fmt, ... ) {
    71         Severity severity = WarningFormats[(int)warning].severity;
    72         switch(severity) {
    73         case Severity::Suppress :
    74                 break;
    75         case Severity::Warn :
    76                 {
    77                         va_list args;
    78                         va_start(args, fmt);
    79                         std::string msg = fmtToString( fmt, args );
    80                         va_end(args);
    81                         std::cerr << ErrorHelpers::bold() << location << ErrorHelpers::warning_str() << ErrorHelpers::reset_font() << msg << std::endl;
    82                 }
    83                 break;
    84         case Severity::Error :
    85                 {
    86                         va_list args;
    87                         va_start(args, fmt);
    88                         std::string msg = fmtToString( fmt, args );
    89                         va_end(args);
    90                         SemanticError(location, msg);
    91                 }
    92                 break;
    93         case Severity::Critical :
    94                 assertf(false, "Critical errors not implemented yet");
    95                 break;
    96         }
     70void SemanticWarningImpl( CodeLocation location, Warning, const char * const fmt, ... ) {
     71        va_list args;
     72        va_start(args, fmt);
     73        std::string msg = fmtToString( fmt, args );
     74        va_end(args);
     75        std::cerr << ErrorHelpers::bold() << location << ErrorHelpers::warning_str() << ErrorHelpers::reset_font() << msg << std::endl;
    9776}
    9877

  • src/Common/SemanticError.h

    r2ae16219 rb2da0574  
    3636// Warnings
    3737
    38 enum class Severity {
    39         Suppress,
    40         Warn,
    41         Error,
    42         Critical
    43 };
    44 
    45 struct WarningData {
    46         const char * const name;
    47         const char * const message;
    48         mutable Severity severity;
    49 };
    50 
    51 constexpr const WarningData WarningFormats[] = {
    52         {"self-assign"         , "self assignment of expression: %s"           , Severity::Warn},
    53         {"reference-conversion", "rvalue to reference conversion of rvalue: %s", Severity::Warn},
     38constexpr const char * const WarningFormats[] = {
     39        "self assignment of expression: %s",
     40        "rvalue to reference conversion of rvalue: %s",
    5441};
    5542
    … …  
    6552);
    6653
    67 #define SemanticWarning(loc, id, ...) SemanticWarningImpl(loc, id, WarningFormats[(int)id].message, __VA_ARGS__)
     54// ## used here to allow empty __VA_ARGS__
     55#define SemanticWarning(loc, id, ...) SemanticWarningImpl(loc, id, WarningFormats[(int)id], ## __VA_ARGS__)
    6856
    6957void SemanticWarningImpl (CodeLocation loc, Warning warn, const char * const fmt, ...) __attribute__((format(printf, 3, 4)));

  • src/Parser/parser.yy

    r2ae16219 rb2da0574  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Tue Apr 17 17:10:30 2018
    13 // Update Count     : 3144
     12// Last Modified On : Wed Mar 28 17:52:24 2018
     13// Update Count     : 3130
    1414//
    1515
    … …  
    391391%precedence '('
    392392
    393 %locations                                                                                              // support location tracking for error messages
     393%locations                      // support location tracking for error messages
    394394
    395395%start translation_unit                                                                 // parse-tree root
    … …  
    17081708        | LONG
    17091709                { $$ = DeclarationNode::newLength( DeclarationNode::Long ); }
     1710        | ZERO_T
     1711                { $$ = DeclarationNode::newBuiltinType( DeclarationNode::Zero ); }
     1712        | ONE_T
     1713                { $$ = DeclarationNode::newBuiltinType( DeclarationNode::One ); }
    17101714        | VALIST                                                                                        // GCC, __builtin_va_list
    17111715                { $$ = DeclarationNode::newBuiltinType( DeclarationNode::Valist ); }
    … …  
    17271731basic_type_specifier:
    17281732        direct_type
    1729                 // Cannot have type modifiers, e.g., short, long, etc.
    17301733        | type_qualifier_list_opt indirect_type type_qualifier_list_opt
    17311734                { $$ = $2->addQualifiers( $1 )->addQualifiers( $3 ); }
    … …  
    17331736
    17341737direct_type:
     1738                // A semantic check is necessary for conflicting type qualifiers.
    17351739        basic_type_name
    17361740        | type_qualifier_list basic_type_name
    … …  
    17511755        | ATTR_TYPEGENname '(' comma_expression ')'                     // CFA: e.g., @type(a+b) y;
    17521756                { $$ = DeclarationNode::newAttr( $1, $3 ); }
    1753         | ZERO_T                                                                                        // CFA
    1754                 { $$ = DeclarationNode::newBuiltinType( DeclarationNode::Zero ); }
    1755         | ONE_T                                                                                         // CFA
    1756                 { $$ = DeclarationNode::newBuiltinType( DeclarationNode::One ); }
    17571757        ;
    17581758

  • src/libcfa/time

    r2ae16219 rb2da0574  
    1010// Created On       : Wed Mar 14 23:18:57 2018
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Apr 14 17:48:23 2018
    13 // Update Count     : 636
     12// Last Modified On : Fri Apr 13 07:51:52 2018
     13// Update Count     : 634
    1414//
    1515
    … …  
    2929
    3030//######################### Duration #########################
     31
     32static inline void ?{}( Duration & dur, Duration d ) with( dur ) { tv = d.tv; }
    3133
    3234static inline Duration ?=?( Duration & dur, zero_t ) { return dur{ 0 }; }
    … …  
    135137//######################### Time #########################
    136138
     139static inline void ?{}( Time & time, Time t ) with( time ) { tv = t.tv; }
    137140void ?{}( Time & time, int year, int month = 0, int day = 0, int hour = 0, int min = 0, int sec = 0, int nsec = 0 );
     141static inline void ?{}( Time & time, timeval t ) with( time ) { tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_usec * 1000; }
     142
    138143static inline Time ?=?( Time & time, zero_t ) { return time{ 0 }; }
    139144
    140 static inline void ?{}( Time & time, timeval t ) with( time ) { tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_usec * 1000; }
    141145static inline Time ?=?( Time & time, timeval t ) with( time ) {
    142146        tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_usec * (TIMEGRAN / 1_000_000LL);
    … …  
    144148} // ?=?
    145149
    146 static inline void ?{}( Time & time, timespec t ) with( time ) { tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_nsec; }
     150static inline void ?{}( Time & time, timespec t ) with( time ) {
     151        tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_nsec;
     152} // Time
     153
    147154static inline Time ?=?( Time & time, timespec t ) with( time ) {
    148155        tv = (int64_t)t.tv_sec * TIMEGRAN + t.tv_nsec;

  • src/tests/concurrent/preempt.c

    r2ae16219 rb2da0574  
    1111}
    1212
    13 #ifdef LONG_TEST
    14 static const unsigned long N = 30_000ul;
    15 #else
    16 static const unsigned long N = 500ul;
    17 #endif
    18 
    1913static volatile int counter = 0;
    2014
    … …  
    2822
    2923void main(worker_t & this) {
    30         while(counter < N) {
     24        while(counter < 1000) {
    3125                if( (counter % 7) == this.value ) {
    3226                        int next = __atomic_add_fetch_4(&counter, 1, __ATOMIC_SEQ_CST);

  • tools/prettyprinter/Makefile.am

    r2ae16219 rb2da0574  
    1111## Created On       : Wed Jun 28 12:07:10 2017
    1212## Last Modified By : Peter A. Buhr
    13 ## Last Modified On : Mon Apr 16 09:43:23 2018
    14 ## Update Count     : 20
     13## Last Modified On : Wed Jun 28 23:11:56 2017
     14## Update Count     : 15
    1515###############################################################################
    1616

  • tools/prettyprinter/lex.ll

    r2ae16219 rb2da0574  
    1010 * Created On       : Sat Dec 15 11:45:59 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Sun Apr 15 21:28:33 2018
    13  * Update Count     : 271
     12 * Last Modified On : Tue Aug 29 17:33:36 2017
     13 * Update Count     : 268
    1414 */
    1515
    … …  
    5050<INITIAL,C_CODE>"/*" {                                                                  // C style comments */
    5151#if defined(DEBUG_ALL) | defined(DEBUG_COMMENT)
    52                 cerr << "\"/*\" : " << yytext << endl;
     52    cerr << "\"/*\" : " << yytext << endl;
    5353#endif
    54                 if ( YYSTATE == C_CODE ) code_str += yytext;
    55                 else comment_str += yytext;
    56                 yy_push_state(C_COMMENT);
     54    if ( YYSTATE == C_CODE ) code_str += yytext;
     55    else comment_str += yytext;
     56    yy_push_state(C_COMMENT);
    5757}
    5858<C_COMMENT>(.|"\n")     {                                                                       // C style comments
    5959#if defined(DEBUG_ALL) | defined(DEBUG_COMMENT)
    60                 cerr << "<C_COMMENT>(.|\\n) : " << yytext << endl;
     60    cerr << "<C_COMMENT>(.|\\n) : " << yytext << endl;
    6161#endif
    62                 if ( yy_top_state() == C_CODE ) code_str += yytext;
    63                 else comment_str += yytext;
     62    if ( yy_top_state() == C_CODE ) code_str += yytext;
     63    else comment_str += yytext;
    6464}
    6565<C_COMMENT>"*/" {                                                                               // C style comments
    … …  
    123123<C_CODE>"%}"    { RETURN_TOKEN( RCURL ) }
    124124
    125 ^"%define"[^\n]*"\n" { RETURN_TOKEN( DEFINE ) }
    126 ^"%expect"              { RETURN_TOKEN( EXPECT ) }
    127 ^"%left"                { RETURN_TOKEN( LEFT ) }
    128 ^"%locations"   { RETURN_TOKEN( LOCATIONS ) }
    129 ^"%nonassoc"    { RETURN_TOKEN( NONASSOC ) }
    130 ^"%precedence"  { RETURN_TOKEN( PRECEDENCE ) }
     125^"%union"       { RETURN_TOKEN( UNION ) }
     126^"%start"       { RETURN_TOKEN( START ) }
     127^"%token"       { RETURN_TOKEN( TOKEN ) }
     128^"%type"            { RETURN_TOKEN( TYPE ) }
     129^"%left"            { RETURN_TOKEN( LEFT ) }
     130^"%right"           { RETURN_TOKEN( RIGHT ) }
     131^"%nonassoc"    { RETURN_TOKEN( NONASSOC ) }
     132^"%precedence"  { RETURN_TOKEN( PRECEDENCE ) }
    131133^"%pure_parser" { RETURN_TOKEN( PURE_PARSER ) }
    132 ^"%right"               { RETURN_TOKEN( RIGHT ) }
    133134^"%semantic_parser"     { RETURN_TOKEN( SEMANTIC_PARSER ) }
    134 ^"%start"               { RETURN_TOKEN( START ) }
    135 ^"%thong"               { RETURN_TOKEN( THONG ) }
    136 ^"%token"               { RETURN_TOKEN( TOKEN ) }
    137 ^"%type"                { RETURN_TOKEN( TYPE ) }
    138 ^"%union"               { RETURN_TOKEN( UNION ) }
     135^"%expect"      { RETURN_TOKEN( EXPECT ) }
     136^"%thong"               { RETURN_TOKEN( THONG ) }
    139137
    140 "%prec"                 { RETURN_TOKEN( PREC ) }
     138"%prec"                 { RETURN_TOKEN( PREC ) }
    141139
    142 {integer}               { RETURN_TOKEN( INTEGER ); }
    143 [']{c_char}[']  { RETURN_TOKEN( CHARACTER ); }
    144 {identifier}    { RETURN_TOKEN( IDENTIFIER ); }
     140{integer}           { RETURN_TOKEN( INTEGER ); }
     141[']{c_char}[']  { RETURN_TOKEN( CHARACTER ); }
     142{identifier}    { RETURN_TOKEN( IDENTIFIER ); }
    145143
    146144<C_CODE>["]{s_char}*["] {                                                               // hide braces "{}" in strings
    … …  
    162160%%
    163161void lexC(void) {
    164         BEGIN(C_CODE);
     162    BEGIN(C_CODE);
    165163}
    166164
    167165string lexYacc(void) {
    168         BEGIN(INITIAL);
    169         //cerr << "CODE: " << endl << code_str << endl;
    170         string temp( code_str );
    171         code_str = "";
    172         return temp;
     166    BEGIN(INITIAL);
     167    //cerr << "CODE: " << endl << code_str << endl;
     168    string temp( code_str );
     169    code_str = "";
     170    return temp;
    173171}
    174172

  • tools/prettyprinter/parser.yy

    r2ae16219 rb2da0574  
    1010// Created On       : Sat Dec 15 13:44:21 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sun Apr 15 21:40:30 2018
    13 // Update Count     : 1052
     12// Last Modified On : Tue Aug 29 16:34:10 2017
     13// Update Count     : 1047
    1414//
    1515
    … …  
    6161%token<tokenp>  CODE                                                                    // C code
    6262
    63 %token<tokenp>  DEFINE                                                                  // %define
    64 %token<tokenp>  EXPECT                                                                  // %expect
     63%token<tokenp>  START                                                                   // %start
     64%token<tokenp>  UNION                                                                   // %union
     65%token<tokenp>  TOKEN                                                                   // %token
    6566%token<tokenp>  LEFT                                                                    // %left
    66 %token<tokenp>  LOCATIONS                                                               // %locations
     67%token<tokenp>  RIGHT                                                                   // %right
    6768%token<tokenp>  NONASSOC                                                                // %nonassoc
    6869%token<tokenp>  PRECEDENCE                                                              // %precedence
     70%token<tokenp>  TYPE                                                                    // %type
    6971%token<tokenp>  PURE_PARSER                                                             // %pure_parser
    70 %token<tokenp>  RIGHT                                                                   // %right
    7172%token<tokenp>  SEMANTIC_PARSER                                                 // %semantic_parser
    72 %token<tokenp>  START                                                                   // %start
     73%token<tokenp>  EXPECT                                                                  // %expect
    7374%token<tokenp>  THONG                                                                   // %thong
    74 %token<tokenp>  TOKEN                                                                   // %token
    75 %token<tokenp>  TYPE                                                                    // %type
    76 %token<tokenp>  UNION                                                                   // %union
    7775
    7876%token<tokenp>  PREC                                                                    // %prec
    7977
    80 %token                  END_TERMINALS                                                   // ALL TERMINAL TOKEN NAMES MUST APPEAR BEFORE THIS
     78%token          END_TERMINALS                                                           // ALL TERMINAL TOKEN NAMES MUST APPEAR BEFORE THIS
    8179
    8280%type<tokenp>   sections
    83 %token                  _SECTIONS
     81%token          _SECTIONS
    8482%type<tokenp>   mark
    8583%type<tokenp>   defsection_opt
    86 %token                  _DEFSECTION_OPT
     84%token          _DEFSECTION_OPT
    8785%type<tokenp>   declarations
    8886%type<tokenp>   literalblock
    89 %token                  _LITERALBLOCK
     87%token          _LITERALBLOCK
    9088%type<tokenp>   declaration
    91 %token                  _DECLARATION
     89%token          _DECLARATION
    9290%type<tokenp>   union
    9391%type<tokenp>   rword
    9492%type<tokenp>   tag_opt
    95 %token                  _TAG_OPT
     93%token          _TAG_OPT
    9694%type<tokenp>   namenolist
    97 %token                  _NAMENOLIST
     95%token          _NAMENOLIST
    9896%type<tokenp>   nameno
    99 %token                  _NAMENO
     97%token          _NAMENO
    10098%type<tokenp>   namelist
    101 %token                  _NAMELIST
     99%token          _NAMELIST
    102100%type<tokenp>   name
    103101%type<tokenp>   rulesection
    104 %token                  _RULESECTION
     102%token          _RULESECTION
    105103%type<tokenp>   rules
    106 %token                  _RULE
     104%token          _RULE
    107105%type<tokenp>   lhs
    108 %token                  _LHS
     106%token          _LHS
    109107%type<tokenp>   rhs
    110 %token                  _RHS
     108%token          _RHS
    111109%type<tokenp>   prod
    112110%type<tokenp>   prec
    113 %token                  _PREC
     111%token          _PREC
    114112%type<tokenp>   action
    115 %token                  _ACTION
     113%token          _ACTION
    116114%type<tokenp>   usersection_opt
    117 %token                  _USERSECTION_OPT
     115%token          _USERSECTION_OPT
    118116%type<tokenp>   ccode_opt
    119117%type<tokenp>   blocks
    … …  
    236234                    $$ = $1;
    237235                }
    238         | DEFINE                                                                                        // bison
    239         | LOCATIONS
    240236        | THONG                                                                                         // bison
    241237        ;

  • tools/prettyprinter/test.y

    r2ae16219 rb2da0574  
    66
    77/* adsad2 */
    8 %locations
    9 %define parse.error verbose
     8
    109%%
    1110
Note: See TracChangeset for help on using the changeset viewer.