Index: doc/papers/concurrency/Paper.tex
===================================================================
--- doc/papers/concurrency/Paper.tex (revision 7bdcac1f3631ee6408a86b4d0321433114fee6d3)
+++ doc/papers/concurrency/Paper.tex (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
@@ -580,7 +580,7 @@
\subsection{\protect\CFA's Thread Building Blocks}
-An important missing feature in C is threading\footnote{While the C11 standard defines a ``threads.h'' header, it is minimal and defined as optional.
+An important missing feature in C is threading\footnote{While the C11 standard defines a \protect\lstinline@threads.h@ header, it is minimal and defined as optional.
As such, library support for threading is far from widespread.
-At the time of writing the paper, neither \protect\lstinline|gcc| nor \protect\lstinline|clang| support ``threads.h'' in their standard libraries.}.
+At the time of writing the paper, neither \protect\lstinline@gcc@ nor \protect\lstinline@clang@ support \protect\lstinline@threads.h@ in their standard libraries.}.
In modern programming languages, a lack of threading is unacceptable~\cite{Sutter05, Sutter05b}, and therefore existing and new programming languages must have tools for writing efficient concurrent programs to take advantage of parallelism.
As an extension of C, \CFA needs to express these concepts in a way that is as natural as possible to programmers familiar with imperative languages.
@@ -1140,5 +1140,5 @@
}
\end{cfa}
-A consequence of the strongly typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \textbf{api}.
+A consequence of the strongly typed approach to main is that memory layout of parameters and return values to/from a thread are now explicitly specified in the \textbf{API}.
\end{comment}
@@ -1443,8 +1443,9 @@
\label{s:InternalScheduling}
-While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed, \eg a bounded buffer, Figure~\ref{f:GenericBoundedBuffer}, may be full/empty so produce/consumer threads must block.
+While monitor mutual-exclusion provides safe access to shared data, the monitor data may indicate that a thread accessing it cannot proceed.
+For example, Figure~\ref{f:GenericBoundedBuffer} shows a bounded buffer that may be full/empty so produce/consumer threads must block.
Leaving the monitor and trying again (busy waiting) is impractical for high-level programming.
Monitors eliminate busy waiting by providing internal synchronization to schedule threads needing access to the shared data, where the synchronization is blocking (threads are parked) versus spinning.
-The synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} is defined as indicating which thread acquires the critical section next.
+Synchronization is generally achieved with internal~\cite{Hoare74} or external~\cite[\S~2.9.2]{uC++} scheduling, where \newterm{scheduling} defines which thread acquires the critical section next.
\newterm{Internal scheduling} is characterized by each thread entering the monitor and making an individual decision about proceeding or blocking, while \newterm{external scheduling} is characterized by an entering thread making a decision about proceeding for itself and on behalf of other threads attempting entry.
@@ -1537,239 +1538,26 @@
External scheduling is controlled by the @waitfor@ statement, which atomically blocks the calling thread, releases the monitor lock, and restricts the routine calls that can next acquire mutual exclusion.
If the buffer is full, only calls to @remove@ can acquire the buffer, and if the buffer is empty, only calls to @insert@ can acquire the buffer.
-Threads making calls to routines that are currently excluded block outside (externally) of the monitor on a calling queue, versus blocking on condition queues inside the monitor.
-
-Both internal and external scheduling extend to multiple monitors in a natural way.
-\begin{cfa}
-monitor M { `condition e`; ... };
-void foo( M & mutex m1, M & mutex m2 ) {
- ... wait( `e` ); ... $\C{// wait( e, m1, m2 )}$
- ... wait( `e, m1` ); ...
- ... wait( `e, m2` ); ...
-}
-
-void rtn$\(_1\)$( M & mutex m1, M & mutex m2 );
-void rtn$\(_2\)$( M & mutex m1 );
-void bar( M & mutex m1, M & mutex m2 ) {
- ... waitfor( `rtn` ); ... $\C{// waitfor( rtn\(_1\), m1, m2 )}$
- ... waitfor( `rtn, m1` ); ... $\C{// waitfor( rtn\(_2\), m1 )}$
-}
-\end{cfa}
-For @wait( e )@, the default semantics is to atomically block the signaller and release all acquired mutex types in the parameter list, \ie @wait( e, m1, m2 )@.
-To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @wait( e, m1 )@.
-Wait statically verifies the released monitors are the acquired mutex-parameters so unconditional release is safe.
-Similarly, for @waitfor( rtn, ... )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
-To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @waitfor( rtn, m1 )@.
-Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
-To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
-
-Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
-\begin{cfa}
-void foo( M & mutex m1, M & mutex m2 ) {
- ... wait( `e, m1` ); ... $\C{// release m1, keeping m2 acquired )}$
-void baz( M & mutex m1, M & mutex m2 ) { $\C{// must acquire m1 and m2 )}$
- ... signal( `e` ); ...
-\end{cfa}
-The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to enter @baz@ to get to the @signal@.
-While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
-
-Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
-If barging is allowed, synchronization between a singller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
-\begin{quote}
-However, we decree that a signal operation be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program.
-It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
-\end{quote}
-\CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
-For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
-Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design and implementation of \CFA concurrency.
-
-
-\subsection{Barging Prevention}
-
-Figure~\ref{f:BargingPrevention} shows \CFA code where bulk acquire adds complexity to the internal-signalling semantics.
-The complexity begins at the end of the inner @mutex@ statement, where the semantics of internal scheduling need to be extended for multiple monitors.
-The problem is that bulk acquire is used in the inner @mutex@ statement where one of the monitors is already acquired.
-When the signalling thread reaches the end of the inner @mutex@ statement, it should transfer ownership of @m1@ and @m2@ to the waiting thread to prevent barging into the outer @mutex@ statement by another thread.
-However, both the signalling and signalled threads still need monitor @m1@.
-
-\begin{figure}
-\newbox\myboxA
-\begin{lrbox}{\myboxA}
-\begin{cfa}[aboveskip=0pt,belowskip=0pt]
-monitor M m1, m2;
-condition c;
-mutex( m1 ) {
- ...
- mutex( m1, m2 ) {
- ... `wait( c )`; // block and release m1, m2
- // m1, m2 acquired
- } // $\LstCommentStyle{\color{red}release m2}$
- // m1 acquired
-} // release m1
-\end{cfa}
-\end{lrbox}
-
-\newbox\myboxB
-\begin{lrbox}{\myboxB}
-\begin{cfa}[aboveskip=0pt,belowskip=0pt]
-
-
-mutex( m1 ) {
- ...
- mutex( m1, m2 ) {
- ... `signal( c )`; ...
- // m1, m2 acquired
- } // $\LstCommentStyle{\color{red}release m2}$
- // m1 acquired
-} // release m1
-\end{cfa}
-\end{lrbox}
-
-\newbox\myboxC
-\begin{lrbox}{\myboxC}
-\begin{cfa}[aboveskip=0pt,belowskip=0pt]
-
-
-mutex( m1 ) {
- ... `wait( c )`; ...
- // m1 acquired
-} // $\LstCommentStyle{\color{red}release m1}$
-
-
-
-
-\end{cfa}
-\end{lrbox}
-
-\begin{cquote}
-\subfloat[Waiting Thread]{\label{f:WaitingThread}\usebox\myboxA}
-\hspace{2\parindentlnth}
-\subfloat[Signalling Thread]{\label{f:SignallingThread}\usebox\myboxB}
-\hspace{2\parindentlnth}
-\subfloat[Other Waiting Thread]{\label{f:SignallingThread}\usebox\myboxC}
-\end{cquote}
-\caption{Barging Prevention}
-\label{f:BargingPrevention}
-\end{figure}
-
-The obvious solution to 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 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 multiple objects to a single group of objects, effectively making the existing single-monitor semantic viable by simply changing monitors to monitor groups.
-This solution releases the monitors once every monitor in a group can be released.
-However, since some monitors are never released (\eg the monitor of a thread), this interpretation means a group might never be released.
-A more interesting interpretation is to transfer the group until all its monitors are released, which means the group is not passed further and a thread can retain its locks.
-
-However, listing \ref{f:int-secret} shows this solution can become much more complicated depending on what is executed while secretly holding B at line \ref{line:secret}, while avoiding the need to transfer ownership of a subset of the condition monitors.
-Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
-Because the third thread is signalled when secretly holding @B@, the goal becomes unreachable.
-Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
-
-\begin{comment}
-\paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
-\paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.
-\\
-
-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 \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
-
-In both cases, 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 knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
-
-
-\subsubsection{Dependency graphs}
-
-\begin{figure}
-\begin{multicols}{3}
-Thread $\alpha$
-\begin{cfa}[numbers=left, firstnumber=1]
-acquire A
- acquire A & B
- wait A & B
- release A & B
-release A
-\end{cfa}
-\columnbreak
-Thread $\gamma$
-\begin{cfa}[numbers=left, firstnumber=6, escapechar=|]
-acquire A
- acquire A & B
- |\label{line:signal-ab}|signal A & B
- |\label{line:release-ab}|release A & B
- |\label{line:signal-a}|signal A
-|\label{line:release-a}|release A
-\end{cfa}
-\columnbreak
-Thread $\beta$
-\begin{cfa}[numbers=left, firstnumber=12, escapechar=|]
-acquire A
- wait A
-|\label{line:release-aa}|release A
-\end{cfa}
-\end{multicols}
-\begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
-\end{cfa}
-\begin{center}
-\input{dependency}
-\end{center}
-\caption{Dependency graph of the statements in listing \ref{f:dependency}}
-\label{fig:dependency}
-\end{figure}
-
-In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
-If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
-Dynamically finding the correct order is therefore the second possible solution.
-The problem is effectively resolving a dependency graph of ownership requirements.
-Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
-This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
-Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
-\begin{figure}
-\begin{multicols}{2}
-\begin{cfa}
-acquire A
- acquire B
- acquire C
- wait A & B & C
- release C
- release B
-release A
-\end{cfa}
-
-\columnbreak
-
-\begin{cfa}
-acquire A
- acquire B
- acquire C
- signal A & B & C
- release C
- release B
-release A
-\end{cfa}
-\end{multicols}
-\begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
-\end{cfa}
-\end{figure}
-
-Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
-The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
-Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
-
-\subsubsection{Partial Signalling} \label{partial-sig}
-\end{comment}
-
-Finally, the solution that is chosen for \CFA is to use partial signalling.
-Again using listing \ref{f:int-bulk-cfa}, the partial signalling solution transfers ownership of monitor @B@ at lines \ref{line:signal1} to the waiter but does not wake the waiting thread since it is still using monitor @A@.
-Only when it reaches line \ref{line:lastRelease} does it actually wake up 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 released and conditionally waking threads if all conditions are met.
-This solution has a much simpler implementation than a dependency graph solving algorithms, which is why it was chosen.
-Furthermore, after being fully implemented, this solution does not appear to have any significant downsides.
-
-Using partial signalling, listing \ref{f:dependency} can be solved easily:
-\begin{itemize}
- \item When thread $\gamma$ reaches line \ref{line:release-ab} it transfers monitor @B@ to thread $\alpha$ and continues to hold monitor @A@.
- \item When thread $\gamma$ reaches line \ref{line:release-a} it transfers monitor @A@ to thread $\beta$ and wakes it up.
- \item When thread $\beta$ reaches line \ref{line:release-aa} it transfers monitor @A@ to thread $\alpha$ and wakes it up.
-\end{itemize}
-
-
-\subsection{Signalling: Now or Later}
+Threads making calls to routines that are currently excluded block outside (external) of the monitor on a calling queue, versus blocking on condition queues inside (internal) of the monitor.
+
+For internal scheduling, non-blocking signalling (as in the producer/consumer example) is used when the signaller is providing the cooperation for a waiting thread;
+the signaller enters the monitor and changes state, detects a waiting threads that can use the state, performs a non-blocking signal on the condition queue for the waiting thread, and exits the monitor to run concurrently.
+The waiter unblocks next, takes the state, and exits the monitor.
+Blocking signalling is the reverse, where the waiter is providing the cooperation for the signalling thread;
+the signaller enters the monitor, detects a waiting thread providing the necessary state, performs a blocking signal to place it on the urgent queue and unblock the waiter.
+The waiter changes state and exits the monitor, and the signaller unblocks next from the urgent queue to take the state.
+
+Figure~\ref{f:DatingService} shows a dating service demonstrating the two forms of signalling: non-blocking and blocking.
+The dating service matches girl and boy threads with matching compatibility codes so they can exchange phone numbers.
+A thread blocks until an appropriate partner arrives.
+The complexity is exchanging phone number in the monitor,
+While the non-barging monitor prevents a caller from stealing a phone number, the monitor mutual-exclusion property
+
+The dating service is an example of a monitor that cannot be written using external scheduling because:
+
+The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
+As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
+To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
+This feature removes the need for a second condition variables and simplifies programming.
+Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
\begin{figure}
@@ -1833,22 +1621,246 @@
\subfloat[\lstinline@signal_block@]{\label{f:DatingSignalBlock}\usebox\myboxB}
\caption{Dating service. }
-\label{f:Dating service}
+\label{f:DatingService}
\end{figure}
-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 @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 @signal_block@ routine.
-
-The example in table \ref{tbl:datingservice} highlights the difference in behaviour.
-As mentioned, @signal@ only transfers ownership once the current critical section exits; this behaviour requires additional synchronization when a two-way handshake is needed.
-To avoid this explicit synchronization, the @condition@ type offers the @signal_block@ routine, which handles the two-way handshake as shown in the example.
-This feature removes the need for a second condition variables and simplifies programming.
-Like every other monitor semantic, @signal_block@ uses barging prevention, which means mutual-exclusion is baton-passed both on the front end and the back end of the call to @signal_block@, meaning no other thread can acquire the monitor either before or after the call.
-
-% ======================================================================
-% ======================================================================
+Both internal and external scheduling extend to multiple monitors in a natural way.
+\begin{cquote}
+\begin{tabular}{@{}l@{\hspace{3\parindentlnth}}l@{}}
+\begin{cfa}
+monitor M { `condition e`; ... };
+void foo( M & mutex m1, M & mutex m2 ) {
+ ... wait( `e` ); ... // wait( e, m1, m2 )
+ ... wait( `e, m1` ); ...
+ ... wait( `e, m2` ); ...
+}
+\end{cfa}
+&
+\begin{cfa}
+void rtn$\(_1\)$( M & mutex m1, M & mutex m2 );
+void rtn$\(_2\)$( M & mutex m1 );
+void bar( M & mutex m1, M & mutex m2 ) {
+ ... waitfor( `rtn` ); ... // $\LstCommentStyle{waitfor( rtn\(_1\), m1, m2 )}$
+ ... waitfor( `rtn, m1` ); ... // $\LstCommentStyle{waitfor( rtn\(_2\), m1 )}$
+}
+\end{cfa}
+\end{tabular}
+\end{cquote}
+For @wait( e )@, the default semantics is to atomically block the signaller and release all acquired mutex types in the parameter list, \ie @wait( e, m1, m2 )@.
+To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @wait( e, m1 )@.
+Wait statically verifies the released monitors are the acquired mutex-parameters so unconditional release is safe.
+Finally, a signaller,
+\begin{cfa}
+void baz( M & mutex m1, M & mutex m2 ) {
+ ... signal( e ); ...
+}
+\end{cfa}
+must have acquired monitor locks that are greater than or equal to the number of locks for the waiting thread signalled from the front of the condition queue.
+In general, the signaller does not know the order of waiting threads, so in general, it must acquire the maximum number of mutex locks for the worst-case waiting thread.
+
+Similarly, for @waitfor( rtn )@, the default semantics is to atomically block the acceptor and release all acquired mutex types in the parameter list, \ie @waitfor( rtn, m1, m2 )@.
+To override the implicit multi-monitor wait, specific mutex parameter(s) can be specified, \eg @waitfor( rtn, m1 )@.
+Waitfor statically verifies the released monitors are the same as the acquired mutex-parameters of the given routine or routine pointer.
+To statically verify the released monitors match with the accepted routine's mutex parameters, the routine (pointer) prototype must be accessible.
+
+Given the ability to release a subset of acquired monitors can result in a \newterm{nested monitor}~\cite{Lister77} deadlock.
+\begin{cfa}
+void foo( M & mutex m1, M & mutex m2 ) {
+ ... wait( `e, m1` ); ... $\C{// release m1, keeping m2 acquired )}$
+void baz( M & mutex m1, M & mutex m2 ) { $\C{// must acquire m1 and m2 )}$
+ ... signal( `e` ); ...
+\end{cfa}
+The @wait@ only releases @m1@ so the signalling thread cannot acquire both @m1@ and @m2@ to enter @baz@ to get to the @signal@.
+While deadlock issues can occur with multiple/nesting acquisition, this issue results from the fact that locks, and by extension monitors, are not perfectly composable.
+
+Finally, an important aspect of monitor implementation is barging, \ie can calling threads barge ahead of signalled threads?
+If barging is allowed, synchronization between a singller and signallee is difficult, often requiring multiple unblock/block cycles (looping around a wait rechecking if a condition is met).
+\begin{quote}
+However, we decree that a signal operation be followed immediately by resumption of a waiting program, without possibility of an intervening procedure call from yet a third program.
+It is only in this way that a waiting program has an absolute guarantee that it can acquire the resource just released by the signalling program without any danger that a third program will interpose a monitor entry and seize the resource instead.~\cite[p.~550]{Hoare74}
+\end{quote}
+\CFA scheduling \emph{precludes} barging, which simplifies synchronization among threads in the monitor and increases correctness.
+For example, there are no loops in either bounded buffer solution in Figure~\ref{f:GenericBoundedBuffer}.
+Supporting barging prevention as well as extending internal scheduling to multiple monitors is the main source of complexity in the design and implementation of \CFA concurrency.
+
+
+\subsection{Barging Prevention}
+
+Figure~\ref{f:BargingPrevention} shows \CFA code where bulk acquire adds complexity to the internal-signalling semantics.
+The complexity begins at the end of the inner @mutex@ statement, where the semantics of internal scheduling need to be extended for multiple monitors.
+The problem is that bulk acquire is used in the inner @mutex@ statement where one of the monitors is already acquired.
+When the signalling thread reaches the end of the inner @mutex@ statement, it should transfer ownership of @m1@ and @m2@ to the waiting threads to prevent barging into the outer @mutex@ statement by another thread.
+However, both the signalling and waiting thread W1 still need monitor @m1@.
+
+\begin{figure}
+\newbox\myboxA
+\begin{lrbox}{\myboxA}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+monitor M m1, m2;
+condition c;
+mutex( m1 ) { // $\LstCommentStyle{\color{red}outer}$
+ ...
+ mutex( m1, m2 ) { // $\LstCommentStyle{\color{red}inner}$
+ ... `signal( c )`; ...
+ // m1, m2 acquired
+ } // $\LstCommentStyle{\color{red}release m2}$
+ // m1 acquired
+} // release m1
+\end{cfa}
+\end{lrbox}
+
+\newbox\myboxB
+\begin{lrbox}{\myboxB}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+
+
+mutex( m1 ) {
+ ...
+ mutex( m1, m2 ) {
+ ... `wait( c )`; // block and release m1, m2
+ // m1, m2 acquired
+ } // $\LstCommentStyle{\color{red}release m2}$
+ // m1 acquired
+} // release m1
+\end{cfa}
+\end{lrbox}
+
+\newbox\myboxC
+\begin{lrbox}{\myboxC}
+\begin{cfa}[aboveskip=0pt,belowskip=0pt]
+
+
+mutex( m2 ) {
+ ... `wait( c )`; ...
+ // m2 acquired
+} // $\LstCommentStyle{\color{red}release m2}$
+
+
+
+
+\end{cfa}
+\end{lrbox}
+
+\begin{cquote}
+\subfloat[Signalling Thread]{\label{f:SignallingThread}\usebox\myboxA}
+\hspace{2\parindentlnth}
+\subfloat[Waiting Thread (W1)]{\label{f:WaitingThread}\usebox\myboxB}
+\hspace{2\parindentlnth}
+\subfloat[Waiting Thread (W2)]{\label{f:OtherWaitingThread}\usebox\myboxC}
+\end{cquote}
+\caption{Barging Prevention}
+\label{f:BargingPrevention}
+\end{figure}
+
+One scheduling solution is for the signaller to keep ownership of all locks until the last lock is ready to be transferred, because this semantics fits most closely to the behaviour of single-monitor scheduling.
+However, Figure~\ref{f:OtherWaitingThread} shows this solution is complex depending on other waiters, resulting is choices when the signaller finishes the inner mutex-statement.
+The singaller can retain @m2@ until completion of the outer mutex statement and pass the locks to waiter W1, or it can pass @m2@ to waiter W2 after completing the inner mutex-statement, while continuing to hold @m1@.
+In the latter case, waiter W2 must eventually pass @m2@ to waiter W1, which is complex because W2 may have waited before W1 so it is unaware of W1.
+Furthermore, there is an execution sequence where the signaller always finds waiter W2, and hence, waiter W1 starves.
+
+While a number of approaches were examined~\cite[\S~4.3]{Delisle18}, the solution chosen for \CFA is a novel techique called \newterm{partial signalling}.
+Signalled threads are moved to an urgent queue and the waiter at the front defines the set of monitors necessary for it to unblock.
+Partial signalling transfers ownership of monitors to the front waiter.
+When the signaller thread exits or waits in the monitor the front waiter is unblocked if all its monitors are released.
+This solution has the benefit that complexity is encapsulated into only two actions: passing monitors to the next owner when they should be released and conditionally waking threads if all conditions are met.
+
+\begin{comment}
+Figure~\ref{f:dependency} shows a slightly different example where a third thread is waiting on monitor @A@, using a different condition variable.
+Because the third thread is signalled when secretly holding @B@, the goal becomes unreachable.
+Depending on the order of signals (listing \ref{f:dependency} line \ref{line:signal-ab} and \ref{line:signal-a}) two cases can happen:
+
+\paragraph{Case 1: thread $\alpha$ goes first.} In this case, the problem is that monitor @A@ needs to be passed to thread $\beta$ when thread $\alpha$ is done with it.
+\paragraph{Case 2: thread $\beta$ goes first.} In this case, the problem is that monitor @B@ needs to be retained and passed to thread $\alpha$ along with monitor @A@, which can be done directly or possibly using thread $\beta$ as an intermediate.
+\\
+
+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 \ref{line:signal-a} before line \ref{line:signal-ab} and get the reverse effect for listing \ref{f:dependency}.
+
+In both cases, 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 knowing when to release a group becomes complex and inefficient (see next section) and therefore effectively precludes this approach.
+
+
+\subsubsection{Dependency graphs}
+
+\begin{figure}
+\begin{multicols}{3}
+Thread $\alpha$
+\begin{cfa}[numbers=left, firstnumber=1]
+acquire A
+ acquire A & B
+ wait A & B
+ release A & B
+release A
+\end{cfa}
+\columnbreak
+Thread $\gamma$
+\begin{cfa}[numbers=left, firstnumber=6, escapechar=|]
+acquire A
+ acquire A & B
+ |\label{line:signal-ab}|signal A & B
+ |\label{line:release-ab}|release A & B
+ |\label{line:signal-a}|signal A
+|\label{line:release-a}|release A
+\end{cfa}
+\columnbreak
+Thread $\beta$
+\begin{cfa}[numbers=left, firstnumber=12, escapechar=|]
+acquire A
+ wait A
+|\label{line:release-aa}|release A
+\end{cfa}
+\end{multicols}
+\begin{cfa}[caption={Pseudo-code for the three thread example.},label={f:dependency}]
+\end{cfa}
+\begin{center}
+\input{dependency}
+\end{center}
+\caption{Dependency graph of the statements in listing \ref{f:dependency}}
+\label{fig:dependency}
+\end{figure}
+
+In listing \ref{f:int-bulk-cfa}, there is a solution that satisfies both barging prevention and mutual exclusion.
+If ownership of both monitors is transferred to the waiter when the signaller releases @A & B@ and then the waiter transfers back ownership of @A@ back to the signaller when it releases it, then the problem is solved (@B@ is no longer in use at this point).
+Dynamically finding the correct order is therefore the second possible solution.
+The problem is effectively resolving a dependency graph of ownership requirements.
+Here even the simplest of code snippets requires two transfers and has a super-linear complexity.
+This complexity can be seen in listing \ref{f:explosion}, which is just a direct extension to three monitors, requires at least three ownership transfer and has multiple solutions.
+Furthermore, the presence of multiple solutions for ownership transfer can cause deadlock problems if a specific solution is not consistently picked; In the same way that multiple lock acquiring order can cause deadlocks.
+\begin{figure}
+\begin{multicols}{2}
+\begin{cfa}
+acquire A
+ acquire B
+ acquire C
+ wait A & B & C
+ release C
+ release B
+release A
+\end{cfa}
+
+\columnbreak
+
+\begin{cfa}
+acquire A
+ acquire B
+ acquire C
+ signal A & B & C
+ release C
+ release B
+release A
+\end{cfa}
+\end{multicols}
+\begin{cfa}[caption={Extension to three monitors of listing \ref{f:int-bulk-cfa}},label={f:explosion}]
+\end{cfa}
+\end{figure}
+
+Given the three threads example in listing \ref{f:dependency}, figure \ref{fig:dependency} shows the corresponding dependency graph that results, where every node is a statement of one of the three threads, and the arrows the dependency of that statement (\eg $\alpha1$ must happen before $\alpha2$).
+The extra challenge is that this dependency graph is effectively post-mortem, but the runtime system needs to be able to build and solve these graphs as the dependencies unfold.
+Resolving dependency graphs being a complex and expensive endeavour, this solution is not the preferred one.
+
+\subsubsection{Partial Signalling} \label{partial-sig}
+\end{comment}
+
+
\section{External scheduling} \label{extsched}
-% ======================================================================
-% ======================================================================
+
An alternative to internal scheduling is external scheduling (see Table~\ref{tbl:sched}).
Index: doc/proposals/user_conversions.md
===================================================================
--- doc/proposals/user_conversions.md (revision 7bdcac1f3631ee6408a86b4d0321433114fee6d3)
+++ doc/proposals/user_conversions.md (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
@@ -5,20 +5,16 @@
There is also a set of _explicit_ conversions that are only allowed through a
cast expression.
-Based on Glen's notes on conversions [1], I propose that safe and unsafe
-conversions be expressed as constructor variants, though I make explicit
-(cast) conversions a constructor variant as well rather than a dedicated
-operator.
+I propose that safe, unsafe, and explicit (cast) conversions be expressed as
+constructor variants.
Throughout this article, I will use the following operator names for
constructors and conversion functions from `From` to `To`:
- void ?{} ( To*, To ); // copy constructor
- void ?{} ( To*, From ); // explicit constructor
- void ?{explicit} ( To*, From ); // explicit cast conversion
- void ?{safe} ( To*, From ); // implicit safe conversion
- void ?{unsafe} ( To*, From ); // implicit unsafe conversion
-
-[1] http://plg.uwaterloo.ca/~cforall/Conversions/index.html
-
-Glen's design made no distinction between constructors and unsafe implicit
+ void ?{} ( To&, To ); // copy constructor
+ void ?{} ( To&, From ); // explicit constructor
+ void ?{explicit} ( To&, From ); // explicit cast conversion
+ void ?{safe} ( To&, From ); // implicit safe conversion
+ void ?{unsafe} ( To&, From ); // implicit unsafe conversion
+
+It has been suggested that all constructors would define unsafe implicit
conversions; this is elegant, but interacts poorly with tuples.
Essentially, without making this distinction, a constructor like the following
@@ -26,5 +22,5 @@
multiplying the space of possible interpretations of all functions:
- void ?{}( Coord *this, int x, int y );
+ void ?{}( Coord& this, int x, int y );
That said, it would certainly be possible to make a multiple-argument implicit
@@ -32,8 +28,8 @@
used infrequently:
- void ?{unsafe}( Coord *this, int x, int y );
+ void ?{unsafe}( Coord& this, int x, int y );
An alternate possibility would be to only count two-arg constructors
-`void ?{} ( To*, From )` as unsafe conversions; under this semantics, safe and
+`void ?{} ( To&, From )` as unsafe conversions; under this semantics, safe and
explicit conversions should also have a compiler-enforced restriction to
ensure that they are two-arg functions (this restriction may be valuable
@@ -43,9 +39,16 @@
is convertable to `To`.
If user-defined conversions are not added to the language,
-`void ?{} ( To*, From )` may be a suitable representation, relying on
+`void ?{} ( To&, From )` may be a suitable representation, relying on
conversions on the argument types to account for transitivity.
-On the other hand, `To*` should perhaps match its target type exactly, so
-another assertion syntax specific to conversions may be required, e.g.
-`From -> To`.
+Since `To&` should be an exact match on `To`, this should put all the implicit
+conversions on the RHS.
+On the other hand, under some models (like [1]), implicit conversions are not
+allowed in assertion parameters, so another assertion syntax specific to
+conversions may be required, e.g. `From -> To`.
+It has also been suggested that, for programmer control, no implicit
+conversions (except, possibly, for polymorphic specialization) should be
+allowed in resolution of cast operators.
+
+[1] ../working/assertion_resolution.md
### Constructor Idiom ###
@@ -53,13 +56,14 @@
that we can use the full range of Cforall features for conversions, including
polymorphism.
-Glen [1] defines a _constructor idiom_ that can be used to create chains of
-safe conversions without duplicating code; given a type `Safe` which members
-of another type `From` can be directly converted to, the constructor idiom
-allows us to write a conversion for any type `To` which `Safe` converts to:
-
- forall(otype To | { void ?{safe}( To*, Safe ) })
- void ?{safe}( To *this, From that ) {
+In an earlier version of this proposal, Glen Ditchfield defines a
+_constructor idiom_ that can be used to create chains of safe conversions
+without duplicating code; given a type `Safe` which members of another type
+`From` can be directly converted to, the constructor idiom allows us to write
+a conversion for any type `To` which `Safe` converts to:
+
+ forall(otype To | { void ?{safe}( To&, Safe ) })
+ void ?{safe}( To& this, From that ) {
Safe tmp = /* some expression involving that */;
- *this = tmp; // uses assertion parameter
+ this{ tmp }; // initialize from assertion parameter
}
@@ -67,14 +71,46 @@
unsafe conversions.
+Glen's original suggestion said the copy constructor for `To` should also be
+accepted as a resolution for `void ?{safe}( To&, Safe )` (`Safe` == `To`),
+allowing this same code to be used for the single-step conversion as well.
+This proposal does come at the cost of an extra copy initialization of the
+target value, though.
+
+Contrariwise, if a monomorphic conversion from `From` to `Safe` is written,
+e.g:
+
+ void ?{safe}( Safe& this, From that ) {
+ this{ /* some parameters involving that */ };
+ }
+
+Then the code for a transitive conversion from `From` to any `To` type
+convertable from `Safe` is written:
+
+ forall(otype To | { void ?{safe}( To&, Safe ) })
+ void ?{safe}( To& this, From that ) {
+ Safe tmp = that; // uses monomorphic conversion
+ this{ tmp }; // initialize from assertion parameter
+ }
+
+Given the entirely-boilerplate nature of this code, but negative performance
+implications of the unmodified constructor idiom, it might be fruitful to have
+transitive and single step conversion operators, and let CFA build the
+transitive conversions; some possible names:
+
+ void ?{safe} (To&, From); void ?{final safe} (To&, From); // single-step
+ void ?{safe*} (To&, From); void ?{safe} (To&, From); // transitive
+
What selective non-use of the constructor idiom gives us is the ability to
define a conversion that may only be the *last* conversion in a chain of such.
-Constructing a conversion graph able to unambiguously represent the full
-hierarchy of implicit conversions in C is provably impossible using only
-single-step conversions with no additional information (see Appendix A), but
-this mechanism is sufficiently powerful (see [1], though the design there has
-some minor bugs; the general idea is to use the constructor idiom to define
-two chains of conversions, one among the signed integral types, another among
-the unsigned, and to use monomorphic conversions to allow conversions between
-signed and unsigned integer types).
+One use for this is to solve the problem that `explicit` conversions were
+added to C++ for, that of conversions to `bool` chaining to become conversions
+to any arithmetic type.
+Another use is to unambiguously represent the full hierarchy of implicit
+conversions in C by making sign conversions non-transitive, allowing the
+compiler to resolve e.g. `int -> unsigned long` as
+`int -> long -> unsigned long` over `int -> unsigned int -> unsigned long`.
+See [2] for more details.
+
+[2] ../working/glen_conversions/index.html#usual
### Appendix A: Partial and Total Orders ###
@@ -153,5 +189,5 @@
convert from `int` to `unsigned long`, so we just put in a direct conversion
and make the compiler smart enough to figure out the costs" - this is the
-approach taken by the existing compipler, but given that in a user-defined
+approach taken by the existing compiler, but given that in a user-defined
conversion proposal the users can build an arbitrary graph of conversions,
this case still needs to be handled.
@@ -160,5 +196,5 @@
exists a chain of conversions from `a` to `b` (see Appendix A for description
of preorders and related constructs).
-This preorder corresponds roughly to a more usual type-theoretic concept of
+This preorder roughly corresponds to a more usual type-theoretic concept of
subtyping ("if I can convert `a` to `b`, `a` is a more specific type than
`b`"); however, since this graph is arbitrary, it may contain cycles, so if
@@ -192,5 +228,5 @@
and so is considered to be the nearer type.
By transitivity, then, the conversion from `X` to `Y2` should be cheaper than
-the conversion from `X` to `W`, but in this case the `X` and `W` are
+the conversion from `X` to `W`, but in this case the `Y2` and `W` are
incomparable by the conversion preorder, so the tie is broken by the shorter
path from `X` to `W` in favour of `W`, contradicting the transitivity property
Index: doc/working/glen_conversions/index.html
===================================================================
--- doc/working/glen_conversions/index.html (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
+++ doc/working/glen_conversions/index.html (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
@@ -0,0 +1,1462 @@
+
+
+
+Conversions for Cforall
+
+
+
+
+Conversions for Cforall
+
+NOTE: This proposal for constructors and user-defined conversions
+does not represent the current state of Cforall language development, but is
+maintained for its possible utility in building user-defined conversions. See
+doc/proposals/user_conversions.md for a more current presentation of
+these ideas.
+
+This is the first draft of a description of a possible extension to the
+current definition of Cforall ("Cforall-as-is") that would let programmers
+fit new types into Cforall's system of conversions.
+
+
+ - Design Notes
+
+ - Goals
+ - Conversions
+ - Constructors
+ - Ambiguity
+
+
+ - Proposed Extension
+
+ - New Operator Identifiers
+ - Cast Expressions
+ - Object Definitions
+ - Default Functions
+
+
+ - Conversion Composition
+ - Constructors and Cost
+ - Heap Allocation
+ - Generic Conversions and Constructors
+ - C's "Usual Arithmetic Conversions"
+
+ - Floating-Point Types
+ - Large Integer Types
+ - C's "Integer Promotions"
+
+
+ - Other Promotions
+ - Other Pre-Defined Implicit Conversions
+ - Pre-Defined Explicit Conversions
+ - Non-Conversions
+ - Assignment Operators
+ - Overload Resolution
+ - Final Notes
+
+
+Design Notes
+
+Goals
+My design goal for this extension is to provide a framework that
+explains the bulk of C's conversion semantics in terms of more basic
+languages, just as Cforall explains most expression semantics in terms of
+overloaded function calls.
+
+My pragmatic goal is to allow a programmer to define a portable rational
+number data type, fit it into the existing C type system, and use it in
+mixed-mode arithmetic expressions, all in a convenient and esthetically
+pleasing manner.
+
+Conversions
+
+A conversion creates a value from a value of a different
+type. C defines a large number of conversions, especially between
+arithmetic types. A subset of these can be performed by implicit
+conversions, which occurs in certain contexts: in assignment
+expressions, when passing arguments to function (where parameters are
+"assigned the value of the corresponding argument"), in initialized
+declarations (where "the same type constraints and conversions as for
+simple assignment apply"), and in mixed mode arithmetic. All conversions
+can be performed explicitly by cast expressions.
+
+C prefers some implicit conversions, the promotions, to the
+others. The promotions are ranked among themselves, creating a hierarchy
+of types. In mixed-mode operations, the "usual arithmetic conversions"
+promote the operands to what amounts to their least common supertype.
+Cforall-as-is uses a slightly larger set of promotions to choose the
+smallest possible promotion when resolving overloading.
+
+An extension should allow Cforall to explain C's conversions as a set of
+pre-defined functions, including its explicit conversions, implicit
+conversions, and preferences among conversions. The extension must let the
+programmer define new conversions for programmer-defined types, for
+instance so that new arithmetic types can be used conveniently in
+mixed-mode arithmetic.
+
+Constructors
+
+C++ introduced constructors to the C language family, and I will use its
+terminology. A constructor is a function that initializes an
+object. C does not have constructors; instead, it makes do with
+initialization, which works like assignment. Cforall-as-is does not have
+constructors, either: instead, by analogy with C's semantics, a
+programmer-defined assignment function may be called during initialization.
+However, there is a key difference between a function that implements
+assignment and a constructor: constructors assume that the object is
+uninitialized, and must set up any data structure invariants that the
+object is supposed to obey. An assignment function assumes that the target
+object obeys its invariants.
+
+A default constructor has no parameters other than the object it
+initializes. It establishes invariants, but need not do anything else. A
+default constructor for a rational number type might set the denominator to be
+non-zero, but leave the numerator undefined.
+
+A copy constructor has two parameters: the object it
+initializes, and a value of the same type. Its purpose is to copy the
+value into the object, and so it is very similar to an assignment
+function. In fact, it could be expressed as a call to a default constructor
+followed by an assignment.
+
+A converting constructor also has two parameters, but the
+second parameter is a value of some type different from the type
+of the object it initializes. Its purpose is to convert the value to the
+object's type before copying it, and so it is very similar to a C
+assignment operation that performs an implicit conversion.
+
+C++ sensibly defines parameter passing as call by initialization, since
+the parameter is uninitialized when the argument value is placed in it.
+Extended Cforall should do the same. However, parameter passing is one of
+the main places where implicit conversions occur. Hence in extended
+Cforall constructors define the implicit conversions. Cforall
+should also encourage programmers to maintain the similarity between
+constructors and assignment.
+
+Ambiguity
+
+In extended Cforall, programmer-defined conversions should fit in with
+the predefined conversions. For instance, programmer-defined promotions
+should interact with the normal promotions so that programmer-defined types
+can take part in mixed-mode arithmetic expressions. The first design that
+springs to mind is to define a minimal set of conversions between
+neighbouring types in the type hierarchy, and to have Cforall create
+conversions between more distant types by composition of predefined and
+programmer-defined conversions. Unfortunately, if one draws a graph of C's
+promotions, with C's types as vertices and C's promotions as edges, the
+result is a directed acyclic graph, not a tree. This means that an attempt
+to build the full set of promotions by composition of a minimal set of
+promotions will fail.
+
+ Consider a simple processor with 32-bit int and
+long types. On such a machine, C's "usual arithmetic
+conversions" dictate that mixed-mode arithmetic that combines a signed
+integer with an unsigned integer must promote the signed integer to an
+unsigned type. Here is a directed graph showing the some of the minimal
+set of promotions. Each of the four promotions is necessary, because each
+could be required by some mixed-mode expression, and none can be decomposed
+into simpler conversions.
+
+
+long --------> unsigned long
+ ^ ^
+ | |
+int ---------> unsigned int
+
+
+Now imagine attempting to compose an int-to-unsigned
+long conversion from the minimal set: there are two paths through
+the graph, so the composition is ambiguous.
+
+(In C, and in Cforall-as-is, no ambiguity exists: there is just one
+int-to-unsigned long promotion, defined by the
+language semantics. In Cforall-as-is, the preference for
+int-to-long over
+int-to-unsigned long is determined by a
+"conversion cost" calculated from the graph of the full set of promotions,
+but the calculation depends on maximal path lengths, not the exact
+path.)
+
+Unfortunately, the same problem with ambiguity creeps in any time
+conversions might be chained together. The extension must carefully
+control conversion composition, so that programmers can avoid ambiguous
+conversions.
+
+Proposed Extension
+
+The rest of this document describes my proposal to add
+programmer-definable conversions and constructors to Cforall.
+
+If your browser supports CSS style sheets, the
+proposal will appear in "normal" paragraphs, and commentary on the proposal
+will have the same appearance as this paragraph.
+
+New Operator Identifiers
+
+Cforall would be given a cast identifier, two
+constructor identifiers, and a destructor
+identifier:
+
+
+ -
(?)?, for cast functions.
+ -
(?create)?, for constructors.
+ -
(?promote)?, for constructors that are promotions.
+ -
(?destroy)?, for destructors.
+
+
+
+
The ugly identifier (?)? is meant to be mnemonic for the
+cast expression. The other identifiers are pretty weak (suggestions,
+anyone?) but are supposed to remind the programmer of the connection
+between conversions and constructors.
+
+
We could instead use a single (?create)? identifier for
+constructors and add a promote storage class specifier, at
+some small risk clashes of with identifiers in existing code.
It is an error to declare two functions with different constructor
+identifiers that have the same type in the same translation unit.
+
+Functions declared with these identifiers can be polymorphic. Unlike
+other polymorphic functions, the return type of a polymorphic cast function
+need not be derivable from the type of its parameters
+
+
+
The return type of a call to a polymorphic cast
+function can be deduced from the calling context.
+
+
+forall(type T1) T1 (?)?(T2); // Legal.
+forall(type T1) T1 pfun(T2); // Illegal -- no way to infer T1.
+
+
A cast function from type T1 to type
+T2 is named "(?)?", accepts exactly one explicit
+argument of type T1, and returns a value of type T2.
+
+If the cast function is polymorphic, it will have
+type parameters and assertion parameters as well, and can be said to be a
+cast function from many different types to many different types.
+
+
+A default constructor function for type T is named
+"(?create)?", accepts exactly one explicit argument of type
+T*, and returns void.
+
+A copy constructor function for type T is named
+"(?create)?", accepts exactly two explicit arguments of types
+T* and T, and returns void.
+
+A converting constructor function for type T1 from
+T2 is named "(?create)?" or "(?promote)?",
+accepts exactly two explicit arguments of types T1* and
+T2, and returns void.
+
+A destructor function for type T is named
+"(?destroy)?", accepts exactly one explicit argument of type
+T*, and returns void.
+
+
+
+
The monomorphic function prototypes for these functions are
+
+T1 (?)?(T2);
+void (?create)?(T1*);
+void (?create)?(T1*, T2);
+void (?promote)?(T1*, T2);
+void (?destroy)?(T1*);
+
+
Cast Expressions
+
+In most cases the cast expression (T)e would
+be treated like the function call (?)?(e), except that
+only cast functions to type T would be valid interpretations of
+(?)?, and e would not be implicitly
+converted to the cast function's parameter type. In particular, the usual
+rules for resolving function overloading (see below)
+would be used to choose the best interpretation of the expression.
+
+
+
For example, in
+
+type Wazzit;
+type Thingum;
+Wazzit w;
+(Thingum)w;
+
+
the cast function that is called must be "Thingum
+(?)?(Wazzit)", or a polymorphic function that can be specialized to
+that.
+
+
The ban on implicit conversions within the cast allows programmers to
+explicitly control composition of conversions and avoid ambiguity. I also
+hope that this will make it easier for compilers and programmers to
+determine which conversions will be applied in which circumstances. If
+implicit conversions could be applied to the inputs and outputs of casts,
+when any and all of the conversion functions involved could be polymorphic
+... the possibilities seem endless, unfortunately.
+
+
Object Definitions
+A definition of an object x would call a constructor function. Let
+T be x's type with type qualifiers removed, and let a
+be x's address (with type T*).
+
+If type qualifiers weren't ignored, const
+objects couldn't be initialized, and every constructor would have to be
+duplicated, with one version for T* objects and one for
+volatile T* objects.
+
+
+ - A definition with an initializer that is a single expression
+ e, optionally enclosed in braces, would call a copy or converting
+ constructor. The call would be treated much like the function call
+
f(a,e), except that only copy and
+ converting constructors for type T would be valid interpretations
+ of f, and e would not be implicitly
+ converted to the type of the constructor's second parameter.
+ - If x has automatic storage duration and is not initialized
+ explicitly, the definition would call a default constructor function.
+ The call would be treated much like the function call
+
f(a), except that only default
+ constructor functions for type T would be valid interpretations of
+ f.
+ If x has static storage duration and is not initialized
+ explicitly, and is defined within the scope of a type definition that
+ defines T, then T's implementation type would determine how
+ x is initialized.
+
+
+ type Rational = struct { int numerator; unsigned denominator; };
+ Rational r; // Both members initialized to 0.
+
+
If x has static storage duration and is not initialized
+ explicitly, and the type T is an opaque type, the definition
+ would be treated as if x was initialized with the expression
+ 0.
+
+
This is a simple extension of C's rules for static objects,
+ which initialized them all to 0. Frequently, the 0 involved
+ will have type T, and the definition will call a copy
+ constructor.
+
+ extern type Rational;
+ extern Rational 0;
+ static Rational r; // initialized with the Rational 0.
+
+
In other cases, the 0 will be an integer or null pointer, and the
+ definition will call a converting constructor.
+
+
The obvious alternative design would call T's default
+ constructor. That design would be inconsistent, because some static
+ objects would go uninitialized. It would also cause subtle problems,
+ because a particular static definition could be uninitialized or
+ initialized to 0 depending on whether T is an extern
+ type or a typedef.
+
+
+Except when calling constructors, parameter passing invokes constructor
+functions. Passing argument expression e to a parameter would be
+equivalent to initializing the parameter with that expression. When
+calling constructors, the value of the argument would be copied into the
+parameter.
+
+When the lifetime of x ends, a destructor function would be called.
+The call would be treated much like the function call
+(?destroy)?(a). When a block ends, the objects that were
+defined in the block would be destroyed in the reverse of the order in which
+they are declared.
+
+The storage class specifier register will have the
+semantics that it has in C++, instead of the semantics of C: it is merely a
+hint to the implementation that the object will be heavily used, and does
+not prevent programs from computing the address of the object.
+
+Default Functions
+
+In Cforall-as-is, every declaration with type-class type
+implicitly declares a default assignment function, with the same scope and
+linkage as the type. Extended Cforall would also declare a default
+default constructor and a default destructor.
+
+
+
+{
+ extern type T;
+ T t; // calls external constructor for T.
+ } // calls external destructor for T.
+
+
The destructor and some sort of constructor are necessary to instantiate
+the type. I include the default constructor because it is the most basic.
+Arguably the declaration should also declare a default copy constructor,
+but I chose not to because Cforall can construct a copy constructor from
+the default constructor and the assignment operator, as will be seen
+below.
+
+
If the type does not need to be instantiated, it probably should have
+been declared by dtype instead of by type.
+
A type definition would implicitly define a default constructor and
+destructor by inheriting the implementation type's default constructor and
+destructor, just as is done for the implicitly defined default assignment
+function.
+
+Conversion Composition
+
+As mentioned above, Cforall does not apply implicit conversions to the
+arguments and results of cast expressions or constructor calls. Neither
+does it automatically create conversions or constructors by composing
+programmer-defined compositions: given
+
+
+T1 (?)?(T2);
+T2 (?)?(T3);
+T3 v3;
+(T1)v3;
+
+
+then Cforall does not automatically create
+
+
+T1 (?)?(T3 p) { return (T1)(T2)p; }
+
+
+Composition of conversions does show up through a third mechanism where
+the programmer has more control: assertion lists. Consider a
+Month type, that represents months as integers between 0 and
+11. Clearly a Month can be promoted to unsigned,
+and to any type above unsigned in the arithmetic type
+hierarchy as well.
+
+
+type Month = unsigned;
+
+forall(type T | void (?promote)(T*, unsigned))
+ void (?promote)?(T* target, Month source) {
+ unsigned u_temp = (unsigned)source;
+ T t_temp = u_temp; // calls the assertion parameter.
+ *target = t_temp;
+ }
+
+
+The intimidating polymorphic promotion declaration says that, if
+T is a type and unsigned can be promoted to
+T, then the function can promote Month to
+T.
+
+
+Month m;
+unsigned long ul = m;
+
+
+To initialize ul, Cforall must bind T to
+unsigned long, find the (pre-defined)
+unsigned-to-unsigned long promotion, and pass it
+to the assertion parameter of the polymorphic
+Month-to-T function.
+
+But what about converting from Month to
+unsigned itself?
+
+
+unsigned u = m; // How?
+
+
+A monomorphic Month-to-unsigned constructor
+would do the job, but its body would mostly duplicate the body of the
+polymorphic function.
+
+Instead, Cforall should use the polymorphic promotion and the
+unsigned copy constructor. To initialize u,
+Cforall should pass the unsigned copy constructor to the assertion
+parameter of the polymorphic Month promotion, and bind
+T to unsigned.
+
+Note that the polymorphic promotion can promote Month to
+the standard types, to implementation-defined extended types, and to
+programmer-defined types that have yet to be written. This is much better
+than writing a flock of monomorphic promotions, with function bodies that
+would be nearly identical, to convert Month to each unsigned
+type individually. The predefined constructors make heavy use of this
+constructor idiom: instead of writing
+
+
+void (?promote)? (T1*, T2);
+
+
+("You can make a T2 into a T1"), write
+
+forall(type T | void (?promote)?(T*, T1) ) void (?promote)?(T*, T2);
+
+
+("You can make a T2 into anything that can be made from a T1").
+
+Constructors and Cost
+
+Calls to constructors have construction costs, which let
+Cforall choose the least expensive implicit conversion when given a
+choice.
+
+
+ - The cost of a call to a copy constructor is 0.
+ - The cost of a call to a monomorphic constructor is 1.
+ - The cost of a call to a polymorphic constructor, or a specialization
+ of it, is 1 plus the sum of the construction costs of constructors
+ that are passed to it through assertion parameters.
+
+
+
+
+
Note that, although point 3 refers to constructors that are
+passed at run-time, the translator statically matches arguments to
+assertion parameters, so it can determine construction costs statically.
+
+
Construction cost is defined for every
+constructor, not just the promotions (which are the equivalent of the safe
+conversions of Cforall-as-is). This seemed like the easiest way to handle
+(admittedly dicey) "mixed" constructors, where the constructor and its
+assertion parameter have different identifiers:
+
+
+type Thingum;
+type Wazzit;
+forall(type T | void (?create)?(T*, Thingum) )
+ void (?promote)?(T*, Wazzit);
+
+
Examples:
+"unsigned ui = 42U;" calls a copy constructor, and so has
+cost 0.
+
+"unsigned ui = m;", where m has type
+Month, calls the polymorphic Month promotion
+defined previously. It passes the
+unsigned-to-unsigned copy constructor to the
+assertion parameter, and so has cost 1+0 = 1.
+
+"unsigned long ul = m;" calls the polymorphic
+Month promotion, passing the
+unsigned-to-unsigned long constructor to the
+assertion parameter. unsigned-to-unsigned long
+is defined below and will turn out to have cost 1, so the total cost is 2.
+
+Inside the body of the Month promotion, the assertion
+parameter has a monomorphic type, and so has a construction cost of 1 where
+it is called by the initialization of t_temp. The cost of the
+argument passed through the assertion parameter has no relevance
+inside the body of the promotion.
+
+Overload Resolution
+
+In Cforall-as-is, there is at most one language-defined implicit
+conversion between any two types. In extended Cforall, more than one
+conversion may be applicable, and overload resolution must be adapted to
+account for that, by using the lowest-cost conversion.
+
+The unsafe conversion cost of a function call expression
+would be the total conversion cost of implicit calls of
+(?create)?() constructors applied directly to arguments of the
+function -- 0 if there are none.
+
+This would replace a rule in Cforall-as-is, which
+considers all unsafe conversions to be equally bad and just counts them. I
+think the difference would be subtle and unimportant.
+
+The promotion cost would be the total conversion costs of
+implicit calls of (?promote)?() constructors applied directly
+to arguments of the function -- 0 if there are none.
+
+Overload resolution would examine each argument expression individually.
+The best interpretations of an expression would be:
+
+
+ - the interpretations with the lowest unsafe conversion cost;
+ - of these, the interpretations with the lowest promotion cost;
+ - of these, if any can be promoted to the parameter type, then just
+ those that can be converted at minimal cost; otherwise, all remaining
+ interpretations.
+
+
+The best interpretation would be implicitly converted to the parameter
+type, by calling the conversion function with minimal cost. If there is
+more than one best interpretation, or if there is more than one
+minimal-cost conversion, the argument is ambiguous.
+
+A maximal set of interpretations of the function call expression that
+have compatible result types produces a single interpretation: the
+interpretations with the lowest unsafe conversion cost, and of these, the
+interpretations with the lowest promotion cost. If there is more than one
+such interpretation, the function call expression is ambiguous.
+
+Heap Allocation
+
+Cforall would define new heap allocation functions that would ensure
+that constructors and destructors would be applied to objects in the
+heap. There's lots of room for ambitious design here, but a simple
+facility might look like this:
+
+
+forall(type T) void delete(T const volatile restrict* ptr) {
+ if (ptr) (?destroy)?(ptr);
+ free(ptr);
+}
+
+
+
+
In a call to delete(), the argument might be a pointer to a
+pointer: T would be a pointer type, and the argument might
+have all three type qualifiers. (If it doesn't, pointer conversions will add
+missing qualifiers to the argument.)
+
+// Pointer to a const volatile restricted pointer to an int:
+int * const volatile restrict * pcvrpi;
+// ...
+delete(cvrpi); // T bound to int *
+
+
A new() function would take the address of a pointer and an
+initial value, and points the pointer at heap storage initialized to that
+value.
+
+forall(type T | void (?create)?(T*, T))
+ void new(T* volatile restrict* ptr, T val) {
+ *ptr = malloc(sizeof(T));
+ if (*ptr) (?create)?(*ptr, val); // explicit constructor call
+}
+
+forall(type T | void (?create)?(T*, T))
+ void new(T const* volatile restrict* ptr, T val),
+ new(T volatile* volatile restrict* ptr, T val),
+ new(T restrict* volatile restrict* ptr, T val),
+ new(T const volatile* volatile restrict* ptr, T val),
+ new(T const restrict* volatile restrict* ptr, T val),
+ new(T volatile restrict* volatile restrict* ptr, T val),
+ new(T const volatile restrict* volatile restrict* ptr, T val);
+
+Cforall can't add type qualifiers to pointed-at
+pointer types, so new() needs one variation for each set of
+type qualifiers.
+
+Another new() function would omit the initial value, and
+apply the default constructor. Obviously, there's
+no point in allocating const-qualified uninitialized
+storage.
+
+forall(type T)
+ void new(T* volatile restrict * ptr) {
+ *ptr = malloc(sizeof(T));
+ if (*ptr) (?create)?(*ptr); // Explicit default constructor call.
+}
+
+forall(type T)
+ void new(T volatile* volatile restrict*),
+ void new(T restrict* volatile restrict*),
+ void new(T volatile restrict* volatile restrict*);
+
+
+Generic Conversions and Constructors
+
+Cforall would provide a polymorphic default constructor function and
+destructor function, for types that do not have their own:
+
+
+forall(type T)
+ void (?create)?(T*) { return; };
+
+forall(type T)
+ void (?destroy)?(T*) { return; };
+
+
+The generic default constructor and destructor provide
+C semantics for uninitialized variables: "do nothing".
+
+For every structure type struct s Cforall would define a
+default constructor function that applies a default constructor to each
+member, in no particular order. Similarly, it would define a destructor that
+applies the destructor of each member in no particular order.
+
+Any promotion would be treated as a plain constructor:
+
+forall(type T, type S | void (?promote)(T*, S))
+ void (?create)?(T*, S) {
+ (?promote)?(T*, S); // Explicit constructor call!
+ }
+
+
+A predefined cast function would allow explicit conversions anywhere
+that implicit conversions are possible:
+
+forall(type T, type S | void (?create)?(T*, S))
+ T (?)?(S source) {
+ T temp = source;
+ return temp;
+ }
+
+
+A predefined converting constructor would allow initialization anywhere
+that assignment is defined:
+
+forall(type T | void (?create)?(T*), type S | T ?=?(T*, S))
+ void (?create)?(T* target, S source) {
+ (?create)?(target);
+ *target = source;
+ }
+
+
+This implements the typical semantic link between
+assignment and initialization.
+
+The predefined copy constructor function is
+
+forall(type T)
+ void (?promote)?(T* target, T source) {
+ (?create)?(target);
+ *target = source;
+ }
+
+
+Since Cforall defines assignment and default
+constructors for structure types, this provides the copy constructor for
+structure types.
+
+Finally, Cforall defines the conversion to void, which
+discards its argument.
+
+forall(type T) void (?promote)(void*, T);
+
+
+C's "Usual Arithmetic Conversions"
+
+C has five groups of arithmetic types: signed integers, unsigned
+integers, complex floating-point numbers, imaginary floating-point numbers,
+and real floating-point numbers. (Implementations are not required to
+provide complex and imaginary types.) Some of the "usual arithmetic
+conversions" promote upward within a group or to a more general group: from
+int to long long, for instance. Others
+promote across from a type in one group to a similar type in another group:
+for instance, from int to unsigned int.
+
+Floating-Point Types
+
+The floating point types would use the constructor
+idiom for upward promotions, and monomorphic constructors for
+promotions across from real and imaginary types to complex types with the
+same precision.
+
+I will use a macro to abbreviate the constructor idiom.
+"Promoter(T,S)" promotes S to any type that
+T can be promoted to
+
+#define Promoter(Target, Source) \
+ forall(type T | void (?promote)?(T*, Target)) void (?promote)?(T*, Source)
+
+Promoter(long double _Complex, double _Complex); // a
+Promoter(double _Complex, float _Complex); // b
+Promoter(long double, double); // c
+Promoter(double, float); // d
+Promoter(long double _Imaginary, double _Imaginary); // e
+Promoter(double _Imaginary, float _Imaginary); // f
+
+void (?promote)?(long double _Complex*, long double); // g
+void (?promote)?(long double _Complex*, long double _Imaginary); // h
+void (?promote)?(double _Complex*, double); // i
+void (?promote)?(double _Complex*, double _Imaginary); // j
+void (?promote)?(float _Complex*, float); // k
+void (?promote)?(float _Complex*, float _Imaginary); // l
+
+
+
+
It helps to draw a graph of the promotions. In this diagram,
+monomorphic promotions are solid arrows from the source type to the target
+type, and polymorphic promotions are dotted arrows from the source type to
+a bubble that surrounds all possible target types. (Twenty years after
+first hearing about them, I have finally found a use for directed
+multigraphs!) To determine the promotion from one type to another, find a
+path of zero or more dotted arrows optionally ending with a solid arrow.
+
+
+
+
+
A long double _Complex can be constructed from
+
+ - a
double _Complex, via a, with a double
+ _Complex copy constructor passed as the assertion
+ parameter.
+ - a
long double, via constructor g.
+ - a
double, via c (which promotes
+ double to long double and higher), with
+ g passed as the assertion parameter. In other words, the path
+ from double to long double _Complex passes
+ through long double
+ - a
float _Complex, via b. For the assertion
+ parameter, Cforall passes a double
+ _Complex-to-long double _Complex constructor that
+ it makes by specializing a; for the assertion parameter of the
+ specialization, it passes a long double
+ _Complex-to-long double _Complex copy
+ constructor.
+ - a
float, via d, with a specialization of c
+ passed as its assertion parameter, with g passed as the
+ specialization's assertion parameter.
+
+
+
Note how "upward" and "across" promotions interact. Polymorphic
+"upward" promotions connect widely separated types by composing
+constructors through their assertion parameters. Monomorphic "across"
+promotions extend composition one step across to corresponding types in
+different groups.
+
+
Defining the set of predefined promotions turned out to be quite tricky.
+For example, if "across" promotions used the constructor idiom, ambiguity
+would result: a conversion from float to double
+_Complex could convert upward through double or across
+through float _Complex. The key points are:
+
+ - Monomorphic constructors are only used to connect neighbouring types
+ in the conversion hierarchy, because they have constructor cost 1.
+ - Polymorphic constructors only connect directly to neighbours, because
+ their minimal cost is 1. They reach other types by composition.
+ - The types in the assertion parameter of a polymorphic constructor
+ specify the exact path between two types by specifying the
+ next type in a sequence of composed constructors.
+ - There can be more than one path between two types, provided that the
+ paths have different construction costs or degrees of
+ polymorphism.
+
+
+
Large Integer Types
+
+The conversions for the integer types cannot be
+defined by a simple list, because the set of integer types is
+implementation-defined, the range of each type is implementation-defined,
+and the set of promotions depend on whether a particular signed type can
+represent all values of a particular unsigned type. As I read the C
+standard, every signed type has a matching unsigned type, but the reverse
+is not true. This complicates the definitions below.
+
+
+ - Let the rank of an integer type be the integer conversion
+ rank defined in C99, with the added condition that the ranks form a
+ continuous sequence of integers.
+ - Let rint be the rank of
+
int.
+ - Let
signed(r) and
+ unsigned(r)
+ be the signed integer type and unsigned integer type with rank
+ r.
+
+
+Integers promote upward to floating-point types. Let SMax be the
+highest ranking signed integer type, and let UMax be the highest
+ranking unsigned integer type. Then Cforall would define
+
+
+Promoter(float, SMax);
+Promoter(float, Umax);
+
+
+Signed types promote across to unsigned types with the same rank. For
+every r >= rint such that
+signed(r) exists, Cforall would define
+
+
+void (?promote)?( unsigned(r)*, signed(r) );
+
+
+Lower-ranking signed integers promote to higher-ranking signed integers.
+For every signed integer type T with rank greater than
+rint, let S be the signed integer type with the
+next lowest rank. Then Cforall would define
+
+
+Promoter(T, S);
+
+
+Similarly, lower-ranking unsigned integers promote to higher-ranking
+unsigned integers. For every r > rint, Cforall
+would define
+
+
+Promoter(unsigned(r), unsigned(r-1));
+
+
+C's usual arithmetic conversions may promote an unsigned type to a
+signed type, but only if the signed type can represent every value of the
+unsigned type. For every r >= rint, if there
+are any signed types that can represent every value in
+unsigned(r), let S be the
+lowest ranking of these types; then Cforall defines
+
+
+Promoter(S, unsigned(r));
+
+
+
+
+
+
+
C's integer promotions apply to "small" types (those with
+rank less than rint): they promote to int if
+int can hold all of their values, and to unsigned
+int otherwise. At least one unsigned type, _Bool,
+will promote to int. This breaks the pattern set by the usual
+arithmetic conversions, where unsigned types always promote to the next
+larger unsigned type. Consider a machine with 32-bit ints and
+16-bit unsigned shorts: if two unsigned shorts
+are added, they must be promoted to int instead of
+unsigned int. Hence for this machine there must not
+be a promotion from unsigned short to unsigned
+int.
+
+
Since the C integer promotions always promote small signed types to
+int, Cforall would extend the chain of polymorphic "upward"
+and monomorphic "across" signed integer promotions to the small
+signed types.
+
For every signed integer type S with rank less than
+rint, Cforall would define
+
+Promoter(T, S);
+
+where T is the signed integer type with the next highest
+rank.
+
+Let rbreak be the rank of the highest-ranking unsigned
+type whose values can all be represented by int, and let
+T be the lowest-ranking signed type that can represent all of the
+values of unsigned(rbreak). Cforall would
+define
+
+
+Promoter(T, unsigned(rbreak));
+
+
+For every
+r less than rint except
+rbreak, Cforall would define
+
+Promoter(unsigned(r+1), unsigned(r));
+
+
+rbreak is the point where the normal
+pattern of unsigned promotion breaks. Unsigned types with higher rank
+promote upward toward unsigned int. Unsigned types with
+lower rank promote upward to the type at the break, which promotes upward
+to a signed type and onward toward int.
+
+For each r < rint such that
+signed(r) exists, Cforall would define
+
+void (?promote)?(unsigned(r)*, signed(r));
+
+
+These "across" promotions are not strictly necessary,
+but it seems useful to extend the pattern of signed-to-unsigned monomorphic
+conversions established by the larger integer types. Note that because of
+these promotions, unsigned(rbreak) does
+promote to the next larger unsigned type, after a detour through a signed
+type that increases the conversion cost.
+
+Finally, char is equivalent to signed char or
+unsigned char, on an implementation-defined basis. If
+char is equivalent to signed char, the
+implementation would define
+
+
+Promoter(signed char, char);
+
+
+Otherwise, it would define
+
+Promoter(unsigned char, char);
+
+
+
+Promotions can add qualifiers to the pointed-to type of a
+pointer type.
+
+forall(dtype DT) void (?promote)?(const DT**, DT*);
+forall(dtype DT) void (?promote)?(volatile DT**, DT*);
+forall(dtype DT) void (?promote)?(restrict DT**, DT*);
+forall(dtype DT) void (?promote)?(const volatile DT**, DT*);
+forall(dtype DT) void (?promote)?(const restrict DT**, DT*);
+forall(dtype DT) void (?promote)?(volatile restrict DT**, DT*);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, DT*);
+
+forall(dtype DT) void (?promote)?(const volatile DT**, const DT*);
+forall(dtype DT) void (?promote)?(const restrict DT**, const DT*);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, const DT*);
+
+forall(dtype DT) void (?promote)?(const volatile DT**, volatile DT*);
+forall(dtype DT) void (?promote)?(volatile restrict DT**, volatile DT*);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, volatile DT*);
+
+forall(dtype DT) void (?promote)?(const restrict DT**, restrict DT*);
+forall(dtype DT) void (?promote)?(volatile restrict DT**, restrict DT*);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, restrict
+DT*);
+
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, const volatile DT);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, const restrict DT);
+forall(dtype DT) void (?promote)?(const volatile restrict DT**, volatile restrict DT);
+
+
+ The type qualifier promotions are simple, but verbose
+because Cforall doesn't abstract over type qualifiers very well. They also
+give every type qualifier promotion a cost of 1. It is possible
+to define a smaller set of promotions, some using the constructor idiom,
+that gives greater cost to promotions that add more qualifiers, but the set
+is arbitrary and asymmetric: only one of the three promotions that add one
+qualifier to an unqualified pointer type can use the constructor idiom, or
+else ambiguity results.
+
+Within the scope of a type definition type T1 =
+T2;, constructors would convert between the new type and its
+implementation type.
+
+
+void (?promote)(T2*, T1);
+void (?promote)(T2**, T1*);
+void (?create)?(T1*, T2);
+void (?create)?(T1**, T2*);
+
+
+The conversion from the implementation type
+T2 to the new type T1 gives
+functions that implement operations on T1 access to the
+type's implementation. The conversion is a promotion because most such
+functions work with the implementation most of the time. The reverse
+conversion is merely implicit, so that mixed operations won't be
+ambiguous.
+
+Other Pre-Defined Implicit Conversions
+Arithmetic Conversions
+
+C defines implicit conversions between any two
+arithmetic types. In Cforall terms, the conversions that are not
+promotions are ordinary conversions. Most of the ordinary conversions
+follow a pattern that looks like the Usual Arithmetic
+Conversions in reverse. Once again, I will use a macro to hide details
+of the constructor idiom.
+
+
+#define Creator(Target, Source) \
+ forall(type T | void (?create)?(T*, Target)) void (?create)?(T*, Source)
+
+Creator(double _Complex, long double _Complex);
+Creator(float _Complex, double _Complex);
+Creator(double, long double);
+Creator(float, double);
+Creator(double _Imaginary, long double _Imaginary);
+Creator(float _Imaginary, double _Imaginary);
+
+void (?create)?(long double*, long double _Complex);
+void (?create)?(long double _Imaginary*, long double _Complex);
+void (?create)?(double*, double _Complex);
+void (?create)?(double _Imaginary*, double _Complex);
+void (?create)?(float*, float _Complex);
+void (?create)?(float _Imaginary*, float _Complex);
+
+
+The C99 draft standards that I have access to state
+that real types and imaginary types are implicitly interconvertible. This
+seems like a mistake, since the result of the conversion will always be
+zero, but ...
+
+
+void (?create)?(long double*, long double _Imaginary);
+void (?create)?(long double _Imaginary*, long double);
+void (?create)?(double*, double _Imaginary);
+void (?create)?(double _Imaginary*, double);
+void (?create)?(float*, float _Imaginary);
+void (?create)?(float _Imaginary*, float);
+
+
+Let SMax be the highest ranking signed integer type, and let
+UMax be the highest ranking unsigned integer type. Then Cforall
+would define
+
+
+Creator(SMax, float);
+Creator(SMax, float _Complex);
+Creator(SMax, float _Imaginary);
+Creator(UMax, float);
+Creator(UMax, float _Complex);
+Creator(UMax, float _Imaginary);
+
+
+For every signed integer type T with rank greater than that of
+signed char, Cforall would define
+
+
+Creator(S, T);
+
+where S is the signed integer type with the next lowest rank.
+
+For every rank r greater than the rank of _Bool,
+Cforall would define
+
+
+Creator(unsigned(r-1), unsigned(r));
+
+
+For every rank r such that signed(r) exists,
+Cforall would define
+
+
+void (?create)?( signed(r)*, unsigned(r) );
+
+
+char and _Bool are interconvertible.
+
+void (?create)?(char*, _Bool);
+void (?create)?(_Bool*, char);
+
+
+If char is equivalent to signed char, the
+implementation would define
+
+
+Creator(char, signed char);
+void (?create)?(char*, unsigned char);
+
+
+Otherwise, the implementation would define
+
+Creator(char, unsigned char);
+void (?create)?(char*, signed char);
+void (?create)?(_Bool*, signed char);
+void (?create)?(signed char*, _Bool);
+
+
+Pointer conversions
+
+Pointer types are implicitly interconvertible with pointers to void,
+provided that the target type has all of the qualifiers of the source
+type.
+
+
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, void*))
+ void (?create)?(QVPtr*, SourceType*);
+
+
+This conversion uses the constructor idiom, but note
+that the assertion parameter is a promotion even though the conversion
+itself is not a promotion. My intent is that the assertion parameter will
+be bound to a promotion that adds type qualifiers
+to a pointer type. A conversion from int* to const
+void* would bind SourceType to int,
+QVPtr to const void*, and the assertion parameter
+to a promotion from void* to const void* (which
+is a specialization of one of the polymorphic type qualifier promotions
+given above). Because of this composition of pointer conversions, I don't
+have to define conversions for every combination of type qualifiers on the
+target type. I do have to handle all combinations of qualifiers on the
+source type:
+
+
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, const void*))
+ void (?create)?(QVPtr*, const SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, volatile void*))
+ void (?create)?(QVPtr*, volatile SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, restrict void*))
+ void (?create)?(QVPtr*, restrict SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, const volatile void*))
+ void (?create)?(QVPtr*, const volatile SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, const restrict void*))
+ void (?create)?(QVPtr*, const restrict SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, volatile restrict void*))
+ void (?create)?(QVPtr*, volatile restrict SourceType*);
+forall(dtype SourceType,
+ type QVPtr | void (?promote)?(QVPtr*, const volatile restrict void*))
+ void (?create)?(QVPtr*, const volatile restrict SourceType*);
+
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, TargetType*)
+ void (?create)?(QTPtr*, void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, const TargetType*)
+ void (?create)?(QTPtr*, const void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, volatile TargetType*)
+ void (?create)?(QTPtr*, volatile void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, restrict TargetType*)
+ void (?create)?(QTPtr*, restrict void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, const volatile TargetType*)
+ void (?create)?(QTPtr*, const volatile void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, const restrict TargetType*)
+ void (?create)?(QTPtr*, const restrict void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, volatile restrict TargetType*)
+ void (?create)?(QTPtr*, volatile restrict void*);
+forall(type QTPtr,
+ dtype TargetType | void (?promote)?(QTPtr*, const volatile restrict TargetType*)
+ void (?create)?(QTPtr*, const volatile restrict void*);
+
+
+Pre-Defined Explicit Conversions
+Function pointers are interconvertible.
+
+forall(ftype FT1, ftype FT2, type T | FT1* (?)?(T) ) FT2* (?)?(FT1*);
+
+
+Data pointers including pointers to void are
+interconvertible, regardless of type qualifiers.
+
+
+forall(dtype DT1, dtype DT2) DT2* (?)?(DT1*);
+forall(dtype DT1, dtype DT2) const DT2* (?)?(DT1*);
+forall(dtype DT1, dtype DT2) volatile DT2* (?)?(DT1*);
+forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(DT1*);
+
+forall(dtype DT1, dtype DT2) DT2* (?)?(const DT1*);
+forall(dtype DT1, dtype DT2) const DT2* (?)?(const DT1*);
+forall(dtype DT1, dtype DT2) volatile DT2* (?)?(const DT1*);
+forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(const DT1*);
+
+forall(dtype DT1, dtype DT2) DT2* (?)?(volatile DT*);
+forall(dtype DT1, dtype DT2) const DT2* (?)?(volatile DT*);
+forall(dtype DT1, dtype DT2) volatile DT2* (?)?(volatile DT*);
+forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(volatile DT*);
+
+forall(dtype DT1, dtype DT2) DT2* (?)?(const volatile DT*);
+forall(dtype DT1, dtype DT2) const DT2* (?)?(const volatile DT*);
+forall(dtype DT1, dtype DT2) volatile DT2* (?)?(const volatile DT*);
+forall(dtype DT1, dtype DT2) const volatile DT2* (?)?(const volatile DT*);
+
+
+Integers and pointers are interconvertible. For every integer type
+I define
+
+forall(dtype DT, type T | I (?)?(T) ) DT* ?(?)(T);
+forall(ftype FT, type T | I (?)?(T) ) FT* ?(?)(T);
+
+forall(dtype DT, type T | DT* (?)?(T) ) I (?)?(T);
+forall(dtype DT, type T | DT* (?)?(T) ) I (?)?(T);
+
+
+Non-Conversions
+C99 has a few other "conversions" that don't fit into this proposal.
+Outside of some special circumstances (such as application of
+sizeof),
+
+ - array lvalues "convert" to pointers
+ - function designators "convert" to pointers to functions
+ - non-array lvalues "convert" to plain values
+ - bit fields undergo "integer promotion" to
int or
+ unsigned int values.
+
+
+I'd like to stop calling these "conversions". Perhaps they could be
+handled by some verbiage in the semantics of "Primary Expressions".
+
+Cforall-as-is provides "specialization", which reduces the number of
+type parameters or assertion parameters of a polymorphic object or
+function. Specialization looks like a conversion -- it can happen
+implicitly or as a result of a cast -- but would no longer be considered to
+be a conversion.
+
+Assignment
+
+Since extended Cforall separates conversion from assignment, it can
+simplify Cforall-as-is's set of assignment operators. Implicit conversions
+can add type qualifiers to the target's type, and to the source's type in
+the case of pointer assignment.
+
+
+char ?=?(volatile char*, char);
+char ?+=?(volatile char*, char);
+// ... and similarly for the rest of the basic types and
+// compound assignment operators.
+
+
+char c;
+c = 'a'; // => ?=?( &c, 'a' );
+ // => ?=?( (volatile char*)&c, 'a' );
+
+
+
+// Assignment between data pointers, where the target has all of
+// the qualifiers of the source.
+forall(dtype DT)
+ DT* ?=?(DT* volatile restrict*, DT*);
+forall(dtype DT)
+ const DT* ?=?(const DT* volatile restrict*, const DT*);
+forall(dtype DT)
+ volatile DT* ?=?(volatile DT* volatile restrict*, volatile DT*);
+forall(dtype DT)
+ const volatile DT* ?=?(const volatile DT* volatile restrict*, const volatile DT*);
+
+// Assignment to data pointers from voidpointers.
+forall(dtype DT) DT* ?=?(DT* volatile restrict*, void*)
+forall(dtype DT)
+ const DT* ?=?(const DT* volatile restrict*, const void*);
+forall(dtype DT)
+ volatile DT* ?=?(volatile DT* volatile restrict*, volatile void*);
+forall(dtype DT)
+ const volatile DT* ?=?(const volatile DT* volatile restrict*, const volatile void*);
+
+// Assignment to void pointers from data pointers.
+forall(dtype DT)
+ void* ?=?(void* volatile restrict*, DT*);
+forall(dtype DT)
+ const void* ?=?(const void* volatile restrict*, const DT*);
+forall(dtype DT)
+ volatile void* ?=?(volatile void* volatile restrict*, volatile DT*);
+forall(dtype DT)
+ const volatile void* ?=?(const volatile void* volatile restrict*, const volatile DT*);
+
+// Assignment from null pointers to other pointer types.
+forall(dtype DT)
+ void* ?=?(void* volatile restrict*, forall(dtype DT2) const DT2*);
+forall(dtype DT)
+ const void* ?=?(const void* volatile restrict*, forall(dtype DT2) const DT2*);
+forall(dtype DT)
+ volatile void* ?=?(volatile void* volatile restrict*, forall(dtype DT2) const DT2*);
+forall(dtype DT)
+ const volatile void* ?=?(const volatile void* volatile restrict*, forall(dtype DT2) const DT2*);
+
+// Function pointer assignment
+forall(ftype FT) FT* ?=?(FT* volatile restrict*, FT*);
+forall(ftype FT) FT* ?=?(FT* volatile restrict*, forall(ftype FT2) FT2*);
+
+
+
+
+
The difference, relative to Cforall-as-is, is that assignment operators
+come in one flavor (a pointer to a volatile value as the first operand)
+instead of two (a pointer to volatile in one case, a plain pointer in the
+other) or the four that restrict would have led to.
+
+
However, to make this work, the type of default assignment
+functions must also change. A declaration of a type T would
+implicitly declare
T ?=?(T volatile restrict*, T)
Final Notes
+
+The constructor idiom is polymorphic in the
+object's type: an initial value of one particular type can initialize
+objects of many types. The constructor that promotes a Wazzit
+into a Thingum is declared
+
+
+forall(type T | void (?promote)?(T*, Thingum) )
+ void (?promote)?(T*, Wazzit);
+
+("You can make a Wazzit into a Thingum and
+types higher in the hierarchy.")
+
+It would also be possible to use a constructor idiom where the object's
+type is fixed and the initial value's type is polymorphic:
+
+
+forall(type T | void (?promote)?(Wazzit*, T) )
+ void (?promote)?(Thingum*, T);
+
+("You can make a Thingum from a Wazzit and
+types lower in the hierarchy.")
+
+The "polymorphic value" idiom has the advantage that it is fairly
+obvious that the function is a constructor for type Thingum.
+In the "polymorphic object" idiom, Thingum is buried in the
+assertion parameter.
+
+However, I chose the "polymorphic object" idiom because it matches C's
+semantics for signed-to-unsigned integer conversions. In the "polymorphic
+object" idiom, the natural way to write the polymorphic promoter from
+int to larger types is
+
+
+
+forall(type T | void (?promote)?(T*, long) )
+ void (?promote)?(T* tp, int i) {
+ long l = i;
+ *tp = (T)l; // calls the assertion parameter.
+ }
+
+
+Now consider the case of a CPU with 16-bit ints, where we
+need to convert an int value -1 to a 32-bit
+unsigned long. The assertion parameter will be bound to the
+monomorphic long-to-unsigned long promoter. The
+function body above converts the int -1 to a long
+-1, and then uses the assertion parameter to convert the result to the
+correct unsigned long value: 4,294,967,295.
+
+In the "polymorphic value" idiom, the conversion would be done by
+calling the polymorphic promoter to unsigned long from smaller
+types:
+
+
+forall(type T | void (?promote)?(unsigned*, T) )
+ void (?promote)?(unsigned long* ulp, T t) {
+ unsigned u = t; // calls the assertion parameter.
+ *ulp = u;
+ }
+
+
+This time the assertion parameter will be bound to the
+int-to-unsigned promoter. The function body uses
+the assertion parameter to convert the integer -1 to unsigned
+65,565, and then converts the result to the incorrect unsigned
+long value 65,535.
+
+Clearly the "polymorphic value" idiom would require the implementation
+to do some unnatural, and probably implementation-dependent, bit mangling
+to get the right answer. Of course, an implementation is allowed to
+perform any unnatural acts it chooses. But programmers would have to
+conform to the prevailing constructor idiom when writing their
+constructors, and will want to write natural and portable code.
+
+
+
+
Index: src/tests/preempt_longrun/Makefile.am
===================================================================
--- src/tests/preempt_longrun/Makefile.am (revision 7bdcac1f3631ee6408a86b4d0321433114fee6d3)
+++ src/tests/preempt_longrun/Makefile.am (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
@@ -45,5 +45,5 @@
clean-local:
- rm -f ${TESTS}
+ rm -f ${TESTS} core* out.log
% : %.c ${CC}
Index: src/tests/preempt_longrun/Makefile.in
===================================================================
--- src/tests/preempt_longrun/Makefile.in (revision 7bdcac1f3631ee6408a86b4d0321433114fee6d3)
+++ src/tests/preempt_longrun/Makefile.in (revision 3fc59bdb3dcc1b79be061440b40a2cebb66b85f3)
@@ -889,5 +889,5 @@
clean-local:
- rm -f ${TESTS}
+ rm -f ${TESTS} core* out.log
% : %.c ${CC}