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