Changeset a67279a for doc


Ignore:
Timestamp:
Mar 9, 2021, 2:46:59 PM (4 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
ab5498ec
Parents:
a33dcd5 (diff), 223ee0d (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/LaTeXmacros/lstlang.sty

    ra33dcd5 ra67279a  
    88%% Created On       : Sat May 13 16:34:42 2017
    99%% Last Modified By : Peter A. Buhr
    10 %% Last Modified On : Wed Sep 23 22:40:04 2020
    11 %% Update Count     : 24
     10%% Last Modified On : Wed Feb 17 09:21:15 2021
     11%% Update Count     : 27
    1212%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1313
    … …  
    113113        morekeywords={
    114114                _Alignas, _Alignof, __alignof, __alignof__, asm, __asm, __asm__, __attribute, __attribute__,
    115                 auto, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
    116                 coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally,
     115                auto, basetypeof, _Bool, catch, catchResume, choose, _Complex, __complex, __complex__, __const, __const__,
     116                coroutine, disable, dtype, enable, exception, __extension__, fallthrough, fallthru, finally, fixup,
    117117                __float80, float80, __float128, float128, forall, ftype, generator, _Generic, _Imaginary, __imag, __imag__,
    118118                inline, __inline, __inline__, __int128, int128, __label__, monitor, mutex, _Noreturn, one_t, or,
    119                 otype, restrict, __restrict, __restrict__, __signed, __signed__, _Static_assert, suspend, thread,
    120                 _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
     119                otype, restrict, __restrict, __restrict__, recover, report, __signed, __signed__, _Static_assert, suspend,
     120                thread, _Thread_local, throw, throwResume, timeout, trait, try, ttype, typeof, __typeof, __typeof__,
    121121                virtual, __volatile, __volatile__, waitfor, when, with, zero_t,
    122122    },

  • doc/theses/andrew_beach_MMath/existing.tex

    ra33dcd5 ra67279a  
    1414\section{Overloading and \lstinline{extern}}
    1515\CFA has extensive overloading, allowing multiple definitions of the same name
    16 to be defined.~\cite{Moss18}
     16to be defined~\cite{Moss18}.
    1717\begin{cfa}
    1818char i; int i; double i;                        $\C[3.75in]{// variable overload}$
    … …  
    4646pointers using the ampersand (@&@) instead of the pointer asterisk (@*@). \CFA
    4747references may also be mutable or non-mutable. If mutable, a reference variable
    48 may be assigned to using the address-of operator (@&@), which converts the
     48may be assigned using the address-of operator (@&@), which converts the
    4949reference to a pointer.
    5050\begin{cfa}
    … …  
    5858\section{Constructors and Destructors}
    5959
    60 Both constructors and destructors are operators, which means they are just
     60Both constructors and destructors are operators, which means they are
    6161functions with special operator names rather than type names in \Cpp. The
    6262special operator names may be used to call the functions explicitly (not
    … …  
    6464
    6565In general, operator names in \CFA are constructed by bracketing an operator
    66 token with @?@, which indicates where the arguments. For example, infixed
     66token with @?@, which indicates the position of the arguments. For example, infixed
    6767multiplication is @?*?@ while prefix dereference is @*?@. This syntax make it
    6868easy to tell the difference between prefix operations (such as @++?@) and
    … …  
    8989definition, \CFA creates a default and copy constructor, destructor and
    9090assignment (like \Cpp). It is possible to define constructors/destructors for
    91 basic and existing types.
     91basic and existing types (unlike \Cpp).
    9292
    9393\section{Polymorphism}
    … …  
    120120        do_once(value);
    121121}
    122 void do_once(int i) { ... }  // provide assertion
    123 int i;
     122void do_once(@int@ i) { ... }  // provide assertion
     123@int@ i;
    124124do_twice(i); // implicitly pass assertion do_once to do_twice
    125125\end{cfa}
    … …  
    172172declarations instead of parameters, returns, and local variable declarations.
    173173\begin{cfa}
    174 forall(dtype T)
     174forall(dtype @T@)
    175175struct node {
    176         node(T) * next;  // generic linked node
    177         T * data;
    178 }
     176        node(@T@) * next;  // generic linked node
     177        @T@ * data;
     178}
     179node(@int@) inode;
    179180\end{cfa}
    180181The generic type @node(T)@ is an example of a polymorphic-type usage.  Like \Cpp
    181 templates usage, a polymorphic-type usage must specify a type parameter.
     182template usage, a polymorphic-type usage must specify a type parameter.
    182183
    183184There are many other polymorphism features in \CFA but these are the ones used
    184185by the exception system.
    185186
    186 \section{Concurrency}
    187 \CFA has a number of concurrency features: @thread@, @monitor@, @mutex@
    188 parameters, @coroutine@ and @generator@. The two features that interact with
    189 the exception system are @thread@ and @coroutine@; they and their supporting
     187\section{Control Flow}
     188\CFA has a number of advanced control-flow features: @generator@, @coroutine@, @monitor@, @mutex@ parameters, and @thread@.
     189The two features that interact with
     190the exception system are @coroutine@ and @thread@; they and their supporting
    190191constructs are described here.
    191192
    … …  
    216217CountUp countup;
    217218\end{cfa}
    218 Each coroutine has @main@ function, which takes a reference to a coroutine
     219Each coroutine has a @main@ function, which takes a reference to a coroutine
    219220object and returns @void@.
    220221\begin{cfa}[numbers=left]
    … …  
    230231In this function, or functions called by this function (helper functions), the
    231232@suspend@ statement is used to return execution to the coroutine's caller
    232 without terminating the coroutine.
     233without terminating the coroutine's function.
    233234
    234235A coroutine is resumed by calling the @resume@ function, \eg @resume(countup)@.
    … …  
    242243@resume(countup).next@.
    243244
    244 \subsection{Monitors and Mutex}
     245\subsection{Monitor and Mutex Parameter}
    245246Concurrency does not guarantee ordering; without ordering results are
    246247non-deterministic. To claw back ordering, \CFA uses monitors and @mutex@
    … …  
    260261and only one runs at a time.
    261262
    262 \subsection{Threads}
     263\subsection{Thread}
    263264Functions, generators, and coroutines are sequential so there is only a single
    264265(but potentially sophisticated) execution path in a program. Threads introduce
    … …  
    268269monitors and mutex parameters. For threads to work safely with other threads,
    269270also requires mutual exclusion in the form of a communication rendezvous, which
    270 also supports internal synchronization as for mutex objects. For exceptions
    271 only the basic two basic operations are important: thread fork and join.
     271also supports internal synchronization as for mutex objects. For exceptions,
     272only two basic thread operations are important: fork and join.
    272273
    273274Threads are created like coroutines with an associated @main@ function:

  • doc/user/user.tex

    ra33dcd5 ra67279a  
    1111%% Created On       : Wed Apr  6 14:53:29 2016
    1212%% Last Modified By : Peter A. Buhr
    13 %% Last Modified On : Mon Feb 15 13:48:53 2021
    14 %% Update Count     : 4452
     13%% Last Modified On : Sun Mar  7 21:50:24 2021
     14%% Update Count     : 4574
    1515%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
    1616
    … …  
    40764076
    40774077
     4078\subsection{Concurrent Stream Access}
     4079
     4080When a stream is shared by multiple threads, input or output characters can be intermixed or cause failure.
     4081For example, if two threads execute the following:
     4082\begin{cfa}
     4083$\emph{thread\(_1\)}$ : sout | "abc " | "def ";
     4084$\emph{thread\(_2\)}$ : sout | "uvw " | "xyz ";
     4085\end{cfa}
     4086possible outputs are:
     4087\begin{cquote}
     4088\begin{tabular}{@{}l|l|l|l|l@{}}
     4089\begin{cfa}
     4090abc def
     4091uvw xyz
     4092\end{cfa}
     4093&
     4094\begin{cfa}
     4095abc uvw xyz
     4096def
     4097\end{cfa}
     4098&
     4099\begin{cfa}
     4100uvw abc xyz def
     4101
     4102\end{cfa}
     4103&
     4104\begin{cfa}
     4105abuvwc dexf
     4106yz
     4107\end{cfa}
     4108&
     4109\begin{cfa}
     4110uvw abc def
     4111xyz
     4112\end{cfa}
     4113\end{tabular}
     4114\end{cquote}
     4115Concurrent operations can even corrupt the internal state of the stream resulting in failure.
     4116As a result, some form of mutual exclusion is required for concurrent stream access.
     4117
     4118A coarse-grained solution is to perform all stream operations via a single thread or within a monitor providing the necessary mutual exclusion for the stream.
     4119A fine-grained solution is to have a lock for each stream, which is acquired and released around stream operations by each thread.
     4120\CFA provides a fine-grained solution where a \Index{recursive lock} is acquired and released indirectly via a manipulator ©acquire© or instantiating an \Index{RAII} type specific for the kind of stream: ©osacquire©\index{ostream@©ostream©!osacquire@©osacquire©} for output streams and ©isacquire©\index{isacquire@©isacquire©}\index{istream@©istream©!isacquire@©isacquire©} for input streams.
     4121
     4122The common usage is manipulator ©acquire©\index{ostream@©ostream©!acquire@©acquire©} to lock a stream during a single cascaded I/O expression, where it should appear as the first item in a cascade list, \eg:
     4123\begin{cfa}
     4124$\emph{thread\(_1\)}$ : sout | @acquire@ | "abc " | "def ";   // manipulator
     4125$\emph{thread\(_2\)}$ : sout | @acquire@ | "uvw " | "xyz ";
     4126\end{cfa}
     4127Now, the order of the thread execution is still non-deterministic, but the output is constrained to two possible lines in either order.
     4128\begin{cquote}
     4129\def\VRfont{\fontfamily{pcr}\upshape\selectfont}
     4130\begin{tabular}{@{}l|l@{}}
     4131\begin{cfa}
     4132abc def
     4133uvw xyz
     4134\end{cfa}
     4135&
     4136\begin{cfa}
     4137uvw xyz
     4138abc def
     4139\end{cfa}
     4140\end{tabular}
     4141\end{cquote}
     4142In summary, the stream lock is acquired by the ©acquire© manipulator and implicitly released at the end of the cascaded I/O expression ensuring all operations in the expression occur atomically.
     4143
     4144To lock a stream across multiple I/O operations, declare an instance of the appropriate ©osacquire© or ©isacquire© type to implicitly acquire and release the stream lock for the object's duration, \eg:
     4145\begin{cfa}
     4146{       // acquire sout for block duration
     4147        @osacquire@ acq = { sout };                             $\C{// named stream locker}$
     4148        sout | 1;
     4149        sout | @acquire@ | 2 | 3;                               $\C{// unnecessary, but ok to acquire and release again}$
     4150        sout | 4;
     4151}       // implicitly release the lock when "acq" is deallocated
     4152\end{cfa}
     4153Note, the unnecessary ©acquire© manipulator works because the recursive stream-lock can be acquired/released multiple times by the owner thread.
     4154Hence, calls to functions that also acquire a stream lock for their output do not result in \Index{deadlock}.
     4155
     4156The previous values written by threads 1 and 2 can be read in concurrently:
     4157\begin{cfa}
     4158{       // acquire sin lock for block duration
     4159        @isacquire acq = { sin };@                              $\C{// named stream locker}$
     4160        int x, y, z, w;
     4161        sin | x;
     4162        sin | @acquire@ | y | z;                                $\C{// unnecessary, but ok to acquire and release again}$
     4163        sin | w;
     4164}       // implicitly release the lock when "acq" is deallocated
     4165\end{cfa}
     4166Again, the order of the reading threads is non-deterministic.
     4167Note, non-deterministic reading is rare.
     4168
     4169\Textbf{WARNING:} The general problem of \Index{nested locking} can occur if routines are called in an I/O sequence that block, \eg:
     4170\begin{cfa}
     4171sout | @acquire@ | "data:" | rtn( mon );        $\C{// mutex call on monitor}$
     4172\end{cfa}
     4173If the thread executing the I/O expression blocks in the monitor with the ©sout© lock, other threads writing to ©sout© also block until the thread holding the lock is unblocked and releases it.
     4174This scenario can lead to \Index{deadlock}, if the thread that is going to unblock the thread waiting in the monitor first writes to ©sout© (deadly embrace).
     4175To prevent nested locking, a simple precaution is to factor out the blocking call from the expression, \eg:
     4176\begin{cfa}
     4177int @data@ = rtn( mon );
     4178sout | acquire | "data:" | @data@;
     4179\end{cfa}
     4180
     4181\Textbf{WARNING:} ©printf©\index{printf@©printf©}, ©scanf©\index{scanf@©scanf©} and their derivatives are unsafe when used with user-level threading, as in \CFA.
     4182These stream routines use kernel-thread locking (©futex©\index{futex@©futex©}), which block kernel threads, to prevent interleaving of I/O.
     4183However, the following simple example illustrates how a deadlock can occur (other complex scenarios are possible).
     4184Assume a single kernel thread and two user-level threads calling ©printf©.
     4185One user-level thread acquires the I/O lock and is time-sliced while performing ©printf©.
     4186The other user-level thread then starts execution, calls ©printf©, and blocks the only kernel thread because it cannot acquire the I/O lock.
     4187It does not help if the kernel lock is multiple acquisition, \ie, the lock owner can acquire it multiple times, because it then results in two user threads in the ©printf© critical section, corrupting the stream.
     4188
     4189
     4190\begin{comment}
    40784191\section{Types}
    40794192
    … …  
    41544267process((int) s); // type is converted, no function is called
    41554268\end{cfa}
     4269\end{comment}
    41564270
    41574271
    … …  
    43694483\begin{table}[hbt]
    43704484\centering
    4371 \input{../refrat/operidents}
     4485\begin{tabular}{@{}l@{\hspace{\parindentlnth}}l@{\hspace{\parindentlnth}}l@{}}
     4486\begin{tabular}{@{}ll@{}}
     4487©?[?]©  & subscripting \impl{?[?]}                                      \\
     4488©?()©   & function call \impl{?()}                                      \\
     4489©?++©   & postfix increment \impl{?++}                          \\
     4490©?--©   & postfix decrement \impl{?--}                          \\
     4491©++?©   & prefix increment \impl{++?}                           \\
     4492©--?©   & prefix decrement \impl{--?}                           \\
     4493©*?©    & dereference \impl{*?}                                         \\
     4494©+?©    & unary plus \impl{+?}                                          \\
     4495©-?©    & arithmetic negation \impl{-?}                         \\
     4496©~?©    & bitwise negation \impl{~?}                            \\
     4497©!?©    & logical complement \impl{"!?}                         \\
     4498©?\?©   & exponentiation \impl{?\?}                                     \\
     4499©?*?©   & multiplication \impl{?*?}                                     \\
     4500©?/?©   & division \impl{?/?}                                           \\
     4501©?%?©   & remainder \impl{?%?}                                          \\
     4502\end{tabular}
     4503&
     4504\begin{tabular}{@{}ll@{}}
     4505©?+?©   & addition \impl{?+?}                                           \\
     4506©?-?©   & subtraction \impl{?-?}                                        \\
     4507©?<<?©  & left shift \impl{?<<?}                                        \\
     4508©?>>?©  & right shift \impl{?>>?}                                       \\
     4509©?<?©   & less than \impl{?<?}                                          \\
     4510©?<=?©  & less than or equal \impl{?<=?}                        \\
     4511©?>=?©  & greater than or equal \impl{?>=?}                     \\
     4512©?>?©   & greater than \impl{?>?}                                       \\
     4513©?==?©  & equality \impl{?==?}                                          \\
     4514©?!=?©  & inequality \impl{?"!=?}                                       \\
     4515©?&?©   & bitwise AND \impl{?&?}                                        \\
     4516©?^?©   & exclusive OR \impl{?^?}                                       \\
     4517©?|?©   & inclusive OR \impl{?"|?}                                      \\
     4518                                                                                                        \\
     4519                                                                                                        \\
     4520\end{tabular}
     4521&
     4522\begin{tabular}{@{}ll@{}}
     4523©?=?©   & simple assignment \impl{?=?}                          \\
     4524©?\=?©  & exponentiation assignment \impl{?\=?}         \\
     4525©?*=?©  & multiplication assignment \impl{?*=?}         \\
     4526©?/=?©  & division assignment \impl{?/=?}                       \\
     4527©?%=?©  & remainder assignment \impl{?%=?}                      \\
     4528©?+=?©  & addition assignment \impl{?+=?}                       \\
     4529©?-=?©  & subtraction assignment \impl{?-=?}            \\
     4530©?<<=?© & left-shift assignment \impl{?<<=?}            \\
     4531©?>>=?© & right-shift assignment \impl{?>>=?}           \\
     4532©?&=?©  & bitwise AND assignment \impl{?&=?}            \\
     4533©?^=?©  & exclusive OR assignment \impl{?^=?}           \\
     4534©?|=?©  & inclusive OR assignment \impl{?"|=?}          \\
     4535                                                                                                        \\
     4536                                                                                                        \\
     4537                                                                                                        \\
     4538\end{tabular}
     4539\end{tabular}
    43724540\caption{Operator Identifiers}
    43734541\label{opids}
    … …  
    65026670\label{s:CFAKeywords}
    65036671
    6504 \CFA introduces the following new keywords.
     6672\CFA introduces the following new \Index{keyword}s, which cannot be used as identifiers.
    65056673
    65066674\begin{cquote}
    6507 \input{../refrat/keywords}
     6675\begin{tabular}{@{}lllllll@{}}
     6676\begin{tabular}{@{}l@{}}
     6677\Indexc{basetypeof}             \\
     6678\Indexc{choose}                 \\
     6679\Indexc{coroutine}              \\
     6680\Indexc{disable}                \\
     6681\end{tabular}
     6682&
     6683\begin{tabular}{@{}l@{}}
     6684\Indexc{enable}                 \\
     6685\Indexc{exception}              \\
     6686\Indexc{fallthrough}    \\
     6687\Indexc{fallthru}               \\
     6688\end{tabular}
     6689&
     6690\begin{tabular}{@{}l@{}}
     6691\Indexc{finally}                \\
     6692\Indexc{fixup}                  \\
     6693\Indexc{forall}                 \\
     6694\Indexc{generator}              \\
     6695\end{tabular}
     6696&
     6697\begin{tabular}{@{}l@{}}
     6698\Indexc{int128}                 \\
     6699\Indexc{monitor}                \\
     6700\Indexc{mutex}                  \\
     6701\Indexc{one_t}                  \\
     6702\end{tabular}
     6703&
     6704\begin{tabular}{@{}l@{}}
     6705\Indexc{report}                 \\
     6706\Indexc{suspend}                \\
     6707\Indexc{throw}                  \\
     6708\Indexc{throwResume}    \\
     6709\end{tabular}
     6710&
     6711\begin{tabular}{@{}l@{}}
     6712\Indexc{trait}                  \\
     6713\Indexc{try}                    \\
     6714\Indexc{virtual}                \\
     6715\Indexc{waitfor}                \\
     6716\end{tabular}
     6717&
     6718\begin{tabular}{@{}l@{}}
     6719\Indexc{when}                   \\
     6720\Indexc{with}                   \\
     6721\Indexc{zero_t}                 \\
     6722                                                \\
     6723\end{tabular}
     6724\end{tabular}
    65086725\end{cquote}
    6509 
     6726\CFA introduces the following new \Index{quasi-keyword}s, which can be used as identifiers.
     6727\begin{cquote}
     6728\begin{tabular}{@{}ll@{}}
     6729\begin{tabular}{@{}l@{}}
     6730\Indexc{catch}                  \\
     6731\Indexc{catchResume}    \\
     6732\Indexc{finally}                \\
     6733\end{tabular}
     6734&
     6735\begin{tabular}{@{}l@{}}
     6736\Indexc{fixup}                  \\
     6737\Indexc{or}                             \\
     6738\Indexc{timeout}                \\
     6739\end{tabular}
     6740\end{tabular}
     6741\end{cquote}
    65106742
    65116743\section{Standard Headers}
Note: See TracChangeset for help on using the changeset viewer.