Context Navigation

← Previous Changeset
Next Changeset →

Changeset 5d9c4bb

Timestamp:

Mar 22, 2023, 11:34:45 AM (20 months ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

ADT, ast-experimental, master

Children:

1d245ea, d63aeba

Parents:

Message:

proofread Mike's list chapter

Location:

doc/theses/mike_brooks_MMath

Files:

: 2 edited

list.tex (modified) (18 diffs)
uw-ethesis.tex (modified) (4 diffs)

Legend:

: Unmodified
: Added
: Removed

doc/theses/mike_brooks_MMath/list.tex

-                      r1f771fc
+                      r5d9c4bb
 \section{Design Issues}
 \label{toc:lst:issue}
 …
 All design-issue discussions assume the following invariants.
+They are stated here to clarify that none of the discussed design issues refers to one of these.
+\PAB{They are stated here to clarify that none of the discussed design issues refers to one of these.}
 Alternatives to the assumptions are discussed under Future Work (Section~\ref{toc:lst:futwork}).
 \begin{itemize}
 …
           The system has freedom over how to represent these links.
           The library is not providing applied wrapper operations that consume a user's hand-implemented list primitives.
     \item These issues are compared at a requirement/functional level.
+    \item \PAB{These issues are compared at a requirement/functional level.}
 \end{itemize}
 Two preexisting linked-list libraries are used throughout, to show examples of the concepts being defined,
 and further libraries are introduced as needed.
-A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
 \begin{description}
     \item[LQ] Linux Queue library\cite{lst:linuxq} of @<sys/queue.h>@.
     \item[STL] C++ Standard Template Library's @std::list@\cite{lst:stl}
 \end{description}
+A general comparison of libraries' abilities is given under Related Work (Section~\ref{toc:lst:relwork}).
 The fictional type @req@ (request) is the user's payload in examples.
 …
 The wrapped style admits the further distinction between wrapping a reference and wrapping a value.
 This distinction is pervasive in all STL collections; @list<req*>@ wraps a reference; @list<req>@ wraps a value.
 (For this discussion, @list<req&>@ is similar to @list<req*>@.)
+This distinction is pervasive in all STL collections; @list<req *>@ wraps a reference; @list<req>@ wraps a value.
+(For this discussion, @list<req &>@ is similar to @list<req *>@.)
 This difference is one of user style, not framework capability.
+Figure~\ref{fig:lst-issues-attach} compares the three styles.
+\begin{comment}
 \begin{figure}
     \begin{tabularx}{\textwidth}{Y|Y|Y}\lstinputlisting[language=C  , firstline=20, lastline=39]{lst-issues-intrusive.run.c}
 …
         (a) & (b) & (c)
     \end{tabularx}
     \caption{
+\caption{
         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};
 …
         (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
+    }
+     \label{fig:lst-issues-attach}
+\end{figure}
+\end{comment}
+\begin{figure}
+\centering
+\newsavebox{\myboxA}                                    % used with subfigure
+\newsavebox{\myboxB}
+\newsavebox{\myboxC}
+\begin{lrbox}{\myboxA}
+\begin{tabular}{@{}l@{}}
+\lstinputlisting[language=C, firstline=20, lastline=39]{lst-issues-intrusive.run.c} \\
+\ \\
+\includegraphics[page=1]{lst-issues-attach.pdf}
+\end{tabular}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{tabular}{@{}l@{}}
+\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-byref.run.cpp} \\
+\ \\
+\includegraphics[page=2]{lst-issues-attach.pdf}
+\end{tabular}
+\end{lrbox}
+\begin{lrbox}{\myboxC}
+\begin{tabular}{@{}l@{}}
+\lstinputlisting[language=C++, firstline=20, lastline=39]{lst-issues-wrapped-emplaced.run.cpp} \\
+\ \\
+\includegraphics[page=3]{lst-issues-attach.pdf}
+\end{tabular}
+\end{lrbox}
+\subfloat[Intrusive]{\label{f:Intrusive}\usebox\myboxA}
+\hspace{10pt}
+\vrule
+\hspace{10pt}
+\subfloat[Wrapped reference]{\label{f:WrappedRef}\usebox\myboxB}
+\hspace{10pt}
+\vrule
+\hspace{10pt}
+\subfloat[Wrapped value]{\label{f:WrappedValue}\usebox\myboxC}
+\caption{
+        Three styles of link attachment: \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}.
+        In \protect\subref*{f:Intrusive}, the field \lstinline{req.x} names a list direction;
+        these are discussed in Section~\ref{toc:lst:issue:derection}.
+        In \protect\subref*{f:WrappedRef} and \protect\subref*{f:WrappedValue}, the type \lstinline{node} represents a
+        system-internal type, which is \lstinline{std::_List_node} in the GNU implementation.
+        (TODO: cite? found in  /usr/include/c++/7/bits/stl\_list.h )
+    }
     \label{fig:lst-issues-attach}
 \end{figure}
-Figure~\ref{fig:lst-issues-attach} compares the three styles.
 The advantage of intrusive attachment is the control that it gives the user over memory layout.
 …
 Both wrapped attachment styles imply system-induced heap allocations.
 Such an allocation has a lifetime that matches the item's membership in the list.
 In (a) and (b), one @req@ object can enter and leave a list many times.
 In (b), doing do implies a dynamic allocation for each time joining; in (a), it does not.
+In \subref*{f:Intrusive} and \subref*{f:WrappedRef}, one @req@ object can enter and leave a list many times.
+In \subref*{f:WrappedRef}, it implies a dynamic allocation/deallocation for each enter/leave; in \subref*{f:Intrusive}, it does not.
 A further aspect of layout control is allowing the user to specify the location of the link fields within the @req@ object.
 …
 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, (a), a @req@ pointer is the right argument type for operations @LIST_NEXT@ or @LIST_REMOVE@;
+In LQ, \subref*{f:Intrusive}, a @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.''
 The same is not true of STL, (b) or (c).
+The same is not true of STL, \subref*{f:WrappedRef} or \subref*{f:WrappedValue}.
 There, the analogous operations work on a parameter of type @list<T>::iterator@;
 they are @iterator::operator++()@, @iterator::operator*()@, and @list::erase(iterator)@.
 There is no mapping from @req&@ to @list<req>::iterator@, except for linear search.
+There is no mapping from @req &@ to @list<req>::iterator@, except for linear search.
 The advantage of wrapped attachment is the abstraction of a data item from its list membership(s).
 In the wrapped style, the @req@ type can come from a library that serves many independent uses,
 which generally have no need for listing.
 Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @re@ library.
+Then, a novel use can still put @req@ in a (further) list, without requiring any upstream change in the @req@ library.
 In intrusive attachment, the ability to be listed must be planned during the definition of @req@.
+Similarly, style (b) allows for one @req@ to occur at several positions in one list.
+Styles (a) and (c) do not support this ability.
+Similarly, style \subref*{f:WrappedRef} allows for one @req@ to occur at several positions in one list.
+Styles \subref*{f:Intrusive} and \subref*{f:WrappedValue} do not support this ability.
+\PAB{But style \subref*{f:WrappedValue} can sort of mimic this effect by have multiple copies of \lstinline{req} in the list, modulo changes to the copies are not seen by the original.}
 \begin{figure}
 …
         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{fig:lst-issues-attach}~(b) and (c) work with this shim in place of real STL.
+        the programs of Figure~\ref{f:WrappedRef} and \protect\subref*{f:WrappedValue} work with this shim in place of real STL.
         Their executions lead to the same memory layouts.
+    }
 …
 So intrusion is a lower-level listing primitive.
 And so, the system design choice is not between forcing users to use intrusion and forcing them to use wrapping.
+And so, the system design choice is not between forcing users to use intrusion or wrapping.
 The choice is whether or not to provide access to an allocation-free layer of functionality.
 A wrapped-primitive library like STL forces users to incur the costs of wrapping, whether or not they access its benefits.
 …
 \subsection{Directionality: Single vs.\ Multi-Static vs.\ Dynamic}
 \label{toc:lst:issue:derection}
+\PAB{I'm not sure about the term \newterm{Directionality}. Directionality to me, means going forward or backwards through a list.
+Would \newterm{dimensionality} work? Think of each list containing the node as a different dimension in which the node sits.}
 Directionality deals with the question:
 In how many different lists can an item be stored, at a given time?
+Consider STL in the wrapped-value arrangement of Figure~\ref{fig:lst-issues-attach}~(c).
+Consider STL in the wrapped-value arrangement of Figure~\ref{f:WrappedValue}.
 The STL API completely hides its @node@ type from a user; the user cannot configure this choice or impose a custom one.
 STL's @node@ type offers the sole set of links shown in the diagram.
 Therefore, every @req@ in existence was allocated either to belong to an occurrence of the diagrammed arrangement,
+Therefore, every @req@ in existence is allocated either to belong to an occurrence of the diagrammed arrangement,
 or to be apart from all occurrences of it.
 In the first case, the @req@ belongs to exactly one list (of the style in question).
 …
 \begin{figure}
-    \label{fig:lst-issues-multi-static}
     \parbox[t]{3.5in} {
         \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c}
 …
         The zoomed-in diagram portion shows the field-level state that results from running the LQ code.
+    }
+    \label{fig:lst-issues-multi-static}
 \end{figure}
 …
 The corresponding flexibility of wrapped attachment means
 the STL wrapped-reference arrangement supports an item being a member of arbitrarily many lists.
 This support also applies to the hybrid in which an item's allocation is within a wrapped-value list,
+This support also applies to the wrapped-value list because the @req@ is copied,
 but wrapped-reference lists provide further link directions.
+\PAB{Explain how}
 STL with wrapped references supports dynamic link directions.
+When allowing multiple static directions,frameworks differ in their ergonomics for
+the typical case, when the user needs only one direction, vs.\ the atypical case, when the user needs several.
+\PAB{Expand}
+When allowing multiple static directions, frameworks differ in their ergonomics for
+the typical case: when the user needs only one direction, vs.\ the atypical case, when the user needs several.
 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{fig:lst-issues-attach}~(a), where a contrived name must be invented and used.
 The example uses @x@; @reqs@ would be a more readily ignored choice.
+but it clutters Figure~\ref{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?}
 \uCpp offers an intrusive list that makes the opposite choice.  TODO: elaborate on inheritance for first direction and acrobatics for subsequent directions.
 \subsection{User integration: Preprocessed vs.\ Type-System Mediated}
 % example of poor error message due to LQ's preprocessed integration
 % programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or ‘(’ before ‘do’
+% programs/lst-issues-multi-static.run.c:46:1: error: expected identifier or '(' before 'do'
 %    46 | LIST_INSERT_HEAD(&reqs_rtr_42, &r42b, by_rqr);
 %       | ^~~~~~~~~~~~~~~~
 …
 an item found in a list (type @req@, of variables like @r1@), and
 a list (type @reql@ or @list<req>@, of variables like @reqs@ or @reqs_rqr_42@).
+The latter type is a head, and these examples are of are headed lists.
+\see{Figure~\ref{fig:lst-issues-attach} and Figure~\ref{fig:lst-issues-multi-static}}
+The latter type is a head, and these examples are of headed lists.
 A bespoke ``pointer to next @req@'' implementation often omits the latter type.
 …
 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.
+\PAB{Create a figure for this.}
 By omitting the head, elements can enter into an adjacency relationship,
 …
 identifies a list using an explicit head.
+\begin{figure}
+    \label{fig:lst-features-intro}
+    \lstinputlisting[language=CFA, firstline=20, lastline=32]{lst-features-intro.run.cfa}
+    \caption[Multiple link directions in \CFA list library]{
+        Demonstration of the running \lstinline{req} example, done using the \CFA list library\protect\footnotemark.
+        This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways.
+    }
+\end{figure}
+\footnotetext{
+The \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}.
+Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{f:Intrusive}.
+The framework-provided type @dlink(...)@ provides the links.
+The user inserts the links into the @req@ structure by using \CFA inline-inheritance (TODO: reference introduction).
+Inline inheritance means the type of the field is @dlink(req)@, the field is unnamed, a reference to a @req@ is implicitly convertible to @dlink@.\footnote{
     The \CFA list examples elide the \lstinline{P9_EMBEDDED} annotations that (TODO: xref P9E future work) proposes to obviate.
     Thus, these examples illustrate a to-be state, free of what is to be historic clutter.
     The elided portions are immaterial to the discussion and the examples work with the annotations provided.
+    The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.
+}.
+My \CFA list library's version of the running @req@ example is in Figure~\ref{fig:lst-features-intro}.
+Its link attachment is intrusive and the resulting memory layout is pure-stack, just as for the LQ version of Figure~\ref{fig:lst-issues-attach}-(a).
+The framework-provided type @dlink(-)@ provides the links.
+The user puts links into the @req@ structure by inline-inheriting (TODO: reference introduction) this type.
+Which means: the type of the field is @dlink(req)@; the field is unnamed; a reference to a @req@ is implicitly convertible to @dlink@.
+As these links have a nontrivial, user-specified location within the @req@ structure, this conversion also encapsulates the implied pointer arithmetic safely.
+\begin{figure}
+    \label{fig:lst-features-multidir}
+    \lstinputlisting[language=CFA, firstline=20, lastline=25]{lst-features-multidir.run.cfa}
+    The \CFA test suite (TODO:cite?) includes equivalent demonstrations, with the annotations included.}
+These links have a nontrivial, user-specified location within the @req@ structure;
+this convention encapsulates the implied pointer arithmetic safely.
+\begin{figure}
+    \lstinputlisting[language=CFA, firstline=20, lastline=32]{lst-features-intro.run.cfa}
+    \caption[Multiple link directions in \CFA list library]{
+        Demonstration of the running \lstinline{req} example, done using the \CFA list library.
+        This example does the same job that Figure~\ref{fig:lst-issues-attach} shows three ways.
+    }
+    \label{fig:lst-features-intro}
+\end{figure}
+\begin{figure}
+\centering
+\begin{tabular}{@{}ll@{}}
+\begin{tabular}{@{}l@{}}
+    \lstinputlisting[language=CFA, firstline=20, lastline=25]{lst-features-multidir.run.cfa} \\
     \lstinputlisting[language=CFA, firstline=40, lastline=67]{lst-features-multidir.run.cfa}
+    \caption{
+    \end{tabular}
+        &
+        \lstinputlisting[language=C++, firstline=20, lastline=60]{lst-issues-multi-static.run.c}
+        \end{tabular}
+\caption{
         Demonstration of multiple static link directions done in the \CFA list library.
         This example does the same job as Figure~\ref{fig:lst-issues-multi-static}.
+    }
+\end{figure}
+The \CFA library supports multi-static link directionality.  Figure~\ref{fig:lst-features-multidir} illustrates how.
+    \label{fig:lst-features-multidir}
+\end{figure}
+Figure~\ref{fig:lst-features-multidir} shows how the \CFA library supports multi-static link directionality.
 The declaration of @req@ now has two inline-inheriting @dlink@ occurrences.
 The first of these lines gives a type named @req.by_pri@; @req@ inherits from it; it inherits from @dlink@.
 The second line gives a similar @req.by_rqr@.
+The first of these lines gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@.
+The second line @req.by_rqr@ is similar to @req.by_pri@.
 Thus, there is a diamond, non-virtual, inheritance from @req@ to @dlink@, with @by_pri@ and @by_rqr@ being the mid-level types.
 Disambiguation occurs in the declarations of the list-head objects.
 The type of the variable @reqs_pri_global@ is @dlist(req, req.by_pri)@,
 meaning operations called on @reqs_pri_global@ are implicitly disambiguated.
 In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we're working by priority.''
+In the example, the calls @insert_first(reqs_pri_global, ...)@ imply, ``here, we are working by priority.''
 The \CFA library also supports the common case, of single directionality, more naturally than LQ.
 Figure~\ref{fig:lst-features-intro} shows a single-direction list done with no contrived name for the link direction,
 where Figure~\ref{fig:lst-issues-attach}-(a) adds the unnecessary name, @x@.
+where Figure~\ref{f:Intrusive} adds the unnecessary name, @x@.
 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(-)@.
+sets up a simple inheritance with @dlink@, and declares a list head to have the simpler type @dlist(...)@.
 While a user doing multiple link directions (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(-, DIR)@.
+sets up a diamond inheritance with @dlink@, and declares a list head to have the more-informed type @dlist(..., DIR)@.
 The \CFA library offers a type-system mediated integration with user code.
 …
 \subsection{Iteration}

doc/theses/mike_brooks_MMath/uw-ethesis.tex

-                      r1f771fc
+                      r5d9c4bb
 % For hyperlinked PDF, suitable for viewing on a computer, use this:
 \documentclass[letterpaper,12pt,titlepage,oneside,final]{book}
+\usepackage{times}
 \usepackage[T1]{fontenc}        % Latin-1 => 256-bit characters, => | not dash, <> not Spanish question marks
 …
 \usepackage{comment} % Removes large sections of the document.
 \usepackage{tabularx}
+\usepackage{subfigure}
+\usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig}
+\renewcommand\thesubfigure{(\alph{subfigure})}
 \usepackage{algorithm}
 \usepackage{algpseudocode}
-\usepackage{pbox}
 % Hyperlinks make it very easy to navigate an electronic document.
 …
     citecolor=blue,        % color of links to bibliography
     filecolor=magenta,      % color of file links
+    urlcolor=blue           % color of external links
+    urlcolor=blue,           % color of external links
+    breaklinks=true
+}
 \ifthenelse{\boolean{PrintVersion}}{   % for improved print quality, change some hyperref options
 …
 \CFAStyle                                               % CFA code-style
 \lstset{language=CFA}                                   % default language
 \lstset{basicstyle=\linespread{0.9}\tt}                 % CFA typewriter font
+\lstset{basicstyle=\linespread{0.9}\sf}                 % CFA typewriter font
 \lstset{inputpath={programs}}
 \newcommand{\PAB}[1]{{\color{red}PAB: #1}}
+\newcommand{\uCpp}{$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}}}
+\newcommand{\uCpp}{$\mu$\CC}
 %======================================================================

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

Download in other formats: