Changeset 0720e049 for doc


Ignore:
Timestamp:
Aug 11, 2017, 10:33:37 AM (8 years ago)
Author:
Rob Schluntz <rschlunt@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
54cd58b0
Parents:
3d4b23fa (diff), 59a75cb (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:/u/cforall/software/cfa/cfa-cc

Location:
doc
Files:
4 added
2 deleted
14 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/common.tex

    r3d4b23fa r0720e049  
    1111%% Created On       : Sat Apr  9 10:06:17 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Thu Jul 13 11:44:59 2017
    14 %% Update Count     : 335
     13%% Last Modified On : Mon Jul 24 21:02:14 2017
     14%% Update Count     : 352
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    134134
    135135% inline text and code index (cannot use ©)
    136 \newcommand{\Indexc}[1]{\lstinline$#1$\index{#1@\lstinline$#1$}}
     136\newcommand{\Indexc}[2][\@empty]{\lstinline[#1]$#2$\index{#2@\lstinline[#1]$#2$}}
    137137% code index (cannot use ©)
    138 \newcommand{\indexc}[1]{\index{#1@\lstinline$#1$}}
     138\newcommand{\indexc}[2][\@empty]{\index{#2@\lstinline[#1]$#2$}}
    139139
    140140% Denote newterms in particular font and index them without particular font and in lowercase, e.g., \newterm{abc}.
    … …  
    234234basicstyle=\linespread{0.9}\sf,                                                 % reduce line spacing and use sanserif font
    235235stringstyle=\tt,                                                                                % use typewriter font
    236 tabsize=6,                                                                                              % N space tabbing
     236tabsize=5,                                                                                              % N space tabbing
    237237xleftmargin=\parindentlnth,                                                             % indent code to paragraph indentation
    238238extendedchars=true,                                                                             % allow ASCII characters in the range 128-255

  • doc/LaTeXmacros/lstlang.sty

    r3d4b23fa r0720e049  
    88%% Created On       : Sat May 13 16:34:42 2017
    99%% Last Modified By : Peter A. Buhr
    10 %% Last Modified On : Wed Jul 12 22:42:09 2017
    11 %% Update Count     : 12
     10%% Last Modified On : Mon Jul 24 20:40:37 2017
     11%% Update Count     : 13
    1212%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1313
    … …  
    112112                finally, forall, ftype, _Generic, _Imaginary, inline, __label__, lvalue, _Noreturn, one_t,
    113113                otype, restrict, _Static_assert, throw, throwResume, trait, try, ttype, typeof, __typeof,
    114                 __typeof__, with, zero_t},
     114                __typeof__, virtual, with, zero_t},
    115115        morekeywords=[2]{
    116116                _Atomic, coroutine, is_coroutine, is_monitor, is_thread, monitor, mutex, nomutex,

  • doc/generic_types/generic_types.tex

    r3d4b23fa r0720e049  
    4949
    5050% Useful macros
    51 \newcommand{\CFA}{C\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\hspace{-1pt}\xspace} % Cforall symbolic name
    52 %\newcommand{\CFA}{C$\mathbf\forall$\xspace} % Cforall symbolic name
    53 \newcommand{\CC}{\rm C\kern-.1em\hbox{+\kern-.25em+}\xspace} % C++ symbolic name
    54 \newcommand{\CCeleven}{\rm C\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name
    55 \newcommand{\CCfourteen}{\rm C\kern-.1em\hbox{+\kern-.25em+}14\xspace} % C++14 symbolic name
    56 \newcommand{\CCseventeen}{\rm C\kern-.1em\hbox{+\kern-.25em+}17\xspace} % C++17 symbolic name
    57 \newcommand{\CCtwenty}{\rm C\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
     51\newcommand{\CFAIcon}{\textsf{C}\raisebox{\depth}{\rotatebox{180}{\textsf{A}}}\xspace} % Cforall symbolic name
     52\newcommand{\CFA}{\protect\CFAIcon} % safe for section/caption
     53\newcommand{\CC}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}\xspace} % C++ symbolic name
     54\newcommand{\CCeleven}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}11\xspace} % C++11 symbolic name
     55\newcommand{\CCfourteen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}14\xspace} % C++14 symbolic name
     56\newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17\xspace} % C++17 symbolic name
     57\newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20\xspace} % C++20 symbolic name
    5858\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj\xspace} % C++ virtual symbolic name
    5959\newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}\xspace} % C# symbolic name
    … …  
    443443This function could acquire the layout for @set(T)@ by calling its layout function with the layout of @T@ implicitly passed into the function.
    444444
    445 Whether a type is concrete, dtype-static, or dynamic is decided solely on the type parameters and @forall@ clause on a declaration.
    446 This design allows opaque forward declarations of generic types, \eg @forall(otype T) struct Box@ -- like in C, all uses of @Box(T)@ can be separately compiled, and callers from other translation units know the proper calling conventions to use.
    447 If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T) struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off.
     445Whether a type is concrete, dtype-static, or dynamic is decided solely on the @forall@'s type parameters.
     446This design allows opaque forward declarations of generic types, \eg @forall(otype T)@ @struct Box@ -- like in C, all uses of @Box(T)@ can be separately compiled, and callers from other translation units know the proper calling conventions to use.
     447If the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static (\eg @forall(otype T)@ @struct unique_ptr { T * p }@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in the existing design is judged to be an appropriate trade-off.
    448448
    449449
    … …  
    855855}
    856856\end{lstlisting}
     857\begin{sloppypar}
    857858Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@.
     859\end{sloppypar}
    858860
    859861\begin{comment}

  • doc/proposals/concurrency/text/concurrency.tex

    r3d4b23fa r0720e049  
    44% ======================================================================
    55% ======================================================================
    6 Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account. 
    7 
    8 Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}. 
    9 
    10 An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA. 
     6Several tool can be used to solve concurrency challenges. Since many of these challenges appear with the use of mutable shared-state, some languages and libraries simply disallow mutable shared-state (Erlang~\cite{Erlang}, Haskell~\cite{Haskell}, Akka (Scala)~\cite{Akka}). In these paradigms, interaction among concurrent objects relies on message passing~\cite{Thoth,Harmony,V-Kernel} or other paradigms that closely relate to networking concepts (channels\cit for example). However, in languages that use routine calls as their core abstraction-mechanism, these approaches force a clear distinction between concurrent and non-concurrent paradigms (i.e., message passing versus routine call). This distinction in turn means that, in order to be effective, programmers need to learn two sets of designs patterns. While this distinction can be hidden away in library code, effective use of the librairy still has to take both paradigms into account.
     7
     8Approaches based on shared memory are more closely related to non-concurrent paradigms since they often rely on basic constructs like routine calls and shared objects. At the lowest level, concurrent paradigms are implemented as atomic operations and locks. Many such mechanisms have been proposed, including semaphores~\cite{Dijkstra68b} and path expressions~\cite{Campbell74}. However, for productivity reasons it is desireable to have a higher-level construct be the core concurrency paradigm~\cite{HPP:Study}.
     9
     10An approach that is worth mentionning because it is gaining in popularity is transactionnal memory~\cite{Dice10}[Check citation]. While this approach is even pursued by system languages like \CC\cit, the performance and feature set is currently too restrictive to be the main concurrency paradigm for general purpose language, which is why it was rejected as the core paradigm for concurrency in \CFA.
    1111
    1212One of the most natural, elegant, and efficient mechanisms for synchronization and communication, especially for shared memory systems, is the \emph{monitor}. Monitors were first proposed by Brinch Hansen~\cite{Hansen73} and later described and extended by C.A.R.~Hoare~\cite{Hoare74}. Many programming languages---e.g., Concurrent Pascal~\cite{ConcurrentPascal}, Mesa~\cite{Mesa}, Modula~\cite{Modula-2}, Turing~\cite{Turing:old}, Modula-3~\cite{Modula-3}, NeWS~\cite{NeWS}, Emerald~\cite{Emerald}, \uC~\cite{Buhr92a} and Java~\cite{Java}---provide monitors as explicit language constructs. In addition, operating-system kernels and device drivers have a monitor-like structure, although they often use lower-level primitives such as semaphores or locks to simulate monitors. For these reasons, this project proposes monitors as the core concurrency-construct.
    … …  
    101101        }
    102102\end{cfacode}
    103 The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order. 
     103The multi-acquisition monitor lock allows a monitor lock to be acquired by both \code{bar} or \code{baz} and acquired again in \code{foo}. In the calls to \code{bar} and \code{baz} the monitors are acquired in opposite order.
    104104
    105105However, such use leads the lock acquiring order problem. In the example above, the user uses implicit ordering in the case of function \code{foo} but explicit ordering in the case of \code{bar} and \code{baz}. This subtle mistake means that calling these routines concurrently may lead to deadlock and is therefore undefined behavior. As shown on several occasion\cit, solving this problem requires:
    … …  
    169169\end{tabular}
    170170\end{center}
    171 Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting. 
     171Notice how the counter is used without any explicit synchronisation and yet supports thread-safe semantics for both reading and writting.
    172172
    173173% ======================================================================
    … …  
    178178Depending on the choice of semantics for when monitor locks are acquired, interaction between monitors and \CFA's concept of polymorphism can be complex to support. However, it is shown that entry-point locking solves most of the issues.
    179179
    180 First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines. 
    181 
    182 Before looking into complex control flow, it is important to present the difference between the two acquiring options : \gls{callsite-locking} and \gls{entry-point-locking}, i.e. acquiring the monitors before making a mutex routine call or as the first instruction of the mutex routine call. For example:
     180First of all, interaction between \code{otype} polymorphism and monitors is impossible since monitors do not support copying. Therefore, the main question is how to support \code{dtype} polymorphism. Since a monitor's main purpose is to ensure mutual exclusion when accessing shared data, this implies that mutual exclusion is only required for routines that do in fact access shared data. However, since \code{dtype} polymorphism always handles incomplete types (by definition), no \code{dtype} polymorphic routine can access shared data since the data requires knowledge about the type. Therefore, the only concern when combining \code{dtype} polymorphism and monitors is to protect access to routines.
     181
     182Before looking into complex control-flow, it is important to present the difference between the two acquiring options : callsite and entry-point locking, i.e. acquiring the monitors before making a mutex routine call or as the first operation of the mutex routine-call. For example:
    183183\begin{center}
    184184\setlength\tabcolsep{1.5pt}
    … …  
    245245\end{center}
    246246
    247 \Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else. Note that the \code{mutex} keyword relies on the resolver rather than another form of language, which mean that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
     247\Gls{callsite-locking} is inefficient, since any \code{dtype} routine may have to obtain some lock before calling a routine, depending on whether or not the type passed is a monitor. However, with \gls{entry-point-locking} calling a monitor routine becomes exactly the same as calling it from anywhere else.
     248
     249Note the \code{mutex} keyword relies on the resolver, which means that in cases where a generic monitor routine is actually desired, writing a mutex routine is possible with the proper trait. This is possible because monitors are designed in terms a trait. For example:
    248250\begin{cfacode}
    249251//Incorrect
    250252//T is not a monitor
    251253forall(dtype T)
    252 void foo(T * mutex t); 
     254void foo(T * mutex t);
    253255
    254256//Correct
    255 //this function only works on monitors 
     257//this function only works on monitors
    256258//(any monitor)
    257259forall(dtype T | is_monitor(T))
    258 void bar(T * mutex t)); 
     260void bar(T * mutex t));
    259261\end{cfacode}
    260262
    … …  
    267269In addition to mutual exclusion, the monitors at the core of \CFA's concurrency can also be used to achieve synchronisation. With monitors, this is generally achieved with internal or external scheduling as in\cit. Since internal scheduling of single monitors is mostly a solved problem, this proposal concentraits on extending internal scheduling to multiple monitors at once. Indeed, like the \gls{group-acquire} semantics, internal scheduling extends to multiple monitors at once in a way that is natural to the user but requires additional complexity on the implementation side.
    268270
    269 First, Here is a simple example of such a technique:
     271First, here is a simple example of such a technique:
    270272
    271273\begin{cfacode}
    … …  
    289291\end{cfacode}
    290292
    291 There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering. 
     293There are two details to note here. First, there \code{signal} is a delayed operation, it only unblocks the waiting thread when it reaches the end of the critical section. This is needed to respect mutual-exclusion. Second, in \CFA, \code{condition} have no particular need to be stored inside a monitor, beyond any software engineering reasons. Here routine \code{foo} waits for the \code{signal} from \code{bar} before making further progress, effectively ensuring a basic ordering.
    292294
    293295An important aspect to take into account here is that \CFA does not allow barging, which means that once function \code{bar} releases the monitor, foo is guaranteed to resume immediately after (unless some other thread waited on the same condition). This guarantees offers the benefit of not having to loop arount waits in order to guarantee that a condition is still met. The main reason \CFA offers this guarantee is that users can easily introduce barging if it becomes a necessity but adding barging prevention or barging avoidance is more involved without language support. Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design of \CFA concurrency.
    … …  
    317319\end{pseudo}
    318320\end{multicols}
    319 
    320 The previous example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention.
     321The example shows the simple case of having two threads (one for each column) and a single monitor A. One thread acquires before waiting (atomically blocking and releasing A) and the other acquires before signalling. There is an important thing to note here, both \code{wait} and \code{signal} must be called with the proper monitor(s) already acquired. This restriction is hidden on the user side in \uC, as it is a logical requirement for barging prevention.
    321322
    322323A direct extension of the previous example is the \gls{group-acquire} version:
    … …  
    337338\end{pseudo}
    338339\end{multicols}
    339 
    340340This version uses \gls{group-acquire} (denoted using the \& symbol), but the presence of multiple monitors does not add a particularly new meaning. Synchronization happens between the two threads in exactly the same way and order. The only difference is that mutual exclusion covers more monitors. On the implementation side, handling multiple monitors does add a degree of complexity as the next few examples demonstrate.
    341341
    … …  
    397397\end{center}
    398398
    399 It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 17), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. We are therefore left with three options:
     399It is particularly important to pay attention to code sections 8 and 3, which are where the existing semantics of internal scheduling need to be extended for multiple monitors. The root of the problem is that \gls{group-acquire} is used in a context where one of the monitors is already acquired and is why it is important to define the behaviour of the previous pseudo-code. When the signaller thread reaches the location where it should "release A \& B" (line 16), it must actually transfer ownership of monitor B to the waiting thread. This ownership trasnfer is required in order to prevent barging. Since the signalling thread still needs the monitor A, simply waking up the waiting thread is not an option because it would violate mutual exclusion. There are three options:
    400400
    401401\subsubsection{Delaying signals}
    402 The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed is what fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single groupd of object. Effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
     402The first more obvious solution to solve the problem of multi-monitor scheduling is to keep ownership of all locks until the last lock is ready to be transferred. It can be argued that that moment is the correct time to transfer ownership when the last lock is no longer needed because this semantics fits most closely to the behaviour of single monitor scheduling. This solution has the main benefit of transferring ownership of groups of monitors, which simplifies the semantics from mutiple objects to a single group of object, effectively making the existing single monitor semantic viable by simply changing monitors to monitor collections.
    403403\begin{multicols}{2}
    404404Waiter
    … …  
    424424\end{pseudo}
    425425\end{multicols}
    426 However, this solution can become much more complicated depending on what is executed while secretly holding B. Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
     426However, this solution can become much more complicated depending on what is executed while secretly holding B (at line 10). Indeed, nothing prevents a user from signalling monitor A on a different condition variable:
    427427\newpage
    428428\begin{multicols}{2}
    … …  
    459459\end{multicols}
    460460
    461 The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen. Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
    462 
    463 \paragraph{Case 1: thread 1 will go first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.
    464 \paragraph{Case 2: thread 2 will go first.} In this case, the problem is that monitor B needs to be passed to thread 1. This can be done directly or using thread 2 as an intermediate.
     461The goal in this solution is to avoid the need to transfer ownership of a subset of the condition monitors. However, this goal is unreacheable in the previous example. Depending on the order of signals (line 12 and 15) two cases can happen.
     462
     463\paragraph{Case 1: thread 1 goes first.} In this case, the problem is that monitor A needs to be passed to thread 2 when thread 1 is done with it.
     464\paragraph{Case 2: thread 2 goes first.} In this case, the problem is that monitor B needs to be passed to thread 1, which can be done directly or using thread 2 as an intermediate.
    465465\\
    466466
     467Note that ordering is not determined by a race condition but by whether signalled threads are enqueued in FIFO or FILO order. However, regardless of the answer, users can move line 15 before line 11 and get the reverse effect.
     468
    467469In both cases however, the threads need to be able to distinguish on a per monitor basis which ones need to be released and which ones need to be transferred. Which means monitors cannot be handled as a single homogenous group.
    468470
    469471\subsubsection{Dependency graphs}
    470 In the Listing 1 pseudo-code, there is a solution which would statisfy both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example the following code which is just a direct extension to three monitors requires at least three ownership transfer and has multiple solutions:
     472In the Listing 1 pseudo-code, there is a solution which statisfies both barging prevention and mutual exclusion. If ownership of both monitors is transferred to the waiter when the signaller releases A and then the waiter transfers back ownership of A when it releases it then the problem is solved. Dynamically finding the correct order is therefore the second possible solution. The problem it encounters is that it effectively boils down to resolving a dependency graph of ownership requirements. Here even the simplest of code snippets requires two transfers and it seems to increase in a manner closer to polynomial. For example, the following code, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions:
    471473
    472474\begin{multicols}{2}
    … …  
    496498
    497499\subsubsection{Partial signalling}
    498 Finally, the solution that was chosen for \CFA is to use partial signalling. Consider the following case:
     500Finally, the solution that is chosen for \CFA is to use partial signalling. Consider the following case:
    499501
    500502\begin{multicols}{2}
    … …  
    518520\end{pseudo}
    519521\end{multicols}
    520 
    521 The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated in to only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
     522The partial signalling solution transfers ownership of monitor B at lines 10 but does not wake the waiting thread since it is still using monitor A. Only when it reaches line 11 does it actually wakeup the waiting thread. This solution has the benefit that complexity is encapsulated into only two actions, passing monitors to the next owner when they should be release and conditionnaly waking threads if all conditions are met. Contrary to the other solutions, this solution quickly hits an upper bound on complexity of implementation.
    522523
    523524% ======================================================================
    … …  
    526527% ======================================================================
    527528% ======================================================================
    528 An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation. This is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
     529An important note is that, until now, signalling a monitor was a delayed operation. The ownership of the monitor is transferred only when the monitor would have otherwise been released, not at the point of the \code{signal} statement. However, in some cases, it may be more convenient for users to immediately transfer ownership to the thread that is waiting for cooperation, which is achieved using the \code{signal_block} routine\footnote{name to be discussed}.
    529530
    530531For example here is an example highlighting the difference in behaviour:
    … …  
    625626        bool inUse;
    626627public:
    627         void P() { 
    628                 if(inUse) wait(c); 
     628        void P() {
     629                if(inUse) wait(c);
    629630                inUse = true;
    630631        }
    631         void V() { 
    632                 inUse = false;         
    633                 signal(c); 
     632        void V() {
     633                inUse = false;
     634                signal(c);
    634635        }
    635636}
    … …  
    639640        bool inUse;
    640641public:
    641         void P() { 
    642                 if(inUse) _Accept(V); 
     642        void P() {
     643                if(inUse) _Accept(V);
    643644                inUse = true;
    644645        }
    645         void g() { 
     646        void g() {
    646647                inUse = false;
    647648

  • doc/proposals/concurrency/version

    r3d4b23fa r0720e049  
    1 0.9.119
     10.9.122

  • doc/proposals/virtual.txt

    r3d4b23fa r0720e049  
    11Proposal for virtual functionality
     2
     3There are two types of virtual inheritance in this proposal, relaxed
     4(implicit) and strict (explicit). Relaxed is the simpler case that uses the
     5existing trait system with the addition of trait references and vtables.
     6Strict adds some constraints and requires some additional notation but allows
     7for down-casting.
     8
     9Relaxed Virtual Inheritance:
    210
    311Imagine the following code :
    … …  
    2028void draw(line*);
    2129
    22 While all the members of this simple UI support drawing creating a UI that easily
    23 supports both these UI requires some tedious boiler-plate code :
     30While all the members of this simple UI support drawing, creating a UI that
     31easily supports both these UI requires some tedious boiler-plate code:
    2432
    2533enum type_t { text, line };
    … …  
    4149}
    4250
    43 While this code will work as indented, adding any new widgets or any new widget behaviors
    44 requires changing existing code to add the desired functionality. To ease this maintenance
    45 effort required CFA introduces the concept of dynamic types, in a manner similar to C++.
    46 
    47 A simple usage of dynamic type with the previous example would look like :
    48 
    49 drawable* objects[10];
     51While this code will work as implemented, adding any new widgets or any new
     52widget behaviors requires changing existing code to add the desired
     53functionality. To ease this maintenance effort required CFA introduces the
     54concept of trait references.
     55
     56Using trait references to implement the above gives the following :
     57
     58trait drawable objects[10];
    5059fill_objects(objects);
    5160
    5261while(running) {
    53       for(drawable* object : objects) {
     62      for(drawable object : objects) {
    5463            draw(object);
    5564      }
    5665}
    5766
    58 However, this is not currently do-able in the current CFA and furthermore is not
    59 possible to implement statically. Therefore we need to add a new feature to handle
    60 having dynamic types like this (That is types that are found dynamically not types
    61 that change dynamically).
    62 
    63 C++ uses inheritance and virtual functions to find the
    64 desired type dynamically. CFA takes inspiration from this solution.
    65 
    66 What we really want to do is express the fact that calling draw() on a object
    67 should find the dynamic type of the parameter before calling the routine, much like the
    68 hand written example given above. We can express this by adding the virtual keyword on
    69 the parameter of the constraints on our trait:
     67The keyword trait is optional (by the same rules as the struct keyword). This
     68is not currently supported in CFA and the lookup is not possible to implement
     69statically. Therefore we need to add a new feature to handle having dynamic
     70lookups like this.
     71
     72What we really want to do is express the fact that calling draw() on a trait
     73reference should find the underlying type of the given parameter and find how
     74it implements the routine, as in the example with the enumeration and union.
     75
     76For instance specifying that the drawable trait reference looks up the type
     77of the first argument to find the implementation would be :
    7078
    7179trait drawable(otype T) {
    … …  
    7381};
    7482
    75 This expresses the idea that drawable is similar to an abstract base class in C++ and
    76 also gives meaning to trying to take a pointer of drawable. That is anything that can
    77 be cast to a drawable pointer has the necessary information to call the draw routine on
    78 that type. Before that drawable was only a abstract type while now it also points to a
    79 piece of storage which specify which behavior the object will have at run time.
    80 
    81 This storage needs to be allocate somewhere. C++ just adds an invisible pointer at
    82 the beginning of the struct but we can do something more explicit for users, actually
    83 have a visible special field :
    84 
    85 struct text {
    86       char* text;
    87       vtable drawable;
    88 };
    89 
    90 struct line{
    91       vtable drawable;
    92       vec2 start;
    93       vec2 end;
    94 };
    95 
    96 With these semantics, adding a "vtable drawable" means that text pointers and line pointers are now
    97 convertible to drawable pointers. This conversion will not necessarily be a type only change however, indeed,
    98 the drawable pointer will point to the field "vtable drawable" not the head of the struct. However, since all
    99 the types are known at compile time, converting pointers becomes a simple offset operations.
    100 
    101 The vtable field contains a pointer to a vtable which contains all the information needed for the caller
    102 to find the function pointer of the desired behavior.
    103 
    104 One of the limitations of this design is that it does not support double dispatching, which
    105 concretely means traits cannot have routines with more than one virtual parameter. This design
    106 would have many ambiguities if it did support multiple virtual parameter. A futher limitation is
    107 that traits over more than one type cannot have vtables meaningfully defined for them, as the
    108 particular vtable to use would be a function of the other type(s) the trait is defined over.
    109 
    110 It is worth noting that the function pointers in these vtables are bound at object construction, rather than
    111 function call-site, as in Cforall's existing polymorphic functions. As such, it is possible that two objects
    112 with the same static type would have a different vtable (consider what happens if draw(line*) is overridden
    113 between the definitions of two line objects). Given that the virtual drawable* erases static types though,
    114 this should not be confusing in practice. A more distressing possibility is that of creating an object that
    115 outlives the scope of one of the functions in its vtable. This is certainly a possible bug, but it is of a
    116 type that C programmers are familiar with, and should be able to avoid by the usual methods.
    117 
    118 Extensibility.
    119 
    120 One of the obvious critics of this implementation is that it lacks extensibility for classes
    121 that cannot be modified (ex: Linux C headers). However this solution can be extended to
    122 allow more extensibility by adding "Fat pointers".
    123 
    124 Indeed, users could already "solve" this issue by writing their own fat pointers as such:
    125 
    126 trait MyContext(otype T) {
    127       void* get_stack(virtual T*)
    128 };
    129 
    130 void* get_stack(ucontext_t *context);
    131 
    132 struct fat_ucontext_t {
    133       vtable MyContext;
    134       ucontext_t *context;
    135 }
    136 
    137 //Tedious forwarding routine
    138 void* get_stack(fat_ucontext_t *ptr) {
    139       return get_stack(ptr->context);
    140 }
    141 
    142 However, users would have to write all the virtual methods they want to override and make
    143 them all simply forward to the existing method that takes the corresponding POCO(Plain Old C Object).
    144 
    145 The alternative we propose is to use language level fat pointers :
    146 
    147 trait MyContext(otype T) {
    148       void* get_stack(virtual T*)
    149 };
    150 
    151 void* get_stack(ucontext_t *context);
    152 
    153 //The type vptr(ucontext_t) all
    154 vptr(ucontext_t) context;
    155 
    156 These behave exactly as the previous example but all the forwarding routines are automatically generated.
    157 
    158 Bikeshedding.
    159 
    160 It may be desirable to add fewer new keywords than discussed in this proposal; it is possible that "virtual"
    161 could replace both "vtable" and "vptr" above with unambiguous contextual meaning. However, for purposes of
    162 clarity in the design discussion it is beneficial to keep the keywords for separate concepts distinct.
    163 
     83This could be implied in simple cases like this one (single parameter on the
     84trait and single generic parameter on the function). In more complex cases it
     85would have to be explicitly given, or a strong convention would have to be
     86enforced (e.g. implementation of trait functions is always drawn from the
     87first polymorphic parameter).
     88
     89Once a function in a trait has been marked as virtual it defines a new
     90function that takes in that trait's reference and then dynamically calls the
     91underlying type implementation. Hence a trait reference becomes a kind of
     92abstract type, cannot be directly instantiated but can still be used.
     93
     94One of the limitations of this design is that it does not support double
     95dispatching, which concretely means traits cannot have routines with more than
     96one virtual parameter. The program must have a single table to look up the
     97function on. Using trait references with traits with more than one parameter
     98is also restricted, initially forbidden, see extension.
     99
     100Extension: Multi-parameter Virtual Traits:
     101
     102This implementation can be extended to traits with multiple parameters if
     103one is called out as being the virtual trait. For example :
     104
     105trait iterator(otype T, dtype Item) {
     106        Maybe(Item) next(virtual T *);
     107}
     108
     109iterator(int) generators[10];
     110
     111Which creates a collection of iterators that produce integers, regardless of
     112how those iterators are implemented. This may require a note that this trait
     113is virtual on T and not Item, but noting it on the functions may be enough.
     114
     115
     116Strict Virtual Inheritance:
     117
     118One powerful feature relaxed virtual does not support is the idea of down
     119casting. Once something has been converted into a trait reference there is
     120very little we can do to recover and of the type information, only the trait's
     121required function implementations are kept.
     122
     123To allow down casting strict virtual requires that all traits and structures
     124involved be organized into a tree. Each trait or struct must have a unique
     125position on this tree (no multiple inheritance).
     126
     127This is declared as follows :
     128
     129trait error(otype T) virtual {
     130        const char * msg(T *);
     131}
     132
     133trait io_error(otype T) virtual error {
     134        FILE * src(T *);
     135}
     136
     137struct eof_error virtual io_error {
     138        FILE * fd;
     139};
     140
     141So the trait error is the head of a new tree and io_error is a child of it.
     142
     143Also the parent trait is implicitly part of the assertions of the children,
     144so all children implement the same operations as the parent. By the unique
     145path down the tree, we can also uniquely order them so that a prefix of a
     146child's vtable has the same format as its parent's.
     147
     148This gives us an important extra feature, runtime checking of the parent-child
     149relationship with a C++ dynamic_cast like operation. Allowing checked
     150conversions from trait references to more particular references, which works
     151if the underlying type is, or is a child of, the new trait type.
     152
     153Extension: Multiple Parents
     154
     155Although each trait/struct must have a unique position on each tree, it could
     156have positions on multiple trees. All this requires is the ability to give
     157multiple parents, as here :
     158
     159trait region(otype T) virtual drawable, collider;
     160
     161The restriction being, the parents must come from different trees. This
     162object (and all of its children) can be cast to either tree. This is handled
     163by generating a separate vtable for each tree the structure is in.
     164
     165Extension: Multi-parameter Strict Virtual
     166
     167If a trait has multiple parameters then one must be called out to be the one
     168we generate separate vtables for, as in :
     169
     170trait example(otype T, otype U) virtual(T) ...
     171
     172This can generate a separate vtable for each U for which all the T+U
     173implementations are provided. These are then separate nodes in the tree (or
     174the root of different trees) as if each was created individually. Providing a
     175single unique instance of these nodes would be the most difficult aspect of
     176this extension, possibly intractable, though with sufficient hoisting and
     177link-once duplication it may be possible.
     178
     179Example:
     180
     181trait argument(otype T) virtual {
     182        char short_name(virtual T *);
     183        bool is_set(virtual T *);
     184};
     185
     186trait value_argument(otype T, otype U) virtual(T) argument {
     187        U get_value(virtual T *);
     188};
     189
     190Extension: Structural Inheritance
     191
     192Currently traits must be the internal nodes and structs the leaf nodes.
     193Structs could be made internal nodes as well, in which case the child structs
     194would likely structurally inherit the fields of their parents.
     195
     196
     197Storing the Virtual Lookup Table (vtable):
     198
     199We have so far been silent on how the vtable is created, stored and accessed.
     200
     201Creation happens at compile time. Function pointers are found by using the
     202same best match rules as elsewhere (additional rules for defaults from the
     203parent may or may not be required). For strict virtual this must happen at the
     204global scope and forbidding static functions, to ensure that a single unique
     205vtable is created. Similarly, there may have to be stricter matching rules
     206for the functions that go into the vtable, possibly requiring an exact match.
     207Relaxed virtual could relax both restrictions, if we allow different vtable
     208at different conversion (struct to trait reference) sites. If it is allowed
     209local functions being bound to a vtable could cause issues when they go out
     210of scope, however this should follow the lifetime rules most C programs
     211already follow implicitly.
     212
     213Most vtables should be stored statically, the only exception being some of
     214the relaxed vtables that could have local function pointers. These may be able
     215to be stack allocated. All vtables should be immutable and require no manual
     216cleanup.
     217
     218Access has two main options:
     219
     220The first is through the use of fat pointers, or a tuple of pointers. When the
     221object is converted to a trait reference, the pointers to its vtables are
     222stored along side it.
     223
     224This allows for compatibility with existing structures (such as those imported
     225from C) and is the default storage method unless a different one is given.
     226
     227The other is by inlining the vtable pointer as "intrusive vtables". This adds
     228a field to the structure to the vtable. The trait reference then has a single
     229pointer to this field, the vtable includes an offset to find the beginning of
     230the structure again.
     231
     232This is used if you specify a vtable field in the structure. If given in the
     233trait the vtable pointer in the trait reference can then become a single
     234pointer to the vtable field and use that to recover the original object
     235pointer as well as retrieve all operations.
     236
     237trait drawable(otype T) {
     238        vtable drawable;
     239};
     240
     241struct line {
     242        vtable drawable;
     243        vec2 start;
     244        vec2 end;
     245};
     246
     247This inline code allows trait references to be converted to plain pointers
     248(although they still must be called specially). The vtable field may just be
     249an opaque block of memory or it may allow user access to the vtable. If so
     250then there should be some way to retrieve the type of the vtable, which will be
     251autogenerated and often unique.
     252
     253
     254Keyword Usage:
     255
     256It may be desirable to add fewer new keywords than discussed in this proposal.
     257It is possible that "virtual" could replace both "vtable" above with
     258unambiguous contextual meaning. However, for purposes of clarity in the design
     259discussion it is beneficial to keep the keywords for separate concepts distinct.
     260
     261
     262Trait References and Operations:
     263
     264sizeof(drawable) will return the size of the trait object itself. However :
     265
     266line a_line;
     267drawable widget = a_line;
     268sizeof(widget);
     269
     270Will instead return the sizeof the underlying object, although the trait must
     271require that its implementation is sized for there to be a meaningful value
     272to return. You may also get the size of the trait reference with
     273
     274sizeof(&widget);
     275
     276Calling free on a trait reference will free the memory for the object. It will
     277leave the vtables alone, as those are (always?) statically allocated.

  • doc/refrat/Makefile

    r3d4b23fa r0720e049  
    99SOURCES = ${addsuffix .tex, \
    1010refrat \
     11keywords \
     12operidents \
    1113}
    1214

  • doc/refrat/refrat.tex

    r3d4b23fa r0720e049  
    1111%% Created On       : Wed Apr  6 14:52:25 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Fri Jun  2 10:43:14 2017
    14 %% Update Count     : 83
     13%% Last Modified On : Sun Aug  6 10:25:31 2017
     14%% Update Count     : 105
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    1717% requires tex packages: texlive-base texlive-latex-base tex-common texlive-humanities texlive-latex-extra texlive-fonts-recommended
    1818
    19 \documentclass[openright,twoside]{report}
     19\documentclass[openright,twoside,11pt]{report}
    2020
    2121%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    … …  
    3737\usepackage{mathptmx}                                   % better math font with "times"
    3838\usepackage[usenames]{color}
    39 \usepackage[pagewise]{lineno}
    40 \renewcommand{\linenumberfont}{\scriptsize\sffamily}
    41 \input{common}                                          % bespoke macros used in the document
     39\input{common}                                          % common CFA document macros
    4240\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    4341\usepackage{breakurl}
    4442\renewcommand{\UrlFont}{\small\sf}
    4543
     44\usepackage[pagewise]{lineno}
     45\renewcommand{\linenumberfont}{\scriptsize\sffamily}
     46\usepackage[firstpage]{draftwatermark}
     47\SetWatermarkLightness{0.9}
     48
     49% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
     50% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
     51% AFTER HYPERREF.
     52\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
     53
    4654\setlength{\topmargin}{-0.45in}                                                 % move running title into header
    4755\setlength{\headsep}{0.25in}
    … …  
    5058
    5159\CFAStyle                                                                                               % use default CFA format-style
     60\lstnewenvironment{C++}[1][]                            % use C++ style
     61{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{®}{®}#1}}
     62{}
    5263
    5364% inline code ©...© (copyright symbol) emacs: C-q M-)
    … …  
    8798
    8899\date{
    89 DRAFT \\ \today
     100\today
    90101}% date
    91102
    … …  
    112123
    113124\clearpage
     125\thispagestyle{plain}
    114126\pdfbookmark[1]{Contents}{section}
    115127\tableofcontents
    116128
    117129\clearpage
     130\thispagestyle{plain}
    118131\pagenumbering{arabic}
    119132
    … …  
    417430
    418431\begin{syntax}
    419 \oldlhs{keyword}
    420 \rhs ©forall©
    421 \rhs ©lvalue©
    422 \rhs ©trait©
    423 \rhs ©dtype©
    424 \rhs ©ftype©
    425 \rhs ©otype©
     432\lhs{keyword} one of
     433\rhs \dots
     434\rhs \input{keywords}
    426435\end{syntax}
    427436
    … …  
    469478
    470479\begin{table}[hbt]
    471 \hfil
    472 \begin{tabular}[t]{ll}
    473 %identifier & operation \\ \hline
    474 ©?[?]© & subscripting \impl{?[?]}\\
    475 ©?()© & function call \impl{?()}\\
    476 ©?++© & postfix increment \impl{?++}\\
    477 ©?--© & postfix decrement \impl{?--}\\
    478 ©++?© & prefix increment \impl{++?}\\
    479 ©--?© & prefix decrement \impl{--?}\\
    480 ©*?© & dereference \impl{*?}\\
    481 ©+?© & unary plus \impl{+?}\\
    482 ©-?© & arithmetic negation \impl{-?}\\
    483 ©~?© & bitwise negation \impl{~?}\\
    484 ©!?© & logical complement \impl{"!?}\\
    485 ©?*?© & multiplication \impl{?*?}\\
    486 ©?/?© & division \impl{?/?}\\
    487 \end{tabular}\hfil
    488 \begin{tabular}[t]{ll}
    489 %identifier & operation \\ \hline
    490 ©?%?© & remainder \impl{?%?}\\
    491 ©?+?© & addition \impl{?+?}\\
    492 ©?-?© & subtraction \impl{?-?}\\
    493 ©?<<?© & left shift \impl{?<<?}\\
    494 ©?>>?© & right shift \impl{?>>?}\\
    495 ©?<?© & less than \impl{?<?}\\
    496 ©?<=?© & less than or equal \impl{?<=?}\\
    497 ©?>=?© & greater than or equal \impl{?>=?}\\
    498 ©?>?© & greater than \impl{?>?}\\
    499 ©?==?© & equality \impl{?==?}\\
    500 ©?!=?© & inequality \impl{?"!=?}\\
    501 ©?&?© & bitwise AND \impl{?&?}\\
    502 \end{tabular}\hfil
    503 \begin{tabular}[t]{ll}
    504 %identifier & operation \\ \hline
    505 ©?^?© & exclusive OR \impl{?^?}\\
    506 ©?|?© & inclusive OR \impl{?"|?}\\
    507 ©?=?© & simple assignment \impl{?=?}\\
    508 ©?*=?© & multiplication assignment \impl{?*=?}\\
    509 ©?/=?© & division assignment \impl{?/=?}\\
    510 ©?%=?© & remainder assignment \impl{?%=?}\\
    511 ©?+=?© & addition assignment \impl{?+=?}\\
    512 ©?-=?© & subtraction assignment \impl{?-=?}\\
    513 ©?<<=?© & left-shift assignment \impl{?<<=?}\\
    514 ©?>>=?© & right-shift assignment \impl{?>>=?}\\
    515 ©?&=?© & bitwise AND assignment \impl{?&=?}\\
    516 ©?^=?© & exclusive OR assignment \impl{?^=?}\\
    517 ©?|=?© & inclusive OR assignment \impl{?"|=?}\\
    518 \end{tabular}
    519 \hfil
     480\centering
     481\input{operidents}
    520482\caption{Operator Identifiers}
    521483\label{opids}

  • doc/rob_thesis/Makefile

    r3d4b23fa r0720e049  
    1 ## Define the appropriate configuration variables.
    2 
    3 TeXLIB = .:../LaTeXmacros:../LaTeXmacros/listings:../LaTeXmacros/enumitem:../bibliography/:
     1TeXLIB = .:../LaTeXmacros:../bibliography/:
    42LaTeX  = TEXINPUTS=${TeXLIB} && export TEXINPUTS && pdflatex -halt-on-error
    53BibTeX = BIBINPUTS=${TeXLIB} && export BIBINPUTS && bibtex
    64
    7 ## Define the text source files.
     5all : thesis.pdf
    86
    9 # SOURCES = ${addsuffix .tex, \
    10 # thesis \
    11 # }
     7thesis.pdf : Makefile ../LaTeXmacros/common.tex cfa-format.tex thesis.tex intro.tex ctordtor.tex tuples.tex variadic.tex conclusions.tex
     8        ${LaTeX} thesis
     9        ${BibTeX} thesis
     10        ${LaTeX} thesis
     11        ${LaTeX} thesis
     12        pdf2ps thesis.pdf thesis.ps
    1213
    13 # FIGURES = ${addsuffix .tex, \
    14 # }
    15 
    16 # PICTURES = ${addsuffix .pstex, \
    17 # }
    18 
    19 # PROGRAMS = ${addsuffix .tex, \
    20 # }
    21 
    22 # GRAPHS = ${addsuffix .tex, \
    23 # }
    24 
    25 # ## Define the documents that need to be made.
    26 
    27 # DOCUMENT = thesis.pdf
    28 
    29 # Directives #
    30 
    31 # all : ${DOCUMENT}
    32 
    33 # clean :
    34 #       rm -f *.bbl *.aux *.dvi *.idx *.ilg *.ind *.brf *.out *.log *.toc *.blg *.pstex_t *.cf \
    35 #               ${FIGURES} ${PICTURES} ${PROGRAMS} ${GRAPHS} ${basename ${DOCUMENT}}.ps ${DOCUMENT}
    36 
    37 # File Dependencies #
    38 
    39 # ${DOCUMENT} : ${basename ${DOCUMENT}}.ps
    40 #       ps2pdf $<
    41 
    42 # ${basename ${DOCUMENT}}.ps : ${basename ${DOCUMENT}}.dvi
    43 #       dvips $< -o $@
    44 
    45 # ${basename ${DOCUMENT}}.dvi : Makefile ${GRAPHS} ${PROGRAMS} ${PICTURES} ${FIGURES} ${SOURCES} ${basename ${DOCUMENT}}.tex \
    46 #               ../LaTeXmacros/common.tex ../LaTeXmacros/indexstyle ../bibliography/cfa.bib
    47 #       # Conditionally create an empty *.ind (index) file for inclusion until makeindex is run.
    48 #       if [ ! -r ${basename $@}.ind ] ; then touch ${basename $@}.ind ; fi
    49 #       # Must have *.aux file containing citations for bibtex
    50 #       if [ ! -r ${basename $@}.aux ] ; then ${LaTeX} ${basename $@}.tex ; fi
    51 #       -${BibTeX} ${basename $@}
    52 #       # Some citations reference others so run steps again to resolve these citations
    53 #       ${LaTeX} ${basename $@}.tex
    54 #       -${BibTeX} ${basename $@}
    55 #       # Make index from *.aux entries and input index at end of document
    56 #       makeindex -s ../LaTeXmacros/indexstyle ${basename $@}.idx
    57 #       ${LaTeX} ${basename $@}.tex
    58 #       # Run again to get index title into table of contents
    59 #       ${LaTeX} ${basename $@}.tex
    60 
    61 # predefined :
    62 #       sed -f predefined.sed ${basename ${DOCUMENT}}.tex > ${basename $@}.cf
    63 
    64 # ## Define the default recipes.
    65 
    66 # %.tex : %.fig
    67 #       fig2dev -L eepic $< > $@
    68 
    69 # %.ps : %.fig
    70 #       fig2dev -L ps $< > $@
    71 
    72 # %.pstex : %.fig
    73 #       fig2dev -L pstex $< > $@
    74 #       fig2dev -L pstex_t -p $@ $< > $@_t
    75 
    76 
    77 all:
    78         $(LaTeX) thesis
    79         $(BibTeX) thesis
    80         $(LaTeX) thesis
    81         $(LaTeX) thesis
    82 
    83 clean:
     14clean :
    8415        rm -f *.aux *.bbl *.blg *.lof *.log *.lot *.out *.toc
    8516
    86 splotless: clean
    87         rm -f thesis.pdf
     17spotless : clean
     18        rm -f thesis.pdf thesis.ps

  • doc/rob_thesis/thesis.tex

    r3d4b23fa r0720e049  
    135135    pdfpagelabels=true,     % adds page number as label in Acrobat's page count
    136136    bookmarks=true,         % show bookmarks bar?
    137     unicode=false,          % non-Latin characters in Acrobat’s bookmarks
    138     pdftoolbar=true,        % show Acrobat’s toolbar?
    139     pdfmenubar=true,        % show Acrobat’s menu?
     137    unicode=false,          % non-Latin characters in Acrobat's bookmarks
     138    pdftoolbar=true,        % show Acrobat's toolbar?
     139    pdfmenubar=true,        % show Acrobat's menu?
    140140    pdffitwindow=false,     % window fit to page when opened
    141141    pdfstartview={FitH},    % fits the width of the page to the window

  • doc/user/EHMHierarchy.fig

    r3d4b23fa r0720e049  
    1 #FIG 3.2  Produced by xfig version 3.2.5b
     1#FIG 3.2  Produced by xfig version 3.2.5c
    22Landscape
    33Center
    … …  
    19192 1 0 1 0 7 100 0 -1 0.000 0 0 -1 1 0 2
    2020        1 1 1.00 60.00 90.00
    21          1950 1425 3000 1200
     21         1950 1425 2925 1200
    22222 1 0 1 0 7 100 0 -1 0.000 0 0 -1 1 0 2
    2323        1 1 1.00 60.00 90.00
    … …  
    2929        1 1 1.00 60.00 90.00
    3030         4950 1950 4950 1725
    31 4 1 0 100 0 0 12 0.0000 0 135 195 1950 1650 IO\001
    32 4 1 0 100 0 0 12 0.0000 0 135 870 4950 1650 Arithmetic\001
    33 4 1 0 100 0 0 12 0.0000 0 135 315 1350 2100 File\001
    34 4 1 0 100 0 0 12 0.0000 0 135 690 2550 2100 Network\001
    35 4 1 0 100 0 0 12 0.0000 0 180 1170 3750 2100 DivideByZero\001
    36 4 1 0 100 0 0 12 0.0000 0 135 750 4950 2100 Overflow\001
    37 4 1 0 100 0 0 12 0.0000 0 135 855 6000 2100 Underflow\001
    38 4 1 0 100 0 0 12 0.0000 0 180 840 3450 1200 Exception\001
     314 1 0 50 -1 0 13 0.0000 2 135 225 1950 1650 IO\001
     324 1 0 50 -1 0 13 0.0000 2 135 915 4950 1650 Arithmetic\001
     334 1 0 50 -1 0 13 0.0000 2 150 330 1350 2100 File\001
     344 1 0 50 -1 0 13 0.0000 2 135 735 2550 2100 Network\001
     354 1 0 50 -1 0 13 0.0000 2 180 1215 3750 2100 DivideByZero\001
     364 1 0 50 -1 0 13 0.0000 2 150 810 4950 2100 Overflow\001
     374 1 0 50 -1 0 13 0.0000 2 150 915 6000 2100 Underflow\001
     384 1 0 50 -1 0 13 0.0000 2 180 855 3450 1200 Exception\001

  • doc/user/Makefile

    r3d4b23fa r0720e049  
    99SOURCES = ${addsuffix .tex, \
    1010user \
     11../refrat/keywords \
     12../refrat/operidents \
    1113}
    1214

  • doc/user/user.tex

    r3d4b23fa r0720e049  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Thu Jul 13 11:44:57 2017
    14 %% Update Count     : 2690
     13%% Last Modified On : Sun Aug  6 10:24:21 2017
     14%% Update Count     : 3036
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    3737\usepackage{mathptmx}                                   % better math font with "times"
    3838\usepackage[usenames]{color}
    39 \usepackage[pagewise]{lineno}
    40 \renewcommand{\linenumberfont}{\scriptsize\sffamily}
    4139\input{common}                                          % common CFA document macros
    4240\usepackage[dvips,plainpages=false,pdfpagelabels,pdfpagemode=UseNone,colorlinks=true,pagebackref=true,linkcolor=blue,citecolor=blue,urlcolor=blue,pagebackref=true,breaklinks=true]{hyperref}
    … …  
    4442\renewcommand{\UrlFont}{\small\sf}
    4543
     44\usepackage[pagewise]{lineno}
     45\renewcommand{\linenumberfont}{\scriptsize\sffamily}
     46\usepackage[firstpage]{draftwatermark}
     47\SetWatermarkLightness{0.9}
     48
    4649% Default underscore is too low and wide. Cannot use lstlisting "literate" as replacing underscore
    4750% removes it as a variable-name character so keywords in variables are highlighted. MUST APPEAR
    4851% AFTER HYPERREF.
    49 \renewcommand{\_}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    5052\renewcommand{\textunderscore}{\leavevmode\makebox[1.2ex][c]{\rule{1ex}{0.075ex}}}
    5153
    … …  
    5658
    5759\CFAStyle                                                                                               % use default CFA format-style
    58 
    59 \lstnewenvironment{C++}[1][]
     60\lstnewenvironment{C++}[1][]                            % use C++ style
    6061{\lstset{language=C++,moredelim=**[is][\protect\color{red}]{®}{®}#1}}
    6162{}
    … …  
    7879\newcommand{\B}[1]{{\Textbf[blue]{#1}}}
    7980\newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}}
     81\newcommand{\KWC}{K-W C\xspace}
    8082
    8183\newsavebox{\LstBox}
    … …  
    105107
    106108\date{
    107 DRAFT \\ \today
     109\today
    108110}% date
    109111
    … …  
    197199This document is a programmer reference-manual for the \CFA programming language.
    198200The manual covers the core features of the language and runtime-system, with simple examples illustrating syntax and semantics of each feature.
    199 The manual does not teach programming, i.e., how to combine the new constructs to build complex programs.
     201The manual does not teach programming, \ie how to combine the new constructs to build complex programs.
    200202A reader should already have an intermediate knowledge of control flow, data structures, and concurrency issues to understand the ideas presented, as well as some experience programming in C/\CC.
    201203Implementers should refer to the \CFA Programming Language Specification for details about the language syntax and semantics.
    … …  
    247249\section{History}
    248250
    249 The \CFA project started with \Index*{K-W C}~\cite{Buhr94a,Till89}, which extended C with new declaration syntax, multiple return values from routines, and advanced assignment capabilities using the notion of tuples.
     251The \CFA project started with \Index*{Dave Till}\index{Till, Dave}'s \Index*{K-W C}~\cite{Buhr94a,Till89}, which extended C with new declaration syntax, multiple return values from routines, and advanced assignment capabilities using the notion of tuples.
    250252(See~\cite{Werther96} for similar work in \Index*[C++]{\CC{}}.)
    251 The first \CFA implementation of these extensions was by Esteves~\cite{Esteves04}.
    252 
    253 The signature feature of \CFA is \Index{overload}able \Index{parametric-polymorphic} functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a ©forall© clause (giving the language its name):
     253The first \CFA implementation of these extensions was by \Index*{Rodolfo Esteves}\index{Esteves, Rodolfo}~\cite{Esteves04}.
     254
     255The signature feature of \CFA is \emph{\Index{overload}able} \Index{parametric-polymorphic} functions~\cite{forceone:impl,Cormack90,Duggan96} with functions generalized using a ©forall© clause (giving the language its name):
    254256\begin{lstlisting}
    255257®forall( otype T )® T identity( T val ) { return val; }
    … …  
    257259\end{lstlisting}
    258260% extending the C type system with parametric polymorphism and overloading, as opposed to the \Index*[C++]{\CC{}} approach of object-oriented extensions.
    259 \CFA{}\hspace{1pt}'s polymorphism was originally formalized by Ditchfiled~\cite{Ditchfield92}, and first implemented by Bilson~\cite{Bilson03}.
     261\CFA{}\hspace{1pt}'s polymorphism was originally formalized by \Index*{Glen Ditchfield}\index{Ditchfield, Glen}~\cite{Ditchfield92}, and first implemented by \Index*{Richard Bilson}\index{Bilson, Richard}~\cite{Bilson03}.
    260262However, at that time, there was little interesting in extending C, so work did not continue.
    261263As the saying goes, ``\Index*{What goes around, comes around.}'', and there is now renewed interest in the C programming language because of legacy code-bases, so the \CFA project has been restarted.
    … …  
    270272Language developers often state that adequate \Index{library support} takes more work than designing and implementing the language itself.
    271273Fortunately, \CFA, like \Index*[C++]{\CC{}}, starts with immediate access to all exiting C libraries, and in many cases, can easily wrap library routines with simpler and safer interfaces, at very low cost.
    272 Hence, \CFA begins by leveraging the large repository of C libraries at little cost.
     274Hence, \CFA begins by leveraging the large repository of C libraries, and than allows programmers to incrementally augment their C programs with modern \Index{backward-compatible} features.
    273275
    274276\begin{comment}
    … …  
    318320\begin{cfa}
    319321char abs( char );
    320 ®extern "C" {®
    321 int abs( int );                                                 §\C{// use default C routine for int}§
    322 ®}® // extern "C"
     322®extern "C" {® int abs( int ); ®}®              §\C{// use default C routine for int}§
    323323long int abs( long int );
    324324long long int abs( long long int );
    … …  
    335335Hence, there is the same need as in \CC, to know if a name is a C or \CFA name, so it can be correctly formed.
    336336There is no way around this problem, other than C's approach of creating unique names for each pairing of operation and type.
     337
    337338This example strongly illustrates a core idea in \CFA: \emph{the \Index{power of a name}}.
    338339The name ``©abs©'' evokes the notion of absolute value, and many mathematical types provide the notion of absolute value.
    … …  
    343344\section[Compiling a CFA Program]{Compiling a \CFA Program}
    344345
    345 The command ©cfa© is used to compile \CFA program(s), and is based on the GNU \Indexc{gcc} command, \eg:
    346 \begin{cfa}
    347 cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] C/§\CFA{}§-files [ assembler/loader-files ]
     346The command ©cfa© is used to compile a \CFA program and is based on the \Index{GNU} \Indexc{gcc} command, \eg:
     347\begin{cfa}
     348cfa§\indexc{cfa}\index{compilation!cfa@©cfa©}§ [ gcc-options ] [ C/§\CFA{}§ source-files ] [ assembler/loader files ]
    348349\end{cfa}
    349350\CFA programs having the following ©gcc© flags turned on:
    … …  
    353354The 1999 C standard plus GNU extensions.
    354355\item
    355 {\lstset{deletekeywords={inline}}
    356 \Indexc{-fgnu89-inline}\index{compilation option!-fgnu89-inline@{©-fgnu89-inline©}}
     356\Indexc[deletekeywords=inline]{-fgnu89-inline}\index{compilation option!-fgnu89-inline@{\lstinline[deletekeywords=inline]$-fgnu89-inline$}}
    357357Use the traditional GNU semantics for inline routines in C99 mode, which allows inline routines in header files.
    358 }%
    359358\end{description}
    360359The following new \CFA options are available:
    … …  
    363362\Indexc{-CFA}\index{compilation option!-CFA@©-CFA©}
    364363Only the C preprocessor and the \CFA translator steps are performed and the transformed program is written to standard output, which makes it possible to examine the code generated by the \CFA translator.
    365 The generated code started with the standard \CFA prelude.
     364The generated code starts with the standard \CFA \Index{prelude}.
    366365
    367366\item
    … …  
    375374\Indexc{-nodebug}\index{compilation option!-nodebug@©-nodebug©}
    376375The program is linked with the non-debugging version of the runtime system, so the execution of the program is faster.
    377 \Emph{However, no runtime checks or ©assert©s are performed so errors usually result in abnormal program termination.}
     376\Emph{However, no runtime checks or ©assert©s are performed so errors usually result in abnormal program behaviour or termination.}
    378377
    379378\item
    … …  
    395394\textbf{This option is the default.}
    396395
     396\begin{comment}
    397397\item
    398398\Indexc{-no-include-stdhdr}\index{compilation option!-no-include-stdhdr@©-no-include-stdhdr©}
    399399Do not supply ©extern "C"© wrappers for \Celeven standard include files (see~\VRef{s:StandardHeaders}).
    400400\textbf{This option is \emph{not} the default.}
     401\end{comment}
    401402\end{description}
    402403
    … …  
    419420\item
    420421\Indexc{__CFA__}\index{preprocessor variables!__CFA__@©__CFA__©},
    421 \Indexc{__CFORALL__}\index{preprocessor variables!__CFORALL__@©__CFORALL__©} and
     422\Indexc{__CFORALL__}\index{preprocessor variables!__CFORALL__@©__CFORALL__©}, and
    422423\Indexc{__cforall}\index{preprocessor variables!__cforall@©__cforall©}
    423424are always available during preprocessing and have no value.
    … …  
    472473\label{s:BackquoteIdentifiers}
    473474
    474 \CFA introduces in new keywords (see \VRef{s:CFAKeywords}) that can clash with existing C variable-names in legacy code.
     475\CFA introduces several new keywords (see \VRef{s:CFAKeywords}) that can clash with existing C variable-names in legacy code.
    475476Keyword clashes are accommodated by syntactic transformations using the \CFA backquote escape-mechanism:
    476477\begin{cfa}
    … …  
    478479double ®`®forall®`® = 3.5;
    479480\end{cfa}
     481
    480482Existing C programs with keyword clashes can be converted by enclosing keyword identifiers in backquotes, and eventually the identifier name can be changed to a non-keyword name.
    481 \VRef[Figure]{f:InterpositionHeaderFile} shows how clashes in C header files (see~\VRef{s:StandardHeaders}) can be handled using preprocessor \newterm{interposition}: ©#include_next© and ©-I filename©:
     483\VRef[Figure]{f:HeaderFileInterposition} shows how clashes in existing C header-files (see~\VRef{s:StandardHeaders}) can be handled using preprocessor \newterm{interposition}: ©#include_next© and ©-I filename©.
     484Several common C header-files with keyword clashes are fixed in the standard \CFA header-library, so there is a seamless programming-experience.
    482485
    483486\begin{figure}
    484487\begin{cfa}
    485 // include file uses the CFA keyword "otype".
    486 #if ! defined( otype )                  §\C{// nesting ?}§
    487 #define otype ®`®otype®`®               §\C{// make keyword an identifier}§
     488// include file uses the CFA keyword "with".
     489#if ! defined( with )                   §\C{// nesting ?}§
     490#define with ®`®with®`®                 §\C{// make keyword an identifier}§
    488491#define __CFA_BFD_H__
    489 #endif // ! otype
    490 
    491 #®include_next® <bfd.h>                 §\C{// must have internal check for multiple expansion}§
    492 
    493 #if defined( otype ) && defined( __CFA_BFD_H__ )        §\C{// reset only if set}§
    494 #undef otype
     492#endif
     493
     494®#include_next <bfdlink.h>              §\C{// must have internal check for multiple expansion}§
     495®
     496#if defined( with ) && defined( __CFA_BFD_H__ ) §\C{// reset only if set}§
     497#undef with
    495498#undef __CFA_BFD_H__
    496 #endif // otype && __CFA_BFD_H__
    497 \end{cfa}
    498 \caption{Interposition of Header File}
    499 \label{f:InterpositionHeaderFile}
     499#endif
     500\end{cfa}
     501\caption{Header-File Interposition}
     502\label{f:HeaderFileInterposition}
    500503\end{figure}
    501504
    … …  
    505508While C provides ©continue© and ©break© statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
    506509Unfortunately, this restriction forces programmers to use \Indexc{goto} to achieve the equivalent control-flow for more than one level of nesting.
    507 To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@\lstinline $continue$!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@\lstinline $break$!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85}.
     510To prevent having to switch to the ©goto©, \CFA extends the \Indexc{continue}\index{continue@\lstinline $continue$!labelled}\index{labelled!continue@©continue©} and \Indexc{break}\index{break@\lstinline $break$!labelled}\index{labelled!break@©break©} with a target label to support static multi-level exit\index{multi-level exit}\index{static multi-level exit}~\cite{Buhr85}, as in Java.
    508511For both ©continue© and ©break©, the target label must be directly associated with a ©for©, ©while© or ©do© statement;
    509512for ©break©, the target label can also be associated with a ©switch©, ©if© or compound (©{}©) statement.
    510 \VRef[Figure]{f:MultiLevelResumeTermination} shows the labelled ©continue© and ©break©, specifying which control structure is the target for exit, and the corresponding C program using only ©goto©.
    511 The innermost loop has 7 exit points, which cause resumption or termination of one or more of the 7 \Index{nested control-structure}s.
    512 Java supports both labelled ©continue© and ©break© statements.
     513\VRef[Figure]{f:MultiLevelExit} shows ©continue© and ©break© indicating the specific control structure, and the corresponding C program using only ©goto© and labels.
     514The innermost loop has 7 exit points, which cause continuation or termination of one or more of the 7 \Index{nested control-structure}s.
    513515
    514516\begin{figure}
    515 \begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{1.5em}}l@{}}
    516 \multicolumn{1}{c@{\hspace{1.5em}}}{\textbf{\CFA}}      & \multicolumn{1}{c}{\textbf{C}}        \\
     517\begin{tabular}{@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     518\multicolumn{1}{@{\hspace{\parindentlnth}}c@{\hspace{\parindentlnth}}}{\textbf{\CFA}}   & \multicolumn{1}{@{\hspace{\parindentlnth}}c}{\textbf{C}}      \\
    517519\begin{cfa}
    518520®LC:® {
    … …  
    523525                        ®LF:® for ( ... ) {
    524526                                ®LW:® while ( ... ) {
    525                                         ... break ®LC®; ...                     // terminate compound
    526                                         ... break ®LS®; ...                     // terminate switch
    527                                         ... break ®LIF®; ...                    // terminate if
    528                                         ... continue ®LF;® ...   // resume loop
    529                                         ... break ®LF®; ...                     // terminate loop
    530                                         ... continue ®LW®; ...   // resume loop
    531                                         ... break ®LW®; ...               // terminate loop
     527                                        ... break ®LC®; ...
     528                                        ... break ®LS®; ...
     529                                        ... break ®LIF®; ...
     530                                        ... continue ®LF;® ...
     531                                        ... break ®LF®; ...
     532                                        ... continue ®LW®; ...
     533                                        ... break ®LW®; ...
    532534                                } // while
    533535                        } // for
    534536                } else {
    535                         ... break ®LIF®; ...                                     // terminate if
     537                        ... break ®LIF®; ...
    536538                } // if
    537539        } // switch
    … …  
    562564} ®LC:® ;
    563565\end{cfa}
     566&
     567\begin{cfa}
     568
     569
     570
     571
     572
     573
     574
     575// terminate compound
     576// terminate switch
     577// terminate if
     578// continue loop
     579// terminate loop
     580// continue loop
     581// terminate loop
     582
     583
     584
     585// terminate if
     586
     587
     588
     589\end{cfa}
    564590\end{tabular}
    565 \caption{Multi-level Resume/Termination}
    566 \label{f:MultiLevelResumeTermination}
     591\caption{Multi-level Exit}
     592\label{f:MultiLevelExit}
    567593\end{figure}
    568 
    569 \begin{comment}
    570 int main() {
    571   LC: {
    572           LS: switch ( 1 ) {
    573                   case 3:
    574                   LIF: if ( 1 ) {
    575                           LF: for ( ;; ) {
    576                                   LW: while ( 1 ) {
    577                                                 break LC;                       // terminate compound
    578                                                 break LS;                       // terminate switch
    579                                                 break LIF;                      // terminate if
    580                                                 continue LF;     // resume loop
    581                                                 break LF;                       // terminate loop
    582                                                 continue LW;     // resume loop
    583                                                 break LW;                 // terminate loop
    584                                         } // while
    585                                 } // for
    586                         } else {
    587                                 break LIF;                                       // terminate if
    588                         } // if
    589                 } // switch
    590         } // compound
    591         {
    592                 switch ( 1 ) {
    593                   case 3:
    594                         if ( 1 ) {
    595                                 for ( ;; ) {
    596                                         while ( 1 ) {
    597                                                 goto LCx;
    598                                                 goto LSx;
    599                                                 goto LIF;
    600                                                 goto LFC;
    601                                                 goto LFB;
    602                                                 goto LWC;
    603                                                 goto LWB;
    604                                           LWC: ; } LWB: ;
    605                                   LFC: ; } LFB: ;
    606                         } else {
    607                                 goto LIF;
    608                         } L3: ;
    609                 } LSx: ;
    610         } LCx: ;
    611 }
    612 
    613 // Local Variables: //
    614 // tab-width: 4 //
    615 // End: //
    616 \end{comment}
    617 
    618594
    619595Both labelled ©continue© and ©break© are a ©goto©\index{goto@\lstinline $goto$!restricted} restricted in the following ways:
    … …  
    624600\item
    625601They cannot branch into a control structure.
    626 This restriction prevents missing initialization at the start of a control structure resulting in undefined behaviour.
     602This restriction prevents missing declarations and/or initializations at the start of a control structure resulting in undefined behaviour.
    627603\end{itemize}
    628604The advantage of the labelled ©continue©/©break© is allowing static multi-level exits without having to use the ©goto© statement, and tying control flow to the target control structure rather than an arbitrary point in a program.
    629 Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader that complex control-flow is occurring in the body of the control structure.
     605Furthermore, the location of the label at the \emph{beginning} of the target control structure informs the reader (\Index{eye candy}) that complex control-flow is occurring in the body of the control structure.
    630606With ©goto©, the label is at the end of the control structure, which fails to convey this important clue early enough to the reader.
    631607Finally, using an explicit target for the transfer instead of an implicit target allows new constructs to be added or removed without affecting existing constructs.
    … …  
    719695The problem with this usage is branching into control structures, which is known to cause both comprehension and technical difficulties.
    720696The comprehension problem occurs from the inability to determine how control reaches a particular point due to the number of branches leading to it.
    721 The technical problem results from the inability to ensure allocation and initialization of variables when blocks are not entered at the beginning.
    722 Often transferring into a block can bypass variable declaration and/or its initialization, which results in subsequent errors.
    723 There are virtually no positive arguments for this kind of control flow, and therefore, there is a strong impetus to eliminate it.
     697The technical problem results from the inability to ensure declaration and initialization of variables when blocks are not entered at the beginning.
     698There are no positive arguments for this kind of control flow, and therefore, there is a strong impetus to eliminate it.
    724699Nevertheless, C does have an idiom where this capability is used, known as ``\Index*{Duff's device}''~\cite{Duff83}:
    725700\begin{cfa}
    … …  
    921896class C {
    922897        int i, j;
    923         int mem() {              ®// implicit "this" parameter
    924                 i = 1;          ®// this->i
    925 ®               j = 3;          ®// this->j
    926 ®       }
     898        int mem() {                                     §\C{\color{red}// implicit "this" parameter}§
     899                i = 1;                                  §\C{\color{red}// this->i}§
     900                j = 2;                                  §\C{\color{red}// this->j}§
     901        }
    927902}
    928903\end{C++}
    929904Since CFA is non-object-oriented, the equivalent object-oriented program looks like:
    930905\begin{cfa}
    931 struct C {
    932         int i, j;
    933 };
    934 int mem( C &this ) {    // explicit "this" parameter
    935         ®this.®i = 1;                     // "this" is not elided
     906struct S { int i, j; };
     907int mem( S &®this® ) {                  §\C{// explicit "this" parameter}§
     908        ®this.®i = 1;                           §\C{// "this" is not elided}§
    936909        ®this.®j = 2;
    937910}
    938911\end{cfa}
    939912but it is cumbersome having to write "©this.©" many times in a member.
    940 \CFA provides a ©with© clause/statement to elided the "©this.©".
    941 \begin{cfa}
    942 int mem( C &this ) ®with this® {
    943         i = 1;                  ®// this.i
    944 ®       j = 2;                  ®// this.j
    945 ®}
     913
     914\CFA provides a ©with© clause/statement (see Pascal~\cite[\S~4.F]{Pascal}) to elided the "©this.©" by opening a scope containing field identifiers, changing the qualified fields into variables and giving an opportunity for optimizing qualified references.
     915\begin{cfa}
     916int mem( S &this ) ®with this® { §\C{// with clause}§
     917        i = 1;                                          §\C{\color{red}// this->i}§
     918        j = 2;                                          §\C{\color{red}// this->j}§
     919}
    946920\end{cfa}
    947921which extends to multiple routine parameters:
    948922\begin{cfa}
    949 struct D {
    950         double m, n;
    951 };
    952 int mem2( C &this1, D &this2 ) ®with this1, this2® {
     923struct T { double m, n; };
     924int mem2( S &this1, T &this2 ) ®with this1, this2® {
    953925        i = 1; j = 2;
    954926        m = 1.0; n = 2.0;
    955927}
    956928\end{cfa}
    957 The ©with© clause/statement comes from Pascal~\cite[\S~4.F]{Pascal}.
    958929
    959930The statement form is used within a block:
    … …  
    962933        struct S1 { ... } s1;
    963934        struct S2 { ... } s2;
    964         ®with s1® {
     935        ®with s1® {                     // with statement
    965936                // access fields of s1 without qualification
    966937                ®with s2® {  // nesting
    967                         // access fields of s2 without qualification
     938                        // access fields of s1 and s2 without qualification
    968939                }
    969940        }
    … …  
    974945\end{cfa}
    975946
    976 Names clashes when opening multiple structures are ambiguous.
    977 \begin{cfa}
    978 struct A { int i; int j; } a, c;
    979 struct B { int i; int k; } b, c;
     947When opening multiple structures, fields with the same name and type are ambiguous and must be fully qualified.
     948For fields with the same name but different type, context/cast can be used to disambiguate.
     949\begin{cfa}
     950struct S { int i; int j; double m; } a, c;
     951struct T { int i; int k; int m } b, c;
    980952®with a, b® {
    981         j + k;                                          §\C{// unambiguous}§
    982         i;                                                      §\C{// ambiguous}§
    983         a.i + b.i;                                      §\C{// unambiguous}§
    984 }
    985 ®with c® {                                              §\C{// ambiguous}§
    986         // ...
    987 }
     953        j + k;                                          §\C{// unambiguous, unique names define unique types}§
     954        i;                                                      §\C{// ambiguous, same name and type}§
     955        a.i + b.i;                                      §\C{// unambiguous, qualification defines unique names}§
     956        m;                                                      §\C{// ambiguous, same name and no context to define unique type}§
     957        m = 5.0;                                        §\C{// unambiguous, same name and context defines unique type}§
     958        m = 1;                                          §\C{// unambiguous, same name and context defines unique type}§
     959}
     960®with c® { ... }                                §\C{// ambiguous, same name and no context}§
     961®with (S)c® { ... }                             §\C{// unambiguous, same name and cast defines unique type}§
    988962\end{cfa}
    989963
    990964
    991965\section{Exception Handling}
     966\label{s:ExceptionHandling}
    992967
    993968Exception handling provides two mechanism: change of control flow from a raise to a handler, and communication from the raise to the handler.
    994 \begin{cfa}
    995 exception void h( int i );
    996 exception int h( int i, double d );
    997 
     969Transfer of control can be local, within a routine, or non-local, among routines.
     970Non-local transfer can cause stack unwinding, \ie non-local routine termination, depending on the kind of raise.
     971\begin{cfa}
     972exception_t E {};                               §\C{// exception type}§
    998973void f(...) {
    999         ... throw h( 3 );
    1000         ... i = resume h( 3, 5.1 );
    1001 }
    1002 
     974        ... throw E{}; ...                      §\C{// termination}§
     975        ... throwResume E{}; ...        §\C{// resumption}§
     976}
    1003977try {
    1004978        f(...);
    1005 } catch h( int w ) {
    1006         // reset
    1007 } resume h( int p, double x ) {
    1008         return 17;  // recover
     979} catch( E e : §boolean-predicate§ ) {                  §\C[8cm]{// termination handler}§
     980        // recover and continue
     981} catchResume( E e : §boolean-predicate§ ) {    §\C{// resumption handler}\CRT§
     982        // repair and return
    1009983} finally {
    1010 }
    1011 \end{cfa}
    1012 So the type raised would be the mangled name of the exception prototype and that name would be matched at the handler clauses by comparing the strings.
    1013 The arguments for the call would have to be packed in a message and unpacked at handler clause and then a call made to the handler.
     984        // always executed
     985}
     986\end{cfa}
     987The kind of raise and handler match: ©throw© with ©catch© and ©throwResume© with ©catchResume©.
     988Then the exception type must match along with any additonal predicate must be true.
     989The ©catch© and ©catchResume© handlers may appear in any oder.
     990However, the ©finally© clause must appear at the end of the ©try© statement.
    1014991
    1015992
    … …  
    12221199
    12231200
     1201\section{Exponentiation Operator}
     1202
     1203C, \CC, and Java (and many other programming languages) have no exponentiation operator\index{exponentiation!operator}\index{operator!exponentiation}, \ie $x^y$, and instead use a routine, like \Indexc{pow}, to perform the exponentiation operation.
     1204\CFA extends the basic operators with the exponentiation operator ©?\?©\index{?\\?@\lstinline$?\?$} and ©?\=?©\index{?\\=?@\lstinline$?\=?$}, as in, ©x \ y© and ©x \= y©, which means $x^y$ and $x \leftarrow x^y$.
     1205The priority of the exponentiation operator is between the cast and multiplicative operators, so that ©w * (int)x \ (int)y * z© is parenthesized as ©((w * (((int)x) \ ((int)y))) * z)©.
     1206
     1207As for \Index{division}, there are exponentiation operators for integral and floating-point types, including the builtin \Index{complex} types.
     1208Unsigned integral exponentiation\index{exponentiation!unsigned integral} is performed with repeated multiplication\footnote{The multiplication computation is optimized to $O(\log y)$.} (or shifting if the base is 2).
     1209Signed integral exponentiation\index{exponentiation!signed integral} is performed with repeated multiplication (or shifting if the base is 2), but yields a floating-point result because $x^{-y}=1/x^y$.
     1210Hence, it is important to designate exponent integral-constants as unsigned or signed: ©3 \ 3u© return an integral result, while ©3 \ 3© returns a floating-point result.
     1211Floating-point exponentiation\index{exponentiation!floating point} is performed using \Index{logarithm}s\index{exponentiation!logarithm}, so the base cannot be negative.
     1212\begin{cfa}
     1213sout | 2 ®\® 8u | 4 ®\® 3u | -4 ®\® 3u | 4 ®\® -3 | -4 ®\® -3 | 4.0 ®\® 2.1 | (1.0f+2.0fi) ®\® (3.0f+2.0fi) | endl;
     1214256 64 -64 0.015625 -0.015625 18.3791736799526 0.264715-1.1922i
     1215\end{cfa}
     1216Parenthesis are necessary for the complex constants or the expresion is parsed as ©1.0f+(2.0fi \ 3.0f)+2.0fi©.
     1217The exponentiation operator is available for all the basic types, but for user-defined types, only the integral-computation versions are available.
     1218For returning an integral value, the user type ©T© must define multiplication, ©*©, and one, ©1©;
     1219for returning a floating-point value, an additional divide of type ©T© into a ©double© returning a ©double© (©double ?/?( double, T )©) is necessary for negative exponents.
     1220
     1221
    12241222\section{Pointer / Reference}
    12251223
    … …  
    12301228An integer constant expression with the value 0, or such an expression cast to type ©void *©, is called a \newterm{null-pointer constant}.\footnote{
    12311229One way to conceptualize the null pointer is that no variable is placed at this address, so the null-pointer address can be used to denote an uninitialized pointer/reference object;
    1232 \ie the null pointer is guaranteed to compare unequal to a pointer to any object or routine.}
     1230\ie the null pointer is guaranteed to compare unequal to a pointer to any object or routine.
     1231In general, a value with special meaning among a set of values is called a \emph{\Index{sentinel value}}, \eg ©-1© as a return code value.}
    12331232An address is \newterm{sound}, if it points to a valid memory location in scope, \ie within the program's execution-environment and has not been freed.
    12341233Dereferencing an \newterm{unsound} address, including the null pointer, is \Index{undefined}, often resulting in a \Index{memory fault}.
    … …  
    12651264\hline
    12661265\begin{cfa}
    1267 lda             r1,100                  // load address of x
    1268 ld               r2,(r1)                  // load value of x
    1269 lda             r3,104                  // load address of y
    1270 st               r2,(r3)                  // store x into y
     1266lda             r1,100  // load address of x
     1267ld               r2,(r1)          // load value of x
     1268lda             r3,104  // load address of y
     1269st               r2,(r3)          // store x into y
    12711270\end{cfa}
    12721271&
    12731272\begin{cfa}
    12741273
    1275 ld              r2,(100)                // load value of x
    1276 
    1277 st              r2,(104)                // store x into y
     1274ld              r2,(100)        // load value of x
     1275
     1276st              r2,(104)        // store x into y
    12781277\end{cfa}
    12791278\end{tabular}
    … …  
    14231422int w, x, y, z, & ar[3] = { x, y, z }; §\C{// initialize array of references}§
    14241423&ar[1] = &w;                                            §\C{// change reference array element}§
    1425 typeof( ar[1] ) p;                                      §\C{// (gcc) is int, i.e., the type of referenced object}§
    1426 typeof( &ar[1] ) q;                                     §\C{// (gcc) is int \&, i.e., the type of reference}§
    1427 sizeof( ar[1] ) == sizeof( int );       §\C{// is true, i.e., the size of referenced object}§
    1428 sizeof( &ar[1] ) == sizeof( int *)      §\C{// is true, i.e., the size of a reference}§
     1424typeof( ar[1] ) p;                                      §\C{// (gcc) is int, \ie the type of referenced object}§
     1425typeof( &ar[1] ) q;                                     §\C{// (gcc) is int \&, \ie the type of reference}§
     1426sizeof( ar[1] ) == sizeof( int );       §\C{// is true, \ie the size of referenced object}§
     1427sizeof( &ar[1] ) == sizeof( int *)      §\C{// is true, \ie the size of a reference}§
    14291428\end{cfa}
    14301429
    … …  
    15711570
    15721571\item
    1573 lvalue to reference conversion: \lstinline[deletekeywords={lvalue}]@lvalue-type cv1 T@ converts to ©cv2 T &©, which allows implicitly converting variables to references.
     1572lvalue to reference conversion: \lstinline[deletekeywords=lvalue]$lvalue-type cv1 T$ converts to ©cv2 T &©, which allows implicitly converting variables to references.
    15741573\begin{cfa}
    15751574int x, &r = ®x®, f( int & p ); // lvalue variable (int) convert to reference (int &)
    … …  
    17651764
    17661765In detail, the brackets, ©[]©, enclose the result type, where each return value is named and that name is a local variable of the particular return type.\footnote{
    1767 \Index*{Michael Tiemann}, with help from \Index*{Doug Lea}, provided named return values in g++, circa 1989.}
     1766\Index*{Michael Tiemann}\index{Tiemann, Michael}, with help from \Index*{Doug Lea}\index{Lea, Doug}, provided named return values in g++, circa 1989.}
    17681767The value of each local return variable is automatically returned at routine termination.
    17691768Declaration qualifiers can only appear at the start of a routine definition, \eg:
    … …  
    22242223
    22252224
     2225\section{Tuple}
     2226
     2227In C and \CFA, lists of elements appear in several contexts, such as the parameter list of a routine call.
     2228\begin{cfa}
     2229f( ®2, x, 3 + i® );                             §\C{// element list}§
     2230\end{cfa}
     2231A list of elements is called a \newterm{tuple}, and is different from a \Index{comma expression}.
     2232
     2233
     2234\subsection{Multiple-Return-Value Functions}
     2235\label{s:MRV_Functions}
     2236
     2237In standard C, functions can return at most one value.
     2238To emulate functions with multiple return values, \emph{\Index{aggregation}} and/or \emph{\Index{aliasing}} is used.
     2239In the former situation, the function designer creates a record type that combines all of the return values into a single type.
     2240For example, consider a function returning the most frequently occurring letter in a string, and its frequency.
     2241This example is complex enough to illustrate that an array is insufficient, since arrays are homogeneous, and demonstrates a potential pitfall that exists with aliasing.
     2242\begin{cfa}
     2243struct mf_ret {
     2244        int freq;
     2245        char ch;
     2246};
     2247
     2248struct mf_ret most_frequent(const char * str) {
     2249        char freqs [26] = { 0 };
     2250        struct mf_ret ret = { 0, 'a' };
     2251        for (int i = 0; str[i] != '\0'; ++i) {
     2252                if (isalpha(str[i])) {        // only count letters
     2253                        int ch = tolower(str[i]);   // convert to lower case
     2254                        int idx = ch-'a';
     2255                        if (++freqs[idx] > ret.freq) {  // update on new max
     2256                          ret.freq = freqs[idx];
     2257                          ret.ch = ch;
     2258                        }
     2259                }
     2260        }
     2261        return ret;
     2262}
     2263
     2264const char * str = "hello world";
     2265struct mf_ret ret = most_frequent(str);
     2266printf("%s -- %d %c\n", str, ret.freq, ret.ch);
     2267\end{cfa}
     2268Of note, the designer must come up with a name for the return type and for each of its fields.
     2269Unnecessary naming is a common programming language issue, introducing verbosity and a complication of the user's mental model.
     2270That is, adding another named type creates another association in the programmer's mind that needs to be kept track of when reading and writing code.
     2271As such, this technique is effective when used sparingly, but can quickly get out of hand if many functions need to return different combinations of types.
     2272
     2273In the latter approach, the designer simulates multiple return values by passing the additional return values as pointer parameters.
     2274The pointer parameters are assigned inside of the routine body to emulate a return.
     2275Using the same example,
     2276\begin{cfa}
     2277int most_frequent(const char * str, char * ret_ch) {
     2278        char freqs [26] = { 0 };
     2279        int ret_freq = 0;
     2280        for (int i = 0; str[i] != '\0'; ++i) {
     2281                if (isalpha(str[i])) {        // only count letters
     2282                        int ch = tolower(str[i]);   // convert to lower case
     2283                        int idx = ch-'a';
     2284                        if (++freqs[idx] > ret_freq) {  // update on new max
     2285                          ret_freq = freqs[idx];
     2286                          *ret_ch = ch;   // assign to out parameter
     2287                        }
     2288                }
     2289        }
     2290        return ret_freq;  // only one value returned directly
     2291}
     2292
     2293const char * str = "hello world";
     2294char ch;                            // pre-allocate return value
     2295int freq = most_frequent(str, &ch); // pass return value as out parameter
     2296printf("%s -- %d %c\n", str, freq, ch);
     2297\end{cfa}
     2298Notably, using this approach, the caller is directly responsible for allocating storage for the additional temporary return values, which complicates the call site with a sequence of variable declarations leading up to the call.
     2299Also, while a disciplined use of ©const© can give clues about whether a pointer parameter is going to be used as an out parameter, it is not immediately obvious from only the routine signature whether the callee expects such a parameter to be initialized before the call.
     2300Furthermore, while many C routines that accept pointers are designed so that it is safe to pass ©NULL© as a parameter, there are many C routines that are not null-safe.
     2301On a related note, C does not provide a standard mechanism to state that a parameter is going to be used as an additional return value, which makes the job of ensuring that a value is returned more difficult for the compiler.
     2302Interestingly, there is a subtle bug in the previous example, in that ©ret_ch© is never assigned for a string that does not contain any letters, which can lead to undefined behaviour.
     2303In this particular case, it turns out that the frequency return value also doubles as an error code, where a frequency of 0 means the character return value should be ignored.
     2304Still, not every routine with multiple return values should be required to return an error code, and error codes are easily ignored, so this is not a satisfying solution.
     2305As with the previous approach, this technique can simulate multiple return values, but in practice it is verbose and error prone.
     2306
     2307In \CFA, functions can be declared to return multiple values with an extension to the function declaration syntax.
     2308Multiple return values are declared as a comma-separated list of types in square brackets in the same location that the return type appears in standard C function declarations.
     2309The ability to return multiple values from a function requires a new syntax for the return statement.
     2310For consistency, the return statement in \CFA accepts a comma-separated list of expressions in square brackets.
     2311The expression resolution phase of the \CFA translator ensures that the correct form is used depending on the values being returned and the return type of the current function.
     2312A multiple-returning function with return type ©T© can return any expression that is implicitly convertible to ©T©.
     2313Using the running example, the ©most_frequent© function can be written using multiple return values as such,
     2314\begin{cfa}
     2315[int, char] most_frequent(const char * str) {
     2316        char freqs [26] = { 0 };
     2317        int ret_freq = 0;
     2318        char ret_ch = 'a';  // arbitrary default value for consistent results
     2319        for (int i = 0; str[i] != '\0'; ++i) {
     2320                if (isalpha(str[i])) {        // only count letters
     2321                        int ch = tolower(str[i]);   // convert to lower case
     2322                        int idx = ch-'a';
     2323                        if (++freqs[idx] > ret_freq) {  // update on new max
     2324                          ret_freq = freqs[idx];
     2325                          ret_ch = ch;
     2326                        }
     2327                }
     2328        }
     2329        return [ret_freq, ret_ch];
     2330}
     2331\end{cfa}
     2332This approach provides the benefits of compile-time checking for appropriate return statements as in aggregation, but without the required verbosity of declaring a new named type, which precludes the bug seen with out-parameters.
     2333
     2334The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site.
     2335The simplest mechanism for retaining a return value in C is variable assignment.
     2336By assigning the return value into a variable, its value can be retrieved later at any point in the program.
     2337As such, \CFA allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions on the left side.
     2338\begin{cfa}
     2339const char * str = "hello world";
     2340int freq;
     2341char ch;
     2342[freq, ch] = most_frequent(str);  // assign into multiple variables
     2343printf("%s -- %d %c\n", str, freq, ch);
     2344\end{cfa}
     2345It is also common to use a function's output as the input to another function.
     2346\CFA also allows this case, without any new syntax.
     2347When a function call is passed as an argument to another call, the expression resolver attempts to find the best match of actual arguments to formal parameters given all of the possible expression interpretations in the current scope \cite{Bilson03}.
     2348For example,
     2349\begin{cfa}
     2350void process(int);       // (1)
     2351void process(char);      // (2)
     2352void process(int, char); // (3)
     2353void process(char, int); // (4)
     2354
     2355process(most_frequent("hello world"));  // selects (3)
     2356\end{cfa}
     2357In this case, there is only one option for a function named ©most_frequent© that takes a string as input.
     2358This function returns two values, one ©int© and one ©char©.
     2359There are four options for a function named ©process©, but only two that accept two arguments, and of those the best match is (3), which is also an exact match.
     2360This expression first calls ©most_frequent("hello world")©, which produces the values ©3© and ©'l'©, which are fed directly to the first and second parameters of (3), respectively.
     2361
     2362\section{Tuple Expressions}
     2363Multiple-return-value functions provide \CFA with a new syntax for expressing a combination of expressions in the return statement and a combination of types in a function signature.
     2364These notions can be generalized to provide \CFA with \emph{tuple expressions} and \emph{tuple types}.
     2365A tuple expression is an expression producing a fixed-size, ordered list of values of heterogeneous types.
     2366The type of a tuple expression is the tuple of the subexpression types, or a \emph{tuple type}.
     2367In \CFA, a tuple expression is denoted by a comma-separated list of expressions enclosed in square brackets.
     2368For example, the expression ©[5, 'x', 10.5]© has type ©[int, char, double]©.
     2369The previous expression has 3 \emph{components}.
     2370Each component in a tuple expression can be any \CFA expression, including another tuple expression.
     2371The order of evaluation of the components in a tuple expression is unspecified, to allow a compiler the greatest flexibility for program optimization.
     2372It is, however, guaranteed that each component of a tuple expression is evaluated for side-effects, even if the result is not used.
     2373Multiple-return-value functions can equivalently be called \emph{tuple-returning functions}.
     2374
     2375\subsection{Tuple Variables}
     2376The call-site of the ©most_frequent© routine has a notable blemish, in that it required the preallocation of return variables in a manner similar to the aliasing example, since it is impossible to declare multiple variables of different types in the same declaration in standard C.
     2377In \CFA, it is possible to overcome this restriction by declaring a \emph{tuple variable}.
     2378\begin{cfa}[emph=ret, emphstyle=\color{red}]
     2379const char * str = "hello world";
     2380[int, char] ret = most_frequent(str);  // initialize tuple variable
     2381printf("%s -- %d %c\n", str, ret);
     2382\end{cfa}
     2383It is now possible to accept multiple values into a single piece of storage, in much the same way that it was previously possible to pass multiple values from one function call to another.
     2384These variables can be used in any of the contexts where a tuple expression is allowed, such as in the ©printf© function call.
     2385As in the ©process© example, the components of the tuple value are passed as separate parameters to ©printf©, allowing very simple printing of tuple expressions.
     2386One way to access the individual components is with a simple assignment, as in previous examples.
     2387\begin{cfa}
     2388int freq;
     2389char ch;
     2390[freq, ch] = ret;
     2391\end{cfa}
     2392
     2393\begin{sloppypar}
     2394In addition to variables of tuple type, it is also possible to have pointers to tuples, and arrays of tuples.
     2395Tuple types can be composed of any types, except for array types, since array assignment is disallowed, which makes tuple assignment difficult when a tuple contains an array.
     2396\begin{cfa}
     2397[double, int] di;
     2398[double, int] * pdi
     2399[double, int] adi[10];
     2400\end{cfa}
     2401This examples declares a variable of type ©[double, int]©, a variable of type pointer to ©[double, int]©, and an array of ten ©[double, int]©.
     2402\end{sloppypar}
     2403
     2404\subsection{Tuple Indexing}
     2405
     2406At times, it is desirable to access a single component of a tuple-valued expression without creating unnecessary temporary variables to assign to.
     2407Given a tuple-valued expression ©e© and a compile-time constant integer $i$ where $0 \leq i < n$, where $n$ is the number of components in ©e©, ©e.i© accesses the $i$\textsuperscript{th} component of ©e©.
     2408For example,
     2409\begin{cfa}
     2410[int, double] x;
     2411[char *, int] f();
     2412void g(double, int);
     2413[int, double] * p;
     2414
     2415int y = x.0;                                                    §\C{// access int component of x}§
     2416y = f().1;                                                              §\C{// access int component of f}§
     2417p->0 = 5;                                                               §\C{// access int component of tuple pointed-to by p}§
     2418g( x.1, x.0 );                                                  §\C{// rearrange x to pass to g}§
     2419double z = [x, f()].0.1;                                §\C{// access second component of first component of tuple expression}§
     2420\end{cfa}
     2421As seen above, tuple-index expressions can occur on any tuple-typed expression, including tuple-returning functions, square-bracketed tuple expressions, and other tuple-index expressions, provided the retrieved component is also a tuple.
     2422This feature was proposed for \KWC but never implemented \cite[p.~45]{Till89}.
     2423
     2424\subsection{Flattening and Structuring}
     2425As evident in previous examples, tuples in \CFA do not have a rigid structure.
     2426In function call contexts, tuples support implicit flattening and restructuring conversions.
     2427Tuple flattening recursively expands a tuple into the list of its basic components.
     2428Tuple structuring packages a list of expressions into a value of tuple type.
     2429\begin{cfa}
     2430int f(int, int);
     2431int g([int, int]);
     2432int h(int, [int, int]);
     2433[int, int] x;
     2434int y;
     2435
     2436f(x);      // flatten
     2437g(y, 10);  // structure
     2438h(x, y);   // flatten & structure
     2439\end{cfa}
     2440In \CFA, each of these calls is valid.
     2441In the call to ©f©, ©x© is implicitly flattened so that the components of ©x© are passed as the two arguments to ©f©.
     2442For the call to ©g©, the values ©y© and ©10© are structured into a single argument of type ©[int, int]© to match the type of the parameter of ©g©.
     2443Finally, in the call to ©h©, ©x© is flattened to yield an argument list of length 3, of which the first component of ©x© is passed as the first parameter of ©h©, and the second component of ©x© and ©y© are structured into the second argument of type ©[int, int]©.
     2444The flexible structure of tuples permits a simple and expressive function-call syntax to work seamlessly with both single- and multiple-return-value functions, and with any number of arguments of arbitrarily complex structure.
     2445
     2446In \KWC \cite{Buhr94a,Till89}, there were 4 tuple coercions: opening, closing, flattening, and structuring.
     2447Opening coerces a tuple value into a tuple of values, while closing converts a tuple of values into a single tuple value.
     2448Flattening coerces a nested tuple into a flat tuple, \ie it takes a tuple with tuple components and expands it into a tuple with only non-tuple components.
     2449Structuring moves in the opposite direction, \ie it takes a flat tuple value and provides structure by introducing nested tuple components.
     2450
     2451In \CFA, the design has been simplified to require only the two conversions previously described, which trigger only in function call and return situations.
     2452This simplification is a primary contribution of this thesis to the design of tuples in \CFA.
     2453Specifically, the expression resolution algorithm examines all of the possible alternatives for an expression to determine the best match.
     2454In resolving a function call expression, each combination of function value and list of argument alternatives is examined.
     2455Given a particular argument list and function value, the list of argument alternatives is flattened to produce a list of non-tuple valued expressions.
     2456Then the flattened list of expressions is compared with each value in the function's parameter list.
     2457If the parameter's type is not a tuple type, then the current argument value is unified with the parameter type, and on success the next argument and parameter are examined.
     2458If the parameter's type is a tuple type, then the structuring conversion takes effect, recursively applying the parameter matching algorithm using the tuple's component types as the parameter list types.
     2459Assuming a successful unification, eventually the algorithm gets to the end of the tuple type, which causes all of the matching expressions to be consumed and structured into a tuple expression.
     2460For example, in
     2461\begin{cfa}
     2462int f(int, [double, int]);
     2463f([5, 10.2], 4);
     2464\end{cfa}
     2465There is only a single definition of ©f©, and 3 arguments with only single interpretations.
     2466First, the argument alternative list ©[5, 10.2], 4© is flattened to produce the argument list ©5, 10.2, 4©.
     2467Next, the parameter matching algorithm begins, with $P = $©int© and $A = $©int©, which unifies exactly.
     2468Moving to the next parameter and argument, $P = $©[double, int]© and $A = $©double©.
     2469This time, the parameter is a tuple type, so the algorithm applies recursively with $P' = $©double© and $A = $©double©, which unifies exactly.
     2470Then $P' = $©int© and $A = $©double©, which again unifies exactly.
     2471At this point, the end of $P'$ has been reached, so the arguments ©10.2, 4© are structured into the tuple expression ©[10.2, 4]©.
     2472Finally, the end of the parameter list $P$ has also been reached, so the final expression is ©f(5, [10.2, 4])©.
     2473
     2474\section{Tuple Assignment}
     2475\label{s:TupleAssignment}
     2476An assignment where the left side of the assignment operator has a tuple type is called tuple assignment.
     2477There are two kinds of tuple assignment depending on whether the right side of the assignment operator has a tuple type or a non-tuple type, called \emph{Multiple} and \emph{Mass} Assignment, respectively.
     2478\begin{cfa}
     2479int x;
     2480double y;
     2481[int, double] z;
     2482[y, x] = 3.14;  // mass assignment
     2483[x, y] = z;     // multiple assignment
     2484z = 10;         // mass assignment
     2485z = [x, y];     // multiple assignment
     2486\end{cfa}
     2487Let $L_i$ for $i$ in $[0, n)$ represent each component of the flattened left side, $R_i$ represent each component of the flattened right side of a multiple assignment, and $R$ represent the right side of a mass assignment.
     2488
     2489For a multiple assignment to be valid, both tuples must have the same number of elements when flattened.
     2490For example, the following is invalid because the number of components on the left does not match the number of components on the right.
     2491\begin{cfa}
     2492[int, int] x, y, z;
     2493[x, y] = z;   // multiple assignment, invalid 4 != 2
     2494\end{cfa}
     2495Multiple assignment assigns $R_i$ to $L_i$ for each $i$.
     2496That is, ©?=?(&$L_i$, $R_i$)© must be a well-typed expression.
     2497In the previous example, ©[x, y] = z©, ©z© is flattened into ©z.0, z.1©, and the assignments ©x = z.0© and ©y = z.1© happen.
     2498
     2499A mass assignment assigns the value $R$ to each $L_i$.
     2500For a mass assignment to be valid, ©?=?(&$L_i$, $R$)© must be a well-typed expression.
     2501These semantics differ from C cascading assignment (\eg ©a=b=c©) in that conversions are applied to $R$ in each individual assignment, which prevents data loss from the chain of conversions that can happen during a cascading assignment.
     2502For example, ©[y, x] = 3.14© performs the assignments ©y = 3.14© and ©x = 3.14©, which results in the value ©3.14© in ©y© and the value ©3© in ©x©.
     2503On the other hand, the C cascading assignment ©y = x = 3.14© performs the assignments ©x = 3.14© and ©y = x©, which results in the value ©3© in ©x©, and as a result the value ©3© in ©y© as well.
     2504
     2505Both kinds of tuple assignment have parallel semantics, such that each value on the left side and right side is evaluated \emph{before} any assignments occur.
     2506As a result, it is possible to swap the values in two variables without explicitly creating any temporary variables or calling a function.
     2507\begin{cfa}
     2508int x = 10, y = 20;
     2509[x, y] = [y, x];
     2510\end{cfa}
     2511After executing this code, ©x© has the value ©20© and ©y© has the value ©10©.
     2512
     2513In \CFA, tuple assignment is an expression where the result type is the type of the left side of the assignment, as in normal assignment.
     2514That is, a tuple assignment produces the value of the left-hand side after assignment.
     2515These semantics allow cascading tuple assignment to work out naturally in any context where a tuple is permitted.
     2516These semantics are a change from the original tuple design in \KWC \cite{Till89}, wherein tuple assignment was a statement that allows cascading assignments as a special case.
     2517Restricting tuple assignment to statements was an attempt to to fix what was seen as a problem with side-effects, wherein assignment can be used in many different locations, such as in function-call argument position.
     2518While permitting assignment as an expression does introduce the potential for subtle complexities, it is impossible to remove assignment expressions from \CFA without affecting backwards compatibility.
     2519Furthermore, there are situations where permitting assignment as an expression improves readability by keeping code succinct and reducing repetition, and complicating the definition of tuple assignment puts a greater cognitive burden on the user.
     2520In another language, tuple assignment as a statement could be reasonable, but it would be inconsistent for tuple assignment to be the only kind of assignment that is not an expression.
     2521In addition, \KWC permits the compiler to optimize tuple assignment as a block copy, since it does not support user-defined assignment operators.
     2522This optimization could be implemented in \CFA, but it requires the compiler to verify that the selected assignment operator is trivial.
     2523
     2524The following example shows multiple, mass, and cascading assignment used in one expression
     2525\begin{cfa}
     2526        int a, b;
     2527        double c, d;
     2528        [void] f([int, int]);
     2529        f([c, a] = [b, d] = 1.5);  // assignments in parameter list
     2530\end{cfa}
     2531The tuple expression begins with a mass assignment of ©1.5© into ©[b, d]©, which assigns ©1.5© into ©b©, which is truncated to ©1©, and ©1.5© into ©d©, producing the tuple ©[1, 1.5]© as a result.
     2532That tuple is used as the right side of the multiple assignment (\ie, ©[c, a] = [1, 1.5]©) that assigns ©1© into ©c© and ©1.5© into ©a©, which is truncated to ©1©, producing the result ©[1, 1]©.
     2533Finally, the tuple ©[1, 1]© is used as an expression in the call to ©f©.
     2534
     2535\subsection{Tuple Construction}
     2536Tuple construction and destruction follow the same rules and semantics as tuple assignment, except that in the case where there is no right side, the default constructor or destructor is called on each component of the tuple.
     2537As constructors and destructors did not exist in previous versions of \CFA or in \KWC, this is a primary contribution of this thesis to the design of tuples.
     2538\begin{cfa}
     2539struct S;
     2540void ?{}(S *);         // (1)
     2541void ?{}(S *, int);    // (2)
     2542void ?{}(S * double);  // (3)
     2543void ?{}(S *, S);      // (4)
     2544
     2545[S, S] x = [3, 6.28];  // uses (2), (3), specialized constructors
     2546[S, S] y;              // uses (1), (1), default constructor
     2547[S, S] z = x.0;        // uses (4), (4), copy constructor
     2548\end{cfa}
     2549In this example, ©x© is initialized by the multiple constructor calls ©?{}(&x.0, 3)© and ©?{}(&x.1, 6.28)©, while ©y© is initialized by two default constructor calls ©?{}(&y.0)© and ©?{}(&y.1)©.
     2550©z© is initialized by mass copy constructor calls ©?{}(&z.0, x.0)© and ©?{}(&z.1, x.0)©.
     2551Finally, ©x©, ©y©, and ©z© are destructed, \ie the calls ©^?{}(&x.0)©, ©^?{}(&x.1)©, ©^?{}(&y.0)©, ©^?{}(&y.1)©, ©^?{}(&z.0)©, and ©^?{}(&z.1)©.
     2552
     2553It is possible to define constructors and assignment functions for tuple types that provide new semantics, if the existing semantics do not fit the needs of an application.
     2554For example, the function ©void ?{}([T, U] *, S);© can be defined to allow a tuple variable to be constructed from a value of type ©S©.
     2555\begin{cfa}
     2556struct S { int x; double y; };
     2557void ?{}([int, double] * this, S s) {
     2558        this->0 = s.x;
     2559        this->1 = s.y;
     2560}
     2561\end{cfa}
     2562Due to the structure of generated constructors, it is possible to pass a tuple to a generated constructor for a type with a member prefix that matches the type of the tuple.
     2563For example,
     2564\begin{cfa}
     2565struct S { int x; double y; int z };
     2566[int, double] t;
     2567S s = t;
     2568\end{cfa}
     2569The initialization of ©s© with ©t© works by default because ©t© is flattened into its components, which satisfies the generated field constructor ©?{}(S *, int, double)© to initialize the first two values.
     2570
     2571\section{Member-Access Tuple Expression}
     2572\label{s:MemberAccessTuple}
     2573It is possible to access multiple fields from a single expression using a \emph{Member-Access Tuple Expression}.
     2574The result is a single tuple-valued expression whose type is the tuple of the types of the members.
     2575For example,
     2576\begin{cfa}
     2577struct S { int x; double y; char * z; } s;
     2578s.[x, y, z];
     2579\end{cfa}
     2580Here, the type of ©s.[x, y, z]© is ©[int, double, char *]©.
     2581A member tuple expression has the form ©a.[x, y, z];© where ©a© is an expression with type ©T©, where ©T© supports member access expressions, and ©x, y, z© are all members of ©T© with types ©T$_x$©, ©T$_y$©, and ©T$_z$© respectively.
     2582Then the type of ©a.[x, y, z]© is ©[T_x, T_y, T_z]©.
     2583
     2584Since tuple index expressions are a form of member-access expression, it is possible to use tuple-index expressions in conjunction with member tuple expressions to manually restructure a tuple (\eg, rearrange components, drop components, duplicate components, etc.).
     2585\begin{cfa}
     2586[int, int, long, double] x;
     2587void f(double, long);
     2588
     2589f(x.[0, 3]);          // f(x.0, x.3)
     2590x.[0, 1] = x.[1, 0];  // [x.0, x.1] = [x.1, x.0]
     2591[long, int, long] y = x.[2, 0, 2];
     2592\end{cfa}
     2593
     2594It is possible for a member tuple expression to contain other member access expressions.
     2595For example,
     2596\begin{cfa}
     2597struct A { double i; int j; };
     2598struct B { int * k; short l; };
     2599struct C { int x; A y; B z; } v;
     2600v.[x, y.[i, j], z.k];
     2601\end{cfa}
     2602This expression is equivalent to ©[v.x, [v.y.i, v.y.j], v.z.k]©.
     2603That is, the aggregate expression is effectively distributed across the tuple, which allows simple and easy access to multiple components in an aggregate, without repetition.
     2604It is guaranteed that the aggregate expression to the left of the ©.© in a member tuple expression is evaluated exactly once.
     2605As such, it is safe to use member tuple expressions on the result of a side-effecting function.
     2606\begin{cfa}
     2607[int, float, double] f();
     2608[double, float] x = f().[2, 1];
     2609\end{cfa}
     2610
     2611In \KWC, member tuple expressions are known as \emph{record field tuples} \cite{Till89}.
     2612Since \CFA permits these tuple-access expressions using structures, unions, and tuples, \emph{member tuple expression} or \emph{field tuple expression} is more appropriate.
     2613
     2614It is possible to extend member-access expressions further.
     2615Currently, a member-access expression whose member is a name requires that the aggregate is a structure or union, while a constant integer member requires the aggregate to be a tuple.
     2616In the interest of orthogonal design, \CFA could apply some meaning to the remaining combinations as well.
     2617For example,
     2618\begin{cfa}
     2619struct S { int x, y; } s;
     2620[S, S] z;
     2621
     2622s.x;  // access member
     2623z.0;  // access component
     2624
     2625s.1;  // ???
     2626z.y;  // ???
     2627\end{cfa}
     2628One possibility is for ©s.1© to select the second member of ©s©.
     2629Under this interpretation, it becomes possible to not only access members of a struct by name, but also by position.
     2630Likewise, it seems natural to open this mechanism to enumerations as well, wherein the left side would be a type, rather than an expression.
     2631One benefit of this interpretation is familiarity, since it is extremely reminiscent of tuple-index expressions.
     2632On the other hand, it could be argued that this interpretation is brittle in that changing the order of members or adding new members to a structure becomes a brittle operation.
     2633This problem is less of a concern with tuples, since modifying a tuple affects only the code that directly uses the tuple, whereas modifying a structure has far reaching consequences for every instance of the structure.
     2634
     2635As for ©z.y©, one interpretation is to extend the meaning of member tuple expressions.
     2636That is, currently the tuple must occur as the member, \ie to the right of the dot.
     2637Allowing tuples to the left of the dot could distribute the member across the elements of the tuple, in much the same way that member tuple expressions distribute the aggregate across the member tuple.
     2638In this example, ©z.y© expands to ©[z.0.y, z.1.y]©, allowing what is effectively a very limited compile-time field-sections map operation, where the argument must be a tuple containing only aggregates having a member named ©y©.
     2639It is questionable how useful this would actually be in practice, since structures often do not have names in common with other structures, and further this could cause maintainability issues in that it encourages programmers to adopt very simple naming conventions to maximize the amount of overlap between different types.
     2640Perhaps more useful would be to allow arrays on the left side of the dot, which would likewise allow mapping a field access across the entire array, producing an array of the contained fields.
     2641The immediate problem with this idea is that C arrays do not carry around their size, which would make it impossible to use this extension for anything other than a simple stack allocated array.
     2642
     2643Supposing this feature works as described, it would be necessary to specify an ordering for the expansion of member-access expressions versus member-tuple expressions.
     2644\begin{cfa}
     2645struct { int x, y; };
     2646[S, S] z;
     2647z.[x, y];  // ???
     2648// => [z.0, z.1].[x, y]
     2649// => [z.0.x, z.0.y, z.1.x, z.1.y]
     2650// or
     2651// => [z.x, z.y]
     2652// => [[z.0, z.1].x, [z.0, z.1].y]
     2653// => [z.0.x, z.1.x, z.0.y, z.1.y]
     2654\end{cfa}
     2655Depending on exactly how the two tuples are combined, different results can be achieved.
     2656As such, a specific ordering would need to be imposed to make this feature useful.
     2657Furthermore, this addition moves a member-tuple expression's meaning from being clear statically to needing resolver support, since the member name needs to be distributed appropriately over each member of the tuple, which could itself be a tuple.
     2658
     2659A second possibility is for \CFA to have named tuples, as they exist in Swift and D.
     2660\begin{cfa}
     2661typedef [int x, int y] Point2D;
     2662Point2D p1, p2;
     2663p1.x + p1.y + p2.x + p2.y;
     2664p1.0 + p1.1 + p2.0 + p2.1;  // equivalent
     2665\end{cfa}
     2666In this simpler interpretation, a tuple type carries with it a list of possibly empty identifiers.
     2667This approach fits naturally with the named return-value feature, and would likely go a long way towards implementing it.
     2668
     2669Ultimately, the first two extensions introduce complexity into the model, with relatively little perceived benefit, and so were dropped from consideration.
     2670Named tuples are a potentially useful addition to the language, provided they can be parsed with a reasonable syntax.
     2671
     2672
     2673\section{Casting}
     2674In C, the cast operator is used to explicitly convert between types.
     2675In \CFA, the cast operator has a secondary use, which is type ascription, since it forces the expression resolution algorithm to choose the lowest cost conversion to the target type.
     2676That is, a cast can be used to select the type of an expression when it is ambiguous, as in the call to an overloaded function.
     2677\begin{cfa}
     2678int f();     // (1)
     2679double f();  // (2)
     2680
     2681f();       // ambiguous - (1),(2) both equally viable
     2682(int)f();  // choose (2)
     2683\end{cfa}
     2684Since casting is a fundamental operation in \CFA, casts need to be given a meaningful interpretation in the context of tuples.
     2685Taking a look at standard C provides some guidance with respect to the way casts should work with tuples.
     2686\begin{cfa}[numbers=left]
     2687int f();
     2688void g();
     2689
     2690(void)f();  // valid, ignore results
     2691(int)g();   // invalid, void cannot be converted to int
     2692
     2693struct A { int x; };
     2694(struct A)f();  // invalid, int cannot be converted to A
     2695\end{cfa}
     2696In C, line 4 is a valid cast, which calls ©f© and discards its result.
     2697On the other hand, line 5 is invalid, because ©g© does not produce a result, so requesting an ©int© to materialize from nothing is nonsensical.
     2698Finally, line 8 is also invalid, because in C casts only provide conversion between scalar types \cite[p.~91]{C11}.
     2699For consistency, this implies that any case wherein the number of components increases as a result of the cast is invalid, while casts that have the same or fewer number of components may be valid.
     2700
     2701Formally, a cast to tuple type is valid when $T_n \leq S_m$, where $T_n$ is the number of components in the target type and $S_m$ is the number of components in the source type, and for each $i$ in $[0, n)$, $S_i$ can be cast to $T_i$.
     2702Excess elements ($S_j$ for all $j$ in $[n, m)$) are evaluated, but their values are discarded so that they are not included in the result expression.
     2703This discarding naturally follows the way that a cast to void works in C.
     2704
     2705For example,
     2706\begin{cfa}
     2707        [int, int, int] f();
     2708        [int, [int, int], int] g();
     2709
     2710        ([int, double])f();           // (1) valid
     2711        ([int, int, int])g();         // (2) valid
     2712        ([void, [int, int]])g();      // (3) valid
     2713        ([int, int, int, int])g();    // (4) invalid
     2714        ([int, [int, int, int]])g();  // (5) invalid
     2715\end{cfa}
     2716
     2717(1) discards the last element of the return value and converts the second element to type double.
     2718Since ©int© is effectively a 1-element tuple, (2) discards the second component of the second element of the return value of ©g©.
     2719If ©g© is free of side effects, this is equivalent to ©[(int)(g().0), (int)(g().1.0), (int)(g().2)]©.
     2720Since ©void© is effectively a 0-element tuple, (3) discards the first and third return values, which is effectively equivalent to ©[(int)(g().1.0), (int)(g().1.1)]©).
     2721% will this always hold true? probably, as constructors should give all of the conversion power we need. if casts become function calls, what would they look like? would need a way to specify the target type, which seems awkward. Also, C++ basically only has this because classes are closed to extension, while we don't have that problem (can have floating constructors for any type).
     2722Note that a cast is not a function call in \CFA, so flattening and structuring conversions do not occur for cast expressions.
     2723As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3.
     2724Similarly, (5) is invalid because the cast ©([int, int, int])(g().1)© is invalid.
     2725That is, it is invalid to cast ©[int, int]© to ©[int, int, int]©.
     2726
     2727\section{Polymorphism}
     2728Due to the implicit flattening and structuring conversions involved in argument passing, ©otype© and ©dtype© parameters are restricted to matching only with non-tuple types.
     2729The integration of polymorphism, type assertions, and monomorphic specialization of tuple-assertions are a primary contribution of this thesis to the design of tuples.
     2730\begin{cfa}
     2731forall(otype T, dtype U)
     2732void f(T x, U * y);
     2733
     2734f([5, "hello"]);
     2735\end{cfa}
     2736In this example, ©[5, "hello"]© is flattened, so that the argument list appears as ©5, "hello"©.
     2737The argument matching algorithm binds ©T© to ©int© and ©U© to ©const char©, and calls the function as normal.
     2738
     2739Tuples can contain otype and dtype components.
     2740For example, a plus operator can be written to add two triples of a type together.
     2741\begin{cfa}
     2742forall(otype T | { T ?+?(T, T); })
     2743[T, T, T] ?+?([T, T, T] x, [T, T, T] y) {
     2744        return [x.0+y.0, x.1+y.1, x.2+y.2];
     2745}
     2746[int, int, int] x;
     2747int i1, i2, i3;
     2748[i1, i2, i3] = x + ([10, 20, 30]);
     2749\end{cfa}
     2750Note that due to the implicit tuple conversions, this function is not restricted to the addition of two triples.
     2751A call to this plus operator type checks as long as a total of 6 non-tuple arguments are passed after flattening, and all of the arguments have a common type that can bind to ©T©, with a pairwise ©?+?© over ©T©.
     2752For example, these expressions also succeed and produce the same value.
     2753\begin{cfa}
     2754([x.0, x.1]) + ([x.2, 10, 20, 30]);  // x + ([10, 20, 30])
     2755x.0 + ([x.1, x.2, 10, 20, 30]);      // x + ([10, 20, 30])
     2756\end{cfa}
     2757This presents a potential problem if structure is important, as these three expressions look like they should have different meanings.
     2758Furthermore, these calls can be made ambiguous by introducing seemingly different functions.
     2759\begin{cfa}
     2760forall(otype T | { T ?+?(T, T); })
     2761[T, T, T] ?+?([T, T] x, [T, T, T, T]);
     2762forall(otype T | { T ?+?(T, T); })
     2763[T, T, T] ?+?(T x, [T, T, T, T, T]);
     2764\end{cfa}
     2765It is also important to note that these calls could be disambiguated if the function return types were different, as they likely would be for a reasonable implementation of ©?+?©, since the return type is used in overload resolution.
     2766Still, these semantics are a deficiency of the current argument matching algorithm, and depending on the function, differing return values may not always be appropriate.
     2767These issues could be rectified by applying an appropriate conversion cost to the structuring and flattening conversions, which are currently 0-cost conversions in the expression resolver.
     2768Care would be needed in this case to ensure that exact matches do not incur such a cost.
     2769\begin{cfa}
     2770void f([int, int], int, int);
     2771
     2772f([0, 0], 0, 0);    // no cost
     2773f(0, 0, 0, 0);      // cost for structuring
     2774f([0, 0,], [0, 0]); // cost for flattening
     2775f([0, 0, 0], 0);    // cost for flattening and structuring
     2776\end{cfa}
     2777
     2778Until this point, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (\ie, no implicit conversions are applied to assertion arguments).
     2779This decision presents a conflict with the flexibility of tuples.
     2780\subsection{Assertion Inference}
     2781\begin{cfa}
     2782int f([int, double], double);
     2783forall(otype T, otype U | { T f(T, U, U); })
     2784void g(T, U);
     2785g(5, 10.21);
     2786\end{cfa}
     2787If assertion arguments must match exactly, then the call to ©g© cannot be resolved, since the expected type of ©f© is flat, while the only ©f© in scope requires a tuple type.
     2788Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code.
     2789To ease this pain point, function parameter and return lists are flattened for the purposes of type unification, which allows the previous example to pass expression resolution.
     2790
     2791This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \cite{Bilson03}.
     2792Now, whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function.
     2793\begin{cfa}
     2794int _thunk(int _p0, double _p1, double _p2) {
     2795        return f([_p0, _p1], _p2);
     2796}
     2797\end{cfa}
     2798Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
     2799
     2800
    22262801\section{Tuples}
    22272802
    … …  
    26803255\begin{cfa}[belowskip=0pt]
    26813256char store[®sepSize®];                                          §\C{// sepSize is the maximum separator size}§
    2682 strcpy( store, sepGet( sout ) );
    2683 sepSet( sout, "_" );
     3257strcpy( store, sepGet( sout ) );                          §\C{// copy current separator}§
     3258sepSet( sout, "_" );                                            §\C{// change separator to underscore}§
    26843259sout | 1 | 2 | 3 | endl;
    26853260\end{cfa}
    … …  
    26883263\end{cfa}
    26893264\begin{cfa}[belowskip=0pt]
    2690 sepSet( sout, store );
     3265sepSet( sout, store );                                          §\C{// change separator back to original}§
    26913266sout | 1 | 2 | 3 | endl;
    26923267\end{cfa}
    … …  
    31133688
    31143689\begin{table}[hbt]
    3115 \hfil
    3116 \begin{tabular}[t]{ll}
    3117 %identifier & operation \\ \hline
    3118 ©?[?]© & subscripting \impl{?[?]}\\
    3119 ©?()© & function call \impl{?()}\\
    3120 ©?++© & postfix increment \impl{?++}\\
    3121 ©?--© & postfix decrement \impl{?--}\\
    3122 ©++?© & prefix increment \impl{++?}\\
    3123 ©--?© & prefix decrement \impl{--?}\\
    3124 ©*?© & dereference \impl{*?}\\
    3125 ©+?© & unary plus \impl{+?}\\
    3126 ©-?© & arithmetic negation \impl{-?}\\
    3127 ©~?© & bitwise negation \impl{~?}\\
    3128 ©!?© & logical complement \impl{"!?}\\
    3129 ©?*?© & multiplication \impl{?*?}\\
    3130 ©?/?© & division \impl{?/?}\\
    3131 \end{tabular}\hfil
    3132 \begin{tabular}[t]{ll}
    3133 %identifier & operation \\ \hline
    3134 ©?%?© & remainder \impl{?%?}\\
    3135 ©?+?© & addition \impl{?+?}\\
    3136 ©?-?© & subtraction \impl{?-?}\\
    3137 ©?<<?© & left shift \impl{?<<?}\\
    3138 ©?>>?© & right shift \impl{?>>?}\\
    3139 ©?<?© & less than \impl{?<?}\\
    3140 ©?<=?© & less than or equal \impl{?<=?}\\
    3141 ©?>=?© & greater than or equal \impl{?>=?}\\
    3142 ©?>?© & greater than \impl{?>?}\\
    3143 ©?==?© & equality \impl{?==?}\\
    3144 ©?!=?© & inequality \impl{?"!=?}\\
    3145 ©?&?© & bitwise AND \impl{?&?}\\
    3146 \end{tabular}\hfil
    3147 \begin{tabular}[t]{ll}
    3148 %identifier & operation \\ \hline
    3149 ©?^?© & exclusive OR \impl{?^?}\\
    3150 ©?|?© & inclusive OR \impl{?"|?}\\
    3151 ©?=?© & simple assignment \impl{?=?}\\
    3152 ©?*=?© & multiplication assignment \impl{?*=?}\\
    3153 ©?/=?© & division assignment \impl{?/=?}\\
    3154 ©?%=?© & remainder assignment \impl{?%=?}\\
    3155 ©?+=?© & addition assignment \impl{?+=?}\\
    3156 ©?-=?© & subtraction assignment \impl{?-=?}\\
    3157 ©?<<=?© & left-shift assignment \impl{?<<=?}\\
    3158 ©?>>=?© & right-shift assignment \impl{?>>=?}\\
    3159 ©?&=?© & bitwise AND assignment \impl{?&=?}\\
    3160 ©?^=?© & exclusive OR assignment \impl{?^=?}\\
    3161 ©?|=?© & inclusive OR assignment \impl{?"|=?}\\
    3162 \end{tabular}
    3163 \hfil
     3690\centering
     3691\input{../refrat/operidents}
    31643692\caption{Operator Identifiers}
    31653693\label{opids}
    … …  
    32083736\section{Auto Type-Inferencing}
    32093737
    3210 Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization expression type.
     3738Auto type-inferencing occurs in a declaration where a variable's type is inferred from its initialization ex\-pression type.
    32113739\begin{quote2}
    32123740\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
    … …  
    32373765\begin{itemize}
    32383766\item
    3239 preventing having to determine or write out long generic types,
     3767preventing having to determine or write long generic types,
    32403768\item
    32413769ensure secondary variables, related to a primary variable, always have the same type.
    … …  
    32453773\Indexc{gcc} provides ©typeof© to declare a secondary variable from a primary variable.
    32463774\CFA also relies heavily on the specification of the left-hand side of assignment for type inferencing, so in many cases it is crucial to specify the type of the left-hand side to select the correct type of the right-hand expression.
    3247 Only for overloaded routines with the same return type is variable type-inferencing possible.
     3775Only for overloaded routines \emph{with the same return type} is variable type-inferencing possible.
    32483776Finally, ©auto© presents the programming problem of tracking down a type when the type is actually needed.
    32493777For example, given
    … …  
    32613789There is also the conundrum in type inferencing of when to \emph{\Index{brand}} a type.
    32623790That is, when is the type of the variable more important than the type of its initialization expression.
    3263 For example, if a change is made in an initialization expression, it can cause hundreds or thousands of cascading type changes and/or errors.
    3264 At some point, a programmer wants the type of the variable to remain constant and the expression to be in error when it changes.
     3791For example, if a change is made in an initialization expression, it can cause significant cascading type changes and/or errors.
     3792At some point, a variable type needs to remain constant and the expression to be in error when it changes.
    32653793
    32663794Given ©typedef© and ©typeof© in \CFA, and the strong need to use the type of left-hand side in inferencing, auto type-inferencing is not supported at this time.
    … …  
    34754003        }
    34764004\end{cfa}
    3477 \end{comment}
    3478 
    3479 
    3480 \subsection{Memory Management}
    3481 
    3482 
    3483 \subsubsection{Manual Memory Management}
    3484 
    3485 Using malloc and free to dynamically allocate memory exposes several potential, and common, errors.
    3486 First, malloc breaks type safety because it returns a pointer to void.
    3487 There is no relationship between the type that the returned pointer is cast to, and the amount of memory allocated.
    3488 This problem is solved with a type-safe malloc.
    3489 Do.s type-safe malloc does not take any arguments for size.
    3490 Instead, it infers the type based on the return value, and then allocates space for the inferred type.
    3491 
    3492 \begin{cfa}
    3493 float *f = malloc(); // allocates the size of a float
    3494 
    3495 struct S {
    3496         int i, j, k;
    3497 };
    3498 
    3499 struct S *s = malloc(); // allocates the size of a struct S
    3500 \end{cfa}
    3501 
    3502 In addition to the improved malloc, \CFA also provides a technique for combining allocation and initialization into one step, using the new function.
    3503 For all constructors defined for a given type (see Operator Overloading), a corresponding call to new can be used to allocate and construct that type.
    3504 
    3505 \begin{cfa}
    3506 type Complex = struct {
    3507         float real;
    3508         float imag;
    3509 };
    3510 
    3511 // default constructor
    3512 
    3513 void ?{}(Complex &c) {
    3514         c.real = 0.0;
    3515         c.imag = 0.0;
    3516 }
    3517 
    3518 
    3519 
    3520 // 2 parameter constructor
    3521 
    3522 void ?{}(Complex &c, float real, float imag) {
    3523         c.real = real;
    3524         c.imag = imag;
    3525 }
    3526 
    3527 
    3528 int main() {
    3529         Complex c1; // No constructor is called
    3530         Complex c2{}; // Default constructor called
    3531         Complex c3{1.0, -1.0}; // 2 parameter constructor is called
    3532 
    3533         Complex *p1 = malloc(); // allocate
    3534         Complex *p2 = new(); // allocate + default constructor
    3535         Complex *p3 = new(0.5, 1.0); // allocate + 2 param constructor
    3536 }
    3537 \end{cfa}
    3538 
    3539 
    3540 \subsubsection{Automatic Memory Management}
    3541 
    3542 \CFA may also support automatic memory management to further improve safety.
    3543 If the compiler can insert all of the code needed to manage dynamically allocated memory (automatic reference counting), then developers can avoid problems with dangling pointers, double frees, memory leaks, etc.
    3544 This feature requires further investigation.
    3545 \CFA will not have a garbage collector, but might use some kind of region-based memory management.
    3546 
    3547 
    3548 \begin{comment}
    3549 \subsection{Unsafe C Constructs}
    3550 
    3551 C programmers are able to access all of the low-level tricks that are sometimes needed for close-to-the-hardware programming.
    3552 Some of these practices however are often error-prone and difficult to read and maintain.
    3553 Since \CFA is designed to be safer than C, such constructs are disallowed in \CFA code.
    3554 If a programmer wants to use one of these unsafe C constructs, the unsafe code must be contained in a C linkage block (see Interoperability), which will be compiled like C code.
    3555 This block means that the user is telling the tools, .I know this is unsafe, but I.m going to do it anyway..
    3556 
    3557 The exact set of unsafe C constructs that will be disallowed in \CFA has not yet been decided, but is sure to include pointer arithmetic, pointer casting, etc.
    3558 Once the full set is decided, the rules will be listed here.
    35594005\end{comment}
    35604006
    … …  
    37804226\label{f:SimpleTasks}
    37814227\end{figure}
    3782 
    3783 
    3784 \begin{comment}
    3785 \begin{cfa}
    3786 type Adder = task {
    3787         int *row;
    3788         int size;
    3789         int &subtotal;
    3790 }
    3791 \end{cfa}
    3792 
    3793 A task may define a constructor, which will be called upon allocation and run on the caller.s thread.
    3794 A destructor may also be defined, which is called at deallocation (when a dynamic object is deleted or when a local object goes out of scope).
    3795 After a task is allocated and initialized, its thread is spawned implicitly and begins executing in its function call method.
    3796 All tasks must define this function call method, with a void return value and no additional parameters, or the compiler will report an error.
    3797 Below are example functions for the above Adder task, and its usage to sum up a matrix on multiple threads.
    3798 (Note that this example is designed to display the syntax and functionality, not the best method to solve this problem)
    3799 \begin{cfa}
    3800 void ?{}(Adder &a, int r[], int s, int &st) { // constructor
    3801         a.row = r;
    3802         a.size = s;
    3803         a.subtotal = st;
    3804 }
    3805 
    3806 // implicitly spawn thread and begin execution here
    3807 
    3808 void ?()(Adder &a) {
    3809         int c;
    3810         subtotal = 0;
    3811         for (c=0; c<a.size; ++c) {
    3812         subtotal += row[c];
    3813         }
    3814 }
    3815 
    3816 int main() {
    3817         const int rows = 100, cols = 1000000;
    3818         int matrix[rows][cols];
    3819         int subtotals[rows];
    3820         int total = 0;
    3821         int r;
    3822 
    3823         { // create a new scope here for our adders
    3824         Adder adders[rows];
    3825         // read in the matrix
    3826         ...
    3827         for (r=0; r<rows; ++r) {
    3828         // tasks are initialized on this thread
    3829         Adders[r] = {matrix[r], cols, subtotals[r]};
    3830         Adders[r](); // spawn thread and begin execution
    3831         }
    3832         } // adders go out of scope; block here until they all finish
    3833         total += subtotals[r];
    3834         printf(.total is %d\n., total);
    3835 }
    3836 \end{cfa}
    3837 
    3838 \subsection{Cooperative Scheduling}
    3839 
    3840 Tasks in \CFA are cooperatively scheduled, meaning that a task will not be interrupted by another task, except at specific yield points.
    3841 In Listing 31, there are no yield points, so each task runs to completion with no interruptions.
    3842 Places where a task could yield include waiting for a lock (explicitly or implicitly), waiting for I/O, or waiting for a specific function (or one of a set of functions) to be called.
    3843 This last option is introduced with the yield function. yield is used to indicate that this task should yield its thread until the specified function is called.
    3844 For example, the code below defines a monitor that maintains a generic list.
    3845 When a task tries to pop from the list, but it is empty, the task should yield until another task puts something into the list, with the push function.
    3846 Similarly, when a task tries to push something onto the list, but it is full, it will yield until another task frees some space with the pop function.
    3847 
    3848 \begin{cfa}
    3849 // type T is used as a generic type for all definitions inside
    3850 // the curly brackets
    3851 
    3852 generic(type T) {
    3853         type Channel = monitor {
    3854         List(T) list; // list is a simple generic list type
    3855         };
    3856 
    3857         T pop(mutex &Channel(T) ch) {
    3858         if (ch.list.empty()) {
    3859         // yield until push is called for this channel
    3860         yield(push);
    3861         }
    3862         return ch.list.pop();
    3863         }
    3864 
    3865         void push(mutex &Channel(T)ch, T val) {
    3866         if (ch.list.full()) {
    3867         // yield until pop is called for this channel
    3868         yield(pop);
    3869         }
    3870         ch.list.push(val);
    3871         }
    3872 }
    3873 \end{cfa}
    3874 
    3875 A task can also yield indefinitely by calling yield with no arguments.
    3876 This will tell the scheduler to yield this task until it is resumed by some other task.
    3877 A task can resume another task by using its functional call operator.
    3878 The code below shows a simple ping-pong example, where two tasks yield back and forth to each other using these methods.
    3879 
    3880 \begin{cfa}
    3881 type Ping = task {
    3882         Pong *partner;
    3883 };
    3884 
    3885 void ?{}(Ping &p, Pong *partner = 0) {
    3886         p.partner = partner;
    3887 }
    3888 
    3889 void ?()(Ping &p) {
    3890         for(;;) { // loop forever
    3891         printf(.ping\n.);
    3892         partner(); // resumes the partner task
    3893         yield(); // yields this task
    3894         }
    3895 }
    3896 
    3897 type Pong = task {
    3898         Ping *partner;
    3899 };
    3900 
    3901 void ?{}(Pong &p, Ping *partner = 0) {
    3902         p.partner = partner;
    3903 }
    3904 
    3905 void ?()(Pong &p) {
    3906         for(;;) { // loop forever
    3907         yield(); // yields this task
    3908         printf(.pong/n.);
    3909         partner(); // resumes the partner task
    3910         }
    3911 }
    3912 
    3913 void main() {
    3914         Ping ping; // allocate ping
    3915         Pong pong{ping}; // allocate, initialize, and start pong
    3916         Ping{pong}; // initialize and start ping
    3917 }
    3918 \end{cfa}
    3919 
    3920 The same functionality can be accomplished by providing functions to be called by the partner task.
    3921 \begin{cfa}
    3922 type Pingpong = task {
    3923         String msg;
    3924         Pingpong *partner;
    3925 };
    3926 
    3927 void ?{}(Pingpong &p, String msg, Pingpong *partner = 0) {
    3928         p.msg = msg;
    3929         p.partner = partner;
    3930 }
    3931 
    3932 void ?()(Pingpong &p) {
    3933         for(;;) {
    3934         yield(go);
    3935         }
    3936 }
    3937 
    3938 void go(Pingpong &p) {
    3939         print(.%(p.msg)\n.);
    3940         go(p.partner);
    3941 }
    3942 
    3943 void main() {
    3944         Pingpong ping = {.ping.};
    3945         Pingpong pong = {.pong., ping};
    3946         ping.partner = pong;
    3947         go(ping);
    3948 }
    3949 \end{cfa}
    3950 \end{comment}
    39514228
    39524229
    … …  
    46094886
    46104887
    4611 \section{Comparison with Other Languages}
     4888\section{Language Comparisons}
    46124889
    46134890\CFA is one of many languages that attempts to improve upon C.
    … …  
    53445621
    53455622
    5346 \section{\texorpdfstring{\CFA Keywords}{Cforall Keywords}}
    5347 \label{s:CFAKeywords}
    5348 
    5349 \CFA introduces the following new keywords.
    5350 
    5351 \begin{quote2}
    5352 \begin{tabular}{lllll}
    5353 \begin{tabular}{@{}l@{}}
    5354 ©_At©                   \\
    5355 ©catch©                 \\
    5356 ©catchResume©   \\
    5357 ©choose©                \\
    5358 ©coroutine©             \\
    5359 \end{tabular}
    5360 &
    5361 \begin{tabular}{@{}l@{}}
    5362 ©disable©               \\
    5363 ©dtype©                 \\
    5364 ©enable©                \\
    5365 ©fallthrough©   \\
    5366 ©fallthru©              \\
    5367 \end{tabular}
    5368 &
    5369 \begin{tabular}{@{}l@{}}
    5370 ©finally©               \\
    5371 ©forall©                \\
    5372 ©ftype©                 \\
    5373 ©lvalue©                \\
    5374 ©monitor©               \\
    5375 \end{tabular}
    5376 &
    5377 \begin{tabular}{@{}l@{}}
    5378 ©mutex©                 \\
    5379 ©one_t©                 \\
    5380 ©otype©                 \\
    5381 ©throw©                 \\
    5382 ©throwResume©   \\
    5383 \end{tabular}
    5384 &
    5385 \begin{tabular}{@{}l@{}}
    5386 ©trait©                 \\
    5387 ©try©                   \\
    5388 ©ttype©                 \\
    5389 ©zero_t©                \\
    5390                                 \\
    5391 \end{tabular}
    5392 \end{tabular}
    5393 \end{quote2}
    5394 
    5395 
    5396 \section{Incompatible}
     5623\section{C Incompatibles}
    53975624
    53985625The following incompatibles exist between \CFA and C, and are similar to Annex C for \CC~\cite{C++14}.
    … …  
    54225649g( p1, p2 ) int p1, p2;                 §\C{// int g( int p1, int p2 );}§
    54235650\end{cfa}
    5424 \CFA supports K\&R routine definitions:
     5651\CFA continues to support K\&R routine definitions:
    54255652\begin{cfa}
    54265653f( a, b, c )                                    §\C{// default int return}§
    … …  
    54955722struct X { int i; struct X *next; };
    54965723static struct X a;                              §\C{// forward definition}§
    5497 static struct X b = { 0, ®&a® };        §\C{// forward reference, valid in C, invalid in \CFA}§
     5724static struct X b = { 0, ®&a® };§\C{// forward reference, valid in C, invalid in \CFA}§
    54985725static struct X a = { 1, &b };  §\C{// definition}§
    54995726\end{cfa}
    … …  
    55105737enum ®Colour® { R, G, B, Y, C, M };
    55115738struct Person {
    5512         enum ®Colour® { R, G, B };      §\C{// nested type}§
     5739        enum ®Colour® { R, G, B };      §\C[7cm]{// nested type}§
    55135740        struct Face {                           §\C{// nested type}§
    55145741                ®Colour® Eyes, Hair;    §\C{// type defined outside (1 level)}§
    … …  
    55195746};
    55205747®Colour® c = R;                                 §\C{// type/enum defined same level}§
    5521 Person®.Colour® pc = Person®.®R;        §\C{// type/enum defined inside}§
    5522 Person®.®Face pretty;                   §\C{// type defined inside}§
     5748Person®.Colour® pc = Person®.®R;§\C{// type/enum defined inside}§
     5749Person®.®Face pretty;                   §\C{// type defined inside}\CRT§
    55235750\end{cfa}
    55245751In C, the name of the nested types belongs to the same scope as the name of the outermost enclosing structure, \ie the nested types are hoisted to the scope of the outer-most type, which is not useful and confusing.
    … …  
    55495776\item
    55505777\begin{description}
     5778\item[Change:] remove implicit conversion of ©void *© to or from any ©T *© pointer:
     5779\begin{cfa}
     5780void foo() {
     5781        int * b = malloc( sizeof(int) );        §\C{// implicitly convert void * to int *}§
     5782        char * c = b;                           §\C{// implicitly convert int * to void *, and then void * to char *}§
     5783}
     5784\end{cfa}
     5785\item[Rationale:] increase type safety
     5786\item[Effect on original feature:] deletion of semantically well-defined feature.
     5787\item[Difficulty of converting:] requires adding a cast (see \VRef{s:StorageManagement} for better alternatives):
     5788\begin{cfa}
     5789        int * b = (int *)malloc( sizeof(int) );
     5790        char * c = (char *)b;
     5791\end{cfa}
     5792\item[How widely used:] Significant.
     5793Some C translators already give a warning if the cast is not used.
     5794\end{description}
     5795
     5796\item
     5797\begin{description}
     5798\item[Change:] Types must be declared in declarations, not in expressions
     5799In C, a sizeof expression or cast expression may create a new type. For example,
     5800\begin{cfa}
     5801p = (void*)(struct x {int i;} *)0;
     5802\end{cfa}
     5803declares a new type, struct x .
     5804\item[Rationale:] This prohibition helps to clarify the location of declarations in the source code.
     5805\item[Effect on original feature:] Deletion of a semantically welldefined feature.
     5806\item[Difficulty of converting:] Syntactic transformation.
     5807\item[How widely used:] Seldom.
     5808\end{description}
     5809
     5810\item
     5811\begin{description}
    55515812\item[Change:] comma expression is disallowed as subscript
    55525813\item[Rationale:] safety issue to prevent subscripting error for multidimensional arrays: ©x[i,j]© instead of ©x[i][j]©, and this syntactic form then taken by \CFA for new style arrays.
    55535814\item[Effect on original feature:] change to semantics of well-defined feature.
    55545815\item[Difficulty of converting:] semantic transformation of ©x[i,j]© to ©x[(i,j)]©
    5555 \item[How widely used:] seldom.
     5816\item[How widely used:] Seldom.
    55565817\end{description}
    55575818\end{enumerate}
    55585819
    55595820
     5821\section{\texorpdfstring{\CFA Keywords}{Cforall Keywords}}
     5822\label{s:CFAKeywords}
     5823
     5824\CFA introduces the following new keywords.
     5825
     5826\begin{quote2}
     5827\input{../refrat/keywords}
     5828\end{quote2}
     5829
     5830
    55605831\section{Standard Headers}
    55615832\label{s:StandardHeaders}
    … …  
    55635834\Celeven prescribes the following standard header-files~\cite[\S~7.1.2]{C11} and \CFA adds to this list:
    55645835\begin{quote2}
    5565 \lstset{deletekeywords={float}}
    5566 \begin{tabular}{@{}llll|l@{}}
    5567 \multicolumn{4}{c|}{C11} & \multicolumn{1}{c}{\CFA}             \\
     5836\begin{tabular}{@{}llllll|l@{}}
     5837\multicolumn{6}{c|}{C11} & \multicolumn{1}{c}{\CFA}             \\
    55685838\hline
    55695839\begin{tabular}{@{}l@{}}
    … …  
    55735843\Indexc{errno.h}                \\
    55745844\Indexc{fenv.h}                 \\
    5575 \Indexc{float.h}                \\
    5576 \Indexc{inttypes.h}             \\
    5577 \Indexc{iso646.h}               \\
    55785845\end{tabular}
    55795846&
    55805847\begin{tabular}{@{}l@{}}
     5848\Indexc[deletekeywords=float]{float.h} \\
     5849\Indexc{inttypes.h}             \\
     5850\Indexc{iso646.h}               \\
    55815851\Indexc{limits.h}               \\
    55825852\Indexc{locale.h}               \\
     5853\end{tabular}
     5854&
     5855\begin{tabular}{@{}l@{}}
    55835856\Indexc{math.h}                 \\
    55845857\Indexc{setjmp.h}               \\
    … …  
    55865859\Indexc{stdalign.h}             \\
    55875860\Indexc{stdarg.h}               \\
    5588 \Indexc{stdatomic.h}    \\
    55895861\end{tabular}
    55905862&
    55915863\begin{tabular}{@{}l@{}}
     5864\Indexc{stdatomic.h}    \\
    55925865\Indexc{stdbool.h}              \\
    55935866\Indexc{stddef.h}               \\
    55945867\Indexc{stdint.h}               \\
    55955868\Indexc{stdio.h}                \\
     5869\end{tabular}
     5870&
     5871\begin{tabular}{@{}l@{}}
    55965872\Indexc{stdlib.h}               \\
    55975873\Indexc{stdnoreturn.h}  \\
    55985874\Indexc{string.h}               \\
    55995875\Indexc{tgmath.h}               \\
     5876\Indexc{threads.h}              \\
    56005877\end{tabular}
    56015878&
    56025879\begin{tabular}{@{}l@{}}
    5603 \Indexc{threads.h}              \\
    56045880\Indexc{time.h}                 \\
    56055881\Indexc{uchar.h}                \\
    … …  
    56075883\Indexc{wctype.h}               \\
    56085884                                                \\
    5609                                                 \\
    5610                                                 \\
    56115885\end{tabular}
    56125886&
    56135887\begin{tabular}{@{}l@{}}
     5888\Indexc{gmp.h}                  \\
     5889\Indexc{malloc.h}               \\
    56145890\Indexc{unistd.h}               \\
    5615 \Indexc{gmp.h}                  \\
    5616                                                 \\
    5617                                                 \\
    5618                                                 \\
    5619                                                 \\
    56205891                                                \\
    56215892                                                \\
    … …  
    56265897hence, names in these include files are not mangled\index{mangling!name} (see~\VRef{s:Interoperability}).
    56275898All other C header files must be explicitly wrapped in ©extern "C"© to prevent name mangling.
    5628 For \Index*[C++]{\CC{}}, the name-mangling issue is handled implicitly because most C header-files are augmented with checks for preprocessor variable ©__cplusplus©, which adds appropriate ©extern "C"© qualifiers.
     5899For \Index*[C++]{\CC{}}, the name-mangling issue is often handled internally in many C header-files through checks for preprocessor variable ©__cplusplus©, which adds appropriate ©extern "C"© qualifiers.
    56295900
    56305901
    … …  
    56365907
    56375908\subsection{Storage Management}
     5909\label{s:StorageManagement}
    56385910
    56395911The storage-management routines extend their C equivalents by overloading, alternate names, providing shallow type-safety, and removing the need to specify the allocation size for non-array types.
    … …  
    56555927The table shows allocation routines supporting different combinations of storage-management capabilities:
    56565928\begin{center}
    5657 \begin{tabular}{@{}lr|l|l|l|l@{}}
    5658                 &                                       & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
     5929\begin{tabular}{@{}r|r|l|l|l|l@{}}
     5930\multicolumn{1}{c}{}&           & \multicolumn{1}{c|}{fill}     & resize        & alignment     & array \\
    56595931\hline
    56605932C               & ©malloc©                      & no                    & no            & no            & no    \\
    … …  
    56635935                & ©memalign©            & no                    & no            & yes           & no    \\
    56645936                & ©posix_memalign©      & no                    & no            & yes           & no    \\
     5937\hline
    56655938C11             & ©aligned_alloc©       & no                    & no            & yes           & no    \\
     5939\hline
    56665940\CFA    & ©alloc©                       & no/copy/yes   & no/yes        & no            & yes   \\
    56675941                & ©align_alloc©         & no/yes                & no            & yes           & yes   \\
    … …  
    58476121long double remainder( long double, long double );
    58486122
    5849 [ int, float ] remquo( float, float );§\indexc{remquo}§
    5850 float remquo( float, float, int * );
     6123float remquo( float, float, int * );§\indexc{remquo}§
     6124double remquo( double, double, int * );
     6125long double remquo( long double, long double, int * );
     6126[ int, float ] remquo( float, float );
    58516127[ int, double ] remquo( double, double );
    5852 double remquo( double, double, int * );
    58536128[ int, long double ] remquo( long double, long double );
    5854 long double remquo( long double, long double, int * );
    5855 
    5856 [ int, float ] div( float, float );                                             // alternative name for remquo
    5857 float div( float, float, int * );§\indexc{div}§
     6129
     6130float div( float, float, int * );§\indexc{div}§ §\C{// alternative name for remquo}§
     6131double div( double, double, int * );
     6132long double div( long double, long double, int * );
     6133[ int, float ] div( float, float );
    58586134[ int, double ] div( double, double );
    5859 double div( double, double, int * );
    58606135[ int, long double ] div( long double, long double );
    5861 long double div( long double, long double, int * );
    58626136
    58636137float fma( float, float, float );§\indexc{fma}§
    … …  
    58896163double exp2( double );
    58906164long double exp2( long double );
    5891 float _Complex exp2( float _Complex );
    5892 double _Complex exp2( double _Complex );
    5893 long double _Complex exp2( long double _Complex );
     6165// float _Complex exp2( float _Complex );
     6166// double _Complex exp2( double _Complex );
     6167// long double _Complex exp2( long double _Complex );
    58946168
    58956169float expm1( float );§\indexc{expm1}§
    … …  
    58976171long double expm1( long double );
    58986172
     6173float pow( float, float );§\indexc{pow}§
     6174double pow( double, double );
     6175long double pow( long double, long double );
     6176float _Complex pow( float _Complex, float _Complex );
     6177double _Complex pow( double _Complex, double _Complex );
     6178long double _Complex pow( long double _Complex, long double _Complex );
     6179\end{cfa}
     6180
     6181
     6182\subsection{Logarithm}
     6183
     6184\leavevmode
     6185\begin{cfa}[aboveskip=0pt,belowskip=0pt]
    58996186float log( float );§\indexc{log}§
    59006187double log( double );
    … …  
    59076194double log2( double );
    59086195long double log2( long double );
    5909 float _Complex log2( float _Complex );
    5910 double _Complex log2( double _Complex );
    5911 long double _Complex log2( long double _Complex );
     6196// float _Complex log2( float _Complex );
     6197// double _Complex log2( double _Complex );
     6198// long double _Complex log2( long double _Complex );
    59126199
    59136200float log10( float );§\indexc{log10}§
    59146201double log10( double );
    59156202long double log10( long double );
    5916 float _Complex log10( float _Complex );
    5917 double _Complex log10( double _Complex );
    5918 long double _Complex log10( long double _Complex );
     6203// float _Complex log10( float _Complex );
     6204// double _Complex log10( double _Complex );
     6205// long double _Complex log10( long double _Complex );
    59196206
    59206207float log1p( float );§\indexc{log1p}§
    … …  
    59296216double logb( double );
    59306217long double logb( long double );
    5931 \end{cfa}
    5932 
    5933 
    5934 \subsection{Power}
    5935 
    5936 \leavevmode
    5937 \begin{cfa}[aboveskip=0pt,belowskip=0pt]
     6218
    59386219float sqrt( float );§\indexc{sqrt}§
    59396220double sqrt( double );
    … …  
    59506231double hypot( double, double );
    59516232long double hypot( long double, long double );
    5952 
    5953 float pow( float, float );§\indexc{pow}§
    5954 double pow( double, double );
    5955 long double pow( long double, long double );
    5956 float _Complex pow( float _Complex, float _Complex );
    5957 double _Complex pow( double _Complex, double _Complex );
    5958 long double _Complex pow( long double _Complex, long double _Complex );
    59596233\end{cfa}
    59606234
    … …  
    60106284long double atan2( long double, long double );
    60116285
    6012 float atan( float, float );                                                             // alternative name for atan2
     6286float atan( float, float );                                     §\C{// alternative name for atan2}§
    60136287double atan( double, double );§\indexc{atan}§
    60146288long double atan( long double, long double );
    … …  
    61986472
    61996473\begin{cfa}
    6200 void ?{}( Int * this );                                 §\C{// constructor}§
     6474void ?{}( Int * this );                                 §\C{// constructor/destructor}§
    62016475void ?{}( Int * this, Int init );
    62026476void ?{}( Int * this, zero_t );
    … …  
    64536727// implementation
    64546728struct Rational {§\indexc{Rational}§
    6455         long int numerator, denominator;                                        // invariant: denominator > 0
     6729        long int numerator, denominator;        §\C{// invariant: denominator > 0}§
    64566730}; // Rational
    64576731

  • doc/working/resolver_design.md

    r3d4b23fa r0720e049  
    9191## Conversion Costs ##
    9292Each possible resolution of an expression has a _cost_ tuple consisting of
    93 the following components: _unsafe_ conversion cost, _polymorphic_
    94 specialization cost, _safe_ conversion cost, a count of _explicit_
    95 conversions, and _qualifier_ conversion cost.
     93the following components:
     941. _unsafe_ conversion cost: summed degree of unsafe conversions; unlike CFA03, this is not a simple count of conversions (for symmetry with the safe conversions)
     952. _polymorphic unifications_: count of parameters and return values bound to some polymorphic type for boxing
     963. _type variables_: number of polymorphic type variables bound
     974. negated _type specializations_: Each type assertion specializes the polymorphism, thus decreasing the cost; nested polymorphic types (e.g. `T*`) are also counted as specializations
     985. _safe_ conversions: summed degree of safe conversions
     996. _qualifier_ conversions: summed degree of qualifier and reference conversions
    96100These components are lexically-ordered and can be summed element-wise;
    97101summation starts at `(0, 0, 0, 0, 0)`.
     102
     103**TODO** update below for consistency with this
    98104
    99105### Lvalue and Qualifier Conversions ###
Note: See TracChangeset for help on using the changeset viewer.