source: doc/theses/mike_brooks_MMath/list.tex@ 3c1e432

\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



\section{Features}

\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.

\begin{figure}
    \lstinput{20-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@{}}
    \lstinput{20-25}{lst-features-multidir.run.cfa} \\
    \lstinput{40-67}{lst-features-multidir.run.cfa}
    \end{tabular}
        &
        \lstinput[language=C++]{20-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}.
    }
    \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)@.

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
\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@?
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.
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);

    ...
}
\end{cfa}
&
\begin{cfa}
void f() {
    ...
    with ( DLINK_VIA(req, req.pri) ) {
        ...
    }
    ...
}
\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.
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.
Errors in user code are reported only with mention of the library's declarations.

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.
\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.
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}
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,
\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.
That is, to be an analog of JavaScript's @for..of@ syntax:
\begin{cfa}
for ( e of a ) total += e;
\end{cfa}

The \CFA team will likely implement an extension of this functionality that moves the @~@ syntax from being part of the loop, to being a first-class operator (with associated multi-pace operators for the elided derived forms).
With this change, both @begin ~ end@ and @end@ (in context of the latter ``two-place for'' expression) parse as \emph{ranges}, and the loop syntax becomes, simply:
\begin{cfa}
    for( elem; rangeExpr )
\end{cfa}
The expansion and underlying API are under discussion.
TODO: explain pivot from ``is at done?'' to ``has more?''
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 $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.

So, asking about the existence of an element happens once more than retrieving an element's value and advancing the position.

Many iteration APIs deal with this fact by splitting these steps across different functions, and relying on the user's knowledge of iterator state to know when to call each.  In Java, the function @hasNext@ should be called $n+1$ times and @next@ should be called $n$ times (doing the double duty of advancing the iteration and returning a value).  In \CC, the jobs are split among the three actions, @it != end@, @it++@ and @*it@, the latter two being called one time more than the first.

TODO: deal with simultaneous axes: @DLINK_VIA@ just works

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}

\subsection{Links}

\VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, now showing the \CFA list library's internal representation.

\begin{figure}
        \centering
        \includegraphics{lst-impl-links.pdf}
        \caption{
                \CFA list library representations for the cases under discussion.
        }
        \label{fig:lst-impl-links}
\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.
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.
Iteration reports ``has more elements'' when crossing natural links, and ``no more elements'' upon reaching a tagged link.

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.
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.

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.



\section{Future Work}
\label{toc:lst:futwork}


TODO: deal with: A doubly linked list is being designed.

TODO: deal with: Link fields are system-managed.
Links in GDB.