1 | \chapter{\CFA Existing Features} |
---|
2 | |
---|
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 | |
---|
14 | \section{Overloading and \lstinline{extern}} |
---|
15 | \CFA has extensive overloading, allowing multiple definitions of the same name |
---|
16 | to be defined~\cite{Moss18}. |
---|
17 | \begin{cfa} |
---|
18 | char i; int i; double i; |
---|
19 | int f(); double f(); |
---|
20 | void g( int ); void g( double ); |
---|
21 | \end{cfa} |
---|
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: |
---|
27 | \begin{cfa} |
---|
28 | // name mangling |
---|
29 | int i; // _X1ii_1 |
---|
30 | @extern "C"@ { // no name mangling |
---|
31 | int j; // j |
---|
32 | @extern "Cforall"@ { // name mangling |
---|
33 | int k; // _X1ki_1 |
---|
34 | } |
---|
35 | // no name mangling |
---|
36 | } |
---|
37 | // name mangling |
---|
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} |
---|
44 | \CFA adds a rebindable reference type to C, but more expressive than the \Cpp |
---|
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 |
---|
48 | may be assigned using the address-of operator (@&@), which converts the |
---|
49 | reference to a pointer. |
---|
50 | \begin{cfa} |
---|
51 | int i, j; |
---|
52 | int @&@ ri = i, @&&@ rri = ri; |
---|
53 | rri = 3; // auto-dereference assign to i |
---|
54 | @&@ri = @&@j; // rebindable |
---|
55 | ri = 5; // assign to j |
---|
56 | \end{cfa} |
---|
57 | |
---|
58 | \section{Constructors and Destructors} |
---|
59 | |
---|
60 | Both constructors and destructors are operators, which means they are |
---|
61 | functions with special operator names rather than type names in \Cpp. The |
---|
62 | special operator names may be used to call the functions explicitly (not |
---|
63 | allowed in \Cpp for constructors). |
---|
64 | |
---|
65 | In general, operator names in \CFA are constructed by bracketing an operator |
---|
66 | token with @?@, which indicates the position of the arguments. For example, infixed |
---|
67 | multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it |
---|
68 | easy to tell the difference between prefix operations (such as @++?@) and |
---|
69 | post-fix operations (@?++@). |
---|
70 | |
---|
71 | The special name for a constructor is @?{}@, which comes from the |
---|
72 | initialization syntax in C. The special name for a destructor is @^{}@, where |
---|
73 | the @^@ has no special meaning. |
---|
74 | % I don't like the \^{} symbol but $^\wedge$ isn't better. |
---|
75 | \begin{cfa} |
---|
76 | struct T { ... }; |
---|
77 | void ?@{}@(@T &@ this, ...) { ... } // constructor |
---|
78 | void ?@^{}@(@T &@ this, ...) { ... } // destructor |
---|
79 | { |
---|
80 | T s = @{@ ... @}@; // same constructor/initialization braces |
---|
81 | } // destructor call automatically generated |
---|
82 | \end{cfa} |
---|
83 | The first parameter is a reference parameter to the type for the |
---|
84 | constructor/destructor. Destructors may have multiple parameters. The compiler |
---|
85 | implicitly matches an overloaded constructor @void ^?{}(T &, ...);@ to an |
---|
86 | object declaration with associated initialization, and generates a construction |
---|
87 | call after the object is allocated. When an object goes out of scope, the |
---|
88 | matching overloaded destructor @void ^?{}(T &);@ is called. Without explicit |
---|
89 | definition, \CFA creates a default and copy constructor, destructor and |
---|
90 | assignment (like \Cpp). It is possible to define constructors/destructors for |
---|
91 | basic and existing types (unlike \Cpp). |
---|
92 | |
---|
93 | \section{Polymorphism} |
---|
94 | \CFA uses parametric polymorphism to create functions and types that are |
---|
95 | defined over multiple types. \CFA polymorphic declarations serve the same role |
---|
96 | as \Cpp templates or Java generics. The ``parametric'' means the polymorphism is |
---|
97 | accomplished by passing argument operations to associate \emph{parameters} at |
---|
98 | the call site, and these parameters are used in the function to differentiate |
---|
99 | among the types the function operates on. |
---|
100 | |
---|
101 | Polymorphic declarations start with a universal @forall@ clause that goes |
---|
102 | before the standard (monomorphic) declaration. These declarations have the same |
---|
103 | syntax except they may use the universal type names introduced by the @forall@ |
---|
104 | clause. For example, the following is a polymorphic identity function that |
---|
105 | works on any type @T@: |
---|
106 | \begin{cfa} |
---|
107 | @forall( T )@ @T@ identity( @T@ val ) { return val; } |
---|
108 | int forty_two = identity( 42 ); // T bound to int, forty_two == 42 |
---|
109 | \end{cfa} |
---|
110 | |
---|
111 | To allow a polymorphic function to be separately compiled, the type @T@ must be |
---|
112 | constrained by the operations used on @T@ in the function body. The @forall@ |
---|
113 | clauses is augmented with a list of polymorphic variables (local type names) |
---|
114 | and assertions (constraints), which represent the required operations on those |
---|
115 | types used in a function, \eg: |
---|
116 | \begin{cfa} |
---|
117 | forall( T @| { void do_once(T); }@) // assertion |
---|
118 | void do_twice(T value) { |
---|
119 | do_once(value); |
---|
120 | do_once(value); |
---|
121 | } |
---|
122 | void do_once(@int@ i) { ... } // provide assertion |
---|
123 | @int@ i; |
---|
124 | do_twice(i); // implicitly pass assertion do_once to do_twice |
---|
125 | \end{cfa} |
---|
126 | Any object with a type fulfilling the assertion may be passed as an argument to |
---|
127 | a @do_twice@ call. |
---|
128 | |
---|
129 | A polymorphic function can be used in the same way as a normal function. The |
---|
130 | polymorphic variables are filled in with concrete types and the assertions are |
---|
131 | checked. An assertion is checked by verifying each assertion operation (with |
---|
132 | all the variables replaced with the concrete types from the arguments) is |
---|
133 | defined at a call site. |
---|
134 | |
---|
135 | Note, a function named @do_once@ is not required in the scope of @do_twice@ to |
---|
136 | compile it, unlike \Cpp template expansion. Furthermore, call-site inferencing |
---|
137 | allows local replacement of the most specific parametric functions needs for a |
---|
138 | call. |
---|
139 | \begin{cfa} |
---|
140 | void do_once(double y) { ... } // global |
---|
141 | int quadruple(int x) { |
---|
142 | void do_once(int y) { y = y * 2; } // local |
---|
143 | do_twice(x); // using local "do_once" |
---|
144 | return x; |
---|
145 | } |
---|
146 | \end{cfa} |
---|
147 | Specifically, the complier deduces that @do_twice@'s T is an integer from the |
---|
148 | argument @x@. It then looks for the most specific definition matching the |
---|
149 | assertion, which is the nested integral @do_once@ defined within the |
---|
150 | function. The matched assertion function is then passed as a function pointer |
---|
151 | to @do_twice@ and called within it. |
---|
152 | |
---|
153 | To avoid typing long lists of assertions, constraints can be collect into |
---|
154 | convenient packages called a @trait@, which can then be used in an assertion |
---|
155 | instead of the individual constraints. |
---|
156 | \begin{cfa} |
---|
157 | trait done_once(T) { |
---|
158 | void do_once(T); |
---|
159 | } |
---|
160 | \end{cfa} |
---|
161 | and the @forall@ list in the previous example is replaced with the trait. |
---|
162 | \begin{cfa} |
---|
163 | forall(dtype T | @done_once(T)@) |
---|
164 | \end{cfa} |
---|
165 | In general, a trait can contain an arbitrary number of assertions, both |
---|
166 | functions and variables, and are usually used to create a shorthand for, and |
---|
167 | give descriptive names to, common groupings of assertions describing a certain |
---|
168 | functionality, like @sumable@, @listable@, \etc. |
---|
169 | |
---|
170 | Polymorphic structures and unions are defined by qualifying the aggregate type |
---|
171 | with @forall@. The type variables work the same except they are used in field |
---|
172 | declarations instead of parameters, returns, and local variable declarations. |
---|
173 | \begin{cfa} |
---|
174 | forall(dtype @T@) |
---|
175 | struct node { |
---|
176 | node(@T@) * next; // generic linked node |
---|
177 | @T@ * data; |
---|
178 | } |
---|
179 | node(@int@) inode; |
---|
180 | \end{cfa} |
---|
181 | The generic type @node(T)@ is an example of a polymorphic-type usage. Like \Cpp |
---|
182 | template usage, a polymorphic-type usage must specify a type parameter. |
---|
183 | |
---|
184 | There are many other polymorphism features in \CFA but these are the ones used |
---|
185 | by the exception system. |
---|
186 | |
---|
187 | \section{Control Flow} |
---|
188 | \CFA has a number of advanced control-flow features: @generator@, @coroutine@, @monitor@, @mutex@ parameters, and @thread@. |
---|
189 | The two features that interact with |
---|
190 | the exception system are @coroutine@ and @thread@; 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. |
---|
213 | \begin{cfa} |
---|
214 | coroutine CountUp { |
---|
215 | unsigned int next; // communication variable |
---|
216 | } |
---|
217 | CountUp countup; |
---|
218 | \end{cfa} |
---|
219 | Each coroutine has a @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 | } |
---|
229 | } |
---|
230 | \end{cfa} |
---|
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's function. |
---|
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@. |
---|
244 | |
---|
245 | \subsection{Monitor and Mutex Parameter} |
---|
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. |
---|
262 | |
---|
263 | \subsection{Thread} |
---|
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. |
---|
267 | |
---|
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 two basic thread operations are important: fork and join. |
---|
273 | |
---|
274 | Threads are created like coroutines with an associated @main@ function: |
---|
275 | \begin{cfa} |
---|
276 | thread StringWorker { |
---|
277 | const char * input; |
---|
278 | int result; |
---|
279 | }; |
---|
280 | void main(StringWorker & this) { |
---|
281 | const char * localCopy = this.input; |
---|
282 | // ... do some work, perhaps hashing the string ... |
---|
283 | this.result = result; |
---|
284 | } |
---|
285 | { |
---|
286 | StringWorker stringworker; // fork thread running in "main" |
---|
287 | } // implicitly join with thread $\(\Rightarrow\)$ wait for completion |
---|
288 | \end{cfa} |
---|
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. |
---|