Changes in / [a9b1b0c:b5563e1]


Ignore:
Files:
1 added
11 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/concurrency/Makefile

    ra9b1b0c rb5563e1  
    44Figures = figures
    55Macros = AMA/AMA-stix/ama
    6 TeXLIB = .:style:annex:../../LaTeXmacros:${Macros}:${Build}:../../bibliography:
     6TeXLIB = .:annex:../../LaTeXmacros:${Macros}:${Build}:../../bibliography:
    77LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${Build}
    88BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
  • doc/papers/concurrency/Paper.tex

    ra9b1b0c rb5563e1  
    1 % inline code ©...© (copyright symbol) emacs: C-q M-)
    2 % red highlighting ®...® (registered trademark symbol) emacs: C-q M-.
    3 % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_
    4 % green highlighting ¢...¢ (cent symbol) emacs: C-q M-"
    5 % LaTex escape §...§ (section symbol) emacs: C-q M-'
    6 % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^
    7 % math escape $...$ (dollar symbol)
    8 
    91\documentclass[AMA,STIX1COL]{WileyNJD-v2}
    102
     
    2012
    2113% Latex packages used in the document.
    22 
    23 \usepackage[T1]{fontenc}                                        % allow Latin1 (extended ASCII) characters
    24 \usepackage{textcomp}
    25 \usepackage[latin1]{inputenc}
    26 
    2714\usepackage{epic,eepic}
    2815\usepackage{xspace}
     
    3421\usepackage{siunitx}
    3522\sisetup{ binary-units=true }
    36 \input{style}                                                           % bespoke macros used in the document
     23%\input{style}                                                          % bespoke macros used in the document
    3724
    3825\hypersetup{breaklinks=true}
     
    5138% Names used in the document.
    5239
    53 \newcommand{\CS}{C\raisebox{-0.9ex}{\large$^\sharp$}\xspace}
     40\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\xspace} % Cforall symbolic name
     41\newcommand{\CFA}{\protect\CFAIcon}             % safe for section/caption
     42\newcommand{\CFL}{\textrm{Cforall}\xspace}      % Cforall symbolic name
     43\newcommand{\Celeven}{\textrm{C11}\xspace}      % C11 symbolic name
     44\newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}\xspace} % C++ symbolic name
     45\newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name
     46\newcommand{\CCfourteen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}14\xspace} % C++14 symbolic name
     47\newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17\xspace} % C++17 symbolic name
     48\newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
     49\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
     50
     51%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    5452
    5553\newcommand{\Textbf}[2][red]{{\color{#1}{\textbf{#2}}}}
     
    6260\newcommand{\TODO}{{\Textbf{TODO}}}
    6361
    64 
    65 \newsavebox{\LstBox}
    66 
    6762%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
     63
     64% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     65% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
     66% AFTER HYPERREF.
     67%\DeclareTextCommandDefault{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.1ex}}}
     68\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
     69
     70\makeatletter
     71% parindent is relative, i.e., toggled on/off in environments like itemize, so store the value for
     72% use rather than use \parident directly.
     73\newlength{\parindentlnth}
     74\setlength{\parindentlnth}{\parindent}
     75
     76\newcommand{\LstBasicStyle}[1]{{\lst@basicstyle{\lst@basicstyle{#1}}}}
     77\newcommand{\LstKeywordStyle}[1]{{\lst@basicstyle{\lst@keywordstyle{#1}}}}
     78\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
     79
     80\newlength{\gcolumnposn}                                        % temporary hack because lstlisting does not handle tabs correctly
     81\newlength{\columnposn}
     82\setlength{\gcolumnposn}{3.5in}
     83\setlength{\columnposn}{\gcolumnposn}
     84\newcommand{\C}[2][\@empty]{\ifx#1\@empty\else\global\setlength{\columnposn}{#1}\global\columnposn=\columnposn\fi\hfill\makebox[\textwidth-\columnposn][l]{\lst@basicstyle{\LstCommentStyle{#2}}}}
     85\newcommand{\CRT}{\global\columnposn=\gcolumnposn}
     86
     87% Denote newterms in particular font and index them without particular font and in lowercase, e.g., \newterm{abc}.
     88% The option parameter provides an index term different from the new term, e.g., \newterm[\texttt{abc}]{abc}
     89% The star version does not lowercase the index information, e.g., \newterm*{IBM}.
     90\newcommand{\newtermFontInline}{\emph}
     91\newcommand{\newterm}{\@ifstar\@snewterm\@newterm}
     92\newcommand{\@newterm}[2][\@empty]{\lowercase{\def\temp{#2}}{\newtermFontInline{#2}}\ifx#1\@empty\index{\temp}\else\index{#1@{\protect#2}}\fi}
     93\newcommand{\@snewterm}[2][\@empty]{{\newtermFontInline{#2}}\ifx#1\@empty\index{#2}\else\index{#1@{\protect#2}}\fi}
     94
     95% Latin abbreviation
     96\newcommand{\abbrevFont}{\textit}                       % set empty for no italics
     97\newcommand{\EG}{\abbrevFont{e}.\abbrevFont{g}.}
     98\newcommand*{\eg}{%
     99        \@ifnextchar{,}{\EG}%
     100                {\@ifnextchar{:}{\EG}%
     101                        {\EG,\xspace}}%
     102}%
     103\newcommand{\IE}{\abbrevFont{i}.\abbrevFont{e}.}
     104\newcommand*{\ie}{%
     105        \@ifnextchar{,}{\IE}%
     106                {\@ifnextchar{:}{\IE}%
     107                        {\IE,\xspace}}%
     108}%
     109\newcommand{\ETC}{\abbrevFont{etc}}
     110\newcommand*{\etc}{%
     111        \@ifnextchar{.}{\ETC}%
     112        {\ETC.\xspace}%
     113}%
     114\newcommand{\ETAL}{\abbrevFont{et}~\abbrevFont{al}}
     115\renewcommand*{\etal}{%
     116        \@ifnextchar{.}{\protect\ETAL}%
     117                {\protect\ETAL.\xspace}%
     118}%
     119\newcommand{\VIZ}{\abbrevFont{viz}}
     120\newcommand*{\viz}{%
     121        \@ifnextchar{.}{\VIZ}%
     122                {\VIZ.\xspace}%
     123}%
     124\makeatother
     125
     126\newenvironment{cquote}{%
     127        \list{}{\lstset{resetmargins=true,aboveskip=0pt,belowskip=0pt}\topsep=3pt\parsep=0pt\leftmargin=\parindentlnth\rightmargin\leftmargin}%
     128        \item\relax
     129}{%
     130        \endlist
     131}% cquote
     132
     133% CFA programming language, based on ANSI C (with some gcc additions)
     134\lstdefinelanguage{CFA}[ANSI]{C}{
     135        morekeywords={
     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},
     145        moredirectives={defined,include_next}%
     146}
     147
     148\lstset{
     149language=CFA,
     150columns=fullflexible,
     151basicstyle=\linespread{0.9}\sf,                                                 % reduce line spacing and use sanserif font
     152stringstyle=\tt,                                                                                % use typewriter font
     153tabsize=5,                                                                                              % N space tabbing
     154xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
     155%mathescape=true,                                                                               % LaTeX math escape in CFA code $...$
     156escapechar=\$,                                                                                  % LaTeX escape in CFA code
     157keepspaces=true,                                                                                %
     158showstringspaces=false,                                                                 % do not show spaces with cup
     159showlines=true,                                                                                 % show blank lines at end of code
     160aboveskip=4pt,                                                                                  % spacing above/below code block
     161belowskip=3pt,
     162% replace/adjust listing characters that look bad in sanserif
     163literate={-}{\makebox[1ex][c]{\raisebox{0.4ex}{\rule{0.8ex}{0.1ex}}}}1 {^}{\raisebox{0.6ex}{$\scriptstyle\land\,$}}1
     164        {~}{\raisebox{0.3ex}{$\scriptstyle\sim\,$}}1 % {`}{\ttfamily\upshape\hspace*{-0.1ex}`}1
     165        {<-}{$\leftarrow$}2 {=>}{$\Rightarrow$}2 {->}{\makebox[1ex][c]{\raisebox{0.5ex}{\rule{0.8ex}{0.075ex}}}\kern-0.2ex{\textgreater}}2,
     166moredelim=**[is][\color{red}]{`}{`},
     167}% lstset
     168
     169% uC++ programming language, based on ANSI C++
     170\lstdefinelanguage{uC++}[ANSI]{C++}{
     171        morekeywords={
     172                _Accept, _AcceptReturn, _AcceptWait, _Actor, _At, _CatchResume, _Cormonitor, _Coroutine, _Disable,
     173                _Else, _Enable, _Event, _Finally, _Monitor, _Mutex, _Nomutex, _PeriodicTask, _RealTimeTask,
     174                _Resume, _Select, _SporadicTask, _Task, _Timeout, _When, _With, _Throw},
     175}
     176\lstdefinelanguage{Golang}{
     177        morekeywords=[1]{package,import,func,type,struct,return,defer,panic,recover,select,var,const,iota,},
     178        morekeywords=[2]{string,uint,uint8,uint16,uint32,uint64,int,int8,int16,int32,int64,
     179                bool,float32,float64,complex64,complex128,byte,rune,uintptr, error,interface},
     180        morekeywords=[3]{map,slice,make,new,nil,len,cap,copy,close,true,false,delete,append,real,imag,complex,chan,},
     181        morekeywords=[4]{for,break,continue,range,goto,switch,case,fallthrough,if,else,default,},
     182        morekeywords=[5]{Println,Printf,Error,},
     183        sensitive=true,
     184        morecomment=[l]{//},
     185        morecomment=[s]{/*}{*/},
     186        morestring=[b]',
     187        morestring=[b]",
     188        morestring=[s]{`}{`},
     189}
     190
     191\lstnewenvironment{cfa}[1][]
     192{\lstset{#1}}
     193{}
     194\lstnewenvironment{C++}[1][]                            % use C++ style
     195{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{`}{`},#1}\lstset{#1}}
     196{}
     197\lstnewenvironment{uC++}[1][]
     198{\lstset{#1}}
     199{}
     200\lstnewenvironment{Go}[1][]
     201{\lstset{#1}}
     202{}
     203
     204% inline code @...@
     205\lstMakeShortInline@%
     206
    68207
    69208\title{\texorpdfstring{Concurrency in \protect\CFA}{Concurrency in Cforall}}
     
    81220\abstract[Summary]{
    82221\CFA is a modern, polymorphic, \emph{non-object-oriented} extension of the C programming language.
    83 This paper discusses the design of the concurrency and parallelism features in \CFA, and the concurrent runtime-system that supports them.
     222This paper discusses the design of the concurrency and parallelism features in \CFA, and the concurrent runtime-system.
    84223These features are created from scratch as ISO C lacks concurrency, relying largely on pthreads.
    85224Coroutines and lightweight (user) threads are introduced into the language.
     
    87226A unique contribution is allowing multiple monitors to be safely acquired simultaneously.
    88227All features respect the expectations of C programmers, while being fully integrate with the \CFA polymorphic type-system and other language features.
    89 Finally, experimental results are presented to validate several of the new features with other concurrent programming-languages.
     228Finally, experimental results are presented to compare the performance of the new features with similar mechanisms in other concurrent programming-languages.
    90229}%
    91230
     
    104243% ======================================================================
    105244
    106 This paper provides a minimal concurrency \textbf{api} that is simple, efficient and can be reused to build higher-level features.
    107 The simplest possible concurrency system is a thread and a lock but this low-level approach is hard to master.
    108 An easier approach for users is to support higher-level constructs as the basis of concurrency.
    109 Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{HPP:Study}.
    110 Examples are task based, message passing and implicit threading.
    111 The high-level approach and its minimal \textbf{api} are tested in a dialect of C, called \CFA.
    112 Furthermore, the proposed \textbf{api} doubles as an early definition of the \CFA language and library.
    113 This paper also provides an implementation of the concurrency library for \CFA as well as all the required language features added to the source-to-source translator.
    114 
    115 There are actually two problems that need to be solved in the design of concurrency for a programming language: which concurrency and which parallelism tools are available to the programmer.
     245This paper provides a minimal concurrency \newterm{API} that is simple, efficient and can be used to build other concurrency features.
     246While the simplest concurrency system is a thread and a lock, this low-level approach is hard to master.
     247An easier approach for programmers is to support higher-level constructs as the basis of concurrency.
     248Indeed, for highly productive concurrent programming, high-level approaches are much more popular~\cite{Hochstein05}.
     249Examples of high-level approaches are task based~\cite{TBB}, message passing~\cite{Erlang,MPI}, and implicit threading~\cite{OpenMP}.
     250
     251The terminology used in this paper is as follows.
     252A \newterm{thread} is a fundamental unit of execution that runs a sequence of code and requires a stack to maintain state.
     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.
     255\newterm{Locking}, and by extension locks, are defined as a mechanism to prevent progress of threads to provide safety.
     256\newterm{Parallelism} is running multiple threads simultaneously.
     257Parallelism implies \emph{actual} simultaneous execution, where concurrency only requires \emph{apparent} simultaneous execution.
     258As such, parallelism is only observable in differences in performance, which is observed through differences in timing.
     259
     260Hence, there are two problems to be solved in the design of concurrency for a programming language: concurrency and parallelism.
    116261While these two concepts are often combined, they are in fact distinct, requiring different tools~\cite{Buhr05a}.
    117 Concurrency tools need to handle mutual exclusion and synchronization, while parallelism tools are about performance, cost and resource utilization.
    118 
    119 In the context of this paper, a \textbf{thread} is a fundamental unit of execution that runs a sequence of code, generally on a program stack.
    120 Having multiple simultaneous threads gives rise to concurrency and generally requires some kind of locking mechanism to ensure proper execution.
    121 Correspondingly, \textbf{concurrency} is defined as the concepts and challenges that occur when multiple independent (sharing memory, timing dependencies, etc.) concurrent threads are introduced.
    122 Accordingly, \textbf{locking} (and by extension locks) are defined as a mechanism that prevents the progress of certain threads in order to avoid problems due to concurrency.
    123 Finally, in this paper \textbf{parallelism} is distinct from concurrency and is defined as running multiple threads simultaneously.
    124 More precisely, parallelism implies \emph{actual} simultaneous execution as opposed to concurrency which only requires \emph{apparent} simultaneous execution.
    125 As such, parallelism is only observable in the differences in performance or, more generally, differences in timing.
     262Concurrency tools handle mutual exclusion and synchronization, while parallelism tools handle performance, cost and resource utilization.
     263
     264The proposed concurrency API is implemented in a dialect of C, called \CFA.
     265The paper discusses how the language features are added to the \CFA translator with respect to parsing, semantic, and type checking, and the corresponding high-perforamnce runtime-library to implement the concurrency features.
    126266
    127267% ======================================================================
     
    139279Interestingly, 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
    140280values''~\cite[3.15]{C11}}, most importantly construction and destruction of objects.
    141 Most of the following code examples can be found on the \CFA website~\cite{www-cfa}.
    142 
    143 % ======================================================================
     281Most of the following code examples can be found on the \CFA website~\cite{Cforall}.
     282
     283
    144284\subsection{References}
    145285
    146286Like \CC, \CFA introduces rebind-able references providing multiple dereferencing as an alternative to pointers.
    147287In regards to concurrency, the semantic difference between pointers and references are not particularly relevant, but since this document uses mostly references, here is a quick overview of the semantics:
    148 \begin{cfacode}
     288\begin{cfa}
    149289int x, *p1 = &x, **p2 = &p1, ***p3 = &p2,
    150290        &r1 = x,    &&r2 = r1,   &&&r3 = r2;
    151 ***p3 = 3;                                                      //change x
    152 r3    = 3;                                                      //change x, ***r3
    153 **p3  = ...;                                            //change p1
    154 *p3   = ...;                                            //change p2
    155 int y, z, & ar[3] = {x, y, z};          //initialize array of references
    156 typeof( ar[1]) p;                                       //is int, referenced object type
    157 typeof(&ar[1]) q;                                       //is int &, reference type
    158 sizeof( ar[1]) == sizeof(int);          //is true, referenced object size
    159 sizeof(&ar[1]) == sizeof(int *);        //is true, reference size
    160 \end{cfacode}
     291***p3 = 3;                                                      $\C{// change x}$
     292r3    = 3;                                                      $\C{// change x, ***r3}$
     293**p3  = ...;                                            $\C{// change p1}$
     294*p3   = ...;                                            $\C{// change p2}$
     295int y, z, & ar[3] = {x, y, z};          $\C{// initialize array of references}$
     296typeof( ar[1]) p;                                       $\C{// is int, referenced object type}$
     297typeof(&ar[1]) q;                                       $\C{// is int \&, reference type}$
     298sizeof( ar[1]) == sizeof(int);          $\C{// is true, referenced object size}$
     299sizeof(&ar[1]) == sizeof(int *);        $\C{// is true, reference size}$
     300\end{cfa}
    161301The important take away from this code example is that a reference offers a handle to an object, much like a pointer, but which is automatically dereferenced for convenience.
    162302
     
    167307As well, \CFA uses the return type as part of the selection criteria, as in Ada~\cite{Ada}.
    168308For routines with multiple parameters and returns, the selection is complex.
    169 \begin{cfacode}
    170 //selection based on type and number of parameters
    171 void f(void);                   //(1)
    172 void f(char);                   //(2)
    173 void f(int, double);    //(3)
    174 f();                                    //select (1)
    175 f('a');                                 //select (2)
    176 f(3, 5.2);                              //select (3)
    177 
    178 //selection based on  type and number of returns
    179 char   f(int);                  //(1)
    180 double f(int);                  //(2)
    181 char   c = f(3);                //select (1)
    182 double d = f(4);                //select (2)
    183 \end{cfacode}
     309\begin{cfa}
     310// selection based on type and number of parameters
     311void f(void);                   $\C{// (1)}$
     312void f(char);                   $\C{// (2)}$
     313void f(int, double);    $\C{// (3)}$
     314f();                                    $\C{// select (1)}$
     315f('a');                                 $\C{// select (2)}$
     316f(3, 5.2);                              $\C{// select (3)}$
     317
     318// selection based on  type and number of returns
     319char   f(int);                  $\C{// (1)}$
     320double f(int);                  $\C{// (2)}$
     321char   c = f(3);                $\C{// select (1)}$
     322double d = f(4);                $\C{// select (2)}$
     323\end{cfa}
    184324This feature is particularly important for concurrency since the runtime system relies on creating different types to represent concurrency objects.
    185325Therefore, overloading is necessary to prevent the need for long prefixes and other naming conventions that prevent name clashes.
    186 As seen in section \ref{basics}, routine \code{main} is an example that benefits from overloading.
     326As seen in section \ref{basics}, routine @main@ is an example that benefits from overloading.
    187327
    188328% ======================================================================
     
    190330Overloading also extends to operators.
    191331The 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.:
    192 \begin{cfacode}
    193 int ++? (int op);                       //unary prefix increment
    194 int ?++ (int op);                       //unary postfix increment
    195 int ?+? (int op1, int op2);             //binary plus
    196 int ?<=?(int op1, int op2);             //binary less than
    197 int ?=? (int & op1, int op2);           //binary assignment
    198 int ?+=?(int & op1, int op2);           //binary plus-assignment
     332\begin{cfa}
     333int ++? (int op);                       $\C{// unary prefix increment}$
     334int ?++ (int op);                       $\C{// unary postfix increment}$
     335int ?+? (int op1, int op2);             $\C{// binary plus}$
     336int ?<=?(int op1, int op2);             $\C{// binary less than}$
     337int ?=? (int & op1, int op2);           $\C{// binary assignment}$
     338int ?+=?(int & op1, int op2);           $\C{// binary plus-assignment}$
    199339
    200340struct S {int i, j;};
    201 S ?+?(S op1, S op2) {                           //add two structures
     341S ?+?(S op1, S op2) {                           $\C{// add two structures}$
    202342        return (S){op1.i + op2.i, op1.j + op2.j};
    203343}
    204344S s1 = {1, 2}, s2 = {2, 3}, s3;
    205 s3 = s1 + s2;                                           //compute sum: s3 == {2, 5}
    206 \end{cfacode}
     345s3 = s1 + s2;                                           $\C{// compute sum: s3 == {2, 5}}$
     346\end{cfa}
    207347While concurrency does not use operator overloading directly, this feature is more important as an introduction for the syntax of constructors.
    208348
     
    211351Object lifetime is often a challenge in concurrency. \CFA uses the approach of giving concurrent meaning to object lifetime as a means of synchronization and/or mutual exclusion.
    212352Since \CFA relies heavily on the lifetime of objects, constructors and destructors is a core feature required for concurrency and parallelism. \CFA uses the following syntax for constructors and destructors:
    213 \begin{cfacode}
     353\begin{cfa}
    214354struct S {
    215355        size_t size;
    216356        int * ia;
    217357};
    218 void ?{}(S & s, int asize) {    //constructor operator
    219         s.size = asize;                         //initialize fields
     358void ?{}(S & s, int asize) {    $\C{// constructor operator}$
     359        s.size = asize;                         $\C{// initialize fields}$
    220360        s.ia = calloc(size, sizeof(S));
    221361}
    222 void ^?{}(S & s) {                              //destructor operator
    223         free(ia);                                       //de-initialization fields
     362void ^?{}(S & s) {                              $\C{// destructor operator}$
     363        free(ia);                                       $\C{// de-initialization fields}$
    224364}
    225365int main() {
    226         S x = {10}, y = {100};          //implicit calls: ?{}(x, 10), ?{}(y, 100)
    227         ...                                                     //use x and y
    228         ^x{};  ^y{};                            //explicit calls to de-initialize
    229         x{20};  y{200};                         //explicit calls to reinitialize
    230         ...                                                     //reuse x and y
    231 }                                                               //implicit calls: ^?{}(y), ^?{}(x)
    232 \end{cfacode}
     366        S x = {10}, y = {100};          $\C{// implicit calls: ?\{\}(x, 10), ?\{\}(y, 100)}$
     367        ...                                                     $\C{// use x and y}$
     368        ^x{};  ^y{};                            $\C{// explicit calls to de-initialize}$
     369        x{20};  y{200};                         $\C{// explicit calls to reinitialize}$
     370        ...                                                     $\C{// reuse x and y}$
     371}                                                               $\C{// implicit calls: \^?\{\}(y), \^?\{\}(x)}$
     372\end{cfa}
    233373The language guarantees that every object and all their fields are constructed.
    234374Like \CC, construction of an object is automatically done on allocation and destruction of the object is done on deallocation.
    235375Allocation and deallocation can occur on the stack or on the heap.
    236 \begin{cfacode}
     376\begin{cfa}
    237377{
    238         struct S s = {10};      //allocation, call constructor
     378        struct S s = {10};      $\C{// allocation, call constructor}$
    239379        ...
    240 }                                               //deallocation, call destructor
    241 struct S * s = new();   //allocation, call constructor
     380}                                               $\C{// deallocation, call destructor}$
     381struct S * s = new();   $\C{// allocation, call constructor}$
    242382...
    243 delete(s);                              //deallocation, call destructor
    244 \end{cfacode}
    245 Note that like \CC, \CFA introduces \code{new} and \code{delete}, which behave like \code{malloc} and \code{free} in addition to constructing and destructing objects, after calling \code{malloc} and before calling \code{free}, respectively.
     383delete(s);                              $\C{// deallocation, call destructor}$
     384\end{cfa}
     385Note that like \CC, \CFA introduces @new@ and @delete@, which behave like @malloc@ and @free@ in addition to constructing and destructing objects, after calling @malloc@ and before calling @free@, respectively.
    246386
    247387% ======================================================================
     
    249389\label{s:ParametricPolymorphism}
    250390Routines in \CFA can also be reused for multiple types.
    251 This capability is done using the \code{forall} clauses, which allow separately compiled routines to support generic usage over multiple types.
     391This capability is done using the @forall@ clauses, which allow separately compiled routines to support generic usage over multiple types.
    252392For example, the following sum function works for any type that supports construction from 0 and addition:
    253 \begin{cfacode}
    254 //constraint type, 0 and +
     393\begin{cfa}
     394// constraint type, 0 and +
    255395forall(otype T | { void ?{}(T *, zero_t); T ?+?(T, T); })
    256396T sum(T a[ ], size_t size) {
    257         T total = 0;                            //construct T from 0
     397        T total = 0;                            $\C{// construct T from 0}$
    258398        for(size_t i = 0; i < size; i++)
    259                 total = total + a[i];   //select appropriate +
     399                total = total + a[i];   $\C{// select appropriate +}$
    260400        return total;
    261401}
    262402
    263403S sa[5];
    264 int i = sum(sa, 5);                             //use S's 0 construction and +
    265 \end{cfacode}
     404int i = sum(sa, 5);                             $\C{// use S's 0 construction and +}$
     405\end{cfa}
    266406
    267407Since writing constraints on types can become cumbersome for more constrained functions, \CFA also has the concept of traits.
    268408Traits are named collection of constraints that can be used both instead and in addition to regular constraints:
    269 \begin{cfacode}
     409\begin{cfa}
    270410trait summable( otype T ) {
    271         void ?{}(T *, zero_t);          //constructor from 0 literal
    272         T ?+?(T, T);                            //assortment of additions
     411        void ?{}(T *, zero_t);          $\C{// constructor from 0 literal}$
     412        T ?+?(T, T);                            $\C{// assortment of additions}$
    273413        T ?+=?(T *, T);
    274414        T ++?(T *);
    275415        T ?++(T *);
    276416};
    277 forall( otype T | summable(T) ) //use trait
     417forall( otype T | summable(T) ) $\C{// use trait}$
    278418T sum(T a[], size_t size);
    279 \end{cfacode}
    280 
    281 Note that the type use for assertions can be either an \code{otype} or a \code{dtype}.
    282 Types declared as \code{otype} refer to ``complete'' objects, i.e., objects with a size, a default constructor, a copy constructor, a destructor and an assignment operator.
    283 Using \code{dtype,} on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.
     419\end{cfa}
     420
     421Note that the type use for assertions can be either an @otype@ or a @dtype@.
     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.
     423Using @dtype@, on the other hand, has none of these assumptions but is extremely restrictive, it only guarantees the object is addressable.
    284424
    285425% ======================================================================
    286426\subsection{with Clause/Statement}
    287427Since \CFA lacks the concept of a receiver, certain functions end up needing to repeat variable names often.
    288 To remove this inconvenience, \CFA provides the \code{with} statement, which opens an aggregate scope making its fields directly accessible (like Pascal).
    289 \begin{cfacode}
     428To remove this inconvenience, \CFA provides the @with@ statement, which opens an aggregate scope making its fields directly accessible (like Pascal).
     429\begin{cfa}
    290430struct S { int i, j; };
    291 int mem(S & this) with (this)           //with clause
    292         i = 1;                                                  //this->i
    293         j = 2;                                                  //this->j
     431int mem(S & this) with (this)           $\C{// with clause}$
     432        i = 1;                                                  $\C{// this->i}$
     433        j = 2;                                                  $\C{// this->j}$
    294434}
    295435int foo() {
    296436        struct S1 { ... } s1;
    297437        struct S2 { ... } s2;
    298         with (s1)                                               //with statement
     438        with (s1)                                               $\C{// with statement}$
    299439        {
    300                 //access fields of s1 without qualification
    301                 with (s2)                                       //nesting
     440                // access fields of s1 without qualification
     441                with (s2)                                       $\C{// nesting}$
    302442                {
    303                         //access fields of s1 and s2 without qualification
     443                        // access fields of s1 and s2 without qualification
    304444                }
    305445        }
    306         with (s1, s2)                                   //scopes open in parallel
     446        with (s1, s2)                                   $\C{// scopes open in parallel}$
    307447        {
    308                 //access fields of s1 and s2 without qualification
    309         }
    310 }
    311 \end{cfacode}
    312 
    313 For more information on \CFA see \cite{cforall-ug,rob-thesis,www-cfa}.
     448                // access fields of s1 and s2 without qualification
     449        }
     450}
     451\end{cfa}
     452
     453For more information on \CFA see \cite{cforall-ug,Schluntz17,www-cfa}.
    314454
    315455% ======================================================================
     
    339479Optimal performance in concurrent applications is often obtained by having as much non-determinism as correctness allows.
    340480
     481
    341482\section{\protect\CFA's Thread Building Blocks}
     483
    342484One 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.
    343485As such, library support for threading is far from widespread.
    344 At the time of writing the paper, neither \texttt{gcc} nor \texttt{clang} support ``threads.h'' in their respective standard libraries.}.
     486At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}.
    345487On modern architectures, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore modern programming languages must have the proper tools to allow users to write efficient concurrent programs to take advantage of parallelism.
    346488As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages.
    347489And being a system-level language means programmers expect to choose precisely which features they need and which cost they are willing to pay.
    348490
     491
    349492\section{Coroutines: A Stepping Stone}\label{coroutine}
     493
    350494While 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.
    351495Therefore, they need to deal with context switches and other context-management operations.
    352496This proposal includes coroutines both as an intermediate step for the implementation of threads, and a first-class feature of \CFA.
    353497Furthermore, many design challenges of threads are at least partially present in designing coroutines, which makes the design effort that much more relevant.
    354 The core \textbf{api} of coroutines revolves around two features: independent call-stacks and \code{suspend}/\code{resume}.
    355 
    356 \begin{table}
     498The core \textbf{api} of coroutines revolves around two features: independent call-stacks and @suspend@/@resume@.
     499
     500\begin{figure}
    357501\begin{center}
    358 \begin{tabular}{c @{\hskip 0.025in}|@{\hskip 0.025in} c @{\hskip 0.025in}|@{\hskip 0.025in} c}
    359 \begin{ccode}[tabsize=2]
    360 //Using callbacks
    361 void fibonacci_func(
    362         int n,
    363         void (*callback)(int)
     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 )
    364507) {
    365         int first = 0;
    366         int second = 1;
    367         int next, i;
    368         for(i = 0; i < n; i++)
    369         {
    370                 if(i <= 1)
    371                         next = i;
    372                 else {
    373                         next = f1 + f2;
    374                         f1 = f2;
    375                         f2 = next;
    376                 }
    377                 callback(next);
    378         }
    379 }
    380 
     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        }
     514}
    381515int main() {
    382         void print_fib(int n) {
    383                 printf("%d\n", n);
    384         }
    385 
    386         fibonacci_func(
    387                 10, print_fib
    388         );
    389 
    390 
    391 
    392 }
    393 \end{ccode}&\begin{ccode}[tabsize=2]
    394 //Using output array
    395 void fibonacci_array(
    396         int n,
    397         int* array
     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
    398527) {
    399         int f1 = 0; int f2 = 1;
    400         int next, i;
    401         for(i = 0; i < n; i++)
    402         {
    403                 if(i <= 1)
    404                         next = i;
    405                 else {
    406                         next = f1 + f2;
    407                         f1 = f2;
    408                         f2 = next;
    409                 }
    410                 array[i] = next;
    411         }
    412 }
    413 
    414 
     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}
    415535int main() {
    416536        int a[10];
    417 
    418         fibonacci_func(
    419                 10, a
    420         );
    421 
    422         for(int i=0;i<10;i++){
    423                 printf("%d\n", a[i]);
    424         }
    425 
    426 }
    427 \end{ccode}&\begin{ccode}[tabsize=2]
    428 //Using external state
    429 typedef struct {
    430         int f1, f2;
    431 } Iterator_t;
    432 
    433 int fibonacci_state(
    434         Iterator_t* it
     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
    435549) {
    436         int f;
    437         f = it->f1 + it->f2;
    438         it->f2 = it->f1;
    439         it->f1 = max(f,1);
    440         return f;
    441 }
    442 
    443 
    444 
    445 
    446 
    447 
    448 
     550        int ret = fib->f1;
     551        int fn = fib->f1 + fib->f2;
     552        fib->f2 = fib->f1; fib->f1 = fn;
     553        return ret;
     554}
    449555int main() {
    450         Iterator_t it={0,0};
    451 
    452         for(int i=0;i<10;i++){
    453                 printf("%d\n",
    454                         fibonacci_state(
    455                                 &it
    456                         );
    457                 );
    458         }
    459 
    460 }
    461 \end{ccode}
     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}
    462563\end{tabular}
    463564\end{center}
    464 \caption{Different implementations of a Fibonacci sequence generator in C.}
    465 \label{lst:fibonacci-c}
    466 \end{table}
     565\caption{Fibonacci Implementations in C}
     566\label{lst:fib-c}
     567\end{figure}
    467568
    468569A good example of a problem made easier with coroutines is generators, e.g., generating the Fibonacci sequence.
     
    474575Listing \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.
    475576This solution has the advantage of having very strong decoupling between how the sequence is generated and how it is used.
    476 Indeed, this version is as easy to use as the \code{fibonacci_state} solution, while the implementation is very similar to the \code{fibonacci_func} example.
     577Indeed, this version is as easy to use as the @fibonacci_state@ solution, while the implementation is very similar to the @fibonacci_func@ example.
    477578
    478579\begin{figure}
    479 \begin{cfacode}[caption={Implementation of Fibonacci using coroutines},label={lst:fibonacci-cfa}]
    480 coroutine Fibonacci {
    481         int fn; //used for communication
     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.
     612The 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.
     613
     614\begin{figure}
     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
    482620};
    483621
    484 void ?{}(Fibonacci& this) { //constructor
    485         this.fn = 0;
    486 }
    487 
    488 //main automatically called on first resume
    489 void main(Fibonacci& this) with (this) {
    490         int fn1, fn2;           //retained between resumes
    491         fn  = 0;
    492         fn1 = fn;
    493         suspend(this);          //return to last resume
    494 
    495         fn  = 1;
    496         fn2 = fn1;
    497         fn1 = fn;
    498         suspend(this);          //return to last resume
    499 
    500         for ( ;; ) {
    501                 fn  = fn1 + fn2;
    502                 fn2 = fn1;
    503                 fn1 = fn;
    504                 suspend(this);  //return to last resume
    505         }
    506 }
    507 
    508 int next(Fibonacci& this) {
    509         resume(this); //transfer to last suspend
    510         return this.fn;
    511 }
    512 
    513 void main() { //regular program main
    514         Fibonacci f1, f2;
    515         for ( int i = 1; i <= 10; i += 1 ) {
    516                 sout | next( f1 ) | next( f2 ) | endl;
    517         }
    518 }
    519 \end{cfacode}
    520 \end{figure}
    521 
    522 Listing \ref{lst:fmt-line} shows the \code{Format} coroutine for restructuring text into groups of character blocks of fixed size.
    523 The 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.
    524 
    525 \begin{figure}
    526 \begin{cfacode}[tabsize=3,caption={Formatting text into lines of 5 blocks of 4 characters.},label={lst:fmt-line}]
    527 //format characters into blocks of 4 and groups of 5 blocks per line
    528 coroutine Format {
    529         char ch;                                                                        //used for communication
    530         int g, b;                                                               //global because used in destructor
    531 };
    532 
    533622void  ?{}(Format& fmt) {
    534         resume( fmt );                                                  //prime (start) coroutine
     623        resume( fmt );                                                  // prime (start) coroutine
    535624}
    536625
     
    541630
    542631void main(Format& fmt) with fmt {
    543         for ( ;; ) {                                                    //for as many characters
    544                 for(g = 0; g < 5; g++) {                //groups of 5 blocks
    545                         for(b = 0; b < 4; fb++) {       //blocks of 4 characters
     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
    546635                                suspend();
    547                                 sout | ch;                                      //print character
     636                                sout | ch;                                      // print character
    548637                        }
    549                         sout | "  ";                                    //print block separator
     638                        sout | "  ";                                    // print block separator
    550639                }
    551                 sout | endl;                                            //print group separator
     640                sout | endl;                                            // print group separator
    552641        }
    553642}
     
    561650        Format fmt;
    562651        char ch;
    563         Eof: for ( ;; ) {                                               //read until end of file
    564                 sin | ch;                                                       //read one character
    565                 if(eof(sin)) break Eof;                 //eof ?
    566                 prt(fmt, ch);                                           //push character for formatting
    567         }
    568 }
    569 \end{cfacode}
     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}
    570659\end{figure}
    571660
     
    582671For example, the following code, while looking benign, can run into undefined behaviour because of thunks:
    583672
    584 \begin{cfacode}
    585 //async: Runs function asynchronously on another thread
     673\begin{cfa}
     674// async: Runs function asynchronously on another thread
    586675forall(otype T)
    587676extern void async(void (*func)(T*), T* obj);
     
    592681void bar() {
    593682        int a;
    594         async(noop, &a); //start thread running noop with argument a
    595 }
    596 \end{cfacode}
     683        async(noop, &a); // start thread running noop with argument a
     684}
     685\end{cfa}
    597686
    598687The generated C code\footnote{Code trimmed down for brevity} creates a local thunk to hold type information:
    599688
    600 \begin{ccode}
     689\begin{cfa}
    601690extern void async(/* omitted */, void (*func)(void*), void* obj);
    602691
     
    612701        async(/* omitted */, ((void (*)(void*))(&_thunk0)), (&a));
    613702}
    614 \end{ccode}
    615 The problem in this example is a storage management issue, the function pointer \code{_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.
     703\end{cfa}
     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.
    616705This challenge is an extension of challenges that come with second-class routines.
    617706Indeed, GCC nested routines also have the limitation that nested routine cannot be passed outside of the declaration scope.
     
    621710One solution to this challenge is to use composition/containment, where coroutine fields are added to manage the coroutine.
    622711
    623 \begin{cfacode}
     712\begin{cfa}
    624713struct Fibonacci {
    625         int fn; //used for communication
    626         coroutine c; //composition
     714        int fn; // used for communication
     715        coroutine c; // composition
    627716};
    628717
     
    633722void ?{}(Fibonacci& this) {
    634723        this.fn = 0;
    635         //Call constructor to initialize coroutine
     724        // Call constructor to initialize coroutine
    636725        (this.c){myMain};
    637726}
    638 \end{cfacode}
     727\end{cfa}
    639728The downside of this approach is that users need to correctly construct the coroutine handle before using it.
    640729Like any other objects, the user must carefully choose construction order to prevent usage of objects not yet constructed.
     
    645734The next alternative is to use language support to annotate coroutines as follows:
    646735
    647 \begin{cfacode}
     736\begin{cfa}
    648737coroutine Fibonacci {
    649         int fn; //used for communication
     738        int fn; // used for communication
    650739};
    651 \end{cfacode}
    652 The \code{coroutine} keyword means the compiler can find and inject code where needed.
     740\end{cfa}
     741The @coroutine@ keyword means the compiler can find and inject code where needed.
    653742The downside of this approach is that it makes coroutine a special case in the language.
    654743Users wanting to extend coroutines or build their own for various reasons can only do so in ways offered by the language.
     
    661750For coroutines as for threads, many implementations are based on routine pointers or function objects~\cite{Butenhof97, C++14, MS:VisualC++, BoostCoroutines15}.
    662751For example, Boost implements coroutines in terms of four functor object types:
    663 \begin{cfacode}
     752\begin{cfa}
    664753asymmetric_coroutine<>::pull_type
    665754asymmetric_coroutine<>::push_type
    666755symmetric_coroutine<>::call_type
    667756symmetric_coroutine<>::yield_type
    668 \end{cfacode}
    669 Often, the canonical threading paradigm in languages is based on function pointers, \texttt{pthread} being one of the most well-known examples.
     757\end{cfa}
     758Often, the canonical threading paradigm in languages is based on function pointers, @pthread@ being one of the most well-known examples.
    670759The main problem of this approach is that the thread usage is limited to a generic handle that must otherwise be wrapped in a custom type.
    671760Since the custom type is simple to write in \CFA and solves several issues, added support for routine/lambda based coroutines adds very little.
    672761
    673 A variation of this would be to use a simple function pointer in the same way \texttt{pthread} does for threads:
    674 \begin{cfacode}
     762A variation of this would be to use a simple function pointer in the same way @pthread@ does for threads:
     763\begin{cfa}
    675764void foo( coroutine_t cid, void* arg ) {
    676765        int* value = (int*)arg;
    677         //Coroutine body
     766        // Coroutine body
    678767}
    679768
     
    683772        coroutine_resume( &cid );
    684773}
    685 \end{cfacode}
     774\end{cfa}
    686775This semantics is more common for thread interfaces but coroutines work equally well.
    687776As discussed in section \ref{threads}, this approach is superseded by static approaches in terms of expressivity.
     
    690779
    691780Finally, the underlying approach, which is the one closest to \CFA idioms, is to use trait-based lazy coroutines.
    692 This approach defines a coroutine as anything that satisfies the trait \code{is_coroutine} (as defined below) and is used as a coroutine.
    693 
    694 \begin{cfacode}
     781This approach defines a coroutine as anything that satisfies the trait @is_coroutine@ (as defined below) and is used as a coroutine.
     782
     783\begin{cfa}
    695784trait is_coroutine(dtype T) {
    696785      void main(T& this);
     
    700789forall( dtype T | is_coroutine(T) ) void suspend(T&);
    701790forall( dtype T | is_coroutine(T) ) void resume (T&);
    702 \end{cfacode}
    703 This ensures that an object is not a coroutine until \code{resume} is called on the object.
    704 Correspondingly, any object that is passed to \code{resume} is a coroutine since it must satisfy the \code{is_coroutine} trait to compile.
    705 The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the \code{get_coroutine} routine.
    706 The \CFA keyword \code{coroutine} simply has the effect of implementing the getter and forward declarations required for users to implement the main routine.
     791\end{cfa}
     792This ensures that an object is not a coroutine until @resume@ is called on the object.
     793Correspondingly, any object that is passed to @resume@ is a coroutine since it must satisfy the @is_coroutine@ trait to compile.
     794The advantage of this approach is that users can easily create different types of coroutines, for example, changing the memory layout of a coroutine is trivial when implementing the @get_coroutine@ routine.
     795The \CFA keyword @coroutine@ simply has the effect of implementing the getter and forward declarations required for users to implement the main routine.
    707796
    708797\begin{center}
    709798\begin{tabular}{c c c}
    710 \begin{cfacode}[tabsize=3]
     799\begin{cfa}[tabsize=3]
    711800coroutine MyCoroutine {
    712801        int someValue;
    713802};
    714 \end{cfacode} & == & \begin{cfacode}[tabsize=3]
     803\end{cfa} & == & \begin{cfa}[tabsize=3]
    715804struct MyCoroutine {
    716805        int someValue;
     
    726815
    727816void main(struct MyCoroutine* this);
    728 \end{cfacode}
     817\end{cfa}
    729818\end{tabular}
    730819\end{center}
     
    736825Both user and kernel threads are supported, where user threads are the concurrency mechanism and kernel threads are the parallel mechanism.
    737826User threads offer a flexible and lightweight interface.
    738 A thread can be declared using a struct declaration \code{thread} as follows:
    739 
    740 \begin{cfacode}
     827A thread can be declared using a struct declaration @thread@ as follows:
     828
     829\begin{cfa}
    741830thread foo {};
    742 \end{cfacode}
     831\end{cfa}
    743832
    744833As for coroutines, the keyword is a thin wrapper around a \CFA trait:
    745834
    746 \begin{cfacode}
     835\begin{cfa}
    747836trait is_thread(dtype T) {
    748837      void ^?{}(T & mutex this);
     
    750839      thread_desc* get_thread(T & this);
    751840};
    752 \end{cfacode}
     841\end{cfa}
    753842
    754843Obviously, for this thread implementation to be useful it must run some user code.
    755844Several other threading interfaces use a function-pointer representation as the interface of threads (for example \Csharp~\cite{Csharp} and Scala~\cite{Scala}).
    756 However, this proposal considers that statically tying a \code{main} routine to a thread supersedes this approach.
    757 Since the \code{main} routine is already a special routine in \CFA (where the program begins), it is a natural extension of the semantics to use overloading to declare mains for different threads (the normal main being the main of the initial thread).
    758 As such the \code{main} routine of a thread can be defined as
    759 \begin{cfacode}
     845However, this proposal considers that statically tying a @main@ routine to a thread supersedes this approach.
     846Since the @main@ routine is already a special routine in \CFA (where the program begins), it is a natural extension of the semantics to use overloading to declare mains for different threads (the normal main being the main of the initial thread).
     847As such the @main@ routine of a thread can be defined as
     848\begin{cfa}
    760849thread foo {};
    761850
     
    763852        sout | "Hello World!" | endl;
    764853}
    765 \end{cfacode}
    766 
    767 In this example, threads of type \code{foo} start execution in the \code{void main(foo &)} routine, which prints \code{"Hello World!".} While this paper encourages this approach to enforce strongly typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity.
     854\end{cfa}
     855
     856In this example, threads of type @foo@ start execution in the @void main(foo &)@ routine, which prints @"Hello World!".@ While this paper encourages this approach to enforce strongly typed programming, users may prefer to use the routine-based thread semantics for the sake of simplicity.
    768857With the static semantics it is trivial to write a thread type that takes a function pointer as a parameter and executes it on its stack asynchronously.
    769 \begin{cfacode}
     858\begin{cfa}
    770859typedef void (*voidFunc)(int);
    771860
     
    781870
    782871void main(FuncRunner & this) {
    783         //thread starts here and runs the function
     872        // thread starts here and runs the function
    784873        this.func( this.arg );
    785874}
     
    793882        return 0?
    794883}
    795 \end{cfacode}
     884\end{cfa}
    796885
    797886A consequence of the strongly typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \textbf{api}.
    798887
    799888Of course, for threads to be useful, it must be possible to start and stop threads and wait for them to complete execution.
    800 While using an \textbf{api} such as \code{fork} and \code{join} is relatively common in the literature, such an interface is unnecessary.
    801 Indeed, the simplest approach is to use \textbf{raii} principles and have threads \code{fork} after the constructor has completed and \code{join} before the destructor runs.
    802 \begin{cfacode}
     889While using an \textbf{api} such as @fork@ and @join@ is relatively common in the literature, such an interface is unnecessary.
     890Indeed, the simplest approach is to use \textbf{raii} principles and have threads @fork@ after the constructor has completed and @join@ before the destructor runs.
     891\begin{cfa}
    803892thread World;
    804893
     
    809898void main() {
    810899        World w;
    811         //Thread forks here
    812 
    813         //Printing "Hello " and "World!" are run concurrently
     900        // Thread forks here
     901
     902        // Printing "Hello " and "World!" are run concurrently
    814903        sout | "Hello " | endl;
    815904
    816         //Implicit join at end of scope
    817 }
    818 \end{cfacode}
     905        // Implicit join at end of scope
     906}
     907\end{cfa}
    819908
    820909This semantic has several advantages over explicit semantics: a thread is always started and stopped exactly once, users cannot make any programming errors, and it naturally scales to multiple threads meaning basic synchronization is very simple.
    821910
    822 \begin{cfacode}
     911\begin{cfa}
    823912thread MyThread {
    824913        //...
    825914};
    826915
    827 //main
     916// main
    828917void main(MyThread& this) {
    829918        //...
     
    832921void foo() {
    833922        MyThread thrds[10];
    834         //Start 10 threads at the beginning of the scope
     923        // Start 10 threads at the beginning of the scope
    835924
    836925        DoStuff();
    837926
    838         //Wait for the 10 threads to finish
    839 }
    840 \end{cfacode}
     927        // Wait for the 10 threads to finish
     928}
     929\end{cfa}
    841930
    842931However, 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.
    843932This 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.
    844933
    845 \begin{cfacode}
     934\begin{cfa}
    846935thread MyThread {
    847936        //...
     
    855944        MyThread* long_lived;
    856945        {
    857                 //Start a thread at the beginning of the scope
     946                // Start a thread at the beginning of the scope
    858947                MyThread short_lived;
    859948
    860                 //create another thread that will outlive the thread in this scope
     949                // create another thread that will outlive the thread in this scope
    861950                long_lived = new MyThread;
    862951
    863952                DoStuff();
    864953
    865                 //Wait for the thread short_lived to finish
     954                // Wait for the thread short_lived to finish
    866955        }
    867956        DoMoreStuff();
    868957
    869         //Now wait for the long_lived to finish
     958        // Now wait for the long_lived to finish
    870959        delete long_lived;
    871960}
    872 \end{cfacode}
     961\end{cfa}
    873962
    874963
     
    888977At the lowest level, concurrent paradigms are implemented as atomic operations and locks.
    889978Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}.
    890 However, for productivity reasons it is desirable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}.
     979However, for productivity reasons it is desirable to have a higher-level construct be the core concurrency paradigm~\cite{Hochstein05}.
    891980
    892981An approach that is worth mentioning because it is gaining in popularity is transactional memory~\cite{Herlihy93}.
     
    909998Methods 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.
    910999Ease 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.
    911 For example, the \CC \code{std::atomic<T>} offers an easy way to express mutual-exclusion on a restricted set of operations (e.g., reading/writing large types atomically).
     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).
    9121001Another challenge with low-level locks is composability.
    9131002Locks have restricted composability because it takes careful organizing for multiple locks to be used while preventing deadlocks.
     
    9381027This concept is generally associated with object-oriented languages like Java~\cite{Java} or \uC~\cite{uC++book} but does not strictly require OO semantics.
    9391028The only requirement is the ability to declare a handle to a shared object and a set of routines that act on it:
    940 \begin{cfacode}
     1029\begin{cfa}
    9411030typedef /*some monitor type*/ monitor;
    9421031int f(monitor & m);
    9431032
    9441033int main() {
    945         monitor m;  //Handle m
    946         f(m);       //Routine using handle
    947 }
    948 \end{cfacode}
     1034        monitor m;  // Handle m
     1035        f(m);       // Routine using handle
     1036}
     1037\end{cfa}
    9491038
    9501039% ======================================================================
     
    9561045First, it is necessary to use pass-by-reference over pass-by-value for monitor routines.
    9571046This semantics is important, because at their core, monitors are implicit mutual-exclusion objects (locks), and these objects cannot be copied.
    958 Therefore, monitors are non-copy-able objects (\code{dtype}).
     1047Therefore, monitors are non-copy-able objects (@dtype@).
    9591048
    9601049Another aspect to consider is when a monitor acquires its mutual exclusion.
    9611050For example, a monitor may need to be passed through multiple helper routines that do not acquire the monitor mutual-exclusion on entry.
    962 Passthrough can occur for generic helper routines (\code{swap}, \code{sort}, etc.) or specific helper routines like the following to implement an atomic counter:
    963 
    964 \begin{cfacode}
     1051Passthrough can occur for generic helper routines (@swap@, @sort@, etc.) or specific helper routines like the following to implement an atomic counter:
     1052
     1053\begin{cfa}
    9651054monitor counter_t { /*...see section $\ref{data}$...*/ };
    9661055
    967 void ?{}(counter_t & nomutex this); //constructor
    968 size_t ++?(counter_t & mutex this); //increment
    969 
    970 //need for mutex is platform dependent
    971 void ?{}(size_t * this, counter_t & mutex cnt); //conversion
    972 \end{cfacode}
     1056void ?{}(counter_t & nomutex this); // constructor
     1057size_t ++?(counter_t & mutex this); // increment
     1058
     1059// need for mutex is platform dependent
     1060void ?{}(size_t * this, counter_t & mutex cnt); // conversion
     1061\end{cfa}
    9731062This counter is used as follows:
    9741063\begin{center}
    9751064\begin{tabular}{c @{\hskip 0.35in} c @{\hskip 0.35in} c}
    976 \begin{cfacode}
    977 //shared counter
     1065\begin{cfa}
     1066// shared counter
    9781067counter_t cnt1, cnt2;
    9791068
    980 //multiple threads access counter
     1069// multiple threads access counter
    9811070thread 1 : cnt1++; cnt2++;
    9821071thread 2 : cnt1++; cnt2++;
     
    9841073        ...
    9851074thread N : cnt1++; cnt2++;
    986 \end{cfacode}
     1075\end{cfa}
    9871076\end{tabular}
    9881077\end{center}
    989 Notice how the counter is used without any explicit synchronization and yet supports thread-safe semantics for both reading and writing, which is similar in usage to the \CC template \code{std::atomic}.
    990 
    991 Here, the constructor (\code{?\{\}}) uses the \code{nomutex} keyword to signify that it does not acquire the monitor mutual-exclusion when constructing.
    992 This semantics is because an object not yet con\-structed should never be shared and therefore does not require mutual exclusion.
     1078Notice how the counter is used without any explicit synchronization and yet supports thread-safe semantics for both reading and writing, which is similar in usage to the \CC template @std::atomic@.
     1079
     1080Here, the constructor (@?{}@) uses the @nomutex@ keyword to signify that it does not acquire the monitor mutual-exclusion when constructing.
     1081This semantics is because an object not yet constructed should never be shared and therefore does not require mutual exclusion.
    9931082Furthermore, it allows the implementation greater freedom when it initializes the monitor locking.
    994 The prefix increment operator uses \code{mutex} to protect the incrementing process from race conditions.
    995 Finally, there is a conversion operator from \code{counter_t} to \code{size_t}.
    996 This conversion may or may not require the \code{mutex} keyword depending on whether or not reading a \code{size_t} is an atomic operation.
     1083The prefix increment operator uses @mutex@ to protect the incrementing process from race conditions.
     1084Finally, there is a conversion operator from @counter_t@ to @size_t@.
     1085This conversion may or may not require the @mutex@ keyword depending on whether or not reading a @size_t@ is an atomic operation.
    9971086
    9981087For maximum usability, monitors use \textbf{multi-acq} semantics, which means a single thread can acquire the same monitor multiple times without deadlock.
    9991088For example, listing \ref{fig:search} uses recursion and \textbf{multi-acq} to print values inside a binary tree.
    10001089\begin{figure}
    1001 \begin{cfacode}[caption={Recursive printing algorithm using \textbf{multi-acq}.},label={fig:search}]
     1090\begin{cfa}[caption={Recursive printing algorithm using \textbf{multi-acq}.},label={fig:search}]
    10021091monitor printer { ... };
    10031092struct tree {
     
    10121101        print(p, t->right);
    10131102}
    1014 \end{cfacode}
     1103\end{cfa}
    10151104\end{figure}
    10161105
    1017 Having both \code{mutex} and \code{nomutex} keywords can be redundant, depending on the meaning of a routine having neither of these keywords.
    1018 For example, it is reasonable that it should default to the safest option (\code{mutex}) when given a routine without qualifiers \code{void foo(counter_t & this)}, whereas assuming \code{nomutex} is unsafe and may cause subtle errors.
    1019 On the other hand, \code{nomutex} is the ``normal'' parameter behaviour, it effectively states explicitly that ``this routine is not special''.
     1106Having both @mutex@ and @nomutex@ keywords can be redundant, depending on the meaning of a routine having neither of these keywords.
     1107For example, it is reasonable that it should default to the safest option (@mutex@) when given a routine without qualifiers @void foo(counter_t & this)@, whereas assuming @nomutex@ is unsafe and may cause subtle errors.
     1108On the other hand, @nomutex@ is the ``normal'' parameter behaviour, it effectively states explicitly that ``this routine is not special''.
    10201109Another alternative is making exactly one of these keywords mandatory, which provides the same semantics but without the ambiguity of supporting routines with neither keyword.
    10211110Mandatory keywords would also have the added benefit of being self-documented but at the cost of extra typing.
     
    10231112Mandatory keywords in \CFA would imply that the compiler must know without doubt whether or not a parameter is a monitor or not.
    10241113Since \CFA relies heavily on traits as an abstraction mechanism, the distinction between a type that is a monitor and a type that looks like a monitor can become blurred.
    1025 For this reason, \CFA only has the \code{mutex} keyword and uses no keyword to mean \code{nomutex}.
    1026 
    1027 The next semantic decision is to establish when \code{mutex} may be used as a type qualifier.
     1114For this reason, \CFA only has the @mutex@ keyword and uses no keyword to mean @nomutex@.
     1115
     1116The next semantic decision is to establish when @mutex@ may be used as a type qualifier.
    10281117Consider the following declarations:
    1029 \begin{cfacode}
     1118\begin{cfa}
    10301119int f1(monitor & mutex m);
    10311120int f2(const monitor & mutex m);
     
    10331122int f4(monitor * mutex m []);
    10341123int f5(graph(monitor *) & mutex m);
    1035 \end{cfacode}
     1124\end{cfa}
    10361125The problem is to identify which object(s) should be acquired.
    10371126Furthermore, each object needs to be acquired only once.
    1038 In the case of simple routines like \code{f1} and \code{f2} it is easy to identify an exhaustive list of objects to acquire on entry.
    1039 Adding indirections (\code{f3}) still allows the compiler and programmer to identify which object is acquired.
    1040 However, adding in arrays (\code{f4}) makes it much harder.
     1127In the case of simple routines like @f1@ and @f2@ it is easy to identify an exhaustive list of objects to acquire on entry.
     1128Adding indirections (@f3@) still allows the compiler and programmer to identify which object is acquired.
     1129However, adding in arrays (@f4@) makes it much harder.
    10411130Array lengths are not necessarily known in C, and even then, making sure objects are only acquired once becomes none-trivial.
    1042 This problem can be extended to absurd limits like \code{f5}, which uses a graph of monitors.
     1131This problem can be extended to absurd limits like @f5@, which uses a graph of monitors.
    10431132To make the issue tractable, this project imposes the requirement that a routine may only acquire one monitor per parameter and it must be the type of the parameter with at most one level of indirection (ignoring potential qualifiers).
    1044 Also note that while routine \code{f3} can be supported, meaning that monitor \code{**m} is acquired, passing an array to this routine would be type-safe and yet result in undefined behaviour because only the first element of the array is acquired.
     1133Also note that while routine @f3@ can be supported, meaning that monitor @**m@ is acquired, passing an array to this routine would be type-safe and yet result in undefined behaviour because only the first element of the array is acquired.
    10451134However, this ambiguity is part of the C type-system with respects to arrays.
    1046 For this reason, \code{mutex} is disallowed in the context where arrays may be passed:
    1047 \begin{cfacode}
    1048 int f1(monitor & mutex m);    //Okay : recommended case
    1049 int f2(monitor * mutex m);    //Not Okay : Could be an array
    1050 int f3(monitor mutex m []);  //Not Okay : Array of unknown length
    1051 int f4(monitor ** mutex m);   //Not Okay : Could be an array
    1052 int f5(monitor * mutex m []); //Not Okay : Array of unknown length
    1053 \end{cfacode}
     1135For this reason, @mutex@ is disallowed in the context where arrays may be passed:
     1136\begin{cfa}
     1137int f1(monitor & mutex m);    // Okay : recommended case
     1138int f2(monitor * mutex m);    // Not Okay : Could be an array
     1139int f3(monitor mutex m []);  // Not Okay : Array of unknown length
     1140int f4(monitor ** mutex m);   // Not Okay : Could be an array
     1141int f5(monitor * mutex m []); // Not Okay : Array of unknown length
     1142\end{cfa}
    10541143Note that not all array functions are actually distinct in the type system.
    10551144However, even if the code generation could tell the difference, the extra information is still not sufficient to extend meaningfully the monitor call semantic.
     
    10571146Unlike object-oriented monitors, where calling a mutex member \emph{implicitly} acquires mutual-exclusion of the receiver object, \CFA uses an explicit mechanism to specify the object that acquires mutual-exclusion.
    10581147A consequence of this approach is that it extends naturally to multi-monitor calls.
    1059 \begin{cfacode}
     1148\begin{cfa}
    10601149int f(MonitorA & mutex a, MonitorB & mutex b);
    10611150
     
    10631152MonitorB b;
    10641153f(a,b);
    1065 \end{cfacode}
     1154\end{cfa}
    10661155While OO monitors could be extended with a mutex qualifier for multiple-monitor calls, no example of this feature could be found.
    10671156The capability to acquire multiple locks before entering a critical section is called \emph{\textbf{bulk-acq}}.
     
    10711160This consistent ordering means acquiring multiple monitors is safe from deadlock when using \textbf{bulk-acq}.
    10721161However, users can still force the acquiring order.
    1073 For example, notice which routines use \code{mutex}/\code{nomutex} and how this affects acquiring order:
    1074 \begin{cfacode}
    1075 void foo(A& mutex a, B& mutex b) { //acquire a & b
     1162For example, notice which routines use @mutex@/@nomutex@ and how this affects acquiring order:
     1163\begin{cfa}
     1164void foo(A& mutex a, B& mutex b) { // acquire a & b
    10761165        ...
    10771166}
    10781167
    1079 void bar(A& mutex a, B& /*nomutex*/ b) { //acquire a
    1080         ... foo(a, b); ... //acquire b
    1081 }
    1082 
    1083 void baz(A& /*nomutex*/ a, B& mutex b) { //acquire b
    1084         ... foo(a, b); ... //acquire a
    1085 }
    1086 \end{cfacode}
    1087 The \textbf{multi-acq} monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}.
    1088 In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order.
     1168void bar(A& mutex a, B& /*nomutex*/ b) { // acquire a
     1169        ... foo(a, b); ... // acquire b
     1170}
     1171
     1172void baz(A& /*nomutex*/ a, B& mutex b) { // acquire b
     1173        ... foo(a, b); ... // acquire a
     1174}
     1175\end{cfa}
     1176The \textbf{multi-acq} monitor lock allows a monitor lock to be acquired by both @bar@ or @baz@ and acquired again in @foo@.
     1177In the calls to @bar@ and @baz@ the monitors are acquired in opposite order.
    10891178
    10901179However, such use leads to lock acquiring order problems.
    1091 In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}.
     1180In the example above, the user uses implicit ordering in the case of function @foo@ but explicit ordering in the case of @bar@ and @baz@.
    10921181This subtle difference means that calling these routines concurrently may lead to deadlock and is therefore undefined behaviour.
    10931182As shown~\cite{Lister77}, solving this problem requires:
     
    11011190
    11021191For example, \textbf{multi-acq} and \textbf{bulk-acq} can be used together in interesting ways:
    1103 \begin{cfacode}
     1192\begin{cfa}
    11041193monitor bank { ... };
    11051194
     
    11101199        deposit( yourbank, me2you );
    11111200}
    1112 \end{cfacode}
     1201\end{cfa}
    11131202This example shows a trivial solution to the bank-account transfer problem~\cite{BankTransfer}.
    11141203Without \textbf{multi-acq} and \textbf{bulk-acq}, the solution to this problem is much more involved and requires careful engineering.
    11151204
    1116 \subsection{\code{mutex} statement} \label{mutex-stmt}
    1117 
    1118 The 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 \code{mutex} statement to work around the need for unnecessary names, avoiding a major software engineering problem~\cite{2FTwoHardThings}.
    1119 Table \ref{lst:mutex-stmt} shows an example of the \code{mutex} statement, which introduces a new scope in which the mutual-exclusion of a set of monitor is acquired.
    1120 Beyond naming, the \code{mutex} statement has no semantic difference from a routine call with \code{mutex} parameters.
     1205
     1206\subsection{\protect\lstinline|mutex| statement} \label{mutex-stmt}
     1207
     1208The 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}.
     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.
     1210Beyond naming, the @mutex@ statement has no semantic difference from a routine call with @mutex@ parameters.
    11211211
    11221212\begin{table}
    11231213\begin{center}
    11241214\begin{tabular}{|c|c|}
    1125 function call & \code{mutex} statement \\
     1215function call & @mutex@ statement \\
    11261216\hline
    1127 \begin{cfacode}[tabsize=3]
     1217\begin{cfa}[tabsize=3]
    11281218monitor M {};
    11291219void foo( M & mutex m1, M & mutex m2 ) {
    1130         //critical section
     1220        // critical section
    11311221}
    11321222
     
    11341224        foo( m1, m2 );
    11351225}
    1136 \end{cfacode}&\begin{cfacode}[tabsize=3]
     1226\end{cfa}&\begin{cfa}[tabsize=3]
    11371227monitor M {};
    11381228void bar( M & m1, M & m2 ) {
    11391229        mutex(m1, m2) {
    1140                 //critical section
    1141         }
    1142 }
    1143 
    1144 
    1145 \end{cfacode}
     1230                // critical section
     1231        }
     1232}
     1233
     1234
     1235\end{cfa}
    11461236\end{tabular}
    11471237\end{center}
    1148 \caption{Regular call semantics vs. \code{mutex} statement}
     1238\caption{Regular call semantics vs. \protect\lstinline|mutex| statement}
    11491239\label{lst:mutex-stmt}
    11501240\end{table}
     
    11591249This data should be intrinsic to the monitor declaration to prevent any accidental use of data without its appropriate protection.
    11601250For example, here is a complete version of the counter shown in section \ref{call}:
    1161 \begin{cfacode}
     1251\begin{cfa}
    11621252monitor counter_t {
    11631253        int value;
     
    11721262}
    11731263
    1174 //need for mutex is platform dependent here
     1264// need for mutex is platform dependent here
    11751265void ?{}(int * this, counter_t & mutex cnt) {
    11761266        *this = (int)cnt;
    11771267}
    1178 \end{cfacode}
    1179 
    1180 Like threads and coroutines, monitors are defined in terms of traits with some additional language support in the form of the \code{monitor} keyword.
     1268\end{cfa}
     1269
     1270Like threads and coroutines, monitors are defined in terms of traits with some additional language support in the form of the @monitor@ keyword.
    11811271The monitor trait is:
    1182 \begin{cfacode}
     1272\begin{cfa}
    11831273trait is_monitor(dtype T) {
    11841274        monitor_desc * get_monitor( T & );
    11851275        void ^?{}( T & mutex );
    11861276};
    1187 \end{cfacode}
    1188 Note that the destructor of a monitor must be a \code{mutex} routine to prevent deallocation while a thread is accessing the monitor.
    1189 As with any object, calls to a monitor, using \code{mutex} or otherwise, is undefined behaviour after the destructor has run.
     1277\end{cfa}
     1278Note that the destructor of a monitor must be a @mutex@ routine to prevent deallocation while a thread is accessing the monitor.
     1279As with any object, calls to a monitor, using @mutex@ or otherwise, is undefined behaviour after the destructor has run.
    11901280
    11911281% ======================================================================
     
    12021292First, here is a simple example of internal scheduling:
    12031293
    1204 \begin{cfacode}
     1294\begin{cfa}
    12051295monitor A {
    12061296        condition e;
     
    12091299void foo(A& mutex a1, A& mutex a2) {
    12101300        ...
    1211         //Wait for cooperation from bar()
     1301        // Wait for cooperation from bar()
    12121302        wait(a1.e);
    12131303        ...
     
    12151305
    12161306void bar(A& mutex a1, A& mutex a2) {
    1217         //Provide cooperation for foo()
     1307        // Provide cooperation for foo()
    12181308        ...
    1219         //Unblock foo
     1309        // Unblock foo
    12201310        signal(a1.e);
    12211311}
    1222 \end{cfacode}
     1312\end{cfa}
    12231313There are two details to note here.
    1224 First, \code{signal} is a delayed operation; it only unblocks the waiting thread when it reaches the end of the critical section.
     1314First, @signal@ is a delayed operation; it only unblocks the waiting thread when it reaches the end of the critical section.
    12251315This semantics is needed to respect mutual-exclusion, i.e., the signaller and signalled thread cannot be in the monitor simultaneously.
    1226 The alternative is to return immediately after the call to \code{signal}, which is significantly more restrictive.
    1227 Second, in \CFA, while it is common to store a \code{condition} as a field of the monitor, a \code{condition} variable can be stored/created independently of a monitor.
    1228 Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, ensuring a basic ordering.
    1229 
    1230 An important aspect of the implementation is that \CFA does not allow barging, which means that once function \code{bar} releases the monitor, \code{foo} is guaranteed to be the next thread to acquire the monitor (unless some other thread waited on the same condition).
     1316The alternative is to return immediately after the call to @signal@, which is significantly more restrictive.
     1317Second, 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.
     1318Here routine @foo@ waits for the @signal@ from @bar@ before making further progress, ensuring a basic ordering.
     1319
     1320An important aspect of the implementation is that \CFA does not allow barging, which means that once function @bar@ releases the monitor, @foo@ is guaranteed to be the next thread to acquire the monitor (unless some other thread waited on the same condition).
    12311321This guarantee offers the benefit of not having to loop around waits to recheck that a condition is met.
    12321322The main reason \CFA offers this guarantee is that users can easily introduce barging if it becomes a necessity but adding barging prevention or barging avoidance is more involved without language support.
     
    12401330It is easy to understand the problem of multi-monitor scheduling using a series of pseudo-code examples.
    12411331Note that for simplicity in the following snippets of pseudo-code, waiting and signalling is done using an implicit condition variable, like Java built-in monitors.
    1242 Indeed, \code{wait} statements always use the implicit condition variable as parameters and explicitly name the monitors (A and B) associated with the condition.
     1332Indeed, @wait@ statements always use the implicit condition variable as parameters and explicitly name the monitors (A and B) associated with the condition.
    12431333Note that in \CFA, condition variables are tied to a \emph{group} of monitors on first use (called branding), which means that using internal scheduling with distinct sets of monitors requires one condition variable per set of monitors.
    12441334The example below shows the simple case of having two threads (one for each column) and a single monitor A.
     
    12461336\begin{multicols}{2}
    12471337thread 1
    1248 \begin{pseudo}
     1338\begin{cfa}
    12491339acquire A
    12501340        wait A
    12511341release A
    1252 \end{pseudo}
     1342\end{cfa}
    12531343
    12541344\columnbreak
    12551345
    12561346thread 2
    1257 \begin{pseudo}
     1347\begin{cfa}
    12581348acquire A
    12591349        signal A
    12601350release A
    1261 \end{pseudo}
     1351\end{cfa}
    12621352\end{multicols}
    12631353One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling.
    1264 It is important to note here that both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired.
     1354It is important to note here that both @wait@ and @signal@ must be called with the proper monitor(s) already acquired.
    12651355This semantic is a logical requirement for barging prevention.
    12661356
    12671357A direct extension of the previous example is a \textbf{bulk-acq} version:
    12681358\begin{multicols}{2}
    1269 \begin{pseudo}
     1359\begin{cfa}
    12701360acquire A & B
    12711361        wait A & B
    12721362release A & B
    1273 \end{pseudo}
     1363\end{cfa}
    12741364\columnbreak
    1275 \begin{pseudo}
     1365\begin{cfa}
    12761366acquire A & B
    12771367        signal A & B
    12781368release A & B
    1279 \end{pseudo}
     1369\end{cfa}
    12801370\end{multicols}
    12811371\noindent This version uses \textbf{bulk-acq} (denoted using the {\sf\&} symbol), but the presence of multiple monitors does not add a particularly new meaning.
     
    12851375
    12861376While deadlock issues can occur when nesting monitors, these issues are only a symptom of the fact that locks, and by extension monitors, are not perfectly composable.
    1287 For monitors, a well-known deadlock problem is the Nested Monitor Problem~\cite{Lister77}, which occurs when a \code{wait} is made by a thread that holds more than one monitor.
    1288 For example, the following pseudo-code runs into the nested-monitor problem:
     1377For monitors, a well-known deadlock problem is the Nested Monitor Problem~\cite{Lister77}, which occurs when a @wait@ is made by a thread that holds more than one monitor.
     1378For example, the following cfa-code runs into the nested-monitor problem:
    12891379\begin{multicols}{2}
    1290 \begin{pseudo}
     1380\begin{cfa}
    12911381acquire A
    12921382        acquire B
     
    12941384        release B
    12951385release A
    1296 \end{pseudo}
     1386\end{cfa}
    12971387
    12981388\columnbreak
    12991389
    1300 \begin{pseudo}
     1390\begin{cfa}
    13011391acquire A
    13021392        acquire B
     
    13041394        release B
    13051395release A
    1306 \end{pseudo}
     1396\end{cfa}
    13071397\end{multicols}
    1308 \noindent The \code{wait} only releases monitor \code{B} so the signalling thread cannot acquire monitor \code{A} to get to the \code{signal}.
    1309 Attempting release of all acquired monitors at the \code{wait} introduces a different set of problems, such as releasing monitor \code{C}, which has nothing to do with the \code{signal}.
     1398\noindent The @wait@ only releases monitor @B@ so the signalling thread cannot acquire monitor @A@ to get to the @signal@.
     1399Attempting release of all acquired monitors at the @wait@ introduces a different set of problems, such as releasing monitor @C@, which has nothing to do with the @signal@.
    13101400
    13111401However, for monitors as for locks, it is possible to write a program using nesting without encountering any problems if nesting is done correctly.
    1312 For example, the next pseudo-code snippet acquires monitors {\sf A} then {\sf B} before waiting, while only acquiring {\sf B} when signalling, effectively avoiding the Nested Monitor Problem~\cite{Lister77}.
     1402For example, the next cfa-code snippet acquires monitors {\sf A} then {\sf B} before waiting, while only acquiring {\sf B} when signalling, effectively avoiding the Nested Monitor Problem~\cite{Lister77}.
    13131403
    13141404\begin{multicols}{2}
    1315 \begin{pseudo}
     1405\begin{cfa}
    13161406acquire A
    13171407        acquire B
     
    13191409        release B
    13201410release A
    1321 \end{pseudo}
     1411\end{cfa}
    13221412
    13231413\columnbreak
    13241414
    1325 \begin{pseudo}
     1415\begin{cfa}
    13261416
    13271417acquire B
     
    13291419release B
    13301420
    1331 \end{pseudo}
     1421\end{cfa}
    13321422\end{multicols}
    13331423
     
    13411431
    13421432A larger example is presented to show complex issues for \textbf{bulk-acq} and its implementation options are analyzed.
    1343 Listing \ref{lst:int-bulk-pseudo} 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 pseudo-code in listing \ref{lst:int-bulk-pseudo}.
    1344 For the purpose of translating the given pseudo-code into \CFA-code, any method of introducing a monitor is acceptable, e.g., \code{mutex} parameters, global variables, pointer parameters, or using locals with the \code{mutex} statement.
    1345 
    1346 \begin{figure}[!t]
     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.
     1435
     1436\begin{figure}
    13471437\begin{multicols}{2}
    13481438Waiting thread
    1349 \begin{pseudo}[numbers=left]
     1439\begin{cfa}[numbers=left]
    13501440acquire A
    1351         //Code Section 1
     1441        // Code Section 1
    13521442        acquire A & B
    1353                 //Code Section 2
     1443                // Code Section 2
    13541444                wait A & B
    1355                 //Code Section 3
     1445                // Code Section 3
    13561446        release A & B
    1357         //Code Section 4
     1447        // Code Section 4
    13581448release A
    1359 \end{pseudo}
     1449\end{cfa}
    13601450\columnbreak
    13611451Signalling thread
    1362 \begin{pseudo}[numbers=left, firstnumber=10,escapechar=|]
     1452\begin{cfa}[numbers=left, firstnumber=10,escapechar=|]
    13631453acquire A
    1364         //Code Section 5
     1454        // Code Section 5
    13651455        acquire A & B
    1366                 //Code Section 6
     1456                // Code Section 6
    13671457                |\label{line:signal1}|signal A & B
    1368                 //Code Section 7
     1458                // Code Section 7
    13691459        |\label{line:releaseFirst}|release A & B
    1370         //Code Section 8
     1460        // Code Section 8
    13711461|\label{line:lastRelease}|release A
    1372 \end{pseudo}
     1462\end{cfa}
    13731463\end{multicols}
    1374 \begin{cfacode}[caption={Internal scheduling with \textbf{bulk-acq}},label={lst:int-bulk-pseudo}]
    1375 \end{cfacode}
     1464\begin{cfa}[caption={Internal scheduling with \textbf{bulk-acq}},label={lst:int-bulk-cfa}]
     1465\end{cfa}
    13761466\begin{center}
    1377 \begin{cfacode}[xleftmargin=.4\textwidth]
     1467\begin{cfa}[xleftmargin=.4\textwidth]
    13781468monitor A a;
    13791469monitor B b;
    13801470condition c;
    1381 \end{cfacode}
     1471\end{cfa}
    13821472\end{center}
    13831473\begin{multicols}{2}
    13841474Waiting thread
    1385 \begin{cfacode}
     1475\begin{cfa}
    13861476mutex(a) {
    1387         //Code Section 1
     1477        // Code Section 1
    13881478        mutex(a, b) {
    1389                 //Code Section 2
     1479                // Code Section 2
    13901480                wait(c);
    1391                 //Code Section 3
    1392         }
    1393         //Code Section 4
    1394 }
    1395 \end{cfacode}
     1481                // Code Section 3
     1482        }
     1483        // Code Section 4
     1484}
     1485\end{cfa}
    13961486\columnbreak
    13971487Signalling thread
    1398 \begin{cfacode}
     1488\begin{cfa}
    13991489mutex(a) {
    1400         //Code Section 5
     1490        // Code Section 5
    14011491        mutex(a, b) {
    1402                 //Code Section 6
     1492                // Code Section 6
    14031493                signal(c);
    1404                 //Code Section 7
    1405         }
    1406         //Code Section 8
    1407 }
    1408 \end{cfacode}
     1494                // Code Section 7
     1495        }
     1496        // Code Section 8
     1497}
     1498\end{cfa}
    14091499\end{multicols}
    1410 \begin{cfacode}[caption={Equivalent \CFA code for listing \ref{lst:int-bulk-pseudo}},label={lst:int-bulk-cfa}]
    1411 \end{cfacode}
     1500\begin{cfa}[caption={Equivalent \CFA code for listing \ref{lst:int-bulk-cfa}},label={lst:int-bulk-cfa}]
     1501\end{cfa}
    14121502\begin{multicols}{2}
    14131503Waiter
    1414 \begin{pseudo}[numbers=left]
     1504\begin{cfa}[numbers=left]
    14151505acquire A
    14161506        acquire A & B
     
    14181508        release A & B
    14191509release A
    1420 \end{pseudo}
     1510\end{cfa}
    14211511
    14221512\columnbreak
    14231513
    14241514Signaller
    1425 \begin{pseudo}[numbers=left, firstnumber=6,escapechar=|]
     1515\begin{cfa}[numbers=left, firstnumber=6,escapechar=|]
    14261516acquire A
    14271517        acquire A & B
    14281518                signal A & B
    14291519        release A & B
    1430         |\label{line:secret}|//Secretly keep B here
     1520        |\label{line:secret}|// Secretly keep B here
    14311521release A
    1432 //Wakeup waiter and transfer A & B
    1433 \end{pseudo}
     1522// Wakeup waiter and transfer A & B
     1523\end{cfa}
    14341524\end{multicols}
    1435 \begin{cfacode}[caption={Listing \ref{lst:int-bulk-pseudo}, with delayed signalling comments},label={lst:int-secret}]
    1436 \end{cfacode}
     1525\begin{cfa}[caption={Listing \ref{lst:int-bulk-cfa}, with delayed signalling comments},label={lst:int-secret}]
     1526\end{cfa}
    14371527\end{figure}
    14381528
    1439 The complexity begins at code sections 4 and 8 in listing \ref{lst:int-bulk-pseudo}, which are where the existing semantics of internal scheduling needs to be extended for multiple monitors.
    1440 The 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 pseudo-code.
    1441 When the signaller thread reaches the location where it should ``release \code{A & B}'' (listing \ref{lst:int-bulk-pseudo} line \ref{line:releaseFirst}), it must actually transfer ownership of monitor \code{B} to the waiting thread.
    1442 This ownership transfer is required in order to prevent barging into \code{B} by another thread, since both the signalling and signalled threads still need monitor \code{A}.
     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.
     1530The 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.
     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.
     1532This 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@.
    14431533There are three options:
    14441534
     
    14521542
    14531543However, 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.
    1454 Listing \ref{lst:dependency} shows a slightly different example where a third thread is waiting on monitor \code{A}, using a different condition variable.
    1455 Because the third thread is signalled when secretly holding \code{B}, the goal  becomes unreachable.
     1544Listing \ref{lst:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
     1545Because the third thread is signalled when secretly holding @B@, the goal  becomes unreachable.
    14561546Depending on the order of signals (listing \ref{lst:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
    14571547
    1458 \paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor \code{A} needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
    1459 \paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor \code{B} needs to be retained and passed to thread $\alpha$ along with monitor \code{A}, which can be done directly or possibly using thread $\beta$ as an intermediate.
     1548\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.
     1549\paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.
    14601550\\
    14611551
     
    14711561\begin{multicols}{3}
    14721562Thread $\alpha$
    1473 \begin{pseudo}[numbers=left, firstnumber=1]
     1563\begin{cfa}[numbers=left, firstnumber=1]
    14741564acquire A
    14751565        acquire A & B
     
    14771567        release A & B
    14781568release A
    1479 \end{pseudo}
     1569\end{cfa}
    14801570\columnbreak
    14811571Thread $\gamma$
    1482 \begin{pseudo}[numbers=left, firstnumber=6, escapechar=|]
     1572\begin{cfa}[numbers=left, firstnumber=6, escapechar=|]
    14831573acquire A
    14841574        acquire A & B
     
    14871577        |\label{line:signal-a}|signal A
    14881578|\label{line:release-a}|release A
    1489 \end{pseudo}
     1579\end{cfa}
    14901580\columnbreak
    14911581Thread $\beta$
    1492 \begin{pseudo}[numbers=left, firstnumber=12, escapechar=|]
     1582\begin{cfa}[numbers=left, firstnumber=12, escapechar=|]
    14931583acquire A
    14941584        wait A
    14951585|\label{line:release-aa}|release A
    1496 \end{pseudo}
     1586\end{cfa}
    14971587\end{multicols}
    1498 \begin{cfacode}[caption={Pseudo-code for the three thread example.},label={lst:dependency}]
    1499 \end{cfacode}
     1588\begin{cfa}[caption={Pseudo-code for the three thread example.},label={lst:dependency}]
     1589\end{cfa}
    15001590\begin{center}
    15011591\input{dependency}
     
    15051595\end{figure}
    15061596
    1507 In listing \ref{lst:int-bulk-pseudo}, there is a solution that satisfies both barging prevention and mutual exclusion.
    1508 If ownership of both monitors is transferred to the waiter when the signaller releases \code{A & B} and then the waiter transfers back ownership of \code{A} back to the signaller when it releases it, then the problem is solved (\code{B} is no longer in use at this point).
     1597In listing \ref{lst:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
     1598If 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).
    15091599Dynamically finding the correct order is therefore the second possible solution.
    15101600The problem is effectively resolving a dependency graph of ownership requirements.
     
    15141604\begin{figure}
    15151605\begin{multicols}{2}
    1516 \begin{pseudo}
     1606\begin{cfa}
    15171607acquire A
    15181608        acquire B
     
    15221612        release B
    15231613release A
    1524 \end{pseudo}
     1614\end{cfa}
    15251615
    15261616\columnbreak
    15271617
    1528 \begin{pseudo}
     1618\begin{cfa}
    15291619acquire A
    15301620        acquire B
     
    15341624        release B
    15351625release A
    1536 \end{pseudo}
     1626\end{cfa}
    15371627\end{multicols}
    1538 \begin{cfacode}[caption={Extension to three monitors of listing \ref{lst:int-bulk-pseudo}},label={lst:explosion}]
    1539 \end{cfacode}
     1628\begin{cfa}[caption={Extension to three monitors of listing \ref{lst:int-bulk-cfa}},label={lst:explosion}]
     1629\end{cfa}
    15401630\end{figure}
    15411631
     
    15461636\subsubsection{Partial Signalling} \label{partial-sig}
    15471637Finally, the solution that is chosen for \CFA is to use partial signalling.
    1548 Again using listing \ref{lst:int-bulk-pseudo}, the partial signalling solution transfers ownership of monitor \code{B} at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor \code{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@.
    15491639Only when it reaches line \ref{line:lastRelease} does it actually wake up the waiting thread.
    15501640This 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.
     
    15541644Using partial signalling, listing \ref{lst:dependency} can be solved easily:
    15551645\begin{itemize}
    1556         \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor \code{B} to thread $\alpha$ and continues to hold monitor \code{A}.
    1557         \item When thread $\gamma$ reaches line \ref{line:release-a}  it transfers monitor \code{A} to thread $\beta$  and wakes it up.
    1558         \item When thread $\beta$  reaches line \ref{line:release-aa} it transfers monitor \code{A} to thread $\alpha$ and wakes it up.
     1646        \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
     1647        \item When thread $\gamma$ reaches line \ref{line:release-a}  it transfers monitor @A@ to thread $\beta$  and wakes it up.
     1648        \item When thread $\beta$  reaches line \ref{line:release-aa} it transfers monitor @A@ to thread $\alpha$ and wakes it up.
    15591649\end{itemize}
    15601650
     
    15661656\begin{table}
    15671657\begin{tabular}{|c|c|}
    1568 \code{signal} & \code{signal_block} \\
     1658@signal@ & @signal_block@ \\
    15691659\hline
    1570 \begin{cfacode}[tabsize=3]
    1571 monitor DatingService
    1572 {
    1573         //compatibility codes
     1660\begin{cfa}[tabsize=3]
     1661monitor DatingService {
     1662        // compatibility codes
    15741663        enum{ CCodes = 20 };
    15751664
     
    15821671condition exchange;
    15831672
    1584 int girl(int phoneNo, int ccode)
    1585 {
    1586         //no compatible boy ?
    1587         if(empty(boys[ccode]))
    1588         {
    1589                 //wait for boy
    1590                 wait(girls[ccode]);
    1591 
    1592                 //make phone number available
    1593                 girlPhoneNo = phoneNo;
    1594 
    1595                 //wake boy from chair
    1596                 signal(exchange);
    1597         }
    1598         else
    1599         {
    1600                 //make phone number available
    1601                 girlPhoneNo = phoneNo;
    1602 
    1603                 //wake boy
    1604                 signal(boys[ccode]);
    1605 
    1606                 //sit in chair
    1607                 wait(exchange);
     1673int girl(int phoneNo, int cfa) {
     1674        // no compatible boy ?
     1675        if(empty(boys[cfa])) {
     1676                wait(girls[cfa]);               // wait for boy
     1677                girlPhoneNo = phoneNo;          // make phone number available
     1678                signal(exchange);               // wake boy from chair
     1679        } else {
     1680                girlPhoneNo = phoneNo;          // make phone number available
     1681                signal(boys[cfa]);              // wake boy
     1682                wait(exchange);         // sit in chair
    16081683        }
    16091684        return boyPhoneNo;
    16101685}
    1611 
    1612 int boy(int phoneNo, int ccode)
    1613 {
    1614         //same as above
    1615         //with boy/girl interchanged
    1616 }
    1617 \end{cfacode}&\begin{cfacode}[tabsize=3]
    1618 monitor DatingService
    1619 {
    1620         //compatibility codes
    1621         enum{ CCodes = 20 };
     1686int boy(int phoneNo, int cfa) {
     1687        // same as above
     1688        // with boy/girl interchanged
     1689}
     1690\end{cfa}&\begin{cfa}[tabsize=3]
     1691monitor DatingService {
     1692
     1693        enum{ CCodes = 20 };    // compatibility codes
    16221694
    16231695        int girlPhoneNo;
     
    16271699condition girls[CCodes];
    16281700condition boys [CCodes];
    1629 //exchange is not needed
    1630 
    1631 int girl(int phoneNo, int ccode)
    1632 {
    1633         //no compatible boy ?
    1634         if(empty(boys[ccode]))
    1635         {
    1636                 //wait for boy
    1637                 wait(girls[ccode]);
    1638 
    1639                 //make phone number available
    1640                 girlPhoneNo = phoneNo;
    1641 
    1642                 //wake boy from chair
    1643                 signal(exchange);
    1644         }
    1645         else
    1646         {
    1647                 //make phone number available
    1648                 girlPhoneNo = phoneNo;
    1649 
    1650                 //wake boy
    1651                 signal_block(boys[ccode]);
    1652 
    1653                 //second handshake unnecessary
     1701// exchange is not needed
     1702
     1703int girl(int phoneNo, int cfa) {
     1704        // no compatible boy ?
     1705        if(empty(boys[cfa])) {
     1706                wait(girls[cfa]);               // wait for boy
     1707                girlPhoneNo = phoneNo;          // make phone number available
     1708                signal(exchange);               // wake boy from chair
     1709        } else {
     1710                girlPhoneNo = phoneNo;          // make phone number available
     1711                signal_block(boys[cfa]);                // wake boy
     1712
     1713                // second handshake unnecessary
    16541714
    16551715        }
     
    16571717}
    16581718
    1659 int boy(int phoneNo, int ccode)
    1660 {
    1661         //same as above
    1662         //with boy/girl interchanged
    1663 }
    1664 \end{cfacode}
     1719int boy(int phoneNo, int cfa) {
     1720        // same as above
     1721        // with boy/girl interchanged
     1722}
     1723\end{cfa}
    16651724\end{tabular}
    1666 \caption{Dating service example using \code{signal} and \code{signal_block}. }
     1725\caption{Dating service example using \protect\lstinline|signal| and \protect\lstinline|signal_block|. }
    16671726\label{tbl:datingservice}
    16681727\end{table}
    16691728An important note is that, until now, signalling a monitor was a delayed operation.
    1670 The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement.
    1671 However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the \code{signal_block} routine.
     1729The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the @signal@ statement.
     1730However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the @signal_block@ routine.
    16721731
    16731732The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
    1674 As mentioned, \code{signal} only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
    1675 To avoid this explicit synchronization, the \code{condition} type offers the \code{signal_block} routine, which handles the two-way handshake as shown in the example.
     1733As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
     1734To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
    16761735This feature removes the need for a second condition variables and simplifies programming.
    1677 Like every other monitor semantic, \code{signal_block} uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to \code{signal_block}, meaning no other thread can acquire the monitor either before or after the call.
     1736Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
    16781737
    16791738% ======================================================================
     
    16871746Internal Scheduling & External Scheduling & Go\\
    16881747\hline
    1689 \begin{ucppcode}[tabsize=3]
     1748\begin{uC++}[tabsize=3]
    16901749_Monitor Semaphore {
    16911750        condition c;
     
    17021761        }
    17031762}
    1704 \end{ucppcode}&\begin{ucppcode}[tabsize=3]
     1763\end{uC++}&\begin{uC++}[tabsize=3]
    17051764_Monitor Semaphore {
    17061765
     
    17171776        }
    17181777}
    1719 \end{ucppcode}&\begin{gocode}[tabsize=3]
     1778\end{uC++}&\begin{Go}[tabsize=3]
    17201779type MySem struct {
    17211780        inUse bool
     
    17371796        s.inUse = false
    17381797
    1739         //This actually deadlocks
    1740         //when single thread
     1798        // This actually deadlocks
     1799        // when single thread
    17411800        s.c <- false
    17421801}
    1743 \end{gocode}
     1802\end{Go}
    17441803\end{tabular}
    17451804\caption{Different forms of scheduling.}
     
    17481807This method is more constrained and explicit, which helps users reduce the non-deterministic nature of concurrency.
    17491808Indeed, as the following examples demonstrate, external scheduling allows users to wait for events from other threads without the concern of unrelated events occurring.
    1750 External scheduling can generally be done either in terms of control flow (e.g., Ada with \code{accept}, \uC with \code{_Accept}) or in terms of data (e.g., 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).
    17511810Of 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.
    17521811Two challenges specific to \CFA arise when trying to add external scheduling with loose object definitions and multiple-monitor routines.
    1753 The previous example shows a simple use \code{_Accept} versus \code{wait}/\code{signal} and its advantages.
    1754 Note that while other languages often use \code{accept}/\code{select} as the core external scheduling keyword, \CFA uses \code{waitfor} to prevent name collisions with existing socket \textbf{api}s.
    1755 
    1756 For the \code{P} member above using internal scheduling, the call to \code{wait} only guarantees that \code{V} is the last routine to access the monitor, allowing a third routine, say \code{isInUse()}, acquire mutual exclusion several times while routine \code{P} is waiting.
    1757 On the other hand, external scheduling guarantees that while routine \code{P} is waiting, no other routine than \code{V} can acquire the monitor.
     1812The previous example shows a simple use @_Accept@ versus @wait@/@signal@ and its advantages.
     1813Note that while other languages often use @accept@/@select@ as the core external scheduling keyword, \CFA uses @waitfor@ to prevent name collisions with existing socket \textbf{api}s.
     1814
     1815For the @P@ member above using internal scheduling, the call to @wait@ only guarantees that @V@ is the last routine to access the monitor, allowing a third routine, say @isInUse()@, acquire mutual exclusion several times while routine @P@ is waiting.
     1816On the other hand, external scheduling guarantees that while routine @P@ is waiting, no other routine than @V@ can acquire the monitor.
    17581817
    17591818% ======================================================================
     
    17651824Since \CFA is not object oriented, monitors become both more difficult to implement and less clear for a user:
    17661825
    1767 \begin{cfacode}
     1826\begin{cfa}
    17681827monitor A {};
    17691828
    17701829void f(A & mutex a);
    17711830void g(A & mutex a) {
    1772         waitfor(f); //Obvious which f() to wait for
    1773 }
    1774 
    1775 void f(A & mutex a, int); //New different F added in scope
     1831        waitfor(f); // Obvious which f() to wait for
     1832}
     1833
     1834void f(A & mutex a, int); // New different F added in scope
    17761835void h(A & mutex a) {
    1777         waitfor(f); //Less obvious which f() to wait for
    1778 }
    1779 \end{cfacode}
     1836        waitfor(f); // Less obvious which f() to wait for
     1837}
     1838\end{cfa}
    17801839
    17811840Furthermore, external scheduling is an example where implementation constraints become visible from the interface.
    1782 Here is the pseudo-code for the entering phase of a monitor:
     1841Here is the cfa-code for the entering phase of a monitor:
    17831842\begin{center}
    17841843\begin{tabular}{l}
    1785 \begin{pseudo}
     1844\begin{cfa}
    17861845        if monitor is free
    17871846                enter
     
    17921851        else
    17931852                block
    1794 \end{pseudo}
     1853\end{cfa}
    17951854\end{tabular}
    17961855\end{center}
    17971856For the first two conditions, it is easy to implement a check that can evaluate the condition in a few instructions.
    1798 However, a fast check for \pscode{monitor accepts me} is much harder to implement depending on the constraints put on the monitors.
     1857However, a fast check for @monitor accepts me@ is much harder to implement depending on the constraints put on the monitors.
    17991858Indeed, monitors are often expressed as an entry queue and some acceptor queue as in Figure~\ref{fig:ClassicalMonitor}.
    18001859
     
    18221881The alternative is to alter the implementation as in Figure~\ref{fig:BulkMonitor}.
    18231882Here, the mutex routine called is associated with a thread on the entry queue while a list of acceptable routines is kept separate.
    1824 Generating a mask dynamically means that the storage for the mask information can vary between calls to \code{waitfor}, allowing for more flexibility and extensions.
     1883Generating a mask dynamically means that the storage for the mask information can vary between calls to @waitfor@, allowing for more flexibility and extensions.
    18251884Storing an array of accepted function pointers replaces the single instruction bitmask comparison with dereferencing a pointer followed by a linear search.
    1826 Furthermore, supporting nested external scheduling (e.g., listing \ref{lst:nest-ext}) may now require additional searches for the \code{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.
    18271886
    18281887\begin{figure}
    1829 \begin{cfacode}[caption={Example of nested external scheduling},label={lst:nest-ext}]
     1888\begin{cfa}[caption={Example of nested external scheduling},label={lst:nest-ext}]
    18301889monitor M {};
    18311890void foo( M & mutex a ) {}
    18321891void bar( M & mutex b ) {
    1833         //Nested in the waitfor(bar, c) call
     1892        // Nested in the waitfor(bar, c) call
    18341893        waitfor(foo, b);
    18351894}
     
    18381897}
    18391898
    1840 \end{cfacode}
     1899\end{cfa}
    18411900\end{figure}
    18421901
     
    18581917External scheduling, like internal scheduling, becomes significantly more complex when introducing multi-monitor syntax.
    18591918Even in the simplest possible case, some new semantics needs to be established:
    1860 \begin{cfacode}
     1919\begin{cfa}
    18611920monitor M {};
    18621921
     
    18641923
    18651924void g(M & mutex b, M & mutex c) {
    1866         waitfor(f); //two monitors M => unknown which to pass to f(M & mutex)
    1867 }
    1868 \end{cfacode}
     1925        waitfor(f); // two monitors M => unknown which to pass to f(M & mutex)
     1926}
     1927\end{cfa}
    18691928The obvious solution is to specify the correct monitor as follows:
    18701929
    1871 \begin{cfacode}
     1930\begin{cfa}
    18721931monitor M {};
    18731932
     
    18751934
    18761935void g(M & mutex a, M & mutex b) {
    1877         //wait for call to f with argument b
     1936        // wait for call to f with argument b
    18781937        waitfor(f, b);
    18791938}
    1880 \end{cfacode}
     1939\end{cfa}
    18811940This syntax is unambiguous.
    1882 Both locks are acquired and kept by \code{g}.
    1883 When routine \code{f} is called, the lock for monitor \code{b} is temporarily transferred from \code{g} to \code{f} (while \code{g} still holds lock \code{a}).
    1884 This behaviour can be extended to the multi-monitor \code{waitfor} statement as follows.
    1885 
    1886 \begin{cfacode}
     1941Both locks are acquired and kept by @g@.
     1942When routine @f@ is called, the lock for monitor @b@ is temporarily transferred from @g@ to @f@ (while @g@ still holds lock @a@).
     1943This behaviour can be extended to the multi-monitor @waitfor@ statement as follows.
     1944
     1945\begin{cfa}
    18871946monitor M {};
    18881947
     
    18901949
    18911950void g(M & mutex a, M & mutex b) {
    1892         //wait for call to f with arguments a and b
     1951        // wait for call to f with arguments a and b
    18931952        waitfor(f, a, b);
    18941953}
    1895 \end{cfacode}
    1896 
    1897 Note that the set of monitors passed to the \code{waitfor} statement must be entirely contained in the set of monitors already acquired in the routine. \code{waitfor} used in any other context is undefined behaviour.
     1954\end{cfa}
     1955
     1956Note that the set of monitors passed to the @waitfor@ statement must be entirely contained in the set of monitors already acquired in the routine. @waitfor@ used in any other context is undefined behaviour.
    18981957
    18991958An important behaviour to note is when a set of monitors only match partially:
    19001959
    1901 \begin{cfacode}
     1960\begin{cfa}
    19021961mutex struct A {};
    19031962
     
    19121971
    19131972void foo() {
    1914         g(a1, b); //block on accept
     1973        g(a1, b); // block on accept
    19151974}
    19161975
    19171976void bar() {
    1918         f(a2, b); //fulfill cooperation
    1919 }
    1920 \end{cfacode}
     1977        f(a2, b); // fulfill cooperation
     1978}
     1979\end{cfa}
    19211980While the equivalent can happen when using internal scheduling, the fact that conditions are specific to a set of monitors means that users have to use two different condition variables.
    19221981In both cases, partially matching monitor sets does not wakeup the waiting thread.
    1923 It is also important to note that in the case of external scheduling the order of parameters is irrelevant; \code{waitfor(f,a,b)} and \code{waitfor(f,b,a)} are indistinguishable waiting condition.
    1924 
    1925 % ======================================================================
    1926 % ======================================================================
    1927 \subsection{\code{waitfor} Semantics}
    1928 % ======================================================================
    1929 % ======================================================================
    1930 
    1931 Syntactically, the \code{waitfor} statement takes a function identifier and a set of monitors.
    1932 While 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 \code{waitfor} statement.
     1982It is also important to note that in the case of external scheduling the order of parameters is irrelevant; @waitfor(f,a,b)@ and @waitfor(f,b,a)@ are indistinguishable waiting condition.
     1983
     1984% ======================================================================
     1985% ======================================================================
     1986\subsection{\protect\lstinline|waitfor| Semantics}
     1987% ======================================================================
     1988% ======================================================================
     1989
     1990Syntactically, the @waitfor@ statement takes a function identifier and a set of monitors.
     1991While 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.
    19331992It checks that the set of monitors passed in matches the requirements for a function call.
    19341993Listing \ref{lst:waitfor} shows various usages of the waitfor statement and which are acceptable.
    1935 The choice of the function type is made ignoring any non-\code{mutex} parameter.
     1994The choice of the function type is made ignoring any non-@mutex@ parameter.
    19361995One limitation of the current implementation is that it does not handle overloading, but overloading is possible.
    19371996\begin{figure}
    1938 \begin{cfacode}[caption={Various correct and incorrect uses of the waitfor statement},label={lst:waitfor}]
     1997\begin{cfa}[caption={Various correct and incorrect uses of the waitfor statement},label={lst:waitfor}]
    19391998monitor A{};
    19401999monitor B{};
     
    19502009        void (*fp)( A & mutex ) = f1;
    19512010
    1952         waitfor(f1, a1);     //Correct : 1 monitor case
    1953         waitfor(f2, a1, b1); //Correct : 2 monitor case
    1954         waitfor(f3, a1);     //Correct : non-mutex arguments are ignored
    1955         waitfor(f1, *ap);    //Correct : expression as argument
    1956 
    1957         waitfor(f1, a1, b1); //Incorrect : Too many mutex arguments
    1958         waitfor(f2, a1);     //Incorrect : Too few mutex arguments
    1959         waitfor(f2, a1, a2); //Incorrect : Mutex arguments don't match
    1960         waitfor(f1, 1);      //Incorrect : 1 not a mutex argument
    1961         waitfor(f9, a1);     //Incorrect : f9 function does not exist
    1962         waitfor(*fp, a1 );   //Incorrect : fp not an identifier
    1963         waitfor(f4, a1);     //Incorrect : f4 ambiguous
    1964 
    1965         waitfor(f2, a1, b2); //Undefined behaviour : b2 not mutex
    1966 }
    1967 \end{cfacode}
     2011        waitfor(f1, a1);     // Correct : 1 monitor case
     2012        waitfor(f2, a1, b1); // Correct : 2 monitor case
     2013        waitfor(f3, a1);     // Correct : non-mutex arguments are ignored
     2014        waitfor(f1, *ap);    // Correct : expression as argument
     2015
     2016        waitfor(f1, a1, b1); // Incorrect : Too many mutex arguments
     2017        waitfor(f2, a1);     // Incorrect : Too few mutex arguments
     2018        waitfor(f2, a1, a2); // Incorrect : Mutex arguments don't match
     2019        waitfor(f1, 1);      // Incorrect : 1 not a mutex argument
     2020        waitfor(f9, a1);     // Incorrect : f9 function does not exist
     2021        waitfor(*fp, a1 );   // Incorrect : fp not an identifier
     2022        waitfor(f4, a1);     // Incorrect : f4 ambiguous
     2023
     2024        waitfor(f2, a1, b2); // Undefined behaviour : b2 not mutex
     2025}
     2026\end{cfa}
    19682027\end{figure}
    19692028
    1970 Finally, for added flexibility, \CFA supports constructing a complex \code{waitfor} statement using the \code{or}, \code{timeout} and \code{else}.
    1971 Indeed, multiple \code{waitfor} clauses can be chained together using \code{or}; this chain forms a single statement that uses baton pass to any function that fits one of the function+monitor set passed in.
    1972 To enable users to tell which accepted function executed, \code{waitfor}s are followed by a statement (including the null statement \code{;}) or a compound statement, which is executed after the clause is triggered.
    1973 A \code{waitfor} chain can also be followed by a \code{timeout}, to signify an upper bound on the wait, or an \code{else}, to signify that the call should be non-blocking, which checks for a matching function call already arrived and otherwise continues.
    1974 Any and all of these clauses can be preceded by a \code{when} condition to dynamically toggle the accept clauses on or off based on some current state.
     2029Finally, for added flexibility, \CFA supports constructing a complex @waitfor@ statement using the @or@, @timeout@ and @else@.
     2030Indeed, multiple @waitfor@ clauses can be chained together using @or@; this chain forms a single statement that uses baton pass to any function that fits one of the function+monitor set passed in.
     2031To enable users to tell which accepted function executed, @waitfor@s are followed by a statement (including the null statement @;@) or a compound statement, which is executed after the clause is triggered.
     2032A @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.
     2033Any 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.
    19752034Listing \ref{lst:waitfor2} demonstrates several complex masks and some incorrect ones.
    19762035
    19772036\begin{figure}
    1978 \begin{cfacode}[caption={Various correct and incorrect uses of the or, else, and timeout clause around a waitfor statement},label={lst:waitfor2}]
     2037\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
     2038\begin{cfa}
    19792039monitor A{};
    19802040
     
    19832043
    19842044void foo( A & mutex a, bool b, int t ) {
    1985         //Correct : blocking case
    1986         waitfor(f1, a);
    1987 
    1988         //Correct : block with statement
    1989         waitfor(f1, a) {
     2045        waitfor(f1, a);                                                 $\C{// Correct : blocking case}$
     2046
     2047        waitfor(f1, a) {                                                $\C{// Correct : block with statement}$
    19902048                sout | "f1" | endl;
    19912049        }
    1992 
    1993         //Correct : block waiting for f1 or f2
    1994         waitfor(f1, a) {
     2050        waitfor(f1, a) {                                                $\C{// Correct : block waiting for f1 or f2}$
    19952051                sout | "f1" | endl;
    19962052        } or waitfor(f2, a) {
    19972053                sout | "f2" | endl;
    19982054        }
    1999 
    2000         //Correct : non-blocking case
    2001         waitfor(f1, a); or else;
    2002 
    2003         //Correct : non-blocking case
    2004         waitfor(f1, a) {
     2055        waitfor(f1, a); or else;                                $\C{// Correct : non-blocking case}$
     2056
     2057        waitfor(f1, a) {                                                $\C{// Correct : non-blocking case}$
    20052058                sout | "blocked" | endl;
    20062059        } or else {
    20072060                sout | "didn't block" | endl;
    20082061        }
    2009 
    2010         //Correct : block at most 10 seconds
    2011         waitfor(f1, a) {
     2062        waitfor(f1, a) {                                                $\C{// Correct : block at most 10 seconds}$
    20122063                sout | "blocked" | endl;
    20132064        } or timeout( 10`s) {
    20142065                sout | "didn't block" | endl;
    20152066        }
    2016 
    2017         //Correct : block only if b == true
    2018         //if b == false, don't even make the call
     2067        // Correct : block only if b == true if b == false, don't even make the call
    20192068        when(b) waitfor(f1, a);
    20202069
    2021         //Correct : block only if b == true
    2022         //if b == false, make non-blocking call
     2070        // Correct : block only if b == true if b == false, make non-blocking call
    20232071        waitfor(f1, a); or when(!b) else;
    20242072
    2025         //Correct : block only of t > 1
     2073        // Correct : block only of t > 1
    20262074        waitfor(f1, a); or when(t > 1) timeout(t); or else;
    20272075
    2028         //Incorrect : timeout clause is dead code
     2076        // Incorrect : timeout clause is dead code
    20292077        waitfor(f1, a); or timeout(t); or else;
    20302078
    2031         //Incorrect : order must be
    2032         //waitfor [or waitfor... [or timeout] [or else]]
     2079        // Incorrect : order must be waitfor [or waitfor... [or timeout] [or else]]
    20332080        timeout(t); or waitfor(f1, a); or else;
    20342081}
    2035 \end{cfacode}
     2082\end{cfa}
     2083\caption{Correct and incorrect uses of the or, else, and timeout clause around a waitfor statement}
     2084\label{lst:waitfor2}
    20362085\end{figure}
    20372086
     
    20412090% ======================================================================
    20422091% ======================================================================
    2043 An interesting use for the \code{waitfor} statement is destructor semantics.
    2044 Indeed, the \code{waitfor} statement can accept any \code{mutex} routine, which includes the destructor (see section \ref{data}).
     2092An interesting use for the @waitfor@ statement is destructor semantics.
     2093Indeed, the @waitfor@ statement can accept any @mutex@ routine, which includes the destructor (see section \ref{data}).
    20452094However, with the semantics discussed until now, waiting for the destructor does not make any sense, since using an object after its destructor is called is undefined behaviour.
    2046 The simplest approach is to disallow \code{waitfor} on a destructor.
    2047 However, 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 \code{mutex} routine, similarly to how a condition is signalled.
     2095The simplest approach is to disallow @waitfor@ on a destructor.
     2096However, 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.
    20482097\begin{figure}
    2049 \begin{cfacode}[caption={Example of an executor which executes action in series until the destructor is called.},label={lst:dtor-order}]
     2098\begin{cfa}[caption={Example of an executor which executes action in series until the destructor is called.},label={lst:dtor-order}]
    20502099monitor Executer {};
    20512100struct  Action;
     
    20612110        }
    20622111}
    2063 \end{cfacode}
     2112\end{cfa}
    20642113\end{figure}
    20652114For 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.
     
    20792128In this decade, it is no longer reasonable to create a high-performance application without caring about parallelism.
    20802129Indeed, parallelism is an important aspect of performance and more specifically throughput and hardware utilization.
    2081 The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like \code{fork}, \code{join}, etc.
     2130The lowest-level approach of parallelism is to use \textbf{kthread} in combination with semantics like @fork@, @join@, etc.
    20822131However, since these have significant costs and limitations, \textbf{kthread} are now mostly used as an implementation tool rather than a user oriented one.
    20832132There are several alternatives to solve these issues that all have strengths and weaknesses.
     
    21582207Conveniently, the call stack fits that description and is easy to use, which is why it is used heavily in the implementation of internal scheduling, particularly variable-length arrays.
    21592208Since stack allocation is based on scopes, the first step of the implementation is to identify the scopes that are available to store the information, and which of these can have a variable-length array.
    2160 The threads and the condition both have a fixed amount of memory, while \code{mutex} routines and blocking calls allow for an unbound amount, within the stack size.
     2209The threads and the condition both have a fixed amount of memory, while @mutex@ routines and blocking calls allow for an unbound amount, within the stack size.
    21612210
    21622211Note that since the major contributions of this paper are extending monitor semantics to \textbf{bulk-acq} and loose object definitions, any challenges that are not resulting of these characteristics of \CFA are considered as solved problems and therefore not discussed.
     
    21682217% ======================================================================
    21692218
    2170 The first step towards the monitor implementation is simple \code{mutex} routines.
     2219The first step towards the monitor implementation is simple @mutex@ routines.
    21712220In the single monitor case, mutual-exclusion is done using the entry/exit procedure in listing \ref{lst:entry1}.
    21722221The entry/exit procedures do not have to be extended to support multiple monitors.
     
    21792228\begin{multicols}{2}
    21802229Entry
    2181 \begin{pseudo}
     2230\begin{cfa}
    21822231if monitor is free
    21832232        enter
     
    21872236        block
    21882237increment recursions
    2189 \end{pseudo}
     2238\end{cfa}
    21902239\columnbreak
    21912240Exit
    2192 \begin{pseudo}
     2241\begin{cfa}
    21932242decrement recursion
    21942243if recursion == 0
    21952244        if entry queue not empty
    21962245                wake-up thread
    2197 \end{pseudo}
     2246\end{cfa}
    21982247\end{multicols}
    2199 \begin{pseudo}[caption={Initial entry and exit routine for monitors},label={lst:entry1}]
    2200 \end{pseudo}
     2248\begin{cfa}[caption={Initial entry and exit routine for monitors},label={lst:entry1}]
     2249\end{cfa}
    22012250\end{figure}
    22022251
     
    22052254However, it is shown that entry-point locking solves most of the issues.
    22062255
    2207 First of all, interaction between \code{otype} polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
    2208 Therefore, the main question is how to support \code{dtype} polymorphism.
     2256First of all, interaction between @otype@ polymorphism (see Section~\ref{s:ParametricPolymorphism}) and monitors is impossible since monitors do not support copying.
     2257Therefore, the main question is how to support @dtype@ polymorphism.
    22092258It 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.
    22102259For example:
    2211 \begin{table}[H]
     2260\begin{table}
    22122261\begin{center}
    22132262\begin{tabular}{|c|c|c|}
    22142263Mutex & \textbf{callsite-locking} & \textbf{entry-point-locking} \\
    2215 call & pseudo-code & pseudo-code \\
     2264call & cfa-code & cfa-code \\
    22162265\hline
    2217 \begin{cfacode}[tabsize=3]
     2266\begin{cfa}[tabsize=3]
    22182267void foo(monitor& mutex a){
    22192268
    2220         //Do Work
     2269        // Do Work
    22212270        //...
    22222271
     
    22292278
    22302279}
    2231 \end{cfacode} & \begin{pseudo}[tabsize=3]
     2280\end{cfa} & \begin{cfa}[tabsize=3]
    22322281foo(& a) {
    22332282
    2234         //Do Work
     2283        // Do Work
    22352284        //...
    22362285
     
    22432292        release(a);
    22442293}
    2245 \end{pseudo} & \begin{pseudo}[tabsize=3]
     2294\end{cfa} & \begin{cfa}[tabsize=3]
    22462295foo(& a) {
    22472296        acquire(a);
    2248         //Do Work
     2297        // Do Work
    22492298        //...
    22502299        release(a);
     
    22572306
    22582307}
    2259 \end{pseudo}
     2308\end{cfa}
    22602309\end{tabular}
    22612310\end{center}
     
    22642313\end{table}
    22652314
    2266 Note the \code{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.:
    2267 \begin{cfacode}
    2268 //Incorrect: T may not be monitor
     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.:
     2316\begin{cfa}
     2317// Incorrect: T may not be monitor
    22692318forall(dtype T)
    22702319void foo(T * mutex t);
    22712320
    2272 //Correct: this function only works on monitors (any monitor)
     2321// Correct: this function only works on monitors (any monitor)
    22732322forall(dtype T | is_monitor(T))
    22742323void bar(T * mutex t));
    2275 \end{cfacode}
     2324\end{cfa}
    22762325
    22772326Both entry point and \textbf{callsite-locking} are feasible implementations.
     
    22992348
    23002349\subsection{Processors}
    2301 Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically \texttt{pthread}s in the current implementation of \CFA.
     2350Parallelism in \CFA is built around using processors to specify how much parallelism is desired. \CFA processors are object wrappers around kernel threads, specifically @pthread@s in the current implementation of \CFA.
    23022351Indeed, any parallelism must go through operating-system libraries.
    23032352However, \textbf{uthread} are still the main source of concurrency, processors are simply the underlying source of parallelism.
     
    23082357\subsection{Stack Management}
    23092358One of the challenges of this system is to reduce the footprint as much as possible.
    2310 Specifically, all \texttt{pthread}s created also have a stack created with them, which should be used as much as possible.
     2359Specifically, all @pthread@s created also have a stack created with them, which should be used as much as possible.
    23112360Normally, 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.
    23122361The exception to this rule is the Main Processor, i.e., the initial \textbf{kthread} that is given to any program.
     
    23232372Obviously, this doubles the context-switch cost because threads must context-switch to an intermediate stack.
    23242373The alternative 1-step context-switch uses the stack of the ``from'' thread to schedule and then context-switches directly to the ``to'' thread.
    2325 However, the performance of the 2-step context-switch is still superior to a \code{pthread_yield} (see section \ref{results}).
    2326 Additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch (akin to the Microsoft \code{SwitchToFiber}~\cite{switchToWindows} routine).
     2374However, the performance of the 2-step context-switch is still superior to a @pthread_yield@ (see section \ref{results}).
     2375Additionally, for users in need for optimal performance, it is important to note that having a 2-step context-switch as the default does not prevent \CFA from offering a 1-step context-switch (akin to the Microsoft @SwitchToFiber@~\cite{switchToWindows} routine).
    23272376This option is not currently present in \CFA, but the changes required to add it are strictly additive.
    23282377
     
    23562405This behaviour is only a problem if all kernel threads, among which a user thread can migrate, differ in terms of signal masks\footnote{Sadly, official POSIX documentation is silent on what distinguishes ``async-signal-safe'' functions from other functions.}.
    23572406However, since the kernel thread handling preemption requires a different signal mask, executing user threads on the kernel-alarm thread can cause deadlocks.
    2358 For this reason, the alarm thread is in a tight loop around a system call to \code{sigwaitinfo}, requiring very little CPU time for preemption.
     2407For this reason, the alarm thread is in a tight loop around a system call to @sigwaitinfo@, requiring very little CPU time for preemption.
    23592408One final detail about the alarm thread is how to wake it when additional communication is required (e.g., on thread termination).
    2360 This unblocking is also done using {\tt SIGALRM}, but sent through the \code{pthread_sigqueue}.
    2361 Indeed, \code{sigwait} can differentiate signals sent from \code{pthread_sigqueue} from signals sent from alarms or the kernel.
     2409This unblocking is also done using {\tt SIGALRM}, but sent through the @pthread_sigqueue@.
     2410Indeed, @sigwait@ can differentiate signals sent from @pthread_sigqueue@ from signals sent from alarms or the kernel.
    23622411
    23632412\subsection{Scheduler}
     
    23732422The following figure is the traditional illustration of a monitor (repeated from page~\pageref{fig:ClassicalMonitor} for convenience):
    23742423
    2375 \begin{figure}[H]
     2424\begin{figure}
    23762425\begin{center}
    23772426{\resizebox{0.4\textwidth}{!}{\input{monitor}}}
     
    23882437Secondly, the thread waiting on the condition has to be separated across multiple monitors, seen in figure \ref{fig:monitor_cfa}.
    23892438
    2390 \begin{figure}[H]
     2439\begin{figure}
    23912440\begin{center}
    23922441{\resizebox{0.8\textwidth}{!}{\input{int_monitor}}}
     
    24022451For a specific signalling operation every monitor needs a piece of thread on its AS-stack.
    24032452
    2404 \begin{figure}[b]
     2453\begin{figure}
    24052454\begin{multicols}{2}
    24062455Entry
    2407 \begin{pseudo}
     2456\begin{cfa}
    24082457if monitor is free
    24092458        enter
     
    24142463increment recursion
    24152464
    2416 \end{pseudo}
     2465\end{cfa}
    24172466\columnbreak
    24182467Exit
    2419 \begin{pseudo}
     2468\begin{cfa}
    24202469decrement recursion
    24212470if recursion == 0
     
    24272476        if entry queue not empty
    24282477                wake-up thread
    2429 \end{pseudo}
     2478\end{cfa}
    24302479\end{multicols}
    2431 \begin{pseudo}[caption={Entry and exit routine for monitors with internal scheduling},label={lst:entry2}]
    2432 \end{pseudo}
     2480\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling},label={lst:entry2}]
     2481\end{cfa}
    24332482\end{figure}
    24342483
     
    24362485Basically, 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.
    24372486This solution is deadlock safe as well as preventing any potential barging.
    2438 The data structures used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the call stack of the \code{wait} and \code{signal_block} routines.
    2439 
    2440 \begin{figure}[H]
     2487The data structures used for the AS-stack are reused extensively for external scheduling, but in the case of internal scheduling, the data is allocated using variable-length arrays on the call stack of the @wait@ and @signal_block@ routines.
     2488
     2489\begin{figure}
    24412490\begin{center}
    24422491{\resizebox{0.8\textwidth}{!}{\input{monitor_structs.pstex_t}}}
     
    24482497Figure \ref{fig:structs} shows a high-level representation of these data structures.
    24492498The main idea behind them is that, a thread cannot contain an arbitrary number of intrusive ``next'' pointers for linking onto monitors.
    2450 The \code{condition node} is the data structure that is queued onto a condition variable and, when signalled, the condition queue is popped and each \code{condition criterion} is moved to the AS-stack.
     2499The @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.
    24512500Once 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}.
    24522501
     
    24582507Similarly 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}.
    24592508For 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).
    2460 However, in the case of external scheduling, there is no equivalent object which is associated with \code{waitfor} statements.
     2509However, in the case of external scheduling, there is no equivalent object which is associated with @waitfor@ statements.
    24612510This absence means the queues holding the waiting threads must be stored inside at least one of the monitors that is acquired.
    2462 These monitors being the only objects that have sufficient lifetime and are available on both sides of the \code{waitfor} statement.
     2511These monitors being the only objects that have sufficient lifetime and are available on both sides of the @waitfor@ statement.
    24632512This requires an algorithm to choose which monitor holds the relevant queue.
    24642513It is also important that said algorithm be independent of the order in which users list parameters.
     
    24772526\begin{itemize}
    24782527        \item The threads waiting on the entry queue need to keep track of which routine they are trying to enter, and using which set of monitors.
    2479 The \code{mutex} routine already has all the required information on its stack, so the thread only needs to keep a pointer to that information.
     2528The @mutex@ routine already has all the required information on its stack, so the thread only needs to keep a pointer to that information.
    24802529        \item The monitors need to keep a mask of acceptable routines.
    24812530This mask contains for each acceptable routine, a routine pointer and an array of monitors to go with it.
    24822531It also needs storage to keep track of which routine was accepted.
    24832532Since this information is not specific to any monitor, the monitors actually contain a pointer to an integer on the stack of the waiting thread.
    2484 Note that if a thread has acquired two monitors but executes a \code{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.
    2485 This becomes relevant when \code{when} clauses affect the number of monitors passed to a \code{waitfor} statement.
     2533Note 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.
     2534This becomes relevant when @when@ clauses affect the number of monitors passed to a @waitfor@ statement.
    24862535        \item The entry/exit routines need to be updated as shown in listing \ref{lst:entry3}.
    24872536\end{itemize}
     
    24912540This routine is needed because of the storage requirements of the call order inversion.
    24922541Indeed, 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.
    2493 For regular \code{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.
    2494 The \code{waitfor} semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
     2542For 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.
     2543The @waitfor@ semantics can then be adjusted correspondingly, as seen in listing \ref{lst:entry-dtor}
    24952544
    24962545\begin{figure}
    24972546\begin{multicols}{2}
    24982547Entry
    2499 \begin{pseudo}
     2548\begin{cfa}
    25002549if monitor is free
    25012550        enter
     
    25082557        block
    25092558increment recursion
    2510 \end{pseudo}
     2559\end{cfa}
    25112560\columnbreak
    25122561Exit
    2513 \begin{pseudo}
     2562\begin{cfa}
    25142563decrement recursion
    25152564if recursion == 0
     
    25242573                wake-up thread
    25252574        endif
    2526 \end{pseudo}
     2575\end{cfa}
    25272576\end{multicols}
    2528 \begin{pseudo}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={lst:entry3}]
    2529 \end{pseudo}
     2577\begin{cfa}[caption={Entry and exit routine for monitors with internal scheduling and external scheduling},label={lst:entry3}]
     2578\end{cfa}
    25302579\end{figure}
    25312580
     
    25332582\begin{multicols}{2}
    25342583Destructor Entry
    2535 \begin{pseudo}
     2584\begin{cfa}
    25362585if monitor is free
    25372586        enter
     
    25472596        wait
    25482597increment recursion
    2549 \end{pseudo}
     2598\end{cfa}
    25502599\columnbreak
    25512600Waitfor
    2552 \begin{pseudo}
     2601\begin{cfa}
    25532602if matching thread is already there
    25542603        if found destructor
     
    25702619block
    25712620return
    2572 \end{pseudo}
     2621\end{cfa}
    25732622\end{multicols}
    2574 \begin{pseudo}[caption={Pseudo code for the \code{waitfor} routine and the \code{mutex} entry routine for destructors},label={lst:entry-dtor}]
    2575 \end{pseudo}
     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}]
     2624\end{cfa}
    25762625\end{figure}
    25772626
     
    25852634
    25862635\section{Threads As Monitors}
    2587 As it was subtly alluded in section \ref{threads}, \code{thread}s in \CFA are in fact monitors, which means that all monitor features are available when using threads.
     2636As it was subtly alluded in section \ref{threads}, @thread@s in \CFA are in fact monitors, which means that all monitor features are available when using threads.
    25882637For example, here is a very simple two thread pipeline that could be used for a simulator of a game engine:
    2589 \begin{figure}[H]
    2590 \begin{cfacode}[caption={Toy simulator using \code{thread}s and \code{monitor}s.},label={lst:engine-v1}]
     2638\begin{figure}
     2639\begin{cfa}[caption={Toy simulator using \protect\lstinline|thread|s and \protect\lstinline|monitor|s.},label={lst:engine-v1}]
    25912640// Visualization declaration
    25922641thread Renderer {} renderer;
     
    26152664        }
    26162665}
    2617 \end{cfacode}
     2666\end{cfa}
    26182667\end{figure}
    26192668One of the obvious complaints of the previous code snippet (other than its toy-like simplicity) is that it does not handle exit conditions and just goes on forever.
    26202669Luckily, the monitor semantics can also be used to clearly enforce a shutdown order in a concise manner:
    2621 \begin{figure}[H]
    2622 \begin{cfacode}[caption={Same toy simulator with proper termination condition.},label={lst:engine-v2}]
     2670\begin{figure}
     2671\begin{cfa}[caption={Same toy simulator with proper termination condition.},label={lst:engine-v2}]
    26232672// Visualization declaration
    26242673thread Renderer {} renderer;
     
    26582707// Call destructor for simulator once simulator finishes
    26592708// Call destructor for renderer to signify shutdown
    2660 \end{cfacode}
     2709\end{cfa}
    26612710\end{figure}
    26622711
     
    26642713As mentioned in section \ref{preemption}, \CFA uses preemptive threads by default but can use fibers on demand.
    26652714Currently, using fibers is done by adding the following line of code to the program~:
    2666 \begin{cfacode}
     2715\begin{cfa}
    26672716unsigned int default_preemption() {
    26682717        return 0;
    26692718}
    2670 \end{cfacode}
     2719\end{cfa}
    26712720This function is called by the kernel to fetch the default preemption rate, where 0 signifies an infinite time-slice, i.e., no preemption.
    26722721However, 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}
    26732722\begin{figure}
    2674 \begin{cfacode}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={lst:fiber-uthread}]
    2675 //Cluster forward declaration
     2723\lstset{language=CFA,deletedelim=**[is][]{`}{`}}
     2724\begin{cfa}[caption={Using fibers and \textbf{uthread} side-by-side in \CFA},label={lst:fiber-uthread}]
     2725// Cluster forward declaration
    26762726struct cluster;
    26772727
    2678 //Processor forward declaration
     2728// Processor forward declaration
    26792729struct processor;
    26802730
    2681 //Construct clusters with a preemption rate
     2731// Construct clusters with a preemption rate
    26822732void ?{}(cluster& this, unsigned int rate);
    2683 //Construct processor and add it to cluster
     2733// Construct processor and add it to cluster
    26842734void ?{}(processor& this, cluster& cluster);
    2685 //Construct thread and schedule it on cluster
     2735// Construct thread and schedule it on cluster
    26862736void ?{}(thread& this, cluster& cluster);
    26872737
    2688 //Declare two clusters
    2689 cluster thread_cluster = { 10`ms };                     //Preempt every 10 ms
    2690 cluster fibers_cluster = { 0 };                         //Never preempt
    2691 
    2692 //Construct 4 processors
     2738// Declare two clusters
     2739cluster thread_cluster = { 10`ms };                     // Preempt every 10 ms
     2740cluster fibers_cluster = { 0 };                         // Never preempt
     2741
     2742// Construct 4 processors
    26932743processor processors[4] = {
    26942744        //2 for the thread cluster
     
    27002750};
    27012751
    2702 //Declares thread
     2752// Declares thread
    27032753thread UThread {};
    27042754void ?{}(UThread& this) {
    2705         //Construct underlying thread to automatically
    2706         //be scheduled on the thread cluster
     2755        // Construct underlying thread to automatically
     2756        // be scheduled on the thread cluster
    27072757        (this){ thread_cluster }
    27082758}
     
    27102760void main(UThread & this);
    27112761
    2712 //Declares fibers
     2762// Declares fibers
    27132763thread Fiber {};
    27142764void ?{}(Fiber& this) {
    2715         //Construct underlying thread to automatically
    2716         //be scheduled on the fiber cluster
     2765        // Construct underlying thread to automatically
     2766        // be scheduled on the fiber cluster
    27172767        (this.__thread){ fibers_cluster }
    27182768}
    27192769
    27202770void main(Fiber & this);
    2721 \end{cfacode}
     2771\end{cfa}
    27222772\end{figure}
    27232773
     
    27312781Table \ref{tab:machine} shows the characteristics of the machine used to run the benchmarks.
    27322782All tests were made on this machine.
    2733 \begin{table}[H]
     2783\begin{table}
    27342784\begin{center}
    27352785\begin{tabular}{| l | r | l | r |}
     
    27632813
    27642814\section{Micro Benchmarks}
    2765 All benchmarks are run using the same harness to produce the results, seen as the \code{BENCH()} macro in the following examples.
     2815All benchmarks are run using the same harness to produce the results, seen as the @BENCH()@ macro in the following examples.
    27662816This macro uses the following logic to benchmark the code:
    2767 \begin{pseudo}
     2817\begin{cfa}
    27682818#define BENCH(run, result) \
    27692819        before = gettime(); \
     
    27712821        after  = gettime(); \
    27722822        result = (after - before) / N;
    2773 \end{pseudo}
    2774 The method used to get time is \code{clock_gettime(CLOCK_THREAD_CPUTIME_ID);}.
     2823\end{cfa}
     2824The method used to get time is @clock_gettime(CLOCK_THREAD_CPUTIME_ID);@.
    27752825Each benchmark is using many iterations of a simple call to measure the cost of the call.
    27762826The specific number of iterations depends on the specific benchmark.
     
    27872837\begin{multicols}{2}
    27882838\CFA Coroutines
    2789 \begin{cfacode}
     2839\begin{cfa}
    27902840coroutine GreatSuspender {};
    27912841void main(GreatSuspender& this) {
     
    28032853        printf("%llu\n", result);
    28042854}
    2805 \end{cfacode}
     2855\end{cfa}
    28062856\columnbreak
    28072857\CFA Threads
    2808 \begin{cfacode}
     2858\begin{cfa}
    28092859
    28102860
     
    28222872        printf("%llu\n", result);
    28232873}
    2824 \end{cfacode}
     2874\end{cfa}
    28252875\end{multicols}
    2826 \begin{cfacode}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={lst:ctx-switch}]
    2827 \end{cfacode}
     2876\begin{cfa}[caption={\CFA benchmark code used to measure context-switches for coroutines and threads.},label={lst:ctx-switch}]
     2877\end{cfa}
    28282878\end{figure}
    28292879
     
    28532903For monitors, the simplest approach is to measure how long it takes to enter and leave a monitor routine.
    28542904Listing \ref{lst:mutex} shows the code for \CFA.
    2855 To put the results in context, the cost of entering a non-inline function and the cost of acquiring and releasing a \code{pthread_mutex} lock is also measured.
     2905To 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.
    28562906The results can be shown in table \ref{tab:mutex}.
    28572907
    28582908\begin{figure}
    2859 \begin{cfacode}[caption={\CFA benchmark code used to measure mutex routines.},label={lst:mutex}]
     2909\begin{cfa}[caption={\CFA benchmark code used to measure mutex routines.},label={lst:mutex}]
    28602910monitor M {};
    28612911void __attribute__((noinline)) call( M & mutex m /*, m2, m3, m4*/ ) {}
     
    28712921        printf("%llu\n", result);
    28722922}
    2873 \end{cfacode}
     2923\end{cfa}
    28742924\end{figure}
    28752925
     
    28832933FetchAdd + FetchSub                             & 26            & 26            & 0    \\
    28842934Pthreads Mutex Lock                             & 31            & 31.86 & 0.99 \\
    2885 \uC \code{monitor} member routine               & 30            & 30            & 0    \\
    2886 \CFA \code{mutex} routine, 1 argument   & 41            & 41.57 & 0.9  \\
    2887 \CFA \code{mutex} routine, 2 argument   & 76            & 76.96 & 1.57 \\
    2888 \CFA \code{mutex} routine, 4 argument   & 145           & 146.68        & 3.85 \\
     2935\uC @monitor@ member routine            & 30            & 30            & 0    \\
     2936\CFA @mutex@ routine, 1 argument        & 41            & 41.57 & 0.9  \\
     2937\CFA @mutex@ routine, 2 argument        & 76            & 76.96 & 1.57 \\
     2938\CFA @mutex@ routine, 4 argument        & 145           & 146.68        & 3.85 \\
    28892939Java synchronized routine                       & 27            & 28.57 & 2.6  \\
    28902940\hline
     
    29022952
    29032953\begin{figure}
    2904 \begin{cfacode}[caption={Benchmark code for internal scheduling},label={lst:int-sched}]
     2954\begin{cfa}[caption={Benchmark code for internal scheduling},label={lst:int-sched}]
    29052955volatile int go = 0;
    29062956condition c;
     
    29322982        return do_wait(m1);
    29332983}
    2934 \end{cfacode}
     2984\end{cfa}
    29352985\end{figure}
    29362986
     
    29422992\hline
    29432993Pthreads Condition Variable                     & 5902.5        & 6093.29       & 714.78 \\
    2944 \uC \code{signal}                                       & 322           & 323   & 3.36   \\
    2945 \CFA \code{signal}, 1 \code{monitor}    & 352.5 & 353.11        & 3.66   \\
    2946 \CFA \code{signal}, 2 \code{monitor}    & 430           & 430.29        & 8.97   \\
    2947 \CFA \code{signal}, 4 \code{monitor}    & 594.5 & 606.57        & 18.33  \\
    2948 Java \code{notify}                              & 13831.5       & 15698.21      & 4782.3 \\
     2994\uC @signal@                                    & 322           & 323   & 3.36   \\
     2995\CFA @signal@, 1 @monitor@      & 352.5 & 353.11        & 3.66   \\
     2996\CFA @signal@, 2 @monitor@      & 430           & 430.29        & 8.97   \\
     2997\CFA @signal@, 4 @monitor@      & 594.5 & 606.57        & 18.33  \\
     2998Java @notify@                           & 13831.5       & 15698.21      & 4782.3 \\
    29492999\hline
    29503000\end{tabular}
     
    29563006
    29573007\subsection{External Scheduling}
    2958 The Internal scheduling benchmark measures the cost of the \code{waitfor} statement (\code{_Accept} in \uC).
     3008The Internal scheduling benchmark measures the cost of the @waitfor@ statement (@_Accept@ in \uC).
    29593009Listing \ref{lst:ext-sched} shows the code for \CFA, with results in table \ref{tab:ext-sched}.
    29603010As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    29613011
    29623012\begin{figure}
    2963 \begin{cfacode}[caption={Benchmark code for external scheduling},label={lst:ext-sched}]
     3013\begin{cfa}[caption={Benchmark code for external scheduling},label={lst:ext-sched}]
    29643014volatile int go = 0;
    29653015monitor M {};
     
    29903040        return do_wait(m1);
    29913041}
    2992 \end{cfacode}
     3042\end{cfa}
    29933043\end{figure}
    29943044
     
    29993049\multicolumn{1}{c |}{} & \multicolumn{1}{c |}{ Median } &\multicolumn{1}{c |}{ Average } & \multicolumn{1}{c |}{ Standard Deviation} \\
    30003050\hline
    3001 \uC \code{Accept}                                       & 350           & 350.61        & 3.11  \\
    3002 \CFA \code{waitfor}, 1 \code{monitor}   & 358.5 & 358.36        & 3.82  \\
    3003 \CFA \code{waitfor}, 2 \code{monitor}   & 422           & 426.79        & 7.95  \\
    3004 \CFA \code{waitfor}, 4 \code{monitor}   & 579.5 & 585.46        & 11.25 \\
     3051\uC @Accept@                                    & 350           & 350.61        & 3.11  \\
     3052\CFA @waitfor@, 1 @monitor@     & 358.5 & 358.36        & 3.82  \\
     3053\CFA @waitfor@, 2 @monitor@     & 422           & 426.79        & 7.95  \\
     3054\CFA @waitfor@, 4 @monitor@     & 579.5 & 585.46        & 11.25 \\
    30053055\hline
    30063056\end{tabular}
     
    30133063\subsection{Object Creation}
    30143064Finally, the last benchmark measures the cost of creation for concurrent objects.
    3015 Listing \ref{lst:creation} shows the code for \texttt{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}.
    30163066As with all other benchmarks, all omitted tests are functionally identical to one of these tests.
    30173067The 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.
     
    30193069\begin{figure}
    30203070\begin{center}
    3021 \texttt{pthread}
    3022 \begin{ccode}
     3071@pthread@
     3072\begin{cfa}
    30233073int main() {
    30243074        BENCH(
     
    30393089        printf("%llu\n", result);
    30403090}
    3041 \end{ccode}
     3091\end{cfa}
    30423092
    30433093
    30443094
    30453095\CFA Threads
    3046 \begin{cfacode}
     3096\begin{cfa}
    30473097int main() {
    30483098        BENCH(
     
    30543104        printf("%llu\n", result);
    30553105}
    3056 \end{cfacode}
     3106\end{cfa}
    30573107\end{center}
    3058 \begin{cfacode}[caption={Benchmark code for \texttt{pthread}s and \CFA to measure object creation},label={lst:creation}]
    3059 \end{cfacode}
     3108\caption{Benchmark code for \protect\lstinline|pthread|s and \CFA to measure object creation}
     3109\label{lst:creation}
    30603110\end{figure}
    30613111
     
    31413191\begin{tabular}[t]{|c|c|c|}
    31423192Sequential & Library Parallel & Language Parallel \\
    3143 \begin{cfacode}[tabsize=3]
     3193\begin{cfa}[tabsize=3]
    31443194void big_sum(
    31453195        int* a, int* b,
     
    31653215//... fill in a & b
    31663216big_sum(a,b,c,10000);
    3167 \end{cfacode} &\begin{cfacode}[tabsize=3]
     3217\end{cfa} &\begin{cfa}[tabsize=3]
    31683218void big_sum(
    31693219        int* a, int* b,
     
    31893239//... fill in a & b
    31903240big_sum(a,b,c,10000);
    3191 \end{cfacode}&\begin{cfacode}[tabsize=3]
     3241\end{cfa}&\begin{cfa}[tabsize=3]
    31923242void big_sum(
    31933243        int* a, int* b,
     
    32133263//... fill in a & b
    32143264big_sum(a,b,c,10000);
    3215 \end{cfacode}
     3265\end{cfa}
    32163266\end{tabular}
    32173267\end{center}
  • doc/papers/concurrency/annex/local.bib

    ra9b1b0c rb5563e1  
    2121@string{pldi="Programming Language Design and Implementation"}
    2222
    23 
    24 @article{HPP:Study,
    25         keywords        = {Parallel, Productivity},
    26         author  = {Lorin Hochstein and Jeff Carver and Forrest Shull and Sima Asgari and Victor Basili and Jeffrey K. Hollingsworth and Marvin V. Zelkowitz },
    27         title   = {Parallel Programmer Productivity: A Case Study of Novice Parallel Programmers},
     23@inproceedings{Hochstein05,
     24    keywords    = {Application software; Computer aided software engineering; Concurrent computing; Educational
     25                  institutions; High performance computing; Humans; Instruments; Productivity; Programming profession;
     26                  Software engineering},
     27    author      = {Lorin Hochstein and Jeff Carver and Forrest Shull and Sima Asgari and Victor Basili and Jeffrey K. Hollingsworth and Marvin V. Zelkowitz},
     28    title       = {Parallel Programmer Productivity: A Case Study of Novice Parallel Programmers},
     29    booktitle   = {Supercomputing, 2005. Proceedings of the ACM/IEEE SC 2005 Conference},
     30    publisher   = {IEEE},
     31    year        = {2005},
     32    pages       = {35-35},
     33    month       = nov,
    2834}
    2935
     
    3541}
    3642
    37 @article{TBB,
    38         key     = {TBB},
    39         keywords        = {Intel, TBB},
    40         title   = {Intel Thread Building Blocks},
    41         note            = "\url{https://www.threadingbuildingblocks.org/}"
     43@misc{TBB,
     44    keywords    = {Intel, TBB},
     45    key         = {TBB},
     46    title       = {Thread Building Blocks},
     47    howpublished= {Intel, \url{https://www.threadingbuildingblocks.org}},
     48    note        = {Accessed: 2018-3},
    4249}
    4350
     
    4855        title   = {C$\forall$ Programmming Language},
    4956        note    = {\url{https://plg.uwaterloo.ca/~cforall}},
    50 }
    51 
    52 @mastersthesis{rob-thesis,
    53         keywords        = {Constructors, Destructors, Tuples},
    54         author  = {Rob Schluntz},
    55         title   = {Resource Management and Tuples in Cforall},
    56         year            = 2017,
    57         school  = {University of Waterloo},
    58         note    = {\url{https://uwspace.uwaterloo.ca/handle/10012/11830}},
    5957}
    6058
  • doc/papers/concurrency/style/cfa-format.tex

    ra9b1b0c rb5563e1  
    1111% from https://gist.github.com/nikolajquorning/92bbbeef32e1dd80105c9bf2daceb89a
    1212\lstdefinelanguage{sml} {
    13   morekeywords= {
    14     EQUAL, GREATER, LESS, NONE, SOME, abstraction, abstype, and, andalso, array, as, before, bool, case, char, datatype, do, else, end, eqtype, exception, exn, false, fn, fun, functor, handle, if, in, include, infix, infixr, int, let, list, local, nil, nonfix, not, o, of, op, open, option, orelse, overload, print, raise, real, rec, ref, sharing, sig, signature, string, struct, structure, substring, then, true, type, unit, val, vector, where, while, with, withtype, word
    15   },
    16   morestring=[b]",
    17   morecomment=[s]{(*}{*)},
     13        morekeywords= {
     14                EQUAL, GREATER, LESS, NONE, SOME, abstraction, abstype, and, andalso, array, as, before,
     15                bool, case, char, datatype, do, else, end, eqtype, exception, exn, false, fn, fun, functor,
     16                handle, if, in, include, infix, infixr, int, let, list, local, nil, nonfix, not, o, of, op,
     17                open, option, orelse, overload, print, raise, real, rec, ref, sharing, sig, signature,
     18                string, struct, structure, substring, then, true, type, unit, val, vector, where, while,
     19                with, withtype, word
     20    },
     21    morestring=[b]",
     22    morecomment=[s]{(*}{*)},
    1823}
    1924
    2025\lstdefinelanguage{D}{
    21   % Keywords
    22   morekeywords=[1]{
    23     abstract, alias, align, auto, body, break, cast, catch, class, const,
    24     continue, debug, delegate, delete, deprecated, do, else, enum, export,
    25     false, final, finally, for, foreach, foreach_reverse, function, goto, if,
    26     immutable, import, in, inout, interface, invariant, is, lazy, macro, mixin,
    27     module, new, nothrow, null, out, override, package, pragma, private,
    28     protected, public, pure, ref, return, shared, static, struct, super,
    29     switch, synchronized, template, this, throw, true, try, typedef, typeid,
    30     typeof, union, unittest, volatile, while, with
    31   },
    32   % Special identifiers, common functions
    33   morekeywords=[2]{enforce},
    34   % Ugly identifiers
    35   morekeywords=[3]{
    36     __DATE__, __EOF__, __FILE__, __LINE__, __TIMESTAMP__, __TIME__, __VENDOR__,
    37     __VERSION__, __ctfe, __gshared, __monitor, __thread, __vptr, _argptr,
    38     _arguments, _ctor, _dtor
    39   },
    40   % Basic types
    41   morekeywords=[4]{
    42      byte, ubyte, short, ushort, int, uint, long, ulong, cent, ucent, void,
    43      bool, bit, float, double, real, ushort, int, uint, long, ulong, float,
    44      char, wchar, dchar, string, wstring, dstring, ireal, ifloat, idouble,
    45      creal, cfloat, cdouble, size_t, ptrdiff_t, sizediff_t, equals_t, hash_t
    46   },
    47   % Strings
    48   morestring=[b]{"},
    49   morestring=[b]{'},
    50   morestring=[b]{`},
    51   % Comments
    52   comment=[l]{//},
    53   morecomment=[s]{/*}{*/},
    54   morecomment=[s][\color{blue}]{/**}{*/},
    55   morecomment=[n]{/+}{+/},
    56   morecomment=[n][\color{blue}]{/++}{+/},
    57   % Options
    58   sensitive=true
     26        % Keywords
     27        morekeywords=[1]{
     28                abstract, alias, align, auto, body, break, cast, catch, class, const, continue, debug,
     29                delegate, delete, deprecated, do, else, enum, export, false, final, finally, for, foreach,
     30                foreach_reverse, function, goto, if, immutable, import, in, inout, interface, invariant, is,
     31                lazy, macro, mixin, module, new, nothrow, null, out, override, package, pragma, private,
     32                protected, public, pure, ref, return, shared, static, struct, super, switch, synchronized,
     33                template, this, throw, true, try, typedef, typeid, typeof, union, unittest, volatile, while,
     34                with
     35        },
     36        % Special identifiers, common functions
     37        morekeywords=[2]{enforce},
     38        % Ugly identifiers
     39        morekeywords=[3]{
     40                __DATE__, __EOF__, __FILE__, __LINE__, __TIMESTAMP__, __TIME__, __VENDOR__,
     41                __VERSION__, __ctfe, __gshared, __monitor, __thread, __vptr, _argptr,
     42                _arguments, _ctor, _dtor
     43        },
     44        % Basic types
     45        morekeywords=[4]{
     46                byte, ubyte, short, ushort, int, uint, long, ulong, cent, ucent, void, bool, bit, float,
     47                double, real, ushort, int, uint, long, ulong, float, char, wchar, dchar, string, wstring,
     48                dstring, ireal, ifloat, idouble, creal, cfloat, cdouble, size_t, ptrdiff_t, sizediff_t,
     49                equals_t, hash_t
     50        },
     51        % Strings
     52        morestring=[b]{"},
     53        morestring=[b]{'},
     54        morestring=[b]{`},
     55        % Comments
     56        comment=[l]{//},
     57        morecomment=[s]{/*}{*/},
     58        morecomment=[s][\color{blue}]{/**}{*/},
     59        morecomment=[n]{/+}{+/},
     60        morecomment=[n][\color{blue}]{/++}{+/},
     61        % Options
     62        sensitive=true
    5963}
    6064
    6165\lstdefinelanguage{rust}{
    62   % Keywords
    63   morekeywords=[1]{
    64     abstract, alignof, as, become, box,
    65     break, const, continue, crate, do,
    66     else, enum, extern, false, final,
    67     fn, for, if, impl, in,
    68     let, loop, macro, match, mod,
    69     move, mut, offsetof, override, priv,
    70     proc, pub, pure, ref, return,
    71     Self, self, sizeof, static, struct,
    72     super, trait, true,  type, typeof,
    73     unsafe, unsized, use, virtual, where,
    74     while, yield
    75   },
    76   % Strings
    77   morestring=[b]{"},
    78   % Comments
    79   comment=[l]{//},
    80   morecomment=[s]{/*}{*/},
    81   % Options
    82   sensitive=true
     66        % Keywords
     67        morekeywords=[1]{
     68                abstract, alignof, as, become, box, break, const, continue, crate, do, else, enum, extern,
     69                false, final, fn, for, if, impl, in, let, loop, macro, match, mod, move, mut, offsetof,
     70                override, priv, proc, pub, pure, ref, return, Self, self, sizeof, static, struct, super,
     71                trait, true, type, typeof, unsafe, unsized, use, virtual, where, while, yield
     72        },
     73        % Strings
     74        morestring=[b]{"},
     75        % Comments
     76        comment=[l]{//},
     77        morecomment=[s]{/*}{*/},
     78        % Options
     79        sensitive=true
    8380}
    8481
    8582\lstdefinelanguage{pseudo}{
    86         morekeywords={string,uint,int,bool,float},%
    87         sensitive=true,%
    88         morecomment=[l]{//},%
    89         morecomment=[s]{/*}{*/},%
    90         morestring=[b]',%
    91         morestring=[b]",%
    92         morestring=[s]{`}{`},%
    93 }%
     83        morekeywords={string,uint,int,bool,float},
     84        sensitive=true,
     85        morecomment=[l]{//},
     86        morecomment=[s]{/*}{*/},
     87        morestring=[b]',
     88        morestring=[b]",
     89        morestring=[s]{`}{`},
     90}
    9491
    9592\newcommand{\KWC}{K-W C\xspace}
    9693
    9794\lstdefinestyle{pseudoStyle}{
    98   escapeinside={@@},
    99   basicstyle=\linespread{0.9}\sf\footnotesize,          % reduce line spacing and use typewriter font
    100   keywordstyle=\bfseries\color{blue},
    101   keywordstyle=[2]\bfseries\color{Plum},
    102   commentstyle=\itshape\color{OliveGreen},                  % green and italic comments
    103   identifierstyle=\color{identifierCol},
    104   stringstyle=\sf\color{Mahogany},                                % use sanserif font
    105   mathescape=true,
    106   columns=fixed,
    107   aboveskip=4pt,                                  % spacing above/below code block
    108   belowskip=3pt,
    109   keepspaces=true,
    110   tabsize=4,
    111   % frame=lines,
    112   literate=,
    113   showlines=true,                                % show blank lines at end of code
    114   showspaces=false,
    115   showstringspaces=false,
    116   escapechar=\$,
    117   xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    118   moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    119   % moredelim=* detects keywords, comments, strings, and other delimiters and applies their formatting
    120   % moredelim=** allows cumulative application
     95        escapeinside={@@},
     96        basicstyle=\linespread{0.9}\sf\footnotesize,            % reduce line spacing and use typewriter font
     97        keywordstyle=\bfseries\color{blue},
     98        keywordstyle=[2]\bfseries\color{Plum},
     99        commentstyle=\itshape\color{OliveGreen},                    % green and italic comments
     100        identifierstyle=\color{identifierCol},
     101        stringstyle=\sf\color{Mahogany},                                          % use sanserif font
     102        mathescape=true,
     103        columns=fixed,
     104        aboveskip=4pt,                                                            % spacing above/below code block
     105        belowskip=3pt,
     106        keepspaces=true,
     107        tabsize=4,
     108        % frame=lines,
     109        literate=,
     110        showlines=true,                                                          % show blank lines at end of code
     111        showspaces=false,
     112        showstringspaces=false,
     113        escapechar=\$,
     114        xleftmargin=\parindentlnth,                                  % indent code to paragraph indentation
     115        moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
     116        % moredelim=* detects keywords, comments, strings, and other delimiters and applies their formatting
     117        % moredelim=** allows cumulative application
    121118}
    122119
    123120\lstdefinestyle{defaultStyle}{
    124   escapeinside={@@},
    125   basicstyle=\linespread{0.9}\tt\footnotesize,          % reduce line spacing and use typewriter font
    126   keywordstyle=\bfseries\color{blue},
    127   keywordstyle=[2]\bfseries\color{Plum},
    128   commentstyle=\itshape\color{OliveGreen},                  % green and italic comments
    129   identifierstyle=\color{identifierCol},
    130   stringstyle=\sf\color{Mahogany},                                % use sanserif font
    131   mathescape=true,
    132   columns=fixed,
    133   aboveskip=4pt,                                  % spacing above/below code block
    134   belowskip=3pt,
    135   keepspaces=true,
    136   tabsize=4,
    137   % frame=lines,
    138   literate=,
    139   showlines=true,                                % show blank lines at end of code
    140   showspaces=false,
    141   showstringspaces=false,
    142   escapechar=\$,
    143   xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    144   moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    145   % moredelim=* detects keywords, comments, strings, and other delimiters and applies their formatting
    146   % moredelim=** allows cumulative application
     121        escapeinside={@@},
     122        basicstyle=\linespread{0.9}\tt\footnotesize,            % reduce line spacing and use typewriter font
     123        keywordstyle=\bfseries\color{blue},
     124        keywordstyle=[2]\bfseries\color{Plum},
     125        commentstyle=\itshape\color{OliveGreen},                    % green and italic comments
     126        identifierstyle=\color{identifierCol},
     127        stringstyle=\sf\color{Mahogany},                                          % use sanserif font
     128        mathescape=true,
     129        columns=fixed,
     130        aboveskip=4pt,                                                            % spacing above/below code block
     131        belowskip=3pt,
     132        keepspaces=true,
     133        tabsize=4,
     134        % frame=lines,
     135        literate=,
     136        showlines=true,                                                          % show blank lines at end of code
     137        showspaces=false,
     138        showstringspaces=false,
     139        escapechar=\$,
     140        xleftmargin=\parindentlnth,                                  % indent code to paragraph indentation
     141        moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
     142        % moredelim=* detects keywords, comments, strings, and other delimiters and applies their formatting
     143        % moredelim=** allows cumulative application
    147144}
    148145
    149146\lstdefinestyle{cfaStyle}{
    150   escapeinside={@@},
    151   basicstyle=\linespread{0.9}\sf,               % reduce line spacing and use typewriter font
     147        escapeinside={@@},
     148        basicstyle=\linespread{0.9}\sf,         % reduce line spacing and use typewriter font
    152149%  keywordstyle=\bfseries\color{blue},
    153   keywordstyle=[2]\bfseries\color{red},
     150        keywordstyle=[2]\bfseries\color{red},
    154151%  commentstyle=\sf\itshape\color{OliveGreen},            % green and italic comments
    155   identifierstyle=\color{identifierCol},
    156 %  stringstyle=\sf\color{Mahogany},                               % use sanserif font
    157   stringstyle=\tt,                                                                              % use typewriter font
    158   mathescape=true,
    159   columns=fixed,
    160   aboveskip=4pt,                                  % spacing above/below code block
    161   belowskip=3pt,
    162   keepspaces=true,
    163   tabsize=4,
    164   % frame=lines,
    165   literate=,
    166   showlines=true,                                % show blank lines at end of code
    167   showspaces=false,
    168   showstringspaces=false,
    169   escapechar=\$,
    170   xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    171   moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    172   morekeywords=[2]{accept, signal, signal_block, wait, waitfor},
     152        identifierstyle=\color{identifierCol},
     153%  stringstyle=\sf\color{Mahogany},                                       % use sanserif font
     154        stringstyle=\tt,                                                                                % use typewriter font
     155        mathescape=true,
     156        columns=fixed,
     157        aboveskip=4pt,                                                            % spacing above/below code block
     158        belowskip=3pt,
     159        keepspaces=true,
     160        tabsize=4,
     161        % frame=lines,
     162        literate=,
     163        showlines=true,                                                          % show blank lines at end of code
     164        showspaces=false,
     165        showstringspaces=false,
     166        escapechar=\$,
     167        xleftmargin=\parindentlnth,                                  % indent code to paragraph indentation
     168        moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
     169        morekeywords=[2]{accept, signal, signal_block, wait, waitfor},
    173170}
    174171
     
    176173
    177174\lstnewenvironment{ccode}[1][]{
    178   \lstset{
    179     language = C,
    180     style=defaultStyle,
    181     captionpos=b,
    182     #1
    183   }
     175        \lstset{
     176                language = C,
     177                style=defaultStyle,
     178                captionpos=b,
     179                #1
     180        }
    184181}{}
    185182
    186183\lstnewenvironment{cfacode}[1][]{
    187   \lstset{
    188     language = CFA,
    189     style=cfaStyle,
    190     captionpos=b,
    191     #1
    192   }
     184        \lstset{
     185                language = CFA,
     186                style=cfaStyle,
     187                captionpos=b,
     188                #1
     189        }
    193190}{}
    194191
    195192\lstnewenvironment{pseudo}[1][]{
    196   \lstset{
    197     language = pseudo,
    198     style=pseudoStyle,
    199     captionpos=b,
    200     #1
    201   }
     193        \lstset{
     194                language = pseudo,
     195                style=pseudoStyle,
     196                captionpos=b,
     197                #1
     198        }
    202199}{}
    203200
    204201\lstnewenvironment{cppcode}[1][]{
    205   \lstset{
    206     language = c++,
    207     style=defaultStyle,
    208     captionpos=b,
    209     #1
    210   }
     202        \lstset{
     203                language = c++,
     204                style=defaultStyle,
     205                captionpos=b,
     206                #1
     207        }
    211208}{}
    212209
    213210\lstnewenvironment{ucppcode}[1][]{
    214   \lstset{
    215     language = c++,
    216     style=defaultStyle,
    217     captionpos=b,
    218     #1
    219   }
     211        \lstset{
     212                language = c++,
     213                style=defaultStyle,
     214                captionpos=b,
     215                #1
     216        }
    220217}{}
    221218
    222219\lstnewenvironment{javacode}[1][]{
    223   \lstset{
    224     language = java,
    225     style=defaultStyle,
    226     captionpos=b,
    227     #1
    228   }
     220        \lstset{
     221                language = java,
     222                style=defaultStyle,
     223                captionpos=b,
     224                #1
     225        }
    229226}{}
    230227
    231228\lstnewenvironment{scalacode}[1][]{
    232   \lstset{
    233     language = scala,
    234     style=defaultStyle,
    235     captionpos=b,
    236     #1
    237   }
     229        \lstset{
     230                language = scala,
     231                style=defaultStyle,
     232                captionpos=b,
     233                #1
     234        }
    238235}{}
    239236
    240237\lstnewenvironment{smlcode}[1][]{
    241   \lstset{
    242     language = sml,
    243     style=defaultStyle,
    244     captionpos=b,
    245     #1
    246   }
     238        \lstset{
     239                language = sml,
     240                style=defaultStyle,
     241                captionpos=b,
     242                #1
     243        }
    247244}{}
    248245
    249246\lstnewenvironment{dcode}[1][]{
    250   \lstset{
    251     language = D,
    252     style=defaultStyle,
    253     captionpos=b,
    254     #1
    255   }
     247        \lstset{
     248                language = D,
     249                style=defaultStyle,
     250                captionpos=b,
     251                #1
     252        }
    256253}{}
    257254
    258255\lstnewenvironment{rustcode}[1][]{
    259   \lstset{
    260     language = rust,
    261     style=defaultStyle,
    262     captionpos=b,
    263     #1
    264   }
     256        \lstset{
     257                language = rust,
     258                style=defaultStyle,
     259                captionpos=b,
     260                #1
     261        }
    265262}{}
    266263
    267264\lstnewenvironment{gocode}[1][]{
    268   \lstset{
    269     language = Golang,
    270     style=defaultStyle,
    271     captionpos=b,
    272     #1
    273   }
     265        \lstset{
     266                language = Golang,
     267                style=defaultStyle,
     268                captionpos=b,
     269                #1
     270        }
    274271}{}
    275272
     
    279276\newcommand{\code}[1]{\lstinline[language=CFA,style=cfaStyle]{#1}}
    280277\newcommand{\pscode}[1]{\lstinline[language=pseudo,style=pseudoStyle]{#1}}
     278
     279% Local Variables: %
     280% tab-width: 4 %
     281% fill-column: 100 %
     282% End: %
  • doc/papers/general/Paper.tex

    ra9b1b0c rb5563e1  
    671671\begin{cfa}
    672672int f( int, int );
    673 int g( [int, int] );
    674 int h( int, [int, int] );
     673[int] g( [int, int] );
     674[int] h( int, [int, int] );
    675675[int, int] x;
    676676int y;
     
    706706This example shows mass, multiple, and cascading assignment used in one expression:
    707707\begin{cfa}
    708 void f( [int, int] );
     708[void] f( [int, int] );
    709709f( [x, y] = z = 1.5 );                                          $\C{// assignments in parameter list}$
    710710\end{cfa}
     
    814814Flattening and restructuring conversions are also applied to tuple types in polymorphic type assertions.
    815815\begin{cfa}
    816 int f( [int, double], double );
     816[int] f( [int, double], double );
    817817forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U );
    818818g( 5, 10.21 );
     
    11521152  case 4:
    11531153        ... `fallthrough common;`
    1154   common: // below fallthrough at same level as case clauses
     1154  `common`: // below fallthrough at same level as case clauses
    11551155        ...      // common code for cases 3 and 4
    11561156        // implicit break
     
    18571857\begin{cfa}
    18581858struct S { double x, y; };
    1859 int i, j;
     1859int x, y;
    18601860void f( int & i, int & j, S & s, int v[] );
    1861 f( 3, i + j, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } );   $\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$
     1861f( 3, x + y, (S){ 1.0, 7.0 }, (int [3]){ 1, 2, 3 } ); $\C{// pass rvalue to lvalue \(\Rightarrow\) implicit temporary}$
    18621862\end{cfa}
    18631863This allows complex values to be succinctly and efficiently passed to functions, without the syntactic overhead of explicit definition of a temporary variable or the runtime cost of pass-by-value.
     
    19461946
    19471947One of the strengths (and weaknesses) of C is memory-management control, allowing resource release to be precisely specified versus unknown release with garbage-collected memory-management.
    1948 However, this manual approach is often verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.
     1948However, this manual approach is verbose, and it is useful to manage resources other than memory (\eg file handles) using the same mechanism as memory.
    19491949\CC addresses these issues using Resource Aquisition Is Initialization (RAII), implemented by means of \newterm{constructor} and \newterm{destructor} functions;
    19501950\CFA adopts constructors and destructors (and @finally@) to facilitate RAII.
     
    19981998{
    19991999        VLA  x,            y = { 20, 0x01 },     z = y; $\C{// z points to y}$
    2000         //      ?{}( x );  ?{}( y, 20, 0x01 );  ?{}( z, y );
     2000        //    ?{}( x );   ?{}( y, 20, 0x01 );    ?{}( z, y );
    20012001        ^x{};                                                                   $\C{// deallocate x}$
    20022002        x{};                                                                    $\C{// reallocate x}$
     
    20992099
    21002100For readability, it is useful to associate units to scale literals, \eg weight (stone, pound, kilogram) or time (seconds, minutes, hours).
    2101 The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call-syntax (literal argument before function name), using the backquote, to convert basic literals into user literals.
     2101The left of Figure~\ref{f:UserLiteral} shows the \CFA alternative call-syntax (postfix: literal argument before function name), using the backquote, to convert basic literals into user literals.
    21022102The backquote is a small character, making the unit (function name) predominate.
    21032103For examples, the multi-precision integer-type in Section~\ref{s:MultiPrecisionIntegers} has user literals:
     
    21072107y = "12345678901234567890123456789"|`mp| + "12345678901234567890123456789"|`mp|;
    21082108\end{cfa}
    2109 Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions.
     2109Because \CFA uses a standard function, all types and literals are applicable, as well as overloading and conversions, where @?`@ denotes a postfix-function name and @`@ denotes a postfix-function call.
    21102110}%
     2111\begin{cquote}
     2112\lstset{language=CFA,moredelim=**[is][\color{red}]{|}{|},deletedelim=**[is][]{`}{`}}
     2113\lstDeleteShortInline@%
     2114\begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{\hspace{2\parindentlnth}}l@{}}
     2115\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}}  \\
     2116\begin{cfa}
     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;
     2130\end{cfa}
     2131&
     2132\begin{cfa}
     2133int i = 7;
     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;
     2146\end{cfa}
     2147\end{tabular}
     2148\lstMakeShortInline@%
     2149\end{cquote}
    21112150
    21122151The right of Figure~\ref{f:UserLiteral} shows the equivalent \CC version using the underscore for the call-syntax.
  • src/Parser/ExpressionNode.cc

    ra9b1b0c rb5563e1  
    1010// Created On       : Sat May 16 13:17:07 2015
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Mar  3 18:22:33 2018
    13 // Update Count     : 796
     12// Last Modified On : Thu Mar 22 11:57:39 2018
     13// Update Count     : 801
    1414//
    1515
     
    9494} // checkLNInt
    9595
    96 static void sepNumeric( string & str, string & units ) {
    97         string::size_type posn = str.find_first_of( "`" );
    98         if ( posn != string::npos ) {
    99                 units = "?" + str.substr( posn );                               // extract units
    100                 str.erase( posn );                                                              // remove units
    101         } // if
    102 } // sepNumeric
    103 
    10496Expression * build_constantInteger( string & str ) {
    10597        static const BasicType::Kind kind[2][6] = {
     
    108100                { BasicType::ShortUnsignedInt, BasicType::UnsignedChar, BasicType::UnsignedInt, BasicType::LongUnsignedInt, BasicType::LongLongUnsignedInt, BasicType::UnsignedInt128, },
    109101        };
    110 
    111         string units;
    112         sepNumeric( str, units );                                                       // separate constant from units
    113102
    114103        bool dec = true, Unsigned = false;                                      // decimal, unsigned constant
     
    232221        } // if
    233222  CLEANUP:
    234         if ( units.length() != 0 ) {
    235                 ret = new UntypedExpr( new NameExpr( units ), { ret } );
    236         } // if
    237223
    238224        delete &str;                                                                            // created by lex
     
    268254        };
    269255
    270         string units;
    271         sepNumeric( str, units );                                                       // separate constant from units
    272 
    273256        bool complx = false;                                                            // real, complex
    274257        int size = 1;                                                                           // 0 => float, 1 => double, 2 => long double
     
    303286        if ( lnth != -1 ) {                                                                     // explicit length ?
    304287                ret = new CastExpr( ret, new BasicType( Type::Qualifiers(), kind[complx][size] ) );
    305         } // if
    306         if ( units.length() != 0 ) {
    307                 ret = new UntypedExpr( new NameExpr( units ), { ret } );
    308288        } // if
    309289
  • src/Parser/lex.ll

    ra9b1b0c rb5563e1  
    1010 * Created On       : Sat Sep 22 08:58:10 2001
    1111 * Last Modified By : Peter A. Buhr
    12  * Last Modified On : Sat Mar  3 18:38:16 2018
    13  * Update Count     : 640
     12 * Last Modified On : Thu Mar 22 16:47:06 2018
     13 * Update Count     : 668
    1414 */
    1515
     
    5454
    5555void rm_underscore() {
    56         // Remove underscores in numeric constant by copying the non-underscore characters to the front of the string.
     56        // SKULLDUGGERY: remove underscores (ok to shorten?)
    5757        yyleng = 0;
    58         for ( int i = 0; yytext[i] != '\0'; i += 1 ) {
    59                 if ( yytext[i] == '`' ) {
    60                         // copy user suffix
    61                         for ( ; yytext[i] != '\0'; i += 1 ) {
    62                                 yytext[yyleng] = yytext[i];
    63                                 yyleng += 1;
    64                         } // for
    65                         break;
    66                 } // if
     58        for ( int i = 0; yytext[i] != '\0'; i += 1 ) {          // copying non-underscore characters to front of string
    6759                if ( yytext[i] != '_' ) {
    6860                        yytext[yyleng] = yytext[i];
     
    7163        } // for
    7264        yytext[yyleng] = '\0';
    73 }
     65} // rm_underscore
    7466
    7567// Stop warning due to incorrectly generated flex code.
     
    9082attr_identifier "@"{identifier}
    9183
    92 user_suffix_opt ("`"{identifier})?
    93 
    9484                                // numeric constants, CFA: '_' in constant
    9585hex_quad {hex}("_"?{hex}){3}
    9686size_opt (8|16|32|64|128)?
    9787length ("ll"|"LL"|[lL]{size_opt})|("hh"|"HH"|[hH])
    98 integer_suffix_opt ("_"?(([uU]({length}?[iI]?)|([iI]{length}))|([iI]({length}?[uU]?)|([uU]{length}))|({length}([iI]?[uU]?)|([uU][iI]))|[zZ]))?{user_suffix_opt}
     88integer_suffix_opt ("_"?(([uU]({length}?[iI]?)|([iI]{length}))|([iI]({length}?[uU]?)|([uU]{length}))|({length}([iI]?[uU]?)|([uU][iI]))|[zZ]))?
    9989
    10090octal_digits ({octal})|({octal}({octal}|"_")*{octal})
     
    118108floating_length ([fFdDlL]|[lL]{floating_size})
    119109floating_suffix ({floating_length}?[iI]?)|([iI]{floating_length})
    120 floating_suffix_opt ("_"?({floating_suffix}|"DL"))?{user_suffix_opt}
     110floating_suffix_opt ("_"?({floating_suffix}|"DL"))?
    121111decimal_digits ({decimal})|({decimal}({decimal}|"_")*{decimal})
    122112floating_decimal {decimal_digits}"."{exponent}?{floating_suffix_opt}
     
    125115
    126116binary_exponent "_"?[pP]"_"?[+-]?{decimal_digits}
    127 hex_floating_suffix_opt ("_"?({floating_suffix}))?{user_suffix_opt}
     117hex_floating_suffix_opt ("_"?({floating_suffix}))?
    128118hex_floating_fraction ({hex_digits}?"."{hex_digits})|({hex_digits}".")
    129119hex_floating_constant {hex_prefix}(({hex_floating_fraction}{binary_exponent})|({hex_digits}{binary_exponent})){hex_floating_suffix_opt}
     
    314304                                /* identifier */
    315305{identifier}    { IDENTIFIER_RETURN(); }
     306"`"{identifier}"`" {                                                                    // CFA
     307        yytext[yyleng - 1] = '\0'; yytext += 1;                         // SKULLDUGGERY: remove backquotes (ok to shorten?)
     308        IDENTIFIER_RETURN();
     309}
    316310{attr_identifier} { ATTRIBUTE_RETURN(); }
    317 "`"                             { BEGIN BKQUOTE; }
    318 <BKQUOTE>{identifier} { IDENTIFIER_RETURN(); }
    319 <BKQUOTE>"`"    { BEGIN 0; }
    320311
    321312                                /* numeric constants */
     
    332323({cwide_prefix}[_]?)?['] { BEGIN QUOTE; rm_underscore(); strtext = new string( yytext, yyleng ); }
    333324<QUOTE>[^'\\\n]* { strtext->append( yytext, yyleng ); }
    334 <QUOTE>['\n]{user_suffix_opt}   { BEGIN 0; strtext->append( yytext, yyleng ); RETURN_STR(CHARACTERconstant); }
     325<QUOTE>['\n]    { BEGIN 0; strtext->append( yytext, yyleng ); RETURN_STR(CHARACTERconstant); }
    335326                                /* ' stop editor highlighting */
    336327
     
    338329({swide_prefix}[_]?)?["] { BEGIN STRING; rm_underscore(); strtext = new string( yytext, yyleng ); }
    339330<STRING>[^"\\\n]* { strtext->append( yytext, yyleng ); }
    340 <STRING>["\n]{user_suffix_opt}  { BEGIN 0; strtext->append( yytext, yyleng ); RETURN_STR(STRINGliteral); }
     331<STRING>["\n]   { BEGIN 0; strtext->append( yytext, yyleng ); RETURN_STR(STRINGliteral); }
    341332                                /* " stop editor highlighting */
    342333
     
    348339                                /* punctuation */
    349340"@"                             { ASCIIOP_RETURN(); }
     341"`"                             { ASCIIOP_RETURN(); }
    350342"["                             { ASCIIOP_RETURN(); }
    351343"]"                             { ASCIIOP_RETURN(); }
     
    412404"?"({op_unary_pre_post}|"()"|"[?]"|"{}") { IDENTIFIER_RETURN(); }
    413405"^?{}"                  { IDENTIFIER_RETURN(); }
    414 "?`"{identifier} { IDENTIFIER_RETURN(); }                               // unit operator
     406"?`"{identifier} { IDENTIFIER_RETURN(); }                               // postfix operator
    415407"?"{op_binary_over}"?"  { IDENTIFIER_RETURN(); }                // binary
    416408        /*
  • src/Parser/parser.yy

    ra9b1b0c rb5563e1  
    1010// Created On       : Sat Sep  1 20:22:55 2001
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Fri Mar 16 17:24:44 2018
    13 // Update Count     : 3081
     12// Last Modified On : Thu Mar 22 16:56:21 2018
     13// Update Count     : 3125
    1414//
    1515
     
    126126        } // if
    127127} // rebindForall
     128
     129NameExpr * build_postfix_name( const string * name ) {
     130        NameExpr * new_name = build_varref( new string( "?`" + *name ) );
     131        delete name;
     132        return new_name;
     133} // build_postfix_name
    128134
    129135bool forall = false;                                                                    // aggregate have one or more forall qualifiers ?
     
    480486        | '(' compound_statement ')'                                            // GCC, lambda expression
    481487                { $$ = new ExpressionNode( new StmtExpr( dynamic_cast< CompoundStmt * >(maybeMoveBuild< Statement >($2) ) ) ); }
     488        | constant '`' IDENTIFIER                                                       // CFA, postfix call
     489                { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $3 ) ), $1 ) ); }
     490        | string_literal '`' IDENTIFIER                                         // CFA, postfix call
     491                { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $3 ) ), new ExpressionNode( $1 ) ) ); }
     492        | IDENTIFIER '`' IDENTIFIER                                                     // CFA, postfix call
     493                { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $3 ) ), new ExpressionNode( build_varref( $1 ) ) ) ); }
     494        | tuple '`' IDENTIFIER                                                          // CFA, postfix call
     495                { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $3 ) ), $1 ) ); }
     496        | '(' comma_expression ')' '`' IDENTIFIER                       // CFA, postfix call
     497                { $$ = new ExpressionNode( build_func( new ExpressionNode( build_postfix_name( $5 ) ), $2 ) ); }
    482498        | type_name '.' no_attr_identifier                                      // CFA, nested type
    483499                { SemanticError( yylloc, "Qualified names are currently unimplemented." ); $$ = nullptr; } // FIX ME
  • src/libcfa/Makefile.am

    ra9b1b0c rb5563e1  
    1111## Created On       : Sun May 31 08:54:01 2015
    1212## Last Modified By : Peter A. Buhr
    13 ## Last Modified On : Fri Feb  9 15:51:24 2018
    14 ## Update Count     : 223
     13## Last Modified On : Thu Mar 22 17:14:15 2018
     14## Update Count     : 224
    1515###############################################################################
    1616
     
    9999        ${stdhdr}                       \
    100100        math                            \
     101        time                            \
    101102        gmp                             \
    102103        bits/align.h            \
  • src/libcfa/Makefile.in

    ra9b1b0c rb5563e1  
    263263        containers/result containers/vector concurrency/coroutine \
    264264        concurrency/thread concurrency/kernel concurrency/monitor \
    265         ${shell find stdhdr -type f -printf "%p "} math gmp \
     265        ${shell find stdhdr -type f -printf "%p "} math time gmp \
    266266        bits/align.h bits/cfatime.h bits/containers.h bits/defs.h \
    267267        bits/debug.h bits/locks.h concurrency/invoke.h
     
    435435        ${stdhdr}                       \
    436436        math                            \
     437        time                            \
    437438        gmp                             \
    438439        bits/align.h            \
  • src/tests/coroutine/fibonacci.c

    ra9b1b0c rb5563e1  
    1010// Created On       : Thu Jun  8 07:29:37 2017
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Tue Dec  5 22:27:54 2017
    13 // Update Count     : 14
     12// Last Modified On : Thu Mar 22 22:45:44 2018
     13// Update Count     : 15
    1414//
    1515
     
    2121void ?{}( Fibonacci & fib ) with( fib ) { fn = 0; }
    2222
     23// main automatically called on first resume
    2324void main( Fibonacci & fib ) with( fib ) {
    2425        int fn1, fn2;                                                                           // retained between resumes
    25 
    26         fn = 0; fn1 = fn;                                                                       // 1st case
     26        fn = 0;  fn1 = fn;                                                                      // 1st case
    2727        suspend();                                                                                      // restart last resume
    28 
    29         fn = 1; fn2 = fn1;  fn1 = fn;                                           // 2nd case
     28        fn = 1;  fn2 = fn1;  fn1 = fn;                                          // 2nd case
    3029        suspend();                                                                                      // restart last resume
    31 
    3230        for ( ;; ) {
    3331                fn = fn1 + fn2; fn2 = fn1;  fn1 = fn;                   // general case
Note: See TracChangeset for help on using the changeset viewer.