Changeset 79ba50c

Timestamp:

Dec 12, 2025, 12:29:38 PM (8 weeks ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

8614140

Parents:

5e0b6657 (diff), fe6047c (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 remote-tracking branch 'refs/remotes/origin/master'

Location:

doc/theses/mike_brooks_MMath

Files:

• background.tex (modified) (40 diffs)
• intro.tex (modified) (4 diffs)
• papers/Final-ONCD-Technical-Report.pdf (added)
• programs/bkgd-c-tyerr.c (modified) (1 diff)
• programs/bkgd-carray-decay.c (modified) (2 diffs)
• programs/bkgd-carray-mdim.c (modified) (1 diff)
• programs/lst-issues-multi-static.run.c (modified) (4 diffs)
• uw-ethesis-frontpgs.tex (modified) (1 diff)
• uw-ethesis.bib (modified) (3 diffs)

doc/theses/mike_brooks_MMath/background.tex

@@ -7 +7 @@
 
 C reports many ill-typed expressions as warnings.
-For example, these attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed.
+For example, these attempts to assign @y@ to @x@ and vice-versa are ill-typed.
 \lstinput{12-15}{bkgd-c-tyerr.c}
 with warnings:
@@ -21 +21 @@
 note: expected 'void (*)(void)' but argument is of type 'float *'
 \end{cfa}
-with a segmentation fault at runtime.
 Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
 Compiling with flag @-Werror@, which turns warnings into errors, is often too pervasive, because some warnings are just warnings, \eg an unused variable.
@@ -87 +86 @@
 (\VRef{s:ArraysDecay} shows pointer decay allows the first form to be written @pa[i] += 1@, which is further syntax confusion.)
 Again, if the priorities were reversed, the expressions become more intuitive: @*pa[i] += 1@ and @*(ap[i]) += 1@.
-Note, a similar priority inversion exists between deference @*@ and field selection @.@ (period), so @*ps.f@ means @*(ps.f)@;
+Note, a similar priority inversion exists between deference '@*@' and field selection '@.@' (period), so @*ps.f@ means @*(ps.f)@;
 this anomaly is \emph{fixed} with operator @->@, which performs the two operations in the more intuitive order: @sp->f@ $\Rightarrow$ @(*sp).f@.
 \end{itemize}
@@ -128 +127 @@
 As declaration size increases, it becomes corresponding difficult to read and understand the C form, whereas reading and understanding a \CFA declaration has linear complexity.
 Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations, \eg \CC \lstinline[language=C++]{auto f( int ) -> int}.
-(Note, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.)
+However, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.
 Interestingly, programmers normally speak a declaration from left to right, regardless of how it is written.
 (It is unclear if Hebrew or Arabic speakers, say declarations right to left.)
 
-\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[Chapter]{c:Array}.
+Specifically, \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[Chapter]{c:Array}.
 The \CFA-thesis column shows the new array declaration form, which is my contribution to safety and ergonomics.
 The 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.
@@ -138 +137 @@
 The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
 Removing the declared variable @x@, gives the type used for variable, structure field, cast, or error messages.
-Unfortunately, parameter declarations have more syntactic forms and rules.
+Unfortunately, parameter declarations have more syntactic forms and rules \see{Section~\ref{s:ArraysDecay}~\VPageref{p:ParameterDeclarations}}.
 
 \begin{table}
@@ -144 +143 @@
 \caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
 \label{bkgd:ar:usr:avp}
-\begin{tabular}{ll|l|l|l}
+\setlength{\tabcolsep}{12pt}
+\begin{tabular}{@{}ll|l|l|l@{}}
         & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
         \hline
@@ -253 +253 @@
 Using the type form yields the same results as the prior expression form.
 \lstinput{46-49}{bkgd-carray-arrty.c}
-The results are also the same when there is no allocation at all.
+The results are also the same when there is no allocation at all, \eg a parameter declaration.
 This time, starting from a pointer-to-array type:
 \lstinput{51-57}{bkgd-carray-arrty.c}
@@ -297 +297 @@
 ``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
 \end{quote}
-This phenomenon is the famous \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
+This phenomenon is the famous (infamous) \newterm{pointer decay}, which is a decay of an array-typed expression into a pointer-typed one.
 It is worthy to note that the list of exceptional cases does not feature the occurrence of @ar@ in @ar[i]@.
 Thus, subscripting happens on pointers not arrays.
@@ -305 +305 @@
 \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.
 Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
-Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
+Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing, as plus is commutative.
 
 Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
@@ -318 +318 @@
 But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.
 
-Under 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)@.
-I call this phenomenon \emph{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.
+Under this assumption, a pointer, @p@, 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 @p@'s address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p).t@.
+I call this phenomenon \emph{array diffraction}, which is a diffraction of a single-element pointer into the assumption that its target is conceptually in the middle of an array whose size is unlimited in both directions.
 No pointer is exempt from array diffraction.
 No array shows its elements without pointer decay.
 
+\label{p:ParameterDeclarations}
 A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
 \cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
@@ -379 +380 @@
 \label{bkgd:ar:usr:decay-parm}
 \centering
-\begin{tabular}{llllll}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{@{}llllll@{}}
         & Description & Type & Parameter Declaration & \CFA  \\
         \hline
@@ -426 +428 @@
 Unfortunately, there is significant misinformation about VLAs, \eg the stack size is limited (small), or VLAs cause stack failures or are inefficient.
 VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.
+Most shells limit the maximum stack size to guard against infinite recursion, but the stack size can be set to unlimited, just like the heap.
 For types with a dynamic-fixed stack, \eg coroutines or user-level threads, large VLAs can overflow the stack without appropriately sizing the stack, so heap allocation is used when the array size is unbounded.
 
@@ -436 +439 @@
 When working with arrays, \eg linear algebra, array dimensions are referred to as \emph{rows} and \emph{columns} for a matrix, adding \emph{planes} for a cube.
 (There is little terminology for higher dimensional arrays.)
-For example, an acrostic poem\footnote{A type of poetry where the first, last or other letters in a line spell out a particular word or phrase in a vertical column.}
+For example, an acrostic poem\footnote{A kind of poetry where the first, last or other letters in a line spell out a word or phrase in a vertical column.}
 can be treated as a grid of characters, where the rows are the text and the columns are the embedded keyword(s).
 Within a poem, there is the concept of a \newterm{slice}, \eg a row is a slice for the poem text, a column is a slice for a keyword.
@@ -510 +513 @@
 For example, an array-of-array may be an array of row pointers to arrays of columns, so the rows may not be contiguous in memory nor even the same length (triangular matrix).
 Regardless, there is usually a uniform subscripting syntax masking the memory layout, even though a language could differentiated between the two forms using subscript syntax, \eg @m[1,2]@ \vs @aa[1][2]@.
-Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (caching/NUMA effects).
-
-C also provides non-contiguous arrays-of-arrays.
+Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (\eg caching/NUMA effects).
+C also provides non-contiguous arrays-of-arrays:
 \begin{cfa}
 int m[5][5];                                                    $\C{// contiguous}$
 int * aa[5];                                                    $\C{// non-contiguous}$
 \end{cfa}
-both with different memory layout using the same subscripting, and both with different degrees of issues.
+both with different memory layout using the same subscripting and different degrees of issues.
+
 The focus of this work is on the contiguous multidimensional arrays in C.
 The reason is that programmers are often forced to use the more complex array-of-array form when a contiguous array would be simpler, faster, and safer.
@@ -524 +527 @@
 \VRef[Figure]{f:ContiguousNon-contiguous} shows a powerful extension made in C99 for manipulating contiguous \vs non-contiguous arrays.\footnote{C90 also supported non-contiguous arrays.}
 For contiguous-array arguments (including VLA), C99 conjoins one or more of the parameters as a downstream dimension(s), \eg @cols@, implicitly using this parameter to compute the row stride of @m@.
-There is now sufficient information to support array copying and subscript checking along the columns to prevent changing the argument or buffer-overflow problems, but neither feature is provided.
+There is now sufficient information to support array copying and subscript checking along the columns to prevent changing the argument or buffer-overflow problems, \emph{but neither feature is provided}.
 If the declaration of @fc@ is changed to:
 \begin{cfa}
@@ -532 +535 @@
 While this contiguous-array capability is a step forward, it is still the programmer's responsibility to manually manage the number of dimensions and their sizes, both at the function definition and call sites.
 That is, the array does not automatically carry its structure and sizes for use in computing subscripts.
-While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row correctly with a correctly bounded loop index.
+While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row with a correctly bounded loop index.
 Specifically, there is no requirement that the rows are the same length, like a poem with different length lines.
 
@@ -583 +586 @@
 Again, an array and a point to each of its axes are different.
 \lstinput{28-36}{bkgd-carray-mdim.c}
-As well, there is pointer decay from each of the matrix axes to pointers, which all have the same address.
+As well, there is pointer decay from each of the matrix axes to pointers, all having the same address.
 \lstinput{38-44}{bkgd-carray-mdim.c}
-Finally, subscripting on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
+Finally, subscripting is allowed on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
 
 
@@ -605 +608 @@
 // caller's perspectives of foo and bar
 \end{cfa}
-From the caller's perspective, the parameter names (by virtue of being optional) are (useful) comments;
-From the callee's perspective, parameter names are semantically significant.
+From the caller's perspective, the parameter names are semantically optional, but provide useful comments.
+From the callee's perspective, parameter names are semantically essential.
 Array parameters introduce a further, subtle, semantic difference and considerable freedom to comment.
 
-At the semantic level, there is no such thing as an array parameter, except for one case (@T [static 5]@) discussed shortly.
-Rather, there are only pointer parameters.
+At the semantic level, there is no such thing as an array parameter, except for one case, @T [static 5]@, discussed shortly.
+Instead, there are only pointer parameters.
 This fact probably shares considerable responsibility for the common sense of \emph{an array is just a pointer}, which has been refuted in non-parameter contexts.
 This fact holds in both the caller's and callee's perspectives.
-However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
-This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's \vs callee's perspectives.
+However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@), which is a pointer type.
+This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's and callee's perspectives.
 In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
 
-\PAB{TODO: add examples of mycode/arrr/bugs/c-dependent/x.cfa:v5102,5103,
-which are shocking how much C ignores.}
+C ignores length information given in parameter declarations entirely, when determining a function's type.
+For example, it accepts this pair of declarations
+\begin{cfa}
+    void f( int, float[][42] );  $\C{// array of len-42 arrays}$
+    void f( int n, float[][n]  );   $\C{// array of VLAs}$
+\end{cfa}
+as a repeat, without an error about conflicting types for @f@.
+Yet, entirely different stride calculations would occur in a function body whose parameters were declared in each of the two styles.
 
 \begin{figure}
+\setlength{\tabcolsep}{7pt}
 \begin{tabular}{@{}llll@{}}
 \begin{cfa}
@@ -663 +673 @@
 Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
 An array parameter declaration can specify the outermost dimension with a dimension value, @[10]@ (which is ignored), an empty dimension list, @[ ]@, or a pointer, @*@, as seen in \VRef[Figure]{f:ArParmEquivDecl}.
-The rationale for rejecting the first invalid row follows shortly, while the second invalid row is simple nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
-Note, in the leftmost style, the typechecker ignores the actual value even in a dynamic expression.
+The rationale for rejecting the first invalid row follows shortly, while the second invalid row is nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
+Note, in the leftmost style, the typechecker ignores the actual value, even for a dynamic expression.
 \begin{cfa}
 int N;
@@ -674 +684 @@
 % So are @float[5]*@, @float[]*@ and @float (*)*@.  These latter ones are simply nonsense, though they hint at ``1d array of pointers'', whose equivalent syntax options are, @float *[5]@, @float *[]@, and @float **@.
 
-It is a matter of taste as to whether a programmer should use a form as far left as possible (getting the most out of possible subscripting and dimension sizes), sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript'').
+It is a matter of taste as to whether a programmer should use the left form to get the most out of commenting subscripting and dimension sizes, sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript'').
 
 Note that this equivalence of pointer and array declarations is special to parameters.
@@ -680 +690 @@
 \begin{cfa}
 void f( float * a ) {
-        float * b = a; // ok
-        float c[] = a; // reject
-        float d[] = { 1.0, 2.0, 3.0 }; // ok
+        float * b = a;           // ok
+        float c[] = a;           // reject
+        float d[] = { 1.0, 2.0, 3.0 };  // ok
         static_assert( sizeof(b) == sizeof(float*) );
         static_assert( sizeof(d) != sizeof(float*) );
 }
 \end{cfa}
-Unfortunately, this equivalence has the consequence that the type system does not help a caller get it right.
+The consequence of this equivalence is that the type system does not help a caller get it right.
 \begin{cfa}
 float sum( float v[] );
@@ -715 +725 @@
 void foo( int [static @3@] );
 int ar[@10@];
-foo( ar ); // check argument dimension 10 > 3
+foo( ar );              // check argument dimension 10 > 3
 \end{cfa}
 Here, the @static@ storage qualifier defines the minimum array size for its argument.
@@ -728 +738 @@
 
 With multidimensional arrays, on dimensions after the first, a size is required and, is not ignored.
-These sizes are required for the callee to be able to subscript.
+These sizes (strides) are required for the callee to be able to subscript.
 \begin{cfa}
 void f( float a[][10], float b[][100] ) {
@@ -739 +749 @@
 The significance of an inner dimension's length is a fact of the callee's perspective.
 In the caller's perspective, the type system is quite lax.
-Here, there is (some, but) little checking that what is being passed, matches.
+Here, there is (some, but) little checking of what is being passed matches the parameter.
 % void f( float [][10] );
 % int n = 100;
@@ -774 +784 @@
 void foo( float a[][10] ) { ... }                               $\C{// definition}$
 \end{cfa}
-Repeating it with the full context of a VLA is useful:
+Repeating it with the full context of a VLA is useful.
 \begin{cfa}
 void foo( int, float [][@*@] );                                 $\C{// declaration}$ 
@@ -794 +804 @@
 typedef long int jmp_buf[8];
 \end{cfa}
-A instance of this array can be declared as a structure field.
+An instance of this array can be declared as a structure field.
 \begin{cfa}
 struct Jmp_Buf {
@@ -819 +829 @@
 Since the data is opaque, list structures are often polymorphic over the data, which is often homogeneous.
 
-The links organize nodes into a particular format, \eg queue, tree, hash table, \etc, with operations specific to that format.
+The links organize nodes into a particular kind of data structure, \eg queue, tree, hash table, \etc, with operations specific to that kind.
 Because a node's existence is independent of the data structure that organizes it, all nodes are manipulated by address not value;
 hence, all data structure routines take and return pointers to nodes and not the nodes themselves.
@@ -828 +838 @@
 
 This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
-Within this restricted space, all design-issue discussions assume the following invariants;
-alternatives to the assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
+Within this restricted space, all design-issue discussions assume the following invariants.
 \begin{itemize}
         \item A doubly-linked list is being designed.
@@ -835 +844 @@
                 Circular \vs ordered linking is discussed under List identity (\VRef{toc:lst:issue:ident}).
         \item Link fields are system-managed.
+                The system has freedom over how to represent these links.
                 The user works with the system-provided API to query and modify list membership.
-                The system has freedom over how to represent these links.
         \item The user data must provide storage for the list link-fields.
                 Hence, a list node is \emph{statically} defined as data and links \vs a node that is \emph{dynamically} constructed from data and links \see{\VRef{toc:lst:issue:attach}}.
 \end{itemize}
+Alternatives to these assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
 
 
@@ -845 +855 @@
 \label{s:PreexistingLinked-ListLibraries}
 
-Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
-and further libraries are introduced as needed.
+To show examples of the concepts being defined, two preexisting linked-list libraries are used throughout and further libraries are introduced as needed.
 \begin{enumerate}
         \item Linux Queue library~\cite{lst:linuxq} (LQ) of @<sys/queue.h>@.
@@ -852 +861 @@
 \end{enumerate}
 %A general comparison of libraries' abilities is given under Related Work (\VRef{toc:lst:relwork}).
-For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
-As well, the list library is helping the user manage (organize) requests, \eg a request can be work on the level of handling a network arrival-event or scheduling a thread.
+For the discussion, assume the type @req@ (request) is the user's payload in examples.
+Then the job of a list library is to help a user manage (organize) requests, \eg a request can be a network arrival-event processed by a web browser or a thread blocked/scheduled by the runtime.
 
 
@@ -866 +875 @@
 The wrapped style distinguishes between wrapping a reference and wrapping a value, \eg @list<req *>@ or @list<req>@.
 (For this discussion, @list<req &>@ is similar to @list<req *>@.)
-This difference is one of user style, not framework capability.
+This difference is one of user style and performance (copying), not framework capability.
 Library LQ is intrusive; STL is wrapped with reference and value.
 
@@ -973 +982 @@
 An example of an attribute on the link fields is cache alignment, possibly in conjunction with other @req@ fields, improving locality and/or avoiding false sharing.
 For example, if a list is frequently traversed in the forward direction, and infrequently gets elements removed at random positions, then an ideal layout for cache locality puts the forward links, together with frequently-used payload data on one cache line, leaving the reverse links on a colder cache line.
-Supplying the link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes.
+In contrast, supplying link fields by inheritance makes them implicit and relies on compiler placement, such as the start or end of @req@, and no explicit attributes.
 Wrapped reference has no control over the link fields, but the separate data allows some control;
 wrapped value has no control over data or links.
 
 Another subtle advantage of intrusive arrangement is that a reference to a user-level item (@req@) is sufficient to navigate or manage the item's membership.
-In LQ, the intrusive @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
+In LQ, the intrusive @req@ pointer is the correct argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
 there is no distinguishing a @req@ from a @req@ in a list.
 The same is not true of STL, wrapped reference or value.
@@ -989 +998 @@
 Then, a novel use can put a @req@ in a list, without requiring any upstream change in the @req@ library.
 In intrusive, the ability to be listed must be planned during the definition of @req@.
+Optimistically adding a couple links for future use is normally cheap because links are small and memory is big.
 
 \begin{figure}
@@ -1014 +1024 @@
 An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
 A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
-\CFA is capable of supporting a wrapped library, if need arose.
+Like LQ, \CFA is capable of supporting a wrapped library, if need arose.
 
 
@@ -1145 +1155 @@
 \subsection{User Integration: Preprocessed \vs Type-System Mediated}
 
-While the syntax for LQ is reasonably succinct, it comes at the cost of using C preprocessor macros for generics, which are not part of the language type-system, like \CC templates.
+While the syntax for LQ is reasonably succinct, it comes at the cost of using C preprocessor macros for generics, which are not part of the language type-system, unlike \CC templates.
 Hence, small errors in macro arguments can lead to large substitution mistakes, as the arguments maybe textually written in many places and/or concatenated with other arguments/text to create new names and expressions.
-This can lead to a cascade of error messages that are confusing and difficult to debug.
-For example, argument errors like @a.b,c@, comma instead of period, or @by-pri@, minus instead of underscore, can produce many error messages.
-
-Instead, language function calls (even with inlining) handled argument mistakes locally at the call, giving very specific error message.
-\CC @concepts@ were introduced in @templates@ to deal with just this problem.
+Hence, textual expansion can lead to a cascade of error messages that are confusing and difficult to debug.
+For example, argument errors like @a.b@{\Large\color{red},}@c@, comma instead of period, or @by@{\Large\color{red}-}@pri@, minus instead of underscore, can produce many error messages.
+Note, similar problems exist for \CC templates.
+
+Instead, language function calls (even with inlining) handle argument mistakes locally at the call, giving very specific error message.
+\CC @concepts@ were introduced in @templates@ to deal with this problem.
 
 % example of poor error message due to LQ's preprocessed integration
@@ -1166 +1177 @@
 All examples so far use two distinct types for:
 an item found in a list (type @req@ of variable @r1@, see \VRef[Figure]{fig:lst-issues-attach}), and the list (type @reql@ of variable @reqs_pri@, see \VRef[Figure]{fig:lst-issues-ident}).
-This kind of list is ``headed'', where the empty list is just a head.
-An alternate ``ad-hoc'' approach omits the header, where the empty list is no nodes.
+This kind of list is \newterm{headed}, where the empty list is just a head.
+An alternate ad-hoc approach omits the header, where the empty list is no nodes.
 Here, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
 Note, a headed list is superset of an ad-hoc list, and can normally perform all of the ad-hoc operations.
@@ -1202 +1213 @@
 Note, a list does not need to use links to denote its size;
 it can use a node counter in the header, where $N$ node traversals indicates complete navigation of the list.
-However, managing the number of nodes is an additional cost, as the links must always be managed.
+However, managing the number of nodes is an additional cost, whereas the links must always be managed.
 
 The following discussion refers to the LQ representations, detailed in \VRef[Figure]{fig:lst-issues-end}, using a null pointer to mark end points.
@@ -1251 +1262 @@
 
 A C character constant is an ASCII/Latin-1 character enclosed in single-quotes, \eg @'x'@, @'@\textsterling@'@.
-A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @\u@ identifies a universal character name.
-A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@ form feed, a delimiter character @'\''@ embedded single quote, or a raw character @'\xa3'@ \textsterling.
+A wide C character constant is the same, except prefixed by the letter @L@, @u@, or @U@, \eg @u'\u25A0'@ (black square), where the @'\u'@ identifies a universal character name.
+A character can be formed from an escape sequence, which expresses a non-typable character @'\f'@, form feed, a delimiter character @'\''@, embedded single quote, or a raw character @'\xa3'@, \textsterling.
 
 A C character string is zero or more regular, wide, or escape characters enclosed in double-quotes @"xyz\n"@.
-The kind of characters in the string is denoted by a prefix: UTF-8 characters are prefixed by @u8@, wide characters are prefixed by @L@, @u@, or @U@.
-
-For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabic Y-Cree OO).
+The kind of characters in the string is denoted by a prefix: wide characters are prefixed by @L@, @u@, or @U@; UTF-8 characters are prefixed by @u8@.
+
 For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the wide characters corresponding to the multi-byte character sequence, \eg @L"abc@$\mu$@"@ and are read/printed using @wscanf@/@wprintf@.
-The value of a wide-character is implementation-defined, usually a UTF-16 character.
+The value of a wide-character is implementation defined, usually a UTF-16 character.
 For 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 wide characters corresponding to the multi-byte character sequence, \eg @u"abc@$\mu$@"@, @U"abc@$\mu$@"@.
 The value of a @"u"@ character is an UTF-16 character;
 the value of a @"U"@ character is an UTF-32 character.
-The value of a string literal containing a multi-byte character or escape sequence not represented in the execution character set is implementation-defined.
+The value of a string literal containing a multi-byte character or escape sequence not represented in the execution character set is implementation defined.
+For UTF-8 string literals, the array elements have type @char@ and are initialized with the characters of the multi-byte character sequences, \eg @u8"\xe1\x90\x87"@ (Canadian syllabic Y-Cree OO).
 
 C strings are null-terminated rather than maintaining a separate string length.
@@ -1273 +1284 @@
 This property is only preserved by the compiler with respect to character constants, \eg @"abc"@ is actually @"abc\0"@, \ie 4 characters rather than 3.
 Otherwise, the compiler does not participate, making string operations both unsafe and inefficient.
-For example, it is common in C to: forget that a character constant is larger than it appears during manipulation, that extra storage is needed in a character array for the terminator, or that the terminator must be preserved during string operations, otherwise there are array overruns.
+For example, it is common in C to:
+\begin{itemize}
+\item
+forget that a character constant is larger than it appears during manipulation,
+\item
+that extra storage is needed in a character array for the terminator,
+\item
+or that the terminator must be preserved during string operations, otherwise there are array overruns.
+\end{itemize}
 Finally, the need to repeatedly scan an entire string to determine its length can result in significant cost, as it is impossible to cache the length in many cases, \eg when a string is passed into another function.
 

doc/theses/mike_brooks_MMath/intro.tex

@@ -1 +1 @@
 \chapter{Introduction}
 
-All modern programming languages provide three high-level containers (collections): array, linked-list, and string.
-Often array is part of the programming language, while linked-lists are built from (recursive) pointer types, and strings from a combination of array and linked-list.
-For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
+All modern programming languages provide at least these three high-level containers (collections): array, linked-list, and string.
+Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
+For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
 
-Unfortunately, these three aspects of C cause a significant number of memory errors~\cite{Oorschot23}.
+Unfortunately, memory misuse under C-idiomatic programming causes a significant number of errors~\cite{Oorschot23}.
 Estimates suggest 50\%~\cite{Mendio24} of total reported open-source vulnerabilities occurring in C result from errors using these facilities (memory errors).
 For operating system and browser vendors, who heavily use systems languages, 60\%--70\% of reported software vulnerabilities involved memory errors~\cite{Kehrer23}.
 For Microsoft, 70\% of vulnerabilities addressed via security updates between 2006--2018 are memory safety issues~\cite[slide 10]{Miller19}.
-In a study of software exploits in the U.S. National Vulnerability Database over 2013--2017, the top reported vulnerability is (memory) buffer errors, among 19 vulnerability categories~\cite{Cifuentes19}.
-Therefore, hardening these three C types goes a long way to make the majority of C programs safer and eliminating major hacker attack-vectors.
+In a study of software exploits in the U.S. National Vulnerability Database over 2013--2017, the top reported vulnerability is buffer errors (in the sense of misused array bounds), among 19 vulnerability categories~\cite{Cifuentes19}.
 
-This work looks at extending these three foundational container types in the programming language \CFA, which is a new dialect of the C programming language.
+While these figures address memory errors, defined without limit to the three primary collections, these authors' explanations of memory errors, among other C analysis efforts, suggest improving on C's language/library options for working with these three collections would be widely beneficial.
+Every one of the safety-statistic sources above includes array bounds in its first characterization of unsafe programming-language features.
+Of the four studies that deal exclusively with memory safety (excluding~\cite{Cifuentes19}), all put @malloc@--@free@ upfront as well.
+The one that specifically surveys C features, \cite{Oorschot23}, also has similarly prominent blame on both of: the null-terminated text idiom, with its support/mandate in the C standard library; the unprotected nature of C pointers.
+An effort at translating C to safe Rust~\cite{Emre2022} has pointers as the stand-out difficult aspect to analyze.\footnote{
+        \cite{Emre2022} demonstrates the difficulty of analyzing C pointers for safety (while tacking some of this difficult problem).
+        It first puts a corpus of C programs through a naive Rust translation, which ``succeeds'' by leaving many uses of Rust's \lstinline{unsafe} marker.
+        Then, it analyzes these uses and presents a technique for reducing those uses that hinge exclusively on referenced object lifetime.
+        Pointer dereference accounts for 80\% of the cases that the naive translation did not make safe (Table 3.2, p33).
+        Of these, 10\% are eligible for the work's own safety improvement technique, while this filtering leaves 75\% with no single cause of unsafety determined (Table 3.5, p39).
+        The presented technique succeeds at making 75\% of the eligible initially unsafe dereferences safe, by inferring the necessary lifetime annotations (Table 4.2, p83).
+        This result leaves, per 1000 LOC, 3.3 unremovable unsafe dereferences that are understood to evade lifetime analysis, among 220 gross unsafe dereferences (Tables 3.5, 4.2 and 3.1, p27).
+        % 3.3 = 1398/413,428 * 1000
+        % 220 ~= (99,101 [@tab3.5] - 9631 [@tab4.2] ) / 413,428 [@tab 3.1] * 1000
+}
+A tool for analyzing C code's use of linked data structures (including, \eg skip list and binary tree) found variations of the linked-list shape to be present in most of the programs in its corpus~\cite{White2016}.
+So, C's array unsafety is infamous, its string pattern necessitates explicit storage management (also infamous), and user-written linked lists are an attrictively recognizable player in the arena of (infamously) unsafe raw pointer uses.
+Therefore, hardening the three primary collections goes a long way to making the majority of C programs safer, and eliminating major hacker attack vectors.
+
+This work looks at extending these foundational container types in the programming language \CFA, which is a new dialect of the C programming language.
 A primary goal of \CFA~\cite{Cforall} is 99\% backward compatibility with C, while maintaining a look and feel that matches with C programmer experience and intuition.
 This goal requires ``thinking inside the box'' to engineer new features that ``work and play'' with C and its massive legacy code-base.
@@ -30 +48 @@
 
 C provides a simple array type as a language feature.
-However, it adopts the controversial position of treating pointer and array as duals, leading to multiple problems.
+However, it adopts the controversial position of treating pointer and array as twins, leading to multiple problems.
+The way that arrays are typicaly passed around a program removes the information necessary to do bound checks.
 
 
@@ -41 +60 @@
 otherwise, elements are heap allocated with internal or external link fields.
 
-C provides a few simple, polymorphic, library data-structures (@glibc@):
+C provides a few simple, library data-structures (@glibc@):
 \begin{itemize}
 \item
@@ -48 +67 @@
 hash search table consisting of a key (string) with associated data (@<search.h>@)
 \end{itemize}
-Because these container libraries can be restrictive, awkward to use, and unsafe, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
+Because these container libraries can be restrictive or awkward to use, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
 
 

doc/theses/mike_brooks_MMath/programs/bkgd-c-tyerr.c

@@ -16 +16 @@
 
         float pi = 3.14;
-        void f( void (*g)(void) ) { g(); }
+        void f( void (*g)(void) );
         @f( &pi );@                     $\C{// wrong}$
 }

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

@@ -10 +10 @@
         assert( sizeof(pa0x) != sizeof(ar) );
 
-        void f( float x[10], float * y ) {
+        void f( @float x[10]@, @float * y@ ) {
                 static_assert( sizeof(x) == sizeof(void *) );
                 static_assert( sizeof(y) == sizeof(void *) );
@@ -16 +16 @@
         f( 0, 0 );
 
-        // reusing local var `float a[10];`}
+        // reusing local variable float ar[10]
         float v;
         f( ar, ar );                            $\C{// ok: two decays, one into an array spelling}$

doc/theses/mike_brooks_MMath/programs/bkgd-carray-mdim.c

@@ -38 +38 @@
 //      float (*b[3])[10];
         float * b[3];
-        for (int i = 0; i < 3; i ++) {
-                b[i] = malloc(sizeof(float[10]));
+        for ( int i = 0; i < 3; i ++ ) {
+                b[i] = malloc( sizeof( float[10] ) );
         }
         mx[2][3];

doc/theses/mike_brooks_MMath/programs/lst-issues-multi-static.run.c

@@ -20 +20 @@
 struct req {
         int pri, rqr;
-        LIST_ENTRY(req) by_pri;
-        LIST_ENTRY(req) by_rqr;
+        LIST_ENTRY( req ) by_pri;
+        LIST_ENTRY( req ) by_rqr;
 };
 
-LIST_HEAD(reql, req);
+LIST_HEAD( reql, req );
 
 struct reql reqs_pri;
@@ -31 +31 @@
 struct reql reqs_rqr_99;
 
-LIST_INIT(&reqs_pri);
-LIST_INIT(&reqs_rqr_42);
-LIST_INIT(&reqs_rqr_17);
-LIST_INIT(&reqs_rqr_99);
+LIST_INIT( &reqs_pri );
+LIST_INIT( &reqs_rqr_42 );
+LIST_INIT( &reqs_rqr_17 );
+LIST_INIT( &reqs_rqr_99 );
 
 struct req
@@ -44 +44 @@
         r99a = {3, 99};
 
-LIST_INSERT_HEAD(&reqs_pri, &r17c, by_pri);
-LIST_INSERT_HEAD(&reqs_pri, &r99a, by_pri);
-LIST_INSERT_HEAD(&reqs_pri, &r17b, by_pri);
-LIST_INSERT_HEAD(&reqs_pri, &r42b, by_pri);
-LIST_INSERT_HEAD(&reqs_pri, &r17a, by_pri);
-LIST_INSERT_HEAD(&reqs_pri, &r42a, by_pri);
+LIST_INSERT_HEAD( &reqs_pri, &r17c, by_pri );
+LIST_INSERT_HEAD( &reqs_pri, &r99a, by_pri );
+LIST_INSERT_HEAD( &reqs_pri, &r17b, by_pri );
+LIST_INSERT_HEAD( &reqs_pri, &r42b, by_pri );
+LIST_INSERT_HEAD( &reqs_pri, &r17a, by_pri );
+LIST_INSERT_HEAD( &reqs_pri, &r42a, by_pri );
 
-LIST_INSERT_HEAD(&reqs_rqr_42, &r42b, by_rqr);
-LIST_INSERT_HEAD(&reqs_rqr_42, &r42a, by_rqr);
+LIST_INSERT_HEAD( &reqs_rqr_42, &r42b, by_rqr );
+LIST_INSERT_HEAD( &reqs_rqr_42, &r42a, by_rqr );
 
-LIST_INSERT_HEAD(&reqs_rqr_17, &r17c, by_rqr);
-LIST_INSERT_HEAD(&reqs_rqr_17, &r17b, by_rqr);
-LIST_INSERT_HEAD(&reqs_rqr_17, &r17a, by_rqr);
+LIST_INSERT_HEAD( &reqs_rqr_17, &r17c, by_rqr );
+LIST_INSERT_HEAD( &reqs_rqr_17, &r17b, by_rqr );
+LIST_INSERT_HEAD( &reqs_rqr_17, &r17a, by_rqr );
 
-LIST_INSERT_HEAD(&reqs_rqr_99, &r99a, by_rqr);
+LIST_INSERT_HEAD( &reqs_rqr_99, &r99a, by_rqr );
 
 
@@ -67 +67 @@
 
 struct req *cur;
-LIST_FOREACH(cur, &reqs_pri, by_pri)
-        printf("{%d %d} ", cur->pri, cur->rqr);
-printf("| ");
-LIST_FOREACH(cur, &reqs_rqr_42, by_rqr)
-        printf("{%d %d} ", cur->pri, cur->rqr);
-printf("| ");
-LIST_FOREACH(cur, &reqs_rqr_17, by_rqr)
-        printf("{%d %d} ", cur->pri, cur->rqr);
-printf("| ");
-LIST_FOREACH(cur, &reqs_rqr_99, by_rqr)
-        printf("{%d %d} ", cur->pri, cur->rqr);
-printf("\n");
+LIST_FOREACH( cur, &reqs_pri, by_pri )
+        printf( "{%d %d} ", cur->pri, cur->rqr );
+printf( "| " );
+LIST_FOREACH( cur, &reqs_rqr_42, by_rqr )
+        printf( "{%d %d} ", cur->pri, cur->rqr );
+printf( "| " );
+LIST_FOREACH( cur, &reqs_rqr_17, by_rqr )
+        printf( "{%d %d} ", cur->pri, cur->rqr );
+printf( "| " );
+LIST_FOREACH( cur, &reqs_rqr_99, by_rqr )
+        printf( "{%d %d} ", cur->pri, cur->rqr );
+printf( "\n" );
 
 }

doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

@@ -131 +131 @@
 \CFA strives to fix mistakes in C, chief among them, safety.
 This thesis presents a significant step forward in \CFA's goal to remove unsafe pointer operations.
-The thesis presents improvements to the \CFA language design, both syntax and semantics, to support advanced container features.
-These features are implemented across the \CFA compiler, libraries, and runtime system.
-The results maintain another \CFA goal of remaining 99\% backwards compatible with C.
-This thesis leverages preexisting work within the compiler's type and runtime systems generated by prior students working on the \CFA project.
-
-All modern programming languages provide three high-level containers (collections): array, linked-list, and string.
-Often array is part of the programming language, while linked-lists are built from (recursive) pointer types, and strings from a combination of array and linked-list.
-For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component level, such as copying, slicing, extracting, and iterating among elements.
-Unfortunately, these three aspects of C cause 60\%--70\% of the reported software vulnerabilities involving memory errors, and 70\%--80\% of hacker attack-vectors target these types.
+It describes improvements to the \CFA language design to support advanced container features.
+These features are implemented across the \CFA compiler and runtime libraries.
+The results maintain another \CFA goal of offering strong backwards compatibility with C.
+This work leverages preexisting \CFA contributiongs of prior students working on the \CFA project, particularly through novel applications of the compiler's type system.
+
+All modern programming languages provide at least these three high-level containers (collections): array, linked-list, and string.
+Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
+For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
+Unfortunately, typical solutions for the the key types in C cause 60\%--70\% of the reported software vulnerabilities involving memory errors; 70\%--80\% of hacker attack vectors target these types.
 Therefore, hardening these three C types goes a long way to make the majority of C programs safer.
 
 Specifically, an array utility is provided that tracks length internally, relieving the user of managing explicit length parameters and stopping buffer-overrun errors.
 This feature requires augmenting the \CFA type system, making array length available at compile and runtime.
-A linked-list utility is provided, which obviates many explicit recursive pointers by catering directly to system-programming uses (intrusive lists) for which a library solution is often dismissed.
+A linked-list utility is provided, which obviates many user-managed recursive pointers by catering directly to system-programming uses (intrusive linking, ad-hoc listing) for which a library solution is often dismissed.
 Finally, a string utility is provided with implicit memory management of text in a specialized heap, relieving error-prone buffer management, including overrun, and providing a copy-on-write speed boost.
 For all three utilities, performance is argued to be on-par with, and occasionally surpassing relevant comparators.

doc/theses/mike_brooks_MMath/uw-ethesis.bib

@@ -94 +94 @@
 }
 
+% -------------------------------------------------
+% Safety
+
 @article{Blache19,
     author      = {Gunter Blache},
@@ -122 +125 @@
 }
 
+@phdthesis{Emre2022,
+    author  = "Mehmet Emre",
+    title   = "Translating C to Safe Rust: Reasoning about Pointer Types and Lifetimes",
+    school  = "UC Santa Barbara",
+    year    = "2022"
+}
+
+@inproceedings{White2016,
+    author = {White, David H. and Rupprecht, Thomas and L\"{u}ttgen, Gerald},
+    title = {DSI: an evidence-based approach to identify dynamic data structures in C programs},
+    year = {2016},
+    isbn = {9781450343909},
+    publisher = {Association for Computing Machinery},
+    address = {New York, NY, USA},
+    url = {https://doi.org/10.1145/2931037.2931071},
+    doi = {10.1145/2931037.2931071},
+    booktitle = {Proceedings of the 25th International Symposium on Software Testing and Analysis},
+    pages = {259–269},
+    numpages = {11},
+    keywords = {Data structure identification, dynamic data structures, pointer programs, program comprehension},
+    location = {Saarbr\"{u}cken, Germany},
+    series = {ISSTA 2016}
+}
+
+% -----------------------------------------------
+% Misc
+
 @misc{RVO20,
     contributer = {pabuhr@plg},
@@ -149 +179 @@
     howpublished= {\url{https://c-faq.com/decl/spiral.anderson.html}},
 }
+