source: doc/theses/mike_brooks_MMath/background.tex @ 297b796

\chapter{Background}

Since this work builds on C, it is necessary to explain the C mechanisms and their shortcomings for array, linked list, and string.


\section{Array}

At the start, the C programming language made a significant design mistake.
\begin{quote}
In C, there is a strong relationship between pointers and arrays, strong enough that pointers and arrays really should be treated simultaneously.
Any operation which can be achieved by array subscripting can also be done with pointers.~\cite[p.~93]{C:old}
\end{quote}
Accessing any storage requires pointer arithmetic, even if it is just base-displacement addressing in an instruction.
The conjoining of pointers and arrays could also be applied to structures, where a pointer references a structure field like an array element.
Finally, while subscripting involves pointer arithmetic (as does field references @x.y.z@), it is very complex for multi-dimensional arrays and requires array descriptors to know stride lengths along dimensions.
Many C errors result from performing pointer arithmetic instead of using subscripting.
Some C textbooks erroneously teach pointer arithmetic suggesting it is faster than subscripting.

C semantics want a programmer to \emph{believe} an array variable is a ``pointer to its first element.''
This desire becomes apparent by a detailed inspection of an array declaration.
\lstinput{34-34}{bkgd-carray-arrty.c}
The inspection begins by using @sizeof@ to provide definite program semantics for the intuition of an expression's type.
\lstinput{35-36}{bkgd-carray-arrty.c}
Now consider the sizes of expressions derived from @ar@, modified by adding ``pointer to'' and ``first element'' (and including unnecessary parentheses to avoid confusion about precedence).
\lstinput{37-40}{bkgd-carray-arrty.c}
Given the size of @float@ is 4, the size of @ar@ with 10 floats being 40 bytes is common reasoning for C programmers.
Equally, C programmers know the size of a \emph{pointer} to the first array element is 8 (or 4 depending on the addressing architecture).
% Now, set aside for a moment the claim that this first assertion is giving information about a type.
Clearly, an array and a pointer to its first element are different things.

In fact, the idea that there is such a thing as a pointer to an array may be surprising and it is not the same thing as a pointer to the first element.
\lstinput{42-45}{bkgd-carray-arrty.c}
The first assignment gets
\begin{cfa}
warning: assignment to `float (*)[10]' from incompatible pointer type `float *'
\end{cfa}
and the second assignment gets the opposite.

The inspection now refutes any suggestion that @sizeof@ is informing about allocation rather than type information.
Note, @sizeof@ has two forms, one operating on an expression and the other on a type.
Using the type form yields the same results as the prior expression form.
\lstinput{46-49}{bkgd-carray-arrty.c}
The results are also the same when there is \emph{no allocation} using a pointer-to-array type.
\lstinput{51-57}{bkgd-carray-arrty.c}
Hence, in all cases, @sizeof@ is informing about type information.

So, thinking of an array as a pointer to its first element is too simplistic an analogue and it is not backed up by the type system.
This misguided analogue works for a single-dimension array but there is no advantage other than possibly teaching beginning programmers about basic runtime array-access.

Continuing, a short form for declaring array variables exists using length information provided implicitly by an initializer.
\lstinput{59-62}{bkgd-carray-arrty.c}
The compiler counts the number of initializer elements and uses this value as the first dimension.
Unfortunately, the implicit element counting does not extend to dimensions beyond the first.
\lstinput{64-67}{bkgd-carray-arrty.c}

My contribution is recognizing:
\begin{itemize}
        \item There is value in using a type that knows its size.
        \item The type pointer to (first) element does not.
        \item C \emph{has} a type that knows the whole picture: array, e.g. @T[10]@.
        \item This type has all the usual derived forms, which also know the whole picture.
        A usefully noteworthy example is pointer to array, e.g. @T (*)[10]@.\footnote{
        The parenthesis are necessary because subscript has higher priority than pointer in C declarations.
        (Subscript also has higher priority than dereference in C expressions.)}
\end{itemize}


\section{Reading Declarations}

A significant area of confusion for reading C declarations results from embedding a declared variable in a declaration, mimicking the way the variable is used in executable statements.
\begin{cquote}
\begin{tabular}{@{}ll@{}}
\multicolumn{1}{@{}c}{\textbf{Array}} & \multicolumn{1}{c@{}}{\textbf{Function Pointer}} \\
\begin{cfa}
int @(*@ar@)[@5@]@; // definition
  ... @(*@ar@)[@3@]@ += 1; // usage
\end{cfa}
&
\begin{cfa}
int @(*@f@())[@5@]@ { ... }; // definition
  ... @(*@f@())[@3@]@ += 1; // usage
\end{cfa}
\end{tabular}
\end{cquote}
Essentially, the type is wrapped around the name in successive layers (like an \Index{onion}).
While attempting to make the two contexts consistent is a laudable goal, it has not worked out in practice, even though Dennis Richie believed otherwise:
\begin{quote}
In spite of its difficulties, I believe that the C's approach to declarations remains plausible, and am comfortable with it; it is a useful unifying principle.~\cite[p.~12]{Ritchie93}
\end{quote}
After all, reading a C array type is easy: just read it from the inside out, and know when to look left and when to look right!

\CFA provides its own type, variable and routine declarations, using a simpler syntax.
The new declarations place qualifiers to the left of the base type, while C declarations place qualifiers to the right of the base type.
The qualifiers have the same meaning in \CFA as in C.
Then, a \CFA declaration is read left to right, where a function return type is enclosed in brackets @[@\,@]@.
\begin{cquote}
\begin{tabular}{@{}l@{\hspace{3em}}ll@{}}
\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}} & \multicolumn{1}{c}{\textbf{read left to right}}   \\
\begin{cfa}
int @*@ x1 @[5]@;
int @(*@x2@)[5]@;
int @(*@f( int p )@)[5]@;
\end{cfa}
&
\begin{cfa}
@[5] *@ int x1;
@* [5]@ int x2;
@[ * [5] int ]@ f( int p );
\end{cfa}
&
\begin{cfa}
// array of 5 pointers to int
// pointer to array of 5 int
// function returning pointer to array of 5 ints
\end{cfa}
\\
& &
\LstCommentStyle{//\ \ \ and taking an int argument}
\end{tabular}
\end{cquote}
As declaration complexity increases, it becomes corresponding difficult to read and understand the C declaration form.
Note, writing declarations left to right is common in other programming languages, where the function return-type is often placed after the parameter declarations.

\VRef[Table]{bkgd:ar:usr:avp} introduces the many layers of the C and \CFA array story, where the \CFA story is discussion in \VRef{XXX}.
The \CFA-thesis column shows the new array declaration form, which is my contributed improvements for safety and ergonomics.
The table shows there are multiple yet equivalent forms for the array types under discussion, and subsequent discussion shows interactions with orthogonal (but easily confused) language features.
Each row of the table shows alternate syntactic forms.
The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
Removing the declared variable @x@, gives the type used for variable, structure field, cast or error messages \PAB{(though note Section TODO points out that some types cannot be casted to)}.
Unfortunately, parameter declarations \PAB{(section TODO)} have more syntactic forms and rules.

\begin{table}
\centering
\caption{Syntactic Reference for Array vs Pointer. Includes interaction with \lstinline{const}ness.}
\label{bkgd:ar:usr:avp}
\begin{tabular}{ll|l|l|l}
        & Description & \multicolumn{1}{c|}{C} & \multicolumn{1}{c|}{\CFA}  & \multicolumn{1}{c}{\CFA-thesis} \\
        \hline
$\triangleright$ & value & @T x;@ & @T x;@ & \\
        \hline
        & immutable value & @const T x;@ & @const T x;@ & \\
        & & @T const x;@ & @T const x;@ & \\
        \hline \hline
$\triangleright$ & pointer to value & @T * x;@ & @* T x;@ & \\
        \hline
        & immutable ptr. to val. & @T * const x;@ & @const * T x;@ & \\
        \hline
        & ptr. to immutable val. & @const T * x;@ & @* const T x;@ & \\
        & & @T const * x;@ & @* T const x;@ & \\
        \hline \hline
$\triangleright$ & array of value & @T x[10];@ & @[10] T x@ & @array(T, 10) x@ \\
        \hline
        & ar.\ of immutable val. & @const T x[10];@ & @[10] const T x@ & @const array(T, 10) x@ \\
    & & @T const x[10];@ & @[10] T const x@ & @array(T, 10) const x@ \\
        \hline
        & ar.\ of ptr.\ to value & @T * x[10];@ & @[10] * T x@ & @array(T *, 10) x@ \\
        & & & & @array(* T, 10) x@ \\
        \hline
        & ar.\ of imm. ptr.\ to val. & @T * const x[10];@ & @[10] const * T x@ & @array(* const T, 10) x@ \\
        & & & & @array(const * T, 10) x@ \\
        \hline
        & ar.\ of ptr.\ to imm. val. & @const T * x[10];@ & @[10] * const T x@ & @array(const T *, 10) x@ \\
        & & @T const * x[10];@ & @[10] * T const x@ & @array(* const T, 10) x@ \\
        \hline \hline
$\triangleright$ & ptr.\ to ar.\ of value & @T (*x)[10];@ & @* [10] T x@ & @* array(T, 10) x@ \\
        \hline
        & imm. ptr.\ to ar.\ of val. & @T (* const x)[10];@ & @const * [10] T x@ & @const * array(T, 10) x@ \\
        \hline
        & ptr.\ to ar.\ of imm. val. & @const T (*x)[10];@ & @* [10] const T x@ & @* const array(T, 10) x@ \\
        & & @T const (*x)[10];@ & @* [10] T const x@ & @* array(T, 10) const x@ \\
        \hline
        & ptr.\ to ar.\ of ptr.\ to val. & @T *(*x)[10];@ & @* [10] * T x@ & @* array(T *, 10) x@ \\
        & & & & @* array(* T, 10) x@ \\
        \hline
\end{tabular}
\end{table}

TODO: Address these parked unfortunate syntaxes
\begin{itemize}
        \item static
        \item star as dimension
        \item under pointer decay: @int p1[const 3]@ being @int const *p1@
\end{itemize}


\subsection{Arrays decay and pointers diffract}

The last section established the difference between these four types:
\lstinput{3-6}{bkgd-carray-decay.c}
But the expression used for obtaining the pointer to the first element is pedantic.
The root of all C programmer experience with arrays is the shortcut
\lstinput{8-8}{bkgd-carray-decay.c}
which reproduces @pa0@, in type and value:
\lstinput{9-9}{bkgd-carray-decay.c}
The validity of this initialization is unsettling, in the context of the facts established in the last section.
Notably, it initializes name @pa0x@ from expression @ar@, when they are not of the same type:
\lstinput{10-10}{bkgd-carray-decay.c}

So, C provides an implicit conversion from @float[10]@ to @float *@.
\begin{quote}
Except when it is the operand of the @sizeof@ operator, or the unary @&@ operator, or is a string literal used to
initialize an array an expression that has type ``array of \emph{type}'' is converted to an expression with type
``pointer to \emph{type}'' that points to the initial element of the array object~\cite[\S~6.3.2.1.3]{C11}
\end{quote}
This phenomenon is the famous ``pointer decay,'' which is a decay of an array-typed expression into a pointer-typed one.
It is worthy to note that the list of exception cases does not feature the occurrence of @ar@ in @ar[i]@.
Thus, subscripting happens on pointers not arrays.

Subscripting proceeds first with pointer decay, if needed.  Next, \cite[\S~6.5.2.1.2]{C11} explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
\cite[\S~6.5.6.8]{C11} explains that the addition, of a pointer with an integer type,  is defined only when the pointer refers to an element that is in an array, with a meaning of ``@i@ elements away from,'' which is valid if @ar@ is big enough and @i@ is small enough.
Finally, \cite[\S~6.5.3.2.4]{C11} explains that the @*@ operator's result is the referenced element.
Taken together, these rules illustrate that @ar[i]@ and @i[a]@ mean the same thing!

Subscripting a pointer when the target is standard-inappropriate is still practically well-defined.
While the standard affords a C compiler freedom about the meaning of an out-of-bound access,
or of subscripting a pointer that does not refer to an array element at all,
the fact that C is famously both generally high-performance, and specifically not bound-checked,
leads to an expectation that the runtime handling is uniform across legal and illegal accesses.
Moreover, consider the common pattern of subscripting on a @malloc@ result:
\begin{cfa}
float * fs = malloc( 10 * sizeof(float) );
fs[5] = 3.14;
\end{cfa}
The @malloc@ behaviour is specified as returning a pointer to ``space for an object whose size is'' as requested (\cite[\S~7.22.3.4.2]{C11}).
But \emph{nothing} more is said about this pointer value, specifically that its referent might \emph{be} an array allowing subscripting.

Under this assumption, a pointer being subscripted (or added to, then dereferenced) by any value (positive, zero, or negative), gives a view of the program's entire address space, centred around the @p@ address, divided into adjacent @sizeof(*p)@ chunks, each potentially (re)interpreted as @typeof(*p)@.
I call this phenomenon ``array diffraction,''  which is a diffraction of a single-element pointer into the assumption that its target is in the middle of an array whose size is unlimited in both directions.
No pointer is exempt from array diffraction.
No array shows its elements without pointer decay.

A further pointer--array confusion, closely related to decay, occurs in parameter declarations.
\cite[\S~6.7.6.3.7]{C11} explains that when an array type is written for a parameter,
the parameter's type becomes a type that can be summarized as the array-decayed type.
The respective handling of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
\lstinput{12-16}{bkgd-carray-decay.c}
As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variable declaration,
@gcc@ also gives this code the warning for the first assertion:
\begin{cfa}
warning: 'sizeof' on array function parameter 'x' will return size of 'float *'
\end{cfa}
The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it is spelled:
\lstinput{18-21}{bkgd-carray-decay.c}
This fragment gives no warnings.

The shortened parameter syntax @T x[]@ is a further way to spell ``pointer.''
Note the opposite meaning of this spelling now, compared with its use in local variable declarations.
This point of confusion is illustrated in:
\lstinput{23-30}{bkgd-carray-decay.c}
The basic two meanings, with a syntactic difference helping to distinguish,
are illustrated in the declarations of @ca@ vs.\ @cp@,
whose subsequent @edit@ calls behave differently.
The syntax-caused confusion is in the comparison of the first and last lines,
both of which use a literal to initialize an object declared with spelling @T x[]@.
But these initialized declarations get opposite meanings,
depending on whether the object is a local variable or a parameter.

In summary, when a function is written with an array-typed parameter,
\begin{itemize}
        \item an appearance of passing an array by value is always an incorrect understanding
        \item a dimension value, if any is present, is ignored
        \item pointer decay is forced at the call site and the callee sees the parameter having the decayed type
\end{itemize}

Pointer decay does not affect pointer-to-array types, because these are already pointers, not arrays.
As a result, a function with a pointer-to-array parameter sees the parameter exactly as the caller does:
\lstinput{32-42}{bkgd-carray-decay.c}
\VRef[Table]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.

\begin{table}
\caption{Syntactic Reference for Decay during Parameter-Passing.
Includes interaction with \lstinline{const}ness, where ``immutable'' refers to a restriction on the callee's ability.}
\label{bkgd:ar:usr:decay-parm}
\centering
\begin{tabular}{llllll}
        & Description & Type & Parameter Declaration & \CFA  \\
        \hline
        & & & @T * x,@ & @* T x,@ \\
$\triangleright$ & pointer to value & @T *@ & @T x[10],@ & @[10] T x,@ \\
        & & & @T x[],@ & @[] T x,@ \\
        \hline
        & & & @T * const x,@ & @const * T x@ \\
        & immutable ptr.\ to val. & @T * const@ & @T x[const 10],@ & @[const 10] T x,@ \\
        & & & @T x[const],@ & @[const] T x,@\\
        \hline
        & & & @const T * x,@ & @ * const T x,@ \\
        & &     & @T const * x,@ & @ * T const x,@ \\
        & ptr.\ to immutable val. & @const T *@ & @const T x[10],@ & @[10] const T x,@ \\
        & & @T const *@ & @T const x[10],@ &  @[10] T const x,@ \\
        & & & @const T x[],@ & @[] const T x,@ \\
        & & & @T const x[],@ & @[] T const x,@ \\
        \hline \hline
        & & & @T (*x)[10],@ & @* [10] T x,@ \\
$\triangleright$ & ptr.\ to ar.\ of val. & @T(*)[10]@ & @T x[3][10],@ & @[3][10] T x,@ \\
        & & & @T x[][10],@ & @[][10] T x,@ \\
        \hline
        & & & @T ** x,@ & @** T x,@ \\
        & ptr.\ to ptr.\ to val. & @T **@ & @T * x[10],@ & @[10] * T x,@ \\
        & & & @T * x[],@ & @[] * T x,@ \\
        \hline
        & ptr.\ to ptr.\ to imm.\ val. & @const char **@ & @const char * argv[],@ & @[] * const char argv,@ \\
    & & & \emph{others elided} & \emph{others elided} \\
        \hline
\end{tabular}
\end{table}


\subsection{Lengths may vary, checking does not}

When the desired number of elements is unknown at compile time, a variable-length array is a solution:
\begin{cfa}
int main( int argc, const char * argv[] ) {
        assert( argc == 2 );
        size_t n = atol( argv[1] );
        assert( 0 < n );
        float ar[n];
        float b[10];
        // ... discussion continues here
}
\end{cfa}
This arrangement allocates @n@ elements on the @main@ stack frame for @ar@, called a \newterm{variable length array} (VLA), as well as 10 elements in the same stack frame for @b@.
The variable-sized allocation of @ar@ is provided by the @alloca@ routine, which bumps the stack pointer.
Note, the C standard supports VLAs~\cite[\S~6.7.6.2.4]{C11} as a conditional feature, but the \CC standard does not;
both @gcc@ and @g++@ support VLAs.
As well, there is misinformation about VLAs, \eg VLAs cause stack failures or are inefficient.
VLAs exist as far back as Algol W~\cite[\S~5.2]{AlgolW} and are a sound and efficient data type.

For high-performance applications, the stack size can be fixed and small (coroutines or user-level threads).
Here, VLAs can overflow the stack, so a heap allocation is used.
\begin{cfa}
float * ax1 = malloc( sizeof( float[n] ) );
float * ax2 = malloc( n * sizeof( float ) );
float * bx1 = malloc( sizeof( float[1000000] ) );
float * bx2 = malloc( 1000000 * sizeof( float ) );
\end{cfa}

Parameter dependency

Checking is best-effort / unsound

Limited special handling to get the dimension value checked (static)


\subsection{Dynamically sized, multidimensional arrays}

In C and \CC, ``multidimensional array'' means ``array of arrays.''  Other meanings are discussed in TODO.

Just as an array's element type can be @float@, so can it be @float[10]@.

While any of @float*@, @float[10]@ and @float(*)[10]@ are easy to tell apart from @float@, telling them apart from each other may need occasional reference back to TODO intro section.
The sentence derived by wrapping each type in @-[3]@ follows.

While any of @float*[3]@, @float[3][10]@ and @float(*)[3][10]@ are easy to tell apart from @float[3]@,
telling them apart from each other is what it takes to know what ``array of arrays'' really means.

Pointer decay affects the outermost array only

TODO: unfortunate syntactic reference with these cases:

\begin{itemize}
        \item ar. of ar. of val (be sure about ordering of dimensions when the declaration is dropped)
        \item ptr. to ar. of ar. of val
\end{itemize}


\subsection{Arrays are (but) almost values}

Has size; can point to

Can't cast to

Can't pass as value

Can initialize

Can wrap in aggregate

Can't assign


\subsection{Returning an array is (but) almost possible}


\subsection{The pointer-to-array type has been noticed before}

\subsection{Multi-Dimensional}

As in the last section, we inspect the declaration ...
\lstinput{16-18}{bkgd-carray-mdim.c}
The significant axis of deriving expressions from @ar@ is now ``itself,'' ``first element'' or ``first grand-element (meaning, first element of first element).''
\lstinput{20-44}{bkgd-carray-mdim.c}


\section{Linked List}

Linked-lists are blocks of storage connected using one or more pointers.
The storage block is logically divided into data and links (pointers), where the links are the only component used by the list structure.
Since the data is opaque, list structures are often polymorphic over the data, which is normally homogeneous.


\section{String}

A string is a logical sequence of symbols, where the form of the symbols can vary significantly: 7/8-bit characters (ASCII/Latin-1), or 2/4/8-byte (UNICODE) characters/symbols or variable length (UTF-8/16/32) characters.
A string can be read left-to-right, right-to-left, top-to-bottom, and have stacked elements (Arabic).

An integer character constant is a sequence of one or more multibyte characters enclosed in single-quotes, as in @'x'@.
A wide character constant is the same, except prefixed by the letter @L@, @u@, or @U@.
With a few exceptions detailed later, the elements of the sequence are any members of the source character set;
they are mapped in an implementation-defined manner to members of the execution character set.

A C character-string literal is a sequence of zero or more multibyte characters enclosed in double-quotes, as in @"xyz"@.
A UTF-8 string literal is the same, except prefixed by @u8@.
A wide string literal is the same, except prefixed by the letter @L@, @u@, or @U@.

For UTF-8 string literals, the array elements have type @char@, and are initialized with the characters of the multibyte character sequence, as encoded in UTF-8.
For wide string literals prefixed by the letter @L@, the array elements have type @wchar_t@ and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by the @mbstowcs@ function with an implementation-defined current locale.
For wide string literals prefixed by the letter @u@ or @U@, the array elements have type @char16_t@ or @char32_t@, respectively, and are initialized with the sequence of wide characters corresponding to the multibyte character sequence, as defined by successive calls to the @mbrtoc16@, or @mbrtoc32@ function as appropriate for its type, with an implementation-defined current locale.
The value of a string literal containing a multibyte character or escape sequence not represented in the executioncharacter set is implementation-defined.


Another bad C design decision is to have null-terminated strings rather than maintaining a separate string length.
\begin{quote}
Technically, a string is an array whose elements are single characters.
The compiler automatically places the null character @\0@ at the end of each such string, so programs can conveniently find the end.
This representation means that there is no real limit to how long a string can be, but programs have to scan one completely to determine its length.
\end{quote}