Changeset 0d41e600

Timestamp:

Apr 15, 2025, 11:49:08 AM (6 days ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

3c1e432, 471613c

Parents:

768d091

Message:

Linked-list chapter writing, pushing work in progress

Location:

doc/theses/mike_brooks_MMath

Files:

• list.tex (modified) (2 diffs)
• pictures/lst-impl-links.pdf (added)
• pictures/lst-impl-links.vsdx (added)

doc/theses/mike_brooks_MMath/list.tex ¶

@@ -83 +83 @@
 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.
@@ -92 +137 @@
 The \CFA library works in headed and headless modes.  TODO: elaborate.
 
-\subsection{Iteration-FOUNDATIONS}
-
-TODO: This section should be moved to a Foundations chapter.  The next section stays under Linked List.
 
 
 \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.
+