source: doc/theses/mike_brooks_MMath/background.tex @ d3a49864

\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}

The following sections introduce the many layers of the C array story, concluding with an \emph{Unfortunate Syntactic Reference}.
It shows how to define (spell) the types under discussion, along with interactions with orthogonal (but easily confused) language features.
Alternate spellings are listed within a row.
The simplest occurrences of types distinguished in the preceding discussion are marked with $\triangleright$.
The Type column gives the spelling used in a cast or error message (though note Section TODO points out that some types cannot be casted to).
The Declaration column gives the spelling used in an object declaration, such as variable or aggregate member; parameter declarations (section TODO) follow entirely different rules.

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-specific spellings (not yet introduced) are also included here for referenceability; these can be skipped on linear reading.
The \CFA-C column gives the, more fortunate, ``new'' syntax of section TODO, for spelling \emph{exactly the same type}.
This fortunate syntax does not have different spellings for types vs declarations;
a declaration is always the type followed by the declared identifier name;
for the example of letting @x@ be a \emph{pointer to array}, the declaration is spelled:
\begin{cfa}
* [10] T x;
\end{cfa}
The \CFA-Full column gives the spelling of a different type, introduced in TODO, which has all of my contributed improvements for safety and ergonomics.

Another example of confusion results from the fact that a routine name and its parameters are embedded within the return type, mimicking the way the return value is used at the routine's call site.
For example, a routine returning a \Index{pointer} to an array of integers is defined and used in the following way:
\begin{cfa}
int @(*@f@())[@5@]@ {...}; $\C{// definition}$
 ... @(*@f@())[@3@]@ += 1; $\C{// usage}$
\end{cfa}
Essentially, the return type is wrapped around the routine 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}

\CFA provides its own type, variable and routine declarations, using a different 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.
In the following example, {\color{red}red} is the base type and {\color{blue}blue} is qualifiers.
The \CFA declarations move the qualifiers to the left of the base type, \ie move the blue to the left of the red, while the qualifiers have the same meaning but are ordered left to right to specify a variable's type.
\begin{cquote}
\begin{tabular}{@{}l@{\hspace{3em}}l@{}}
\multicolumn{1}{c@{\hspace{3em}}}{\textbf{C}}   & \multicolumn{1}{c}{\textbf{\CFA}}     \\
\begin{cfa}[moredelim={**[is][\color{blue}]{\#}{\#}}]
@int@ #*# x1 #[5]#;
@int@ #(*#x2#)[5]#;
#int (*#f@( int p )@#)[5]#;
\end{cfa}
&
\begin{cfa}[moredelim={**[is][\color{blue}]{\#}{\#}}]
#[5] *# @int@ x1;
#* [5]# @int@ x2;
#[* [5] int]# f@( int p )@;
\end{cfa}
\end{tabular}
\end{cquote}

\VRef[Figure]{bkgd:ar:usr:avp} gives this reference for the discussion so far.

\begin{figure}
\centering
\setlength{\tabcolsep}{3pt}
\begin{tabular}{ll|l|l|l|l}
        & Description & Type & Declaration & \CFA  & \CFA-thesis \\ \hline
        $\triangleright$ & val. & @T@ & @T x;@ & @T@ & \\
        \hline
        & immutable val. & @const T@ & @T const x;@ & @const T@ & \\
        & & @T const@ & @T const x;@ & @T const@ & \\
        \hline \hline
        $\triangleright$ & ptr.\ to val. & @T *@ & @T * x;@ & @* T@ & \\
        \hline
        & immutable ptr. to val. & @T * const@ & @T * const x;@ & @const * T@ & \\
        \hline
        & ptr. to immutable val. & @const T *@ & @const T * x;@ & @* const T@ & \\
        & & @T const *@ & @T const * x;@ & @* T const@ & \\
        \hline \hline
        $\triangleright$ & ar.\ of val. & @T[10]@ & @T x[10];@ & @[10] T@ & @array(T, 10)@ \\
        \hline
        & ar.\ of immutable val. & @const T[10]@ & @const T x[10];@ & @[10] const T@ & @const array(T, 10)@ \\
    & & @T const [10]@ & @T const x[10];@ & @[10] T const@ & @array(T, 10) const@ \\
        \hline
        & ar.\ of ptr.\ to val. & @T * [10]@ & @T * x[10];@ & @[10] * T@ & @array(T * | * T, 10)@ \\
        \hline
        & ar.\ of imm. ptr.\ to val. & @T * const [10]@ & @T * const x[10];@ & @[10] const * T@ & @array(const * T, 10)@ \\
        \hline
        & ar.\ of ptr.\ to imm. val. & @const T * [10]@ & @const T * x[10];@ & @[10] * const T@ & @array(* const T, 10)@ \\
        & & @T const * [10]@ & @T const * x[10];@ & @[10] * T const@ & @array(* T const, 10)@ \\
        \hline \hline
        $\triangleright$ & ptr.\ to ar.\ of val. & @T(*)[10]@ & @T (*x)[10];@ & @* [10] T@ & @* array(T, 10)@ \\
        \hline
        & imm. ptr.\ to ar.\ of val. & @T(* const)[10]@ & @T (* const x)[10];@ & @const * [10] T@ & @const * array(T, 10)@ \\
        \hline
        & ptr.\ to ar.\ of imm. val. & @const T(*)[10]@ & @const T (*x)[10];@ & @* [10] const T@ & @* const array(T, 10)@ \\
        & & @T const (*) [10]}@ & @T const (*x)[10];@ & @* [10] T const@ & @* array(T, 10) const@ \\
        \hline
        & ptr.\ to ar.\ of ptr.\ to val. & @T*(*)[10]@ & @T *(*x)[10];@ & @* [10] * T@ & @* array(T * | * T, 10)@ \\
        \hline
\end{tabular}
\caption{Unfortunate Syntactic Reference for Array vs Pointer.  Includes interaction with constness.}
\label{bkgd:ar:usr:avp}
\end{figure}





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*@, as described in ARM-6.3.2.1.3:
\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 type'' is
converted to an expression with type ``pointer to type'' that points to the initial element of
the array object
\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, ARM-6.5.2.1.2 explains that @ar[i]@ is treated as if it were @(*((a)+(i)))@.
ARM-6.5.6.8 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, ARM-6.5.3.2.4 explains that the @*@ operator's result is the referenced element.

Taken together, these rules also happen to 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 (ARM-7.22.3.4.2).
But program says \emph{nothing} more about this pointer value, that might cause its referent to \emph{be} an array, before doing the subscript.

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.
ARM-6.7.6.3.7 explains that when an array type is written for a parameter,
the parameter's type becomes a type that I summarize as being 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: ```sizeof' on array function parameter `x' will return size of `float *'.''

The caller of such a function is left with the reality that a pointer parameter is a pointer, no matter how it's 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[Figure]{bkgd:ar:usr:decay-parm} gives the reference for the decay phenomenon seen in parameter declarations.

\begin{figure}
\centering
\begin{tabular}{llllll}
        & Description & Type & Param. Decl & \CFA-C  \\ \hline
        $\triangleright$ & ptr.\ to val.
            & @T *@ 
            & \pbox{20cm}{ \vspace{2pt} \lstinline{T * x,} \\ \lstinline{T x[10],} \\ \lstinline{T x[],}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * T ]} \\ \lstinline{[ [10] T ]} \\ \lstinline{[ [] T  ]}   }
            \\ \hline
        & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
            & @T * const@ 
            & \pbox{20cm}{ \vspace{2pt} \lstinline{T * const x,} \\ \lstinline{T x[const 10],} \\ \lstinline{T x[const],}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[ const * T ]} \\ \lstinline{[ [const 10] T ]} \\ \lstinline{[ [const] T  ]}   }
            \\ \hline
        & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*x}}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{const T *} \\ \lstinline{T const *}   }
            & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x,} \\ \lstinline{T const * x,} \\ \lstinline{const T x[10],} \\ \lstinline{T const x[10],} \\ \lstinline{const T x[],} \\ \lstinline{T const x[],}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[* const T]} \\ \lstinline{[ [10] const T ]} \\ \lstinline{[ [] const T  ]}   }
            \\ \hline \hline
        $\triangleright$ & ptr.\ to ar.\ of val.
            & @T(*)[10]@
            & \pbox{20cm}{ \vspace{2pt} \lstinline{T (*x)[10],} \\ \lstinline{T x[3][10],} \\ \lstinline{T x[][10],}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[* [10] T]} \\ \lstinline{[ [3] [10] T ]} \\ \lstinline{[ [] [10] T  ]}   }
            \\ \hline
        & ptr.\ to ptr.\ to val.
            & @T **@
            & \pbox{20cm}{ \vspace{2pt} \lstinline{T ** x,} \\ \lstinline{T *x[10],} \\ \lstinline{T *x[],}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[ * * T ]} \\ \lstinline{[ [10] * T ]} \\ \lstinline{[ [] * T  ]}   }
            \\ \hline
        & \pbox{20cm}{ \vspace{2pt} ptr.\ to ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{**argv}}   }\vspace{2pt}
            & @const char **@
            & \pbox{20cm}{ \vspace{2pt} \lstinline{const char *argv[],} \\ \footnotesize{(others elided)}   }\vspace{2pt}
            & \pbox{20cm}{ \vspace{2pt} \lstinline{[ [] * const char ]} \\ \footnotesize{(others elided)}   }
            \\ \hline
\end{tabular}
\caption{Unfortunate Syntactic Reference for Decay during Parameter-Passing.  Includes interaction with constness, where ``no writing'' refers to a restriction on the callee's ability.}
\label{bkgd:ar:usr:decay-parm}
\end{figure}


\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 && n < 1000 );

        float ar[n];
        float b[10];

        // ... discussion continues here
}
\end{cfa}
This arrangement allocates @n@ elements on the @main@ stack frame for @ar@, just as it puts 10 elements on the @main@ stack frame for @b@.
The variable-sized allocation of @ar@ is provided by @alloca@.

In a situation where the array sizes are not known to be small enough for stack allocation to be sensible, corresponding heap allocations are achievable as:
\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}


VLA

Parameter dependency

Checking is best-effort / unsound

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



\subsection{C has full-service, dynamically sized, multidimensional arrays (and \CC does not)}

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}


\section{String}