Context Navigation

-              rf632bd50
+              rb195498
 \section{Ill-typed expressions}
+\section{Ill-Typed Expressions}
 C reports many ill-typed expressions as warnings.
 …
 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.
 In the following discussion, ``ill-typed'' means giving a nonzero @gcc@ exit condition with a message that discusses typing.
+In the following discussion, \emph{ill-typed} means giving a nonzero @gcc@ exit condition with a message that discusses typing.
 Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors.
 …
 % *1  TAPL-pg1 definition of a type system
+\section{Reading declarations}
+A significant area of confusion for reading C declarations results from:
+\begin{itemize}
+% reading C declaration: https://c-faq.com/decl/spiral.anderson.html
+\section{Reading Declarations}
+A significant area of confusion is reading C declarations, which results from interesting design choices.
+\begin{itemize}[leftmargin=*]
 \item
+C is unique in having dimension be higher priority than pointer in declarations.\footnote{
+For consistency, subscript has higher priority than dereference, yielding \lstinline{(*arp)[3]} rather than \lstinline{*arp[3]}.}
+In C, it is possible to have a value and a pointer to it.
+\begin{cfa}
+int i = 3, * pi = &i;
+\end{cfa}
+Extending this idea, it should be possible to have an array of values and pointer to it.
+\begin{cfa}
+int a[5] = { 1, 2, 3, 4, 5 },  * pa[5] = &a;
+\end{cfa}
+However, the declaration of @pa@ is incorrect because dimension has higher priority than pointer, so the declaration means an array of 5 pointers to integers.
+The declarations for the two interpretations of @* [5]@ are:
+\begin{cquote}
+\begin{tabular}[t]{@{}ll@{\hspace{15pt}}|@{\hspace{15pt}}ll@{}}
+\begin{cfa}
+int (* pa)[5]
+\end{cfa}
+&
+\raisebox{-0.4\totalheight}{\includegraphics{PtrToArray.pdf}}
+&
+\begin{cfa}
+int * ap[5]
+\end{cfa}
+&
+\raisebox{-0.75\totalheight}{\includegraphics{ArrayOfPtr.pdf}}
+\end{tabular}
+\end{cquote}
+If the priorities of dimension and pointer were reversed, the declarations become more intuitive: @int * pa[5]@ and @int * (ap[5])@.
 \item
+Embedding a declared variable in a declaration, mimics the way the variable is used in executable statements.
+This priority inversion extends into an expression between dereference and subscript, so usage syntax mimics declaration.
+\begin{cquote}
+\setlength{\tabcolsep}{20pt}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+int (* pa)[5]
+      (*pa)[i] += 1;
+\end{cfa}
+&
+\begin{cfa}
+int * ap[5]
+      *ap[i] += 1;
+\end{cfa}
+\end{tabular}
+\end{cquote}
+(\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)@;
+this anomaly is \emph{fixed} with operator @->@, which performs the two operations in the more intuitive order: @sp->f@ $\Rightarrow$ @(*sp).f@.
 \end{itemize}
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
+\multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
+\begin{cfa}
+int @(*@ar@)[@5@]@; // definition
+  ... @(*@ar@)[@3@]@ += 1; // usage
+\end{cfa}
+&
+\begin{cfa}
+int @(*@f@())[@5@]@ { ... }; // definition
+  ... @(*@f@())[@3@]@ += 1; // usage
+\end{cfa}
+\end{tabular}
+\end{cquote}
+The parenthesis are necessary to achieve a pointer to a @T@, and the type is wrapped around the name in successive layers (like an \Index{onion}) to match usage in an expression.
+While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
+While attempting to make the declaration and expression contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
 \begin{quote}
 In 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}
 \end{quote}
 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!
+\CFA provides its own type, variable and routine declarations, using a simpler syntax.
+Unfortunately, \CFA cannot correct these operator priority inversions without breaking C compatibility.
+The alternative solution is for \CFA to provide its own type, variable and routine declarations, using a more intuitive syntax.
 The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
 The qualifiers have the same syntax and semantics in \CFA as in C.
 Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
+The qualifiers have the same syntax and semantics in \CFA as in C, so there is nothing to learn.
+Then, a \CFA declaration is read left to right, where a function return-type is enclosed in brackets @[@\,@]@.
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
 …
 \end{tabular}
 \end{cquote}
 As declaration size increases, it becomes corresponding difficult to read and understand the C declaration form, whereas reading and understanding a \CFA declaration has linear complexity as the declaration size increases.
+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}.
+Unfortunately, \CFA cannot interchange the priorities of subscript and dereference in expressions without breaking C compatibility.
+(Note, 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}.
 …
 The conjoining of pointers and arrays could also be applied to structures, where a pointer references a structure field like an array element.
 Finally, while subscripting involves pointer arithmetic (as does a field reference @x.y.z@), the computation is complex for multi-dimensional arrays and requires array descriptors to know stride lengths along dimensions.
+Many C errors result from manually performing pointer arithmetic instead of using language subscripting, letting the compiler perform any arithmetic.
+Some C textbooks erroneously suggest manual pointer arithmetic is faster than subscripting.
+A sound and efficient C program does not require explicit pointer arithmetic.
+TODO: provide an example, explain the belief, and give modern refutation
+C semantics wants a programmer to \emph{believe} an array variable is a ``pointer to its first element.''
+Many C errors result from manually performing pointer arithmetic instead of using language subscripting so the compiler performs the arithmetic.
+Some modern C textbooks and web sites erroneously suggest manual pointer arithmetic is faster than subscripting.
+When compiler technology was young, this statement might have been true.
+However, a sound and efficient C program coupled with a modern C compiler does not require explicit pointer arithmetic.
+For example, the @gcc@ compiler at @-O3@ generates identical code for the following two summation loops.
+\begin{cquote}
+\vspace*{-10pt}
+\begin{cfa}
+int a[1000], sum;
+\end{cfa}
+\setlength{\tabcolsep}{20pt}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+for ( int i = 0; i < 1000; i += 1 ) {
+        sum += a[i];
+}
+\end{cfa}
+&
+\begin{cfa}
+for ( int * ip = a ; ip < &a[1000]; ip += 1 ) {
+        sum += *ip;
+}
+\end{cfa}
+\end{tabular}
+\end{cquote}
+I believe it is possible to refute any code examples purporting to show pointer arithmetic is faster than subscripting.
+This believe stems from the performance work I did on \CFA arrays, where it is possible to generate equivalent \CFA subscripting and performance to C subscripting.
+Unfortunately, C semantics want a programmer to \emph{believe} an array variable is a \emph{pointer to its first element}.
 This desire becomes apparent by a detailed inspection of an array declaration.
 \lstinput{34-34}{bkgd-carray-arrty.c}
 …
+\subsection{Arrays decay and pointers diffract}
+\subsection{Arrays Decay and Pointers Diffract}
+\label{s:ArraysDecay}
 The last section established the difference among these four types:
 …
 Thus, subscripting happens on pointers not arrays.
+Subscripting 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)))@.
+\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.
+Subscripting 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)))@.
+\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!
 …
 \end{cfa}
 The shortened parameter syntax @T x[]@ is a further way to spell ``pointer.''
+The shortened parameter syntax @T x[]@ is a further way to spell \emph{pointer}.
 Note the opposite meaning of this spelling now, compared with its use in local variable declarations.
 This point of confusion is illustrated in:
 …
 \begin{table}
 \caption{Syntactic Reference for Decay during Parameter-Passing.
 Includes interaction with \lstinline{const}ness, where ``immutable'' refers to a restriction on the callee's ability.}
+Includes interaction with \lstinline{const}ness, where \emph{immutable} refers to a restriction on the callee's ability.}
 \label{bkgd:ar:usr:decay-parm}
 \centering
 …
 \subsection{Variable Length Arrays}
+\subsection{Variable-length Arrays}
 As of C99, the C standard supports a \newterm{variable length array} (VLA)~\cite[\S~6.7.5.2.5]{C99}, providing a dynamic-fixed array feature \see{\VRef{s:ArrayIntro}}.
 …
 % TODO: introduce multidimensional array feature and approaches
 When working with arrays, \eg linear algebra, array dimensions are referred to as ``rows'' and ``columns'' for a matrix, adding ``planes'' for a cube.
+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.}
 …
 Many languages allow multidimensional arrays-of-arrays, \eg in Pascal or \CC.
 \begin{cquote}
+\setlength{\tabcolsep}{15pt}
 \begin{tabular}{@{}ll@{}}
 \begin{pascal}
 …
 \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 (including VLA) arguments, 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@.
+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.
 If the declaration of @fc@ is changed to:
 …
+\subsection{Multi-dimensional arrays decay and pointers diffract}
+As for single-dimension arrays, multi-dimensional arrays have similar issues.
+\subsection{Multi-Dimensional Arrays Decay and Pointers Diffract}
+As for single-dimension, multi-dimensional arrays have similar issues \see{\VRef{s:Array}}.
+Again, the inspection begins by using @sizeof@ to provide program semantics for the intuition of an expression's type.
 \lstinput{16-18}{bkgd-carray-mdim.c}
+The significant axis of deriving expressions from @ar@ is now ``itself,'' ``first element'' or ``first grand-element (meaning, first element of first element).''
+\PAB{Explain, explain, explain.}
+There are now three axis for deriving expressions from @mx@: \emph{itself}, \emph{first element}, and \emph{first grand-element} (meaning, first element of first element).
 \lstinput{20-26}{bkgd-carray-mdim.c}
+\PAB{Explain, explain, explain.}
+Given that arrays are contiguous and the size of @float@ is 4, then the size of @mx@ with 3 $\times$ 10 floats is 120 bytes, the size of its first element (row) is 40 bytes, and the size of the first element of the first row is 4.
+Again, an array and a point to each of its axes are different.
 \lstinput{28-36}{bkgd-carray-mdim.c}
+\PAB{Explain, explain, explain.}
+As well, there is pointer decay from each of the matrix axes to pointers, which all have 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.
 …
 Passing an array as an argument to a function is necessary.
 Assume a parameter is an array when the function intends to subscript it.
 This section asserts that a more satisfactory/formal characterization does not exist in C, surveys the ways that C API authors communicate ``@p@ has zero or more dimensions'' and calls out the minority cases where the C type system is using or verifying such claims.
 A C parameter declarations look different, from the caller's and callee's perspectives.
+Assume a parameter is an array where the function intends to subscript it.
+This section asserts that a more satisfactory/formal characterization does not exist in C, then surveys the ways that C API authors communicate @p@ has zero or more dimensions, and finally calls out the minority cases where the C type system is using or verifying such claims.
+A C parameter declaration looks different from the caller's and callee's perspectives.
 Both perspectives consist of the text read by a programmer and the semantics enforced by the type system.
 The caller's perspective is available from a function declaration, which allow definition-before-use and separate compilation, but can also be read from (the non-body part of) a function definition.
+The caller's perspective is available from a function declaration, which allows definition-before-use and separate compilation, but can also be read from (the non-body part of) a function definition.
 The callee's perspective is what is available inside the function.
 \begin{cfa}
 int foo( int, float, char );                            $\C{// declaration, names optional}$
 int bar( int i, float f, char c ) {             $\C{// definition, names mandatory}$
         // caller's perspective of foo; callee's perspective of bar
+int foo( int, float, char );                            $\C{// declaration, parameter names optional}$
+int bar( int i, float f, char c ) {             $\C{// definition, parameter names mandatory}$
+        // callee's perspective of foo and bar
+}
 // caller's perspectives of foo's and bar's
 \end{cfa}
 In caller's perspective, the parameter names (by virtue of being optional) are really comments;
 in the callee's perspective, parameter names are semantically significant.
+// 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.
 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.
 This fact probably shares considerable responsibility for the common sense of ``an array is just a pointer,'' which has been refuted in non-parameter contexts.
+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.
+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.
+In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the flavour of parameter.
+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.
+In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
 \begin{figure}
-\begin{cquote}
 \begin{tabular}{@{}llll@{}}
 \begin{cfa}
 float sum( float a[5] );
 float sum( float a[5][4] );
+float sum( float m[5][4] );
 float sum( float a[5][] );
 float sum( float a[5]* );
 …
 \begin{cfa}
 float sum( float a[] );
 float sum( float a[][4] );
+float sum( float m[][4] );
 float sum( float a[][] );
 float sum( float a[]* );
 …
 \begin{cfa}
 float sum( float *a );
 float sum( float (*a)[4] );
+float sum( float (*m)[4] );
 float sum( float (*a)[] );
 float sum( float (*a)* );
 …
+&
 \begin{cfa}
 // ar of float
 // mat of float
+// array of float
+// matrix of float
 // invalid
 // invalid
+// ar of ptr to float
+\end{cfa}
+\end{tabular}
+\end{cquote}
+// array of ptr to float
+\end{cfa}
+\end{tabular}
 \caption{Multiple ways to declare an array parameter.
 Across a valid row, every declaration is equivalent.
 …
 \end{figure}
+In the leftmost style, the typechecker ignores the actual value in most practical cases.
+This value is allowed to be a dynamic expression, and then it has practical cases.
+\begin{cfa}
+void foo( int @n@ ) {
+        float _42( float @a[n]@ ) {    // nested function
+                a[0] = 42;
+        }
+        float b[n];
+        _42( b );
+}
+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.
+\begin{cfa}
+int N;
+void foo( float @a[N] ) ; // N is ignored
 \end{cfa}
 …
 % 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 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'').
 Note that this equivalence of pointer and array declarations is special to parameters.
 …
+}
 \end{cfa}
 This equivalence has the consequence that the type system does not help a caller get it right.
+Unfortunately, this equivalence has the consequence that the type system does not help a caller get it right.
 \begin{cfa}
 float sum( float v[] );
 …
 void foo( int [@const  volatile@ 5] );          $\C{// 5 is ignored}$
 \end{cfa}
 To make the first dimension size meaningful, C adds this form.
 \begin{cquote}
 …
 \end{cfa}
 Here, the @static@ storage qualifier defines the minimum array size for its argument.
+@gcc@ ignores this dimension qualifier, \ie it gives no warning if the argument array size is less than the parameter minimum.  However, @clang@ implements the check, in accordance with the standard.  TODO: be specific about versions
+Earlier versions of @gcc@ ($<$ 11) and possibly @clang@ ignore this dimension qualifier, while later versions implement the check, in accordance with the standard.
 Note that there are now two different meanings for modifiers in the same position.  In
 …
 Here, the distance between the first and second elements of each array depends on the inner dimension size.
 This significance of an inner dimension's length is a fact of the callee's perspective.
 In the caller's perspective, the type sytem is quite lax.
+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.
 % void f( float [][10] );
 …
 \end{cfa}
 The cases without comments are rejections, but simply because the array ranks do not match; in the commented cases, the ranks match and the rules being discussed apply.
 The cases @f(b)@ and @f(&a)@ show where some length checking occurs.
 But this checking misses the cases @f(d)@ and @f(&c)@, allowing the calls with mismatched lengths, actually 100 for 10.
+The cases @f( b )@ and @f( &a )@ show where some length checking occurs.
+But this checking misses the cases @f( d )@ and @f( &c )@, allowing the calls with mismatched lengths, actually 100 for 10.
 The C checking rule avoids false alarms, at the expense of safety, by allowing any combinations that involve dynamic values.
 Ultimately, an inner dimension's size is a callee's \emph{assumption} because the type system uses declaration details in the callee's perspective that it does not enforce in the caller's perspective.
 Finally, to handle higher-dimensional VLAs, C repurposed the @*@ \emph{within} the dimension in a declaration to mean that the callee has make an assumption about the size, but no (unchecked, possibly wrong) information about this assumption is included for the caller-programmer's benefit/over-confidence.
+Finally, to handle higher-dimensional VLAs, C repurposed the @*@ \emph{within} the dimension in a declaration to mean that the callee has make an assumption about the size, but no (checked, possibly wrong) information about this assumption is included for the caller-programmer's benefit/\-over-confidence.
 \begin{cquote}
 @[@ \textit{type-qualifier-list$_{opt}$} @* ]@
 …
 \subsection{Arrays could be values}
+\subsection{Arrays Could be Values}
 All arrays have a know runtime size at their point of declaration.
 …
 \begin{cfa}
 Jmp_Buf jb1, jb2;
 jb1 = jb2;
+jb1 = jb2;            // copy
 void foo( Jmp_Buf );
 foo( jb2 );
+foo( jb2 );           // copy
 \end{cfa}
 This same argument applies to returning arrays from functions.
 There can be sufficient information to return an array by value but it is not supported.
 Again, array wrapping allows an array to be returned from a function and copied into variable.
+There can be sufficient information to return an array by value but it is unsupported.
+Again, array wrapping allows an array to be returned from a function and copied into a variable.
 …
 \subsection{Design issues}
+\subsection{Design Issues}
 \label{toc:lst:issue}
 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 (Section~\ref{toc:lst:futwork}).
+alternatives to the assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
 \begin{itemize}
         \item A doubly-linked list is being designed.
                 Generally, the discussed issues apply similarly for singly-linked lists.
                 Circular \vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
+                Circular \vs ordered linking is discussed under List identity (\VRef{toc:lst:issue:ident}).
         \item Link fields are system-managed.
                 The user works with the system-provided API to query and modify list membership.
 …
 \subsection{Preexisting linked-list libraries}
+\subsection{Preexisting Linked-List Libraries}
 \label{s:PreexistingLinked-ListLibraries}
 …
         \item \CC Standard Template Library's (STL)\footnote{The term STL is contentious as some people prefer the term standard library.} @std::list@\cite{lst:stl}
 \end{enumerate}
 %A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
+%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.
 \subsection{Link attachment: intrusive vs.\ wrapped}
+\subsection{Link Attachment: Intrusive \vs Wrapped}
 \label{toc:lst:issue:attach}
 …
                 Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
                 The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
                 head objects are discussed in Section~\ref{toc:lst:issue:ident}.
+                head objects are discussed in \VRef{toc:lst:issue:ident}.
                 In (a), the field \lstinline{req.x} names a list direction;
                 these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
+                these are discussed in \VRef{toc:lst:issue:simultaneity}.
                 In (b) and (c), the type \lstinline{node} represents a system-internal type,
                 which is \lstinline{std::_List_node} in the GNU implementation.
 …
                 % \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped reference, and \protect\subref*{f:WrappedValue}~wrapped value.
                 The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
                 head objects are discussed in Section~\ref{toc:lst:issue:ident}.
+                head objects are discussed in \VRef{toc:lst:issue:ident}.
                 In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
                 these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
+                these are discussed in \VRef{toc:lst:issue:simultaneity}.
                 In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
                 library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
 …
 In all three cases, a @req@ object can enter and leave a list many times.
 However, in intrusive a @req@ can only be on one list at a time, unless there are separate link-fields for each simultaneous list.
 In wrapped reference, a @req@ can appear multiple times on the same or different lists simultaneously, but since @req@ is shared via the pointer, care must be taken if updating data also occurs simultaneously, \eg concurrency.
+In wrapped reference, a @req@ can appear multiple times on the same or different lists, but since @req@ is shared via the pointer, care must be taken if updating data also occurs simultaneously, \eg concurrency.
 In wrapped value, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
 however, knowing which of the @req@ object is the ``true'' object becomes complex.
+however, knowing which of the @req@ object is the \emph{true} object becomes complex.
 \see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
 The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
 The macro @LIST_INSERT_HEAD(&reqs, &r2, d);@ takes the list header, a pointer to the node, and the offset of the link fields in the node.
+The macro @LIST_INSERT_HEAD( &reqs, &r2, d )@ takes the list header, a pointer to the node, and the offset of the link fields in the node.
 One of the fields generated by @LIST_ENTRY@ is a pointer to the node, which is set to the node address, \eg @r2@.
 Hence, the offset to the link fields provides an access to the entire node, \ie the node points at itself.
 For list traversal, @LIST_FOREACH(cur, &reqs_pri, by_pri)@, there is the node cursor, the list, and the offset of the link fields within the node.
+For list traversal, @LIST_FOREACH( cur, &reqs_pri, by_pri )@, there is the node cursor, the list, and the offset of the link fields within the node.
 The traversal actually moves from link fields to link fields within a node and sets the node cursor from the pointer within the link fields back to the node.
 …
 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@;
 there is no distinguishing a @req@ from ``a @req@ in a list.''
+there is no distinguishing a @req@ from a @req@ in a list.
 The same is not true of STL, wrapped reference or value.
 There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list<T>::iterator@;
 …
                 the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
                 When using a custom-patched version of LQ to work around this issue,
                 the programs of Figure~\ref{f:WrappedRef} and wrapped value work with this shim in place of real STL.
+                the programs of \VRef[Figure]{f:WrappedRef} and wrapped value work with this shim in place of real STL.
                 Their executions lead to the same memory layouts.
+        }
 …
 \end{figure}
 It is possible to simulate wrapped using intrusive, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
+It is possible to simulate wrapped using intrusive, illustrated in \VRef[Figure]{fig:lst-issues-attach-reduction}.
 This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
 But there is no reduction going the other way.
 …
 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.
+\subsection{Simultaneity: single vs.\ multi-static vs.\ dynamic}
+\CFA is capable of supporting a wrapped library, if need arose.
+\subsection{Simultaneity: Single \vs Multi-Static \vs Dynamic}
 \label{toc:lst:issue:simultaneity}
 …
 \newterm{Simultaneity} deals with the question:
 In how many different lists can a node be stored, at the same time?
 Figure~\ref{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
+\VRef[Figure]{fig:lst-issues-multi-static} shows an example that can traverse all requests in priority order (field @pri@) or navigate among requests with the same request value (field @rqr@).
 Each of ``by priority'' and ``by common request value'' is a separate list.
 For example, there is a single priority-list linked in order [1, 2, 2, 3, 3, 4], where nodes may have the same priority, and there are three common request-value lists combining requests with the same values: [42, 42], [17, 17, 17], and [99], giving four head nodes one for each list.
 …
 This feature is used in the \CFA runtime, where a thread node may be on a blocked or running list, but never on both simultaneously.
 Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}.
+Now consider the STL in the wrapped-reference arrangement of \VRef[Figure]{f:WrappedRef}.
 Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
 Each group of intrusive links become the links for each separate STL list.
 …
 Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
 Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
+Now consider the STL in the wrapped-value arrangement of \VRef[Figure]{f:WrappedValue}.
 Again, it is possible to construct the same simultaneity by creating multiple STL lists, each copying the appropriate nodes, where the intrusive links become the links for each separate STL list.
 The upside is the same as for wrapped-reference arrangement with an unlimited number of list bindings.
 …
 % LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
 % Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
 % This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
 % but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
+% This decision works well in \VRef[Figure]{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
+% but it clutters \VRef[Figure]{f:Intrusive}, where a contrived name must be invented and used.
 % The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
 …
+\subsection{User integration: preprocessed vs.\ type-system mediated}
+\PAB{What do you want to say here?}
+\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.
+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.
 % example of poor error message due to LQ's preprocessed integration
 …
 \subsection{List identity: headed vs.\ ad-hoc}
+\subsection{List Identity: Headed \vs Ad-Hoc}
 \label{toc:lst:issue:ident}
+All examples so far use distinct user-facing types:
+an item found in a list (type @req@ of variable @r1@, see \VRef[Figure]{fig:lst-issues-attach}), and a list (type @reql@ of variable @reqs_pri@, see \VRef[Figure]{fig:lst-issues-ident}).
+The latter type is a head.
+The resulting identity model (empty list) is just the head.
+A bespoke ``pointer to next @req@'' implementation often omits the header;
+hence, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
+The resulting identity model is ad-hoc.
+Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
+the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
+In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
+In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
+By omitting the head, elements can enter into an adjacency relationship, without requiring allocation for a head for the list, or finding a correct existing head.
+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.
+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.
+\VRef[Figure]{fig:lst-issues-ident} shows both approaches for different list lengths and unlisted elements.
+For headed, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
+For ad-hoc, there are no length-zero lists and every element belongs to a list of length at least one.
 \begin{figure}
 …
 \end{figure}
 A head defines one or more element roles, among elements that share a transitive adjacency.
 ``First'' and ``last'' are element roles.
 One moment's ``first'' need not be the next moment's.
 There is a cost to maintaining these roles.
+The purpose of a header is to provide specialized but implicit node access, such as the first/last nodes in the list, where accessing these nodes is deemed a commonly occurring operation and should be $O(1)$ for performance of certain operations.
+For example, without a last pointer in a singly-linked list, adding to the end of the list is an $O(N)$ operation to traverse the list to find the last node.
+Without the header, this specialized information must be managed explicitly, where the programmer builds their own external, equivalent header information.
+However, external management of particular nodes might not be beneficial because the list does not provide operations that can take advantage of them, such as using an external pointer to update an internal link.
+Clearly, there is a cost maintaining this specialized information, which needs to be amortized across the list operations that use it, \eg rarely adding to the end of a list.
 A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@.
+Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
+Its @LIST@ maintains a \emph{first}, but not a \emph{last};
+its @TAILQ@ maintains both roles.
 (Both types are doubly linked and an analogous choice is available for singly linked.)
+TODO: finish making this point
+See WIP in lst-issues-adhoc-*.ignore.*.
+The code-complexity component of the cost ...
+Ability to offer heads is good.  Point: Does maintaining a head mean that the user has to provide more state when manipulating the list?  Requiring the user to do so is bad, because the user may have lots of "list" typed variables in scope, and detecting that the user passed the wrong one requires testing all the listing edge cases.
+\subsection{End treatment: cased vs.\ uniform }
+A linear (non-circular), nonempty linked-list has a first element and a last element, whether or not the list is headed.
+A first element has no predecessor and a last element has no successor.
+\subsection{End Treatment: Cased \vs Uniform }
+All lists must have a logical \emph{beginning/ending}, otherwise list traversal is infinite.
+\emph{End treatment} refers to how the list represents the lack of a predecessor/successor to demarcate end point(s).
+For example, in a doubly-linked list containing a single node, the next/prev links have no successor/predecessor nodes.
+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.
+The following discussion refers to the LQ representations, detailed in \VRef[Figure]{fig:lst-issues-end}, using a null pointer to mark end points.
+LQ uses this representation for its successor/last.
+For example, consider the operation of inserting after a given element.
+A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
+This step must happen when the given node has a successor (when its successor pointer is non-null),
+and must be skipped when it does not (when its successor pointer cannot be navigated).
+So this operation contains a branch, to decide which case is happening.
+All branches have pathological cases where branch prediction's success rate is low and the execution pipeline stalls often.
+Hence, this issue is relevant to achieving high performance.
 \begin{figure}
 …
 \end{figure}
+End treatment refers to how the list represents the lack of a predecessor/successor.
+The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
+The most obvious representation, a null pointer, mandates a cased end treatment.
+LQ uses this representation for its successor/last.
+Consider the operation of inserting after a given element.
+A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
+This step must happen when the given node has a successor (when its successor pointer is non-null),
+and must be skipped when it does not (when its successor pointer cannot be navigated).
+So this operation contains a branch, to decide which case is happening.
+All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
+Hence, this issue is implementation-level, relevant to achieving high performance.
+This branch is sometimes avoidable; the result is a uniform end treatment.
+Here is one example of such an implementation that works for a headed list.
+LQ uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
+Interestingly, this branch is sometimes avoidable, giving a uniform end-treatment in the code.
+For example, LQ is headed at the front.
 For predecessor/first navigation, the relevant operation is inserting before a given element.
 LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
 When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
 When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
 The list head contains a pointer to the first node.
+Now, the list head contains a pointer to the first node.
 When inserting before the first node, the list head's first-pointer is the one that must change.
 So, the first node's ``predecessor'' pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
+So, the first node's \emph{predecessor} pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
 Now, inserting before a given element does the same logic in both cases:
 follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
+follow the guaranteed-non-null predecessor pointer, and update that location to refer to the new node.
 Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow.
 Considering a path length of only a few instructions (less than the processor's pipeline length),

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset b195498 for doc/theses/mike_brooks_MMath/background.tex

Legend:

doc/theses/mike_brooks_MMath/background.tex

Download in other formats: