source: doc/theses/mike_brooks_MMath/array.tex @ 1a9592a

\chapter{Array}

\section{Features Added}

The present work adds a type @array@ to the \CFA standard library~\cite{Cforall}.

This array's length is statically governed and dynamically valued.  This static governance achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference).  In present state, this work is a runtime libray accessed through a system of macros, while section [TODO: discuss C conexistence] discusses a path for the new array type to be accessed directly by \CFA's array syntax, replacing the lifted C array that this syntax currently exposes.

This section presents motivating examples of the new array type's usage, and follows up with definitions of the notations that appear.

The core of the new array governance is tracking all array lengths in the type system.  Dynamically valued lengths are represented using type variables.  The stratification of type variables preceding object declarations makes a length referenceable everywhere that it is needed.  For example, a declaration can share one length, @N@, among a pair of parameters and the return.
\lstinputlisting[language=CFA, firstline=50, lastline=59]{hello-array.cfa}
Here, the function @f@ does a pointwise comparison, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated bool array.

The array type uses the parameterized length information in its @sizeof(-)@ determination, illustrated in the example's call to @alloc@.  That call requests an allocation of type @array(bool, N)@, which the type system deduces from the left-hand side of the initialization, into the return type of the @alloc@ call.  Preexesting \CFA behaviour is leveraged here, both in the return-type-only polymorphism, and the @sized(T)@-aware standard-library @alloc@ routine.  The new @array@ type plugs into this behaviour by implementing the @sized@/@sizeof(-)@ assertion to have the intuitive meaning.  As a result, this design avoids an opportunity for programmer error by making the size/length communication to a called routine implicit, compared with C's @calloc@ (or the low-level \CFA analog @aalloc@) which take an explicit length parameter not managed by the type system.

A harness for this @f@ function shows how dynamic values are fed into the system.
\lstinputlisting[language=CFA, firstline=100, lastline=119]{hello-array.cfa}
Here, the @a@ sequence is loaded with decreasing values, and the @b@ sequence with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later.  The driver program is run with two different inputs of sequence length.

The loops in the driver follow the more familiar pattern of using the ordinary variable @n@ to convey the length.  The type system implicitly captures this value at the call site (@main@ calling @f@) and makes it available within the callee (@f@'s loop bound).

The two parts of the example show @Z(n)@ adapting a variable into a type-system governed length (at @main@'s declarations of @a@, @b@, and @result@), @z(N)@ adapting in the opposite direction (at @f@'s loop bound), and a passthru use of a governed length (at @f@'s declaration of @ret@.)  It is hoped that future language integration will allow the macros @Z@ and @z@ to be omitted entirely from the user's notation, creating the appearance of seamlessly interchanging numeric values with appropriate generic parameters.

The macro-assisted notation, @forall...ztype@, participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function body.  So future language integration only sweetens this form and does not seek to elimimate the declaration.  The present form is chosen to parallel, as closely as a macro allows, the existing forall forms:
\begin{lstlisting}
  forall( dtype T  ) ...
  forall( otype T  ) ...
  forall( ztype(N) ) ...
\end{lstlisting}

The notation @array(thing, N)@ is also macro-assisted, though only in service of enabling multidimensional uses discussed further in section \ref{toc:mdimpl}.  In a single-dimensional case, the marco expansion gives a generic type instance, exactly like the original form suggests.



In summary:

\begin{tabular}{p{15em}p{20em}}
  @ztype( N )@ & within a forall, declares the type variable @N@ to be a governed length \\[0.25em]
  @Z( @ $e$ @ )@ & a type representing the value of $e$ as a governed length, where $e$ is a @size_t@-typed expression \\[0.25em]
  @z( N )@ & an expression of type @size_t@, whose value is the governed length @N@ \\[0.25em]
  @array( thing, N0, N1, ... )@
  &  a type wrapping $\prod_i N_i$ adjacent occurrences of @thing@ objects
\end{tabular}

Unsigned integers have a special status in this type system.  Unlike how C++ allows @template< size_t N, char * msg, typename T >...@ declarations, this system does not accommodate values of any user-provided type.  TODO: discuss connection with dependent types.


An example of a type error demonstrates argument safety.  The running example has @f@ expecting two arrays of the same length.  A compile-time error occurs when attempting to call @f@ with arrays whose lengths may differ.
\lstinputlisting[language=CFA, firstline=150, lastline=155]{hello-array.cfa}
As is common practice in C, the programmer is free to cast, to assert knownledge not shared with the type system.
\lstinputlisting[language=CFA, firstline=200, lastline=202]{hello-array.cfa}

Argument safety, and the associated implicit communication of length, work with \CFA's generic types too.  As a structure can be defined over a parameterized element type, so can it be defined over a parameterized length.  Doing so gives a refinement of C's ``flexible array member'' pattern, that allows nesting structures with array members anywhere within other structures.
\lstinputlisting[language=CFA, firstline=20, lastline=26]{hello-accordion.cfa}
This structure's layout has the starting offest of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic paramters.  For a function that operates on a @request@ structure, the type system handles this variation transparently.
\lstinputlisting[language=CFA, firstline=50, lastline=57]{hello-accordion.cfa}
In the example runs of a driver program, different offset values are navigated in the two cases.
\lstinputlisting[language=CFA, firstline=100, lastline=115]{hello-accordion.cfa}
The output values show that @summarize@ and its caller agree on both the offsets (where the callee starts reading @cost_contribs@ and where the callee writes @total_cost@).  Yet the call site still says just, ``pass the request.''


\section{Multidimensional implementation}
\label{toc:mdimpl}


TODO: introduce multidimensional array feature and approaches

The new \CFA standard library @array@ datatype supports multidimensional uses more richly than the C array.  The new array's multimentsional interface and implementation, follows an array-of-arrays setup, meaning, like C's @float[n][m]@ type, one contiguous object, with coarsely-strided dimensions directly wrapping finely-strided dimensions.  This setup is in contrast with the pattern of array of pointers to other allocations representing a sub-array.  Beyond what C's type offers, the new array brings direct support for working with a noncontiguous array slice, allowing a program to work with dimension subscripts given in a non-physical order.  C and C++ require a programmer with such a need to manage pointer/offset arithmetic manually.

Examples are shown using a $5 \times 7$ float array, @a@, loaded with increments of $0.1$ when stepping across the length-7 finely-strided dimension shown on columns, and with increments of $1.0$ when stepping across the length-5 corsely-strided dimension shown on rows.
\lstinputlisting[language=CFA, firstline=120, lastline=128]{hello-md.cfa}
The memory layout of @a@ has strictly increasing numbers along its 35 contiguous positions.

A trivial form of slicing extracts a contiguous inner array, within an array-of-arrays.  Like with the C array, a lesser-dimensional array reference can be bound to the result of subscripting a greater-dimensional array, by a prefix of its dimensions.  This action first subscripts away the most coaresly strided dimensions, leaving a result that expects to be be subscripted by the more finely strided dimensions.
\lstinputlisting[language=CFA, firstline=60, lastline=66]{hello-md.cfa}
\lstinputlisting[language=CFA, firstline=140, lastline=140]{hello-md.cfa}

This function declaration is asserting too much knowledge about its parameter @c@, for it to be usable for printing either a row slice or a column slice.  Specifically, declaring the parameter @c@ with type @array@ means that @c@ is contiguous.  However, the function does not use this fact.  For the function to do its job, @c@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@), with governed length @N@.  The new-array library provides the trait @ix@, so-defined.  With it, the original declaration can be generalized, while still implemented with the same body, to the latter declaration:
\lstinputlisting[language=CFA, firstline=40, lastline=44]{hello-md.cfa}
\lstinputlisting[language=CFA, firstline=145, lastline=145]{hello-md.cfa}

Nontrivial slicing, in this example, means passing a noncontiguous slice to @print1d@.  The new-array library provides a ``subscript by all'' operation for this purpose.  In a multi-dimensional subscript operation, any dimension given as @all@ is left ``not yet subscripted by a value,'' implementing the @ix@ trait, waiting for such a value.
\lstinputlisting[language=CFA, firstline=150, lastline=151]{hello-md.cfa}

The example has shown that @a[2]@ and @a[[2, all]]@ both refer to the same, ``2.*'' slice.  Indeed, the various @print1d@ calls under discussion access the entry with value 2.3 as @a[2][3]@, @a[[2,all]][3]@, and @a[[all,3]][2]@.  This design preserves (and extends) C array semantics by defining @a[[i,j]]@ to be @a[i][j]@ for numeric subscripts, but also for ``subscripting by all''.  That is:

\begin{tabular}{cccccl}
    @a[[2,all]][3]@  &  $=$  &  @a[2][all][3]@  & $=$  &  @a[2][3]@  & (here, @all@ is redundant)  \\
    @a[[all,3]][2]@  &  $=$  &  @a[all][3][2]@  & $=$  &  @a[2][3]@  & (here, @all@ is effective)
\end{tabular}

Narrating progress through each of the @-[-][-][-]@ expressions gives, firstly, a definition of @-[all]@, and secondly, a generalization of C's @-[i]@.

\noindent Where @all@ is redundant:

\begin{tabular}{ll}
    @a@  & 2-dimensional, want subscripts for coarse then fine \\
    @a[2]@  & 1-dimensional, want subscript for fine; lock coarse = 2 \\
    @a[2][all]@  & 1-dimensional, want subscript for fine \\
    @a[2][all][3]@  & 0-dimensional; lock fine = 3
\end{tabular}

\noindent Where @all@ is effective:

\begin{tabular}{ll}
    @a@  & 2-dimensional, want subscripts for coarse then fine \\
    @a[all]@  & 2-dimensional, want subscripts for fine then coarse \\
    @a[all][3]@  & 1-dimensional, want subscript for coarse; lock fine = 3 \\
    @a[all][3][2]@  & 0-dimensional; lock coarse = 2
\end{tabular}

The semantics of @-[all]@ is to dequeue from the front of the ``want subscripts'' list and re-enqueue at its back.  The semantics of @-[i]@ is to dequeue from the front of the ``want subscripts'' list and lock its value to be @i@.

Contiguous arrays, and slices of them, are all realized by the same underlying parameterized type.  It includes stride information in its metatdata.  The @-[all]@ operation is a conversion from a reference to one instantiation, to a reference to another instantiation.  The running example's @all@-effective step, stated more concretely, is:

\begin{tabular}{ll}
    @a@       & : 5 of ( 7 of float each spaced 1 float apart ) each spaced 7 floats apart \\
    @a[all]@  & : 7 of ( 5 of float each spaced 7 floats apart ) each spaced 1 float apart
\end{tabular}

\begin{figure}
    \includegraphics{measuring-like-layout}
    \caption{Visualization of subscripting by value and by \lstinline[language=CFA,basicstyle=\ttfamily]{all}, for \lstinline[language=CFA,basicstyle=\ttfamily]{a} of type \lstinline[language=CFA,basicstyle=\ttfamily]{array( float, Z(5), Z(7) )}. The horizontal dimension represents memory addresses while vertical layout is conceptual.}
    \label{fig:subscr-all}
\end{figure}

\noindent While the latter description implies overlapping elements, Figure \ref{fig:subscr-all} shows that the overlaps only occur with unused spaces between elements.  Its depictions of @a[all][...]@ show the navigation of a memory layout with nontrivial strides, that is, with ``spaced \_ floats apart'' values that are greater or smaller than the true count of valid indeces times the size of a logically indexed element.  Reading from the bottom up, the expression @a[all][3][2]@ shows a float, that is masquerading as a @float[7]@, for the purpose of being arranged among its peers; five such occurrences form @a[all][3]@.  The tail of flatter boxes extending to the right of a poper element represents this stretching.  At the next level of containment, the structure @a[all][3]@ masquerades as a @float[1]@, for the purpose of being arranged among its peers; seven such occurrences form @a[all]@.  The verical staircase arrangement represents this compression, and resulting overlapping.

The new-array library defines types and operations that ensure proper elements are accessed soundly in spite of the overlapping.  The private @arpk@ structure (array with explicit packing) is generic over these two types (and more): the contained element, what it is masquerading as.  This structure's public interface is the @array(...)@ construction macro and the two subscript operators.  Construction by @array@ initializes the masquerading-as type information to be equal to the contained-element information.  Subscrpting by @all@ rearranges the order of masquerading-as types to achieve, in genernal, nontrivial striding.  Subscripting by a number consumes the masquerading-as size of the contained element type, does normal array stepping according to that size, and returns there element found there, in unmasked form.

The @arpk@ structure and its @-[i]@ operator are thus defined as:
\begin{lstlisting}
forall( ztype(N),               // length of current dimension
        dtype(S) | sized(S),    // masquerading-as
        dtype E_im,             // immediate element, often another array
        dtype E_base            // base element, e.g. float, never array
      ) {
    struct arpk {
        S strides[z(N)];        // so that sizeof(this) is N of S
    };

    // expose E_im, stride by S
    E_im & ?[?]( arpk(N, S, E_im, E_base) & a, ptrdiff_t i ) {
        return (E_im &) a.strides[i];
    }
}
\end{lstlisting}

An instantion of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ exapnsion, which is @arpk( N0, Rec, Rec, E_base )@, where @Rec@ is @array(E_base, N1, ...)@.  In the base case, @array(E_base)@ is just @E_base@.  Because this construction uses the same value for the generic parameters @S@ and @E_im@, the resulting layout has trivial strides.

Subscripting by @all@, to operate on nontrivial strides, is a dequeue-enqueue operation on the @E_im@ chain, which carries @S@ instatiations, intact, to new positions.  Expressed as an operation on types, this rotation is:
\begin{eqnarray*}
suball( arpk(N, S, E_i, E_b) ) & = & enq( N, S, E_i, E_b ) \\
enq( N, S, E_b, E_b ) & = & arpk( N, S, E_b, E_b ) \\
enq( N, S, arpk(N', S', E_i', E_b), E_b ) & = & arpk( N', S', enq(N, S, E_i', E_b), E_b )
\end{eqnarray*}