Changeset e02e13f for doc


Ignore:
Timestamp:
Apr 4, 2023, 10:12:57 PM (14 months ago)
Author:
Mike Brooks <mlbrooks@…>
Branches:
ADT, ast-experimental, master
Children:
9bb8ee42
Parents:
ff71057 (diff), bb7422a (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/common.sty

    rff71057 re02e13f  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Fri Feb 10 12:09:30 2023
    14 %% Update Count     : 581
     13%% Last Modified On : Tue Apr  4 12:03:19 2023
     14%% Update Count     : 585
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    266266\newcommand{\LstCommentStyle}[1]{{\lst@basicstyle{\lst@commentstyle{#1}}}}
    267267\newcommand{\LstStringStyle}[1]{{\lst@basicstyle{\lst@stringstyle{#1}}}}
     268\newcommand{\LstNumberStyle}[1]{{\lst@basicstyle{\lst@numberstyle{#1}}}}
    268269
    269270\newlength{\gcolumnposn}                                % temporary hack because lstlisting does not handle tabs correctly
    … …  
    286287columns=fullflexible,
    287288basicstyle=\linespread{0.9}\sf,                 % reduce line spacing and use sanserif font
    288 stringstyle=\tt,                                                % use typewriter font
     289stringstyle=\small\tt,                                  % use typewriter font
    289290tabsize=5,                                                              % N space tabbing
    290291xleftmargin=\parindentlnth,                             % indent code to paragraph indentation

  • doc/LaTeXmacros/common.tex

    rff71057 re02e13f  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Fri Feb 17 08:32:47 2023
    14 %% Update Count     : 565
     13%% Last Modified On : Tue Apr  4 12:03:18 2023
     14%% Update Count     : 567
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    291291columns=fullflexible,
    292292basicstyle=\linespread{0.9}\sf,                 % reduce line spacing and use sanserif font
    293 stringstyle=\tt,                                                % use typewriter font
     293stringstyle=\small\tt,                                  % use typewriter font
    294294tabsize=5,                                                              % N space tabbing
    295295xleftmargin=\parindentlnth,                             % indent code to paragraph indentation

  • doc/theses/colby_parsons_MMAth/Makefile

    rff71057 re02e13f  
    9696
    9797${BASE}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${DATA} \
    98                 ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib | ${Build}
     98                style/style.tex ${Macros}/common.tex ${Macros}/indexstyle local.bib ../../bibliography/pl.bib | ${Build}
    9999        # Must have *.aux file containing citations for bibtex
    100100        if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi

  • doc/theses/colby_parsons_MMAth/style/style.tex

    rff71057 re02e13f  
    11\input{common}
     2\CFAStyle                                               % CFA code-style
     3\lstset{language=CFA}                                   % default language
    24
    3 \lstdefinestyle{defaultStyle}{
    4     escapeinside={@@},
    5     %  basicstyle=\linespread{0.9}\tt\footnotesize,             % reduce line spacing and use typewriter font
    6       basicstyle=\linespread{0.9}\sf,           % reduce line spacing and use typewriter font
    7     %  keywordstyle=\bfseries\color{blue},
    8     %  keywordstyle=[2]\bfseries\color{Plum},
    9     %  commentstyle=\sf\itshape\color{OliveGreen},                % green and italic comments
    10     %  identifierstyle=\color{identifierCol},
    11     %  stringstyle=\sf\color{Mahogany},                           % use sanserif font
    12       stringstyle=\tt,                            % use sanserif font
    13       mathescape=true,
    14     %  columns=fixed,
    15       columns=fullflexible,
    16     %  aboveskip=4pt,                                  % spacing above/below code block
    17     %  belowskip=3pt,
    18       keepspaces=true,
    19       tabsize=4,
    20       % frame=lines,
    21       literate=,
    22       showlines=true,                                 % show blank lines at end of code
    23       showspaces=false,
    24       showstringspaces=false,
    25       showlines=true,                                                   % show blank lines at end of code
    26       escapechar=\$,
    27       xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    28       moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    29       morekeywords=[2]{accept, signal, signal_block, wait, waitfor, waituntil},
    30       abovecaptionskip=5pt,
    31 }
    32 
    33 \lstdefinestyle{cfaStyle}{
    34   escapeinside={@@},
    35   basicstyle=\linespread{0.9}\sf,               % reduce line spacing and use typewriter font
    36   stringstyle=\tt,                                % use sanserif font
    37   mathescape=true,
    38   columns=fullflexible,
    39   keepspaces=true,
    40   tabsize=4,
    41   literate=,
    42   showlines=true,                                 % show blank lines at end of code
    43   showspaces=false,
    44   showstringspaces=false,
    45   showlines=true,                                                       % show blank lines at end of code
    46   escapechar=\$,
    47   xleftmargin=\parindentlnth,                     % indent code to paragraph indentation
    48   moredelim=[is][\color{red}\bfseries]{**R**}{**R**},    % red highlighting
    49   morekeywords=[2]{accept, signal, signal_block, wait, waitfor, waituntil},
    50   abovecaptionskip=5pt,
    51 }
    52 
    53 \lstnewenvironment{cfacode}[1][]{
    54   \lstset{
    55     language = CFA,
    56     style=cfaStyle,
    57     captionpos=b,
    58     #1
    59   }
    60 }{}
    61 
    62 \lstnewenvironment{cppcode}[1][]{
    63   \lstset{
    64     language = c++,
    65     style=defaultStyle,
    66     captionpos=b,
    67     #1
    68   }
    69 }{}
    70 
    71 \newcommand{\code}[1]{\lstinline[language=CFA,style=cfaStyle]{#1}}
     5\newcommand{\code}[1]{\lstinline[language=CFA]{#1}}
    726\newcommand{\uC}{$\mu$\CC}
    737

  • doc/theses/colby_parsons_MMAth/text/CFA_concurrency.tex

    rff71057 re02e13f  
    11\chapter{Concurrency in \CFA}\label{s:cfa_concurrency}
    22
    3 The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis\cite{Delisle18}.
    4 In that work he introduced coroutines, user level threading, and monitors.
    5 Not listed in that work were the other concurrency features that were needed as building blocks, such as locks, futures, and condition variables which he also added to \CFA.
     3The groundwork for concurrency in \CFA was laid by Thierry Delisle in his Master's Thesis~\cite{Delisle18}.
     4In that work, he introduced generators, coroutines, monitors, and user-level threading.
     5Not listed in that work were basic concurrency features needed as building blocks, such as locks, futures, and condition variables, which he also added to \CFA.
    66
    77\section{Threading Model}\label{s:threading}
    8 \CFA has user level threading and supports a $M:N$ threading model where $M$ user threads are scheduled on $N$ cores, where both $M$ and $N$ can be explicitly set by the user.
    9 Cores are used by a program by creating instances of a \code{processor} struct.
    10 User threads types are defined using the \code{thread} keyword, in the place where a \code{struct} keyword is typically used.
    11 For each thread type a corresponding main must be defined, which is where the thread starts running once it is created.
    12 Listing~\ref{l:cfa_thd_init} shows an example of processor and thread creation.
    13 When processors are added, they are added alongside the existing processor given to each program.
    14 Thus if you want $N$ processors you need to allocate $N-1$.
    15 To join a thread the thread must be deallocated, either deleted if it is allocated on the heap, or go out of scope if stack allocated.
    16 The thread performing the deallocation will wait for the thread being deallocated to terminate before the deallocation can occur.
    17 A thread terminates by returning from the main routine where it starts.
     8\CFA provides user-level threading and supports an $M$:$N$ threading model where $M$ user threads are scheduled on $N$ kernel threads, where both $M$ and $N$ can be explicitly set by the user.
     9Kernel threads are created by instancing a @processor@ structure.
     10User-thread types are defined by creating a @thread@ aggregate-type, \ie replace @struct@ with @thread@.
     11For each thread type a corresponding @main@ routine must be defined, which is where the thread starts running once it is created.
     12Examples of \CFA  user thread and processor creation are shown in \VRef[Listing]{l:cfa_thd_init}.
    1813
    19 \begin{cfacode}[tabsize=3,caption={\CFA user thread and processor creation},label={l:cfa_thd_init}]
    20 
    21 thread my_thread {}     // user thread type
    22 void main( my_thread & this ) { // thread start routine
    23     printf("Hello threading world\n");
     14\begin{cfa}[caption={Example of \CFA user thread and processor creation},label={l:cfa_thd_init}]
     15@thread@ my_thread {...};                       $\C{// user thread type}$
     16void @main@( my_thread & this ) {       $\C{// thread start routine}$
     17        sout | "Hello threading world";
    2418}
    2519
    2620int main() {
    27     // add 2 processors, now 3 total
    28     processor p[2];   
    29     {
    30         my_thread t1;
    31         my_thread t2;
    32     } // waits for threads to end before going out of scope
     21        @processor@ p[2];                               $\C{// add 2 processors = 3 total with starting processor}$
     22        {
     23                my_thread t[2], * t3 = new();   $\C{// create 3 user threads, running in main routine}$
     24                ... // execute concurrently
     25                delete( t3 );                           $\C{// wait for thread to end and deallocate}$
     26        } // wait for threads to end and deallocate
    3327}
     28\end{cfa}
    3429
    35 \end{cfacode}
     30When processors are added, they are added alongside the existing processor given to each program.
     31Thus, for $N$ processors, allocate $N-1$ processors.
     32A thread is implicitly joined at deallocated, either implicitly at block exit for stack allocation or explicitly at @delete@ for heap allocation.
     33The thread performing the deallocation must wait for the thread to terminate before the deallocation can occur.
     34A thread terminates by returning from the main routine where it starts.
     35
     36% Local Variables: %
     37% tab-width: 4 %
     38% End: %

  • doc/theses/colby_parsons_MMAth/text/CFA_intro.tex

    rff71057 re02e13f  
    77\section{Overview}
    88The following serves as an introduction to \CFA.
    9 \CFA is a layer over C, is transpiled to C and is largely considered to be an extension of C.
    10 Beyond C, it adds productivity features, libraries, a type system, and many other language constructions.
    11 However, \CFA stays true to C as a language, with most code revolving around \code{struct}'s and routines, and respects the same rules as C.
    12 \CFA is not object oriented as it has no notion of \code{this} and no classes or methods, but supports some object oriented adjacent ideas including costructors, destructors, and limited inheritance.
    13 \CFA is rich with interesting features, but a subset that is pertinent to this work will be discussed.
     9\CFA is a layer over C, is transpiled\footnote{Source to source translator.} to C, and is largely considered to be an extension of C.
     10Beyond C, it adds productivity features, extended libraries, an advanced type system, and many control-flow/concurrency constructions.
     11However, \CFA stays true to the C programming style, with most code revolving around @struct@'s and routines, and respects the same rules as C.
     12\CFA is not object oriented as it has no notion of @this@ (receiver) and no structures with methods, but supports some object oriented ideas including constructors, destructors, and limited containment inheritance.
     13While \CFA is rich with interesting features, only the subset pertinent to this work is discussed.
    1414
    1515\section{References}
    16 References in \CFA are similar to references in \CC, however in \CFA references are rebindable, and support multi-level referencing.
     16References in \CFA are similar to references in \CC; however \CFA references are rebindable, and support multi-level referencing.
    1717References in \CFA are a layer of syntactic sugar over pointers to reduce the number of ref/deref operations needed with pointer usage.
    18 Some examples of references in \CFA are shown in Listing~\ref{l:cfa_ref}.
    19 Another related item to note is that the \CFA equivalent of \CC's \code{nullptr} is \code{0p}.
    20 
    21 \begin{cfacode}[caption={Example of \CFA references},label={l:cfa_ref}]
     18Another difference is the use of @0p@ instead of C's @NULL@ or \CC's @nullptr@.
     19Examples of references are shown in \VRef[Listing]{l:cfa_ref}.
     20
     21\begin{cfa}[caption={Example of \CFA references},label={l:cfa_ref}]
    2222int i = 2;
    23 int & ref_i = i;            // declare ref to i
    24 int * ptr_i = &i;           // ptr to i
     23int & ref_i = i;                        $\C{// declare ref to i}$
     24int * ptr_i = &i;                       $\C{// ptr to i}$
    2525
    2626// address of ref_i is the same as address of i
    2727assert( &ref_i == ptr_i );
    2828
    29 int && ref_ref_i = ref_i;   // can have a ref to a ref
    30 ref_i = 3;                  // set i to 3
     29int && ref_ref_i = ref_i;       $\C{// can have a ref to a ref}$
     30ref_i = 3;                                      $\C{// set i to 3}$
    3131int new_i = 4;
    3232
    3333// syntax to rebind ref_i (must cancel implicit deref)
    34 &ref_i = &new_i; // (&*)ref_i = &new_i; (sets underlying ptr)
    35 \end{cfacode}
    36 
    37 
    38 \section{Overloading}
    39 In \CFA routines can be overloaded on parameter type, number of parameters, and return type.
     34&ref_i = &new_i;                        $\C{// (\&*)ref\_i = \&new\_i; (sets underlying ptr)}$
     35\end{cfa}
     36
     37
     38\section{Overloading}\label{s:Overloading}
     39\CFA routines can be overloaded on parameter type, number of parameters, and \emph{return type}.
    4040Variables can also be overloaded on type, meaning that two variables can have the same name so long as they have different types.
    41 The variables will be disambiguated via type, sometimes requiring a cast.
    42 The code snippet in Listing~\ref{l:cfa_overload} contains examples of overloading.
    43 
    44 
    45 \begin{cfacode}[caption={Example of \CFA function overloading},label={l:cfa_overload}]
    46 int foo() { printf("A\n");  return 0;}
    47 int foo( int bar ) { printf("B\n"); return 1; }
    48 int foo( double bar ) { printf("C\n"); return 2; }
    49 double foo( double bar ) { printf("D\n"); return 3;}
    50 void foo( double bar ) { printf("%.0f\n", bar); }
    51 
    52 int main() {
    53     foo();                  // prints A
    54     foo( 0 );               // prints B
    55     int a = foo( 0.0 );     // prints C
    56     double a = foo( 0.0 );  // prints D
    57     foo( a );               // prints 3
    58 }
    59 \end{cfacode}
     41A routine or variable is disambiguated at each usage site via its type and surrounding expression context.
     42A cast is used to disambiguate any conflicting usage.
     43Examples of overloading are shown in \VRef[Listing]{l:cfa_overload}.
     44
     45\begin{cfa}[caption={Example of \CFA overloading},label={l:cfa_overload}]
     46int foo() { sout | "A";  return 0;}
     47int foo( int bar ) { sout | "B"; return 1; }
     48int foo( double bar ) { sout | "C"; return 2; }
     49double foo( double bar ) { sout | "D"; return 3; }
     50void foo( double bar ) { sout | bar; }
     51
     52int main() {
     53        foo();                                          $\C{// prints A}$
     54        foo( 0 );                                       $\C{// prints B}$
     55        int foo = foo( 0.0 );           $\C{// prints C}$
     56        double foo = foo( 0.0 );        $\C{// prints D}$
     57        foo( foo );                                     $\C{// prints 3., where left-hand side of expression is void}$
     58}
     59\end{cfa}
    6060
    6161
    6262\section{With Statement}
    63 The with statement is a tool for exposing members of aggregate types within a scope in \CFA.
    64 It allows users to use fields of aggregate types without using their fully qualified name.
    65 This feature is also implemented in Pascal.
    66 It can exist as a stand-alone statement or it can be used on routines to expose fields in the body of the routine.
    67 An example is shown in Listing~\ref{l:cfa_with}.
    68 
    69 
    70 \begin{cfacode}[tabsize=3,caption={Usage of \CFA with statement},label={l:cfa_with}]
    71 struct obj {
    72     int a, b, c;
    73 };
    74 struct pair {
    75     double x, y;
    76 };
    77 
    78 // Stand-alone with stmt:
     63The \CFA @with@ statement is for exposing fields of an aggregate type within a scope, allowing field names without qualification.
     64This feature is also implemented in Pascal~\cite{Pascal}.
     65It can exist as a stand-alone statement or wrap a routine body to expose aggregate fields.
     66Examples of the @with@ statement are shown in \VRef[Listing]{l:cfa_with}.
     67
     68\begin{cfa}[caption={Example of \CFA \lstinline{with} statement},label={l:cfa_with}]
     69struct pair {  double x, y;  };
     70struct triple {  int a, b, c;  };
    7971pair p;
    80 with( p ) {
    81     x = 6.28;
    82     y = 1.73;
    83 }
    84 
    85 // Can be used on routines:
    86 void foo( obj o, pair p ) with( o, p ) {
    87     a = 1;
    88     b = 2;
    89     c = 3;
    90     x = 3.14;
    91     y = 2.71;
    92 }
    93 
    94 // routine foo is equivalent to routine bar:
    95 void bar( obj o, pair p ) {
    96     o.a = 1;
    97     o.b = 2;
    98     o.c = 3;
    99     p.x = 3.14;
    100     p.y = 2.71;
    101 }
    102 \end{cfacode}
     72
     73@with( p )@ {                                   $\C{// stand-alone with}$
     74        p.x = 6.28;  p.y = 1.73;        $\C{// long form}$
     75           x = 6.28;     y = 1.73;      $\C{// short form}$
     76}
     77void foo( triple t, pair p ) @with( t, p )@ {  $\C{// routine with}$
     78        t.a = 1;  t.b = 2;  t.c = 3;  p.x = 3.14;  p.y = 2.71;  $\C{// long form}$
     79          a = 1;    b = 2;    c = 3;     x = 3.14;     y = 2.71;  $\C{// short form}$
     80}
     81\end{cfa}
    10382
    10483
    10584\section{Operators}
    10685Operators can be overloaded in \CFA with operator routines.
    107 Operators in \CFA are named using the operator symbol and '?' to respresent operands.
    108 An example is shown in Listing~\ref{l:cfa_operate}.
    109 
    110 
    111 \begin{cfacode}[tabsize=3,caption={Example of \CFA operators},label={l:cfa_operate}]
     86Operators in \CFA are named using an operator symbol and '@?@' to represent operands.
     87Examples of \CFA operators are shown in \VRef[Listing]{l:cfa_operate}.
     88
     89\begin{cfa}[caption={Example of \CFA operators},label={l:cfa_operate}]
    11290struct coord {
    113     double x;
    114     double y;
    115     double z;
    116 };
    117 coord ++?( coord & c ) with(c) {
    118     x++;
    119     y++;
    120     z++;
    121     return c;
    122 }
    123 coord ?<=?( coord op1, coord op2 ) with( op1 ) {
    124     return (x*x + y*y + z*z) <=
    125         (op2.x*op2.x + op2.y*op2.y + op2.z*op2.z);
    126 }
    127 \end{cfacode}
     91        double x, y, z;
     92};
     93coord ++@?@( coord & c ) with( c ) { $\C{// post increment}$
     94        x++;  y++;  z++;
     95        return c;
     96}
     97coord @?@<=@?@( coord op1, coord op2 ) with( op1 ) { $\C{// ambiguous with both parameters}$
     98        return (x * x + y * y + z * z) <= (op2.x * op2.x + op2.y * op2.y + op2.z * op2.z);
     99}
     100\end{cfa}
    128101
    129102
    130103\section{Constructors and Destructors}
    131 Constructors and destructors in \CFA are two special operator routines that are used for creation and destruction of objects.
    132 The default constructor and destructor for a type are called implicitly upon creation and deletion respectively if they are defined.
    133 An example is shown in Listing~\ref{l:cfa_ctor}.
    134 
    135 
    136 \begin{cfacode}[tabsize=3,caption={Example of \CFA constructors and destructors},label={l:cfa_ctor}]
     104Constructors and destructors in \CFA are special operator routines used for creation and destruction of objects.
     105The default constructor and destructor for a type are called implicitly upon creation and deletion, respectively.
     106Examples of \CFA constructors and destructors are shown in \VRef[Listing]{l:cfa_ctor}.
     107
     108\begin{cfa}[caption={Example of \CFA constructors and destructors},label={l:cfa_ctor}]
    137109struct discrete_point {
    138     int x;
    139     int y;
    140 };
    141 void ?{}( discrete_point & this ) with(this) { // ctor
    142     x = 0;
    143     y = 0;
    144 }
    145 void ?{}( discrete_point & this, int x, int y ) { // ctor
    146     this.x = x;
    147     this.y = y;
    148 }
    149 void ^?{}( discrete_point & this ) with(this) { // dtor
    150     x = 0;
    151     y = 0;
    152 }
    153 
    154 int main() {
    155     discrete_point d; // implicit call to ?{}
    156     discrete_point p{}; // same call as line above
    157     discrete_point dp{ 2, -4 }; // specialized ctor
    158 } // ^d{}, ^p{}, ^dp{} all called as they go out of scope
    159 \end{cfacode}
     110        int x, y;
     111};
     112void ?{}( discrete_point & this ) with(this) { $\C{// default constructor}$
     113        [x, y] = 0;
     114}
     115void ?{}( discrete_point & this, int x, int y ) { $\C{// explicit constructor}$
     116        this.[x, y] = [x, y];
     117}
     118void ^?{}( discrete_point & this ) with(this) { $\C{// destructor}$
     119        ?{}( this );  $\C{// reset by calling default constructor}$
     120}
     121int main() {
     122        discrete_point x, y{};  $\C{// implicit call to default ctor, ?\{\}}$
     123        discrete_point s = { 2, -4 }, t{ 4, 2 };  $\C{// explicit call to specialized ctor}$
     124} // ^t{}, ^s{}, ^y{}, ^x{} implicit calls in reverse allocation order
     125\end{cfa}
    160126
    161127
    162128\section{Polymorphism}\label{s:poly}
    163 C does not natively support polymorphism, and requires users to implement polymorphism themselves if they want to use it.
    164 \CFA extends C with two styles of polymorphism that it supports, parametric polymorphism and nominal inheritance.
     129C supports limited polymorphism, often requiring users to implement polymorphism using a @void *@ (type erasure) approach.
     130\CFA extends C with generalized overloading polymorphism (see \VRef{s:Overloading}), as well as, parametric polymorphism and nominal inheritance.
    165131
    166132\subsection{Parametric Polymorphism}
    167 \CFA provides parametric polymorphism in the form of \code{forall}, and \code{trait}s.
    168 A \code{forall} takes in a set of types and a list of constraints.
    169 The declarations that follow the \code{forall} are parameterized over the types listed that satisfy the constraints.
    170 Sometimes the list of constraints can be long, which is where a \code{trait} can be used.
    171 A \code{trait} is a collection of constraints that is given a name and can be reused in foralls.
    172 An example of the usage of parametric polymorphism in \CFA is shown in Listing~\ref{l:cfa_poly}.
    173 
    174 \begin{cfacode}[tabsize=3,caption={Example of \CFA polymorphism},label={l:cfa_poly}]
     133\CFA provides parametric polymorphism in the form of @forall@, and @trait@s.
     134A @forall@ takes in a set of types and a list of constraints.
     135The declarations that follow the @forall@ are parameterized over the types listed that satisfy the constraints.
     136A list of @forall@ constraints can be refactored into a named @trait@ and reused in @forall@s.
     137Examples of \CFA parametric polymorphism are shown in \VRef[Listing]{l:cfa_poly}.
     138
     139\begin{cfa}[caption={Example of \CFA parametric polymorphism},label={l:cfa_poly}]
    175140// sized() is a trait that means the type has a size
    176 forall( V & | sized(V) )        // type params for trait
     141forall( V & | sized(V) )                $\C{// type params for trait}$
    177142trait vector_space {
    178     V add( V, V );              // vector addition
    179     V scalar_mult( int, V );    // scalar multiplication
    180 
    181     // dtor and copy ctor needed in constraints to pass by copy
    182     void ?{}( V &, V & );       // copy ctor for return
    183     void ^?{}( V & );           // dtor
    184 };
    185 
    186 forall( V & | vector_space( V )) {
    187     V get_inverse( V v1 ) {
    188         return scalar_mult( -1, v1 );  // can use ?*? routine defined in trait
    189     }
    190     V add_and_invert( V v1, V v2 ) {
    191         return get_inverse( add( v1, v2 ) );  // can use ?*? routine defined in trait
    192     }
     143        // dtor and copy ctor needed in constraints to pass by copy
     144        void ?{}( V &, V & );           $\C{// copy ctor for return}$
     145        void ^?{}( V & );                       $\C{// dtor}$
     146        V ?+?( V, V );                          $\C{// vector addition}$
     147        V ?*?( int, V );                        $\C{// scalar multiplication}$
     148};
     149
     150forall( V & | vector_space( V ) ) {
     151        V get_inverse( V v1 ) {
     152                return -1 * v1;                 $\C{// can use ?*? routine defined in trait}$
     153        }
     154        V add_and_invert( V v1, V v2 ) {
     155                return get_inverse( v1 + v2 );  $\C{// can use ?+? routine defined in trait}$
     156        }
    193157}
    194158struct Vec1 { int x; };
    … …  
    196160void ?{}( Vec1 & this, int x ) { this.x = x; }
    197161void ^?{}( Vec1 & this ) {}
    198 Vec1 add( Vec1 v1, Vec1 v2 ) { v1.x += v2.x; return v1; }
    199 Vec1 scalar_mult( int c, Vec1 v1 ) { v1.x = v1.x * c; return v1; }
     162Vec1 ?+?( Vec1 v1, Vec1 v2 ) { v1.x += v2.x; return v1; }
     163Vec1 ?*?( int c, Vec1 v1 ) { v1.x = v1.x * c; return v1; }
    200164
    201165struct Vec2 { int x; int y; };
    … …  
    203167void ?{}( Vec2 & this, int x ) { this.x = x; this.y = x; }
    204168void ^?{}( Vec2 & this ) {}
    205 Vec2 add( Vec2 v1, Vec2 v2 ) { v1.x += v2.x; v1.y += v2.y; return v1; }
    206 Vec2 scalar_mult( int c, Vec2 v1 ) { v1.x = v1.x * c; v1.y = v1.y * c; return v1; }
    207 
    208 int main() {
    209     Vec1 v1{ 1 }; // create Vec1 and call ctor
    210     Vec2 v2{ 2 }; // create Vec2 and call ctor
    211 
    212     // can use forall defined routines since types satisfy trait
    213     add_and_invert( get_inverse( v1 ), v1 );
    214     add_and_invert( get_inverse( v2 ), v2 );
    215 }
    216 
    217 \end{cfacode}
     169Vec2 ?+?( Vec2 v1, Vec2 v2 ) { v1.x += v2.x; v1.y += v2.y; return v1; }
     170Vec2 ?*?( int c, Vec2 v1 ) { v1.x = v1.x * c; v1.y = v1.y * c; return v1; }
     171
     172int main() {
     173        Vec1 v1{ 1 };                           $\C{// create Vec1 and call ctor}$
     174        Vec2 v2{ 2 };                           $\C{// create Vec2 and call ctor}$
     175        // can use forall defined routines since types satisfy trait
     176        add_and_invert( get_inverse( v1 ), v1 );
     177        add_and_invert( get_inverse( v2 ), v2 );
     178}
     179\end{cfa}
    218180
    219181\subsection{Inheritance}
    220 Inheritance in \CFA copies its style from Plan-9 C nominal inheritance.
    221 In \CFA structs can \code{inline} another struct type to gain its fields and to be able to be passed to routines that require a parameter of the inlined type.
    222 An example of \CFA inheritance is shown in Listing~\ref{l:cfa_inherit}.
    223 
    224 \begin{cfacode}[tabsize=3,caption={Example of \CFA inheritance},label={l:cfa_inherit}]
     182Inheritance in \CFA is taken from Plan-9 C's containment inheritance.
     183In \CFA, @struct@s can @inline@ another struct type to gain its fields and masquerade as that type.
     184Examples of \CFA containment inheritance are shown in \VRef[Listing]{l:cfa_inherit}.
     185
     186\begin{cfa}[caption={Example of \CFA containment inheritance},label={l:cfa_inherit}]
    225187struct one_d { double x; };
    226188struct two_d {
    227     inline one_d;
    228     double y;
     189        @inline@ one_d;
     190        double y;
    229191};
    230192struct three_d {
    231     inline two_d;
    232     double z;
     193        @inline@ two_d;
     194        double z;
    233195};
    234196double get_x( one_d & d ){ return d.x; }
    … …  
    236198struct dog {};
    237199struct dog_food {
    238     int count;
     200        int count;
    239201};
    240202struct pet {
    241     inline dog;
    242     inline dog_food;
    243 };
    244 void pet_dog( dog & d ){printf("woof\n");}
    245 void print_food( dog_food & f ){printf("%d\n", f.count);}
    246 
    247 int main() {
    248     one_d x;
    249     two_d y;
    250     three_d z;
    251     x.x = 1;
    252     y.x = 2;
    253     z.x = 3;
    254     get_x( x ); // returns 1;
    255     get_x( y ); // returns 2;
    256     get_x( z ); // returns 3;
    257     pet p;
    258     p.count = 5;
    259     pet_dog( p );    // prints woof
    260     print_food( p ); // prints 5
    261 }
    262 \end{cfacode}
    263 
    264 
     203        @inline@ dog;
     204        @inline@ dog_food;
     205};
     206void pet_dog( dog & d ) { sout | "woof"; }
     207void print_food( dog_food & f ) { sout | f.count; }
     208
     209int main() {
     210        one_d x;
     211        two_d y;
     212        three_d z;
     213        x.x = 1;
     214        y.x = 2;
     215        z.x = 3;
     216        get_x( x );                                     $\C{// returns 1;}$
     217        get_x( y );                                     $\C{// returns 2;}$
     218        get_x( z );                                     $\C{// returns 3;}$
     219        pet p;
     220        p.count = 5;
     221        pet_dog( p );                           $\C{// prints woof}$
     222        print_food( p );                        $\C{// prints 5}$
     223}
     224\end{cfa}
     225
     226% Local Variables: %
     227% tab-width: 4 %
     228% End: %

  • doc/theses/colby_parsons_MMAth/text/actors.tex

    rff71057 re02e13f  
    8888Similarly to create a message type a user must define a struct which \code{inline}'s the base \code{message} struct.
    8989
    90 \begin{cfacode}
     90\begin{cfa}
    9191struct derived_actor {
    9292    inline actor;       // Plan-9 C inheritance
    … …  
    118118    return 0;
    119119}
    120 \end{cfacode}
     120\end{cfa}
    121121
    122122The above code is a simple actor program in \CFA.
    … …  
    125125Key things to highlight include the \code{receive} signature, and calls to \code{start_actor_system}, and \code{stop_actor_system}.
    126126To define a behaviour for some derived actor and derived message type, one must declare a routine with the signature:
    127 \begin{cfacode}
     127\begin{cfa}
    128128Allocation receive( derived_actor & receiver, derived_msg & msg )
    129 \end{cfacode}
     129\end{cfa}
    130130Where \code{derived_actor} and \code{derived_msg} can be any derived actor and derived message types respectively.
    131131The return value of \code{receive} must be a value from the \code{Allocation} enum:
    132 \begin{cfacode}
     132\begin{cfa}
    133133enum Allocation { Nodelete, Delete, Destroy, Finished };
    134 \end{cfacode}
     134\end{cfa}
    135135The \code{Allocation} enum is a set of actions that dictate what the executor should do with a message or actor after a given behaviour has been completed.
    136136In the case of an actor, the \code{receive} routine returns the \code{Allocation} status to the executor which sets the status on the actor and takes the appropriate action.
    137137For messages, they either default to \code{Nodelete}, or they can be passed an \code{Allocation} via the \code{message} constructor.
    138138Message state can be updated via a call to:
    139 \begin{cfacode}
     139\begin{cfa}
    140140void set_allocation( message & this, Allocation state )
    141 \end{cfacode}
     141\end{cfa}
    142142
    143143The following describes the use of each of the \code{Allocation} values:
    … …  
    186186All message sends are done using the left shift operater, \ie <<, similar to the syntax of \CC's output.
    187187The signature of the left shift operator is:
    188 \begin{cfacode}
     188\begin{cfa}
    189189Allocation ?<<?( derived_actor & receiver, derived_msg & msg )
    190 \end{cfacode}
     190\end{cfa}
    191191
    192192An astute eye will notice that this is the same signature as the \code{receive} routine which is no coincidence.
    … …  
    368368To first verify sequential correctness, consider the equivalent sequential swap below:
    369369
    370 \begin{cfacode}
     370\begin{cfa}
    371371void swap( uint victim_idx, uint my_idx  ) {
    372372    // Step 0:
    … …  
    380380    request_queues[my_idx] = vic_queue;
    381381}
    382 \end{cfacode}
     382\end{cfa}
    383383
    384384Step 1 is missing in the sequential example since in only matter in the concurrent context presented later.
    … …  
    386386Temporary copies of each pointer being swapped are stored, and then the original values of each pointer are set using the copy of the other pointer.
    387387
    388 \begin{cfacode}
     388\begin{cfa}
    389389// This routine is atomic
    390390bool CAS( work_queue ** ptr, work_queue ** old, work_queue * new ) {
    … …  
    427427    return true;
    428428}
    429 \end{cfacode}\label{c:swap}
     429\end{cfa}\label{c:swap}
    430430
    431431Now consider the concurrent implementation of the swap.

  • doc/theses/colby_parsons_MMAth/text/channels.tex

    rff71057 re02e13f  
    118118Also note that in the Go version~\ref{l:go_chan_bar}, the size of the barrier channels has to be larger than in the \CFA version to ensure that the main thread does not block when attempting to clear the barrier.
    119119
    120 \begin{cfacode}[tabsize=3,caption={\CFA channel barrier termination},label={l:cfa_chan_bar}]
     120\begin{cfa}[tabsize=3,caption={\CFA channel barrier termination},label={l:cfa_chan_bar}]
    121121struct barrier {
    122122    channel( int ) barWait;
    … …  
    171171    return 0;
    172172}
    173 \end{cfacode}
    174 
    175 \begin{cfacode}[tabsize=3,caption={Go channel barrier termination},label={l:go_chan_bar}]
     173\end{cfa}
     174
     175\begin{cfa}[tabsize=3,caption={Go channel barrier termination},label={l:go_chan_bar}]
    176176
    177177struct barrier {
    … …  
    237237    return 0;
    238238}
    239 \end{cfacode}
     239\end{cfa}
    240240
    241241In Listing~\ref{l:cfa_resume} an example of channel closing with resumption is used.
    … …  
    244244If the same program was implemented in Go it would require explicit synchronization with both producers and consumers by some mechanism outside the channel to ensure that all elements were removed before task termination.
    245245
    246 \begin{cfacode}[tabsize=3,caption={\CFA channel resumption usage},label={l:cfa_resume}]
     246\begin{cfa}[tabsize=3,caption={\CFA channel resumption usage},label={l:cfa_resume}]
    247247channel( int ) chan{ 128 };
    248248
    … …  
    280280    return 0;
    281281}
    282 \end{cfacode}
     282\end{cfa}
    283283
    284284\section{Performance}

  • doc/theses/colby_parsons_MMAth/text/mutex_stmt.tex

    rff71057 re02e13f  
    1212Additionally, it provides the safety guarantee of deadlock-freedom, both by acquiring the locks in a deadlock-free manner, and by ensuring that the locks release on error, or normal program execution via \gls{raii}.
    1313
    14 \begin{cfacode}[tabsize=3,caption={\CFA mutex statement usage},label={l:cfa_mutex_ex}]
     14\begin{cfa}[tabsize=3,caption={\CFA mutex statement usage},label={l:cfa_mutex_ex}]
    1515owner_lock lock1, lock2, lock3;
    1616int count = 0;
    … …  
    2020}
    2121mutex( lock2, lock3 ) count++; // or inline statement
    22 \end{cfacode}
     22\end{cfa}
    2323
    2424\section{Other Languages}
    … …  
    3232An example of \CC scoped\_lock usage is shown in Listing~\ref{l:cc_scoped_lock}.
    3333
    34 \begin{cppcode}[tabsize=3,caption={\CC scoped\_lock usage},label={l:cc_scoped_lock}]
     34\begin{cfa}[tabsize=3,caption={\CC scoped\_lock usage},label={l:cc_scoped_lock}]
    3535std::mutex lock1, lock2, lock3;
    3636{
    … …  
    3838    // locks are released via raii at end of scope
    3939}
    40 \end{cppcode}
     40\end{cfa}
    4141
    4242\section{\CFA implementation}
    … …  
    5858This use case is shown in Listing~\ref{l:sout}.
    5959
    60 \begin{cfacode}[tabsize=3,caption={\CFA sout with mutex statement},label={l:sout}]
     60\begin{cfa}[tabsize=3,caption={\CFA sout with mutex statement},label={l:sout}]
    6161mutex( sout )
    6262    sout | "This output is protected by mutual exclusion!";
    63 \end{cfacode}
     63\end{cfa}
    6464
    6565\section{Deadlock Avoidance}
    … …  
    7070The algorithm presented is taken directly from the source code of the \code{<mutex>} header, with some renaming and comments for clarity.
    7171
    72 \begin{cppcode}[caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}]
     72\begin{cfa}[caption={\CC scoped\_lock deadlock avoidance algorithm},label={l:cc_deadlock_avoid}]
    7373int first = 0;  // first lock to attempt to lock
    7474do {
    … …  
    8686// if first lock is still held then all have been acquired
    8787} while (!locks[first].owns_lock());  // is first lock held?
    88 \end{cppcode}
     88\end{cfa}
    8989
    9090The algorithm in \ref{l:cc_deadlock_avoid} successfully avoids deadlock, however there is a potential livelock scenario.

  • doc/theses/colby_parsons_MMAth/thesis.tex

    rff71057 re02e13f  
    9898\hypersetup{
    9999    plainpages=false,       % needed if Roman numbers in frontpages
    100     unicode=false,          % non-Latin characters in Acrobat’s bookmarks
    101     pdftoolbar=true,        % show Acrobat’s toolbar?
    102     pdfmenubar=true,        % show Acrobat’s menu?
     100    unicode=false,          % non-Latin characters in Acrobat's bookmarks
     101    pdftoolbar=true,        % show Acrobat's toolbar?
     102    pdfmenubar=true,        % show Acrobat's menu?
    103103    pdffitwindow=false,     % window fit to page when opened
    104104    pdfstartview={FitH},    % fits the width of the page to the window
    … …  
    110110    colorlinks=true,        % false: boxed links; true: colored links
    111111    linkcolor=blue,         % color of internal links
    112     citecolor=green,        % color of links to bibliography
     112    citecolor=blue,        % color of links to bibliography
    113113    filecolor=magenta,      % color of file links
    114114    urlcolor=cyan           % color of external links
Note: See TracChangeset for help on using the changeset viewer.