Changeset 9c12dd0 for doc/theses/mike_brooks_MMath/array.tex

Timestamp:

Apr 27, 2026, 7:17:34 PM (33 hours ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

f1ffc47

Parents:

602cec4

Message:

Apply document-level formatting and rearrange the array-in-struct discussion.

Formatting:

• add visual separation of figures from text
• prevent "formula"-style code fragments from page breaking
• (thereby prevent code formula broken at end of page from mistakenly restarting the reader in a code figure at the top of the next page)
• give short+long figure captions
• assure descriptive captions
• remove Title-Like Captialization in Captions
• turn a couple figures into tables where the figure visual separator looks bad

Array-in-struct

• remove lingering use of "accordion"
• call it Dynamic Array Member
• oranize discussion as, first explain example, then argue feature is good

File:

• doc/theses/mike_brooks_MMath/array.tex (modified) (14 diffs)

doc/theses/mike_brooks_MMath/array.tex

@@ -30 +30 @@
 
 A function can be polymorphic over @array@ arguments using the \CFA @forall@ declaration prefix.
+\begin{minipage}{\linewidth} % forbid page splitting, force
 \begin{cfa}
 forall( T, @[N]@ )
@@ -40 +41 @@
 Cforall Runtime error: subscript 1000 exceeds dimension range [0,99) $for$ array 0x555555558020.
 \end{cfa}
+\end{minipage}
 Function @g@ takes an arbitrary type parameter @T@ and an unsigned integer \emph{dimension} @N@.
 The dimension represents a to-be-determined number of elements, managed by the type system, where 0 represents an empty array.
@@ -125 +127 @@
 \lstinput{30-43}{hello-array.cfa}
 \lstinput{45-48}{hello-array.cfa}
-\caption{Example of calling a dimension-generic function.}
+\caption{Example of calling a dimension-generic function}
 \label{f:fExample}
 \end{figure}
@@ -243 +245 @@
 This static check's rules are presented in \VRef[Section]{s:ArrayTypingC}.
 
-Orthogonally, the \CFA array type works within generic \emph{types}, \ie @forall@-on-@struct@.
-The same argument safety and the associated implicit communication of array length occurs.
+Orthogonally, the \CFA array type also works inside generic \emph{types}.
+That is, an @array@ as a generic @struct@'s member and an @[N]@ can parameterize a @struct@.
+The same argument safety, and the associated implicit length communication, occur.
 Preexisting \CFA allowed aggregate types to be generalized with type parameters, enabling parameterizing of element types.
-This feature is extended to allow parameterizing by dimension.
-Doing so gives a refinement of C's ``flexible array member''~\cite[\S~6.7.2.1.18]{C11}:
+As polymorphism on functions was extended to allow parameterizing over dimensions, so is polymorphism on types.
+The result has profound consequences for safe memory management.
+
+C's Flexible Array Member (FAM) pattern~\cite[\S~6.7.2.1.18]{C11} gives an unsafe way to put an array of dynamic length inside a structure.
 \begin{cfa}
 struct S {
         ...
-        double d []; // incomplete array type => flexible array member
-} * s = malloc( sizeof( struct S ) + sizeof( double [10] ) );
-\end{cfa}
-which creates a VLA of size 10 @double@s at the end of the structure.
-A C flexible array member can only occur at the end of a structure;
-\CFA allows length-parameterized array members to be nested at arbitrary locations, with intervening member declarations.
-\lstinput{10-15}{hello-accordion.cfa}
-The structure has course- and student-level metadata (their respective field names) and a position-based preferences' matrix.
-The structure's layout is dynamic; the starting offset of @student_ids@ varies according to the generic parameter @C@; the offset of @preferences@ varies by both.
-
-\VRef[Figure]{f:checkExample} shows a program main using @School@ and results with different array sizes.
+        double d[]; // incomplete array type => flexible array member
+};
+struct S * s = malloc( sizeof( struct S ) + sizeof( double [10] ) );
+\end{cfa}
+This type-@S@ declaration defines a quasi-VLA named @d@ as the last structure member.
+The variable-@s@ initialization sizes this particular array at 10 elements.
+The choice of @malloc@ here is the common-case FAM idiom, but @alloca@ can be substituted, resulting in stack allocation.
+A \CFA @[N]@-parameterized structure improves on this pattern.
+
+\begin{figure}
+        \lstinput{10-15}{hello-accordion.cfa}
+        \caption{\CFA Dynamic Array Member (DAM) declaration}
+        \label{DAM-declaration}
+\end{figure}
+
+\CFA allows length-parameterized array members to be nested at arbitrary locations, with further member declarations interleaved.
+The result is a \newterm{Dynamic Array Member (DAM)}
+% \footnote{
+%       To keep the names straight, it may help to think of C's flexible array member as ``too flexible,'' where the discussion that follows makes the case that a FAM is weakly typed.
+% },
+as illustrated in \VRef[Figure]{DAM-declaration}.  The example's @School@ structure has course- and student-level metadata (in the respectively named fields) and a position-based preferences' matrix.
+The structure's layout is dynamic; the starting offset of @student_ids@ varies according to the generic parameter @C@, which affects the size of the @course_codes@ field.
+Similarly, the offset of @preferences@ varies by both parameters.
+
+\VRef[Figure]{f:DAM-example} shows a program main using the @School@ type, along with results at different array sizes.
 The @school@ variable holds many students' course-preference forms.
 It is on the stack and its initialization does not use any casting or size arithmetic.
-Both of these points are impossible with a C flexible array member.
-When heap allocation is preferred, the original pattern still applies.
+When heap allocation is preferred, the original pattern still applies, with the same qualities.
 \begin{cfa}
 School( classes, students ) * sp = alloc();
 \end{cfa}
-This ability to avoid casting and size arithmetic improves safety and usability over C flexible array members.
 The example program prints the courses in each student's preferred order, all using the looked-up display names.
-When a function operates on a @School@ structure, the type system handles its memory layout transparently.
-In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class.
-Finally, inputs and outputs are given on the right for different sized schools.
+In the example, function @getPref@ returns, for the student at position @is@, the position of their @pref@\textsuperscript{th}-favoured class.
+This function helps the program to output each student's ordered preferences.
+The program's inputs and outputs are given on the right, for two different school sizes.
 
 \begin{figure}
@@ -304 +321 @@
 \end{tabular}
 
-\caption{\lstinline{School} Example, Input and Output}
-\label{f:checkExample}
+
+\caption[\CFA Dynamic Array Member (DAM) usage]{
+        \CFA Dynamic Array Member (DAM) usage.
+        Example program (left) with input and output (right).}
+\label{f:DAM-example}
 \end{figure}
+
+Much of these \CFA DAM features are impossible with a C FAM.
+In C, they can only occur at the end of a structure;
+\CFA allows them anywhere.
+As a consequence, \CFA allows several of them, while C is limited to one.
+The \CFA ability to avoid casting and size arithmetic improves safety and usability over C.
+While C offers the \emph{VLA} language feature, to eliminate casting and size arithmetic for stack-allocated \emph{simple arrays}, this feature does not extend to stack-allocating a FAM-structure, which makes the user fall back on explicit @alloca@.
+The \CFA DAM, by contrast, treats every stack allocation as a simple variable declaration.
+When a function operates on a \CFA DAM structure, the type system handles its memory layout transparently.
+
 
 
@@ -343 +373 @@
         The ``resolver'' compiler pass, which provides argument values for a declaration's type-system parameters, gathered from type information in scope at the usage site.
 \item
-        The ``box'' compiler pass, which encodes information about type parameters into ``extra'' regular parameters on declarations and and arguments on calls.
+        The ``box'' compiler pass, which encodes information about type parameters into ``extra'' regular parameters on declarations, and corresponding arguments on calls.
         Notably, it conveys the size of a type @foo@ as a @__sizeof_foo@ parameter, and rewrites the @sizeof(foo)@ expression as @__sizeof_foo@, \ie a use of the parameter.
 \end{itemize}
@@ -690 +720 @@
         \end{itemize}
 
-        \caption{Case comparison for array type compatibility, given pairs of dimension expressions.}
+        \caption[Case comparison for array type compatibility]{Case comparison for array type compatibility, given pairs of dimension expressions.}
         \label{f:DimexprRuleCompare}
 \end{figure}
@@ -946 +976 @@
 \begin{figure}
 \includegraphics{measuring-like-layout}
-\caption{Visualization of subscripting by value and by \lstinline[language=CFA]{all}, for \lstinline{x} of type \lstinline{array( float, 5, 7 )} understood as 5 rows by 7 columns.
-The horizontal layout represents contiguous memory addresses while the vertical layout is conceptual.
-The vertical shaded band highlights the location of the targeted element, 2.3.
-Any such vertical slice contains various interpretations of a single address.}
+\caption[Visualization of subscripting by value and by `all']{
+        Visualization of subscripting by value and by `\lstinline[language=CFA]{all}.'
+        Uses example variable \lstinline{x} of type \lstinline{array( float, 5, 7 )}, understood as 5 rows by 7 columns.
+        The horizontal layout represents contiguous memory addresses while the vertical layout is conceptual.
+        The vertical shaded band highlights the location of the targeted element, 2.3.
+        Any such vertical slice contains various interpretations of a single address.
+}
 \label{fig:subscr-all}
 \end{figure}
@@ -1007 +1040 @@
 % \noindent END: Paste looking for a home
 
-The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping.
-The @arpk@ structure and its @-[i]@ operator are defined as:
+\begin{figure}
 \begin{cfa}
 forall(
@@ -1026 +1058 @@
 }
 \end{cfa}
+\caption{Definition of structure `\lstinline{arpk},' which underlies the \CFA array}
+\label{f:arpk}
+\end{figure}
+
+The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping.
+The @arpk@ structure and its @-[i]@ operator are defined in \VRef[Figure]{f:arpk}.
 The private @arpk@ structure (array with explicit packing) is generic over four types: dimension length, masquerading-as, ...
 This structure's public interface is hidden behind the @array(...)@ macro and the subscript operator.
@@ -1101 +1139 @@
 \multicolumn{1}{c}{(i)}
 \end{tabular}
-\caption{Overhead comparison, control case.
-All three programs/compilers generate equally performant code when the programmer ``self-checks'' bounds via a loop's condition.
-Yet both \CFA and \CC versions generate code that is slower and safer than C's when the programmer might overrun the bounds.}
+\caption[Bound-check overhead comparison, control case]{
+        Bound-check overhead comparison, control case.
+        All three programs/compilers generate equally performant code when the programmer ``self-checks'' bounds via a loop's condition.
+        Yet both \CFA and \CC versions generate code that is slower and safer than C's when the programmer might overrun the bounds.
+}
 \label{f:ovhd-ctl}
 \end{figure}
@@ -1344 +1384 @@
 \end{cfa}
 \end{tabular}
-\caption{Exponential thunk generation under the otype-recursion pattern.
+\caption[Exponential thunk generation under the otype-recursion pattern]{
+        Exponential thunk generation under the otype-recursion pattern.
         Each time one type's function (\eg ctor) uses another type's function, the \CFA compiler generates a thunk, to capture the used function's dependencies, presented according to the using function's need.
         So, each non-leaf line represents a generated thunk and every line represents a search request for the resolver to find a satisfying function.}
@@ -1640 +1681 @@
 \hspace{6pt}
 
-\caption{Triangular Matrix}
+\caption{Triangular matrix in Java and C}
 \label{f:JavaVsCTriangularMatrix}
 \end{figure}
@@ -1684 +1725 @@
 
 Thus, these options do not offer an allocation with a dynamically given fixed size.
-And furthermore, they do not provide any improvement to the C flexible array member pattern, for making a dynamic amount of storage contiguous with its header, as do \CFA's accordions.
+And furthermore, they do not provide any improvement to the C flexible array member pattern, for making a dynamic amount of storage contiguous with its header, as do \CFA's new dynamic array members.