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

\chapter{Background}

This chapter states facts about the prior work, upon which my contributions build.
Each receives a justification of the extent to which its statement is phrased to provoke controversy or surprise.

\section{C}

\subsection{Common knowledge}

The reader is assumed to have used C or \CC for the coursework of at least four university-level courses, or have equivalent experience.
The current discussion introduces facts, unaware of which, such a functioning novice may be operating.

% TODO: decide if I'm also claiming this collection of facts, and test-oriented presentation is a contribution; if so, deal with (not) arguing for its originality

\subsection{Convention: C is more touchable than its standard}

When it comes to explaining how C works, I like illustrating definite program semantics.
I prefer doing so, over a quoting manual's suggested programmer's intuition, or showing how some compiler writers chose to model their problem.
To illustrate definite program semantics, I devise a program, whose behaviour exercises the point at issue, and I show its behaviour.

This behaviour is typically one of
\begin{itemize}
    \item my statement that the compiler accepts or rejects the program
    \item the program's printed output, which I show
    \item my implied assurance that its assertions do not fail when run
\end{itemize}

The compiler whose program semantics is shown is
\begin{lstlisting}
$ gcc --version
gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0
\end{lstlisting}
running on Architecture @x86_64@, with the same environment targeted.

Unless explicit discussion ensues about differences among compilers or with (versions of) the standard, it is further implied that there exists a second version of GCC and some version of Clang, running on and for the same platform, that give substantially similar behaviour.
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.


\subsection{C reports many ill-typed expressions as warnings}

TODO: typeset
\lstinputlisting[language=C, firstline=13, lastline=56]{bkgd-c-tyerr.c}


\section{C Arrays}

\subsection{C has an array type (!)}

TODO: typeset
\lstinputlisting[language=C, firstline=35, lastline=116]{bkgd-carray-arrty.c}

My contribution is enabled by recognizing
\begin{itemize}
    \item There is value in using a type that knows how big the whole thing is.
    \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]@.
\end{itemize}

Each of these sections, which introduces another layer of of the C arrays' story,
concludes with an \emph{Unfortunate Syntactic Reference}.
It shows how to spell the types under discussion,
along with interactions with orthogonal (but easily confused) language features.
Alterrnate spellings are listed withing 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{lstlisting}
[ * [10] T ] x;
\end{lstlisting}
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.

\noindent
\textbf{Unfortunate Syntactic Reference}

\noindent
\begin{tabular}{llllll}
    & Description & Type & Declaration & \CFA-C  & \CFA-Full \\ \hline
    $\triangleright$ & val.
        & @T@ 
        & @T x;@ 
        & @[ T ]@
        & 
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} 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;}   }
        & @[ const T ]@
        & 
        \\ \hline
    $\triangleright$ & ptr.\ to val.
        & @T *@ 
        & @T * x;@ 
        & @[ * T ]@
        &
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
        & @T * const@ 
        & @T * const x;@ 
        & @[ 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;}   }
        & @[ * const T ]@
        & 
        \\ \hline
    $\triangleright$ & ar.\ of val.
        & @T[10]@ 
        & @T x[10];@ 
        & @[ [10] T ]@
        & @[ array(T, 10) ]@
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{x[5]}}   }\vspace{2pt}
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T[10]} \\ \lstinline{T const[10]}   }
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T x[10];} \\ \lstinline{T const x[10];}   }
        & @[ [10] const T ]@
        & @[ const array(T, 10) ]@
        \\ \hline
    & ar.\ of ptr.\ to val.
        & @T*[10]@
        & @T *x[10];@
        & @[ [10] * T ]@
        & @[ array(* T, 10) ]@
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x[5]}}   }\vspace{2pt}
        & @T * const [10]@ 
        & @T * const x[10];@ 
        & @[ [10] const * T ]@
        & @[ array(const * T, 10) ]@
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ar.\ of ptr.\ to val.\\ \footnotesize{no writing the val.\ in \lstinline{*(x[5])}}   }\vspace{2pt}
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * [10]} \\ \lstinline{T const * [10]}   }
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T * x[10];} \\ \lstinline{T const * x[10];}   }
        & @[ [10] * const T ]@
        & @[ array(* const T, 10) ]@
        \\ \hline
    $\triangleright$ & ptr.\ to ar.\ of val.
        & @T(*)[10]@
        & @T (*x)[10];@
        & @[ * [10] T ]@
        & @[ * array(T, 10) ]@
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the ptr.\ in \lstinline{x}}   }\vspace{2pt}
        & @T(* const)[10]@
        & @T (* const x)[10];@
        & @[ const * [10] T ]@
        & @[ const * array(T, 10) ]@
        \\ \hline
    & \pbox{20cm}{ \vspace{2pt} ptr.\ to ar.\ of val.\\ \footnotesize{no writing the val.\ in \lstinline{(*x)[5]}}   }\vspace{2pt}
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T(*)[10]} \\ \lstinline{T const (*) [10]}   }
        & \pbox{20cm}{ \vspace{2pt} \lstinline{const T (*x)[10];} \\ \lstinline{T const (*x)[10];}   }
        & @[ * [10] const T ]@
        & @[ * const array(T, 10) ]@
        \\ \hline
    & ptr.\ to ar.\ of ptr.\ to val.
        & @T*(*)[10]@
        & @T *(*x)[10];@
        & @[ * [10] * T ]@
        & @[ * array(* T, 10) ]@
        \\ \hline
\end{tabular}


\subsection{Arrays decay and pointers diffract}

TODO: typeset
\lstinputlisting[language=C, firstline=4, lastline=26]{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 @a@ in @a[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 @a[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 @a@ 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 @a[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{lstlisting}
    float * fs = malloc( 10 * sizeof(float) );
    fs[5] = 3.14;
\end{lstlisting}
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 handlings of the following two parameter spellings shows that the array-spelled one is really, like the other, a pointer.
\lstinputlisting[language=C, firstline=40, lastline=44]{bkgd-carray-decay.c}
As the @sizeof(x)@ meaning changed, compared with when run on a similarly-spelled local variariable 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:
\lstinputlisting[language=C, firstline=60, lastline=63]{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:
\lstinputlisting[language=C, firstline=80, lastline=87]{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 initialze an object decalared with spelling @T x[]@.
But these initialized declarations get opposite meanings,
depending on whether the object is a local variable or a parameter.


In sumary, when a funciton 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 ignorred
    \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:
\lstinputlisting[language=C, firstline=100, lastline=110]{bkgd-carray-decay.c}


\noindent
\textbf{Unfortunate Syntactic Reference}

\noindent
(Parameter declaration; ``no writing'' refers to the callee's ability)

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



\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{lstlisting}
    int main( int argc, const char *argv[] ) {

        assert( argc == 2 );
        size_t n = atol( argv[1] );
        assert( 0 < n && n < 1000 );

        float a[n];
        float b[10];

        // ... discussion continues here
    }
\end{lstlisting}
This arrangement allocates @n@ elements on the @main@ stack frame for @a@,
just as it puts 10 elements on the @main@ stack frame for @b@.
The variable-sized allocation of @a@ 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{lstlisting}
    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{lstlisting}


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}


\section{\CFA}

Traditionally, fixing C meant leaving the C-ism alone, while providing a better alternative beside it.
(For later:  That's what I offer with array.hfa, but in the future-work vision for arrays, the fix includes helping programmers stop accidentally using a broken C-ism.)

\subsection{\CFA features interacting with arrays}

Prior work on \CFA included making C arrays, as used in C code from the wild,
work, if this code is fed into @cfacc@.
The quality of this this treatment was fine, with no more or fewer bugs than is typical.

More mixed results arose with feeding these ``C'' arrays into preexisting \CFA features.

A notable success was with the \CFA @alloc@ function,
which type information associated with a polymorphic return type
replaces @malloc@'s use of programmer-supplied size information.
\begin{lstlisting}
    // C, library
    void * malloc( size_t );
    // C, user
    struct tm * el1 = malloc(      sizeof(struct tm) );
    struct tm * ar1 = malloc( 10 * sizeof(struct tm) );

    // CFA, library
    forall( T * ) T * alloc();
    // CFA, user
    tm * el2 = alloc();
    tm (*ar2)[10] = alloc();
\end{lstlisting}
The alloc polymorphic return compiles into a hidden parameter, which receives a compiler-generated argument.
This compiler's argument generation uses type information from the left-hand side of the initialization to obtain the intended type.
Using a compiler-produced value eliminates an opportunity for user error.

TODO: fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa

Bringing in another \CFA feature, reference types, both resolves a sore spot of the last example, and gives a first example of an array-interaction bug.
In the last example, the choice of ``pointer to array'' @ar2@ breaks a parallel with @ar1@.
They are not subscripted in the same way.
\begin{lstlisting}
    ar1[5];
    (*ar2)[5];
\end{lstlisting}
Using ``reference to array'' works at resolving this issue.  TODO: discuss connection with Doug-Lea \CC proposal.
\begin{lstlisting}
    tm (&ar3)[10] = *alloc();
    ar3[5];
\end{lstlisting}
The implicit size communication to @alloc@ still works in the same ways as for @ar2@.

Using proper array types (@ar2@ and @ar3@) addresses a concern about using raw element pointers (@ar1@), albeit a theoretical one.
TODO xref C standard does not claim that @ar1@ may be subscripted,
because no stage of interpreting the construction of @ar1@ has it be that ``there is an \emph{array object} here.''
But both @*ar2@ and the referent of @ar3@ are the results of \emph{typed} @alloc@ calls,
where the type requested is an array, making the result, much more obviously, an array object.

The ``reference to array'' type has its sore spots too.  TODO see also @dimexpr-match-c/REFPARAM_CALL (under TRY_BUG_1)@



TODO: I fixed a bug associated with using an array as a T.  I think.  Did I really?  What was the bug?