source: doc/theses/andrew_beach_MMath/existing.tex @ 29c9b23

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since 29c9b23 was 29c9b23, checked in by Andrew Beach <ajbeach@…>, 9 months ago

Andrew MMath: Supposed to be focused on features but it ended up leaking out.

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