[4706098c] | 1 | \chapter{\texorpdfstring{\CFA Existing Features}{Cforall Existing Features}} |
---|
[f28fdee] | 2 | |
---|
[6c79bef] | 3 | \CFA (C-for-all)~\cite{Cforall} is an open-source project extending ISO C with |
---|
| 4 | modern safety and productivity features, while still ensuring backwards |
---|
| 5 | compatibility with C and its programmers. \CFA is designed to have an |
---|
| 6 | orthogonal feature-set based closely on the C programming paradigm |
---|
| 7 | (non-object-oriented) and these features can be added incrementally to an |
---|
| 8 | existing C code-base allowing programmers to learn \CFA on an as-needed basis. |
---|
| 9 | |
---|
| 10 | Only those \CFA features pertinent to this thesis are discussed. Many of the |
---|
| 11 | \CFA syntactic and semantic features used in the thesis should be fairly |
---|
| 12 | obvious to the reader. |
---|
| 13 | |
---|
[1c1c180] | 14 | \section{\texorpdfstring{Overloading and \lstinline|extern|} |
---|
| 15 | {Overloading and extern}} |
---|
[6c79bef] | 16 | \CFA has extensive overloading, allowing multiple definitions of the same name |
---|
| 17 | to be defined.~\cite{Moss18} |
---|
[f28fdee] | 18 | \begin{cfa} |
---|
[6c79bef] | 19 | char i; int i; double i; $\C[3.75in]{// variable overload}$ |
---|
| 20 | int f(); double f(); $\C{// return overload}$ |
---|
| 21 | void g( int ); void g( double ); $\C{// parameter overload}\CRT$ |
---|
[f28fdee] | 22 | \end{cfa} |
---|
[6c79bef] | 23 | This feature requires name mangling so the assembly symbols are unique for |
---|
| 24 | different overloads. For compatibility with names in C, there is also a syntax |
---|
| 25 | to disable name mangling. These unmangled names cannot be overloaded but act as |
---|
| 26 | the interface between C and \CFA code. The syntax for disabling/enabling |
---|
| 27 | mangling is: |
---|
[f28fdee] | 28 | \begin{cfa} |
---|
[6c79bef] | 29 | // name mangling |
---|
| 30 | int i; // _X1ii_1 |
---|
| 31 | @extern "C"@ { // no name mangling |
---|
| 32 | int j; // j |
---|
| 33 | @extern "Cforall"@ { // name mangling |
---|
| 34 | int k; // _X1ki_1 |
---|
| 35 | } |
---|
| 36 | // no name mangling |
---|
[6e7b969] | 37 | } |
---|
[6c79bef] | 38 | // name mangling |
---|
| 39 | \end{cfa} |
---|
| 40 | Both forms of @extern@ affect all the declarations within their nested lexical |
---|
| 41 | scope and transition back to the previous mangling state when the lexical scope |
---|
| 42 | ends. |
---|
| 43 | |
---|
| 44 | \section{Reference Type} |
---|
| 45 | \CFA adds a rebindable reference type to C, but more expressive than the \CC |
---|
| 46 | reference. Multi-level references are allowed and act like auto-dereferenced |
---|
| 47 | pointers using the ampersand (@&@) instead of the pointer asterisk (@*@). \CFA |
---|
| 48 | references may also be mutable or non-mutable. If mutable, a reference variable |
---|
| 49 | may be assigned to using the address-of operator (@&@), which converts the |
---|
| 50 | reference to a pointer. |
---|
| 51 | \begin{cfa} |
---|
| 52 | int i, j; |
---|
| 53 | int @&@ ri = i, @&&@ rri = ri; |
---|
| 54 | rri = 3; // auto-dereference assign to i |
---|
| 55 | @&@ri = @&@j; // rebindable |
---|
| 56 | ri = 5; // assign to j |
---|
[f28fdee] | 57 | \end{cfa} |
---|
[6e7b969] | 58 | |
---|
| 59 | \section{Constructors and Destructors} |
---|
| 60 | |
---|
| 61 | Both constructors and destructors are operators, which means they are just |
---|
[6c79bef] | 62 | functions with special operator names rather than type names in \CC. The |
---|
| 63 | special operator names may be used to call the functions explicitly (not |
---|
| 64 | allowed in \CC for constructors). |
---|
| 65 | |
---|
| 66 | In general, operator names in \CFA are constructed by bracketing an operator |
---|
| 67 | token with @?@, which indicates where the arguments. For example, infixed |
---|
| 68 | multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it |
---|
| 69 | easy to tell the difference between prefix operations (such as @++?@) and |
---|
| 70 | post-fix operations (@?++@). |
---|
| 71 | |
---|
| 72 | The special name for a constructor is @?{}@, which comes from the |
---|
| 73 | initialization syntax in C. The special name for a destructor is @^{}@, where |
---|
| 74 | the @^@ has no special meaning. |
---|
| 75 | % I don't like the \^{} symbol but $^\wedge$ isn't better. |
---|
| 76 | \begin{cfa} |
---|
| 77 | struct T { ... }; |
---|
| 78 | void ?@{}@(@T &@ this, ...) { ... } // constructor |
---|
| 79 | void ?@^{}@(@T &@ this, ...) { ... } // destructor |
---|
| 80 | { |
---|
| 81 | T s = @{@ ... @}@; // same constructor/initialization braces |
---|
| 82 | } // destructor call automatically generated |
---|
| 83 | \end{cfa} |
---|
| 84 | The first parameter is a reference parameter to the type for the |
---|
| 85 | constructor/destructor. Destructors may have multiple parameters. The compiler |
---|
| 86 | implicitly matches an overloaded constructor @void ^?{}(T &, ...);@ to an |
---|
| 87 | object declaration with associated initialization, and generates a construction |
---|
| 88 | call after the object is allocated. When an object goes out of scope, the |
---|
| 89 | matching overloaded destructor @void ^?{}(T &);@ is called. Without explicit |
---|
| 90 | definition, \CFA creates a default and copy constructor, destructor and |
---|
| 91 | assignment (like \CC). It is possible to define constructors/destructors for |
---|
| 92 | basic and existing types. |
---|
[6e7b969] | 93 | |
---|
| 94 | \section{Polymorphism} |
---|
[6c79bef] | 95 | \CFA uses parametric polymorphism to create functions and types that are |
---|
| 96 | defined over multiple types. \CFA polymorphic declarations serve the same role |
---|
| 97 | as \CC templates or Java generics. The ``parametric'' means the polymorphism is |
---|
| 98 | accomplished by passing argument operations to associate \emph{parameters} at |
---|
| 99 | the call site, and these parameters are used in the function to differentiate |
---|
| 100 | among the types the function operates on. |
---|
| 101 | |
---|
| 102 | Polymorphic declarations start with a universal @forall@ clause that goes |
---|
| 103 | before the standard (monomorphic) declaration. These declarations have the same |
---|
| 104 | syntax except they may use the universal type names introduced by the @forall@ |
---|
| 105 | clause. For example, the following is a polymorphic identity function that |
---|
| 106 | works on any type @T@: |
---|
| 107 | \begin{cfa} |
---|
| 108 | @forall( T )@ @T@ identity( @T@ val ) { return val; } |
---|
| 109 | int forty_two = identity( 42 ); // T bound to int, forty_two == 42 |
---|
| 110 | \end{cfa} |
---|
[6e7b969] | 111 | |
---|
[6c79bef] | 112 | To allow a polymorphic function to be separately compiled, the type @T@ must be |
---|
| 113 | constrained by the operations used on @T@ in the function body. The @forall@ |
---|
| 114 | clauses is augmented with a list of polymorphic variables (local type names) |
---|
| 115 | and assertions (constraints), which represent the required operations on those |
---|
| 116 | types used in a function, \eg: |
---|
[f28fdee] | 117 | \begin{cfa} |
---|
[6c79bef] | 118 | forall( T @| { void do_once(T); }@) // assertion |
---|
| 119 | void do_twice(T value) { |
---|
| 120 | do_once(value); |
---|
| 121 | do_once(value); |
---|
[6e7b969] | 122 | } |
---|
[6c79bef] | 123 | void do_once(int i) { ... } // provide assertion |
---|
| 124 | int i; |
---|
| 125 | do_twice(i); // implicitly pass assertion do_once to do_twice |
---|
[f28fdee] | 126 | \end{cfa} |
---|
[6c79bef] | 127 | Any object with a type fulfilling the assertion may be passed as an argument to |
---|
| 128 | a @do_twice@ call. |
---|
| 129 | |
---|
| 130 | A polymorphic function can be used in the same way as a normal function. The |
---|
| 131 | polymorphic variables are filled in with concrete types and the assertions are |
---|
| 132 | checked. An assertion is checked by verifying each assertion operation (with |
---|
| 133 | all the variables replaced with the concrete types from the arguments) is |
---|
| 134 | defined at a call site. |
---|
| 135 | |
---|
| 136 | Note, a function named @do_once@ is not required in the scope of @do_twice@ to |
---|
| 137 | compile it, unlike \CC template expansion. Furthermore, call-site inferencing |
---|
| 138 | allows local replacement of the most specific parametric functions needs for a |
---|
| 139 | call. |
---|
[f28fdee] | 140 | \begin{cfa} |
---|
[6c79bef] | 141 | void do_once(double y) { ... } // global |
---|
[6e7b969] | 142 | int quadruple(int x) { |
---|
[6c79bef] | 143 | void do_once(int y) { y = y * 2; } // local |
---|
| 144 | do_twice(x); // using local "do_once" |
---|
| 145 | return x; |
---|
[6e7b969] | 146 | } |
---|
[f28fdee] | 147 | \end{cfa} |
---|
[6c79bef] | 148 | Specifically, the complier deduces that @do_twice@'s T is an integer from the |
---|
| 149 | argument @x@. It then looks for the most specific definition matching the |
---|
| 150 | assertion, which is the nested integral @do_once@ defined within the |
---|
| 151 | function. The matched assertion function is then passed as a function pointer |
---|
| 152 | to @do_twice@ and called within it. |
---|
| 153 | |
---|
| 154 | To avoid typing long lists of assertions, constraints can be collect into |
---|
| 155 | convenient packages called a @trait@, which can then be used in an assertion |
---|
| 156 | instead of the individual constraints. |
---|
[f28fdee] | 157 | \begin{cfa} |
---|
[6c79bef] | 158 | trait done_once(T) { |
---|
| 159 | void do_once(T); |
---|
[6e7b969] | 160 | } |
---|
[f28fdee] | 161 | \end{cfa} |
---|
[6c79bef] | 162 | and the @forall@ list in the previous example is replaced with the trait. |
---|
[f28fdee] | 163 | \begin{cfa} |
---|
[6c79bef] | 164 | forall(dtype T | @done_once(T)@) |
---|
[f28fdee] | 165 | \end{cfa} |
---|
[6c79bef] | 166 | In general, a trait can contain an arbitrary number of assertions, both |
---|
| 167 | functions and variables, and are usually used to create a shorthand for, and |
---|
| 168 | give descriptive names to, common groupings of assertions describing a certain |
---|
| 169 | functionality, like @sumable@, @listable@, \etc. |
---|
| 170 | |
---|
| 171 | Polymorphic structures and unions are defined by qualifying the aggregate type |
---|
| 172 | with @forall@. The type variables work the same except they are used in field |
---|
| 173 | declarations instead of parameters, returns, and local variable declarations. |
---|
[f28fdee] | 174 | \begin{cfa} |
---|
[6e7b969] | 175 | forall(dtype T) |
---|
| 176 | struct node { |
---|
[6c79bef] | 177 | node(T) * next; // generic linked node |
---|
| 178 | T * data; |
---|
[6e7b969] | 179 | } |
---|
[f28fdee] | 180 | \end{cfa} |
---|
[6c79bef] | 181 | The generic type @node(T)@ is an example of a polymorphic-type usage. Like \CC |
---|
| 182 | templates usage, a polymorphic-type usage must specify a type parameter. |
---|
[6e7b969] | 183 | |
---|
[6c79bef] | 184 | There are many other polymorphism features in \CFA but these are the ones used |
---|
| 185 | by the exception system. |
---|
[6e7b969] | 186 | |
---|
| 187 | \section{Concurrency} |
---|
[6c79bef] | 188 | \CFA has a number of concurrency features: @thread@, @monitor@, @mutex@ |
---|
| 189 | parameters, @coroutine@ and @generator@. The two features that interact with |
---|
| 190 | the exception system are @thread@ and @coroutine@; they and their supporting |
---|
| 191 | constructs are described here. |
---|
| 192 | |
---|
| 193 | \subsection{Coroutine} |
---|
| 194 | A coroutine is a type with associated functions, where the functions are not |
---|
| 195 | required to finish execution when control is handed back to the caller. Instead |
---|
| 196 | they may suspend execution at any time and be resumed later at the point of |
---|
| 197 | last suspension. (Generators are stackless and coroutines are stackful.) These |
---|
| 198 | types are not concurrent but share some similarities along with common |
---|
| 199 | underpinnings, so they are combined with the \CFA threading library. Further |
---|
| 200 | discussion in this section only refers to the coroutine because generators are |
---|
| 201 | similar. |
---|
| 202 | |
---|
| 203 | In \CFA, a coroutine is created using the @coroutine@ keyword, which is an |
---|
| 204 | aggregate type like @struct,@ except the structure is implicitly modified by |
---|
| 205 | the compiler to satisfy the @is_coroutine@ trait; hence, a coroutine is |
---|
| 206 | restricted by the type system to types that provide this special trait. The |
---|
| 207 | coroutine structure acts as the interface between callers and the coroutine, |
---|
| 208 | and its fields are used to pass information in and out of coroutine interface |
---|
| 209 | functions. |
---|
| 210 | |
---|
| 211 | Here is a simple example where a single field is used to pass (communicate) the |
---|
| 212 | next number in a sequence. |
---|
[f28fdee] | 213 | \begin{cfa} |
---|
[6e7b969] | 214 | coroutine CountUp { |
---|
[6c79bef] | 215 | unsigned int next; // communication variable |
---|
[6e7b969] | 216 | } |
---|
[6c79bef] | 217 | CountUp countup; |
---|
[f28fdee] | 218 | \end{cfa} |
---|
[6c79bef] | 219 | Each coroutine has @main@ function, which takes a reference to a coroutine |
---|
| 220 | object and returns @void@. |
---|
| 221 | \begin{cfa}[numbers=left] |
---|
| 222 | void main(@CountUp & this@) { // argument matches trait is_coroutine |
---|
| 223 | unsigned int up = 0; // retained between calls |
---|
| 224 | while (true) { |
---|
| 225 | next = up; // make "up" available outside function |
---|
| 226 | @suspend;@$\label{suspend}$ |
---|
| 227 | up += 1; |
---|
| 228 | } |
---|
[6e7b969] | 229 | } |
---|
[f28fdee] | 230 | \end{cfa} |
---|
[6c79bef] | 231 | In this function, or functions called by this function (helper functions), the |
---|
| 232 | @suspend@ statement is used to return execution to the coroutine's caller |
---|
| 233 | without terminating the coroutine. |
---|
| 234 | |
---|
| 235 | A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@. |
---|
| 236 | The first resume calls the @main@ function at the top. Thereafter, resume calls |
---|
| 237 | continue a coroutine in the last suspended function after the @suspend@ |
---|
| 238 | statement, in this case @main@ line~\ref{suspend}. The @resume@ function takes |
---|
| 239 | a reference to the coroutine structure and returns the same reference. The |
---|
| 240 | return value allows easy access to communication variables defined in the |
---|
| 241 | coroutine object. For example, the @next@ value for coroutine object @countup@ |
---|
| 242 | is both generated and collected in the single expression: |
---|
| 243 | @resume(countup).next@. |
---|
[6e7b969] | 244 | |
---|
| 245 | \subsection{Monitors and Mutex} |
---|
[6c79bef] | 246 | Concurrency does not guarantee ordering; without ordering results are |
---|
| 247 | non-deterministic. To claw back ordering, \CFA uses monitors and @mutex@ |
---|
| 248 | (mutual exclusion) parameters. A monitor is another kind of aggregate, where |
---|
| 249 | the compiler implicitly inserts a lock and instances are compatible with |
---|
| 250 | @mutex@ parameters. |
---|
| 251 | |
---|
| 252 | A function that requires deterministic (ordered) execution, acquires mutual |
---|
| 253 | exclusion on a monitor object by qualifying an object reference parameter with |
---|
| 254 | @mutex@. |
---|
| 255 | \begin{cfa} |
---|
| 256 | void example(MonitorA & @mutex@ argA, MonitorB & @mutex@ argB); |
---|
| 257 | \end{cfa} |
---|
| 258 | When the function is called, it implicitly acquires the monitor lock for all of |
---|
| 259 | the mutex parameters without deadlock. This semantics means all functions with |
---|
| 260 | the same mutex type(s) are part of a critical section for objects of that type |
---|
| 261 | and only one runs at a time. |
---|
[6e7b969] | 262 | |
---|
[6c79bef] | 263 | \subsection{Threads} |
---|
| 264 | Functions, generators, and coroutines are sequential so there is only a single |
---|
| 265 | (but potentially sophisticated) execution path in a program. Threads introduce |
---|
| 266 | multiple execution paths that continue independently. |
---|
[6e7b969] | 267 | |
---|
[6c79bef] | 268 | For threads to work safely with objects requires mutual exclusion using |
---|
| 269 | monitors and mutex parameters. For threads to work safely with other threads, |
---|
| 270 | also requires mutual exclusion in the form of a communication rendezvous, which |
---|
| 271 | also supports internal synchronization as for mutex objects. For exceptions |
---|
| 272 | only the basic two basic operations are important: thread fork and join. |
---|
[6e7b969] | 273 | |
---|
[6c79bef] | 274 | Threads are created like coroutines with an associated @main@ function: |
---|
[f28fdee] | 275 | \begin{cfa} |
---|
[6e7b969] | 276 | thread StringWorker { |
---|
[6c79bef] | 277 | const char * input; |
---|
| 278 | int result; |
---|
[6e7b969] | 279 | }; |
---|
| 280 | void main(StringWorker & this) { |
---|
[6c79bef] | 281 | const char * localCopy = this.input; |
---|
| 282 | // ... do some work, perhaps hashing the string ... |
---|
| 283 | this.result = result; |
---|
[6e7b969] | 284 | } |
---|
[6c79bef] | 285 | { |
---|
| 286 | StringWorker stringworker; // fork thread running in "main" |
---|
| 287 | } // implicitly join with thread $\(\Rightarrow\)$ wait for completion |
---|
[f28fdee] | 288 | \end{cfa} |
---|
[6c79bef] | 289 | The thread main is where a new thread starts execution after a fork operation |
---|
| 290 | and then the thread continues executing until it is finished. If another thread |
---|
| 291 | joins with an executing thread, it waits until the executing main completes |
---|
| 292 | execution. In other words, everything a thread does is between a fork and join. |
---|
| 293 | |
---|
| 294 | From the outside, this behaviour is accomplished through creation and |
---|
| 295 | destruction of a thread object. Implicitly, fork happens after a thread |
---|
| 296 | object's constructor is run and join happens before the destructor runs. Join |
---|
| 297 | can also be specified explicitly using the @join@ function to wait for a |
---|
| 298 | thread's completion independently from its deallocation (\ie destructor |
---|
| 299 | call). If @join@ is called explicitly, the destructor does not implicitly join. |
---|