Changeset 02ea981

Timestamp:

Oct 16, 2024, 1:31:40 PM (5 weeks ago)

Author:

Michael Brooks <mlbrooks@…>

Branches:

master

Children:

187be97, e8b5ba4

Parents:

4e0168a

Message:

Thesis introduction contributions, first try.

File:

• doc/theses/mike_brooks_MMath/intro.tex (modified) (4 diffs)

doc/theses/mike_brooks_MMath/intro.tex

@@ -19 +19 @@
 Because array layout has contiguous components, subscripting is a computation (some form of pointer arithmetic).
 
+C provides an array as a language feature.
 
 \section{Linked list}
 
-A linked-list provides a homogeneous container often with $O(log N)$/$O(N)$ access to elements using successor and predecessor operations that normally involve pointer chasing.
+A linked-list provides a homogeneous container often with $O(log N)$ or $O(N)$ access to elements using successor and predecessor operations that normally involve pointer chasing.
 Subscripting by value is sometimes available, \eg hash table.
 Linked types are normally dynamically sized by adding/removing nodes using link fields internal or external to the elements (nodes).
@@ -28 +29 @@
 otherwise, elements are heap allocated with explicitly/implicitly managed.
 
+C does not provide a linked-list, either as an obvious commonly-accepted library, nor as an outright language feature.
+C programmers commonly build linked-list behaviours into their bespoke data structures, directly using its language feature of pointers.
 
 \section{String}
@@ -38 +41 @@
 In some cases, string management is separate from heap management, \ie strings roll their own heap.
 
+The C string type is a user-managed allocation of the language-provided character array,
+plus the convention of marking its (variable) length by placing the 0-valued control character at the end (``null-terminated'').
+The C standard library includes many operations for working on this representation.
 
 \section{Iterator}
@@ -90 +96 @@
 As well, a strong plan for general iteration has been sketched out.
 
+This thesis mainly describes improvements made to the source code of the \CFA compiler and runtime system,
+available at TODO.
+
+This work often leverages preexisting    xxxxxxxxxx
+
 \subsection{Linked list}
+
+The linked list is a new runtime library, available as @#include <dlist.hfa>@.
+The library offers a novel combination of the preexisting \CFA features of:
+references, inline inheritance, polymorphism and declaration scoping.
+A programmer's experience of the list datatype within the type system is novel.
+The list's runtime representation follows the established design pattern of intrusion.
+This thesis includes a performance evaluation that shows
+the list performing comparably with other C-family intrusive lists,
+and notably better than the \CC standard list.
 
 \subsection{Array}
 
+This work's array improvements are
+\begin{enumerate}[leftmargin=*]
+\item
+subtle changes to the typing rules for the C array,
+\item
+a new \CFA language construct for a type-system managed array length, and
+\item
+a new standard-library array type, available as @#include <array.hfa>@.
+\end{enumerate}
+The new array type, enabled by the earlier features, defines an array with
+guaranteed runtime bound checks (often optimizer-removable) and
+implicit (guaranteed accurate) inter-function length communication.
+Leveraging the preexisting \CFA type system to achieve
+this length-related type checking is an original contribution.
+
+Furthermore, the new array incorporates multidimensional capabilities
+typical of scientific/machine-learning languages,
+made to coexist with the C ``raw-memory-aware'' tradition in a novel way.
+
 \subsection{String}
 
+The string is a new runtime library, available as @#include <string.hfa>@.
+The library offers a type whose basic usage is comparable to the \CC @string@ type,
+including analogous coexistence with raw character pointers.
+Its implementation, however, follows different princliples,
+enabling programs to work with strings by value, without incurring excessive copying.
+Mutability is retained.
+Substrings are supported, including the ability for overlapping ranges to share edits transparently.
+Ultimately, this implementation is a case of strings rolling their own heap.
+
+The string library includes writing and reading strings via the preexsiting \CFA I/O stream library.
+Enabling transparent reading (of unknown length into a managed allocation) included revision of
+the stream libarary's existing handling of character arrays.
+
 \subsection{Iterator}
+
+Some prototyping, available in the \CFA standard library,
+addresses the infamous \CC bug source of iterator invalidation.
+A family of iterator styles is presented, with cheap iterators that resist being misused,
+plus full-featured iterators that observe modifications without becoming invalid.
+
+Further design within this thesis presents a home for Liskov-style iterators in \CFA.
+This design extends a preexisting proposal to adapt the \CFA for-each style loop to be more user-pluggable.
+It also builds upon preexisting \CFA coroutines.
+It simplifies the work a programmer must do to leverage the suspended-state abstraction.