Changeset 6224eeb

Timestamp:

Apr 27, 2026, 8:05:23 PM (28 hours ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

c910d308

Parents:

b3e77cc

Message:

change to consistent "collection" over "container"

Location:

doc/theses/mike_brooks_MMath

Files:

• array.tex (modified) (2 diffs)
• background.tex (modified) (1 diff)
• conclusion.tex (modified) (2 diffs)
• intro.tex (modified) (6 diffs)
• list.tex (modified) (2 diffs)
• uw-ethesis-frontpgs.tex (modified) (3 diffs)
• uw-ethesis.tex (modified) (1 diff)

doc/theses/mike_brooks_MMath/array.tex

@@ -919 +919 @@
 However, function @print1d_cstyle@ is asserting too much knowledge about its parameter @r@ for printing either a row slice or a column slice.
 Specifically, declaring the parameter @r@ with type @array@ means that @r@ is contiguous, which is unnecessarily restrictive.
-That is, @r@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@) with managed length @N@.
+That is, @r@ need only be of a collection type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@) with managed length @N@.
 The new-array library provides the trait @ar@, so-defined.
 With it, the original declaration can be generalized with the same body.
@@ -1721 +1721 @@
 
 \CC~23's @std::mdspan@ adds multidimensional indexing and reshaping capabilities analogous to those built into \CFA's @array@.
-Like @span@, it works over multiple underlying container types.
+Like @span@, it works over multiple underlying collection types.
 But neither @span@ nor @mdspan@ augments the available allocation options.
 

doc/theses/mike_brooks_MMath/background.tex

@@ -225 +225 @@
 \end{cquote}
 % I believe it is possible to refute any code examples purporting to show pointer arithmetic is faster than subscripting.
-% This believe stems from the performance work I did on \CFA arrays, where it is possible to generate equivalent \CFA subscripting and performance to C subscripting.
+% This belief stems from the performance work I did on \CFA arrays, where it is possible to generate equivalent \CFA subscripting and performance to C subscripting.
 
 Unfortunately, C semantics want a programmer to \emph{believe} an array variable is a \emph{pointer to its first element}.

doc/theses/mike_brooks_MMath/conclusion.tex

@@ -1 +1 @@
 \chapter{Conclusion}
 
-This thesis performed a detailed examination of the three most important high-level containers in many programming languages: array, linked-list, and string.
-The goal of the work is to make containers easier to use, performant and safer.
-Since some subset of these three containers are used in almost every program in every programming language, this is a laudable goal.
+This thesis performed a detailed examination of the three most important high-level collections in many programming languages: array, linked-list, and string.
+The goal of the work is to make collections easier to use, performant and safer.
+Since some subset of these three collections are used in almost every program in every programming language, this is a laudable goal.
 Accomplishing this goal in C is difficult because these features are poorly designed.
 In contrast, \CFA's advanced type system and language features plus my critical design choices made it possible to provide better support with significant safety.
 The result is application code that is easier to write, understand, maintain, and significantly safer from hacker attach-vectors.
-Finally, the performance sections for each container demonstrated that safety does not have to reduce performance, \ie rolling-your-own container is now an excuse not a reason.
+Finally, the performance sections for each collection demonstrated that safety does not have to reduce performance, \ie rolling-your-own collection is now an excuse not a reason.
 
 
@@ -42 +42 @@
 \section{Future Work}
 
-All three forms of containers presented in this work are in their nascence, both in design and implementation.
+All three forms of collections presented in this work are in their nascence, both in design and implementation.
 This work provides the foundation for future \CFA students to add more functionality along with robust and performant implementations.
 Completing the syntax change from @array@ to C-style for dimensions and subscripts is an important first step to fit with C-programmer expectation resulting in faster adoption.

doc/theses/mike_brooks_MMath/intro.tex

@@ -1 +1 @@
 \chapter{Introduction}
 
-All modern programming languages provide at least these three high-level containers (collections): array, linked-list, and string.
+All modern programming languages provide at least these three high-level collections (containers): array, linked-list, and string.
 Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, iterating among, adding and removing elements.
@@ -39 +39 @@
 Therefore, hardening the three primary collections goes a long way to making the majority of C programs safer, eliminating major hacker attack vectors.
 
-My work looks at extending these foundational container types in the programming language \CFA, which is a new dialect of the C programming language.
+My work looks at extending these foundational collection types in the programming language \CFA, which is a new dialect of the C programming language.
 A primary goal of \CFA~\cite{Cforall} is 99\% backward compatibility with C, while maintaining a look and feel that matches with C programmer experience and intuition.
 This goal requires ``thinking inside the box'' to engineer new features that ``work and play'' with C and its massive legacy code-base.
 An equally important goal is balancing good performance with safety.
 
-The thesis describes improvements I made to the \CFA language design, both syntax and semantics, to support the container features, and the source code created within the \CFA compiler, libraries, and runtime system to implement these features.
+The thesis describes improvements I made to the \CFA language design, both syntax and semantics, to support the collection features, and the source code created within the \CFA compiler, libraries, and runtime system to implement these features.
 This work leverages preexisting work within the compiler's type and runtime systems generated by prior graduate students working on the \CFA project.
 
@@ -50 +50 @@
 \section{Array}
 
-An array provides a homogeneous container with $O(1)$ access to elements using subscripting.
+An array provides a homogeneous collection with $O(1)$ access to elements using subscripting.
 Higher-level operations like array slicing (single or multidimensional) may have significantly higher cost, but provide a better programmer experience.
 The array size can be static, dynamic but fixed after creation, or dynamic and variable after creation.
@@ -64 +64 @@
 \section{Linked List}
 
-A linked-list provides a homogeneous container often with $O(n)$ access to elements using successor and predecessor operations that involve pointer chasing.
+A linked-list provides a homogeneous collection often with $O(n)$ access to elements using successor and predecessor operations that involve pointer chasing.
 It is the most foundational case of the linked data structures, which include trees and hash tables.
 Among the linked structures, the list's defining characteristic is maintaining a user-explicit total order (chain shape).
@@ -83 +83 @@
 hash search table consisting of a key (string) with associated data (@<search.h>@)
 \end{itemize}
-Because these container libraries can be restrictive or awkward to use, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
+Because these collection libraries can be restrictive or awkward to use, C programmers often build bespoke linked data-structures, which further increases the potential for memory errors.
 
 
@@ -117 +117 @@
 \begin{enumerate}[leftmargin=*]
 \item
-The three primary container types in C are difficult to understand, teach, and get right because they are too low level.
-Providing higher-level, feature-rich versions of these containers in \CFA is a major component of the primary goal.
+The three primary collection types in C are difficult to understand, teach, and get right because they are too low level.
+Providing higher-level, feature-rich versions of these collections in \CFA is a major component of the primary goal.
 The result is a simplified programming experience, which increases productivity and maintainability.
 \item
-The new container types must be as correct and safe to use as those in other modern programming languages, to elide the concerns of industry, government, and military~\cite{ONCD}.
+The new collection types must be as correct and safe to use as those in other modern programming languages, to elide the concerns of industry, government, and military~\cite{ONCD}.
 Prior approaches focus on out-of-bound array accesses using a model-based approach (ASCET) in embedded systems (\eg cars)~\cite{Blache19}, and general and null-terminated string arrays using a \CC template syntax (Checked C)~\cite{Elliott18,Ruef19}.
 Both White House~\cite{WhiteHouse24} and DARPA~\cite{DARPA24} recently released a recommendation to \emph{move away} from C and \CC, because of cybersecurity threats exploiting vulnerabilities in these languages.

doc/theses/mike_brooks_MMath/list.tex

@@ -199 +199 @@
 Within the @with@, the code acts as if there is only one list axis, without explicit casting.
 
-Unlike the \CC template container-types, the \CFA library works completely within the type system;
+Unlike the \CC template collection types, the \CFA library works completely within the type system;
 both @dlink@ and @dlist@ are ordinary types, not language macros.
 There is no textual expansion other than header-included static-inline function for performance.
@@ -544 +544 @@
 Hence, to be \emph{exception safe}, all internal list operations must complete before the copy/move so the list is consistent should the return fail.
 This coding style can result in contrived code, but is usually possible;
-however, it requires the container designer to anticipate the potential throw.
-(Note, this anticipation issue is pervasive in exception systems, not just with containers.)
-The solution moves the coding complexity from the container designer to the programer~\cite[ch~10, part 3]{Sutter99}.
-First, obtain the node, which might fail, but the container is unmodified.
-Second, remove the node, which modifies the container without the possibly of an exception.
+however, it requires the collection designer to anticipate the potential throw.
+(Note, this anticipation issue is pervasive in exception systems, not just with collections.)
+The solution moves the coding complexity from the collection designer to the programer~\cite[ch~10, part 3]{Sutter99}.
+First, obtain the node, which might fail, but the collection is unmodified.
+Second, remove the node, which modifies the collection without the possibly of an exception.
 This movement of responsibility increases the cognitive effort for programmers.
 Unfortunately, this \emph{single-responsibility principle}, \ie preferring separate operations, is often repeated as a necessary requirement rather an an optional one.

doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

@@ -13 +13 @@
         \vspace*{1.0cm}
 
-  % TODO: punch up the title, thinking getting interest in the department-wide posting of my presentation
-  % Modern collections for C
-        {\Huge\bf \CFA Container Library}
+        {\Huge\bf \CFA Collection Library}
 
         \vspace*{1.0cm}
@@ -131 +129 @@
 \CFA strives to fix issues in C, chief among them safety.
 This thesis presents a significant step forward in \CFA's goal to remove unsafe pointer operations.
-It describes improvements to the \CFA language design to support advanced container features.
+It describes improvements to the \CFA language design to support advanced collection features.
 These features are implemented across the \CFA compiler and runtime libraries.
 The results maintain another \CFA goal of offering strong backwards compatibility with C.
 To achieve these goals, this work leverages preexisting \CFA contributions by prior students, particularly novel applications of the compiler's type system.
 
-All modern programming languages provide these three high-level containers (collections): array, linked-list, and string.
+All modern programming languages provide these three high-level collections (containers): array, linked-list, and string.
 Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
 For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
@@ -149 +147 @@
 With the array, this case is made by showing complete erasure down to a naked C array, modulo runtime bound checks, which are removable more often than with Java-style length management.
 With the linked list and string, empirical measures are compared with C and \CC comparable libraries.
-These containers offer programmers workable alternatives to hand-rolling specialized libraries, which is a huge safety benefit, eliminating many system vulnerabilities.
+These collections offer programmers workable alternatives to hand-rolling specialized libraries, which is a huge safety benefit, eliminating many system vulnerabilities.
 The results establish \CFA's position as a safety-forward programming alternative.
 

doc/theses/mike_brooks_MMath/uw-ethesis.tex

@@ -183 +183 @@
     pdffitwindow=false,     % window fit to page when opened
     pdfstartview={FitH},    % fits the width of the page to the window
-    pdftitle={\CFA Container Library}, % title: CHANGE THIS TEXT!
+    pdftitle={\CFA Collection Library}, % title: CHANGE THIS TEXT!
     pdfauthor={Mike Brooks},    % author: CHANGE THIS TEXT! and uncomment this line
     pdfsubject={Cforall},  % subject: CHANGE THIS TEXT! and uncomment this line
-    pdfkeywords={Cforall} {container library} {C language}, % optional list of keywords
+    pdfkeywords={Cforall} {container library} {collection library} {array} {linked list} {string} {C language}, % optional list of keywords
     pdfnewwindow=true,      % links in new window
     colorlinks=true,        % false: boxed links; true: colored links