Index: doc/user/user.tex =================================================================== --- doc/user/user.tex (revision d4d4ac8c7b7430722cd1def52b6646a6947d5568) +++ doc/user/user.tex (revision 0ebbca40873f4e872ca756a8ae284370c8977e5f) @@ -11,6 +11,6 @@ %% Created On : Wed Apr 6 14:53:29 2016 %% Last Modified By : Peter A. Buhr -%% Last Modified On : Sun Oct 10 12:45:00 2021 -%% Update Count : 5095 +%% Last Modified On : Sat Feb 12 10:10:11 2022 +%% Update Count : 5372 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% @@ -40,5 +40,5 @@ % blue highlighting ß...ß (sharp s symbol) emacs: C-q M-_ % green highlighting ¢...¢ (cent symbol) emacs: C-q M-" -% LaTex escape §...§ (section symbol) emacs: C-q M-' +% LaTex escape ...§ (section symbol) emacs: C-q M-' % keyword escape ¶...¶ (pilcrow symbol) emacs: C-q M-^ % math escape $...$ (dollar symbol) @@ -85,4 +85,5 @@ \newcommand{\B}[1]{{\Textbf[blue]{#1}}} \newcommand{\G}[1]{{\Textbf[OliveGreen]{#1}}} +\newcommand{\Sp}{\R{\textvisiblespace}} \newcommand{\KWC}{K-W C\xspace} @@ -156,6 +157,6 @@ One of the main design philosophies of \CFA is to ``\Index{describe not prescribe}'', which means \CFA tries to provide a pathway from low-level C programming to high-level \CFA programming, but it does not force programmers to ``do the right thing''. Programmers can cautiously add \CFA extensions to their C programs in any order and at any time to incrementally move towards safer, higher-level programming. -A programmer is always free to reach back to C from \CFA, for any reason, and in many cases, new \CFA features can be locally switched back to there C counterpart. -There is no notion or requirement for \emph{rewriting} a legacy C program in \CFA; +A programmer is always free to reach back to C from \CFA, for any reason, and in many cases, new \CFA features can be locally switched back to their C counterpart. +There is no notion or requirement for \emph{rewriting} a legacy C program to \CFA; instead, a programmer evolves a legacy program into \CFA by incrementally incorporating \CFA features. As well, new programs can be written in \CFA using a combination of C and \CFA features. @@ -163,13 +164,13 @@ \Index*[C++]{\CC{}}~\cite{c++:v1} had a similar goal 30 years ago, allowing object-oriented programming to be incrementally added to C. -However, \CC currently has the disadvantages of a strong object-oriented bias, multiple legacy design-choices that cannot be updated, and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project. +However, \CC currently has the disadvantages of a strong object-oriented bias, multiple legacy design-choices that are difficult to update, and active divergence of the language model from C, requiring significant effort and training to incrementally add \CC to a C-based project. In contrast, \CFA has 30 years of hindsight and a clean starting point. Like \Index*[C++]{\CC{}}, there may be both old and new ways to achieve the same effect. For example, the following programs compare the C, \CFA, and \CC I/O mechanisms, where the programs output the same result. -\begin{center} +\begin{flushleft} \begin{tabular}{@{}l@{\hspace{1em}}l@{\hspace{1em}}l@{}} -\multicolumn{1}{c@{\hspace{1em}}}{\textbf{C}} & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{\CC}} \\ -\begin{cfa} +\multicolumn{1}{@{}c@{\hspace{1em}}}{\textbf{C}} & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c@{}}{\textbf{\CC}} \\ +\begin{cfa}[tabsize=3] #include $\indexc{stdio.h}$ @@ -180,5 +181,5 @@ \end{cfa} & -\begin{cfa} +\begin{cfa}[tabsize=3] #include $\indexc{fstream}$ @@ -189,14 +190,14 @@ \end{cfa} & -\begin{cfa} +\begin{cfa}[tabsize=3] #include $\indexc{iostream}$ using namespace std; int main() { int x = 0, y = 1, z = 2; - ®cout< +#include $\C{// setlocale}$ +#include $\C{// getenv}$ + +int main() { + void print() { + sout | 12 | 123 | 1234 | 12345 | 123456 | 1234567; + sout | 12. | 123.1 | 1234.12 | 12345.123 | 123456.1234 | 1234567.12345; + sout | nl; + } + sout | "Default locale off"; + print(); + sout | "Locale on" | ®setlocale( LC_NUMERIC, getenv( "LANG" ) )®; // enable local locale + print(); + sout | "German" | ®setlocale( LC_NUMERIC, "de_DE.UTF-8" )®; // enable German locale + print(); + sout | "Ukraine" | ®setlocale( LC_NUMERIC, "uk_UA.utf8" )®; // enable Ukraine locale + print(); + sout | "Default locale off" | ®setlocale( LC_NUMERIC, "C" )®; // disable locale + print(); +} + +Default locale off +12 123 1234 12345 123456 1234567 +12. 123.1 1234.12 12345.123 123456.1234 1234567.12345 + +Locale on en_US.UTF-8 +12 123 1®,®234 12®,®345 123®,®456 1®,®234®,®567 +12®.® 123®.®1 1®,®234®.®12 12®,®345®.®123 123®,®456®.®1234 1®,®234®,®567®.®12345 + +German de_DE.UTF-8 +12 123 1®.®234 12®.®345 123®.®456 1®.®234®.®567 +12®.® 123®,®1®.® 1®.®234®,®12 12®.®345®,®123 123®.®456®,®1234 1®.®234®.®567®,®12345 + +Ukraine uk_UA.utf8 +12 123 1 234 12 345 123 456 1 234 567 +12®.® 123®,®1®.® 1$\Sp$234®,®12®.® 12$\Sp$ 345®,®123®.® 123$\Sp$ 456®,®1234®.® 1$\Sp$ 234$\Sp$567®,®12345®.® + +Default locale off C +12 123 1234 12345 123456 1234567 +12. 123.1 1234.12 12345.123 123456.1234 1234567.12345 +\end{cfa} +\caption{Stream Locale} +\label{f:StreamLocale} +\end{figure} @@ -4555,4 +4666,5 @@ \end{figure} + \begin{comment} \section{Types} @@ -4637,5 +4749,5 @@ -\subsection{Structures} +\section{Structures} Structures in \CFA are basically the same as structures in C. @@ -5270,5 +5382,5 @@ \subsection{Coroutine} -\Index{Coroutines} are the precursor to tasks. +\Index{Coroutines} are the precursor to threads. \VRef[Figure]{f:FibonacciCoroutine} shows a coroutine that computes the \Index*{Fibonacci} numbers. @@ -5372,9 +5484,9 @@ -\subsection{Tasks} +\subsection{Threads} \CFA also provides a simple mechanism for creating and utilizing user level threads. -A task provides mutual exclusion like a monitor, and also has its own execution state and a thread of control. -Similar to a monitor, a task is defined like a structure: +A thread provides mutual exclusion like a monitor, and also has its own execution state and a thread of control. +Similar to a monitor, a thread is defined like a structure: \begin{figure} @@ -5420,6 +5532,6 @@ } \end{cfa} -\caption{Simple Tasks} -\label{f:SimpleTasks} +\caption{Simple Threads} +\label{f:SimpleThreads} \end{figure} @@ -6788,6 +6900,6 @@ In \CFA, there are ambiguous cases with dereference and operator identifiers, \eg ©int *?*?()©, where the string ©*?*?© can be interpreted as: \begin{cfa} -*?$\R{\textvisiblespace}$*? $\C{// dereference operator, dereference operator}$ -*$\R{\textvisiblespace}$?*? $\C{// dereference, multiplication operator}$ +*?$\Sp$*? $\C{// dereference operator, dereference operator}$ +*$\Sp$?*? $\C{// dereference, multiplication operator}$ \end{cfa} By default, the first interpretation is selected, which does not yield a meaningful parse. @@ -6813,6 +6925,6 @@ Therefore, it is necessary to disambiguate these cases with a space: \begin{cfa} -i++$\R{\textvisiblespace}$? i : 0; -i?$\R{\textvisiblespace}$++i : 0; +i++$\Sp$? i : 0; +i?$\Sp$++i : 0; \end{cfa} @@ -7430,17 +7542,17 @@ char random( void );$\indexc{random}$ char random( char u ); $\C{// [0,u)}$ -char random( char l, char u ); $\C{// [l,u)}$ +char random( char l, char u ); $\C{// [l,u]}$ int random( void ); int random( int u ); $\C{// [0,u)}$ -int random( int l, int u ); $\C{// [l,u)}$ +int random( int l, int u ); $\C{// [l,u]}$ unsigned int random( void ); unsigned int random( unsigned int u ); $\C{// [0,u)}$ -unsigned int random( unsigned int l, unsigned int u ); $\C{// [l,u)}$ +unsigned int random( unsigned int l, unsigned int u ); $\C{// [l,u]}$ long int random( void ); long int random( long int u ); $\C{// [0,u)}$ -long int random( long int l, long int u ); $\C{// [l,u)}$ +long int random( long int l, long int u ); $\C{// [l,u]}$ unsigned long int random( void ); unsigned long int random( unsigned long int u ); $\C{// [0,u)}$ -unsigned long int random( unsigned long int l, unsigned long int u ); $\C{// [l,u)}$ +unsigned long int random( unsigned long int l, unsigned long int u ); $\C{// [l,u]}$ float random( void ); $\C{// [0.0, 1.0)}$ double random( void ); $\C{// [0.0, 1.0)}$ @@ -8104,4 +8216,185 @@ Duration boot(); $\C{// monotonic duration since computer boot}$ \end{cfa} + + +\section{Pseudo Random Number Generator} +\label{s:PRNG} + +Random numbers are values generated independently, i.e., new values do not depend on previous values (independent trials), \eg lottery numbers, shuffled cards, dice roll, coin flip. +While a primary goal of programming is computing values that are \emph{not} random, random values are useful in simulation, cryptography, games, etc. +A random-number generator is an algorithm computing independent values. +If the algorithm uses deterministic computation (predictable sequence of values), it generates \emph{pseudo} random numbers versus \emph{true} random numbers. + +All \newterm{pseudo random-number generators} (\newterm{PRNG}) involve some technique to scramble bits of a value, \eg multiplicative recurrence: +\begin{cfa} +rand = 36973 * (rand & 65535) + (rand >> 16); // scramble bits +\end{cfa} +Multiplication of large values adds new least-significant bits and drops most-significant bits. +\begin{quote} +\begin{tabular}{@{}r|l@{}} +bits 63--32 (most) & bits 31--0 (least) \\ +\hline +0x0 & 0x3e8e36 \\ +0x5f & 0x718c25e1 \\ +0xad3e & 0x7b5f1dbe \\ +0xbc3b & 0xac69ff19 \\ +0x1070f & 0x2d258dc6 \\ +\end{tabular} +\end{quote} +By dropping bits 63--32, bits 31--0 become scrambled after each multiply. +The least-significant bits \emph{appear} random but the same bits are always generated given a fixed starting value, called the \newterm{seed} (value 0x3e8e36 above). +Hence, if a program uses the same seed, the same sequence of pseudo-random values is generated from the PRNG. +Often the seed is set to another random value like a program's process identifier (©getpid©\index{getpid@©getpid©}) or time when the program is run; +hence, one random value bootstraps another. +Finally, a PRNG usually generates a range of large values, \eg ©[0, UINT_MAX]©, which are scaled using the modulus operator, \eg ©prng() % 5© produces random values in the range 0--4. + +\CFA provides a sequential and concurrent PRNGs. +\begin{itemize} +\item +For sequential programs, like coroutining, the PRNG is used to randomize behaviour or values during execution, \eg in games, a character makes a random move or an object takes on a random value. +\begin{cfa} +struct PRNG { ... }; $\C[3.75in]{// opaque type}$ +void ?{}( PRNG & prng ); $\C{// random seed}$ +void ?{}( PRNG & prng, uint32_t seed ); $\C{// fixed seed}$ +void set_seed( PRNG & prng, uint32_t seed_ ); $\C{// set seed}$ +uint32_t get_seed( PRNG & prng ); $\C{// get seed}$ +uint32_t prng( PRNG & prng ); $\C{// [0,UINT\_MAX]}$ +uint32_t prng( PRNG & prng, uint32_t u ); $\C{// [0,u)}$ +uint32_t prng( PRNG & prng, uint32_t l, uint32_t u ); $\C{// [l,u]}$ +uint32_t calls( PRNG & prng ); $\C{// number of calls}\CRT$ +\end{cfa} +Sequential execution is repeatable given the same starting seeds for all ©PRNG©s. +In this scenario, it is useful to have multiple ©PRNG©, \eg one per player or object so a type is provided to generate multiple instances. +\VRef[Figure]{f:SequentialPRNG} shows an example that creates two sequential ©PRNG©s, sets both to the same seed (1009), and illustrates the 3 forms for generating random values, where both ©PRNG©s generate the same sequence of values. + +\begin{figure} +\begin{cfa} +PRNG prng1, prng2; +®set_seed( prng1, 1009 )®; ®set_seed( prng2, 1009 )®; +for ( 10 ) { + // Do not cascade prng calls because side-effect functions called in arbitrary order. + sout | nlOff | ®prng( prng1 )®; sout | ®prng( prng1, 5 )®; sout | ®prng( prng1, 0, 5 )® | '\t'; + sout | ®prng( prng2 )®; sout | ®prng( prng2, 5 )®; sout | ®prng( prng2, 0, 5 )® | nlOn; +} +\end{cfa} +\begin{cquote} +\begin{tabular}{@{}ll@{}} +\begin{cfa} +37301721 2 2 +1681308562 1 3 +290112364 3 2 +1852700364 4 3 +733221210 1 3 +1775396023 2 3 +123981445 2 3 +2062557687 2 0 +283934808 1 0 +672325890 1 3 +\end{cfa} +& +\begin{cfa} +37301721 2 2 +1681308562 1 3 +290112364 3 2 +1852700364 4 3 +733221210 1 3 +1775396023 2 3 +123981445 2 3 +2062557687 2 0 +283934808 1 0 +672325890 1 3 +\end{cfa} +\end{tabular} +\end{cquote} +\vspace{-10pt} +\caption{Sequential PRNG} +\label{f:SequentialPRNG} +\end{figure} + +\item +For concurrent programs, it is important the PRNG is thread-safe and not a point of contention. +A PRNG in concurrent programs is often used to randomize execution in short-running programs, \eg ©yield( prng() % 5 )©. + +Because concurrent execution is non-deterministic, seeding the concurrent PRNG is less important, as repeatable execution is impossible. +Hence, there is one system-wide PRNG (global seed) but each \CFA thread has its own non-contended PRNG state. +If the global seed is set, threads start with this seed, until it is reset and than threads start with the reset seed. +Hence, these threads generate the same sequence of random numbers from their specific starting seed. +If the global seed is \emph{not} set, threads start with a random seed, until the global seed is set. +Hence, these threads generate different sequences of random numbers. +If each thread needs its own seed, use a sequential ©PRNG© in each thread. + +There are two versions of the PRNG functions to manipulate the thread-local PRNG-state, which are differentiated by performance. +\begin{cfa} +void set_seed( uint32_t seed ); $\C[3.75in]{// set global seed}$ +uint32_t get_seed(); $\C{// get global seed}$ +// SLOWER +uint32_t prng(); $\C{// [0,UINT\_MAX]}$ +uint32_t prng( uint32_t u ); $\C{// [0,u)}$ +uint32_t prng( uint32_t l, uint32_t u ); $\C{// [l,u]}$ +// FASTER +uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th ); $\C{// [0,UINT\_MAX]}$ +uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t u ); $\C{// [0,u)}$ +uint32_t prng( $thread\LstStringStyle{\textdollar}$ & th, uint32_t l, uint32_t u ); $\C{// [l,u]}\CRT$ +\end{cfa} +The slower ©prng© functions call ©active_thread© internally to access the thread-local PRNG-state, while the faster ©prng© functions are passed a pointer to the active thread. +If the thread pointer is known, \eg in a thread ©main©, eliminating the call to ©active_thread© significantly reduces the cost for accessing the thread's PRNG state. +\VRef[Figure]{f:ConcurrentPRNG} shows an example using the slower/faster concurrent PRNG in the program main and a thread. + +\begin{figure} +\begin{cfa} +thread T {}; +void main( ®T & th® ) { // thread address + for ( i; 10 ) { + sout | nlOff | ®prng()®; sout | ®prng( 5 )®; sout | ®prng( 0, 5 )® | '\t'; // SLOWER + sout | nlOff | ®prng( th )®; sout | ®prng( th, 5 )®; sout | ®prng( th, 0, 5 )® | nlOn; // FASTER + } +} +int main() { + set_seed( 1009 ); + $\R{thread\LstStringStyle{\textdollar}}$ ®& th = *active_thread()®; // program-main thread-address + for ( i; 10 ) { + sout | nlOff | ®prng()®; sout | ®prng( 5 )®; sout | ®prng( 0, 5 )® | '\t'; // SLOWER + sout | nlOff | ®prng( th )®; sout | ®prng( th, 5 )®; sout | ®prng( th, 0, 5 )® | nlOn; // FASTER + } + sout | nl; + T t; // run thread +} +\end{cfa} +\begin{cquote} +\begin{tabular}{@{}ll@{}} +\begin{cfa} +37301721 2 2 +290112364 3 2 +733221210 1 3 +123981445 2 3 +283934808 1 0 +1414344101 1 3 +871831898 3 4 +2142057611 4 4 +802117363 0 4 +2346353643 1 3 +\end{cfa} +& +\begin{cfa} +1681308562 1 3 +1852700364 4 3 +1775396023 2 3 +2062557687 2 0 +672325890 1 3 +873424536 3 4 +866783532 0 1 +17310256 2 5 +492964499 0 0 +2143013105 3 2 +\end{cfa} +\end{tabular} +\begin{cfa} +// same output as above from thread t +\end{cfa} +\end{cquote} +\caption{Concurrent PRNG} +\label{f:ConcurrentPRNG} +\end{figure} +\end{itemize}