Changeset b195498


Ignore:
Timestamp:
Apr 24, 2025, 6:35:41 PM (5 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
6b33e89, f85de47
Parents:
f632bd50
Message:

proofreading intro and background chapters, capitalize section titles, update backtick calls to regular calls

Location:
doc/theses/mike_brooks_MMath
Files:
10 edited

Legend:

Unmodified
Added
Removed

  • doc/theses/mike_brooks_MMath/array.tex

    rf632bd50 rb195498  
    9090
    9191
    92 \section{Dependent typing}
     92\section{Dependent Typing}
    9393
    9494General dependent typing allows the type system to encode arbitrary predicates (\eg behavioural specifications for functions),
    … …  
    103103
    104104
    105 \section{Features added}
     105\section{Features Added}
    106106
    107107This section shows more about using the \CFA array and dimension parameters, demonstrating their syntax and semantics by way of motivating examples.
    … …  
    782782
    783783
    784 Figure~\ref{f:DimexprRuleCompare} gives a case-by-case comparison of the consequences of these rule sets.
     784\VRef[Figure]{f:DimexprRuleCompare} gives a case-by-case comparison of the consequences of these rule sets.
    785785It demonstrates that the \CFA false alarms occur in the same cases as C treats unsafe.
    786786It also shows that C-incompatibilities only occur in cases that C treats unsafe.
    … …  
    859859
    860860
    861 \section{Multidimensional array implementation}
     861\section{Multidimensional Array Implementation}
    862862\label{s:ArrayMdImpl}
    863863
    … …  
    978978\end{figure}
    979979
    980 Figure~\ref{fig:subscr-all} shows one element (in the shaded band) accessed two different ways: as @x[2][3]@ and as @x[all][3][2]@.
     980\VRef[Figure]{fig:subscr-all} shows one element (in the shaded band) accessed two different ways: as @x[2][3]@ and as @x[all][3][2]@.
    981981In both cases, value 2 selects from the coarser dimension (rows of @x@),
    982982while the value 3 selects from the finer dimension (columns of @x@).
    … …  
    10241024% The choice to implement this style-1 system upon C's style-2 arrays, rather than its style-3 pointer arithmetic, reduces the attack surface of unsafe code.
    10251025% My casting is unsafe, but I do not do any pointer arithmetic.
    1026 % When a programmer works in the common-case style-2 subset (in the no-@[all]@ top of Figure~\ref{fig:subscr-all}), my casts are identities, and the C compiler is doing its usual displacement calculations.
     1026% When a programmer works in the common-case style-2 subset (in the no-@[all]@ top of \VRef[Figure]{fig:subscr-all}), my casts are identities, and the C compiler is doing its usual displacement calculations.
    10271027% If I had implemented my system upon style-3 pointer arithmetic, then this common case would be circumventing C's battle-hardened displacement calculations in favour of my own.
    10281028
    … …  
    10671067
    10681068
    1069 \section{Bound checks, added and removed}
     1069\section{Bound Checks, Added and Removed}
    10701070
    10711071\CFA array subscripting is protected with runtime bound checks.
    … …  
    10891089
    10901090
    1091 \section{Array lifecycle}
     1091\section{Array Lifecycle}
    10921092
    10931093An array is an aggregate, like a structure;
    … …  
    13411341% note to Mike, I have more fragments on some details available in push24\fragments\uNoCtor.txt
    13421342
    1343 \section{Comparison with other arrays}
     1343\section{Comparison with Other Arrays}
    13441344
    13451345
    … …  
    14571457
    14581458
    1459 \subsection{Levels of dependently typed arrays}
     1459\subsection{Levels of Dependently Typed Arrays}
    14601460
    14611461The \CFA array and the field of ``array language'' comparators all leverage dependent types to improve on the expressiveness over C and Java, accommodating examples such as:
    … …  
    15041504Having no instances means there is no type for a variable @i@ that constrains @i@ to be in the range for @N@, unlike Dex, [TODO: verify], but like Futhark.
    15051505
    1506 \subsection{Static safety in C extensions}
    1507 
    1508 
    1509 \section{Future work}
    1510 
    1511 \subsection{Declaration syntax}
    1512 
    1513 \subsection{Range slicing}
    1514 
    1515 \subsection{With a module system}
    1516 
    1517 \subsection{With described enumerations}
     1506\subsection{Static Safety in C Extensions}
     1507
     1508
     1509\section{Future Work}
     1510
     1511\subsection{Declaration Syntax}
     1512
     1513\subsection{Range Slicing}
     1514
     1515\subsection{With a Module System}
     1516
     1517\subsection{With Described Enumerations}
    15181518
    15191519A project in \CFA's current portfolio will improve enumerations.
    … …  
    16021602In the case of adapting this pattern to \CFA, my current work provides an adapter from ``successively subscripted'' to ``subscripted by tuple,'' so it is likely that generalizing my adapter beyond ``subscripted by @ptrdiff_t@'' is sufficient to make a user-provided adapter unnecessary.
    16031603
    1604 \subsection{Retire pointer arithmetic}
     1604\subsection{Retire Pointer Arithmetic}
    16051605
    16061606
    … …  
    16141614(For later:  That's what I offer with array.hfa, but in the future-work vision for arrays, the fix includes helping programmers stop accidentally using a broken C-ism.)
    16151615
    1616 \subsection{\CFA features interacting with arrays}
     1616\subsection{\CFA Features Interacting with Arrays}
    16171617
    16181618Prior work on \CFA included making C arrays, as used in C code from the wild,

  • doc/theses/mike_brooks_MMath/background.tex

    rf632bd50 rb195498  
    44
    55
    6 \section{Ill-typed expressions}
     6\section{Ill-Typed Expressions}
    77
    88C reports many ill-typed expressions as warnings.
    … …  
    2424Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
    2525Compiling with flag @-Werror@, which turns warnings into errors, is often too pervasive, because some warnings are just warnings, \eg an unused variable.
    26 In the following discussion, ``ill-typed'' means giving a nonzero @gcc@ exit condition with a message that discusses typing.
     26In the following discussion, \emph{ill-typed} means giving a nonzero @gcc@ exit condition with a message that discusses typing.
    2727Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors.
    2828
    … …  
    3737% *1  TAPL-pg1 definition of a type system
    3838
    39 
    40 \section{Reading declarations}
    41 
    42 A significant area of confusion for reading C declarations results from:
    43 \begin{itemize}
     39% reading C declaration: https://c-faq.com/decl/spiral.anderson.html
     40
     41
     42\section{Reading Declarations}
     43
     44A significant area of confusion is reading C declarations, which results from interesting design choices.
     45\begin{itemize}[leftmargin=*]
    4446\item
    45 C is unique in having dimension be higher priority than pointer in declarations.\footnote{
    46 For consistency, subscript has higher priority than dereference, yielding \lstinline{(*arp)[3]} rather than \lstinline{*arp[3]}.}
     47In C, it is possible to have a value and a pointer to it.
     48\begin{cfa}
     49int i = 3, * pi = &i;
     50\end{cfa}
     51Extending this idea, it should be possible to have an array of values and pointer to it.
     52\begin{cfa}
     53int a[5] = { 1, 2, 3, 4, 5 },  * pa[5] = &a;
     54\end{cfa}
     55However, the declaration of @pa@ is incorrect because dimension has higher priority than pointer, so the declaration means an array of 5 pointers to integers.
     56The declarations for the two interpretations of @* [5]@ are:
     57\begin{cquote}
     58\begin{tabular}[t]{@{}ll@{\hspace{15pt}}|@{\hspace{15pt}}ll@{}}
     59\begin{cfa}
     60int (* pa)[5]
     61\end{cfa}
     62&
     63\raisebox{-0.4\totalheight}{\includegraphics{PtrToArray.pdf}}
     64&
     65\begin{cfa}
     66int * ap[5]
     67\end{cfa}
     68&
     69\raisebox{-0.75\totalheight}{\includegraphics{ArrayOfPtr.pdf}}
     70\end{tabular}
     71\end{cquote}
     72If the priorities of dimension and pointer were reversed, the declarations become more intuitive: @int * pa[5]@ and @int * (ap[5])@.
    4773\item
    48 Embedding a declared variable in a declaration, mimics the way the variable is used in executable statements.
     74This priority inversion extends into an expression between dereference and subscript, so usage syntax mimics declaration.
     75\begin{cquote}
     76\setlength{\tabcolsep}{20pt}
     77\begin{tabular}{@{}ll@{}}
     78\begin{cfa}
     79int (* pa)[5]
     80      (*pa)[i] += 1;
     81\end{cfa}
     82&
     83\begin{cfa}
     84int * ap[5]
     85      *ap[i] += 1;
     86\end{cfa}
     87\end{tabular}
     88\end{cquote}
     89(\VRef{s:ArraysDecay} shows pointer decay allows the first form to be written @pa[i] += 1@, which is further syntax confusion.)
     90Again, if the priorities were reversed, the expressions become more intuitive: @*pa[i] += 1@ and @*(ap[i]) += 1@.
     91Note, a similar priority inversion exists between deference @*@ and field selection @.@ (period), so @*ps.f@ means @*(ps.f)@;
     92this anomaly is \emph{fixed} with operator @->@, which performs the two operations in the more intuitive order: @sp->f@ $\Rightarrow$ @(*sp).f@.
    4993\end{itemize}
    50 \begin{cquote}
    51 \begin{tabular}{@{}ll@{}}
    52 \multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
    53 \begin{cfa}
    54 int @(*@ar@)[@5@]@; // definition
    55   ... @(*@ar@)[@3@]@ += 1; // usage
    56 \end{cfa}
    57 &
    58 \begin{cfa}
    59 int @(*@f@())[@5@]@ { ... }; // definition
    60   ... @(*@f@())[@3@]@ += 1; // usage
    61 \end{cfa}
    62 \end{tabular}
    63 \end{cquote}
    64 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.
    65 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:
     94While 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:
    6695\begin{quote}
    6796In 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}
    6897\end{quote}
    6998After 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!
    70 
    71 \CFA provides its own type, variable and routine declarations, using a simpler syntax.
     99Unfortunately, \CFA cannot correct these operator priority inversions without breaking C compatibility.
     100
     101The alternative solution is for \CFA to provide its own type, variable and routine declarations, using a more intuitive syntax.
    72102The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
    73 The qualifiers have the same syntax and semantics in \CFA as in C.
    74 Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
     103The qualifiers have the same syntax and semantics in \CFA as in C, so there is nothing to learn.
     104Then, a \CFA declaration is read left to right, where a function return-type is enclosed in brackets @[@\,@]@.
    75105\begin{cquote}
    76106\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
    … …  
    98128\end{tabular}
    99129\end{cquote}
    100 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.
     130As declaration size increases, it becomes corresponding difficult to read and understand the C form, whereas reading and understanding a \CFA declaration has linear complexity.
    101131Note, 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}.
    102 Unfortunately, \CFA cannot interchange the priorities of subscript and dereference in expressions without breaking C compatibility.
     132(Note, putting the return type at the end deviates from where the return value logically appears in an expression, @x = f(...)@ versus @f(...) = x@.)
     133Interestingly, programmers normally speak a declaration from left to right, regardless of how it is written.
     134(It is unclear if Hebrew or Arabic speakers, say declarations right to left.)
    103135
    104136\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}.
    … …  
    168200The conjoining of pointers and arrays could also be applied to structures, where a pointer references a structure field like an array element.
    169201Finally, 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.
    170 Many C errors result from manually performing pointer arithmetic instead of using language subscripting, letting the compiler perform any arithmetic.
    171 
    172 Some C textbooks erroneously suggest manual pointer arithmetic is faster than subscripting.
    173 A sound and efficient C program does not require explicit pointer arithmetic.
    174 TODO: provide an example, explain the belief, and give modern refutation
    175 
    176 C semantics wants a programmer to \emph{believe} an array variable is a ``pointer to its first element.''
     202Many C errors result from manually performing pointer arithmetic instead of using language subscripting so the compiler performs the arithmetic.
     203
     204Some modern C textbooks and web sites erroneously suggest manual pointer arithmetic is faster than subscripting.
     205When compiler technology was young, this statement might have been true.
     206However, a sound and efficient C program coupled with a modern C compiler does not require explicit pointer arithmetic.
     207For example, the @gcc@ compiler at @-O3@ generates identical code for the following two summation loops.
     208\begin{cquote}
     209\vspace*{-10pt}
     210\begin{cfa}
     211int a[1000], sum;
     212\end{cfa}
     213\setlength{\tabcolsep}{20pt}
     214\begin{tabular}{@{}ll@{}}
     215\begin{cfa}
     216for ( int i = 0; i < 1000; i += 1 ) {
     217        sum += a[i];
     218}
     219\end{cfa}
     220&
     221\begin{cfa}
     222for ( int * ip = a ; ip < &a[1000]; ip += 1 ) {
     223        sum += *ip;
     224}
     225\end{cfa}
     226\end{tabular}
     227\end{cquote}
     228I believe it is possible to refute any code examples purporting to show pointer arithmetic is faster than subscripting.
     229This 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.
     230
     231Unfortunately, C semantics want a programmer to \emph{believe} an array variable is a \emph{pointer to its first element}.
    177232This desire becomes apparent by a detailed inspection of an array declaration.
    178233\lstinput{34-34}{bkgd-carray-arrty.c}
    … …  
    224279
    225280
    226 \subsection{Arrays decay and pointers diffract}
     281\subsection{Arrays Decay and Pointers Diffract}
     282\label{s:ArraysDecay}
    227283
    228284The last section established the difference among these four types:
    … …  
    247303Thus, subscripting happens on pointers not arrays.
    248304
    249 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)))@.
    250 \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.
     305Subscripting proceeds first with pointer decay, if needed.
     306Next, \cite[\S~6.5.2.1.2]{C11} explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
     307\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.
    251308Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
    252309Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!
    … …  
    285342\end{cfa}
    286343
    287 The shortened parameter syntax @T x[]@ is a further way to spell ``pointer.''
     344The shortened parameter syntax @T x[]@ is a further way to spell \emph{pointer}.
    288345Note the opposite meaning of this spelling now, compared with its use in local variable declarations.
    289346This point of confusion is illustrated in:
    … …  
    321378\begin{table}
    322379\caption{Syntactic Reference for Decay during Parameter-Passing.
    323 Includes interaction with \lstinline{const}ness, where ``immutable'' refers to a restriction on the callee's ability.}
     380Includes interaction with \lstinline{const}ness, where \emph{immutable} refers to a restriction on the callee's ability.}
    324381\label{bkgd:ar:usr:decay-parm}
    325382\centering
    … …  
    357414
    358415
    359 \subsection{Variable Length Arrays}
     416\subsection{Variable-length Arrays}
    360417
    361418As 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}}.
    … …  
    379436% TODO: introduce multidimensional array feature and approaches
    380437
    381 When working with arrays, \eg linear algebra, array dimensions are referred to as ``rows'' and ``columns'' for a matrix, adding ``planes'' for a cube.
     438When 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.
    382439(There is little terminology for higher dimensional arrays.)
    383440For 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.}
    … …  
    433490Many languages allow multidimensional arrays-of-arrays, \eg in Pascal or \CC.
    434491\begin{cquote}
     492\setlength{\tabcolsep}{15pt}
    435493\begin{tabular}{@{}ll@{}}
    436494\begin{pascal}
    … …  
    467525
    468526\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.}
    469 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@.
     527For 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@.
    470528There 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.
    471529If the declaration of @fc@ is changed to:
    … …  
    517575
    518576
    519 \subsection{Multi-dimensional arrays decay and pointers diffract}
    520 
    521 As for single-dimension arrays, multi-dimensional arrays have similar issues.
     577\subsection{Multi-Dimensional Arrays Decay and Pointers Diffract}
     578
     579As for single-dimension, multi-dimensional arrays have similar issues \see{\VRef{s:Array}}.
     580Again, the inspection begins by using @sizeof@ to provide program semantics for the intuition of an expression's type.
    522581\lstinput{16-18}{bkgd-carray-mdim.c}
    523 The significant axis of deriving expressions from @ar@ is now ``itself,'' ``first element'' or ``first grand-element (meaning, first element of first element).''
    524 \PAB{Explain, explain, explain.}
     582There 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).
    525583\lstinput{20-26}{bkgd-carray-mdim.c}
    526 \PAB{Explain, explain, explain.}
     584Given 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.
     585Again, an array and a point to each of its axes are different.
    527586\lstinput{28-36}{bkgd-carray-mdim.c}
    528 \PAB{Explain, explain, explain.}
     587As well, there is pointer decay from each of the matrix axes to pointers, which all have the same address.
    529588\lstinput{38-44}{bkgd-carray-mdim.c}
     589Finally, subscripting on a @malloc@ result, where the referent may or may not allow subscripting or have the right number of subscripts.
    530590
    531591
    … …  
    533593
    534594Passing an array as an argument to a function is necessary.
    535 Assume a parameter is an array when the function intends to subscript it.
    536 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.
    537 
    538 A C parameter declarations look different, from the caller's and callee's perspectives.
     595Assume a parameter is an array where the function intends to subscript it.
     596This 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.
     597
     598A C parameter declaration looks different from the caller's and callee's perspectives.
    539599Both perspectives consist of the text read by a programmer and the semantics enforced by the type system.
    540 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.
     600The 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.
    541601The callee's perspective is what is available inside the function.
    542602\begin{cfa}
    543 int foo( int, float, char );                            $\C{// declaration, names optional}$
    544 int bar( int i, float f, char c ) {             $\C{// definition, names mandatory}$
    545         // caller's perspective of foo; callee's perspective of bar
     603int foo( int, float, char );                            $\C{// declaration, parameter names optional}$
     604int bar( int i, float f, char c ) {             $\C{// definition, parameter names mandatory}$
     605        // callee's perspective of foo and bar
    546606}
    547 // caller's perspectives of foo's and bar's
    548 \end{cfa}
    549 In caller's perspective, the parameter names (by virtue of being optional) are really comments;
    550 in the callee's perspective, parameter names are semantically significant.
     607// caller's perspectives of foo and bar
     608\end{cfa}
     609From the caller's perspective, the parameter names (by virtue of being optional) are (useful) comments;
     610From the callee's perspective, parameter names are semantically significant.
    551611Array parameters introduce a further, subtle, semantic difference and considerable freedom to comment.
    552612
    553613At the semantic level, there is no such thing as an array parameter, except for one case (@T [static 5]@) discussed shortly.
    554614Rather, there are only pointer parameters.
    555 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.
     615This 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.
    556616This fact holds in both the caller's and callee's perspectives.
    557 However, a parameter's type can include ``array of.'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
     617However, a parameter's type can include ``array of'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
    558618This 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.
    559 In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the flavour of parameter.
    560 
    561 Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
    562 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}.
    563 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.
     619In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the parameter flavour.
    564620
    565621\begin{figure}
    566 \begin{cquote}
    567622\begin{tabular}{@{}llll@{}}
    568623\begin{cfa}
    569624float sum( float a[5] );
    570 float sum( float a[5][4] );
     625float sum( float m[5][4] );
    571626float sum( float a[5][] );
    572627float sum( float a[5]* );
    … …  
    576631\begin{cfa}
    577632float sum( float a[] );
    578 float sum( float a[][4] );
     633float sum( float m[][4] );
    579634float sum( float a[][] );
    580635float sum( float a[]* );
    … …  
    584639\begin{cfa}
    585640float sum( float *a );
    586 float sum( float (*a)[4] );
     641float sum( float (*m)[4] );
    587642float sum( float (*a)[] );
    588643float sum( float (*a)* );
    … …  
    591646&
    592647\begin{cfa}
    593 // ar of float
    594 // mat of float
     648// array of float
     649// matrix of float
    595650// invalid
    596651// invalid
    597 // ar of ptr to float
    598 \end{cfa}
    599 \end{tabular}
    600 \end{cquote}
     652// array of ptr to float
     653\end{cfa}
     654\end{tabular}
    601655\caption{Multiple ways to declare an array parameter.
    602656Across a valid row, every declaration is equivalent.
    … …  
    606660\end{figure}
    607661
    608 In the leftmost style, the typechecker ignores the actual value in most practical cases.
    609 This value is allowed to be a dynamic expression, and then it has practical cases.
    610 \begin{cfa}
    611 void foo( int @n@ ) {
    612         float _42( float @a[n]@ ) {    // nested function
    613                 a[0] = 42;
    614         }
    615         float b[n];
    616         _42( b );
    617 }
     662Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
     663An 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}.
     664The 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.
     665Note, in the leftmost style, the typechecker ignores the actual value even in a dynamic expression.
     666\begin{cfa}
     667int N;
     668void foo( float @a[N] ) ; // N is ignored
    618669\end{cfa}
    619670
    … …  
    622673% 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 **@.
    623674
    624 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).
     675It 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'').
    625676
    626677Note that this equivalence of pointer and array declarations is special to parameters.
    … …  
    635686}
    636687\end{cfa}
    637 This equivalence has the consequence that the type system does not help a caller get it right.
     688Unfortunately, this equivalence has the consequence that the type system does not help a caller get it right.
    638689\begin{cfa}
    639690float sum( float v[] );
    … …  
    656707void foo( int [@const  volatile@ 5] );          $\C{// 5 is ignored}$
    657708\end{cfa}
    658 
    659709To make the first dimension size meaningful, C adds this form.
    660710\begin{cquote}
    … …  
    667717\end{cfa}
    668718Here, the @static@ storage qualifier defines the minimum array size for its argument.
    669 @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
     719Earlier versions of @gcc@ ($<$ 11) and possibly @clang@ ignore this dimension qualifier, while later versions implement the check, in accordance with the standard.
     720
    670721
    671722Note that there are now two different meanings for modifiers in the same position.  In
    … …  
    685736Here, the distance between the first and second elements of each array depends on the inner dimension size.
    686737
    687 This significance of an inner dimension's length is a fact of the callee's perspective.
    688 In the caller's perspective, the type sytem is quite lax.
     738The significance of an inner dimension's length is a fact of the callee's perspective.
     739In the caller's perspective, the type system is quite lax.
    689740Here, there is (some, but) little checking that what is being passed, matches.
    690741% void f( float [][10] );
    … …  
    709760\end{cfa}
    710761The 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.
    711 The cases @f(b)@ and @f(&a)@ show where some length checking occurs.
    712 But this checking misses the cases @f(d)@ and @f(&c)@, allowing the calls with mismatched lengths, actually 100 for 10.
     762The cases @f( b )@ and @f( &a )@ show where some length checking occurs.
     763But this checking misses the cases @f( d )@ and @f( &c )@, allowing the calls with mismatched lengths, actually 100 for 10.
    713764The C checking rule avoids false alarms, at the expense of safety, by allowing any combinations that involve dynamic values.
    714765Ultimately, 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.
    715766
    716 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.
     767Finally, 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.
    717768\begin{cquote}
    718769@[@ \textit{type-qualifier-list$_{opt}$} @* ]@
    … …  
    731782
    732783
    733 \subsection{Arrays could be values}
     784\subsection{Arrays Could be Values}
    734785
    735786All arrays have a know runtime size at their point of declaration.
    … …  
    751802\begin{cfa}
    752803Jmp_Buf jb1, jb2;
    753 jb1 = jb2;
     804jb1 = jb2;            // copy
    754805void foo( Jmp_Buf );
    755 foo( jb2 );
     806foo( jb2 );           // copy
    756807\end{cfa}
    757808
    758809This same argument applies to returning arrays from functions.
    759 There can be sufficient information to return an array by value but it is not supported.
    760 Again, array wrapping allows an array to be returned from a function and copied into variable.
     810There can be sufficient information to return an array by value but it is unsupported.
     811Again, array wrapping allows an array to be returned from a function and copied into a variable.
    761812
    762813
    … …  
    772823
    773824
    774 \subsection{Design issues}
     825\subsection{Design Issues}
    775826\label{toc:lst:issue}
    776827
    777828This thesis focuses on a reduced design space for linked lists that target \emph{system programmers}.
    778829Within this restricted space, all design-issue discussions assume the following invariants;
    779 alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
     830alternatives to the assumptions are discussed under Future Work (\VRef{toc:lst:futwork}).
    780831\begin{itemize}
    781832        \item A doubly-linked list is being designed.
    782833                Generally, the discussed issues apply similarly for singly-linked lists.
    783                 Circular \vs ordered linking is discussed under List identity (Section~\ref{toc:lst:issue:ident}).
     834                Circular \vs ordered linking is discussed under List identity (\VRef{toc:lst:issue:ident}).
    784835        \item Link fields are system-managed.
    785836                The user works with the system-provided API to query and modify list membership.
    … …  
    790841
    791842
    792 \subsection{Preexisting linked-list libraries}
     843\subsection{Preexisting Linked-List Libraries}
    793844\label{s:PreexistingLinked-ListLibraries}
    794845
    … …  
    799850        \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}
    800851\end{enumerate}
    801 %A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
     852%A general comparison of libraries' abilities is given under Related Work (\VRef{toc:lst:relwork}).
    802853For the discussion, assume the fictional type @req@ (request) is the user's payload in examples.
    803854As 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.
    804855
    805856
    806 \subsection{Link attachment: intrusive vs.\ wrapped}
     857\subsection{Link Attachment: Intrusive \vs Wrapped}
    807858\label{toc:lst:issue:attach}
    808859
    … …  
    837888                Three styles of link attachment: (a)~intrusive, (b)~wrapped reference, and (c)~wrapped value.
    838889                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
    839                 head objects are discussed in Section~\ref{toc:lst:issue:ident}.
     890                head objects are discussed in \VRef{toc:lst:issue:ident}.
    840891                In (a), the field \lstinline{req.x} names a list direction;
    841                 these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
     892                these are discussed in \VRef{toc:lst:issue:simultaneity}.
    842893                In (b) and (c), the type \lstinline{node} represents a system-internal type,
    843894                which is \lstinline{std::_List_node} in the GNU implementation.
    … …  
    889940                % \protect\subref*{f:Intrusive}~intrusive, \protect\subref*{f:WrappedRef}~wrapped reference, and \protect\subref*{f:WrappedValue}~wrapped value.
    890941                The diagrams show the memory layouts that result after the code runs, eliding the head object \lstinline{reqs};
    891                 head objects are discussed in Section~\ref{toc:lst:issue:ident}.
     942                head objects are discussed in \VRef{toc:lst:issue:ident}.
    892943                In \protect\subref*{f:Intrusive}, the field \lstinline{req.d} names a list direction;
    893                 these are discussed in Section~\ref{toc:lst:issue:simultaneity}.
     944                these are discussed in \VRef{toc:lst:issue:simultaneity}.
    894945                In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
    895946                library-internal type, which is \lstinline{std::_List_node} in the GNU implementation
    … …  
    905956In all three cases, a @req@ object can enter and leave a list many times.
    906957However, in intrusive a @req@ can only be on one list at a time, unless there are separate link-fields for each simultaneous list.
    907 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.
     958In 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.
    908959In wrapped value, the @req@ is copied, which increases storage usage, but allows independent simultaneous changes;
    909 however, knowing which of the @req@ object is the ``true'' object becomes complex.
     960however, knowing which of the @req@ object is the \emph{true} object becomes complex.
    910961\see*{\VRef{toc:lst:issue:simultaneity} for further discussion.}
    911962
    912963The implementation of @LIST_ENTRY@ uses a trick to find the links and the node containing the links.
    913 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.
     964The 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.
    914965One of the fields generated by @LIST_ENTRY@ is a pointer to the node, which is set to the node address, \eg @r2@.
    915966Hence, the offset to the link fields provides an access to the entire node, \ie the node points at itself.
    916 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.
     967For 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.
    917968The 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.
    918969
    … …  
    926977Another 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.
    927978In LQ, the intrusive @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
    928 there is no distinguishing a @req@ from ``a @req@ in a list.''
     979there is no distinguishing a @req@ from a @req@ in a list.
    929980The same is not true of STL, wrapped reference or value.
    930981There, the analogous operations, @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@, work on a parameter of type @list<T>::iterator@;
    … …  
    946997                the LQ C macros do not expand to valid C++ when instantiated with template parameters---there is no \lstinline{struct El}.
    947998                When using a custom-patched version of LQ to work around this issue,
    948                 the programs of Figure~\ref{f:WrappedRef} and wrapped value work with this shim in place of real STL.
     999                the programs of \VRef[Figure]{f:WrappedRef} and wrapped value work with this shim in place of real STL.
    9491000                Their executions lead to the same memory layouts.
    9501001        }
    … …  
    9521003\end{figure}
    9531004
    954 It is possible to simulate wrapped using intrusive, illustrated in Figure~\ref{fig:lst-issues-attach-reduction}.
     1005It is possible to simulate wrapped using intrusive, illustrated in \VRef[Figure]{fig:lst-issues-attach-reduction}.
    9551006This shim layer performs the implicit dynamic allocations that pure intrusion avoids.
    9561007But there is no reduction going the other way.
    … …  
    9611012An intrusive-primitive library like LQ lets users choose when to make this tradeoff.
    9621013A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
    963 
    964 
    965 \subsection{Simultaneity: single vs.\ multi-static vs.\ dynamic}
     1014\CFA is capable of supporting a wrapped library, if need arose.
     1015
     1016
     1017\subsection{Simultaneity: Single \vs Multi-Static \vs Dynamic}
    9661018\label{toc:lst:issue:simultaneity}
    9671019
    … …  
    9861038\newterm{Simultaneity} deals with the question:
    9871039In how many different lists can a node be stored, at the same time?
    988 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@).
     1040\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@).
    9891041Each of ``by priority'' and ``by common request value'' is a separate list.
    9901042For 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.
    … …  
    9961048This feature is used in the \CFA runtime, where a thread node may be on a blocked or running list, but never on both simultaneously.
    9971049
    998 Now consider the STL in the wrapped-reference arrangement of Figure~\ref{f:WrappedRef}.
     1050Now consider the STL in the wrapped-reference arrangement of \VRef[Figure]{f:WrappedRef}.
    9991051Here it is possible to construct the same simultaneity by creating multiple STL lists, each pointing at the appropriate nodes.
    10001052Each group of intrusive links become the links for each separate STL list.
    … …  
    10031055Note, it might be possible to wrap the multiple lists in another type to hide this implementation issue.
    10041056
    1005 Now consider the STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
     1057Now consider the STL in the wrapped-value arrangement of \VRef[Figure]{f:WrappedValue}.
    10061058Again, 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.
    10071059The upside is the same as for wrapped-reference arrangement with an unlimited number of list bindings.
    … …  
    10151067% LQ's ergonomics are well-suited to the uncommon case of multiple list directions.
    10161068% Its intrusion declaration and insertion operation both use a mandatory explicit parameter naming the direction.
    1017 % This decision works well in Figure~\ref{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
    1018 % but it clutters Figure~\ref{f:Intrusive}, where a contrived name must be invented and used.
     1069% This decision works well in \VRef[Figure]{fig:lst-issues-multi-static}, where the names @by_pri@ and @by_rqr@ work well,
     1070% but it clutters \VRef[Figure]{f:Intrusive}, where a contrived name must be invented and used.
    10191071% The example uses @x@; @reqs@ would be a more readily ignored choice. \PAB{wording?}
    10201072
    … …  
    10891141
    10901142
    1091 \subsection{User integration: preprocessed vs.\ type-system mediated}
    1092 
    1093 \PAB{What do you want to say here?}
     1143\subsection{User Integration: Preprocessed \vs Type-System Mediated}
     1144
     1145While 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.
     1146Hence, 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.
     1147This can lead to a cascade of error messages that are confusing and difficult to debug.
     1148For example, argument errors like @a.b,c@, comma instead of period, or @by-pri@, minus instead of underscore, can produce many error messages.
     1149
     1150Instead, language function calls (even with inlining) handled argument mistakes locally at the call, giving very specific error message.
     1151\CC @concepts@ were introduced in @templates@ to deal with just this problem.
    10941152
    10951153% example of poor error message due to LQ's preprocessed integration
    … …  
    11011159
    11021160
    1103 \subsection{List identity: headed vs.\ ad-hoc}
     1161\subsection{List Identity: Headed \vs Ad-Hoc}
    11041162\label{toc:lst:issue:ident}
    11051163
    1106 All examples so far use distinct user-facing types:
    1107 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}).
    1108 The latter type is a head.
    1109 The resulting identity model (empty list) is just the head.
    1110 A bespoke ``pointer to next @req@'' implementation often omits the header;
    1111 hence, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
    1112 The resulting identity model is ad-hoc.
    1113 
    1114 Figure~\ref{fig:lst-issues-ident} shows the identity model's impact on
    1115 the existence of certain conceptual constructs, like zero-lengths lists and unlisted elements.
    1116 In headed thinking, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
    1117 In ad-hoc thinking, there are no length-zero lists and every element belongs to a list of length at least one.
    1118 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.
     1164All examples so far use two distinct types for:
     1165an 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}).
     1166This kind of list is ``headed'', where the empty list is just a head.
     1167An alternate ``ad-hoc'' approach omits the header, where the empty list is no nodes.
     1168Here, a pointer to any node can traverse its link fields: right or left and around, depending on the data structure.
     1169Note, a headed list is superset of an ad-hoc list, and can normally perform all of the ad-hoc operations.
     1170\VRef[Figure]{fig:lst-issues-ident} shows both approaches for different list lengths and unlisted elements.
     1171For headed, there are length-zero lists (heads with no elements), and an element can be listed or not listed.
     1172For ad-hoc, there are no length-zero lists and every element belongs to a list of length at least one.
    11191173
    11201174\begin{figure}
    … …  
    11281182\end{figure}
    11291183
    1130 A head defines one or more element roles, among elements that share a transitive adjacency.
    1131 ``First'' and ``last'' are element roles.
    1132 One moment's ``first'' need not be the next moment's.
    1133 
    1134 There is a cost to maintaining these roles.
     1184The 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.
     1185For 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.
     1186Without the header, this specialized information must be managed explicitly, where the programmer builds their own external, equivalent header information.
     1187However, 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.
     1188Clearly, 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.
    11351189A runtime component of this cost is evident in LQ's offering the choice of type generators @LIST@ \vs @TAILQ@.
    1136 Its @LIST@ maintains a ``first,'' but not a ``last;'' its @TAILQ@ maintains both roles.
     1190Its @LIST@ maintains a \emph{first}, but not a \emph{last};
     1191its @TAILQ@ maintains both roles.
    11371192(Both types are doubly linked and an analogous choice is available for singly linked.)
    11381193
    1139 TODO: finish making this point
    1140 
    1141 See WIP in lst-issues-adhoc-*.ignore.*.
    1142 
    1143 The code-complexity component of the cost ...
    1144 
    1145 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.
    1146 
    1147 
    1148 \subsection{End treatment: cased vs.\ uniform }
    1149 
    1150 A linear (non-circular), nonempty linked-list has a first element and a last element, whether or not the list is headed.
    1151 A first element has no predecessor and a last element has no successor.
     1194
     1195\subsection{End Treatment: Cased \vs Uniform }
     1196
     1197All lists must have a logical \emph{beginning/ending}, otherwise list traversal is infinite.
     1198\emph{End treatment} refers to how the list represents the lack of a predecessor/successor to demarcate end point(s).
     1199For example, in a doubly-linked list containing a single node, the next/prev links have no successor/predecessor nodes.
     1200Note, a list does not need to use links to denote its size;
     1201it can use a node counter in the header, where $N$ node traversals indicates complete navigation of the list.
     1202However, managing the number of nodes is an additional cost, as the links must always be managed.
     1203
     1204The following discussion refers to the LQ representations, detailed in \VRef[Figure]{fig:lst-issues-end}, using a null pointer to mark end points.
     1205LQ uses this representation for its successor/last.
     1206For example, consider the operation of inserting after a given element.
     1207A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
     1208This step must happen when the given node has a successor (when its successor pointer is non-null),
     1209and must be skipped when it does not (when its successor pointer cannot be navigated).
     1210So this operation contains a branch, to decide which case is happening.
     1211All branches have pathological cases where branch prediction's success rate is low and the execution pipeline stalls often.
     1212Hence, this issue is relevant to achieving high performance.
    11521213
    11531214\begin{figure}
    … …  
    11641225\end{figure}
    11651226
    1166 End treatment refers to how the list represents the lack of a predecessor/successor.
    1167 The following elaboration refers to the LQ representations, detailed in Figure~\ref{fig:lst-issues-end}.
    1168 The most obvious representation, a null pointer, mandates a cased end treatment.
    1169 LQ uses this representation for its successor/last.
    1170 Consider the operation of inserting after a given element.
    1171 A doubly-linked list must update the given node's successor, to make its predecessor-pointer refer to the new node.
    1172 This step must happen when the given node has a successor (when its successor pointer is non-null),
    1173 and must be skipped when it does not (when its successor pointer cannot be navigated).
    1174 So this operation contains a branch, to decide which case is happening.
    1175 All branches have pathological cases where branch prediction's success rate is low and the execution pipeline is stalling often.
    1176 Hence, this issue is implementation-level, relevant to achieving high performance.
    1177 
    1178 This branch is sometimes avoidable; the result is a uniform end treatment.
    1179 Here is one example of such an implementation that works for a headed list.
    1180 LQ uses this representation for its predecessor/first.  (All LQ offerings are headed at the front.)
     1227Interestingly, this branch is sometimes avoidable, giving a uniform end-treatment in the code.
     1228For example, LQ is headed at the front.
    11811229For predecessor/first navigation, the relevant operation is inserting before a given element.
    11821230LQ's predecessor representation is not a pointer to a node, but a pointer to a pseudo-successor pointer.
    11831231When there is a predecessor node, that node contains a real-successor pointer; it is the target of the reference node's predecessor pointer.
    11841232When there is no predecessor node, the reference node (now known to be first node) acts as the pseudo-successor of the list head.
    1185 The list head contains a pointer to the first node.
     1233Now, the list head contains a pointer to the first node.
    11861234When inserting before the first node, the list head's first-pointer is the one that must change.
    1187 So, the first node's ``predecessor'' pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
     1235So, the first node's \emph{predecessor} pointer (to a pseudo-successor pointer) is set as the list head's first-pointer.
    11881236Now, inserting before a given element does the same logic in both cases:
    1189 follow the guaranteed-non-null predecessor pointer, and update what you find there to refer to the new node.
     1237follow the guaranteed-non-null predecessor pointer, and update that location to refer to the new node.
    11901238Applying this trick makes it possible to have list management routines that are completely free of conditional control-flow.
    11911239Considering a path length of only a few instructions (less than the processor's pipeline length),

  • doc/theses/mike_brooks_MMath/benchmarks/list/_classic.c

    rf632bd50 rb195498  
    232232        for ( t = 0; t < Times; t += 1 ) {
    233233                Repeat( insert_last( lst, s[i] ) );
    234                 Repeat( remove( lst`first ) );
     234                Repeat( remove( first( lst ) ) );
    235235        }
    236236        end = clock();

  • doc/theses/mike_brooks_MMath/benchmarks/list/fx-cfa-cfa.h

    rf632bd50 rb195498  
    1111#define BFX_INSERT_BEFORE(S, lst, item, refIter) (insert_before(*refIter, item), (S*)&(item))
    1212#define BFX_INSERT_AFTER(S, lst, item, refIter)  (insert_after (*refIter, item), (S*)&(item))
    13 #define BFX_REMOVE_FIRST(S, lst)                 remove(lst`first)
    14 #define BFX_REMOVE_LAST(S, lst)                  remove(lst`last)
     13#define BFX_REMOVE_FIRST(S, lst)                 remove( first( lst ) )
     14#define BFX_REMOVE_LAST(S, lst)                  remove( last( lst ) )
    1515#define BFX_REMOVE_HERE(S, lst, refIter)         remove(*refIter)
    1616#define BFX_INIT(S, lst)
    1717
    18 #define BFX_GET_AFTER(S, lst, iter)              (&(*iter)`next)
    19 #define BFX_GET_BEFORE(S, lst, iter)             (&(*iter)`prev)
     18#define BFX_GET_AFTER(S, lst, iter)              (&next( *iter))
     19#define BFX_GET_BEFORE(S, lst, iter)             (&prev( *iter ))
    2020#define BFX_IS_VALID_POS(S, lst, iter)           ((iter)!=NULL)
    2121#define BFX_DEREF_POS(S, lst, iter)              (iter)

  • doc/theses/mike_brooks_MMath/conclusion.tex

    rf632bd50 rb195498  
    77\section{Strings}
    88
    9 \section{Future work}
     9\section{Future Work}

  • doc/theses/mike_brooks_MMath/intro.tex

    rf632bd50 rb195498  
    2727
    2828
    29 \section{Linked list}
     29\section{Linked List}
    3030
    3131A linked-list provides a homogeneous container often with $O(log N)$ or $O(N)$ access to elements using successor and predecessor operations that normally involve pointer chasing.
    … …  
    4242hash search table consisting of a key (string) with associated data (@<search.h>@)
    4343\end{itemize}
    44 Because these libraries are simple, awkward to use, and unsafe, C programmers commonly build linked-list behaviours into their bespoke data structures.
     44Because these libraries are simple, awkward to use, and unsafe, C programmers commonly build bespoke linked data-structures.
    4545
    4646
    … …  
    5454In some cases, string management is separate from heap management, \ie strings roll their own heap.
    5555
    56 The C string type requires user storage-management of a language-provided character array.
     56The C string type is just a character array and requires user storage-management to handle varying size.
    5757The character array uses the convention of marking its (variable) array length by placing the 0-valued control character at the end (null-terminated).
    5858The C standard library includes a number of high-level operations for working with this representation.
     59Most of these operations are awkward and error prone.
    5960
    6061
    … …  
    8485While multiple new languages purport to be systems languages replacing C, the reality is that rewriting massive C code-bases is impractical and a non-starter if the new runtime uses garage collection.
    8586Furthermore, new languages must still interact with the underlying C operating system through fragile, type-unsafe, interlanguage-communication.
    86 Switching to \CC is equally impractical as its complex and interdependent type-system (\eg objects, overloading, inheritance, templates) means idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
     87Switching to \CC is equally impractical as its complex and interdependent type-system (\eg objects, overloading, inheritance, templates) means idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning new \CC.
    8788Hence, rewriting and retraining costs for these languages can be prohibitive for companies with a large C software-base (Google, Apple, Microsoft, Amazon, AMD, Nvidia).
    8889
    … …  
    9394However, most programming languages are only partially explained by their standard's manual(s).
    9495When it comes to explaining how C works, the definitive source is the @gcc@ compiler, which is mimicked by other C compilers, such as Clang~\cite{clang}.
    95 Often other C compilers must mimic @gcc@ because a large part of the C library (runtime) system (@glibc@ on Linux) contains @gcc@ features.
     96Often other C compilers \emph{must} mimic @gcc@ because a large part of the C library (runtime) system (@glibc@ on Linux) contains @gcc@ features.
    9697Some key aspects of C need to be explained and understood by quoting from the language reference manual.
    9798However, to illustrate actual program semantics, this thesis constructs multiple small programs whose behaviour exercises a particular point and then confirms the behaviour by running the program using multiple @gcc@ compilers.
    … …  
    100101        \item if the compiler accepts or rejects certain syntax,
    101102        \item prints output to buttress a behavioural claim,
    102         \item or executes without triggering any embedded assertions testing pre/post-assertions or invariants.
     103        \item or fails to trigger embedded assertions testing pre/post-assertions or invariants.
    103104\end{itemize}
    104105These programs are tested across @gcc@ versions 8--14 and clang versions 10--14 running on ARM, AMD, and Intel architectures.
    … …  
    120121Introduce a small number of subtle changes to the typing rules for the C array, while still achieving significant backwards compatibility
    121122\item
    122 Create a new polymorphic mechanism into the \CFA @forall@ clause for specifying array dimension values, similar to a fixed-typed parameter in a \CC \lstinline[language=C++]{template}.
     123Create a new polymorphic mechanism in the \CFA @forall@ clause to specify array dimension values, similar to a fixed-typed parameter in a \CC \lstinline[language=C++]{template}.
    123124\item
    124125Construct a new standard-library array-type, available through @#include <array.hfa>@.
    … …  
    130131
    131132
    132 \subsection{Linked list}
     133\subsection{Linked List}
    133134
    134135The linked list is a new runtime library, available through @#include <dlist.hfa>@.
    … …  
    141142\subsection{String}
    142143
    143 The string is a new runtime library, available through @#include <string.hfa>@.
     144The new string type and its runtime library are available through @#include <string.hfa>@.
    144145The library offers a type where basic usage is comparable to the \CC @string@ type, including analogous coexistence with raw-character pointers.
    145146Its implementation, however, follows different principles, enabling programs to work with strings by value, without incurring excessive copying.
    146147Mutability is retained.
    147148Substrings are supported, including the ability for overlapping ranges to share edits transparently.
    148 Ultimately, the implementation is a set of strings rolled into their own specialized heap.
     149The implementation allows a set of strings to use an optimized, shared, custom heap or to use the regular heap for thread safety.
    149150
    150 The string library includes writing and reading strings via the preexisting \CFA I/O stream library.
    151 Enabling transparent reading (of unknown length into a managed allocation) included revision of the stream library's existing handling of character arrays.
    152 All reasonable stream manipulators are supported, \eg width, justification (left/right), printing characters as their numeric values, and complex input scanning to isolate strings.
     151The string library includes reading and writing strings via the preexisting \CFA I/O stream library.
     152Enabling transparent reading of unknown length strings using managed allocation required revision of the stream library's existing handling of character arrays.
     153All reasonable stream manipulators are supported, \eg width, justification (left/right), printing characters as their numeric values, and complex input scanning to isolate strings in the input stream.
    153154
    154155
    … …  
    159160Hence, the infamous \CC bug of iterator invalidation, where structural changes cause legitimate operations to fail, \eg iterator over a list and deleting each element.
    160161
    161 Further design provides a home for Liskov-style iterators in \CFA.
     162Further design provides a home for Liskov-style iterators (stackless-coroutine) in \CFA.
    162163This design extends a preexisting proposal to adapt the \CFA (fixed) for-each loop to be more user-pluggable, and builds upon preexisting \CFA coroutines.
    163164Overall, it simplifies the work a programmer must do to leverage the suspended-state abstraction during iteration.

  • doc/theses/mike_brooks_MMath/list.tex

    rf632bd50 rb195498  
    1515
    1616The doubly-linked list attaches links intrusively, supports multiple link directions, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head.
    17 This design covers system and data management issues stated in Section~\ref{toc:lst:issue}.
    18 
    19 Figure~\ref{fig:lst-features-intro} continues the running @req@ example from Figure~\ref{fig:lst-issues-attach} using the \CFA list.
    20 The \CFA link attachment is intrusive so the resulting memory layout is per user node, as for the LQ version of Figure~\ref{f:Intrusive}.
     17This design covers system and data management issues stated in \VRef{toc:lst:issue}.
     18
     19\VRef[Figure]{fig:lst-features-intro} continues the running @req@ example from \VRef[Figure]{fig:lst-issues-attach} using the \CFA list.
     20The \CFA link attachment is intrusive so the resulting memory layout is per user node, as for the LQ version of \VRef[Figure]{f:Intrusive}.
    2121The \CFA framework provides generic type @dlink( T, T )@ for the two link fields (front and back).
    2222A user inserts the links into the @req@ structure via \CFA inline-inheritance from the Plan-9 C dialect~\cite[\S~3.3]{Thompson90new}.
    … …  
    3434    \caption[Multiple link directions in \CFA list library]{
    3535        Demonstration of the running \lstinline{req} example, done using the \CFA list library.
    36         This example is equivalent to the three approaches in Figure~\ref{fig:lst-issues-attach}.
     36        This example is equivalent to the three approaches in \VRef[Figure]{fig:lst-issues-attach}.
    3737    }
    3838    \label{fig:lst-features-intro}
    3939\end{figure}
    4040
    41 Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously.
     41\VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously.
    4242The declaration of @req@ has two inline-inheriting @dlink@ occurrences.
    4343The first of these gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
    … …  
    4848The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@, meaning operations called on @reqs_pri_global@ are implicitly disambiguated.
    4949In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we are working by priority.''
    50 As in Figure~\ref{fig:lst-issues-multi-static}, three lists are constructed, a priority list containing all nodes, a list with only nodes containing the value 42, and a list with only nodes containing the value 17.
     50As in \VRef[Figure]{fig:lst-issues-multi-static}, three lists are constructed, a priority list containing all nodes, a list with only nodes containing the value 42, and a list with only nodes containing the value 17.
    5151
    5252\begin{figure}
    … …  
    6363\caption{
    6464        Demonstration of multiple static link directions done in the \CFA list library.
    65         The right example is from Figure~\ref{fig:lst-issues-multi-static}.
     65        The right example is from \VRef[Figure]{fig:lst-issues-multi-static}.
    6666                The left \CFA example does the same job.
    6767    }
    … …  
    7070
    7171The \CFA library also supports the common case, of single directionality, more naturally than LQ. 
    72 Figure~\ref{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
    73 where Figure~\ref{f:Intrusive} adds the unnecessary field name, @d@.
    74 In \CFA, a user doing a single direction (Figure~\ref{fig:lst-features-intro}) sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist( T )@.
    75 In contrast, (Figure~\ref{fig:lst-features-multidir}) sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist( T, DIR )@.
     72\VRef[Figure]{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
     73where \VRef[Figure]{f:Intrusive} adds the unnecessary field name, @d@.
     74In \CFA, a user doing a single direction (\VRef[Figure]{fig:lst-features-intro}) sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist( T )@.
     75In contrast, (\VRef[Figure]{fig:lst-features-multidir}) sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist( T, DIR )@.
    7676
    7777The directionality issue also has an advanced corner-case that needs treatment.
    … …  
    118118By using a larger scope, a user can put code within that acts as if there is only one list direction.
    119119This boost is needed only when operating on a list with several directions, using operations that do not take the list head.
    120 Otherwise, the sole applicable list direction ``just works.''
     120Otherwise, the sole applicable list direction \emph{just works}.
    121121
    122122Unlike \CC templates container-types, the \CFA library works completely within the type system;
    … …  
    138138@isEmpty@ returns true if the list has no nodes and false otherwise.
    139139\item
    140 @first@ returns a pointer to the first node of the list without removing it or @0p@ if the list is empty.
    141 \item
    142 @last@ returns a pointer to the last node of the list without removing it or @0p@ if the list is empty.
    143 \item
    144 @next@ returns a pointer to the next (successor, towards last) node after the specified node or @0p@ if the specified node is the last node in the list.
    145 \item
    146 @pred@ returns a pointer to the previous (predecessor, towards first) node before the specified node or @0p@ if the specified node is the first node in the list.
     140@first@ returns a reference to the first node of the list without removing it or @0p@ if the list is empty.
     141\item
     142@last@ returns a reference to the last node of the list without removing it or @0p@ if the list is empty.
    147143\item
    148144@insert_before@ adds a node before the specified node and returns the added node for cascading.
    … …  
    150146@insert_after@ adds a node after the specified node and returns the added node for cascading.
    151147\item
    152 @remove@ removes the specified node from the list (any location) and returns a pointer to the node.
    153 \item
    154 @insert_first@ adds a node to the start of the list so it becomes the first node and returns a pointer to the node for cascading.
    155 \item
    156 @insert_last@ adds a node to the end of the list so it becomes the last node and returns returns a pointer to the node for cascading.
    157 \item
    158 @insert@ is a synonym for @insert_last@.
    159 \item
    160 @remove_first@ removes the first node and returns a pointer to it or @0p@ if the list is empty.
    161 \item
    162 @remove_last@ removes the last node and returns a pointer to it or @0p@ if the list is emptyy.
     148@remove@ removes the specified node from the list (any location) and returns a reference to the node.
     149\item
     150@iter@ create an iterator for the list.
     151\item
     152@recede@ returns true if the iterator cursor is advanced to the previous (predecessor, towards first) node before the prior cursor node and false otherwise.
     153\item
     154@advance@ returns true if the iterator cursor is advanced to the next (successor, towards last) node after the prior cursor node and false otherwise.
     155\item
     156@isFirst@ returns true if the node is the first node in the list and false otherwise.
     157\item
     158@isLast@ returns true if the node is the last node in the list and false otherwise.
     159\item
     160@pred@ returns a reference to the previous (predecessor, towards first) node before the specified node or @0p@ if the specified node is the first node in the list.
     161\item
     162@next@ returns a reference to the next (successor, towards last) node after the specified node or @0p@ if the specified node is the last node in the list.
     163\item
     164@insert_first@ adds a node to the start of the list so it becomes the first node and returns a reference to the node for cascading.
     165\item
     166@insert_last@ adds a node to the end of the list so it becomes the last node and returns returns a reference to the node for cascading.
     167\item
     168@remove_first@ removes the first node and returns a reference to it or @0p@ if the list is empty.
     169\item
     170@remove_last@ removes the last node and returns a reference to it or @0p@ if the list is empty.
    163171\item
    164172@transfer@ transfers all nodes from the @from@ list to the end of the @to@ list; the @from@ list is empty after the transfer.
    … …  
    170178\begin{figure}
    171179\begin{cfa}
    172 E & ?`isEmpty( dlist( E ) & list );
    173 E & ?`isListed( E & node );
    174 E & ?`first( dlist( E ) & list );
    175 E & ?`last( dlist( E ) & list );
    176 E & ?`next( E & node );
    177 E & ?`prev( E & node );
     180E & isListed( E & node );
     181E & isEmpty( dlist( E ) & list );
     182E & first( dlist( E ) & list );
     183E & last( dlist( E ) & list );
    178184E & insert_before( E & before, E & node );
    179185E & insert_after( E & after, E & node );
    180186E & remove( E & node );
    181 E & ?`elems( dlist( E ) & list );
    182 E & ?`head( dlist( E ) & list );
    183 bool ?`moveNext( E && refx );
    184 bool ?`next( E && refx );                                                       // alternate name
    185 bool ?`movePrev( E && refx );
    186 bool ?`prev( E && refx );                                                       // alternate name
    187 bool ?`hasNext( E & node );
    188 bool ?`hasPrev( E & node );
     187E & iter( dlist( E ) & list );
     188bool advance( E && refx );
     189bool recede( E && refx );
     190bool isFirst( E & node );
     191bool isLast( E & node );
     192E & prev( E & node );
     193E & next( E & node );
    189194E & insert_first( dlist( E ) & list, E & node );
    190195E & insert_last( dlist( E ) & list, E & node );
    191 E & insert( dlist( E ) & list, E & node );              // alternate name
    192196E & remove_first( dlist( E ) & list );
    193197E & remove_last( dlist( E ) & list );
    194198void transfer( dlist( E ) & to, dlist( E ) & from ) {
    195199void split( dlist( E ) & to, dlist( E ) & from, E & node ) {
    196 E & try_pop_front( dlist( E ) & list );
    197 E & try_pop_back( dlist( E ) & list );
    198200\end{cfa}
    199201\caption{\CFA List API}
    … …  
    205207
    206208It is possible to iterate through a list manually or using a set of standard macros.
    207 \VRef[Figure]{f:IteratorExample} shows the iterator template, managing a list of nodes, used throughout the following iterator examples.
     209\VRef[Figure]{f:IteratorTemple} shows the iterator template, managing a list of nodes, used throughout the following iterator examples.
    208210Each example assumes its loop body prints the value in the current node.
    209211
    … …  
    222224        insert( list, n1 );   insert( list, n2 );   insert( list, n3 );   insert( list, n4 );
    223225        sout | nlOff;
    224         for ( node & it = list`first; &it; &it = &it`next ) @sout | it.v | ",";   sout | nl;@
    225         // other iterator examples
     226        for ( ... ) @sout | it.v | ",";   sout | nl;@ // iterator examples in text
    226227        remove( n1 );   remove( n2 );   remove( n3 );   remove( n4 );
    227228}
    228229\end{cfa}
    229 \caption{Iterator Example}
    230 \label{f:IteratorExample}
     230\caption{Iterator Temple}
     231\label{f:IteratorTemple}
    231232\end{figure}
    232233
    … …  
    243244\begin{tabular}{@{}l|l@{}}
    244245\begin{cfa}
    245 for ( node & it = list`@first@; &it /* != 0p */ ; &it = &it`@next@ ) ...
    246 for ( node & it = list`@last@; &it; &it = &it`@prev@ ) ...
     246for ( node & it = @first@( list ); &it /* != 0p */ ; &it = &@next@( it ) ...
     247for ( node & it = @last@( list ); &it; &it = &@prev@( it ) ) ...
    247248\end{cfa}
    248249&
    … …  
    258259\begin{tabular}{@{}l|l@{}}
    259260\begin{cfa}
    260 for ( node & it = @n2@; &it; &it = &it`@next@ ) ...
    261 for ( node & it = @n3@; &it; &it = &it`@prev@ ) ...
     261for ( node & it = @n2@; &it; &it = &@next@( it ) ) ...
     262for ( node & it = @n3@; &it; &it = &@prev@( it ) ) ...
    262263\end{cfa}
    263264&
    … …  
    268269\end{tabular}
    269270\end{cquote}
    270 Iterating forward and reverse from a starting node to an ending node through the remaining list.
    271 \begin{cquote}
    272 \setlength{\tabcolsep}{15pt}
    273 \begin{tabular}{@{}l|l@{}}
    274 \begin{cfa}
    275 for ( node & it = @n2@; &it @!= &n4@; &it = &it`@next@ ) ...
    276 for ( node & it = @n4@; &it @!= &n2@; &it = &it`@prev@ ) ...
     271Iterating forward and reverse from a starting node to an ending node through the contained list.
     272\begin{cquote}
     273\setlength{\tabcolsep}{15pt}
     274\begin{tabular}{@{}l|l@{}}
     275\begin{cfa}
     276for ( node & it = @n2@; &it @!= &n4@; &it = &@next@( it ) ) ...
     277for ( node & it = @n4@; &it @!= &n2@; &it = &@prev@( it ) ) ...
    277278\end{cfa}
    278279&
    … …  
    284285\end{cquote}
    285286Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a direction.
    286 In this case, @next@ and @prev@ return a boolean, like \CC @while ( cin >> i )@.
    287 \begin{cquote}
    288 \setlength{\tabcolsep}{15pt}
    289 \begin{tabular}{@{}l|l@{}}
    290 \begin{cfa}
    291 for ( node & it = list`@head@; it`@next@; ) ...
    292 for ( node & it = list`@head@; it`@prev@; ) ...
     287In this case, @advance@ and @recede@ return a boolean, like \CC @while ( cin >> i )@.
     288\begin{cquote}
     289\setlength{\tabcolsep}{15pt}
     290\begin{tabular}{@{}l|l@{}}
     291\begin{cfa}
     292for ( node & it = @iter@( list ); @advance@( it ); ) ...
     293for ( node & it = @iter@( list ); @recede@( it ); ) ...
    293294\end{cfa}
    294295&
    … …  
    330331\end{tabular}
    331332\end{cquote}
    332 The ability to provide a language-level @foreach@ is a future \CFA project.
     333Macros are not ideal, so future work is to provide a language-level @foreach@ statement, like \CC.
    333334Finally, a predicate can be added to any of the manual iteration loops.
    334335\begin{cquote}
    … …  
    336337\begin{tabular}{@{}l|l@{}}
    337338\begin{cfa}
    338 for ( node & it = list`first; &it @&& !(it.v == 3)@; &it = &it`next ) ...
    339 for ( node & it = list`last; &it @&& !(it.v == 1)@; &it = &it`prev ) ...
    340 for ( node & it = list`head; it`next @&& !(it.v == 3)@; ) ...
    341 for ( node & it = list`head; it`prev @&& !(it.v == 1)@; ) ...
     339for ( node & it = first( list ); &it @&& !(it.v == 3)@; &it = &next( it ) ) ...
     340for ( node & it = last( list ); &it @&& !(it.v == 1)@; &it = &prev( it ) ) ...
     341for ( node & it = iter( list ); advance( it ) @&& !(it.v == 3)@; ) ...
     342for ( node & it = iter( list ); recede( it ) @&& !(it.v == 1)@; ) ...
    342343\end{cfa}
    343344&
    … …  
    439440
    440441
    441 
    442442\section{Implementation}
    443 
    444 \subsection{Links}
    445443
    446444\VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, now showing the \CFA list library's internal representation.
    447445The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque to a user.
    448 Even though the user-facing list model is ordered (linear), the CFA library implements all listing as circular.
     446Even though the user-facing list model is linear, the CFA library implements all listing as circular.
    449447This choice helps achieve uniform end treatment and TODO finish summarizing benefit.
    450448A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@.
    … …  
    460458\end{figure}
    461459
    462 Link pointers are internally tagged according to whether the link is user-visible.
    463 Links among user-requested neighbours are left natural, with the tag bit not set.
    464 System-added links, which produce the circular implementation, have the tag bit set.
     460System-added link pointers (dashed lines) are internally tagged to indicate linear endpoints that are the circular pointers.
     461Links among neighbour nodes are not tagged.
    465462Iteration reports ``has more elements'' when crossing natural links, and ``no more elements'' upon reaching a tagged link.
    466463
    467464In a headed list, the list head (@dlist(req)@) acts as an extra element in the implementation-level circularly-linked list.
    468 The content of a @dlist@ is a (private) @dlink@, with the @next@ pointer purposed for the first element, and the @prev@ pointer purposed for the last element.
    469 Since the head wraps a @dlink@, since a @req@ does too, and since a link-pointer targets a @dlink@, the resulting cycle is among @dlink@ structures, situated inside of other things.
    470 The tags on the links say what the wrapper is: untagged (user link) means the targeted @dlink@ is within a @req@, while tagged (system link) means the targeted @dlink@ is within a list head.
    471 
    472 In a headless list, the circular backing list is only among @dlink@s within @req@s.  The tags are set on the links that a user cannot navigate.
    473 
    474 No distinction is made between an unlisted item under a headed model and a singleton list under a headless model.  Both are represented as an item referring to itself, with both tags set.
    475 
     465The content of a @dlist@ is a (private) @dlink@, with the @next@ pointer to the first element, and the @prev@ pointer to the last element.
     466Since the head wraps a @dlink@, as does a @req@ does too, and since a link-pointer targets a @dlink@, the resulting cycle is among @dlink@ structures, situated inside of header/node.
     467An untagged pointer points within a @req@, while a tagged pointer points within a list head.
     468In a headless list, the circular backing list is only among @dlink@s within @req@s.
     469The tags are set on the links that a user cannot navigate.
     470
     471No distinction is made between an unlisted item under a headed model and a singleton list under a headless model.
     472Both are represented as an item referring to itself, with both tags set.
    476473
    477474

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

    rf632bd50 rb195498  
    1414
    1515int main() {
    16         float ar[3][10];
    17         static_assert( sizeof(float) == 4 );    $\C{// floats (atomic elements) are 4 bytes}$
    18         static_assert( sizeof(void*) == 8 );    $\C{// pointers are 8 bytes}$
     16        float mx[3][10];
     17        static_assert( sizeof(float) == 4 );    $\C[3.25in]{// floats (atomic elements) are 4 bytes}$
     18        static_assert( sizeof(void *) == 8 );   $\C{// pointers are 8 bytes}$
    1919
    20         static_assert( sizeof(ar) == 120 );             $\C{// the array, float[3][10]}$
    21         static_assert( sizeof(ar[0]) == 40 );   $\C{// its first element, float[10]}$
    22         static_assert( sizeof(ar[0][0]) == 4 ); $\C{// its first grand element, float}$
     20        static_assert( sizeof(mx) == 120 );             $\C{// the array, float[3][10]}$
     21        static_assert( sizeof(mx[0]) == 40 );   $\C{// its first element, float[10]}$
     22        static_assert( sizeof(mx[0][0]) == 4 ); $\C{// its first grand element, float}$
    2323
    24         static_assert( sizeof(&(ar)) == 8 );    $\C{// pointer to the array, float(*)[3][10]}$
    25         static_assert( sizeof(&(ar[0])) == 8 ); $\C{// pointer to its first element, float(*)[10]}$
    26         static_assert( sizeof(&(ar[0][0])) == 8 );      $\C{// pointer to its first grand-element, float*}$
     24        static_assert( sizeof(&(mx)) == 8 );    $\C{// pointer to the array, float(*)[3][10]}$
     25        static_assert( sizeof(&(mx[0])) == 8 ); $\C{// pointer to its first element, float(*)[10]}$
     26        static_assert( sizeof(&(mx[0][0])) == 8 );      $\C{// pointer to its first grand-element, float*}\CRT$
    2727
    28         float (*pa)[3][10] = &(ar);
    29         float (*pa0)[10] = &(ar[0]);
    30         float *pa00 = &(ar[0][0]);
     28        float (*pm)[3][10] = &(mx);
     29        float (*pm0)[10] = &(mx[0]);
     30        float *pm00 = &(mx[0][0]);
    3131
    32         static_assert( (void*)&ar == (void*)&(ar[0] ) );
    33         static_assert( (void*)&ar == (void*)&(ar[0][0]) );
     32        static_assert( (void *)&mx == (void *)&(mx[0] ) );
     33        static_assert( (void *)&mx == (void *)&(mx[0][0]) );
    3434
    35         assert( (void *) pa == (void *) pa0 );
    36         assert( (void *) pa == (void *) pa00 );
     35        assert( (void *) pm == (void *) pm0 );
     36        assert( (void *) pm == (void *) pm00 );
    3737
    3838//      float (*b[3])[10];
    39         float *b[3];
     39        float * b[3];
    4040        for (int i = 0; i < 3; i ++) {
    4141                b[i] = malloc(sizeof(float[10]));
    4242        }
    43         ar[2][3];
     43        mx[2][3];
    4444        b[2][3];
    4545/*

  • doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa

    rf632bd50 rb195498  
    5050
    5151
    52 while( req & cur = reqs`elems; cur`moveNext )
     52        while( req & cur = iter( reqs ); advance( cur ) )
    5353        printf("{%d %d} ", cur.pri, cur.rqr);
    5454printf("\n");

  • doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa

    rf632bd50 rb195498  
    7979
    8080with(DLINK_VIA(req, req.by_pri)) {
    81         while( req & cur = reqs_pri_global`elems; cur`moveNext )
     81        while( req & cur = iter( reqs_pri_global ); advance( cur ) )
    8282                printf("{%d %d} ", cur.pri, cur.rqr);
    8383        printf("| ");
    … …  
    8585
    8686with(DLINK_VIA(req, req.by_rqr)) {
    87         while( req & cur = reqs_rqr_42`elems; cur`moveNext )
     87        while( req & cur = iter( reqs_rqr_42 ); advance( cur ) )
    8888                printf("{%d %d} ", cur.pri, cur.rqr);
    8989        printf("| ");
    90         while( req & cur = reqs_rqr_17`elems; cur`moveNext )
     90        while( req & cur = iter( reqs_rqr_17 ); advance( cur ) )
    9191                printf("{%d %d} ", cur.pri, cur.rqr);
    9292        printf("| ");
    93         while( req & cur = reqs_rqr_99`elems; cur`moveNext )
     93        while( req & cur = iter( reqs_rqr_99 ); advance( cur ) )
    9494                printf("{%d %d} ", cur.pri, cur.rqr);
    9595        printf("\n");
Note: See TracChangeset for help on using the changeset viewer.