Changeset b78c54f for doc/theses


Ignore:
Timestamp:
Apr 12, 2024, 7:49:21 AM (18 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
3e1cd17, 90320ac
Parents:
feb999f (diff), ab780e6 (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/theses/mike_brooks_MMath
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/background.tex

    rfeb999f rb78c54f  
    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
    … …  
    4545Hence, in all cases, @sizeof@ is informing about type information.
    4646
    47 So, thinking of an array as a pointer to its first element is too simplistic an analogue and it is not backed up the type system.
    48 This misguided analogue can be forced onto single-dimension arrays but there is no advantage other than possibly teaching beginning programmers about basic runtime array-access.
    49 
    50 Continuing, a shortened form for declaring local variables exists, provided that length information is given in the initializer:
     47So, thinking of an array as a pointer to its first element is too simplistic an analogue and it is not backed up by the type system.
     48This misguided analogue works for a single-dimension array but there is no advantage other than possibly teaching beginning programmers about basic runtime array-access.
     49
     50Continuing, a short form for declaring array variables exists using length information provided implicitly by an initializer.
    5151\lstinput{59-62}{bkgd-carray-arrty.c}
    52 In these declarations, the resulting types are both arrays, but their lengths are inferred.
    53 
    54 My contribution is enabled by recognizing
     52The compiler counts the number of initializer elements and uses this value as the first dimension.
     53Unfortunately, the implicit element counting does not extend to dimensions beyond the first.
     54\lstinput{64-67}{bkgd-carray-arrty.c}
     55
     56My contribution is recognizing:
    5557\begin{itemize}
    56         \item There is value in using a type that knows how big the whole thing is.
     58        \item There is value in using a type that knows its size.
    5759        \item The type pointer to (first) element does not.
    5860        \item C \emph{has} a type that knows the whole picture: array, e.g. @T[10]@.
    59         \item This type has all the usual derived forms, which also know the whole picture.  A usefully noteworthy example is pointer to array, e.g. @T(*)[10]@.
     61        \item This type has all the usual derived forms, which also know the whole picture.
     62        A usefully noteworthy example is pointer to array, e.g. @T (*)[10]@.\footnote{
     63        The parenthesis are necessary because subscript has higher priority than pointer in C declarations.
     64        (Subscript also has higher priority than dereference in C expressions.)}
    6065\end{itemize}
    6166
    62 Each of these sections, which introduces another layer of of the C arrays' story,
    63 concludes with an \emph{Unfortunate Syntactic Reference}.
    64 It shows how to spell the types under discussion,
    65 along with interactions with orthogonal (but easily confused) language features.
    66 Alternate spellings are listed within a row.
     67
     68\section{Reading Declarations}
     69
     70A significant area of confusion for reading C declarations results from embedding a declared variable in a declaration, mimicking the way the variable is used in executable statements.
     71\begin{cquote}
     72\begin{tabular}{@{}ll@{}}
     73\multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
     74\begin{cfa}
     75int @(*@ar@)[@5@]@; // definition
     76  ... @(*@ar@)[@3@]@ += 1; // usage
     77\end{cfa}
     78&
     79\begin{cfa}
     80int @(*@f@())[@5@]@ { ... }; // definition
     81  ... @(*@f@())[@3@]@ += 1; // usage
     82\end{cfa}
     83\end{tabular}
     84\end{cquote}
     85Essentially, the type is wrapped around the name in successive layers (like an \Index{onion}).
     86While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
     87\begin{quote}
     88In spite of its difficulties, I believe that the C's approach to declarations remains plausible, and am comfortable with it; it is a useful unifying principle.~\cite[p.~12]{Ritchie93}
     89\end{quote}
     90After 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!
     91
     92\CFA provides its own type, variable and routine declarations, using a simpler syntax.
     93The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
     94The qualifiers have the same meaning in \CFA as in C.
     95Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
     96\begin{cquote}
     97\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
     98\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{read left to right}}   \\
     99\begin{cfa}
     100int @*@ x1 @[5]@;
     101int @(*@x2@)[5]@;
     102int @(*@f( int p )@)[5]@;
     103\end{cfa}
     104&
     105\begin{cfa}
     106@[5] *@ int x1;
     107@* [5]@ int x2;
     108@[ * [5] int ]@ f( int p );
     109\end{cfa}
     110&
     111\begin{cfa}
     112// array of 5 pointers to int
     113// pointer to array of 5 int
     114// function returning pointer to array of 5 ints
     115\end{cfa}
     116\\
     117& &
     118\LstCommentStyle{//\ \ \ and taking an int argument}
     119\end{tabular}
     120\end{cquote}
     121As declaration complexity increases, it becomes corresponding difficult to read and understand the C declaration form.
     122Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations.
     123
     124\VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef{XXX}.
     125The \CFA-thesis column shows the new array declaration form, which is my contributed improvements for safety and ergonomics.
     126The table shows there are multiple yet equivalent forms for the array types under discussion, and subsequent discussion shows interactions with orthogonal (but easily confused) language features.
     127Each row of the table shows alternate syntactic forms.
    67128The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
    68 The Type column gives the spelling used in a cast or error message (though note Section TODO points out that some types cannot be casted to).
    69 The Declaration column gives the spelling used in an object declaration, such as variable or aggregate member; parameter declarations (section TODO) follow entirely different rules.
    70 
    71 After 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!
    72 
    73 
    74 \CFA-specific spellings (not yet introduced) are also included here for referenceability; these can be skipped on linear reading.
    75 The \CFA-C column gives the, more fortunate, ``new'' syntax of section TODO, for spelling \emph{exactly the same type}.
    76 This fortunate syntax does not have different spellings for types vs declarations;
    77 a declaration is always the type followed by the declared identifier name;
    78 for the example of letting @x@ be a \emph{pointer to array}, the declaration is spelled:
    79 \begin{cfa}
    80 [ * [10] T ] x;
    81 \end{cfa}
    82 The \CFA-Full column gives the spelling of a different type, introduced in TODO, which has all of my contributed improvements for safety and ergonomics.
    83 
    84 \VRef[Figure]{bkgd:ar:usr:avp} gives this reference for the discussion so far.
    85 
    86 \begin{figure}
     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)}.
     130Unfortunately, parameter declarations \PAB{(section TODO)} have more syntactic forms and rules.
     131
     132\begin{table}
    87133\centering
    88 \setlength{\tabcolsep}{3pt}
    89 \begin{tabular}{llllll}
    90         & Description & Type & Declaration & \CFA-C  & \CFA-Full \\ \hline
    91         $\triangleright$ & val.
    92             & @T@
    93             & @T x;@
    94             & @[ T ]@
    95             &
    96             \\ \hline
    97         & \pbox{20cm}{ \vspace{2pt} val.\\ \footnotesize{no writing the val.\ in \lstinline{x}}   }\vspace{2pt}
    98             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T} \\ \lstinline{T const}   }
    99             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T x;} \\ \lstinline{T const x;}   }
    100             & @[ const T ]@
    101             &
    102             \\ \hline \hline
    103         $\triangleright$ & ptr.\ to val.
    104             & @T *@
    105             & @T * x;@
    106             & @[ * T ]@
    107             &
    108             \\ \hline
    109         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
    110             & @T * const@
    111             & @T * const x;@
    112             & @[ const * T ]@
    113             &
    114             \\ \hline
    115         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}}   }\vspace{2pt}
    116             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *}   }
    117             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x;} \\ \lstinline{T const * x;}   }
    118             & @[ * const T ]@
    119             &
    120             \\ \hline \hline
    121         $\triangleright$ & ar.\ of val.
    122             & @T[10]@
    123             & @T x[10];@
    124             & @[ [10] T ]@
    125             & @[ array(T, 10) ]@
    126             \\ \hline
    127         & \pbox{20cm}{ \vspace{2pt} ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{x[5]}}   }\vspace{2pt}
    128             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T[10]} \\ \lstinline{T const[10]}   }
    129             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T x[10];} \\ \lstinline{T const x[10];}   }
    130             & @[ [10] const T ]@
    131             & @[ const array(T, 10) ]@
    132             \\ \hline
    133         & ar.\ of ptr.\ to val.
    134             & @T*[10]@
    135             & @T *x[10];@
    136             & @[ [10] * T ]@
    137             & @[ array(* T, 10) ]@
    138             \\ \hline
    139         & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x[5]}}   }\vspace{2pt}
    140             & @T * const [10]@
    141             & @T * const x[10];@
    142             & @[ [10] const * T ]@
    143             & @[ array(const * T, 10) ]@
    144             \\ \hline
    145         & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*(x[5])}}   }\vspace{2pt}
    146             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * [10]} \\ \lstinline{T const * [10]}   }
    147             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x[10];} \\ \lstinline{T const * x[10];}   }
    148             & @[ [10] * const T ]@
    149             & @[ array(* const T, 10) ]@
    150             \\ \hline \hline
    151         $\triangleright$ & ptr.\ to ar.\ of val.
    152             & @T(*)[10]@
    153             & @T (*x)[10];@
    154             & @[ * [10] T ]@
    155             & @[ * array(T, 10) ]@
    156             \\ \hline
    157         & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
    158             & @T(* const)[10]@
    159             & @T (* const x)[10];@
    160             & @[ const * [10] T ]@
    161             & @[ const * array(T, 10) ]@
    162             \\ \hline
    163         & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{(*x)[5]}}   }\vspace{2pt}
    164             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T(*)[10]} \\ \lstinline{T const (*) [10]}   }
    165             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T (*x)[10];} \\ \lstinline{T const (*x)[10];}   }
    166             & @[ * [10] const T ]@
    167             & @[ * const array(T, 10) ]@
    168             \\ \hline
    169         & ptr.\ to ar.\ of ptr.\ to val.
    170             & @T*(*)[10]@
    171             & @T *(*x)[10];@
    172             & @[ * [10] * T ]@
    173             & @[ * array(* T, 10) ]@
    174             \\ \hline
     134\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
     135\label{bkgd:ar:usr:avp}
     136\begin{tabular}{ll|l|l|l}
     137        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
     138        \hline
     139$\triangleright$ & value & @T x;@ & @T x;@ & \\
     140        \hline
     141        & immutable value & @const T x;@ & @const T x;@ & \\
     142        & & @T const x;@ & @T const x;@ & \\
     143        \hline \hline
     144$\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
     145        \hline
     146        & immutable ptr. to val. & @T * const x;@ & @const * T x;@ & \\
     147        \hline
     148        & ptr. to immutable val. & @const T * x;@ & @* const T x;@ & \\
     149        & & @T const * x;@ & @* T const x;@ & \\
     150        \hline \hline
     151$\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
     152        \hline
     153        & ar.\ of immutable val. & @const T x[10];@ & @[10] const T x@ & @const array(T, 10) x@ \\
     154    & & @T const x[10];@ & @[10] T const x@ & @array(T, 10) const x@ \\
     155        \hline
     156        & ar.\ of ptr.\ to value & @T * x[10];@ & @[10] * T x@ & @array(T *, 10) x@ \\
     157        & & & & @array(* T, 10) x@ \\
     158        \hline
     159        & ar.\ of imm. ptr.\ to val. & @T * const x[10];@ & @[10] const * T x@ & @array(* const T, 10) x@ \\
     160        & & & & @array(const * T, 10) x@ \\
     161        \hline
     162        & ar.\ of ptr.\ to imm. val. & @const T * x[10];@ & @[10] * const T x@ & @array(const T *, 10) x@ \\
     163        & & @T const * x[10];@ & @[10] * T const x@ & @array(* const T, 10) x@ \\
     164        \hline \hline
     165$\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
     166        \hline
     167        & imm. ptr.\ to ar.\ of val. & @T (* const x)[10];@ & @const * [10] T x@ & @const * array(T, 10) x@ \\
     168        \hline
     169        & ptr.\ to ar.\ of imm. val. & @const T (*x)[10];@ & @* [10] const T x@ & @* const array(T, 10) x@ \\
     170        & & @T const (*x)[10];@ & @* [10] T const x@ & @* array(T, 10) const x@ \\
     171        \hline
     172        & ptr.\ to ar.\ of ptr.\ to val. & @T *(*x)[10];@ & @* [10] * T x@ & @* array(T *, 10) x@ \\
     173        & & & & @* array(* T, 10) x@ \\
     174        \hline
    175175\end{tabular}
    176 \caption{Unfortunate Syntactic Reference for Array vs Pointer.  Includes interaction with constness.}
    177 \label{bkgd:ar:usr:avp}
    178 \end{figure}
    179 
    180 
    181 
    182 
     176\end{table}
    183177
    184178TODO: Address these parked unfortunate syntaxes
    … …  
    186180        \item static
    187181        \item star as dimension
    188         \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@
    189183\end{itemize}
    190184
    … …  
    203197\lstinput{10-10}{bkgd-carray-decay.c}
    204198
    205 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 *@.
    206200\begin{quote}
    207 Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a
    208 string literal used to initialize an array
    209 an expression that has type ``array of type'' is
    210 converted to an expression with type ``pointer to type'' that points to the initial element of
    211 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}
    212204\end{quote}
    213 
    214205This phenomenon is the famous ``pointer decay,'' which is a decay of an array-typed expression into a pointer-typed one.
    215 
    216206It is worthy to note that the list of exception cases does not feature the occurrence of @ar@ in @ar[i]@.
    217 Thus, subscripting happens on pointers, not arrays.
    218 
    219 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)))@.
    220 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.
    221 Finally, ARM-6.5.3.2.4 explains that the @*@ operator's result is the referenced element.
    222 
    223 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!
    224213
    225214Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
    … …  
    233222fs[5] = 3.14;
    234223\end{cfa}
    235 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).
    236 But program says \emph{nothing} more about this pointer value, that might cause its referent to \emph{be} an array, before doing the subscript.
    237 
    238 Under this assumption, a pointer being subscripted (or added to, then dereferenced)
    239 by any value (positive, zero, or negative), gives a view of the program's entire address space,
    240 centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks,
    241 each potentially (re)interpreted as @typeof(*p)@.
    242 
    243 I call this phenomenon ``array diffraction,''  which is a diffraction of a single-element pointer
    244 into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
    245 
     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.
    246229No pointer is exempt from array diffraction.
    247 
    248230No array shows its elements without pointer decay.
    249231
    250232A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
    251 ARM-6.7.6.3.7 explains that when an array type is written for a parameter,
    252 the parameter's type becomes a type that I summarize as being the array-decayed type.
    253 The respective handlings of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
     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.
     235The respective handling of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
    254236\lstinput{12-16}{bkgd-carray-decay.c}
    255237As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variable declaration,
    256 GCC also gives this code the warning: ```sizeof' on array function parameter `x' will return size of `float *'.''
    257 
    258 The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it's spelled:
     238@gcc@ 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:
    259243\lstinput{18-21}{bkgd-carray-decay.c}
    260244This fragment gives no warnings.
    … …  
    272256depending on whether the object is a local variable or a parameter.
    273257
    274 
    275258In summary, when a function is written with an array-typed parameter,
    276259\begin{itemize}
    … …  
    283266As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does:
    284267\lstinput{32-42}{bkgd-carray-decay.c}
    285 
    286 \VRef[Figure]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter decalarations.
    287 
    288 \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}
    289274\centering
    290275\begin{tabular}{llllll}
    291         & Description & Type & Param. Decl & \CFA-C  \\ \hline
    292         $\triangleright$ & ptr.\ to val.
    293             & @T *@
    294             & \pbox{20cm}{ \vspace{2pt} \lstinline{T * x,} \\ \lstinline{T x[10],} \\ \lstinline{T x[],}   }\vspace{2pt}
    295             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * T ]} \\ \lstinline{[ [10] T ]} \\ \lstinline{[ [] T  ]}   }
    296             \\ \hline
    297         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
    298             & @T * const@
    299             & \pbox{20cm}{ \vspace{2pt} \lstinline{T * const x,} \\ \lstinline{T x[const 10],} \\ \lstinline{T x[const],}   }\vspace{2pt}
    300             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ const * T ]} \\ \lstinline{[ [const 10] T ]} \\ \lstinline{[ [const] T  ]}   }
    301             \\ \hline
    302         & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}}   }\vspace{2pt}
    303             & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *}   }
    304             & \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}
    305             & \pbox{20cm}{ \vspace{2pt} \lstinline{[* const T]} \\ \lstinline{[ [10] const T ]} \\ \lstinline{[ [] const T  ]}   }
    306             \\ \hline \hline
    307         $\triangleright$ & ptr.\ to ar.\ of val.
    308             & @T(*)[10]@
    309             & \pbox{20cm}{ \vspace{2pt} \lstinline{T (*x)[10],} \\ \lstinline{T x[3][10],} \\ \lstinline{T x[][10],}   }\vspace{2pt}
    310             & \pbox{20cm}{ \vspace{2pt} \lstinline{[* [10] T]} \\ \lstinline{[ [3] [10] T ]} \\ \lstinline{[ [] [10] T  ]}   }
    311             \\ \hline
    312         & ptr.\ to ptr.\ to val.
    313             & @T **@
    314             & \pbox{20cm}{ \vspace{2pt} \lstinline{T ** x,} \\ \lstinline{T *x[10],} \\ \lstinline{T *x[],}   }\vspace{2pt}
    315             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * * T ]} \\ \lstinline{[ [10] * T ]} \\ \lstinline{[ [] * T  ]}   }
    316             \\ \hline
    317         & \pbox{20cm}{ \vspace{2pt} ptr.\ to ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{**argv}}   }\vspace{2pt}
    318             & @const char **@
    319             & \pbox{20cm}{ \vspace{2pt} \lstinline{const char *argv[],} \\ \footnotesize{(others elided)}   }\vspace{2pt}
    320             & \pbox{20cm}{ \vspace{2pt} \lstinline{[ [] * const char ]} \\ \footnotesize{(others elided)}   }
    321             \\ \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
    322304\end{tabular}
    323 \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.}
    324 \label{bkgd:ar:usr:decay-parm}
    325 \end{figure}
     305\end{table}
    326306
    327307
    328308\subsection{Lengths may vary, checking does not}
    329309
    330 When the desired number of elements is unknown at compile time,
    331 a variable-length array is a solution:
    332 \begin{cfa}
    333 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[] ) {
    334313        assert( argc == 2 );
    335314        size_t n = atol( argv[1] );
    336         assert( 0 < n && n < 1000 );
    337 
     315        assert( 0 < n );
    338316        float ar[n];
    339317        float b[10];
    340 
    341318        // ... discussion continues here
    342319}
    343320\end{cfa}
    344 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@.
    345 The variable-sized allocation of @ar@ is provided by @alloca@.
    346 
    347 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:
    348 \begin{cfa}
    349 float *ax1 = malloc( sizeof( float[n] ) );
    350 float *ax2 = malloc( n * sizeof( float ) );
    351 float *bx1 = malloc( sizeof( float[1000000] ) );
    352 float *bx2 = malloc( 1000000 * sizeof( float ) );
    353 \end{cfa}
    354 
    355 
    356 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~\cite[\S~6.7.6.2.4]{C11} as a conditional feature, 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
     328For high-performance applications, the stack size can be fixed and small (coroutines or user-level threads).
     329Here, VLAs can overflow the stack, so a heap allocation is used.
     330\begin{cfa}
     331float * ax1 = malloc( sizeof( float[n] ) );
     332float * ax2 = malloc( n * sizeof( float ) );
     333float * bx1 = malloc( sizeof( float[1000000] ) );
     334float * bx2 = malloc( 1000000 * sizeof( float ) );
     335\end{cfa}
    357336
    358337Parameter dependency
    … …  
    363342
    364343
    365 
    366 \subsection{C has full-service, dynamically sized, multidimensional arrays (and \CC does not)}
     344\subsection{Dynamically sized, multidimensional arrays}
    367345
    368346In C and \CC, ``multidimensional array'' means ``array of arrays.''  Other meanings are discussed in TODO.
    … …  
    416394\section{Linked List}
    417395
     396Linked-lists are blocks of storage connected using one or more pointers.
     397The storage block is logically divided into data and links (pointers), where the links are the only component used by the list structure.
     398Since the data is opaque, list structures are often polymorphic over the data, which is normally homogeneous.
     399
    418400
    419401\section{String}
     402
     403A string is a logical sequence of symbols, where the form of the symbols can vary significantly: 7/8-bit characters (ASCII/Latin-1), or 2/4/8-byte (UNICODE) characters/symbols or variable length (UTF-8/16/32) characters.
     404A string can be read left-to-right, right-to-left, top-to-bottom, and have stacked elements (Arabic).
     405
     406An integer character constant is a sequence of one or more multibyte characters enclosed in single-quotes, as in @'x'@.
     407A wide character constant is the same, except prefixed by the letter @L@, @u@, or @U@.
     408With a few exceptions detailed later, the elements of the sequence are any members of the source character set;
     409they are mapped in an implementation-defined manner to members of the execution character set.
     410
     411A C character-string literal is a sequence of zero or more multibyte characters enclosed in double-quotes, as in @"xyz"@.
     412A UTF-8 string literal is the same, except prefixed by @u8@.
     413A wide string literal is the same, except prefixed by the letter @L@, @u@, or @U@.
     414
     415For UTF-8 string literals, the array elements have type @char@, and are initialized with the characters of the multibyte character sequence, as encoded in UTF-8.
     416For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by the @mbstowcs@ function with an implementation-defined current locale.
     417For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by successive calls to the @mbrtoc16@, or @mbrtoc32@ function as appropriate for its type, with an implementation-defined current locale.
     418The value of a string literal containing a multibyte character or escape sequence not represented in the executioncharacter set is implementation-defined.
     419
     420
     421Another bad C design decision is to have null-terminated strings rather than maintaining a separate string length.
     422\begin{quote}
     423Technically, a string is an array whose elements are single characters.
     424The compiler automatically places the null character @\0@ at the end of each such string, so programs can conveniently find the end.
     425This representation means that there is no real limit to how long a string can be, but programs have to scan one completely to determine its length.
     426\end{quote}

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

    rfeb999f rb78c54f  
    5757        f( &ar );
    5858
    59         float fs[] = {3.14, 1.707};
     59        float fs[] = {3.14, 1.77};
    6060        char cs[] = "hello";
    6161        static_assert( sizeof(fs) == 2 * sizeof(float) );
    6262        static_assert( sizeof(cs) == 6 * sizeof(char) );  $\C{// 5 letters + 1 null terminator}$
    6363
     64        float fm[][2] = { {3.14, 1.77}, {12.4, 0.01}, {7.8, 1.23} };  $\C{// brackets define structuring}$
     65        char cm[][sizeof("hello")] = { "hello", "hello", "hello" };
     66        static_assert( sizeof(fm) == 3 * 2 * sizeof(float) );
     67        static_assert( sizeof(cm) == 3 * 6 * sizeof(char) );
    6468}
    6569

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

    rfeb999f rb78c54f  
    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.