Changeset 4740281

TabularUnified doc/theses/mike_brooks_MMath/list.tex ¶

-                      r15eebd4
+                      r4740281
 \chapter{Linked List}
+I wrote a linked-list library for \CFA.  This chapter describes it.
+The library provides a doubly-linked list that
+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.
+TODO: more summary
+This chapter presents my work on designing and building a linked-list library for \CFA.
+Due to time limitations and the needs expressed by the \CFA runtime developers, I focussed on providing a doubly-linked list, and its bidirectionally iterators for traversal.
+Simpler data-structures, like stack and queue, can be built from the doubly-linked mechanism with only a slight storage/performance cost because of the unused link field.
+Reducing to data-structures with a single link follows directly from the more complex doubly-links and its iterators.
 \section{Features}
+The following features directed this project, where the goal is high-performance list operations required by \CFA runtime components, like the threading library.
 \subsection{Core Design Issues}
+This section reviews how a user experiences my \CFA list library's position on the issues of Section~\ref{toc:lst:issue}.
+The library provides a doubly-linked list that
+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.
+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.}
+These links have a nontrivial, user-specified location within the @req@ structure;
+this convention encapsulates the implied pointer arithmetic safely.
+The 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.
+This design covers system and data management issues stated in Section~\ref{toc:lst:issue}.
+Figure~\ref{fig:lst-features-intro} continues the running @req@ example from Figure~\ref{fig:lst-issues-attach} using the \CFA list.
+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}.
+The \CFA framework provides generic type @dlink( T, T )@ for the two link fields (front and back).
+A user inserts the links into the @req@ structure via \CFA inline-inheritance from the Plan-9 C dialect~\cite[\S~3.3]{Thompson90new}.
+Inline inheritance is containment, where the inlined field is unnamed but the type's internal fields are hoisted into the containing structure.
+Hence, the field names must be unique, unlike \CC nested types, but the type names are at a nested scope level, unlike aggregate nesting in C.
+Note, the position of the containment is normally unimportant, unless there is some form of memory or @union@ overlay.
+The key feature of inlined inheritance is that a pointer to the containing structure is automatically converted to a pointer to any anonymous inline field for assignments and function calls, providing containment inheritance with implicit subtyping.
+Therefore, a reference to a @req@ is implicitly convertible to @dlink@ in assignments and function calls.
+% These links have a nontrivial, user-specified location within the @req@ structure;
+% this convention encapsulates the implied pointer arithmetic safely.
+The links in @dlist@ point at (links) in the containing node, know the offsets of all links (data is abstract), and any field-offset arithmetic or link-value changes are safe and abstract.
 \begin{figure}
     \lstinput{20-32}{lst-features-intro.run.cfa}
+    \lstinput{20-30}{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.
+        This example is equivalent to the three approaches in Figure~\ref{fig:lst-issues-attach}.
+    }
     \label{fig:lst-features-intro}
 \end{figure}
+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.
+The declaration of @req@ has two inline-inheriting @dlink@ occurrences.
+The first of these 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: @reqs_pri_global@, @reqs_rqr_42@, @reqs_rqr_17@, and @reqs_rqr_99@.
+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 are working by priority.''
+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.
 \begin{figure}
 …
 \begin{tabular}{@{}ll@{}}
 \begin{tabular}{@{}l@{}}
     \lstinput{20-25}{lst-features-multidir.run.cfa} \\
     \lstinput{40-67}{lst-features-multidir.run.cfa}
+    \lstinput{20-31}{lst-features-multidir.run.cfa} \\
+    \lstinput{43-71}{lst-features-multidir.run.cfa}
     \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}.
+        The right example is from Figure~\ref{fig:lst-issues-multi-static}.
+                The left \CFA example does the same job.
+    }
     \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, 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 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{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(...)@.
+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)@.
+where Figure~\ref{f:Intrusive} adds the unnecessary field name, @d@.
+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 )@.
+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 )@.
 The directionality issue also has an advanced corner-case that needs treatment.
 When working with multiple directions, while calls like @insert_first@ benefit from implicit direction disambiguation, other calls like @insert_after@ still require explicit disambiguation.
 It happens because the call
+When working with multiple directions, calls like @insert_first@ benefit from implicit direction disambiguation;
+however, other calls like @insert_after@ still require explicit disambiguation, \eg the call
 \begin{cfa}
 insert_after(r1, r2);
 \end{cfa}
 does not have enough information to clarify which of a request's simultaneous list directions is intended.
 Is @r2@ supposed to be the next-priority request after @r1@, or is @r2@ supposed to join the same-requestor list of @r1@?
+Is @r2@ supposed to be the next-priority request after @r1@, or is @r2@ supposed to join the same-requester list of @r1@?
 As such, the \CFA compiler gives an ambiguity error for this call.
 To let the programmer resolve the ambiguity, the list library provides a hook for applying the \CFA language's scoping and priority rules.
+To resolve the ambiguity, the list library provides a hook for applying the \CFA language's scoping and priority rules.
 It applies as:
 \begin{cfa}
 with ( DLINK_VIA(req, req.pri) ) insert_after(r1, r2);
 \end{cfa}
+Here, importing (using the @with@ syntax on) the @DLINK_VIA@ result causes one of the list directions to become a more attrictive candidate to \CFA's overload resolution.
+This boost applies within the scope of the the import, which is a single line in the example just given, but could also be a custom block or an entire function body.
+\noindent
+\begin{tabular}{ll}
+\begin{cfa}
+void f() with ( DLINK_VIA(req, req.pri) ) {
+    ...
+    insert_after(r1, r2);
+    ...
+Here, the @with@ statement opens the scope of the object type for the expression;
+hence, the @DLINK_VIA@ result causes one of the list directions to become a more attractive candidate to \CFA's overload resolution.
+This boost applies within the scope of the following statement, but could also be a custom block or an entire function body.
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+void f() @with( DLINK_VIA(req, req.pri) )@ {
+        ...
+        insert_after(r1, r2);
+        ...
+}
 \end{cfa}
 …
 \begin{cfa}
 void f() {
     ...
     with ( DLINK_VIA(req, req.pri) ) {
         ...
+    }
     ...
+        ...
+        @with( DLINK_VIA(req, req.pri) )@ {
+                ...  insert_after(r1, r2);  ...
+        }
+        ...
+}
 \end{cfa}
 \end{tabular}
+\noindent
+By doing in on a larger scope, a user can put code within that acts as if there is only one list direction.
+This boost is needed only when operating on a list with several directions, using operations that do not take list heads.
+\end{cquote}
+By using a larger scope, a user can put code within that acts as if there is only one list direction.
+This boost is needed only when operating on a list with several directions, using operations that do not take the list head.
 Otherwise, the sole applicable list direction ``just works.''
+The \CFA library offers a type-system mediated integration with user code.
+The examples presented do not use preprocessor macros.
+The touchpoints @dlink@ and @dlist@ are ordinary types.
+Even though they are delivered as header-included static-inline implementations,
+the \CFA compiler typechecks the list library code separately from user code.
+Unlike \CC templates container-types, the \CFA library works completely within the type system;
+both @dlink@ and @dlist@ are ordinary types.
+There is no textual expansion other than header-included static-inline function for performance.
 Errors in user code are reported only with mention of the library's declarations.
+Finally, the library is separately compiled from the usage code.
 The \CFA library works in headed and headless modes.  TODO: elaborate.
 …
 \subsection{Iteration}
 Many languages offer an iterator interface for collections to implement, and a corresponding for-each loop syntax for consuming the items through implicit interface calls.
+Many languages offer an iterator interface for collections, and a corresponding for-each loop syntax for consuming the items through implicit interface calls.
 \CFA does not yet have a general-purpose form of such a feature, though it has a form that addresses some use cases.
 This section shows why the incumbemt \CFA pattern does not work for linked lists and gives the alternative now offered by the linked-list libary.
+This section shows why the incumbent \CFA pattern does not work for linked lists and gives the alternative now offered by the linked-list library.
 Chapter 5 [TODO: deal with optimism here] presents a design that satisfies both uses and accommodates even more complex collections.
+The incumbent \CFA extensible loop syntax is:
+\begin{cfa}
+The current \CFA extensible loop syntax is:
+\begin{cfa}
+for( elem; end )
 for( elem; begin ~ end )
+for( elem; end )
+\end{cfa}
+Many derived forms of @begin ~ end@ exist, but they of primaty interest to defining numeric ranges, so they are excluded from the linked-list discussion.
+This ``two-place for'' syntax abbreviates, respectively:
+\begin{cfa}
+for( typeof(end) elem = begin; elem < end; elem += 1 )
+for( typeof(end) elem = 0; elem < end; elem += 1 )
+\end{cfa}
+From these calls, letting @E@ be @typeof(end)@, the implied interface is:
+\begin{itemize}
+\item
+    case-appropriate construction: one of @void ?{}( E &, typeof(begin) )@, or @void ?{}( E &, zero_t )@, depending on the specific loop form
+\item
+    comparison, for termination testing: @int ?<?( const E &, const E & )@
+\item
+    increment, for ``next item'': @E & ?+=?( E &, one_t )@
+\end{itemize}
+The shortened loop works well for using a numeric range to step through an array:
+\begin{cfa}
+for ( i; n ) total += a[i];
+\end{cfa}
+When used for array-stepping, the loop is acting like JavaScript's @for...in@ construct,
+for( elem; begin ~ end ~ step )
+\end{cfa}
+Many derived forms of @begin ~ end@ exist, but are used for defining numeric ranges, so they are excluded from the linked-list discussion.
+These three forms are rely on the iterative trait:
+\begin{cfa}
+forall( T ) trait Iterate {
+        void ?{}( T & t, zero_t );
+        int ?<?( T t1, T t2 );
+        int ?<=?( T t1, T t2 );
+        int ?>?( T t1, T t2 );
+        int ?>=?( T t1, T t2 );
+        T ?+=?( T & t1, T t2 );
+        T ?+=?( T & t, one_t );
+        T ?-=?( T & t1, T t2 );
+        T ?-=?( T & t, one_t );
+}
+\end{cfa}
+where @zero_t@ and @one_t@ are constructors for the constants 0 and 1.
+The simple loops above are abbreviates for:
+\begin{cfa}
+for( typeof(end) elem = @0@; elem @<@ end; elem @+=@ @1@ )
+for( typeof(begin) elem = begin; elem @<@ end; elem @+=@ @1@ )
+for( typeof(begin) elem = @0@; elem @<@ end; elem @+=@ @step@ )
+\end{cfa}
+which use a subset of the trait operations.
+The shortened loop works well for iterating a number of times or through an array.
+\begin{cfa}
+for ( 20 ) // 20 iterations
+for ( i: 1 ~= 21 ~ 2 ) // odd numbers
+for ( i; n ) total += a[i]; // subscripts
+\end{cfa}
+which is similar to other languages, like JavaScript.
 \begin{cfa}
 for ( i in a ) total += a[i];
 \end{cfa}
+albeit with different mechanisms for expressing the array's length.
+But the similarity is that the loop binds the declared identifier (@i@) to the array's \emph{indeces}, not its contained values.
+A linked list has only values, no keys.
+So, to seek iteration of a linked list via the existing loop syntax is to ask whether this syntax can also do double-duty for iterating values.
+Albeit with different mechanisms for expressing the array's length.
+It might be possible to take the \CC iterator:
+\begin{c++}
+for ( list<int>::iterator it=mylist.begin(); it != mylist.end(); ++it )
+\end{c++}
+and convert it to the \CFA form
+\begin{cfa}
+for ( it; begin() ~= end() )
+\end{cfa}
+by having a list operator @<=@ that just looks for equality, and @+=@ that moves to the next node, \etc.
+However, the list usage is contrived, because a list does use its data values for relational comparison, only links for equality comprison.
+Hence, the focus of a list iterator's stopping condition is fundamentally different.
+So, iteration of a linked list via the existing loop syntax is to ask whether this syntax can also do double-duty for iterating values.
 That is, to be an analog of JavaScript's @for..of@ syntax:
 \begin{cfa}
 …
 Advantages of this change include being able to pass ranges to functions, for example, projecting a numerically regular subsequence of array entries, and being able to use the loop syntax to cover more collection types, such as looping over the keys of a hashtable.
+When iteratig an empty list, the question, ``Is there a further element?'' needs to be posed once, receiving the answer, ``no.''
+When iterating an empty list, the question, ``Is there a further element?'' needs to be posed once, receiving the answer, ``no.''
 When iterating an $n$-item list, the same question gets $n$ ``yes'' answers (one for each element), plus one ``no'' answer, once there are no more elements; the question is posed $n+1$ times.
 When iteratig an empty list, the question, ``What is the value of the current element?'' is never posed, nor is the command, ``Move to the next element,'' issued.  When iterating an $n$-item list, each happens $n$ times.
+When iterating an empty list, the question, ``What is the value of the current element?'' is never posed, nor is the command, ``Move to the next element,'' issued.  When iterating an $n$-item list, each happens $n$ times.
 So, asking about the existence of an element happens once more than retrieving an element's value and advancing the position.
 …
 TODO: deal with spontaneous simultaneity, like a single-axis req, put into an array: which ``axis'' is @&req++@ navigating: array-adjacency vs link dereference.  It should sick according to how you got it in the first place: navigating dlist(req, req.pri) vs navigating array(req, 42).  (prob. future work)
 \section{Implementation}
 …
 \VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, now showing the \CFA list library's internal representation.
+The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque to a user.
+Even though the user-facing list model is ordered (linear), the CFA library implements all listing as circular.
+This choice helps achieve uniform end treatment and TODO finish summarizing benefit.
+A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@.
+(Recall, the running example has the user putting a @dlink@ within a @req@.)
 \begin{figure}
 …
 \end{figure}
+The @dlink@ structure contains exactly two pointers: @next@ and @prev@.  This @dlink@ content is opaque to the user.
+Even though the user-facing list model is ordered (linear), the CFA library implements all listing as circular.
+This choice helps achieve uniform end treatment and TODO finish summarizing benefit.
+A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@.
+(Recall, the running example has the user putting a @dlink@ within a @req@.)
+Link pointers are tagged according to whether the link is user-visible.
+Link pointers are internally tagged according to whether the link is user-visible.
 Links among user-requested neighbours are left natural, with the tag bit not set.
 System-added links, which produce the circular implementation, have the tag bit set.
 …
 In a headed list, the list head (@dlist(req)@) acts as an extra element in the implementation-level circularly-linked list.
 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.
 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@ strucures, situated inside of other things.
+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.
 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.
 In a headless list, the cicular backing list is only among @dlink@s within @req@s.  The tags are set on the links that a user cannot navigate.
+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.
 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.
 …
 \label{toc:lst:futwork}
+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.
+\begin{cfa}
+struct mary {
+        float anotherdatum;
+        inline dlink(mary);
+};
+struct fred {
+        float adatum;
+        inline struct mine { inline dlink(fred); };
+        inline struct yours { inline dlink(fred); };
+};
+\end{cfa}
+like in the thesis examples.  You have to say
+\begin{cfa}
+struct mary {
+        float anotherdatum;
+        inline dlink(mary);
+};
+P9_EMBEDDED(mary, dlink(mary))
+struct fred {
+        float adatum;
+        inline struct mine { inline dlink(fred); };
+        inline struct yours { inline dlink(fred); };
+};
+P9_EMBEDDED(fred, fred.mine)
+P9_EMBEDDED(fred, fred.yours)
+P9_EMBEDDED(fred.mine, dlink(fred))
+P9_EMBEDDED(fred.yours, dlink(fred))
+\end{cfa}
+like in tests/list/dlist-insert-remove.
+Future work should autogen those @P9_EMBEDDED@ declarations whenever it sees a plan-9 declaration.
+The exact scheme chosen should harmonize with general user-defined conversions.
+Today's P9 scheme is:  mary gets a function `inner returning this as dlink(mary).
+Fred gets four of them in a diamond.
+They're defined so that `inner is transitive; i.e. fred has two further ambiguous overloads mapping fred to dlink(fred).
+The scheme allows the dlist functions to give the assertion, "we work on any T that gives a `inner to dlink(T)."
 TODO: deal with: A doubly linked list is being designed.

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

-                      r15eebd4
+                      r4740281
 struct req {
         int pri, rqr;
         inline dlink(req);
+        inline dlink(req);              // containment inheritance, fields hoisted into structure
 };
 dlist(req) reqs;
+req
+        r1 = {1, 42},
+        r2 = {2, 42};
+req r1 = {1, 42}, r2 = {2, 42};
 insert_first(reqs, r2);
 insert_first(reqs, r1);

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

-                      r15eebd4
+                      r4740281
 // need to spice this case; can't forward declare nested struct
 P9_EMBEDDED_INFUNC(req, req.by_pri)
 …
 P9_EMBEDDED_INFUNC(req.by_pri, dlink(req))
 P9_EMBEDDED_INFUNC(req.by_rqr, dlink(req))

Context Navigation

Legend:

TabularUnified doc/theses/mike_brooks_MMath/list.tex ¶

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

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

Download in other formats: