Index: doc/theses/mike_brooks_MMath/array.tex =================================================================== --- doc/theses/mike_brooks_MMath/array.tex (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/array.tex (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -6,15 +6,15 @@ \begin{lstlisting} - array(float, 99) x; // x contains 99 floats - - void f( array(float, 42) & a ) {} - f(x); // statically rejected: types are different - - forall( T, [N] ) - void g( array(T, N) & a, int i ) { - T elem = a[i]; // dynamically checked: requires 0 <= i < N - } - g(x, 0); // T is float, N is 99, succeeds - g(x, 1000); // T is float, N is 99, dynamic check fails +array(float, 99) x; // x contains 99 floats + +void f( array(float, 42) & a ) {} +f(x); // statically rejected: types are different + +forall( T, [N] ) +void g( array(T, N) & a, int i ) { + T elem = a[i]; // dynamically checked: requires 0 <= i < N +} +g(x, 0); // T is float, N is 99, succeeds +g(x, 1000); // T is float, N is 99, dynamic check fails \end{lstlisting} @@ -31,9 +31,9 @@ \begin{lstlisting} - forall( [N] ) - void declDemo() { - float a1[N]; // built-in type ("C array") - array(float, N) a2; // type from library - } +forall( [N] ) +void declDemo() { + float a1[N]; // built-in type ("C array") + array(float, N) a2; // type from library +} \end{lstlisting} @@ -54,35 +54,42 @@ My contributions are \begin{itemize} - \item a type system enhancement that lets polymorphic functions and generic types be parameterized by a numeric value: @forall( [N] )@ - \item [TODO: general parking...] - \item identify specific abilities brought by @array@ - \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 +\item a type system enhancement that lets polymorphic functions and generic types be parameterized by a numeric value: @forall( [N] )@ +\item TODO: general parking... +\item identify specific abilities brought by @array@ +\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{itemize} - \section{Definitions and design considerations} + \subsection{Dependent typing} - - \section{Features Added} The present work adds a type @array@ to the \CFA standard library~\cite{Cforall}. -This array's length is statically managed and dynamically valued. This static management achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference). +This array's length is statically managed and dynamically valued. +This static management achieves argument safety and suggests a path to subscript safety as future work (TODO: cross reference). 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 management 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. +The core of the new array management 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=10, lastline=17]{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. Preexisting \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. +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. +Preexisting \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. \VRef[Figure]{f:fHarness} shows the harness to use the @f@ function illustrating how dynamic values are fed into the system. -Here, the @a@ array is loaded with decreasing values, and the @b@ array with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later. The program main is run with two different inputs of sequence length. +Here, the @a@ array is loaded with decreasing values, and the @b@ array with amounts off by a constant, giving relative differences within tolerance at first and out of tolerance later. +The program main is run with two different inputs of sequence length. \begin{figure} @@ -92,9 +99,11 @@ \end{figure} -The loops in the program main 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 loops in the program main 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 @n@ adapting a variable into a type-system managed length (at @main@'s declarations of @a@, @b@, and @result@), @N@ adapting in the opposite direction (at @f@'s loop bound), and a pass-thru use of a managed length (at @f@'s declaration of @ret@). -The @forall( ...[N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function @b@. The present form is chosen to parallel the existing @forall@ forms: +The @forall( ...[N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and in the function @b@. +The present form is chosen to parallel the existing @forall@ forms: \begin{cfa} forall( @[N]@ ) ... // array kind @@ -115,10 +124,33 @@ @array( thing, N0, N1, ... )@ -- a type wrapping $\prod_i N_i$ adjacent occurrences of @thing@ objects \end{itemize} -Unsigned integers have a special status in this type system. Unlike how C++ allows @template< size_t N, char * msg, typename T >...@ declarations, \CFA 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=60, lastline=65]{hello-array.cfa} +Unsigned integers have a special status in this type system. +Unlike how C++ allows +\begin{lstlisting}[language=c++] +template< size_t N, char * msg, typename T >... // declarations +\end{lstlisting} +\CFA 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. +\begin{cfa} +forall( [M], [N] ) +void bad( array(float, M) &a, array(float, N) &b ) { + f( a, a ); // ok + f( b, b ); // ok + f( a, b ); // error +} +\end{cfa} +%\lstinputlisting[language=CFA, firstline=60, lastline=65]{hello-array.cfa} As is common practice in C, the programmer is free to cast, to assert knowledge not shared with the type system. -\lstinputlisting[language=CFA, firstline=70, lastline=75]{hello-array.cfa} +\begin{cfa} +forall( [M], [N] ) +void bad_fixed( array(float, M) & a, array(float, N) & b ) { + if ( M == N ) { + f( a, (array(float, M) &)b ); // cast b to matching type + } +} +\end{cfa} +%\lstinputlisting[language=CFA, firstline=70, lastline=75]{hello-array.cfa} Argument safety and the associated implicit communication of array length work with \CFA's generic types too. @@ -126,9 +158,11 @@ 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=10, lastline=16]{hello-accordion.cfa} -This structure's layout has the starting offset of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic parameters. For a function that operates on a @request@ structure, the type system handles this variation transparently. +This structure's layout has the starting offset of @cost_contribs@ varying in @Nclients@, and the offset of @total_cost@ varying in both generic parameters. +For a function that operates on a @request@ structure, the type system handles this variation transparently. \lstinputlisting[language=CFA, firstline=40, lastline=47]{hello-accordion.cfa} In the example, different runs of the program result in different offset values being used. \lstinputlisting[language=CFA, firstline=60, lastline=76]{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.'' +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.'' @@ -136,29 +170,44 @@ \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 multidimensional 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. +The new \CFA standard library @array@ datatype supports multidimensional uses more richly than the C array. +The new array's multidimensional 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 coarsely-strided dimension shown on rows. -\lstinputlisting[language=CFA, firstline=120, lastline=126]{hello-md.cfa} +%\lstinputlisting[language=CFA, firstline=120, lastline=126]{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 coarsely strided dimensions, leaving a result that expects to be be subscripted by the more finely strided dimensions. +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 coarsely 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[aboveskip=0pt, 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 managed 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: +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 managed 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[aboveskip=0pt, 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. +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: +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) +@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} @@ -168,8 +217,8 @@ \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 +@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} @@ -177,50 +226,68 @@ \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 +@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: +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 +@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, 5, 7 )}. The horizontal dimension represents memory addresses while vertical layout is conceptual.} - \label{fig:subscr-all} +\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, 5, 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 indices 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 proper 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 vertical 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. Subscripting by @all@ rearranges the order of masquerading-as types to achieve, in general, 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. +\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 indices 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 proper 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 vertical 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. +Subscripting by @all@ rearranges the order of masquerading-as types to achieve, in general, 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[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 instantiation of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ expansion, 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@ instantiations, intact, to new positions. Expressed as an operation on types, this rotation is: + 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[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 instantiation of the @arpk@ generic is given by the @array(E_base, N0, N1, ...)@ expansion, 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@ instantiations, 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 ) \\ @@ -232,13 +299,20 @@ \section{Bound checks, added and removed} -\CFA array subscripting is protected with runtime bound checks. Having dependent typing causes the optimizer to remove more of these bound checks than it would without them. This section provides a demonstration of the effect. - -The experiment compares the \CFA array system with the padded-room system [TODO:xref] most typically exemplified by Java arrays, but also reflected in the C++ pattern where restricted vector usage models a checked array. The essential feature of this padded-room system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. The experiment compares with the C++ version to keep access to generated assembly code simple. - -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 C++ versions. 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 an occurrence the mistake. +\CFA array subscripting is protected with runtime bound checks. +Having dependent typing causes the optimizer to remove more of these bound checks than it would without them. +This section provides a demonstration of the effect. + +The experiment compares the \CFA array system with the padded-room system [TODO:xref] most typically exemplified by Java arrays, but also reflected in the C++ pattern where restricted vector usage models a checked array. +The essential feature of this padded-room system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based. +The experiment compares with the C++ version to keep access to generated assembly code simple. + +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 C++ versions. +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 an occurrence the mistake. TODO: paste source and assembly codes -Incorporating reuse among dimension sizes is seen to give \CFA an advantage at being optimized. The case is naive matrix multiplication over a row-major encoding. +Incorporating reuse among dimension sizes is seen to give \CFA an advantage at being optimized. +The case is naive matrix multiplication over a row-major encoding. TODO: paste source codes @@ -250,28 +324,43 @@ \section{Comparison with other arrays} -\CFA's array is the first lightweight application of dependently-typed bound tracking to an extension of C. Other extensions of C that apply dependently-typed bound tracking are heavyweight, in that the bound tracking is part of a linearly typed ownership system that further helps guarantee statically the validity of every pointer deference. These systems, therefore, ask the programmer to convince the type checker that every pointer dereference is valid. \CFA imposes the lighter-weight obligation, with the more limited guarantee, that initially-declared bounds are respected thereafter. - -\CFA's array is also the first extension of C to use its tracked bounds to generate the pointer arithmetic implied by advanced allocation patterns. Other bound-tracked extensions of C either forbid certain C patterns entirely, or address the problem of \emph{verifying} that the user's provided pointer arithmetic is self-consistent. The \CFA array, applied to accordion structures [TOD: cross-reference] \emph{implies} the necessary pointer arithmetic, generated automatically, and not appearing at all in a user's program. +\CFA's array is the first lightweight application of dependently-typed bound tracking to an extension of C. +Other extensions of C that apply dependently-typed bound tracking are heavyweight, in that the bound tracking is part of a linearly typed ownership system that further helps guarantee statically the validity of every pointer deference. +These systems, therefore, ask the programmer to convince the type checker that every pointer dereference is valid. +\CFA imposes the lighter-weight obligation, with the more limited guarantee, that initially-declared bounds are respected thereafter. + +\CFA's array is also the first extension of C to use its tracked bounds to generate the pointer arithmetic implied by advanced allocation patterns. +Other bound-tracked extensions of C either forbid certain C patterns entirely, or address the problem of \emph{verifying} that the user's provided pointer arithmetic is self-consistent. +The \CFA array, applied to accordion structures [TOD: cross-reference] \emph{implies} the necessary pointer arithmetic, generated automatically, and not appearing at all in a user's program. \subsection{Safety in a padded room} -Java's array [TODO:cite] is a straightforward example of assuring safety against undefined behaviour, at a cost of expressiveness for more applied properties. Consider the array parameter declarations in: +Java's array [TODO:cite] is a straightforward example of assuring safety against undefined behaviour, at a cost of expressiveness for more applied properties. +Consider the array parameter declarations in: \begin{tabular}{rl} - C & @void f( size_t n, size_t m, float a[n][m] );@ \\ - Java & @void f( float[][] a );@ +C & @void f( size_t n, size_t m, float a[n][m] );@ \\ +Java & @void f( float[][] a );@ \end{tabular} -Java's safety against undefined behaviour assures the callee that, if @a@ is non-null, then @a.length@ is a valid access (say, evaluating to the number $\ell$) and if @i@ is in $[0, \ell)$ then @a[i]@ is a valid access. If a value of @i@ outside this range is used, a runtime error is guaranteed. In these respects, C offers no guarantees at all. Notably, the suggestion that @n@ is the intended size of the first dimension of @a@ is documentation only. Indeed, many might prefer the technically equivalent declarations @float a[][m]@ or @float (*a)[m]@ as emphasizing the ``no guarantees'' nature of an infrequently used language feature, over using the opportunity to explain a programmer intention. Moreover, even if @a[0][0]@ is valid for the purpose intended, C's basic infamous feature is the possibility of an @i@, such that @a[i][0]@ is not valid for the same purpose, and yet, its evaluation does not produce an error. +Java's safety against undefined behaviour assures the callee that, if @a@ is non-null, then @a.length@ is a valid access (say, evaluating to the number $\ell$) and if @i@ is in $[0, \ell)$ then @a[i]@ is a valid access. +If a value of @i@ outside this range is used, a runtime error is guaranteed. +In these respects, C offers no guarantees at all. +Notably, the suggestion that @n@ is the intended size of the first dimension of @a@ is documentation only. +Indeed, many might prefer the technically equivalent declarations @float a[][m]@ or @float (*a)[m]@ as emphasizing the ``no guarantees'' nature of an infrequently used language feature, over using the opportunity to explain a programmer intention. +Moreover, even if @a[0][0]@ is valid for the purpose intended, C's basic infamous feature is the possibility of an @i@, such that @a[i][0]@ is not valid for the same purpose, and yet, its evaluation does not produce an error. Java's lack of expressiveness for more applied properties means these outcomes are possible: \begin{itemize} - \item @a[0][17]@ and @a[2][17]@ are valid accesses, yet @a[1][17]@ is a runtime error, because @a[1]@ is a null pointer - \item the same observation, now because @a[1]@ refers to an array of length 5 - \item execution times vary, because the @float@ values within @a@ are sometimes stored nearly contiguously, and other times, not at all +\item @a[0][17]@ and @a[2][17]@ are valid accesses, yet @a[1][17]@ is a runtime error, because @a[1]@ is a null pointer +\item the same observation, now because @a[1]@ refers to an array of length 5 +\item execution times vary, because the @float@ values within @a@ are sometimes stored nearly contiguously, and other times, not at all \end{itemize} C's array has none of these limitations, nor do any of the ``array language'' comparators discussed in this section. -This Java level of safety and expressiveness is also exemplified in the C family, with the commonly given advice [TODO:cite example], for C++ programmers to use @std::vector@ in place of the C++ language's array, which is essentially the C array. The advice is that, while a vector is also more powerful (and quirky) than an array, its capabilities include options to preallocate with an upfront size, to use an available bound-checked accessor (@a.at(i)@ in place of @a[i]@), to avoid using @push_back@, and to use a vector of vectors. Used with these restrictions, out-of-bound accesses are stopped, and in-bound accesses never exercise the vector's ability to grow, which is to say, they never make the program slow to reallocate and copy, and they never invalidate the program's other references to the contained values. Allowing this scheme the same referential integrity assumption that \CFA enjoys [TODO:xref], this scheme matches Java's safety and expressiveness exactly. [TODO: decide about going deeper; some of the Java expressiveness concerns have mitigations, up to even more tradeoffs.] +This Java level of safety and expressiveness is also exemplified in the C family, with the commonly given advice [TODO:cite example], for C++ programmers to use @std::vector@ in place of the C++ language's array, which is essentially the C array. +The advice is that, while a vector is also more powerful (and quirky) than an array, its capabilities include options to preallocate with an upfront size, to use an available bound-checked accessor (@a.at(i)@ in place of @a[i]@), to avoid using @push_back@, and to use a vector of vectors. +Used with these restrictions, out-of-bound accesses are stopped, and in-bound accesses never exercise the vector's ability to grow, which is to say, they never make the program slow to reallocate and copy, and they never invalidate the program's other references to the contained values. +Allowing this scheme the same referential integrity assumption that \CFA enjoys [TODO:xref], this scheme matches Java's safety and expressiveness exactly. +[TODO: decide about going deeper; some of the Java expressiveness concerns have mitigations, up to even more tradeoffs.] \subsection{Levels of dependently typed arrays} @@ -279,13 +368,21 @@ The \CFA array and the field of ``array language'' comparators all leverage dependent types to improve on the expressiveness over C and Java, accommodating examples such as: \begin{itemize} - \item a \emph{zip}-style operation that consumes two arrays of equal length - \item a \emph{map}-style operation whose produced length matches the consumed length - \item a formulation of matrix multiplication, where the two operands must agree on a middle dimension, and where the result dimensions match the operands' outer dimensions +\item a \emph{zip}-style operation that consumes two arrays of equal length +\item a \emph{map}-style operation whose produced length matches the consumed length +\item a formulation of matrix multiplication, where the two operands must agree on a middle dimension, and where the result dimensions match the operands' outer dimensions \end{itemize} -Across this field, this expressiveness is not just an available place to document such assumption, but these requirements are strongly guaranteed by default, with varying levels of statically/dynamically checked and ability to opt out. Along the way, the \CFA array also closes the safety gap (with respect to bounds) that Java has over C. - -Dependent type systems, considered for the purpose of bound-tracking, can be full-strength or restricted. In a full-strength dependent type system, a type can encode an arbitrarily complex predicate, with bound-tracking being an easy example. The tradeoff of this expressiveness is complexity in the checker, even typically, a potential for its nontermination. In a restricted dependent type system (purposed for bound tracking), the goal is to check helpful properties, while keeping the checker well-behaved; the other restricted checkers surveyed here, including \CFA's, always terminate. [TODO: clarify how even Idris type checking terminates] - -Idris is a current, general-purpose dependently typed programming language. Length checking is a common benchmark for full dependent type systems. Here, the capability being considered is to track lengths that adjust during the execution of a program, such as when an \emph{add} operation produces a collection one element longer than the one on which it started. [TODO: finish explaining what Data.Vect is and then the essence of the comparison] +Across this field, this expressiveness is not just an available place to document such assumption, but these requirements are strongly guaranteed by default, with varying levels of statically/dynamically checked and ability to opt out. +Along the way, the \CFA array also closes the safety gap (with respect to bounds) that Java has over C. + +Dependent type systems, considered for the purpose of bound-tracking, can be full-strength or restricted. +In a full-strength dependent type system, a type can encode an arbitrarily complex predicate, with bound-tracking being an easy example. +The tradeoff of this expressiveness is complexity in the checker, even typically, a potential for its nontermination. +In a restricted dependent type system (purposed for bound tracking), the goal is to check helpful properties, while keeping the checker well-behaved; the other restricted checkers surveyed here, including \CFA's, always terminate. +[TODO: clarify how even Idris type checking terminates] + +Idris is a current, general-purpose dependently typed programming language. +Length checking is a common benchmark for full dependent type systems. +Here, the capability being considered is to track lengths that adjust during the execution of a program, such as when an \emph{add} operation produces a collection one element longer than the one on which it started. +[TODO: finish explaining what Data.Vect is and then the essence of the comparison] POINTS: @@ -293,15 +390,24 @@ it can also do these other cool checks, but watch how I can mess with its conservativeness and termination -Two current, state-of-the-art array languages, Dex\cite{arr:dex:long} and Futhark\cite{arr:futhark:tytheory}, offer offer novel contributions concerning similar, restricted dependent types for tracking array length. Unlike \CFA, both are garbage-collected functional languages. Because they are garbage-collected, referential integrity is built-in, meaning that the heavyweight analysis, that \CFA aims to avoid, is unnecessary. So, like \CFA, the checking in question is a lightweight bounds-only analysis. Like \CFA, their checks that are conservatively limited by forbidding arithmetic in the depended-upon expression. - - - -The Futhark work discusses the working language's connection to a lambda calculus, with typing rules and a safety theorem proven in reference to an operational semantics. There is a particular emphasis on an existential type, enabling callee-determined return shapes. +Two current, state-of-the-art array languages, Dex\cite{arr:dex:long} and Futhark\cite{arr:futhark:tytheory}, offer offer novel contributions concerning similar, restricted dependent types for tracking array length. +Unlike \CFA, both are garbage-collected functional languages. +Because they are garbage-collected, referential integrity is built-in, meaning that the heavyweight analysis, that \CFA aims to avoid, is unnecessary. +So, like \CFA, the checking in question is a lightweight bounds-only analysis. +Like \CFA, their checks that are conservatively limited by forbidding arithmetic in the depended-upon expression. + + + +The Futhark work discusses the working language's connection to a lambda calculus, with typing rules and a safety theorem proven in reference to an operational semantics. +There is a particular emphasis on an existential type, enabling callee-determined return shapes. + Dex uses a novel conception of size, embedding its quantitative information completely into an ordinary type. -Futhark and full-strength dependently typed languages treat array sizes are ordinary values. Futhark restricts these expressions syntactically to variables and constants, while a full-strength dependent system does not. - -CFA's hybrid presentation, @forall( [N] )@, has @N@ belonging to the type system, yet has no instances. Belonging to the type system means it is inferred at a call site and communicated implicitly, like in Dex and unlike in Futhark. Having no instances means there is no type for a variable @i@ that constrains @i@ to be in the range for @N@, unlike Dex, [TODO: verify], but like Futhark. +Futhark and full-strength dependently typed languages treat array sizes are ordinary values. +Futhark restricts these expressions syntactically to variables and constants, while a full-strength dependent system does not. + +CFA's hybrid presentation, @forall( [N] )@, has @N@ belonging to the type system, yet has no instances. +Belonging to the type system means it is inferred at a call site and communicated implicitly, like in Dex and unlike in Futhark. +Having no instances means there is no type for a variable @i@ that constrains @i@ to be in the range for @N@, unlike Dex, [TODO: verify], but like Futhark. \subsection{Static safety in C extensions} @@ -318,32 +424,36 @@ \subsection{With described enumerations} -A project in \CFA's current portfolio will improve enumerations. In the incumbent state, \CFA has C's enumerations, unmodified. I will not discuss the core of this project, which has a tall mission already, to improve type safety, maintain appropriate C compatibility and offer more flexibility about storage use. It also has a candidate stretch goal, to adapt \CFA's @forall@ generic system to communicate generalized enumerations: -\begin{lstlisting} - forall( T | is_enum(T) ) - void show_in_context( T val ) { - for( T i ) { - string decorator = ""; - if ( i == val-1 ) decorator = "< ready"; - if ( i == val ) decorator = "< go" ; - sout | i | decorator; - } - } - enum weekday { mon, tue, wed = 500, thu, fri }; - show_in_context( wed ); +A project in \CFA's current portfolio will improve enumerations. +In the incumbent state, \CFA has C's enumerations, unmodified. +I will not discuss the core of this project, which has a tall mission already, to improve type safety, maintain appropriate C compatibility and offer more flexibility about storage use. +It also has a candidate stretch goal, to adapt \CFA's @forall@ generic system to communicate generalized enumerations: +\begin{lstlisting} +forall( T | is_enum(T) ) +void show_in_context( T val ) { + for( T i ) { + string decorator = ""; + if ( i == val-1 ) decorator = "< ready"; + if ( i == val ) decorator = "< go" ; + sout | i | decorator; + } +} +enum weekday { mon, tue, wed = 500, thu, fri }; +show_in_context( wed ); \end{lstlisting} with output \begin{lstlisting} - mon - tue < ready - wed < go - thu - fri -\end{lstlisting} -The details in this presentation aren't meant to be taken too precisely as suggestions for how it should look in \CFA. But the example shows these abilities: +mon +tue < ready +wed < go +thu +fri +\end{lstlisting} +The details in this presentation aren't meant to be taken too precisely as suggestions for how it should look in \CFA. +But the example shows these abilities: \begin{itemize} - \item a built-in way (the @is_enum@ trait) for a generic routine to require enumeration-like information about its instantiating type - \item an implicit implementation of the trait whenever a user-written enum occurs (@weekday@'s declaration implies @is_enum@) - \item a total order over the enumeration constants, with predecessor/successor (@val-1@) available, and valid across gaps in values (@tue == 1 && wed == 500 && tue == wed - 1@) - \item a provision for looping (the @for@ form used) over the values of the type. +\item a built-in way (the @is_enum@ trait) for a generic routine to require enumeration-like information about its instantiating type +\item an implicit implementation of the trait whenever a user-written enum occurs (@weekday@'s declaration implies @is_enum@) +\item a total order over the enumeration constants, with predecessor/successor (@val-1@) available, and valid across gaps in values (@tue == 1 && wed == 500 && tue == wed - 1@) +\item a provision for looping (the @for@ form used) over the values of the type. \end{itemize} @@ -352,34 +462,46 @@ [TODO: introduce Ada in the comparators] -In Ada and Dex, an array is conceived as a function whose domain must satisfy only certain structural assumptions, while in C, C++, Java, Futhark and \CFA today, the domain is a prefix of the natural numbers. The generality has obvious aesthetic benefits for programmers working on scheduling resources to weekdays, and for programmers who prefer to count from an initial number of their own choosing. - -This change of perspective also lets us remove ubiquitous dynamic bound checks. [TODO: xref] discusses how automatically inserted bound checks can often be optimized away. But this approach is unsatisfying to a programmer who believes she has written code in which dynamic checks are unnecessary, but now seeks confirmation. To remove the ubiquitous dynamic checking is to say that an ordinary subscript operation is only valid when it can be statically verified to be in-bound (and so the ordinary subscript is not dynamically checked), and an explicit dynamic check is available when the static criterion is impractical to meet. +In Ada and Dex, an array is conceived as a function whose domain must satisfy only certain structural assumptions, while in C, C++, Java, Futhark and \CFA today, the domain is a prefix of the natural numbers. +The generality has obvious aesthetic benefits for programmers working on scheduling resources to weekdays, and for programmers who prefer to count from an initial number of their own choosing. + +This change of perspective also lets us remove ubiquitous dynamic bound checks. +[TODO: xref] discusses how automatically inserted bound checks can often be optimized away. +But this approach is unsatisfying to a programmer who believes she has written code in which dynamic checks are unnecessary, but now seeks confirmation. +To remove the ubiquitous dynamic checking is to say that an ordinary subscript operation is only valid when it can be statically verified to be in-bound (and so the ordinary subscript is not dynamically checked), and an explicit dynamic check is available when the static criterion is impractical to meet. [TODO, fix confusion: Idris has this arrangement of checks, but still the natural numbers as the domain.] -The structural assumptions required for the domain of an array in Dex are given by the trait (there, ``interface'') @Ix@, which says that the parameter @n@ is a type (which could take an argument like @weekday@) that provides two-way conversion with the integers and a report on the number of values. Dex's @Ix@ is analogous the @is_enum@ proposed for \CFA above. +The structural assumptions required for the domain of an array in Dex are given by the trait (there, ``interface'') @Ix@, which says that the parameter @n@ is a type (which could take an argument like @weekday@) that provides two-way conversion with the integers and a report on the number of values. +Dex's @Ix@ is analogous the @is_enum@ proposed for \CFA above. \begin{lstlisting} interface Ix n - get_size n : Unit -> Int - ordinal : n -> Int - unsafe_from_ordinal n : Int -> n -\end{lstlisting} - -Dex uses this foundation of a trait (as an array type's domain) to achieve polymorphism over shapes. This flavour of polymorphism lets a function be generic over how many (and the order of) dimensions a caller uses when interacting with arrays communicated with this function. Dex's example is a routine that calculates pointwise differences between two samples. Done with shape polymorphism, one function body is equally applicable to a pair of single-dimensional audio clips (giving a single-dimensional result) and a pair of two-dimensional photographs (giving a two-dimensional result). In both cases, but with respectively dimensioned interpretations of ``size,'' this function requires the argument sizes to match, and it produces a result of the that size. - -The polymorphism plays out with the pointwise-difference routine advertising a single-dimensional interface whose domain type is generic. In the audio instantiation, the duration-of-clip type argument is used for the domain. In the photograph instantiation, it's the tuple-type of $ \langle \mathrm{img\_wd}, \mathrm{img\_ht} \rangle $. This use of a tuple-as-index is made possible by the built-in rule for implementing @Ix@ on a pair, given @Ix@ implementations for its elements + get_size n : Unit -> Int + ordinal : n -> Int + unsafe_from_ordinal n : Int -> n +\end{lstlisting} + +Dex uses this foundation of a trait (as an array type's domain) to achieve polymorphism over shapes. +This flavour of polymorphism lets a function be generic over how many (and the order of) dimensions a caller uses when interacting with arrays communicated with this function. +Dex's example is a routine that calculates pointwise differences between two samples. +Done with shape polymorphism, one function body is equally applicable to a pair of single-dimensional audio clips (giving a single-dimensional result) and a pair of two-dimensional photographs (giving a two-dimensional result). +In both cases, but with respectively dimensioned interpretations of ``size,'' this function requires the argument sizes to match, and it produces a result of the that size. + +The polymorphism plays out with the pointwise-difference routine advertising a single-dimensional interface whose domain type is generic. +In the audio instantiation, the duration-of-clip type argument is used for the domain. +In the photograph instantiation, it's the tuple-type of $ \langle \mathrm{img\_wd}, \mathrm{img\_ht} \rangle $. +This use of a tuple-as-index is made possible by the built-in rule for implementing @Ix@ on a pair, given @Ix@ implementations for its elements \begin{lstlisting} instance {a b} [Ix a, Ix b] Ix (a & b) - get_size = \(). size a * size b - ordinal = \(i, j). (ordinal i * size b) + ordinal j - unsafe_from_ordinal = \o. - bs = size b - (unsafe_from_ordinal a (idiv o bs), unsafe_from_ordinal b (rem o bs)) + get_size = \(). size a * size b + ordinal = \(i, j). (ordinal i * size b) + ordinal j + unsafe_from_ordinal = \o. +bs = size b +(unsafe_from_ordinal a (idiv o bs), unsafe_from_ordinal b (rem o bs)) \end{lstlisting} and by a user-provided adapter expression at the call site that shows how to indexing with a tuple is backed by indexing each dimension at a time \begin{lstlisting} - img_trans :: (img_wd,img_ht)=>Real - img_trans.(i,j) = img.i.j - result = pairwise img_trans +img_trans :: (img_wd,img_ht)=>Real +img_trans.(i,j) = img.i.j +result = pairwise img_trans \end{lstlisting} [TODO: cite as simplification of example from https://openreview.net/pdf?id=rJxd7vsWPS section 4] Index: doc/theses/mike_brooks_MMath/background.tex =================================================================== --- doc/theses/mike_brooks_MMath/background.tex (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/background.tex (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -21,14 +21,14 @@ 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 + \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} +\begin{cfa} $ gcc --version gcc (Ubuntu 9.4.0-1ubuntu1~20.04.1) 9.4.0 -\end{lstlisting} +\end{cfa} running on Architecture @x86_64@, with the same environment targeted. @@ -39,6 +39,32 @@ \subsection{C reports many ill-typed expressions as warnings} -TODO: typeset -\lstinputlisting[language=C, firstline=13, lastline=56]{bkgd-c-tyerr.c} +These attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed. +\lstinput{12-15}{bkgd-c-tyerr.c} +with warnings: +\begin{cfa} +warning: assignment to 'float *' from incompatible pointer type 'void (*)(void)' +warning: assignment to 'void (*)(void)' from incompatible pointer type 'float *' +\end{cfa} +Similarly, +\lstinput{17-19}{bkgd-c-tyerr.c} +with warning: +\begin{cfa} +warning: passing argument 1 of 'f' from incompatible pointer type +note: expected 'void (*)(void)' but argument is of type 'float *' +\end{cfa} +with a segmentation fault at runtime. + +That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@. +Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition. + +A "tractable syntactic method for proving the absence of certain program behaviours by classifying phrases according to the kinds of values they compute"*1 rejected the program. +The behaviour (whose absence is unprovable) is neither minor nor unlikely. +The rejection shows that the program is ill-typed. + +Yet, the rejection presents as a GCC warning. + +In the discussion following, ``ill-typed'' means giving a nonzero @gcc -Werror@ exit condition with a message that discusses typing. + +*1 TAPL-pg1 definition of a type system @@ -47,13 +73,94 @@ \subsection{C has an array type (!)} -TODO: typeset -\lstinputlisting[language=C, firstline=35, lastline=116]{bkgd-carray-arrty.c} +When a programmer works with an array, C semantics provide access to a type that is different in every way from ``pointer to its first element.'' +Its qualities become apparent by inspecting the 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. +Assuming a target platform keeps things concrete: +\lstinput{35-36}{bkgd-carray-arrty.c} +Consider the sizes of expressions derived from @a@, modified by adding ``pointer to'' and ``first element'' (and including unnecessary parentheses to avoid confusion about precedence). +\lstinput{37-40}{bkgd-carray-arrty.c} +That @a@ takes up 40 bytes is common reasoning for C programmers. +Set aside for a moment the claim that this first assertion is giving information about a type. +For now, note that an array and a pointer to its first element are, sometimes, different things. + +The idea that there is such a thing as a pointer to an array may be surprising. +It is not the same thing as a pointer to the first element: +\lstinput{42-45}{bkgd-carray-arrty.c} +The first gets +\begin{cfa} +warning: assignment to `float (*)[10]' from incompatible pointer type `float *' +\end{cfa} +and the second gets the opposite. + +We now refute a concern that @sizeof(a)@ is reporting on special knowledge from @a@ being an local variable, +say that it is informing about an allocation, rather than simply a type. + +First, recognizing that @sizeof@ has two forms, one operating on an expression, the other on a type, we observe that the original answers are unaffected by using the type-parameterized form: +\lstinput{46-50}{bkgd-carray-arrty.c} +Finally, the same sizing is reported when there is no allocation at all, and we launch the analysis instead from the pointer-to-array type. +\lstinput{51-57}{bkgd-carray-arrty.c} +So, in spite of considerable programmer success enabled by an understanding that an array just a pointer to its first element (revisited TODO pointer decay), this understanding is simplistic. + +A shortened form for declaring local variables exists, provided that length information is given in the initializer: +\lstinput{59-63}{bkgd-carray-arrty.c} +In these declarations, the resulting types are both arrays, but their lengths are inferred. + +\begin{tabular}{lllllll} +@float x;@ & $\rightarrow$ & (base element) & @float@ & @float x;@ & @[ float ]@ & @[ float ]@ \\ +@float * x;@ & $\rightarrow$ & pointer & @float *@ & @float * x;@ & @[ * float ]@ & @[ * float ]@ \\ +@float x[10];@ & $\rightarrow$ & array & @float[10]@ & @float x[10];@ & @[ [10] float ]@ & @[ array(float, 10) ]@ \\ +@float *x[10];@ & $\rightarrow$ & array of pointers & @(float*)[10]@ & @float *x[10];@ & @[ [10] * float ]@ & @[ array(*float, 10) ]@ \\ +@float (*x)[10];@ & $\rightarrow$ & pointer to array & @float(*)[10]@ & @float (*x)[10];@ & @[ * [10] float ]@ & @[ * array(float, 10) ]@ \\ +@float *(*x5)[10];@ & $\rightarrow$ & pointer to array & @(float*)(*)[10]@ & @float *(*x)[10];@ & @[ * [10] * float ]@ & @[ * array(*float, 10) ]@ +\end{tabular} +\begin{cfa} + x5 = (float*(*)[10]) x4; +// x5 = (float(*)[10]) x4; // wrong target type; meta test suggesting above cast uses correct type + + // [here] + // const + + // [later] + // static + // star as dimension + // under pointer decay: int p1[const 3] being int const *p1 + + const float * y1; + float const * y2; + float * const y3; + + y1 = 0; + y2 = 0; + // y3 = 0; // bad + + // *y1 = 3.14; // bad + // *y2 = 3.14; // bad + *y3 = 3.14; + + const float z1 = 1.414; + float const z2 = 1.414; + + // z1 = 3.14; // bad + // z2 = 3.14; // bad + + +} + +#define T float +void stx2() { const T x[10]; +// x[5] = 3.14; // bad + } +void stx3() { T const x[10]; +// x[5] = 3.14; // bad + } +\end{cfa} 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]@. + \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} @@ -75,7 +182,7 @@ 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} +\begin{cfa} [ * [10] T ] x; -\end{lstlisting} +\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. @@ -83,108 +190,118 @@ \textbf{Unfortunate Syntactic Reference} -\noindent +\begin{figure} +\centering +\setlength{\tabcolsep}{3pt} \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 + & 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 \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 \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 \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} +\caption{Figure} +\end{figure} \subsection{Arrays decay and pointers diffract} -TODO: typeset -\lstinputlisting[language=C, firstline=4, lastline=26]{bkgd-carray-decay.c} - +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 @a@, 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 +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} @@ -206,8 +323,8 @@ 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} +\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. @@ -229,10 +346,10 @@ 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} +\lstinput{12-16}{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} +\lstinput{18-21}{bkgd-carray-decay.c} This fragment gives no warnings. @@ -240,5 +357,5 @@ 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} +\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@, @@ -252,13 +369,12 @@ 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 + \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} - +\lstinput{32-42}{bkgd-carray-decay.c} \noindent @@ -268,39 +384,41 @@ (Parameter declaration; ``no writing'' refers to the callee's ability) -\noindent +\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 - $\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 + & 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{Figure} +\end{figure} @@ -309,30 +427,26 @@ 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@. +\begin{cfa} +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{cfa} +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} +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} @@ -353,6 +467,5 @@ 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. +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. @@ -360,19 +473,14 @@ 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 + \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} @@ -391,6 +499,4 @@ \subsection{Returning an array is (but) almost possible} - - @@ -414,17 +520,17 @@ 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} +\begin{cfa} +// 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{cfa} 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. @@ -436,13 +542,13 @@ 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} +\begin{cfa} +ar1[5]; +(*ar2)[5]; +\end{cfa} 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} +\begin{cfa} +tm (&ar3)[10] = *alloc(); +ar3[5]; +\end{cfa} The implicit size communication to @alloc@ still works in the same ways as for @ar2@. @@ -453,7 +559,6 @@ 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)@ - - +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? Index: doc/theses/mike_brooks_MMath/programs/bkgd-c-tyerr.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-c-tyerr.c (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/programs/bkgd-c-tyerr.c (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -10,49 +10,15 @@ int main() { + float * x; $\C{// x points at a floating-point number}$ + void (*y)(void); $\C{// y points at a function}$ + @x = y;@ $\C{// wrong}$ + @y = x;@ $\C{// wrong}$ -/* - These attempts to assign @y@ to @x@ and vice-versa are obviously ill-typed. -*/ - float * x; // x points at a floating-point number - void (*y)(void); // y points at a function - ERR( - x = y; // wrong - y = x; // wrong - ) + float pi = 3.14; + void f( void (*g)(void) ) { g(); } + @f( &pi );@ $\C{// wrong}$ +} -/* - The first gets - warning: assignment to `float *' from incompatible pointer type `void (*)(void)' - and the second gets the opposite. - - Similarly, -*/ - - float pi = 3.14; - void f( void (*g)(void) ) { - g(); - } - ERR( - f( & pi ); // wrong - ) -/* - gets - warning: passing argument 1 of `f' from incompatible pointer type - with a segmentation fault at runtime. - - That @f@'s attempt to call @g@ fails is not due to 3.14 being a particularly unlucky choice of value to put in the variable @pi@. - Rather, it is because obtaining a program that includes this essential fragment, yet exhibits a behaviour other than "doomed to crash," is a matter for an obfuscated coding competition. - - A "tractable syntactic method for proving the absence of certain program behaviours - by classifying phrases according to the kinds of values they compute"*1 - rejected the program. The behaviour (whose absence is unprovable) is neither minor nor unlikely. - The rejection shows that the program is ill-typed. - - Yet, the rejection presents as a GCC warning. - - In the discussion following, ``ill-typed'' means giving a nonzero @gcc -Werror@ exit condition with a message that discusses typing. - - *1 TAPL-pg1 definition of a type system -*/ - -} +// Local Variables: // +// compile-command: "sed -f sedcmd bkgd-c-tyerr.c > tmp.c; gcc tmp.c" // +// End: // Index: doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/programs/bkgd-carray-arrty.c (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -24,172 +24,117 @@ - // SHOW(sizeof( a ), "%zd"); - // SHOW(sizeof(&a ), "%zd"); - // SHOW(sizeof( a[0]), "%zd"); - // SHOW(sizeof(&a[0]), "%zd"); + // SHOW(sizeof( a ), "%zd"); + // SHOW(sizeof(&a ), "%zd"); + // SHOW(sizeof( a[0]), "%zd"); + // SHOW(sizeof(&a[0]), "%zd"); int main() { + float a[10]; + static_assert(sizeof(float) == 4); $\C{// floats (array elements) are 4 bytes}$ + static_assert(sizeof(void*) == 8); $\C{// pointers are 8 bytes}$ + static_assert(sizeof(a) == 40); $\C{// array}$ + static_assert(sizeof(&a) == 8 ); $\C{// pointer to array}$ + static_assert(sizeof(a[0]) == 4 ); $\C{// first element}$ + static_assert(sizeof(&(a[0])) == 8 ); $\C{// pointer to first element}$ -/* -When a programmer works with an array, C semantics provide access to a type that is different in every way from ``pointer to its first element.'' + typeof(&a) x; $\C{// x is pointer to array}$ + typeof(&(a[0])) y; $\C{// y is pointer to first element}$ + @x = y;@ $\C{// ill-typed}$ + @y = x;@ $\C{// ill-typed}$ + static_assert(sizeof(typeof(a)) == 40); + static_assert(sizeof(typeof(&a)) == 8 ); + static_assert(sizeof(typeof(a[0])) == 4 ); + static_assert(sizeof(typeof(&(a[0]))) == 8 ); -Its qualities become apparent by inspecting the declaration -*/ - float a[10]; -/* + void f( float (*pa)[10] ) { + static_assert(sizeof( *pa ) == 40); $\C{// array}$ + static_assert(sizeof( pa ) == 8 ); $\C{// pointer to array}$ + static_assert(sizeof( (*pa)[0] ) == 4 ); $\C{// first element}$ + static_assert(sizeof(&((*pa)[0])) == 8 ); $\C{// pointer to first element}$ + } + f( & a ); -The inspection begins by using @sizeof@ to provide definite program semantics for the intuition of an expression's type. + float fs[] = {3.14, 1.707}; + char cs[] = "hello"; -Assuming a target platform keeps things concrete: -*/ - static_assert(sizeof(float)==4); // floats (array elements) are 4 bytes - static_assert(sizeof(void*)==8); // pointers are 8 bytes -/* - -Consider the sizes of expressions derived from @a@, modified by adding ``pointer to'' and ``first element'' (and including unnecessary parentheses to avoid confusion about precedence). -*/ - static_assert(sizeof( a ) == 40); // array - static_assert(sizeof(& a ) == 8 ); // pointer to array - static_assert(sizeof( a[0] ) == 4 ); // first element - static_assert(sizeof(&(a[0])) == 8 ); // pointer to first element -/* -That @a@ takes up 40 bytes is common reasoning for C programmers. -Set aside for a moment the claim that this first assertion is giving information about a type. -For now, note that an array and a pointer to its first element are, sometimes, different things. - -The idea that there is such a thing as a pointer to an array may be surprising. -It is not the same thing as a pointer to the first element: -*/ - typeof(& a ) x; // x is pointer to array - typeof(&(a[0])) y; // y is pointer to first element - ERR( - x = y; // ill-typed - y = x; // ill-typed - ) -/* -The first gets - warning: warning: assignment to `float (*)[10]' from incompatible pointer type `float *' -and the second gets the opposite. -*/ - -/* -We now refute a concern that @sizeof(a)@ is reporting on special knowledge from @a@ being an local variable, -say that it is informing about an allocation, rather than simply a type. - -First, recognizing that @sizeof@ has two forms, one operating on an expression, the other on a type, we observe that the original answers are unaffected by using the type-parameterized form: -*/ - static_assert(sizeof(typeof( a )) == 40); - static_assert(sizeof(typeof(& a )) == 8 ); - static_assert(sizeof(typeof( a[0] )) == 4 ); - static_assert(sizeof(typeof(&(a[0]))) == 8 ); - -/* -Finally, the same sizing is reported when there is no allocation at all, and we launch the analysis instead from the pointer-to-array type. -*/ - void f( float (*pa)[10] ) { - static_assert(sizeof( *pa ) == 40); // array - static_assert(sizeof( pa ) == 8 ); // pointer to array - static_assert(sizeof( (*pa)[0] ) == 4 ); // first element - static_assert(sizeof(&((*pa)[0])) == 8 ); // pointer to first element - } - f( & a ); - -/* -So, in spite of considerable programmer success enabled by an understanding that -an array just a pointer to its first element (revisited TODO pointer decay), -this understanding is simplistic. -*/ - -/* -A shortened form for declaring local variables exists, provided that length information is given in the initializer: -*/ - float fs[] = {3.14, 1.707}; - char cs[] = "hello"; - - static_assert( sizeof(fs) == 2 * sizeof(float) ); - static_assert( sizeof(cs) == 6 * sizeof(char) ); // 5 letters + 1 null terminator - -/* -In these declarations, the resulting types are both arrays, but their lengths are inferred. -*/ - + static_assert( sizeof(fs) == 2 * sizeof(float) ); + static_assert( sizeof(cs) == 6 * sizeof(char) ); $\C{// 5 letters + 1 null terminator}$ } +void syntaxReferenceCheck(void) { + // $\rightarrow$ & (base element) + // & @float@ + // & @float x;@ + // & @[ float ]@ + // & @[ float ]@ + float x0; -void syntaxReferenceCheck(void) { - // $\rightarrow$ & (base element) - // & @float@ - // & @float x;@ - // & @[ float ]@ - // & @[ float ]@ - float x0; + // $\rightarrow$ & pointer + // & @float *@ + // & @float * x;@ + // & @[ * float ]@ + // & @[ * float ]@ + float * x1; - // $\rightarrow$ & pointer - // & @float *@ - // & @float * x;@ - // & @[ * float ]@ - // & @[ * float ]@ - float * x1; + // $\rightarrow$ & array + // & @float[10]@ + // & @float x[10];@ + // & @[ [10] float ]@ + // & @[ array(float, 10) ]@ + float x2[10]; - // $\rightarrow$ & array - // & @float[10]@ - // & @float x[10];@ - // & @[ [10] float ]@ - // & @[ array(float, 10) ]@ - float x2[10]; + typeof(float[10]) x2b; - typeof(float[10]) x2b; - - // & array of pointers - // & @(float*)[10]@ - // & @float *x[10];@ - // & @[ [10] * float ]@ - // & @[ array(*float, 10) ]@ - float *x3[10]; + // & array of pointers + // & @(float*)[10]@ + // & @float *x[10];@ + // & @[ [10] * float ]@ + // & @[ array(*float, 10) ]@ + float *x3[10]; // (float *)x3a[10]; NO - // $\rightarrow$ & pointer to array - // & @float(*)[10]@ - // & @float (*x)[10];@ - // & @[ * [10] float ]@ - // & @[ * array(float, 10) ]@ - float (*x4)[10]; + // $\rightarrow$ & pointer to array + // & @float(*)[10]@ + // & @float (*x)[10];@ + // & @[ * [10] float ]@ + // & @[ * array(float, 10) ]@ + float (*x4)[10]; - // & pointer to array - // & @(float*)(*)[10]@ - // & @float *(*x)[10];@ - // & @[ * [10] * float ]@ - // & @[ * array(*float, 10) ]@ - float *(*x5)[10]; - x5 = (float*(*)[10]) x4; + // & pointer to array + // & @(float*)(*)[10]@ + // & @float *(*x)[10];@ + // & @[ * [10] * float ]@ + // & @[ * array(*float, 10) ]@ + float *(*x5)[10]; + x5 = (float*(*)[10]) x4; // x5 = (float(*)[10]) x4; // wrong target type; meta test suggesting above cast uses correct type - // [here] - // const + // [here] + // const - // [later] - // static - // star as dimension - // under pointer decay: int p1[const 3] being int const *p1 + // [later] + // static + // star as dimension + // under pointer decay: int p1[const 3] being int const *p1 - const float * y1; - float const * y2; - float * const y3; + const float * y1; + float const * y2; + float * const y3; - y1 = 0; - y2 = 0; - // y3 = 0; // bad + y1 = 0; + y2 = 0; + // y3 = 0; // bad - // *y1 = 3.14; // bad - // *y2 = 3.14; // bad - *y3 = 3.14; + // *y1 = 3.14; // bad + // *y2 = 3.14; // bad + *y3 = 3.14; - const float z1 = 1.414; - float const z2 = 1.414; + const float z1 = 1.414; + float const z2 = 1.414; - // z1 = 3.14; // bad - // z2 = 3.14; // bad + // z1 = 3.14; // bad + // z2 = 3.14; // bad @@ -199,6 +144,10 @@ void stx2() { const T x[10]; // x[5] = 3.14; // bad - } + } void stx3() { T const x[10]; // x[5] = 3.14; // bad - } + } + +// Local Variables: // +// compile-command: "sed -f sedcmd bkgd-carray-arrty.c > tmp.c; gcc tmp.c" // +// End: // Index: doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c =================================================================== --- doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/programs/bkgd-carray-decay.c (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -1,111 +1,47 @@ #include int main() { + float a[10]; $\C{// array}$ + float (*pa)[10] = &a; $\C{// pointer to array}$ + float a0 = a[0]; $\C{// element}$ + float *pa0 = &(a[0]); $\C{// pointer to element}$ -/* -The last section established the difference between these four types: -*/ + float *pa0x = a; $\C{// (ok)}$ + assert( pa0 == pa0x ); + assert( sizeof(pa0x) != sizeof(a) ); - float a [10] ; // array - float (*pa )[10] = & a ; // pointer to array - float a0 = a[0] ; // element - float *pa0 = &(a[0]); // pointer to element + void f( float x[10], float *y ) { + static_assert( sizeof(x) == sizeof(void*) ); + static_assert( sizeof(y) == sizeof(void*) ); + } + f(0,0); -/* -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 -*/ - float *pa0x = a ; // (ok) -/* -which reproduces @pa0@, in type and value: -*/ - assert( pa0 == pa0x ); -/* -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 @a@, when they are not of the same type: -*/ - assert( sizeof(pa0x) != sizeof(a) ); + // reusing local var `float a[10];`} + float v; + f( a, a ); $\C{// ok: two decays, one into an array spelling}$ + f( &v, &v ); $\C{// ok: no decays; a non-array passes to an array spelling}$ + char ca[] = "hello"; $\C{// array on stack, initialized from read-only data}$ + char *cp = "hello"; $\C{// pointer to read-only data [decay here]}$ + void edit(char c[]) { $\C{// param is pointer}$ + c[3] = 'p'; + } + edit(ca); $\C{// ok [decay here]}$ + edit(cp); $\C{// Segmentation fault}$ + edit("hello"); $\C{// Segmentation fault [decay here]}$ + void decay( float x[10] ) { + static_assert( sizeof(x) == sizeof(void*) ); + } + static_assert( sizeof(a) == 10 * sizeof(float) ); + decay(a); + void no_decay( float (*px)[10] ) { + static_assert( sizeof(*px) == 10 * sizeof(float) ); + } + static_assert( sizeof(*pa) == 10 * sizeof(float) ); + no_decay(pa); +} - - - - - - - - - - void f( float x[10], float *y ) { - static_assert( sizeof(x) == sizeof(void*) ); - static_assert( sizeof(y) == sizeof(void*) ); - } - f(0,0); - - - - - - - - - - - - - - - - // reusing local var `float a[10];` - float v; - f( a, a ); // ok: two decays, one into an array spelling - f( &v, &v ); // ok: no decays; a non-array passes to an array spelling - - - - - - - - - - - - - - - - - char ca[] = "hello"; // array on stack, initialized from read-only data - char *cp = "hello"; // pointer to read-only data [decay here] - void edit(char c[]) { // param is pointer - c[3] = 'p'; - } - edit(ca); // ok [decay here] - edit(cp); // Segmentation fault - edit("hello"); // Segmentation fault [decay here] - - - - - - - - - - - - - void decay( float x[10] ) { - static_assert( sizeof(x) == sizeof(void*) ); - } - static_assert( sizeof(a) == 10 * sizeof(float) ); - decay(a); - - void no_decay( float (*px)[10] ) { - static_assert( sizeof(*px) == 10 * sizeof(float) ); - } - static_assert( sizeof(*pa) == 10 * sizeof(float) ); - no_decay(pa); -} +// Local Variables: // +// compile-command: "sed -f sedcmd bkgd-carray-decay.c > tmp.c; gcc tmp.c" // +// End: // Index: doc/theses/mike_brooks_MMath/programs/sedcmd =================================================================== --- doc/theses/mike_brooks_MMath/programs/sedcmd (revision 266732e2818527a06669f666f04fb32c296a3b9f) +++ doc/theses/mike_brooks_MMath/programs/sedcmd (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -0,0 +1,3 @@ +s/@//g +s/\$\\C{//g +s/}\$//g Index: doc/theses/mike_brooks_MMath/string.tex =================================================================== --- doc/theses/mike_brooks_MMath/string.tex (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/string.tex (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -6,4 +6,13 @@ \input{sharing-demo.tex} + +Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@. +\par\noindent +\begin{tabular}{llll} + & @s1@ & @s1a@ & @s2@ \\ +%\input{sharing-demo1.tex} +\end{tabular} +\par\noindent + \subsection{RAII limitations} @@ -225,2 +234,4 @@ } \end{lstlisting} + +\section{String I/O} Index: doc/theses/mike_brooks_MMath/uw-ethesis.tex =================================================================== --- doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision e72fc60c45c40f15ed2eb81b8f581c866cf011dc) +++ doc/theses/mike_brooks_MMath/uw-ethesis.tex (revision 266732e2818527a06669f666f04fb32c296a3b9f) @@ -1,8 +1,8 @@ %====================================================================== -% University of Waterloo Thesis Template for LaTeX -% Last Updated November, 2020 -% by Stephen Carr, IST Client Services, +% University of Waterloo Thesis Template for LaTeX +% Last Updated August 2022 +% by IST Client Services, % University of Waterloo, 200 University Ave. W., Waterloo, Ontario, Canada -% FOR ASSISTANCE, please send mail to request@uwaterloo.ca +% FOR ASSISTANCE, please send mail to helpdesk@uwaterloo.ca % DISCLAIMER @@ -21,9 +21,10 @@ % DON'T FORGET TO ADD YOUR OWN NAME AND TITLE in the "hyperref" package configuration below. -% THIS INFORMATION GETS EMBEDDED IN THE PDF FINAL PDF DOCUMENT. +% Search for: PDFTITLE, PDFAUTHOR, PDFSUBJECT, and PDFKEYWORDS. +% THIS INFORMATION GETS EMBEDDED IN THE FINAL PDF DOCUMENT. % You can view the information if you view properties of the PDF document. -% Many faculties/departments also require one or more printed copies. -% This template attempts to satisfy both types of output. +% Many faculties/departments also require one or more printed copies. +% This template attempts to satisfy both types of output. % See additional notes below. % It is based on the standard "book" document class which provides all necessary sectioning structures and allows multi-part theses. @@ -32,5 +33,5 @@ % For people who prefer to install their own LaTeX distributions on their own computers, and process the source files manually, the following notes provide the sequence of tasks: - + % E.g. to process a thesis called "mythesis.tex" based on this template, run: @@ -51,5 +52,5 @@ % Tip: Photographs should be cropped and compressed so as not to be too large. -% To create a PDF output that is optimized for double-sided printing: +% To create a PDF output that is optimized for double-sided printing: % 1) comment-out the \documentclass statement in the preamble below, and un-comment the second \documentclass line. % 2) change the value assigned below to the boolean variable "PrintVersion" from " false" to "true". @@ -60,7 +61,6 @@ % For hyperlinked PDF, suitable for viewing on a computer, use this: \documentclass[letterpaper,12pt,titlepage,oneside,final]{book} -\usepackage{times} \usepackage[T1]{fontenc} % Latin-1 => 256-bit characters, => | not dash, <> not Spanish question marks - + % For PDF, suitable for double-sided printing, change the PrintVersion variable below to "true" and use this \documentclass line instead of the one above: %\documentclass[letterpaper,12pt,titlepage,openright,twoside,final]{book} @@ -69,5 +69,5 @@ % If you have to, it's easier to make changes to nomenclature once here than in a million places throughout your thesis! \newcommand{\package}[1]{\textbf{#1}} % package names in bold text -\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font +\newcommand{\cmmd}[1]{\textbackslash\texttt{#1}} % command name in tt font \newcommand{\href}[1]{#1} % does nothing, but defines the command so the print-optimized version will ignore \href tags (redefined by hyperref pkg). %\newcommand{\texorpdfstring}[2]{#1} % does nothing, but defines the command @@ -82,22 +82,35 @@ %\usepackage{nomencl} % For a nomenclature (optional; available from ctan.org) \usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments +\usepackage{fullpage,times,comment} \usepackage{xcolor} \usepackage{epic,eepic} \usepackage{graphicx} -\graphicspath{{pictures/}} % picture directory -\usepackage{comment} % Removes large sections of the document. \usepackage{tabularx} \usepackage[labelformat=simple,aboveskip=0pt,farskip=0pt,font=normalsize]{subfig} \renewcommand\thesubfigure{(\alph{subfigure})} -\usepackage{algorithm} -\usepackage{algpseudocode} - +\graphicspath{{pictures/}} % picture directory +%\usepackage{algorithm} +%\usepackage{algpseudocode} \usepackage{pbox} + +\makeatletter +\newcommand{\lstinput}[2]{\lstinputlisting[linerange={#1},xleftmargin=4pt,escapechar={\$},moredelim={**[is][\color{red}]{@}{@}}]{#2}} +\makeatother +% cfa macros used in the document +\input{common} +%\usepackage{common} +\CFAStyle % CFA code-style +\lstset{language=cfa,belowskip=-1pt} % set default language to CFA +\lstset{inputpath={programs}} + +\newcommand{\uCpp}{$\mu$\CC} +\newcommand{\PAB}[1]{{\color{red}PAB: #1}} % Hyperlinks make it very easy to navigate an electronic document. % In addition, this is where you should specify the thesis title and author as they appear in the properties of the PDF document. -% Use the "hyperref" package +% Use the "hyperref" package % N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE +\usepackage{url} \usepackage[pagebackref=true]{hyperref} % with basic options %\usepackage[pdftex,pagebackref=true]{hyperref} @@ -110,28 +123,31 @@ pdffitwindow=false, % window fit to page when opened pdfstartview={FitH}, % fits the width of the page to the window - pdftitle={Cforall Memory Allocation}, % title: CHANGE THIS TEXT! - pdfauthor={Mubeen Zulfiqar}, % author: CHANGE THIS TEXT! and uncomment this line + pdftitle={\CFA Container Library}, % title: CHANGE THIS TEXT! + pdfauthor={Mike Brooks}, % author: CHANGE THIS TEXT! and uncomment this line pdfsubject={Cforall}, % subject: CHANGE THIS TEXT! and uncomment this line - pdfkeywords={Cforall} {storage allocation} {C language}, % optional list of keywords + pdfkeywords={Cforall} {container library} {C language}, % optional list of keywords pdfnewwindow=true, % links in new window colorlinks=true, % false: boxed links; true: colored links linkcolor=blue, % color of internal links - citecolor=blue, % color of links to bibliography + citecolor=blue, % color of links to bibliography filecolor=magenta, % color of file links - urlcolor=blue, % color of external links + urlcolor=blue, % color of external links breaklinks=true } \ifthenelse{\boolean{PrintVersion}}{ % for improved print quality, change some hyperref options \hypersetup{ % override some previously defined hyperref options +% colorlinks,% citecolor=black,% filecolor=black,% linkcolor=black,% - urlcolor=black -}}{} % end of ifthenelse (no else) + urlcolor=black} +}{} % end of ifthenelse (no else) + +\usepackage{breakurl} \urlstyle{sf} %\usepackage[automake,toc,abbreviations]{glossaries-extra} % Exception to the rule of hyperref being the last add-on package -% If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra), -% although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and +% If glossaries-extra is not in your LaTeX distribution, get it from CTAN (http://ctan.org/pkg/glossaries-extra), +% although it's supposed to be in both the TeX Live and MikTeX distributions. There are also documentation and % installation instructions there. @@ -140,9 +156,9 @@ % Setting up the page margins... -\setlength{\textheight}{9in} -\setlength{\topmargin}{-0.45in} -\setlength{\headsep}{0.25in} +%\setlength{\textheight}{9in} +%\setlength{\topmargin}{-0.45in} +%\setlength{\headsep}{0.25in} % uWaterloo thesis requirements specify a minimum of 1 inch (72pt) margin at the -% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter margin (on binding side). +% top, bottom, and outside page edges and a 1.125 in. (81pt) gutter margin (on binding side). % While this is not an issue for electronic viewing, a PDF may be printed, and so we have the same page layout for both printed and electronic versions, we leave the gutter margin in. % Set margins to minimum permitted by uWaterloo thesis regulations: @@ -152,5 +168,5 @@ % edge is less than 15 mm (0.6 in.) \setlength{\marginparsep}{0pt} % width of space between body text and margin notes -\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all +\setlength{\evensidemargin}{0.125in} % Adds 1/8 in. to binding side of all % even-numbered pages when the "twoside" printing option is selected \setlength{\oddsidemargin}{0.125in} % Adds 1/8 in. to the left of all pages when "oneside" printing is selected, and to the left of all odd-numbered pages when "twoside" printing is selected @@ -161,5 +177,5 @@ \setlength{\parskip}{\medskipamount} -% The following statement controls the line spacing. +% The following statement controls the line spacing. % The default spacing corresponds to good typographic conventions and only slight changes (e.g., perhaps "1.2"), if any, should be made. \renewcommand{\baselinestretch}{1} % this is the default line space setting @@ -174,19 +190,7 @@ \let\cleardoublepage\clearemptydoublepage -% Define Glossary terms (This is properly done here, in the preamble and -% could also be \input{} from a separate file...) +% Define Glossary terms (This is properly done here, in the preamble and could also be \input{} from a separate file...) %\input{glossaries} %\makeglossaries - -% cfa macros used in the document -\input{common} -%\usepackageinput{common} -\CFAStyle % CFA code-style -\lstset{language=CFA} % default language -\lstset{basicstyle=\linespread{0.9}\sf} % CFA typewriter font -\lstset{inputpath={programs}} -\newcommand{\PAB}[1]{{\color{red}PAB: #1}} - -\newcommand{\uCpp}{$\mu$\CC} %====================================================================== @@ -202,5 +206,5 @@ % dedication, table of contents, list of tables, list of figures, nomenclature, etc. %---------------------------------------------------------------------- -\input{uw-ethesis-frontpgs} +\input{uw-ethesis-frontpgs} %---------------------------------------------------------------------- @@ -211,5 +215,5 @@ % Tip: Putting each sentence on a new line is a way to simplify later editing. %---------------------------------------------------------------------- -\begin{sloppypar} + \input{intro} \input{background} @@ -219,6 +223,4 @@ \input{conclusion} -\end{sloppypar} - %---------------------------------------------------------------------- % END MATERIAL @@ -228,12 +230,12 @@ % Bibliography -% The following statement selects the style to use for references. +% The following statement selects the style to use for references. % It controls the sort order of the entries in the bibliography and also the formatting for the in-text labels. \bibliographystyle{plain} -% This specifies the location of the file containing the bibliographic information. +% This specifies the location of the file containing the bibliographic information. % It assumes you're using BibTeX to manage your references (if not, why not?). \cleardoublepage % This is needed if the "book" document class is used, to place the anchor in the correct page, because the bibliography will start on its own page. % Use \clearpage instead if the document class uses the "oneside" argument -\phantomsection % With hyperref package, enables hyperlinking from the table of contents to bibliography +\phantomsection % With hyperref package, enables hyperlinking from the table of contents to bibliography % The following statement causes the title "References" to be used for the bibliography section: \renewcommand*{\bibname}{References} @@ -243,8 +245,8 @@ \bibliography{pl,uw-ethesis} -% Tip: You can create multiple .bib files to organize your references. +% Tip: You can create multiple .bib files to organize your references. % Just list them all in the \bibliogaphy command, separated by commas (no spaces). -% The following statement causes the specified references to be added to the bibliography even if they were not cited in the text. +% The following statement causes the specified references to be added to the bibliography even if they were not cited in the text. % The asterisk is a wildcard that causes all entries in the bibliographic database to be included (optional). % \nocite{*} @@ -261,6 +263,5 @@ % \input{appendix-matlab_plots.tex} -% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. -% provided by the glossaries-extra package) +% GLOSSARIES (Lists of definitions, abbreviations, symbols, etc. provided by the glossaries-extra package) % ----------------------------- %\printglossaries