Context Navigation

-              r76425bc
+              rc721105
 All modern programming languages provide three high-level containers (collection): array, linked-list, and string.
 Often array is part of the programming language, while linked-list is built from pointer types, and string from a combination of array and linked-list.
+For all three types, there is some corresponding mechanism for iterating through the structure, where the iterator flexibility varies with the kind of structure and ingenuity of the iterator implementor.
-\cite{Blache19}
-\cite{Oorschot23}
-\cite{Ruef19}
 \section{Array}
 Array provides a homogeneous container with $O(1)$ access to elements using subscripting.
+An array provides a homogeneous container with $O(1)$ access to elements using subscripting (some form of pointer arithmetic).
 The array size can be static, dynamic but fixed after creation, or dynamic and variable after creation.
 For static and dynamic-fixed, an array can be stack allocated, while dynamic-variable requires the heap.
+Because array layout has contiguous components, subscripting is a computation.
+However, the computation can exceed the array bounds resulting in programming errors and security violations~\cite{Elliott18, Blache19, Ruef19, Oorschot23}.
+The goal is to provide good performance with safety.
 \section{Linked List}
 Linked-list provides a homogeneous container with $O(log N)$/$O(N)$ access to elements using successor and predecessor operations.
+A linked-list provides a homogeneous container often with $O(log N)$/$O(N)$ access to elements using successor and predecessor operations.
 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).
 …
 \section{String}
 String provides a dynamic array of homogeneous elements, where the elements are often human-readable characters.
 What differentiates string from other types in that string operations work on blocks of elements for scanning and changing the elements, rather than accessing individual elements.
 Nevertheless, subscripting is often available.
 The cost of string operations is less important than the power of the block operation to accomplish complex manipulation.
 The dynamic nature of string means storage is normally heap allocated but often implicitly managed, even in unmanaged languages.
+A string provides a dynamic array of homogeneous elements, where the elements are often human-readable characters.
+What differentiates a string from other types in that its operations work on blocks of elements for scanning and changing the elements, rather than accessing individual elements, \eg @index@ and @substr@.
+Subscripting individual elements is often available.
+Often the cost of string operations is less important than the power of the operations to accomplish complex text manipulation, \eg search, analysing, composing, and decomposing.
+The dynamic nature of a string means storage is normally heap allocated but often implicitly managed, even in unmanaged languages.
 \section{Motivation}
 The goal of this work is to introduce safe and complex versions of array, link-lists, and string into the programming language \CFA~\cite{Cforall}, which is based on C.
+The goal of this work is to introduce safe and complex versions of array, link lists, and strings into the programming language \CFA~\cite{Cforall}, which is based on C.
 Unfortunately, to make C better, while retaining a high level of backwards compatibility, requires a significant knowledge of C's design.
 Hence, it is assumed the reader has a medium knowledge of C or \CC, on which extensive new C knowledge is built.
 …
 However, most programming languages are only partially explained by standard's manuals.
 When it comes to explaining how C works, the definitive source is the @gcc@ compiler, which is mimicked by other C compilers, such as Clang~\cite{clang}.
 Often other C compilers must \emph{ape} @gcc@ because a large part of the C library (runtime) system contains @gcc@ features.
+Often other C compilers must mimic @gcc@ because a large part of the C library (runtime) system contains @gcc@ features.
 While some key aspects of C need to be explained by quoting from the language reference manual, to illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and shows its behaviour.
 These example programs show
 …
 This work has been tested across @gcc@ versions 8--12 and clang version 10 running on ARM, AMD, and Intel architectures.
 Any discovered anomalies among compilers or versions is discussed.
 In this case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard.
+In all case, I do not argue that my sample of major Linux compilers is doing the right thing with respect to the C standard.
 …
 \end{cfa}
 with a segmentation fault at runtime.
 Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems like madness.
 Compiling with flag @-Werror@, which turns warnings into errors, is often too strong, because some warnings are just warnings.
+Clearly, @gcc@ understands these ill-typed case, and yet allows the program to compile, which seems inappropriate.
+Compiling with flag @-Werror@, which turns warnings into errors, is often too strong, because some warnings are just warnings, \eg unsed variable.
 In the following discussion, ``ill-typed'' means giving a nonzero @gcc@ exit condition with a message that discusses typing.
 Note, \CFA's type-system rejects all these ill-typed cases as type mismatch errors.
 …
 \subsection{String}
+\subsection{Iterator}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset c721105 for doc/theses/mike_brooks_MMath/intro.tex

Legend:

doc/theses/mike_brooks_MMath/intro.tex

Download in other formats: