Index: doc/theses/mike_brooks_MMath/list.tex =================================================================== --- doc/theses/mike_brooks_MMath/list.tex (revision 0d41e600f9eaba42a581f99e01c510016cd805bb) +++ doc/theses/mike_brooks_MMath/list.tex (revision e86735ba792af3d1f8cd52cf612e489ab650c080) @@ -1,49 +1,52 @@ \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} @@ -51,6 +54,6 @@ \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} & @@ -60,53 +63,43 @@ \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} @@ -114,24 +107,22 @@ \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. @@ -141,42 +132,62 @@ \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 ??( 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::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} @@ -193,11 +204,8 @@ 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. @@ -209,4 +217,5 @@ 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} @@ -214,4 +223,9 @@ \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} @@ -224,13 +238,5 @@ \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. @@ -239,8 +245,8 @@ 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. @@ -251,4 +257,45 @@ \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. Index: doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa =================================================================== --- doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa (revision 0d41e600f9eaba42a581f99e01c510016cd805bb) +++ doc/theses/mike_brooks_MMath/programs/lst-features-intro.run.cfa (revision e86735ba792af3d1f8cd52cf612e489ab650c080) @@ -20,15 +20,15 @@ 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); + + Index: doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa =================================================================== --- doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa (revision 0d41e600f9eaba42a581f99e01c510016cd805bb) +++ doc/theses/mike_brooks_MMath/programs/lst-features-multidir.run.cfa (revision e86735ba792af3d1f8cd52cf612e489ab650c080) @@ -28,4 +28,6 @@ + + // need to spice this case; can't forward declare nested struct P9_EMBEDDED_INFUNC(req, req.by_pri) @@ -33,4 +35,6 @@ P9_EMBEDDED_INFUNC(req.by_pri, dlink(req)) P9_EMBEDDED_INFUNC(req.by_rqr, dlink(req)) + +