Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision 4904b0516ef6e24899be795ccffb6835533284bc) +++ doc/theses/mike_brooks_MMath/array.tex (revision 4226eedea8f0ca871b86969883d3dd7a5d0355b0) @@ -8,4 +8,5 @@ However, a few compatibility-breaking changes to the behaviour of the C array are necessary, both as an implementation convenience and to fix C's lax treatment of arrays. Hence, the @array@ type is an opportunity to start from a clean slate and show a cohesive selection of features, making it unnecessary to deal with every inherited complexity of the C array. +Future work is to sugar the @array@ syntax to look like C arrays \see{\VRef{f:FutureWork}}. @@ -79,5 +80,5 @@ \item Provide a dimension/subscript-checked array-type in the \CFA standard library, where the array's length is statically managed and dynamically valued. \item Provide argument/parameter passing safety for arrays and subscript safety. -\item Identify the interesting specific abilities available by the new @array@ type. +\item Identify the interesting abilities available by the new @array@ type. \item Where there is a gap concerning this feature's readiness for prime-time, identification of specific workable improvements that are likely to close the gap. \end{enumerate} @@ -135,5 +136,4 @@ Except for the lifetime-management issue of @result@, \ie explicit @free@, this program has eliminated both the syntactic and semantic problems associated with C arrays and their usage. The result is a significant improvement in safety and usability. - In summary: \begin{itemize}[leftmargin=*] @@ -145,5 +145,5 @@ The value of an @N@-expression is the acquired length, derived from the usage site, \ie generic declaration or function call. \item -@array( thing, N0, N1, ... )@ is a multi-dimensional type wrapping $\prod_i N_i$ adjacent occurrences of @thing@-typed objects. +@array( T, N0, N1, ... )@ is a multi-dimensional type wrapping $\prod_i N_i$ contiguous @T@-typed objects. \end{itemize} @@ -181,4 +181,5 @@ \begin{figure} +\setlength{\tabcolsep}{3pt} \begin{tabular}{@{}ll@{}} \begin{c++} @@ -189,10 +190,9 @@ } int main() { - const size_t n = 10; // must be constant - int ret[n], x[n]; + const size_t n = 10; $\C[1.9in]{// must be constant}$ + int ret[n], x[n]; $\C{// static size}$ for ( int i = 0; i < n; i += 1 ) x[i] = i; @copy( ret, x );@ - for ( int i = 0; i < n; i += 1 ) - cout << ret[i] << ' '; + for ( int i = 0; i < n; i += 1 ) cout << ret[i] << ' '; cout << endl; } @@ -201,5 +201,5 @@ \begin{cfa} int main() { - @forall( T, [N] )@ // nested function + @forall( T, [N] )@ $\C{// nested function}$ void copy( array( T, @N@ ) & ret, array( T, @N@ ) & x ) { for ( i; N ) ret[i] = x[i]; @@ -207,9 +207,8 @@ size_t n; sin | n; - array( int, n ) ret, x; - for ( i; n ) x[i] = i; - @copy( ret, x );@ - for ( i; n ) - sout | ret[i] | nonl; + array( int, n ) ret, x; $\C{// dynamic-fixed size}$ + for ( i; n ) x[i] = i; $\C{// initialize}$ + @copy( ret, x );@ $\C{// alternative ret = x}$ + for ( i; n ) sout | ret[i] | nonl; $\C{// print}\CRT$ sout | nl; } @@ -260,10 +259,13 @@ \end{cfa} This ability to avoid casting and size arithmetic improves safety and usability over C flexible array members. +The example program prints the courses in each student's preferred order, all using the looked-up display names. +When a function operates on a @School@ structure, the type system handles its memory layout transparently. +In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class. Finally, inputs and outputs are given on the right for different sized schools. -The example program prints the courses in each student's preferred order, all using the looked-up display names. \begin{figure} \begin{lrbox}{\myboxA} \begin{tabular}{@{}l@{}} +\lstinput{30-38}{hello-accordion.cfa} \\ \lstinput{50-55}{hello-accordion.cfa} \\ \lstinput{90-98}{hello-accordion.cfa} @@ -295,10 +297,6 @@ \end{figure} -When a function operates on a @School@ structure, the type system handles its memory layout transparently. -\lstinput{30-36}{hello-accordion.cfa} -In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class? - - -\section{Dimension Parameter Implementation} + +\section{Single Dimension Array Implementation} The core of the preexisting \CFA compiler already has the ``heavy equipment'' needed to provide the feature set just reviewed (up to bugs in cases not yet exercised). @@ -309,16 +307,17 @@ This new dimension type, encoding the array dimension within it, is the first limited \newterm{dependent type}~\cite{DependentType} added to the \CFA type-system and is used at appropriate points during type resolution. -Furthermore, the @array@ type itself is really ``icing on the cake.'' -Presenting its full version is deferred until \VRef[Section]{s:ArrayMdImpl} -(where added complexity needed for multiple dimensions is considered). -But simplifications close enough for the present discussion are: +% Furthermore, the @array@ type itself is really ``icing on the cake.'' +% Presenting its full version is deferred until \VRef[Section]{s:ArrayMdImpl} (where added complexity needed for multiple dimensions is considered). +The new array implementation is broken into single and multiple dimensions \see{\VRef[Section]{s:ArrayMdImpl}}. +Details of the @array@ macros are sprinkles among the implementation discussion. +The single dimension implementation begins with a simple example without @array@ macros. \begin{cfa} forall( [N] ) struct array_1d_float { - float items[N]; + float items[N]; $\C[2in]{// monomorphic type}$ }; forall( T, [N] ) struct array_1d_T { - T items[N]; + T items[N]; $\C{// polymorphic type}\CRT$ }; \end{cfa} @@ -428,5 +427,5 @@ At the end of the desugaring and downstream processing, the original C idiom of ``pass both a length parameter and a pointer'' has been reconstructed. In the programmer-written form, only the @thing@ is passed. -The compiler's action produces the more complex form, which if handwritten, would be error-prone. +The compiler's action produces the more complex form, which if handwritten, is error-prone. At the compiler front end, the parsing changes AST schema extensions and validation rules for enabling the sugared user input. @@ -484,5 +483,5 @@ array( float, @n@ ) x; array( float, @999@ ) * xp = &x; $\C{// static rejection here}$ -(*xp)[@500@]; $\C{// runtime check passes}$ +(*xp)[@500@]; $\C{// runtime check would pass if program compiled}$ \end{cfa} The way the \CFA array is implemented, the type analysis for this case reduces to a case similar to the earlier C version. @@ -541,5 +540,5 @@ extern float g(); void f() { - float x[@n@] = { g() }; + float x[@n@] = { @g()@ }; // side-effect float (*xp)[@n@] = x; // reject } @@ -594,5 +593,5 @@ \item[Potentially Unstable] The catch-all category. Notable examples include: - any function-call result, @float x[foo()]@, the particular function-call result that is a pointer dereference, @void f(const int * n)@ @{ float x[*n]; }@, and any use of a reference-typed variable. + any function-call result, @float x[foo()]@, the particular function-call result that is a pointer dereference, @void f(const int * n)@ @{ float x[*n]; }@, and any use of a reference-type variable. \end{description} Within these groups, my \CFA rules are: @@ -756,11 +755,11 @@ The conservatism of the new rule set can leave a programmer requiring a recourse, when needing to use a dimension expression whose stability argument is more subtle than current-state analysis. This recourse is to declare an explicit constant for the dimension value. -Consider these two dimension expressions, whose uses are rejected by the blunt current-state rules: +Consider these two dimension expressions, rejected by the blunt current-state rules: \begin{cfa} void f( int @&@ nr, @const@ int nv ) { float x[@nr@]; - float (*xp)[@nr@] = &x; // reject: nr varying (no references) + float (*xp)[@nr@] = &x; $\C[2.5in]{// reject: nr varying (no references)}$ float y[@nv + 1@]; - float (*yp)[@nv + 1@] = &y; // reject: ?+? unpredictable (no functions) + float (*yp)[@nv + 1@] = &y; $\C{// reject: ?+? unpredictable (no functions)}\CRT$ } \end{cfa} @@ -773,8 +772,8 @@ @const int nx@ = nr; float x[nx]; - float (*xp)[nx] = & x; // accept + float (*xp)[nx] = & x; $\C[2.5in]{// accept}$ @const int ny@ = nv + 1; float y[ny]; - float (*yp)[ny] = & y; // accept + float (*yp)[ny] = & y; $\C{// accept}\CRT$ } \end{cfa} @@ -785,6 +784,6 @@ Rather obviously, every array must be subscriptable, even a bizarre one: \begin{cfa} -array( float, @rand(10)@ ) x; -x[@0@]; // 10% chance of bound-check failure +array( float, @rand(10)@ ) x; $\C[2.5in]{// x[0] => no elements}$ +x[@0@]; $\C{// 10\% chance of bound-check failure}\CRT$ \end{cfa} Less obvious is that the mechanism of subscripting is a function call, which must communicate length accurately. @@ -855,5 +854,5 @@ The new \CFA standard-library @array@-datatype supports richer multidimensional features than C. The new array implementation follows C's contiguous approach, \ie @float [r][c]@, with one contiguous object subscripted by coarsely-strided dimensions directly wrapping finely-strided dimensions. -Beyond what C's array 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. +Beyond what C's array type offers, the new array brings direct support for working with a \emph{noncontiguous} array slice, allowing a program to work with dimension subscripts given in a non-physical order. The following examples use the matrix declaration @array( float, 5, 7 ) m@, loaded with values incremented by $0.1$, when stepping across the length-7 finely-strided column dimension, and stepping across the length-5 coarsely-strided row dimension. @@ -870,5 +869,5 @@ \lstinput[aboveskip=0pt]{140-140}{hello-md.cfa} -However, function @print1d@ is asserting too much knowledge about its parameter @r@ for printing either a row slice or a column slice. +However, function @print1d_cstyle@ is asserting too much knowledge about its parameter @r@ for printing either a row slice or a column slice. Specifically, declaring the parameter @r@ with type @array@ means that @r@ is contiguous, which is unnecessarily restrictive. That is, @r@ need only be of a container type that offers a subscript operator (of type @ptrdiff_t@ $\rightarrow$ @float@) with managed length @N@. @@ -942,14 +941,18 @@ Proceeding from @x@ gives the numeric indices as coarse then fine, while proceeding from @x[all]@ gives them fine then coarse. These two starting expressions, which are the example's only multidimensional subexpressions -(those that received zero numeric indices so far), are illustrated with vertical steps where a \emph{first} numeric index would select. - -The figure's presentation offers an intuition answer to: What is an atomic element of @x[all]@? -From there, @x[all]@ itself is simply a two-dimensional array, in the strict C sense, of these building blocks. -An atom (like the bottommost value, @x[all][3][2]@), is the contained value (in the square box) -and a lie about its size (the left diagonal above it, growing upward). +(those that received zero numeric indices so far), are illustrated with vertical steps where a \emph{first} numeric index selects. + +The figure's presentation offers an intuitive answer to: What is an atomic element of @x[all]@? +\begin{enumerate}[leftmargin=*] +\item +@x[all]@ itself is simply a two-dimensional array, in the strict C sense, of these building blocks. +\item An array of these atoms (like the intermediate @x[all][3]@) is just a contiguous arrangement of them, done according to their size; call such an array a column. A column is almost ready to be arranged into a matrix; it is the \emph{contained value} of the next-level building block, but another lie about size is required. +\item +An atom (like the bottommost value, @x[all][3][2]@), is the contained value (in the square box) and a lie about its size (the left diagonal above it, growing upward). +\end{enumerate} At first, an atom needs to be arranged as if it is bigger, but now a column needs to be arranged as if it is smaller (the left diagonal above it, shrinking upward). These lying columns, arranged contiguously according to their size (as announced) form the matrix @x[all]@. @@ -1028,15 +1031,14 @@ At runtime, the \CFA array is exactly a C array. \CFA array subscripting is protected with runtime bound checks. -The array dependent-typing provides information to the C optimizer, allowing it remove many of the bound checks. +The array dependent-typing provides information to the C optimizer, allowing it to remove many of the bound checks. This section provides a demonstration of these effects. -The experiment compares the \CFA array system with the simple-safety system most typically exemplified by Java arrays (\VRef[Section]{JavaCompare}), but also reflected in the \CC pattern where restricted vector usage models a checked array (\VRef[Section]{CppCompare}). -The essential feature of this simple system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. -The experiment uses the \CC version to simplify access to generated assembly code. -While ``\CC'' labels a participant, it is really the simple-safety system (of @vector@ with @.at@) whose limitations are being explained, and not limitations of \CC optimization. - -As a control case, a simple loop (with no reused dimension sizes) is seen to get the same optimization treatment in both the \CFA and \CC versions. -Firstly, when the programmer treats the array's bound correctly (making the subscript ``obviously fine''), no dynamic bound check is observed in the program's optimized assembly code. -But when the bounds are adjusted, such that the subscript is possibly invalid, the bound check appears in the optimized assembly, ready to catch a mistake. +The experiment compares the \CFA array system with the simple-safety system most typically exemplified by Java arrays (\VRef[Section]{JavaCompare}), and reflected in \CC vector using member @.at@ for subscripting (\VRef[Section]{CppCompare}). +The essential feature is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. +Hence, it is the implicit \CFA checked subscripting and explicit \CC @vector@ @.at@ mechanisms being explained and not limitations of \CC optimization. + +As a control case, a simple loop receives the same optimization treatment in both the \CFA and \CC versions. +When the surrounding code makes it clear subscripting is always in bound, no dynamic bound check is observed in the program's optimized assembly code. +But when the environment is adjusted, such that the subscript is possibly invalid, the bound check appears in the optimized assembly, ready to catch a mistake. \VRef[Figure]{f:ovhd-ctl} gives a control-case example of summing values in an array, where each column shows the program in languages C (a,~d,~g), \CFA (b,~e,~h), and \CC (c,~f,~i). @@ -1099,5 +1101,5 @@ When dimension sizes get reused, \CFA has an advantage over \CC-vector at getting simply written programs well optimized. -The example case of \VRef[Figures]{f:ovhd-treat-src} and \VRef[]{f:ovhd-treat-asm} is a simple matrix multiplication over a row-major encoding. +\VRef[Figures]{f:ovhd-treat-src} shows a simple matrix multiplication over a row-major encoding. Simple means coding directly to the intuition of the mathematical definition without trying to optimize for memory layout. In the assembly code of \VRef[Figure]{f:ovhd-treat-asm}, the looping pattern of \VRef[Figure]{f:ovhd-ctl} (d, e, f), ``Skip ahead on zero; loop back for next,'' occurs with three nesting levels. @@ -1145,5 +1147,5 @@ Or more technically, guaranteeing @N@ as the basis for the imposed bound check \emph{of every row.} As well, the \CC type does not impose the mathematically familiar constraint of $(M \times P) (P \times N) \rightarrow (M \times N)$. -Even assuming away the first issue, \eg that in @lhs@, all minor/cell counts agree, the data format allows the @rhs@ major/row count to disagree. +Even assuming away the first issue, \eg that in @lhs@ all minor/cell counts agree, the data format allows the @rhs@ major/row count to disagree. Or, the possibility that the row count @res.size()@ disagrees with the row count @lhs.size()@ illustrates this bound-mistake type in isolation. The \CFA solution guards against this possibility by keeping length information separate from the array data, and therefore eligible for sharing. @@ -1380,8 +1382,8 @@ \begin{cfa} thread worker { int id; }; -void ?{}( worker & ) = void; // remove default constructor +void ?{}( worker & ) = void; $\C[2.5in]{// remove default constructor}$ void ?{}( worker &, int id ); -array( worker, 5 ) ws = @{}@; // rejected; but desire is for no initialization yet -for ( i; 5 ) (ws[i]){ @i@ }; // explicitly initialize each thread, giving id +array( worker, 5 ) ws = @{}@; $\C{// rejected; but desire is for no initialization yet}$ +for ( i; 5 ) (ws[i]){ @i@ }; $\C{// explicit (placement) initialization for each thread, giving id}\CRT$ \end{cfa} Note the use of the \CFA explicit constructor call, analogous to \CC's placement-@new@. @@ -1393,5 +1395,5 @@ Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions. -Another \CFA feature for providing C backwards compatibility, at first seem viable for initializing the array @ws@, though on closer inspection is not. +Another \CFA feature for providing C backwards compatibility, at first seems viable for initializing the array @ws@, though on closer inspection is not. C initialization without a constructor is specified with \lstinline|@=|, \eg \lstinline|array(worker, 5) ws @= {}| ignores all \CFA lifecycle management and uses C empty initialization. This option does achieve the desired semantics on the construction side. @@ -1424,5 +1426,5 @@ let fa: [f64; 5] = [1.2, fval, 5.6, 7.3, 9.1]; $\C{// immutable, individual initialization}$ \end{rust} -Initialization is required even if the array is subsequently initialized. +Initialization is required even if an array is subsequently initialized. Rust arrays are not VLAs, but the compile-time length can be queried using member @len()@. Arrays can be assigned and passed to parameters by value or reference, if and only if, the type and dimension match, meaning a different function is needed for each array size. @@ -1548,6 +1550,6 @@ \begin{figure} -\setlength{\tabcolsep}{15pt} -\begin{tabular}{ll@{}} +\centering +\begin{lrbox}{\myboxA} \begin{java} int m[][] = { // triangular matrix @@ -1579,5 +1581,7 @@ } \end{java} -& +\end{lrbox} + +\begin{lrbox}{\myboxB} \begin{cfa} int * m[5] = { // triangular matrix @@ -1609,6 +1613,14 @@ } \end{cfa} -\end{tabular} -\caption{Java (left) \vs C (right) Triangular Matrix} +\end{lrbox} + +\subfloat[Java]{\label{f:JavaTriangularMatrix}\usebox\myboxA} +\hspace{6pt} +\vrule +\hspace{6pt} +\subfloat[C]{\label{f:CTriangularMatrix}\usebox\myboxB} +\hspace{6pt} + +\caption{Triangular Matrix} \label{f:JavaVsCTriangularMatrix} \end{figure} @@ -1639,8 +1651,8 @@ But none makes an allocation with a dynamically given fixed size less awkward than the vector arrangement just described. -\CC~26 adds @std::inplace_vector@, which provides an interesting vector--array hybrid,\footnote{ - Like a vector, it lets a user construct elements in a loop, rather than imposing uniform construction. - Yet it preserves \lstinline{std::array}'s ability to be entirely stack-allocated, by avoiding an auxiliary elements' allocation. -} but does not change the fundamental limit of \lstinline{std::array}, that the length, being a template parameter, must be a static value. +\CC~26 adds @std::inplace_vector@ providing an interesting vector--array hybrid. +Like a vector, it lets a user construct elements in a loop, rather than imposing uniform construction. +Yet it preserves \lstinline{std::array}'s ability to be entirely stack-allocated, by avoiding an auxiliary elements' allocation. +However, it preserves the fundamental limit of \lstinline{std::array}, that the length, being a template parameter, must be a static value. \CC~20's @std::span@ is a view that unifies true arrays, vectors, static sizes and dynamic sizes, under a common API that adds bounds checking. @@ -1772,4 +1784,5 @@ \section{Future Work} +\label{f:FutureWork} % \subsection{Array Syntax}