source: doc/theses/mike_brooks_MMath/intro.tex @ ea10f64

\chapter{Introduction}

All modern programming languages provide three high-level containers (collections): array, linked-list, and string.
Often array is part of the programming language, while linked-list is built from (recursive) pointer types, and string from a combination of array and linked-list.
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 level, such as copying, slicing, extracting, and iterating among elements.

This work looks at extending these three foundational container 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 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.
This work leverages preexisting work within the compiler's type and runtime systems generated by prior graduate students working on the \CFA project.


\section{Array}
\label{s:ArrayIntro}

An array provides a homogeneous container 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.
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 (some form of pointer arithmetic).

C provides a simple array type as a language feature.
However, it adopts the controversial language position of treating pointer and array as duals, leading to multiple problems.


\section{Linked list}

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 (rather than position or location as for array) is sometimes available, \eg hash table.
Linked types are normally dynamically sized by adding and removing nodes using link fields internal or external to the elements (nodes).
If a programming language allows pointers to stack storage, linked-list nodes can be allocated on the stack and connected with stack addresses (pointers);
otherwise, elements are heap allocated with internal or external link fields.

C provides a few simple, polymorphic, library data-structures (@glibc@):
\begin{itemize}
\item
singly-linked lists, singly-linked tail queues, lists, and tail queues (@<sys/queue.h>@) \see{\VRef{s:PreexistingLinked-ListLibraries}}
\item
hash search table consisting of a key (string) with associated data (@<search.h>@)
\end{itemize}
Because these libraries are simple, awkward to use, and unsafe, C programmers commonly build linked-list behaviours into their bespoke data structures.


\section{String}

A string provides a dynamic array of homogeneous elements, where the elements are (often) some form of human-readable characters.
What differentiates a string from other types in that many of its operations work on groups of elements for scanning and changing, \eg @index@ and @substr@.
While subscripting individual elements is usually available, working at the individual character level is considered poor practise, \ie underutilizing the powerful string operations.
Therefore, the cost of a string operation is usually less important than the power of the operation to accomplish complex text manipulation, \eg search, analysing, composing, and decomposing string text.
The dynamic nature of a string means storage is normally heap allocated but often implicitly managed, even in unmanaged languages.
In some cases, string management is separate from heap management, \ie strings roll their own heap.

The C string type requires user storage-management of a language-provided character array.
The character array uses the convention of marking its (variable) array length by placing the 0-valued control character at the end (null-terminated).
The C standard library includes a number of high-level operations for working with this representation.


\section{Iterator}

As a side issue to complex structured-types is iterating through them.
Some thought has been given to \emph{general} versus specific iteration capabilities as part of of this work.
However, the general iteration work is only a sketch for others as future work.
Nevertheless, sufficed work was done to write out the ideas that developed and how they should apply in the main context of this work. 


\section{Motivation}

The primary motivation for this work is two fold:
\begin{enumerate}[leftmargin=*]
\item
These three aspects of C are difficult to understand, teach, and get right because they are correspondingly low level.
Providing higher-level, feature-rich versions of these containers in \CFA is a major component of the primary goal.
\item
These three aspects of C cause the greatest safety issues because there are few or no safe guards when a programmer misunderstands or misuses these features~\cite{Elliott18, Blache19, Ruef19, Oorschot23}.
Estimates suggest 50\%~\cite{Mendio24} of total reported open-source vulnerabilities occurring in C result from errors using these facilities (memory errors), providing the major hacker attack-vectors.
\end{enumerate}
Both White House~\cite{WhiteHouse24} and DARPA~\cite{DARPA24} recently released a recommendation to move away from C and \CC, because of cybersecurity threats exploiting vulnerabilities in these older languages.
Hardening these three types goes a long way to make the majority of C programs safer.


While multiple new languages purport to be systems languages replacing C, the reality is that rewriting massive C code-bases is impractical and a non-starter if the new runtime uses garage collection.
Furthermore, new languages must still interact with the underlying C operating system through fragile, type-unsafe, interlanguage-communication.
Switching to \CC is equally impractical as its complex and interdependent type-system (\eg objects, overloading, inheritance, templates) means idiomatic \CC code is difficult to use from C, and C programmers must expend significant effort learning \CC.
Hence, rewriting and retraining costs for these languages can be prohibitive for companies with a large C software-base (Google, Apple, Microsoft, Amazon, AMD, Nvidia).


\section{C?}

Like many established programming languages, C has a standards committee and multiple ANSI/\-ISO language manuals~\cite{C99,C11,C18,C23}.
However, most programming languages are only partially explained by their standard's manual(s).
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 mimic @gcc@ because a large part of the C library (runtime) system (@glibc@ on Linux) contains @gcc@ features.
Some key aspects of C need to be explained and understood by quoting from the language reference manual.
However, to illustrate actual program semantics, this thesis constructs multiple small programs whose behaviour exercises a particular point and then confirms the behaviour by running the program using multiple @gcc@ compilers.
These example programs show
\begin{itemize}
        \item if the compiler accepts or rejects certain syntax,
        \item prints output to buttress a behavioural claim,
        \item or executes without triggering any embedded assertions testing pre/post-assertions or invariants.
\end{itemize}
These programs are tested across @gcc@ versions 8--14 and clang versions 10--14 running on ARM, AMD, and Intel architectures.
Any discovered anomalies among compilers, versions, or architectures is discussed.
In general, it is never clear whether the \emph{truth} lies in the C standard or the compiler(s), which may be true for other programming languages.


\section{Contributions}

Overall, this work has produced significant syntactic and semantic improvements to C's arrays, linked-lists and string types.
As well, a strong plan for general iteration has been sketched out.
The following are the detailed contributions, where performance and safety were always the motivating factors.

\subsection{Array}

This work's array improvements are:
\begin{enumerate}[leftmargin=*]
\item
Introduce a small number of subtle changes to the typing rules for the C array, while still achieving significant backwards compatibility
\item
Create a new polymorphic mechanism into the \CFA @forall@ clause for specifying array dimension values, similar to a fixed-typed parameter in a \CC \lstinline[language=C++]{template}.
\item
Construct a new standard-library array-type, available through @#include <array.hfa>@.
\end{enumerate}
The new array type, enabled by prior 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.
The thesis includes a performance evaluation that shows \CFA arrays perform comparably with C arrays in many programming cases.


\subsection{Linked list}

The linked list is a new runtime library, available through @#include <dlist.hfa>@.
The library offers a novel combination of the preexisting \CFA features: references, inline inheritance, polymorphism, and declaration scoping.
A programmer's experience using the list data-types within the type system is novel.
The list's runtime representation follows the established design pattern of intrusive link-fields for performance reasons, especially in concurrent programs.
The 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{String}

The string is a new runtime library, available through @#include <string.hfa>@.
The library offers a type where basic usage is comparable to the \CC @string@ type, including analogous coexistence with raw-character pointers.
Its implementation, however, follows different principles, 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, the implementation is a set of strings rolled into their own specialized heap.

The string library includes writing and reading strings via the preexisting \CFA I/O stream library.
Enabling transparent reading (of unknown length into a managed allocation) included revision of the stream library's existing handling of character arrays.
All reasonable stream manipulators are supported, \eg width, justification (left/right), printing characters as their numeric values, and complex input scanning to isolate strings.


\subsection{Iterator}

Some advanced iterator prototyping now exists, available in the \CFA standard library.
Specifically, a family of iterator styles is provided, with cheap iterators that are robust to being misused, plus full-featured iterators that observe structural modifications without becoming invalid.
Hence, the infamous \CC bug of iterator invalidation, where structural changes cause legitimate operations to fail, \eg iterator over a list and deleting each element.

Further design provides a home for Liskov-style iterators in \CFA.
This design extends a preexisting proposal to adapt the \CFA (fixed) for-each loop to be more user-pluggable, and builds upon preexisting \CFA coroutines.
Overall, it simplifies the work a programmer must do to leverage the suspended-state abstraction during iteration.