Ignore:
Timestamp:
Apr 9, 2024, 10:11:29 PM (8 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
c4024b46
Parents:
0bbe172
Message:

finish current proofreading of background chapter

Location:
doc/theses/mike_brooks_MMath
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/background.tex

    r0bbe172 r0554c1a  
    11\chapter{Background}
    22
    3 Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string,
     3Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string.
    44
    55
    … …  
    7171\begin{cquote}
    7272\begin{tabular}{@{}ll@{}}
    73 \multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function}} \\
     73\multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
    7474\begin{cfa}
    7575int @(*@ar@)[@5@]@; // definition
    … …  
    9090After all, reading a C array type is easy: just read it from the inside out, and know when to look left and when to look right!
    9191
    92 \CFA provides its own type, variable and routine declarations, using a different syntax.
     92\CFA provides its own type, variable and routine declarations, using a simpler syntax.
    9393The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
    9494The qualifiers have the same meaning in \CFA as in C.
    95 Hence, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[]@.
     95Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
    9696\begin{cquote}
    9797\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
    98 \multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} &   \\
     98\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{read left to right}}   \\
    9999\begin{cfa}
    100100int @*@ x1 @[5]@;
    … …  
    127127Each row of the table shows alternate syntactic forms.
    128128The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
    129 Removing the declared variable @x@, gives the type used for variable, structure field, cast or error message \PAB{(though note Section TODO points out that some types cannot be casted to)}.
     129Removing the declared variable @x@, gives the type used for variable, structure field, cast or error messages \PAB{(though note Section TODO points out that some types cannot be casted to)}.
    130130Unfortunately, parameter declarations \PAB{(section TODO)} have more syntactic forms and rules.
    131131
    132132\begin{table}
    133133\centering
    134 \caption{Syntactic Reference for Array vs Pointer. Includes interaction with constness.}
     134\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
    135135\label{bkgd:ar:usr:avp}
    136136\begin{tabular}{ll|l|l|l}
    137137        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
    138138        \hline
    139         $\triangleright$ & value & @T x;@ & @T x;@ & \\
     139$\triangleright$ & value & @T x;@ & @T x;@ & \\
    140140        \hline
    141141        & immutable value & @const T x;@ & @const T x;@ & \\
    142142        & & @T const x;@ & @T const x;@ & \\
    143143        \hline \hline
    144         $\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
     144$\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
    145145        \hline
    146146        & immutable ptr. to val. & @T * const x;@ & @const * T x;@ & \\
    … …  
    149149        & & @T const * x;@ & @* T const x;@ & \\
    150150        \hline \hline
    151         $\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
     151$\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
    152152        \hline
    153153        & ar.\ of immutable val. & @const T x[10];@ & @[10] const T x@ & @const array(T, 10) x@ \\
    … …  
    163163        & & @T const * x[10];@ & @[10] * T const x@ & @array(* const T, 10) x@ \\
    164164        \hline \hline
    165         $\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
     165$\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
    166166        \hline
    167167        & imm. ptr.\ to ar.\ of val. & @T (* const x)[10];@ & @const * [10] T x@ & @const * array(T, 10) x@ \\
    … …  
    180180        \item static
    181181        \item star as dimension
    182         \item under pointer decay:                              int p1[const 3]  being  int const *p1
     182        \item under pointer decay: @int p1[const 3]@ being @int const *p1@
    183183\end{itemize}
    184184
    … …  
    197197\lstinput{10-10}{bkgd-carray-decay.c}
    198198
    199 So, C provides an implicit conversion from @float[10]@ to @float*@, as described in ARM-6.3.2.1.3:
     199So, C provides an implicit conversion from @float[10]@ to @float *@.
    200200\begin{quote}
    201 Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a
    202 string literal used to initialize an array
    203 an expression that has type ``array of type'' is
    204 converted to an expression with type ``pointer to type'' that points to the initial element of
    205 the array object
     201Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a string literal used to
     202initialize an array an expression that has type ``array of \emph{type}'' is converted to an expression with type
     203``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
    206204\end{quote}
    207 
    208205This phenomenon is the famous ``pointer decay,'' which is a decay of an array-typed expression into a pointer-typed one.
    209 
    210206It is worthy to note that the list of exception cases does not feature the occurrence of @ar@ in @ar[i]@.
    211 Thus, subscripting happens on pointers, not arrays.
    212 
    213 Subscripting proceeds first with pointer decay, if needed.  Next, ARM-6.5.2.1.2 explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
    214 ARM-6.5.6.8 explains that the addition, of a pointer with an integer type,  is defined only when the pointer refers to an element that is in an array, with a meaning of ``@i@ elements away from,'' which is valid if @ar@ is big enough and @i@ is small enough.
    215 Finally, ARM-6.5.3.2.4 explains that the @*@ operator's result is the referenced element.
    216 
    217 Taken together, these rules also happen to illustrate that @ar[i]@ and @i[a]@ mean the same thing.
     207Thus, subscripting happens on pointers not arrays.
     208
     209Subscripting proceeds first with pointer decay, if needed.  Next, \cite[\S~6.5.2.1.2]{C11} explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
     210\cite[\S~6.5.6.8]{C11} explains that the addition, of a pointer with an integer type,  is defined only when the pointer refers to an element that is in an array, with a meaning of ``@i@ elements away from,'' which is valid if @ar@ is big enough and @i@ is small enough.
     211Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
     212Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
    218213
    219214Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
    … …  
    227222fs[5] = 3.14;
    228223\end{cfa}
    229 The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (ARM-7.22.3.4.2).
    230 But program says \emph{nothing} more about this pointer value, that might cause its referent to \emph{be} an array, before doing the subscript.
    231 
    232 Under this assumption, a pointer being subscripted (or added to, then dereferenced)
    233 by any value (positive, zero, or negative), gives a view of the program's entire address space,
    234 centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks,
    235 each potentially (re)interpreted as @typeof(*p)@.
    236 
    237 I call this phenomenon ``array diffraction,''  which is a diffraction of a single-element pointer
    238 into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
    239 
     224The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (\cite[\S~7.22.3.4.2]{C11}).
     225But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.
     226
     227Under this assumption, a pointer being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p)@.
     228I call this phenomenon ``array diffraction,''  which is a diffraction of a single-element pointer into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
    240229No pointer is exempt from array diffraction.
    241 
    242230No array shows its elements without pointer decay.
    243231
    244232A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
    245 ARM-6.7.6.3.7 explains that when an array type is written for a parameter,
    246 the parameter's type becomes a type that I summarize as being the array-decayed type.
     233\cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
     234the parameter's type becomes a type that can be summarized as the array-decayed type.
    247235The respective handling of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
    248236\lstinput{12-16}{bkgd-carray-decay.c}
    249237As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variable declaration,
    250 GCC also gives this code the warning: ```sizeof' on array function parameter `x' will return size of `float *'.''
    251 
    252 The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it's spelled:
     238GCC also gives this code the warning for the first assertion:
     239\begin{cfa}
     240warning: 'sizeof' on array function parameter 'x' will return size of 'float *'
     241\end{cfa}
     242The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it is spelled:
    253243\lstinput{18-21}{bkgd-carray-decay.c}
    254244This fragment gives no warnings.
    … …  
    266256depending on whether the object is a local variable or a parameter.
    267257
    268 
    269258In summary, when a function is written with an array-typed parameter,
    270259\begin{itemize}
    … …  
    277266As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does:
    278267\lstinput{32-42}{bkgd-carray-decay.c}
    279 
    280 \VRef[Figure]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.
    281 
    282 \begin{figure}
     268\VRef[Table]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.
     269
     270\begin{table}
     271\caption{Syntactic Reference for Decay during Parameter-Passing.
     272Includes interaction with \lstinline{const}ness, where ``immutable'' refers to a restriction on the callee's ability.}
     273\label{bkgd:ar:usr:decay-parm}
    283274\centering
    284275\begin{tabular}{llllll}
    285         & Description & Type & Param. Decl & \CFA-C  \\ \hline
    286         $\triangleright$ & ptr.\ to val.
    287             & @T *@
    288             & \pbox{20cm}{ \vspace{2pt} \lstinline{T * x,} \\ \lstinline{T x[10],} \\ \lstinline{T x[],}   }\vspace{2pt}
    289             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * T ]} \\ \lstinline{[ [10] T ]} \\ \lstinline{[ [] T  ]}   }
    290             \\ \hline
    291         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
    292             & @T * const@
    293             & \pbox{20cm}{ \vspace{2pt} \lstinline{T * const x,} \\ \lstinline{T x[const 10],} \\ \lstinline{T x[const],}   }\vspace{2pt}
    294             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ const * T ]} \\ \lstinline{[ [const 10] T ]} \\ \lstinline{[ [const] T  ]}   }
    295             \\ \hline
    296         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}}   }\vspace{2pt}
    297             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *}   }
    298             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x,} \\ \lstinline{T const * x,} \\ \lstinline{const T x[10],} \\ \lstinline{T const x[10],} \\ \lstinline{const T x[],} \\ \lstinline{T const x[],}   }\vspace{2pt}
    299             & \pbox{20cm}{ \vspace{2pt} \lstinline{[* const T]} \\ \lstinline{[ [10] const T ]} \\ \lstinline{[ [] const T  ]}   }
    300             \\ \hline \hline
    301         $\triangleright$ & ptr.\ to ar.\ of val.
    302             & @T(*)[10]@
    303             & \pbox{20cm}{ \vspace{2pt} \lstinline{T (*x)[10],} \\ \lstinline{T x[3][10],} \\ \lstinline{T x[][10],}   }\vspace{2pt}
    304             & \pbox{20cm}{ \vspace{2pt} \lstinline{[* [10] T]} \\ \lstinline{[ [3] [10] T ]} \\ \lstinline{[ [] [10] T  ]}   }
    305             \\ \hline
    306         & ptr.\ to ptr.\ to val.
    307             & @T **@
    308             & \pbox{20cm}{ \vspace{2pt} \lstinline{T ** x,} \\ \lstinline{T *x[10],} \\ \lstinline{T *x[],}   }\vspace{2pt}
    309             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * * T ]} \\ \lstinline{[ [10] * T ]} \\ \lstinline{[ [] * T  ]}   }
    310             \\ \hline
    311         & \pbox{20cm}{ \vspace{2pt} ptr.\ to ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{**argv}}   }\vspace{2pt}
    312             & @const char **@
    313             & \pbox{20cm}{ \vspace{2pt} \lstinline{const char *argv[],} \\ \footnotesize{(others elided)}   }\vspace{2pt}
    314             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ [] * const char ]} \\ \footnotesize{(others elided)}   }
    315             \\ \hline
     276        & Description & Type & Parameter Declaration & \CFA  \\
     277        \hline
     278        & & & @T * x,@ & @* T x,@ \\
     279$\triangleright$ & pointer to value & @T *@ & @T x[10],@ & @[10] T x,@ \\
     280        & & & @T x[],@ & @[] T x,@ \\
     281        \hline
     282        & & & @T * const x,@ & @const * T x@ \\
     283        & immutable ptr.\ to val. & @T * const@ & @T x[const 10],@ & @[const 10] T x,@ \\
     284        & & & @T x[const],@ & @[const] T x,@\\
     285        \hline
     286        & & & @const T * x,@ & @ * const T x,@ \\
     287        & &     & @T const * x,@ & @ * T const x,@ \\
     288        & ptr.\ to immutable val. & @const T *@ & @const T x[10],@ & @[10] const T x,@ \\
     289        & & @T const *@ & @T const x[10],@ &  @[10] T const x,@ \\
     290        & & & @const T x[],@ & @[] const T x,@ \\
     291        & & & @T const x[],@ & @[] T const x,@ \\
     292        \hline \hline
     293        & & & @T (*x)[10],@ & @* [10] T x,@ \\
     294$\triangleright$ & ptr.\ to ar.\ of val. & @T(*)[10]@ & @T x[3][10],@ & @[3][10] T x,@ \\
     295        & & & @T x[][10],@ & @[][10] T x,@ \\
     296        \hline
     297        & & & @T ** x,@ & @** T x,@ \\
     298        & ptr.\ to ptr.\ to val. & @T **@ & @T * x[10],@ & @[10] * T x,@ \\
     299        & & & @T * x[],@ & @[] * T x,@ \\
     300        \hline
     301        & ptr.\ to ptr.\ to imm.\ val. & @const char **@ & @const char * argv[],@ & @[] * const char argv,@ \\
     302    & & & \emph{others elided} & \emph{others elided} \\
     303        \hline
    316304\end{tabular}
    317 \caption{Unfortunate Syntactic Reference for Decay during Parameter-Passing.  Includes interaction with constness, where ``no writing'' refers to a restriction on the callee's ability.}
    318 \label{bkgd:ar:usr:decay-parm}
    319 \end{figure}
     305\end{table}
    320306
    321307
    322308\subsection{Lengths may vary, checking does not}
    323309
    324 When the desired number of elements is unknown at compile time,
    325 a variable-length array is a solution:
    326 \begin{cfa}
    327 int main( int argc, const char *argv[] ) {
     310When the desired number of elements is unknown at compile time, a variable-length array is a solution:
     311\begin{cfa}
     312int main( int argc, const char * argv[] ) {
    328313        assert( argc == 2 );
    329314        size_t n = atol( argv[1] );
    330         assert( 0 < n && n < 1000 );
    331 
     315        assert( 0 < n );
    332316        float ar[n];
    333317        float b[10];
    334 
    335318        // ... discussion continues here
    336319}
    337320\end{cfa}
    338 This arrangement allocates @n@ elements on the @main@ stack frame for @ar@, just as it puts 10 elements on the @main@ stack frame for @b@.
    339 The variable-sized allocation of @ar@ is provided by @alloca@.
    340 
    341 In a situation where the array sizes are not known to be small enough for stack allocation to be sensible, corresponding heap allocations are achievable as:
    342 \begin{cfa}
    343 float *ax1 = malloc( sizeof( float[n] ) );
    344 float *ax2 = malloc( n * sizeof( float ) );
    345 float *bx1 = malloc( sizeof( float[1000000] ) );
    346 float *bx2 = malloc( 1000000 * sizeof( float ) );
    347 \end{cfa}
    348 
    349 
    350 VLA
     321This arrangement allocates @n@ elements on the @main@ stack frame for @ar@, called a \newterm{variable length array} (VLA), as well as 10 elements in the same stack frame for @b@.
     322The variable-sized allocation of @ar@ is provided by the @alloca@ routine, which bumps the stack pointer.
     323Note, the C standard supports VLAs, but the \CC standard does not;
     324both @gcc@ and @g++@ support VLAs.
     325As well, there is misinformation about VLAs, \eg VLAs cause stack failures or are inefficient.
     326VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.
     327
     328In situations where the stack size has a small bound (coroutines or user-level threads), unbounded VLAs can overflow the stack so a heap allocation is used.
     329\begin{cfa}
     330float * ax1 = malloc( sizeof( float[n] ) );
     331float * ax2 = malloc( n * sizeof( float ) );
     332float * bx1 = malloc( sizeof( float[1000000] ) );
     333float * bx2 = malloc( 1000000 * sizeof( float ) );
     334\end{cfa}
    351335
    352336Parameter dependency
    … …  
    357341
    358342
    359 
    360 \subsection{C has full-service, dynamically sized, multidimensional arrays (and \CC does not)}
     343\subsection{Dynamically sized, multidimensional arrays}
    361344
    362345In C and \CC, ``multidimensional array'' means ``array of arrays.''  Other meanings are discussed in TODO.

  • doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c

    r0bbe172 r0554c1a  
    44        float (*pa)[10] = &a;           $\C{// pointer to array}$
    55        float a0 = a[0];                        $\C{// element}$
    6         float *pa0 = &(a[0]);           $\C{// pointer to element}$
     6        float * pa0 = &(a[0]);          $\C{// pointer to element}$
    77
    8         float *pa0x = a;                        $\C{// (ok)}$
     8        float * pa0x = a;                       $\C{// (ok)}$
    99        assert( pa0 == pa0x );
    1010        assert( sizeof(pa0x) != sizeof(a) );
    1111
    12         void f( float x[10], float *y ) {
    13                 static_assert( sizeof(x) == sizeof(void*) );
    14                 static_assert( sizeof(y) == sizeof(void*) );
     12        void f( float x[10], float * y ) {
     13                static_assert( sizeof(x) == sizeof(void *) );
     14                static_assert( sizeof(y) == sizeof(void *) );
    1515        }
    1616        f(0,0);
    … …  
    2222
    2323        char ca[] = "hello";            $\C{// array on stack, initialized from read-only data}$
    24         char *cp = "hello";                     $\C{// pointer to read-only data [decay here]}$
    25         void edit( char c[] ) {         $\C{// param is pointer}$
     24        char * cp = "hello";            $\C{// pointer to read-only data [decay here]}$
     25        void edit( char c[] ) {         $\C{// parameter is pointer}$
    2626                c[3] = 'p';
    2727        }
    2828        edit( ca );                                     $\C{// ok [decay here]}$
    29         edit( c p );                            $\C{// Segmentation fault}$
     29        edit( cp );                                     $\C{// Segmentation fault}$
    3030        edit( "hello" );                        $\C{// Segmentation fault [decay here]}$
    3131
    3232        void decay( float x[10] ) {
    33                 static_assert( sizeof(x) == sizeof(void*) );
     33                static_assert( sizeof(x) == sizeof(void *) );
    3434        }
    3535        static_assert( sizeof(a) == 10 * sizeof(float) );
Note: See TracChangeset for help on using the changeset viewer.