Changeset 8614140

doc/theses/mike_brooks_MMath/Makefile

-              r79ba50c
+              r8614140
 BibRep = ../../bibliography
+strip-top-dir = $(foreach p,$1,$(patsubst %/,%,$(subst $(firstword $(subst /, ,$(p)))/,, $(p))))
+.SUFFIXES:  # disable make built-in rules
 TeXSRC = ${wildcard *.tex}
 PicSRC = ${notdir ${wildcard ${Pictures}/*.png}} ${notdir ${wildcard ${Pictures}/*.fig}}
 …
 PgmSRC = ${notdir ${wildcard ${Programs}/*}}
 RunPgmSRC = ${notdir ${wildcard ${Programs}/*.run.*}}
+NondemoPgmSRC = ${call strip-top-dir,${wildcard ${Programs}/*/*.c*}}
 BibSRC = ${wildcard *.bib}
 …
 # File Dependencies
 ${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${PlotSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
+${DOCUMENT}: ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${NondemoPgmSRC} ${PlotSRC} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
         echo ${PicSRC}
         echo ${GraphSRC_OLD}

doc/theses/mike_brooks_MMath/array.tex

-              r79ba50c
+              r8614140
 \label{c:Array}
 Arrays in C are possibly the single most misunderstood and incorrectly used feature in the language, resulting in the largest proportion of runtime errors and security violations.
+Arrays in C are possibly the single most misunderstood and incorrectly used feature in the language \see{\VRef{s:Array}}, resulting in the largest proportion of runtime errors and security violations.
 This chapter describes the new \CFA language and library features that introduce a length-checked array type, @array@, to the \CFA standard library~\cite{Cforall}.
 …
 \label{s:ArrayIntro}
+The new \CFA array is declared by instantiating the generic @array@ type,
+much like instantiating any other standard-library generic type (such as \CC @vector@),
+though using a new style of generic parameter.
+The new \CFA array is declared by instantiating the generic @array@ type, much like instantiating any other standard-library generic type (such as \CC @vector@), using a new style of generic parameter.
 \begin{cfa}
 @array( float, 99 )@ x;                                 $\C[2.5in]{// x contains 99 floats}$
 …
 void f( @array( float, 42 )@ & p ) {}   $\C{// p accepts 42 floats}$
 f( x );                                                                 $\C{// statically rejected: type lengths are different, 99 != 42}$
 test2.cfa:3:1 error: Invalid application of existing declaration(s) in expression.
 Applying untyped:  Name: f ... to:  Name: x
 …
 g( x, 0 );                                                              $\C{// T is float, N is 99, dynamic subscript check succeeds}$
 g( x, 1000 );                                                   $\C{// T is float, N is 99, dynamic subscript check fails}$
 Cforall Runtime error: subscript 1000 exceeds dimension range [0,99) $for$ array 0x555555558020.
 \end{cfa}
 …
 is a sufficient postcondition.
 In an imperative language like C and \CFA, it is also necessary to discuss side effects, for which an even heavier formalism, like separation logic, is required.
 Secondly, TODO: bash Rust.
 % TODO: cite the crap out of these claims.
+Secondly: ... bash Rust.
+... cite the crap out of these claims.
 \end{comment}
 …
 forall( T & | sized(T) )
 T * alloc() {
         return @(T *)@malloc( @sizeof(T)@ );
+        return @(T *)@malloc( @sizeof(T)@ );    // C malloc
+}
 \end{cfa}
 …
 The loops follow the familiar pattern of using the variable @dim@ to iterate through the arrays.
 Most importantly, the type system implicitly captures @dim@ at the call of @f@ and makes it available throughout @f@ as @N@.
 The example shows @dim@ adapting into a type-system managed length at the declarations of @x@, @y@, and @result@, @N@ adapting in the same way at @f@'s loop bound, and a pass-thru use of @dim@ at @f@'s declaration of @ret@.
+The example shows @dim@ adapting into a type-system managed length at the declarations of @x@, @y@, and @result@; @N@ adapting in the same way at @f@'s loop bound; and a pass-thru use of @dim@ at @f@'s declaration of @ret@.
 Except for the lifetime-management issue of @result@, \ie explicit @free@, this program has eliminated both the syntactic and semantic problems associated with C arrays and their usage.
 The result is a significant improvement in safety and usability.
 …
 \end{itemize}
+\VRef[Figure]{f:TemplateVsGenericType} shows @N@ is not the same as a @size_t@ declaration in a \CC \lstinline[language=C++]{template}.
+\VRef[Figure]{f:TemplateVsGenericType} shows @N@ is not the same as a @size_t@ declaration in a \CC \lstinline[language=C++]{template}.\footnote{
+The \CFA program requires a snapshot declaration for \lstinline{n} to compile, as described at the end of \Vref{s:ArrayTypingC}.}
 \begin{enumerate}[leftmargin=*]
 \item
 The \CC template @N@ can only be a compile-time value, while the \CFA @N@ may be a runtime value.
 \item
 \CC does not allow a template function to be nested, while \CFA lets its polymorphic functions to be nested.
+\CC does not allow a template function to be nested, while \CFA allows polymorphic functions be nested.
 Hence, \CC precludes a simple form of information hiding.
 \item
 …
 % mycode/arrr/thesis-examples/check-peter/cs-cpp.cpp, v10
 \end{enumerate}
+The \CC template @array@ type mitigates points \VRef[]{p:DimensionPassing} and \VRef[]{p:ArrayCopy}, but it is also trying to accomplish a similar mechanism to \CFA @array@.
+The \CC template @std::array@ tries to accomplish a similar mechanism to \CFA @array@.
+It is an aggregate type with the same semantics as a @struct@ holding a C-style array \see{\VRef{s:ArraysCouldbeValues}}, which mitigates points \VRef[]{p:DimensionPassing} and \VRef[]{p:ArrayCopy}.
 \begin{figure}
 \begin{tabular}{@{}l@{\hspace{20pt}}l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{c++}
 …
+}
 int main() {
         int ret[10], x[10];
         for ( int i = 0; i < 10; i += 1 ) x[i] = i;
         @copy<int, 10 >( ret, x );@
         for ( int i = 0; i < 10; i += 1 )
+        const size_t  n = 10;   // must be constant
+        int ret[n], x[n];
+        for ( int i = 0; i < n; i += 1 ) x[i] = i;
+        @copy<int, n >( ret, x );@
+        for ( int i = 0; i < n; i += 1 )
                 cout << ret[i] << ' ';
         cout << endl;
 …
                 for ( i; N ) ret[i] = x[i];
+        }
         const int n = promptForLength();
+        size_t  n;
+        sin | n;
         array( int, n ) ret, x;
         for ( i; n ) x[i] = i;
 …
 When the argument lengths themselves are statically unknown,
 the static check is conservative and, as always, \CFA's casting lets the programmer use knowledge not shared with the type system.
+\begin{tabular}{@{\hspace{0.5in}}l@{\hspace{1in}}l@{}}
+\lstinput{90-97}{hello-array.cfa}
+&
+\lstinput{110-117}{hello-array.cfa}
+\end{tabular}
+\noindent
+This static check's full rules are presented in \VRef[Section]{s:ArrayTypingC}.
+\lstinput{90-96}{hello-array.cfa}
+This static check's rules are presented in \VRef[Section]{s:ArrayTypingC}.
 Orthogonally, the \CFA array type works within generic \emph{types}, \ie @forall@-on-@struct@.
 The same argument safety and the associated implicit communication of array length occurs.
 Preexisting \CFA allowed aggregate types to be generalized with type parameters, enabling parameterizing of element types.
 This has been extended to allow parameterizing by dimension.
 Doing so gives a refinement of C's ``flexible array member''~\cite[\S~6.7.2.1.18]{C11}.
+This feature is extended to allow parameterizing by dimension.
+Doing so gives a refinement of C's ``flexible array member''~\cite[\S~6.7.2.1.18]{C11}:
 \begin{cfa}
 struct S {
 …
 \end{cfa}
 This ability to avoid casting and size arithmetic improves safety and usability over C flexible array members.
 Finally, inputs and outputs are given at the bottom for different sized schools.
+Finally, inputs and outputs are given on the right for different sized schools.
 The example program prints the courses in each student's preferred order, all using the looked-up display names.
 \begin{figure}
+\begin{cquote}
+\lstinput{50-55}{hello-accordion.cfa}
+\begin{lrbox}{\myboxA}
+\begin{tabular}{@{}l@{}}
+\lstinput{50-55}{hello-accordion.cfa} \\
 \lstinput{90-98}{hello-accordion.cfa}
+\ \\
+@$ cat school1@
+\lstinput{}{school1}
+@$ ./a.out < school1@
+\lstinput{}{school1.out}
+@$ cat school2@
+\lstinput{}{school2}
+@$ ./a.out < school2@
+\lstinput{}{school2.out}
+\end{cquote}
+\end{tabular}
+\end{lrbox}
+\begin{lrbox}{\myboxB}
+\begin{tabular}{@{}l@{}}
+@$ cat school1@ \\
+\lstinputlisting{school1} \\
+@$ ./a.out < school1@ \\
+\lstinputlisting{school1.out} \\
+@$ cat school2@ \\
+\lstinputlisting{school2} \\
+@$ ./a.out < school2@ \\
+\lstinputlisting{school2.out}
+\end{tabular}
+\end{lrbox}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{@{}ll@{}}
+\usebox\myboxA
+&
+\usebox\myboxB
+\end{tabular}
 \caption{\lstinline{School} Example, Input and Output}
 …
 When a function operates on a @School@ structure, the type system handles its memory layout transparently.
 \lstinput{30-37}{hello-accordion.cfa}
+\lstinput{30-36}{hello-accordion.cfa}
 In the example, function @getPref@ returns, for the student at position @is@, what is the position of their @pref@\textsuperscript{th}-favoured class?
 …
 \section{Dimension Parameter Implementation}
 The core of the preexisting \CFA compiler already had the ``heavy equipment'' needed to provide the feature set just reviewed (up to bugs in cases not yet exercised).
+The core of the preexisting \CFA compiler already has the ``heavy equipment'' needed to provide the feature set just reviewed (up to bugs in cases not yet exercised).
 To apply this equipment in tracking array lengths, I encoded a dimension (array's length) as a type.
 The type in question does not describe any data that the program actually uses at runtime.
 …
 \begin{itemize}[leftmargin=*]
 \item
         Resolver provided values for a used declaration's type-system variables, gathered from type information in scope at the usage site.
 \item
         The box pass, encoding information about type parameters into ``extra'' regular parameters/arguments on declarations and calls.
+        Resolver provided values for a declaration's type-system variables, gathered from type information in scope at the usage site.
+\item
+        The box pass, encoding information about type parameters into ``extra'' regular parameters and arguments on declarations and calls.
         Notably, it conveys the size of a type @foo@ as a @__sizeof_foo@ parameter, and rewrites the @sizeof(foo)@ expression as @__sizeof_foo@, \ie a use of the parameter.
 \end{itemize}
 …
 The rules for resolution had to be restricted slightly, in order to achieve important refusal cases.
 This work is detailed in \VRef[Section]{s:ArrayTypingC}.
 However, the resolution--boxing scheme, in its preexisting state, was already equipped to work on (desugared) dimension parameters.
+However, the resolution--boxing scheme, in its preexisting state, is equipped to work on (desugared) dimension parameters.
 The following discussion explains the desugaring and how correctly lowered code results.
 …
 \end{enumerate}
 The chosen solution is to encode the value @N@ \emph{as a type}, so items 1 and 2 are immediately available for free.
 Item 3 needs a way to recover the encoded value from a (valid) type (and to reject invalid types occurring here).
+Item 3 needs a way to recover the encoded value from a (valid) type and to reject invalid types.
 Item 4 needs a way to produce a type that encodes the given value.
 …
         The type @thing(N)@ is (replaced by @void *@, but thereby effectively) gone.
 \item
         The @sout...@ expression (being an application of the @?|?@ operator) has a regular variable (parameter) usage for its second argument.
+        The @sout...@ expression has a regular variable (parameter) usage for its second argument.
 \item
         Information about the particular @thing@ instantiation (value 10) is moved, from the type, to a regular function-call argument.
 …
 \begin{cfa}
 enum { n = 42 };
 float x[@n@];   // or just 42
 float (*xp1)[@42@] = &x;    // accept
 float (*xp2)[@999@] = &x;   // reject
+float x[@n@];   $\C{// or just 42}$
+float (*xp1)[@42@] = &x;    $\C{// accept}$
+float (*xp2)[@999@] = &x;   $\C{// reject}$
 warning: initialization of 'float (*)[999]' from incompatible pointer type 'float (*)[42]'
 \end{cfa}
 When a variable is involved, C and \CFA take two different approaches.
 Today's C compilers accept the following without warning.
+Today's C compilers accept the following without a warning.
 \begin{cfa}
 static const int n = 42;
 …
 The way the \CFA array is implemented, the type analysis for this case reduces to a case similar to the earlier C version.
 The \CFA compiler's compatibility analysis proceeds as:
 \begin{itemize}[parsep=0pt]
+\begin{itemize}[leftmargin=*,parsep=0pt]
 \item
         Is @array( float, 999 )@ type-compatible with @array( float, n )@?
 …
         in order to preserve the length information that powers runtime bound-checking.}
 Therefore, the need to upgrade legacy C code is low.
 Finally, if this incompatibility is a problem onboarding C programs to \CFA, it is should be possible to change the C type check to a warning rather than an error, acting as a \emph{lint} of the original code for a missing type annotation.
+Finally, if this incompatibility is a problem onboarding C programs to \CFA, it should be possible to change the C type check to a warning rather than an error, acting as a \emph{lint} of the original code for a missing type annotation.
 To handle two occurrences of the same variable, more information is needed, \eg, this is fine,
 …
 int n = 42;
 float x[@n@];
 float (*xp)[@n@] = x;   // accept
+float (*xp)[@n@] = x;   $\C{// accept}$
 \end{cfa}
 where @n@ remains fixed across a contiguous declaration context.
 However, intervening dynamic statement cause failures.
+However, intervening dynamic statements can cause failures.
 \begin{cfa}
 int n = 42;
 float x[@n@];
 @n@ = 999; // dynamic change
 float (*xp)[@n@] = x;   // reject
 \end{cfa}
 However, side-effects can occur in a contiguous declaration context.
+@n@ = 999; $\C{// dynamic change}$
+float (*xp)[@n@] = x;   $\C{// reject}$
+\end{cfa}
+As well, side-effects can even occur in a contiguous declaration context.
 \begin{cquote}
 \setlength{\tabcolsep}{20pt}
 …
 void f() {
         float x[@n@] = { g() };
         float (*xp)[@n@] = x;   // reject
+        float (*xp)[@n@] = x;                   // reject
+}
 \end{cfa}
 …
 int @n@ = 42;
 void g() {
         @n@ = 99;
+        @n@ = 999;              // accept
+}
 …
 The issue here is that knowledge needed to make a correct decision is hidden by separate compilation.
 Even within a translation unit, static analysis might not be able to provide all the information.
 However, if the example uses @const@, the check is possible.
+However, if the example uses @const@, the check is possible even though the value is unknown.
 \begin{cquote}
 \setlength{\tabcolsep}{20pt}
 …
 void f() {
         float x[n] = { g() };
         float (*xp)[n] = x;   // reject
+        float (*xp)[n] = x;             // accept
+}
 \end{cfa}
 …
 @const@ int n = 42;
 void g() {
         @n = 99@; // allowed
+        @n = 999@;              // reject
+}
 …
 An expression-compatibility question is a new addition to the \CFA compiler, and occurs in the context of dimension expressions, and possibly enumerations assigns, which must be unique.
 % TODO: ensure these compiler implementation matters are treated under \CFA compiler background: type unification, cost calculation, GenPoly.
+% ... ensure these compiler implementation matters are treated under \CFA compiler background: type unification, cost calculation, GenPoly.
 The relevant technical component of the \CFA compiler is the standard type-unification within the type resolver.
 …
 \end{cfa}
 when resolving a function call to @g@, the first unification stage compares the type @T@ of the parameter with @array( float, n + 1 )@, of the argument.
-\PAB{TODO: finish.}
 The actual rules for comparing two dimension expressions are conservative.
 …
 is to imply, ``all else being equal, allow an array with length calculated by $e_1$
 to be passed to a function expecting a length-$e_2$ array.''\footnote{
         TODO: Deal with directionality, that I'm doing exact-match, no ``at least as long as,'' no subtyping.
+        ... Deal with directionality, that I'm doing exact-match, no ``at least as long as,'' no subtyping.
         Should it be an earlier scoping principle?  Feels like it should matter in more places than here.}
 So, a ``yes'' answer must represent a guarantee that both expressions evaluate the
 …
 So, a variable and a literal can never match.
 TODO: Discuss the interaction of this dimension hoisting with the challenge of extra unification for cost calculation
+... Discuss the interaction of this dimension hoisting with the challenge of extra unification for cost calculation
 \end{comment}
 The conservatism of the new rule set can leave a programmer needing a recourse, when needing to use a dimension expression whose stability argument is more subtle than current-state analysis.
+The conservatism of the new rule set can leave a programmer requiring a recourse, when needing to use a dimension expression whose stability argument is more subtle than current-state analysis.
 This recourse is to declare an explicit constant for the dimension value.
 Consider these two dimension expressions, whose uses are rejected by the blunt current-state rules:
 …
 void f( int @&@ nr, @const@ int nv ) {
         float x[@nr@];
         float (*xp)[@nr@] = &x;   // reject: nr varying (no references)
+        float (*xp)[@nr@] = &x;                 // reject: nr varying (no references)
         float y[@nv + 1@];
         float (*yp)[@nv + 1@] = &y;   // reject: ?+? unpredictable (no functions)
+        float (*yp)[@nv + 1@] = &y;             // reject: ?+? unpredictable (no functions)
+}
 \end{cfa}
 Yet, both dimension expressions are reused safely.
 The @nr@ reference is never written, not volatile meaning no implicit code (load) between declarations, and control does not leave the function between the uses.
+The @nr@ reference is never written, no implicit code (load) between declarations, and control does not leave the function between the uses.
 As well, the build-in @?+?@ function is predictable.
 To make these cases work, the programmer must add the follow constant declarations (cast does not work):
 …
         @const int nx@ = nr;
         float x[nx];
         float (*xp)[nx] = & x;   // accept
+        float (*xp)[nx] = & x;                  // accept
         @const int ny@ = nv + 1;
         float y[ny];
         float (*yp)[ny] = & y;   // accept
+        float (*yp)[ny] = & y;                  // accept
+}
 \end{cfa}
 …
 \end{cfa}
 Dimension hoisting already existed in the \CFA compiler.
 But its was buggy, particularly with determining, ``Can hoisting the expression be skipped here?'', for skipping this hoisting is clearly desirable in some cases.
+However, it was buggy, particularly with determining, ``Can hoisting the expression be skipped here?'', for skipping this hoisting is clearly desirable in some cases.
 For example, when a programmer has already hoisted to perform an optimization to prelude duplicate code (expression) and/or expression evaluation.
 In the new implementation, these cases are correct, harmonized with the accept/reject criteria.
 …
 \item
 Flexible-stride memory:
 this model has complete independence between subscripting ordering and memory layout, offering the ability to slice by (provide an index for) any dimension, \eg slice a plane, row, or column, \eg @c[3][*][*]@, @c[3][4][*]@, @c[3][*][5]@.
+this model has complete independence between subscript ordering and memory layout, offering the ability to slice by (provide an index for) any dimension, \eg slice a row, column, or plane, \eg @c[3][4][*]@, @c[3][*][5]@, @c[3][*][*]@.
 \item
 Fixed-stride memory:
 …
 Style 3 is the inevitable target of any array implementation.
 The hardware offers this model to the C compiler, with bytes as the unit of displacement.
 C offers this model to its programmer as pointer arithmetic, with arbitrary sizes as the unit.
+C offers this model to programmers as pointer arithmetic, with arbitrary sizes as the unit.
 Casting a multidimensional array as a single-dimensional array/pointer, then using @x[i]@ syntax to access its elements, is still a form of pointer arithmetic.
+Now stepping into the implementation of \CFA's new type-1 multidimensional arrays in terms of C's existing type-2 multidimensional arrays, it helps to clarify that even the interface is quite low-level.
+A C/\CFA array interface includes the resulting memory layout.
+The defining requirement of a type-2 system is the ability to slice a column from a column-finest matrix.
+The required memory shape of such a slice is fixed, before any discussion of implementation.
+The implementation presented here is how the \CFA array-library wrangles the C type system, to make it do memory steps that are consistent with this layout while not affecting legacy C programs.
+To step into the implementation of \CFA's new type-1 multidimensional arrays in terms of C's existing type-2 multidimensional arrays, it helps to clarify that the interface is low-level, \ie a C/\CFA array interface includes the resulting memory layout.
+Specifically, the defining requirement of a type-2 system is the ability to slice a column from a column-finest matrix.
+Hence, the required memory shape of such a slice is fixed, before any discussion of implementation.
+The implementation presented here is how the \CFA array-library wrangles the C type system to make it do memory steps that are consistent with this layout while not affecting legacy C programs.
 % TODO: do I have/need a presentation of just this layout, just the semantics of -[all]?
 …
 \lstinput[aboveskip=0pt]{145-145}{hello-md.cfa}
 The nontrivial slicing in this example now allows passing a \emph{noncontiguous} slice to @print1d@, where 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 a placeholder, \ie ``not yet subscripted by a value'', waiting for such a value, implementing the @ar@ trait.
+In a multi-dimensional subscript operation, any dimension given as @all@ is a placeholder, \ie ``not yet subscripted by a value'', waiting for a value implementing the @ar@ trait.
 \lstinput{150-151}{hello-md.cfa}
 …
 A column is almost ready to be arranged into a matrix;
 it is the \emph{contained value} of the next-level building block, but another lie about size is required.
 At first, an atom needs to be arranged as if it were bigger, but now a column needs to be arranged as if it is smaller (the left diagonal above it, shrinking upward).
+At first, an atom needs to be arranged as if it is bigger, but now a column needs to be arranged as if it is smaller (the left diagonal above it, shrinking upward).
 These lying columns, arranged contiguously according to their size (as announced) form the matrix @x[all]@.
 Because @x[all]@ takes indices, first for the fine stride, then for the coarse stride, it achieves the requirement of representing the transpose of @x@.
 …
+\section{Bound Checks, Added and Removed}
+\section{Zero Overhead}
+At runtime, the \CFA array is exactly a C array.
 \CFA array subscripting is protected with runtime bound checks.
+The array dependent-typing provides information to the C optimizer allowing it remove many of the bound checks.
+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 \CC 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 \CC version to keep access to generated assembly code simple.
+The array dependent-typing provides information to the C optimizer, allowing it remove many of the bound checks.
+This section provides a demonstration of these effects.
+The experiment compares the \CFA array system with the simple-safety system most typically exemplified by Java arrays (\VRef[Section]{JavaCompare}), but also reflected in the \CC pattern where restricted vector usage models a checked array (\VRef[Section]{CppCompare}).
+The essential feature of this simple system is the one-to-one correspondence between array instances and the symbolic bounds on which dynamic checks are based.
+The experiment uses the \CC version to simplify access to generated assembly code.
+While ``\CC'' labels a participant, it is really the simple-safety system (of @vector@ with @.at@) whose limitations are being explained, and not limitations of \CC optimization.
 As a control case, a simple loop (with no reused dimension sizes) is seen to get the same optimization treatment in both the \CFA and \CC versions.
+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.
+TODO: paste source codes
+Firstly, when the programmer treats the array's bound correctly (making the subscript ``obviously fine''), no dynamic bound check is observed in the program's optimized assembly code.
+But when the bounds are adjusted, such that the subscript is possibly invalid, the bound check appears in the optimized assembly, ready to catch a mistake.
+\VRef[Figure]{f:ovhd-ctl} gives a control-case example of summing values in an array, where each column shows the program in languages C (a,~d,~g), \CFA (b,~e,~h), and \CC (c,~f,~i).
+The C code has no bounds checking, while the \CFA and \CC can have bounds checking.
+The source-code functions in (a, b, c) can be compiled to have either correct or incorrect uses of bounds.
+When compiling for correct bound use, the @BND@ macro passes its argument through, so the loops cover exactly the passed array sizes.
+When compiling for possible incorrect bound use (a programming error), the @BND@ macro hardcodes the loops for 100 iterations, which implies out-of-bound access attempts when the passed array has fewer than 100 elements.
+The assembly code excerpts show optimized translations for correct-bound mode in (d, e, f) and incorrect-bound mode in (g, h, i).
+Because incorrect-bound mode hardcodes 100 iterations, the loop always executes a first time, so this mode does not have the @n == 0@ branch seen in correct-bound mode.
+For C, this difference is the only (d--g) difference.
+For correct bounds, the \CFA translation equals the C translation, \ie~there is no (d--e) difference, while \CC has an additional indirection to dereference the vector's auxiliary allocation.
+\begin{figure}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{llll@{}}
+\multicolumn{1}{c}{C} &
+\multicolumn{1}{c}{\CFA} &
+\multicolumn{1}{c}{\CC (nested vector)}
+\\[1em]
+\lstinput{20-28}{ar-bchk/control.c} &
+\lstinput{20-28}{ar-bchk/control.cfa} &
+\lstinput{20-28}{ar-bchk/control.cc}
+\\
+\multicolumn{1}{c}{(a)} &
+\multicolumn{1}{c}{(b)} &
+\multicolumn{1}{c}{(c)}
+\\[1em]
+\multicolumn{4}{l}{
+        \includegraphics[page=1,trim=0 9.125in 2in 0,clip]{ar-bchk}
+}
+\\
+\multicolumn{1}{c}{(d)} &
+\multicolumn{1}{c}{(e)} &
+\multicolumn{1}{c}{(f)}
+\\[1em]
+\multicolumn{4}{l}{
+        \includegraphics[page=2,trim=0 8.75in 2in 0,clip]{ar-bchk}
+}
+\\
+\multicolumn{1}{c}{(g)} &
+\multicolumn{1}{c}{(h)} &
+\multicolumn{1}{c}{(i)}
+\end{tabular}
+\caption{Overhead comparison, control case.
+All three programs/compilers generate equally performant code when the programmer ``self-checks'' bounds via a loop's condition.
+Yet both \CFA and \CC versions generate code that is slower and safer than C's when the programmer might overrun the bounds.}
+\label{f:ovhd-ctl}
+\end{figure}
+Differences arise when the bound-incorrect programs are passed an array shorter than 100.
+The C version, (g), proceeds with undefined behaviour, reading past the end of the array.
+The \CFA and \CC versions, (h, i), flag the mistake with the runtime check, the @i >= n@ branch.
+This check is provided implicitly by the library types @array@ and @vector@, respectively.
+The significant result is the \emph{absence} of runtime checks from the bound-correct translations, (e, f).
+The code optimizer has removed them because, at the point where they would occur (immediately past @.L28@/@.L3@), it knows from the surrounding control flow either @i == 0 && 0 < n@ or @i < n@ (directly), \ie @i < n@ either way.
+So any repeated checks, \ie the branch and its consequent code (raise error), are removable.
+% Progressing from the control case, a deliberately bound-incorrect mode is no longer informative.
+% Rather, given a (well-typed) program that does good work on good data, the issue is whether it is (determinably) bound-correct on all data.
+When dimension sizes get reused, \CFA has an advantage over \CC-vector at getting simply written programs well optimized.
+The example case of \VRef[Figures]{f:ovhd-treat-src} and \VRef[]{f:ovhd-treat-asm} is a simple matrix multiplication over a row-major encoding.
+Simple means coding directly to the intuition of the mathematical definition without trying to optimize for memory layout.
+In the assembly code of \VRef[Figure]{f:ovhd-treat-asm}, the looping pattern of \VRef[Figure]{f:ovhd-ctl} (d, e, f), ``Skip ahead on zero; loop back for next,'' occurs with three nesting levels.
+Simultaneously, the dynamic bound-check pattern of \VRef[Figure]{f:ovhd-ctl} (h,~i), ``Get out on invalid,'' occurs, targeting @.L7@, @.L9@ and @.L8@ (bottom right).
+Here, \VRef[Figures]{f:ovhd-treat-asm} shows the \CFA solution optimizing into practically the C solution, while the \CC solution shows added runtime bound checks.
+Like in \VRef[Figure]{f:ovhd-ctl} (e), the significance is the \emph{absence} of library-imposed runtime checks, even though the source code is working through the the \CFA @array@ library.
+The optimizer removed the library-imposed checks because the data structure @array@-of-@array@ is constrained by its type to be shaped correctly for the intuitive looping.
+In \CC, the same constraint does not apply to @vector@-of-@vector@.
+Because every individual @vector@ carries its own size, two types of bound mistakes are possible.
+\begin{figure}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{llll@{}}
+\multicolumn{1}{c}{C} &
+\multicolumn{1}{c}{\CFA} &
+\multicolumn{1}{c}{\CC (nested vector)}
+\\
+\lstinput{20-37}{ar-bchk/treatment.c} &
+\lstinput{20-37}{ar-bchk/treatment.cfa} &
+\lstinput{20-37}{ar-bchk/treatment.cc}
+\end{tabular}
+\caption{Overhead comparison, differentiation case, source.}
+\label{f:ovhd-treat-src}
+\end{figure}
+\begin{figure}
+\newcolumntype{C}[1]{>{\centering\arraybackslash}p{#1}}
+\begin{tabular}{C{1.5in}C{1.5in}C{1.5in}p{1in}}
+C &
+\CFA &
+\CC (nested vector)
+\\[1em]
+\multicolumn{4}{l}{
+        \includegraphics[page=3,trim=0 4in 2in 0,clip]{ar-bchk}
+}
+\end{tabular}
+\caption{Overhead comparison, differentiation case, assembly.
+}
+\label{f:ovhd-treat-asm}
+\end{figure}
+In detail, the three structures received may not be matrices at all, per the obvious/dense/total interpretation; rather, any one might be ragged-right in its rows.
+The \CFA solution guards against this possibility by encoding the minor length (number of columns) in the major element (row) type.
+In @res@, for example, each of the @M@ rows is @array(float, N)@, guaranteeing @N@ cells within it.
+Or more technically, guaranteeing @N@ as the basis for the imposed bound check \emph{of every row.}
+As well, the \CC type does not impose the mathematically familiar constraint of $(M \times P) (P \times N) \rightarrow (M \times N)$.
+Even assuming away the first issue, \eg that in @lhs@, all minor/cell counts agree, the data format allows the @rhs@ major/row count to disagree.
+Or, the possibility that the row count @res.size()@ disagrees with the row count @lhs.size()@ illustrates this bound-mistake type in isolation.
+The \CFA solution guards against this possibility by keeping length information separate from the array data, and therefore eligible for sharing.
+This capability lets \CFA escape the one-to-one correspondence between array instances and symbolic bounds, where this correspondence leaves a \CC-vector programmer stuck with a matrix representation that repeats itself.
+It is important to clarify that the \CFA solution does not become unsafe (like C) in losing its dynamic checks, even though it becomes fast (as C) in losing them.
+The dynamic checks are dismissed as unnecessary \emph{because} the program is safe to begin with.
+To achieve the same performance, a \CC programmer must state appropriate assertions or assumptions, to allow the optimizer to dismiss the runtime checks.
+% Especially considering that two of them are in the inner-most loop.
+The solution requires doing the work of the inner-loop checks as a \emph{preflight step}.
+But this step requires looping and doing it upfront gives too much separation for the optimizer to see ``has been checked already'' in the deep loop.
+So, the programmer must restate the preflight observation within the deep loop, but this time as an unchecked assumption.
+Such assumptions are risky because they introduce further undefined behaviour when misused.
+Only the programmer's discipline remains to ensure this work is done without error.
+In summary, the \CFA solution lets a simply stated program have dynamic guards that catch bugs, while letting a simply stated bug-free program run as fast as the unguarded C equivalent.
+\begin{comment}
+The ragged-right issue brings with it a source-of-truth difficulty: Where, in the \CC version, is one to find the value of $N$?  $M$ can come from either @res@'s or @lhs@'s major/row count, and checking these for equality is straightforward.  $P$ can come from @rhs@'s major/row count.  But $N$ is only available from columns, \ie minor/cell counts, which are ragged.  So any choice of initial source of truth, \eg
+\end{comment}
 …
 However, it only needs @float@'s default constructor, as the other operations are never used.
 Current work by the \CFA team aims to improve this situation.
-Therefore, I had to construct a workaround.
 My workaround moves from otype (value) to dtype (pointer) with a default-constructor assertion, where dtype does not generate any constructors but the assertion claws back the default otype constructor.
 \begin{cquote}
 …
 \subsection{Java}
+\label{JavaCompare}
 Java arrays are references, so multi-dimension arrays are arrays-of-arrays \see{\VRef{toc:mdimpl}}.
 …
 \subsection{\CC}
+\label{CppCompare}
 Because C arrays are difficult and dangerous, the mantra for \CC programmers is to use @std::vector@ in place of the C array.
+While the vector size can grow and shrink dynamically, \vs a fixed-size dynamic size with VLAs, the cost of this extra feature is mitigated by preallocating the maximum size (like the VLA) at the declaration (one dynamic call) to avoid using @push_back@.
+While the vector size can grow and shrink dynamically, \vs an unchanging dynamic size with VLAs, the cost of this extra feature is mitigated by preallocating the maximum size (like the VLA) at the declaration.
+So, it costs one upfront dynamic allocation and avoids growing the array through pushing.
 \begin{c++}
 vector< vector< int > > m( 5, vector<int>(8) ); // initialize size of 5 x 8 with 6 dynamic allocations
 \end{c++}
 Multidimensional arrays are arrays-of-arrays with associated costs.
+Each @vector@ array has an array descriptor contain the dimension, which allows bound checked using @x.at(i)@ in place of @x[i]@.
+Used with these restrictions, out-of-bound accesses are caught, and in-bound accesses never exercise the vector's ability to grow, preventing costly reallocate and copy, and never invalidate references to contained values.
+This scheme matches Java's safety and expressiveness exactly, but with the inherent costs.
+Each @vector@ array has an array descriptor containing the dimension, which allows bound checked using @x.at(i)@ in place of @x[i]@.
+Used with these restrictions, out-of-bound accesses are caught, and in-bound accesses never exercise the vector's ability to grow, preventing costly reallocate-and-copy, and never invalidating references to contained values.
+This scheme matches a Java array's safety and expressiveness exactly, with the same inherent costs.
+Notably, a \CC vector of vectors does not provide contiguous element storage (even when upfront allocation is done carefully) because a vector puts its elements in an auxiliary allocation.
+So, in spite of @vector< vector< int > >@ appearing to be ``everything by value,'' it is still a first array whose elements include pointers to further arrays.
+\CC has options for working with memory-adjacent data in desirable ways, particularly in recent revisions.
+But none makes an allocation with a dynamically given fixed size less awkward than the vector arrangement just described.
+\CC~26 adds @std::inplace_vector@, which provides an interesting vector--array hybrid,\footnote{
+  Like a vector, it lets a user construct elements in a loop, rather than imposing uniform construction.
+  Yet it preserves \lstinline{std::array}'s ability to be entirely stack-allocated, by avoiding an auxiliary elements' allocation.
+} but does not change the fundamental limit of \lstinline{std::array}, that the length, being a template parameter, must be a static value.
+\CC~20's @std::span@ is a view that unifies true arrays, vectors, static sizes and dynamic sizes, under a common API that adds bounds checking.
+When wrapping a vector, bounds checking occurs on regular subscripting, \ie one need not remember to use @.at@.
+When wrapping a locally declared fixed-size array, bound communication is implicit.
+But it has a soundness gap by offering construction from pointer and user-given length.
+\CC~23's @std::mdspan@ adds multidimensional indexing and reshaping capabilities analogous to those built into \CFA's @array@.
+Like @span@, it works over multiple underlying container types.
+But neither @span@ nor @mdspan@ augments the available allocation options.
+Thus, these options do not offer an allocation with a dynamically given fixed size.
+And furthermore, they do not provide any improvement to the C flexible array member pattern, for making a dynamic amount of storage contiguous with its header, as do \CFA's accordions.
+\begin{comment}
 \subsection{Levels of Dependently Typed Arrays}
+TODO: fix the position; checked c does not do linear types
 \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, which further helps guarantee statically the validity of every pointer deference.
 …
 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 novel contributions concerning similar, restricted dependent types for tracking array length.
+Two contemporary array-centric languages, Dex\cite{arr:dex:long} and Futhark\cite{arr:futhark:tytheory}, contribute 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.
 …
 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.
+Dex uses an Ada-style conception of size, embedding quantitative information completely into an ordinary type.
+Futhark and full-strength dependently typed languages treat array sizes as 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.
+\CFA's hybrid presentation, @forall( [N] )@, has @N@ belonging to the type system, yet no objects of type @[N]@ occur.
 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.
 …
 In Ada and Dex, an array is conceived as a function whose domain must satisfy only certain structural assumptions, while in C, \CC, 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.
+The Ada--Dex generality has aesthetic benefits for certain programmers.  For those working on scheduling resources to weekdays:
+For those who prefer to count from an initial number of their own choosing:
 This change of perspective also lets us remove ubiquitous dynamic bound checks.
 …
 (unsafe_from_ordinal a (idiv o bs), unsafe_from_ordinal b (rem o bs))
 \end{cfa}
+% fix mike's syntax highlighter
 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{cfa}
 …
 \subsection{Static Safety in C Extensions}
+\end{comment}
 \section{Future Work}
 \subsection{Array Syntax}
 An important goal is to recast @array(...)@ syntax into C-style @[]@.
 The proposal (which is partially implemented) is an alternate dimension and subscript syntax.
 C multi-dimension and subscripting syntax uses multiple brackets.
 \begin{cfa}
 int m@[2][3]@;  // dimension
 m@[0][1]@ = 3;  // subscript
 \end{cfa}
+Leveraging this syntax, the following (simpler) syntax should be intuitive to C programmers with only a small backwards compatibility issue.
 \begin{cfa}
 int m@[2, 3]@;  // dimension
 m@[0, 1]@ = 3;  // subscript
 \end{cfa}
 However, the new subscript syntax is not backwards compatible, as @0, 1@ is a comma expression.
 Interestingly, disallowed the comma expression in this context eliminates an unreported error: subscripting a matrix with @m[i, j]@ instead of @m[i][j]@, which selects the @j@th row not the @i, j@ element.
+Hence, a comma expression in this context is rare.
+Finally, it is possible to write @m[(i, j)]@ in the new syntax to achieve the equivalent of the old @m[i, j]@.
+Note, the new subscript syntax can easily be internally lowered to @[-][-]...@ and handled as regular subscripting.
+The only ambiguity with C syntax is for a single dimension array, where the syntax for old and new are the same.
+\begin{cfa}
+int m[2@,@];  // single dimension
+m[0] = 3;  // subscript
+\end{cfa}
+The solution for the dimension is to use a terminating comma to denote a new single-dimension array.
 This syntactic form is also used for the (rare) singleton tuple @[y@{\color{red},}@]@.
+% \subsection{Array Syntax}
+An important goal is to recast \CFA-style @array(...)@ syntax into C-style array syntax.
+The proposal (which is partially implemented) is an alternate dimension and subscript syntax for multi-dimension arrays.
+C multi-dimension and subscripting syntax uses multiple bracketed constants/expressions.
+\begin{cfa}
+int m@[2][3]@;   // dimension
+m@[0][1]@ = 3;   // subscript
+\end{cfa}
+The alternative \CFA syntax is a comma separated list:
+\begin{cfa}
+int m@[2, 3]@;   // dimension
+m@[0, 1]@ = 3;   // subscript
+\end{cfa}
+which should be intuitive to C programmers and is used in mathematics $M_{i,j}$ and other programing languages, \eg PL/I, Fortran.
+With respect to the dimension expressions, C only allows an assignment expression, not a comma expression.
+\begin{cfa}
+        a[i, j];
+test.c:3:16: error: expected ']' before ',' token
+\end{cfa}
+However, there is an ambiguity for a single dimension array, where the syntax for old and new arrays are the same, @int ar[10]@.
+The solution is to use a terminating comma to denote a \CFA-style single-dimension array.
+\begin{cfa}
+int ar[2$\Huge\color{red},$];  // single dimension new array
+\end{cfa}
+This syntactic form is also used for the (rare) singleton tuple @[y@{\Large\color{red},}@]@.
 The extra comma in the dimension is only mildly annoying, and acts as eye-candy differentiating old and new arrays.
+The subscript operator is not an issue as overloading selects the correct single-dimension operation for old/new array types.
+The ultimately goal is to replace all C arrays with \CFA arrays, establishing a higher level of safety in C programs, and eliminating the need for the terminating comma.
+Hence, \CFA can repurpose the comma expression in this context for a list of dimensions.
+The ultimate goal is to replace all C arrays with \CFA arrays, establishing a higher level of safety in C programs, and eliminating the need for the terminating comma.
+With respect to the subscript expression, the comma expression is allowed.
+However, a comma expression in this context is rare, and is most commonly a (silent) mistake: subscripting a matrix with @m[i, j]@ instead of @m[i][j]@ selects the @j@th row not the @i, j@ element.
+It is still possible to write @m[(i, j)]@ in the new syntax to achieve the equivalent of the old @m[i, j]@.
+Internally, the compiler must de-sugar @[i, j, k]@ into @[i][j][k]@ to match with three calls to subscript operators.
+Note, there is no ambiguity for subscripting a single dimensional array, as the subscript operator selects the correct form from the array type.
+Currently, @array@ supports the old and new subscript syntax \see{\VRef[Figure]{f:ovhd-treat-src}}, including combinations of new and old, @arr[1, 2][3]@.
+The new subscript syntax can be extended to C arrays for uniformity, but requires the non-compatible removal of the (rare) comma-expression as a subscript.
+\begin{comment}
 \subsection{Range Slicing}
 …
-\begin{comment}
 \section{\texorpdfstring{\CFA}{Cforall}}
 …
 Using a compiler-produced value eliminates an opportunity for user error.
 TODO: fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa
+...someday... fix in following: even the alloc call gives bad code gen: verify it was always this way; walk back the wording about things just working here; assignment (rebind) seems to offer workaround, as in bkgd-cfa-arrayinteract.cfa
 Bringing in another \CFA feature, reference types, both resolves a sore spot of the last example, and gives a first example of an array-interaction bug.
 …
 (*ar2)[5];
 \end{cfa}
 Using ``reference to array'' works at resolving this issue.  TODO: discuss connection with Doug-Lea \CC proposal.
+Using ``reference to array'' works at resolving this issue.  ...someday... discuss connection with Doug-Lea \CC proposal.
 \begin{cfa}
 tm (&ar3)[10] = *alloc();
 …
 Using proper array types (@ar2@ and @ar3@) addresses a concern about using raw element pointers (@ar1@), albeit a theoretical one.
 TODO xref C standard does not claim that @ar1@ may be subscripted,
+...someday...  xref C standard does not claim that @ar1@ may be subscripted,
 because no stage of interpreting the construction of @ar1@ has it be that ``there is an \emph{array object} here.''
 But both @*ar2@ and the referent of @ar3@ are the results of \emph{typed} @alloc@ calls,
 …
 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?
+...someday...  see also @dimexpr-match-c/REFPARAM_CALL@ (under @TRY_BUG_1@)
+...someday... I fixed a bug associated with using an array as a T.  I think.  Did I really?  What was the bug?
 \end{comment}

doc/theses/mike_brooks_MMath/background.tex

-              r79ba50c
+              r8614140
     void f( int n, float[][n]  );   $\C{// array of VLAs}$
 \end{cfa}
 as a repeat, without an error about conflicting types for @f@.
 Yet, entirely different stride calculations would occur in a function body whose parameters were declared in each of the two styles.
+without an error about conflicting types for @f@.
+Yet, entirely different stride calculations occur in the function body for each of the two parameter styles.
 \begin{figure}
 …
 \subsection{Arrays Could be Values}
+\label{s:ArraysCouldbeValues}
 All arrays have a know runtime size at their point of declaration.

doc/theses/mike_brooks_MMath/plots/list-zoomout-noshuf.gp

-              r79ba50c
+              r8614140
 set key top left
 set logscale x
 set logscale y
 set yrange [1:1000];
+#set logscale y
+#set yrange [1:1000];
 set xlabel "List length (item count)" offset 2,0
 set ylabel "Duration (ns)"

doc/theses/mike_brooks_MMath/plots/list-zoomout-shuf.gp

-              r79ba50c
+              r8614140
 set logscale x
 set logscale y
 set yrange [1:1000];
+#set yrange [1:1000];
 set xlabel "List length (item count)" offset 2,0
 set ylabel "Duration (ns)"
+set ylabel "Duration (ns), log scale"
 set linetype 3 dashtype 2
 set linetype 4 dashtype 2

doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp

-              r79ba50c
+              r8614140
 set terminal pdf color enhanced size 6.0in,3.0in font "Times,17"
+set terminal pdf color enhanced size 6.5in,3.5in font "Times,17"
 #set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5;
 #set terminal wxt size 950,1250
 …
 set grid
 set key top left
+set xrange [1:500]
 set xtics (1,2,5,10,20,50,100,200,500)
 set logscale x
 …
 set linetype 4 dashtype 2
 plot INDIR."/plot-string-peq-cppemu.dat" \
+           i 0 using 1:2 title columnheader(1)  with points lt rgb "red"  pt  2  ps 1, \
+        '' i 1 using 1:2 title columnheader(1)  with points lt rgb "red"  pt  1  ps 1, \
+        '' i 2 using 1:2 title columnheader(1)  with points lt rgb "blue" pt  6  ps 1, \
+        '' i 3  using 1:2 title columnheader(1) with points lt rgb "blue" pt  8  ps 1
+           i 0 using 1:2 title columnheader(1)  with points lt rgb "red" pt 2  ps 1, \
+        '' i 0 using 1:2 notitle smooth sbezier lt rgb "red" dashtype 1, \
+        '' i 1 using 1:2 title columnheader(1)  with points lt rgb "red" pt 1  ps 1, \
+        '' i 1 using 1:2 notitle smooth sbezier lt rgb "red" dashtype 4, \
+        '' i 2 using 1:2 title columnheader(1)  with points lt rgb "blue" pt 6  ps 1, \
+        '' i 2 using 1:2 notitle smooth sbezier lt rgb "blue" dashtype 1, \
+        '' i 3 using 1:2 title columnheader(1) with points lt rgb "blue" pt 8  ps 1, \
+        '' i 3 using 1:2 notitle smooth sbezier lt rgb "blue" dashtype 4 \

doc/theses/mike_brooks_MMath/plots/string-peq-sharing.gp

-              r79ba50c
+              r8614140
 set terminal pdf color enhanced size 6.0in,3.0in font "Times,17"
+set terminal pdf color enhanced size 6.5in,3.5in font "Times,17"
 #set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5;
 #set terminal wxt size 950,1250
 …
 set grid
 set key top left
+set xrange [1:500]
 set xtics (1,2,5,10,20,50,100,200,500)
 set logscale x
 …
 set linetype 4 dashtype 2
 plot INDIR."/plot-string-peq-sharing.dat" \
+           i 0 using 1:2 title columnheader(1) with points lt rgb "red"  pt  2  ps 1, \
+        '' i 1 using 1:2 title columnheader(1) with points lt rgb "red"  pt  1  ps 1, \
+        '' i 2 using 1:2 title columnheader(1) with points lt rgb "blue" pt  6  ps 1, \
+        '' i 3 using 1:2 title columnheader(1) with points lt rgb "blue" pt  8  ps 1
+           i 0 using 1:2 title columnheader(1)  with points lt rgb "red" pt 2  ps 1, \
+        '' i 0 using 1:2 notitle smooth sbezier lt rgb "red" dashtype 1, \
+        '' i 1 using 1:2 title columnheader(1)  with points lt rgb "red" pt 1  ps 1, \
+        '' i 1 using 1:2 notitle smooth sbezier lt rgb "red" dashtype 4, \
+        '' i 2 using 1:2 title columnheader(1)  with points lt rgb "blue" pt 6  ps 1, \
+        '' i 2 using 1:2 notitle smooth sbezier lt rgb "blue" dashtype 1, \
+        '' i 3 using 1:2 title columnheader(1) with points lt rgb "blue" pt 8  ps 1, \
+        '' i 3 using 1:2 notitle smooth sbezier lt rgb "blue" dashtype 4 \

doc/theses/mike_brooks_MMath/plots/string-pta-sharing.gp

-              r79ba50c
+              r8614140
 set terminal pdf color enhanced size 6.0in,3.0in font "Times,17"
+set terminal pdf color enhanced size 6.5in,3.5in font "Times,17"
 #set terminal postscript portrait enhanced size 7.5, 10. color solid 9.5;
 #set terminal wxt size 950,1250
 …
 set grid
 set key top left
+set xrange [1:500]
 set xtics (1,2,5,10,20,50,100,200,500)
 set logscale x
 …
 set xlabel "String Length being appended (mean, geo. dist.), log scale" offset 2,0
 set ylabel "Time per append (ns, mean), log_{2} scale"
-#show colornames
 plot INDIR."/plot-string-pta-sharing.dat" \
+           i 0 using 1:2 title columnheader(1) with points lt rgb "red"        pt  2   ps 1, \
+        '' i 1 using 1:2 title columnheader(1) with points lt rgb "dark-green" pt  4   ps 1, \
+        '' i 2 using 1:2 title columnheader(1) with points lt rgb "blue"       pt  6   ps 1, \
+        '' i 3 using 1:2 title columnheader(1) with points lt rgb "dark-green" pt  12  ps 1
+           i 0 using 1:2 title columnheader(1)  with points lt rgb "red" pt 2  ps 1, \
+        '' i 0 using 1:2 notitle smooth sbezier lt rgb "red" dashtype 1, \
+        '' i 1 using 1:2 title columnheader(1)  with points lt rgb "dark-green" pt 4  ps 1, \
+        '' i 1 using 1:2 notitle smooth sbezier lt rgb "dark-green" dashtype 4, \
+        '' i 2 using 1:2 title columnheader(1)  with points lt rgb "blue" pt 6  ps 1, \
+        '' i 2 using 1:2 notitle smooth sbezier lt rgb "blue" dashtype 1, \
+        '' i 3 using 1:2 title columnheader(1) with points lt rgb "dark-green" pt 12  ps 1, \
+        '' i 3 using 1:2 notitle smooth sbezier lt rgb "dark-green" dashtype 4 \

doc/theses/mike_brooks_MMath/programs/hello-accordion.cfa

-              r79ba50c
+              r8614140
 int getPref( @School( C, S ) & school@, int is, int pref ) {
         for ( ic; C ) {
                 if ( pref == @school.preferences@[ic][is]; ) return ic; $\C{// offset calculation implicit}$
+                if ( pref == @school.preferences@[ic][is] ) return ic; $\C{// offset calculation implicit}$
+        }
         assert( false );
+        assert( false );        // must find a match
+}
 …
         for ( is; ns ) {
                 sout | school.student_ids[is] | ": " | nonl;
+                sout | school.student_ids[is] | ": ";
                 for ( pref; 1 ~= nc ) {
                         int ic = getPref( school, is, pref );

doc/theses/mike_brooks_MMath/programs/hello-array.cfa

-              r79ba50c
+              r8614140
 forall( [M], [N] )
+void bad( array(float, M) &x,
+                array(float, N) &y ) {
+void f( array(float, M) &x, array(float, N) &y ) {
         f( x, x );              $\C[0.5in]{// ok}$
         f( y, y );              $\C{// ok}$
         f( x, y );              $\C{// error}\CRT$
+        if ( M == N ) f( x, @(array( float, M ) &)@y ); $\C{// ok}\CRT$
+}
 #endif
 …
 forall( [M], [N] )
+void bad_fixed( array( float, M ) & x,
+                array( float, N ) & y ) {
+void f( array( float, M ) & x, array( float, N ) & y ) {
         f( x, x );              $\C[0.5in]{// ok}$
         f( y, y );              $\C{// ok}$
+        if ( M == N )
+                f( x, @(array( float, M ) &)@y ); $\C{// ok}\CRT$
+        if ( M == N ) f( x, @(array( float, M ) &)@y ); $\C{// ok}\CRT$
+}
 …
 forall( [M], [N] )
+void bad_ok_only( array(float, M) &x,
+                array(float, N) &y ) {
+void bad_ok_only( array(float, M) &x, array(float, N) &y ) {
         f( x, x );
         f( y, y );

doc/theses/mike_brooks_MMath/programs/school1

-              r79ba50c
+              r8614140
 courses, 2 students
 c\s     90111111 90222222
 ENGL101        3        2
 PHYS101        1        3
 CHEM101        2        1
+c\s              90111111 90222222
+ENGL101                 3               2
+PHYS101                 1               3
+CHEM101                2               1

doc/theses/mike_brooks_MMath/programs/school1.out

r79ba50c	r8614140
1		90111111: PHYS101 CHEM101 ENGL101
2		90222222: CHEM101 ENGL101 PHYS101
	1	90111111:
	2	PHYS101 CHEM101 ENGL101
	3	90222222:
	4	CHEM101 ENGL101 PHYS101

doc/theses/mike_brooks_MMath/programs/school2

-              r79ba50c
+              r8614140
 courses, 3 students
 c\s     90111111 90222222 90333333
 ENGL101        3        2        3
 PHYS101        1        3        4
 CHEM101        2        1        5
 PHIL101        4        5        2
 MATH499        5        4        1
+c\s              90111111 90222222 90333333
+ENGL101                 3               2               3
+PHYS101                 1               3               4
+CHEM101                2               1               5
+PHIL101                   4               5               2
+MATH499                 5               4               1

doc/theses/mike_brooks_MMath/programs/school2.out

-              r79ba50c
+              r8614140
+90111111: PHYS101 CHEM101 ENGL101 PHIL101 MATH499
+90222222: CHEM101 ENGL101 PHYS101 MATH499 PHIL101
+90333333: MATH499 PHIL101 ENGL101 PHYS101 CHEM101
+90111111:
+PHYS101 CHEM101 ENGL101 PHIL101 MATH499
+90222222:
+CHEM101 ENGL101 PHYS101 MATH499 PHIL101
+90333333:
+MATH499 PHIL101 ENGL101 PHYS101 CHEM101

doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa

r79ba50c	r8614140
300	300	open( outfile, "build/sharing10.tex" );
301	301	outfile \| "\\begin{cquote}";
	302	outfile \| "\\setlength{\\tabcolsep}{10pt}";
302	303	outfile \| "\\begin{tabular}{@{}rlllll@{}}";
303	304	outfile \| "\t\t\t\t& @s1@\t& @s1_bgn@\t& @s1_crs@\t& @s1_mid@\t& @s1_end@\t\\\\";

doc/theses/mike_brooks_MMath/string.tex

-              r79ba50c
+              r8614140
 \begin{cquote}
 \begin{tabular}{@{}l|l|l|l@{}}
 C @char [ ]@                    &  \CC @string@                 & Java @String@ & \CFA @string@ \\
+C @char [ ]@                    & \CC @string@                  & Java @String@ & \CFA @string@ \\
 \hline
 @strcpy@, @strncpy@             & @=@                                   & @=@                   & @=@   \\
 …
 As a result, a @string@ declaration does not specify a maximum length, where a C string array does.
 For \CFA, as a @string@ dynamically grows and shrinks in size, so does its underlying storage.
 For C, as a string dynamically grows and shrinks in size, but its underlying storage does not.
+For C, as a string dynamically grows and shrinks in size, its underlying storage does not.
 The maximum storage for a \CFA @string@ value is @size_t@ characters, which is $2^{32}$ or $2^{64}$ respectively.
 A \CFA string manages its length separately from the string, so there is no null (@'\0'@) terminating value at the end of a string value.
 …
 Hence, the basic types @char@, @char *@, @int@, @double@, @_Complex@, including any signness and size variations, implicitly convert to type @string@ (as in Java).
 \begin{cquote}
+\begin{tabular}{@{}l|ll|l@{}}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{@{}llll@{}}
 \begin{cfa}
 string s = 5;
 …
 Conversions can be explicitly specified using a compound literal.
 \begin{cfa}
 s = (string){ 5 };    s = (string){ "abc" };   s = (string){ 5.5 };
+s = (string){ 5 };    s = (string){ "abc" };    s = (string){ 5.5 };
 \end{cfa}
 Conversions from @string@ to @char *@ attempt to be safe.
 The @strncpy@ conversion requires the maximum length for the pointer's target buffer.
+The overloaded @strncpy@ function is safe, if the length of the C string is correct.
 The assignment operator and constructor both allocate the buffer and return its address, meaning the programmer must free it.
 Note, a C string is always null terminated, implying storage is always necessary for the null.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 string s = "abcde";
 char cs[4];
 strncpy( cs, s, sizeof(cs) );
 char * cp = s;          // ownership
+char * cp = s;            // ownership
 delete( cp );
 cp = s + ' ' + s;       // ownership
 …
 \subsection{Length}
 The @len@ operation (short for @strlen@) returns the length of a C or \CFA string.
 For compatibility, @strlen@ also works with \CFA strings.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+The @len@ operation (short for @strlen@) returns the length of a C (not including the terminating null) or \CFA string.
+For compatibility, an overloaded @strlen@ works with \CFA strings.
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 i = len( "" );
 …
 In C, these operators compare the C string pointer not its value, which does not match programmer expectation.
 C strings use function @strcmp@ to lexicographically compare the string value.
 Java has the same issue with @==@ and @.equals@.
+Java has the same issue with @==@ (reference) and @.equals@ (value) comparison.
 …
 The binary operators @+@ and @+=@ concatenate C @char@, @char *@ and \CFA strings, creating the sum of the characters.
 \begin{cquote}
+\begin{tabular}{@{}l|l@{\hspace{15pt}}l|l@{\hspace{15pt}}l|l@{}}
+\setlength{\tabcolsep}{5pt}
+\begin{tabular}{@{}ll|ll|ll@{}}
 \begin{cfa}
 s = "";
 …
 Similarly, it is impossible to restrict or remove addition on type @char *@ because (unfortunately) it is subscripting: @cs + 'a'@ implies @cs['a']@ or @'a'[cs]@.
 The prior \CFA concatenation examples show complex mixed-mode interactions among @char@, @char *@, and @string@ constants work correctly (variables are the same).
+The prior \CFA concatenation examples show complex mixed-mode interactions among @char@, @char *@, and @string@ constants work correctly (@string@ variables are the same).
 The reason is that the \CFA type-system handles this kind of overloading well using the left-hand assignment-type and complex conversion costs.
 Hence, the type system correctly handles all uses of addition (explicit or implicit) for @char *@.
 …
 If $N = 0$, a zero length string, @""@, is returned.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 s = 'x' * 0;
 …
 multiplication of pointers does not exist in C.
 \begin{cfa}
 ch = ch * 3;            $\C[2in]{// LHS disambiguate, multiply character values}$
+ch = ch * 3;            $\C[2in]{// LHS disambiguate, multiply character value}$
 s = 'a' * 3;            $\C{// LHS disambiguate, concatenate characters}$
 printf( "%c\n", @'a' * 3@ ); $\C{// no LHS information, ambiguous}$
 …
 The substring operation returns a subset of a string starting at a position in the string and traversing a length, or matching a pattern string.
 \begin{cquote}
 \setlength{\tabcolsep}{10pt}
 \begin{tabular}{@{}l|ll|l@{}}
+\setlength{\tabcolsep}{8pt}
+\begin{tabular}{@{}ll|ll@{}}
 \multicolumn{2}{@{}c}{\textbf{length}} & \multicolumn{2}{c@{}}{\textbf{pattern}} \\
 \multicolumn{4}{@{}l}{\lstinline{string name = "PETER"}} \\
 …
 "TER"   // clip length to 3
 "ER"
 ""                 // beyond string to right, clip to null
 ""                 // beyond string to left, clip to null
+""                 // clip, beyond right
+""                 // clip, beyond left
 "ER"
 "TER"   // to end of string
 …
 Hence, the left string may decrease, stay the same, or increase in length.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}[escapechar={}]
 digit( 3, 3 ) = "";
 …
 \end{tabular}
 \end{cquote}
 Now substring pattern matching is useful on the left-hand side of assignment.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+Here, substring pattern matching is useful on the left-hand side of assignment.
+\begin{cquote}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}[escapechar={}]
 digit( "$$" ) = "345";
 …
 \end{tabular}
 \end{cquote}
 Extending the pattern to a regular expression is a possible extension.
+Supporting a regular-expression pattern is a possible extension.
 The replace operation extends substring to substitute all occurrences.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 s = replace( "PETER", "E", "XX" );
 …
 If the key does not appear in the string, the length of the string is returned.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 i = find( digit, '3' );
 …
 A character-class operation indicates if a string is composed completely of a particular class of characters, \eg, alphabetic, numeric, vowels, \etc.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 charclass vowels{ "aeiouy" };
 …
 Function @exclude@ is the reverse of @include@, checking if all characters in the string are excluded from the class (compliance).
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 i = exclude( "cdbfghmk", vowels );
 …
 Both forms can return the longest substring of compliant characters.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 s = include( "aaeiuyoo", vowels );
 …
 There are also versions of @include@ and @exclude@, returning a position or string, taking a validation function, like one of the C character-class functions.\footnote{It is part of the hereditary of C that these function take and return an \lstinline{int} rather than a \lstinline{bool}, which affects the function type.}
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 i = include( "1FeC34aB", @isxdigit@ );
 …
 The translate operation returns a string with each character transformed by one of the C character transformation functions.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 s = translate( "abc", @toupper@ );
 …
 However, string search can fail, which is reported as an alternate search outcome, possibly an exception.
 Many string libraries use a return code to indicate search failure, with a failure value of @0@ or @-1@ (PL/I~\cite{PLI} returns @0@).
 This semantics leads to the awkward pattern, which can appear many times in a string library or user code.
+This semantics leads to an awkward pattern, which can appear many times in a string library or user code.
 \begin{cfa}
 i = exclude( s, alpha );
 …
 else return "";
 \end{cfa}
+The problem is that substring does the wrong thing or fails with the failure return-code in most string libraries, so it has to be special cased.
 \CFA adopts a return code but the failure value is taken from the index-of function in APL~\cite{apl}, which returns the length of the target string $N$ (or $N+1$ for 1 origin).
 …
 \begin{figure}
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \multicolumn{1}{c}{\textbf{\CC}} & \multicolumn{1}{c}{\textbf{\CFA}} \\
 \begin{cfa}
 …
 \begin{cquote}
 \begin{tabular}{@{}ll@{}}
 \begin{cfa}
+char s[32];   // string s;
+\multicolumn{2}{@{}l@{}}{\lstinline{char s[32];   // changing s's type to string works}} \\
+\begin{cfa}
 strlen( s );
 strnlen( s, 3 );
 …
+&
 \begin{cfa}
 strcpy( s, "abc" );
 strncpy( s, "abcdef", 3 );
 …
 \subsection{I/O Operators}
 The ability to input and output strings is as essential as for any other type.
 The goal for character I/O is to also work with groups rather than individual characters.
+The ability to input and output a string is as essential as for any other type.
+The goal for character I/O is to work with groups rather than individual characters.
 A comparison with \CC string I/O is presented as a counterpoint to \CFA string I/O.
 …
 The \CC manipulators are @setw@, and its associated width controls @left@, @right@ and @setfill@.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{c++}
 string s = "abc";
 …
 The \CFA manipulators are @bin@, @oct@, @hex@, @wd@, and its associated width control and @left@.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{cfa}
 string s = "abc";
 …
 Reading into a @char@ is safe as the size is 1, @char *@ is unsafe without using @setw@ to constraint the length (which includes @'\0'@), @string@ is safe as its grows dynamically as characters are read.
 \begin{cquote}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{c++}
 char ch, c[10];
 …
 \end{cquote}
 Input text can be \emph{gulped}, including whitespace, from the current point to an arbitrary delimiter character using @getline@.
+\begin{cquote}
+\setlength{\tabcolsep}{10pt}
+\begin{tabular}{@{}ll@{}}
+\multicolumn{1}{c}{\textbf{\CC}} & \multicolumn{1}{c}{\textbf{\CFA}} \\
+\begin{cfa}
+string s1, s2, s3;
+getline( cin, s1, 'a' );
+getline( cin, s2, 'w' );
+getline( cin, s3 );
+cout << s1 << ' ' << s2 << ' ' << s3 << endl;
+@bbbad ddwxyz@
+\end{cfa}
+&
+\begin{cfa}
+sin | getline( s1, 'a' )
+        | getline( s2, 'w' )
+        | getline( s3 );
+sout | s1 | s2 | s3;       "bbb" "d dd" "xyz"
+\end{cfa}
+\end{tabular}
+\end{cquote}
 The \CFA philosophy for input is that, for every constant type in C, these constants should be usable as input.
 …
 \begin{cquote}
 \setlength{\tabcolsep}{10pt}
 \begin{tabular}{@{}l|l@{}}
+\begin{tabular}{@{}ll@{}}
 \begin{c++}
 char ch, c[10];
 …
 sin | ch | wdi( 5, c ) | s;
 @abcde fg@
 sin | quote( ch ) | quote( wdi( sizeof(c), c ) ) | quote( s, '[', ']' ) | nl;
 @'a' "bcde" [fg]@
+sin | @quote@( ch ) | @quote@( wdi( sizeof(c), c ) ) | @quote@( s, '[', ']' ) | nl;
+@'a'   "bcde"      [fg]@
 sin | incl( "a-zA-Z0-9 ?!&\n", s ) | nl;
 @x?&000xyz TOM !.@
 …
 For example, the \CC @replace@ function selects a substring in the target and substitutes it with the source string, which can be smaller or larger than the substring.
 \CC modifies the mutable receiver object, replacing by position (zero origin) and length.
-\begin{cquote}
-\begin{tabular}{@{}l|l@{}}
 \begin{c++}
 string s1 = "abcde";
 s1.replace( 2, 3, "xy" );
+s1.replace( 2, 3, "xy" );                        "abxy"
 \end{c++}
+&
-\begin{c++}
-"abxy"
-\end{c++}
-\end{tabular}
-\end{cquote}
 Java cannot modify the receiver (immutable strings) so it returns a new string, replacing by text.
 \label{p:JavaReplace}
-\begin{cquote}
-\begin{tabular}{@{}l|l@{}}
 \begin{java}
 String s = "abcde";
 String r = s.replace( "cde", "xy" );
+String r = s.replace( "cde", "xy" );      "abxy"
 \end{java}
+&
-\begin{java}
-"abxy"
-\end{java}
-\end{tabular}
-\end{cquote}
 Java also provides a mutable @StringBuffer@, replacing by position (zero origin) and length.
-\begin{cquote}
-\begin{tabular}{@{}l|l@{}}
 \begin{java}
 StringBuffer sb = new StringBuffer( "abcde" );
 sb.replace( 2, 5, "xy" );
+sb.replace( 2, 5, "xy" );                         "abxy"
 \end{java}
+&
-\begin{java}
-"abxy"
-\end{java}
-\end{tabular}
-\end{cquote}
 However, there are anomalies.
 @StringBuffer@'s @substring@ returns a @String@ copy that is immutable rather than modifying the receiver.
 …
 \begin{figure}
 \setlength{\extrarowheight}{2pt}
+\begin{tabularx}{\textwidth}{@{}p{0.6in}XXcccc@{}}
+\setlength{\tabcolsep}{5pt}
+\begin{tabularx}{\textwidth}{@{}p{0.8in}XXcccc@{}}
                                         &                       &                       & \multicolumn{4}{@{}c@{}}{\underline{Supports Helpful?}} \\
                                         & Required      & Helpful       & C                     & \CC           & Java          & \CFA \\
 \hline
 Type abst'n
+Type Abstraction
                                         & Low-level: The string type is a varying amount of text communicated via a parameter or return.
                                                                 & High-level: The string-typed relieves the user of managing memory for the text.
 …
 String s3 = s2.substring( 1, 2 );  $\C{// snapshot state (possible), strict symmetry, fragment referent}\CRT$
 System.out.println( s + ' ' + s1 + ' ' + s2 + ' ' + s3 );
+$\texttt{\small abcde abcde bc c}$
 System.out.println( (s == s1) + " " + (s == s2) + " " + (s2 == s3) );
-$\texttt{\small abcde abcde bc c}$
 $\texttt{\small true false false}$
 \end{java}
 …
 string s3 = s`share; $\C{// alias state, strict symmetry, variable-constrained referent}$
 string s4 = s( 1, 2 ); $\C{// snapshot state, strict symmetry, fragment referent}$
 string s5 = s4( 1, 1 )`share'; $\C{// alias state, strict symmetry, fragment referent}\CRT$
+string s5 = s4( 1, 1 )`share; $\C{// alias state, strict symmetry, fragment referent}\CRT$
 sout | s | s1 | s2 | s3 | s4 | s5;
 $\texttt{\small abcde abcde abcde abcde bc c}$
 …
 String sharing is expressed using the @`share@ marker to indicate aliasing (mutations shared) \vs snapshot (not quite an immutable result, but one with subsequent mutations isolated).
 This aliasing relationship is a sticky property established at initialization.
+This aliasing relationship is a \newterm{sticky property} established at initialization.
 For example, here strings @s1@ and @s1a@ are in an aliasing relationship, while @s2@ is in a copy relationship.
 \input{sharing1.tex}
 …
 When changes happen on an aliasing substring that overlap.
 \input{sharing10.tex}
 Strings @s1_crs@ and @s1_mid@ overlap at character 4, @j@, because the substrings are 3,2 and 4,2.
+Strings @s1_crs@ and @s1_mid@ overlap at character 4, @'j'@, because the substrings are 3,2 and 4,2.
 When @s1_crs@'s size increases by 1, @s1_mid@'s starting location moves from 4 to 5, but the overlapping character remains, changing to @'+'@.
 …
 Normally, one global context is appropriate for an entire program;
 concurrency is discussed in \VRef{s:ControllingImplicitSharing}.
 A string is a handle to a node in a linked list containing a information about a string text in the buffer.
+A string is a handle to a node in a linked list containing information about a string text in the buffer.
 The list is doubly linked for $O(1)$ insertion and removal at any location.
 Strings are ordered in the list by text start address.
 …
 The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
 The string handles are maintained in sorted order, so the handle list can be traversed, copying the first live text to the start of the buffer, and subsequent strings after each other.
 After compaction, if free storage is still be less than the new string allocation, a larger text buffer is heap-allocated, the current buffer is copied into the new buffer, and the original buffer is freed.
+After compaction, if free storage is still less than the new string allocation, a larger text buffer is heap-allocated, the current buffer is copied into the new buffer, and the original buffer is freed.
 Note, the list of string handles is structurally unaffected during a compaction;
 only the text pointers in the handles are modified to new buffer locations.
 …
 There are two fundamental string-creation functions: importing external text like a C-string or reading a string, and initialization from an existing \CFA string.
 When importing, storage comes from the end of the buffer, into which the text is copied.
 The new string handle is inserted at the end of the handle list because the new text is at the end of the buffer.
+To maintain sorted order, the new string handle is inserted at the end of the handle list because the new text is at the end of the buffer.
 When initializing from text already in the buffer, the new handle is a second reference into the original run of characters.
 In this case, the new handle's linked-list position is after the original handle.
+To maintain sorted order, the new handle's linked-list position is after the original handle.
 Both string initialization styles preserve the string module's internal invariant that the linked-list order matches the buffer order.
 For string destruction, handles are removed from the list.
 …
 Favourable conditions allow for in-place editing: where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location see the new value.
 One notable example of favourable conditions occurs because the most recently written string is often the last in the buffer, after which a large amount of free space occurs.
 So, repeated appends often occur without copying previously accumulated characters.
+Now, repeated appends (reading) can occur without copying previously accumulated characters.
 However, the general case requires a new buffer allocation: where the new value does not fit in the old place, or if other handles are still using the old value.
 …
 Both \CC and \CFA RAII systems are powerful enough to achieve reference counting.
+In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a @this@ parameter providing an object's memory address.
+In general, a lifecycle function has access to an object by location, \ie constructors and destructors receive a parameter providing an object's memory address.\footnote{
+Historically in \CC, the type of \lstinline[language=C++]{this} is a pointer versus a reference;
+in \CFA, the first parameter of a constructor or destructor must be a reference.}
 \begin{cfa}
 struct S { int * ip; };
 void ?{}( S & @this@ ) { this.ip = new(); } $\C[3in]{// default constructor}$
 void ?{}( S & @this@, int i ) { (this){}; *this.ip = i; } $\C{// initializing constructor}$
 void ?{}( S & @this@, S s ) { (this){*s.ip}; } $\C{// copy constructor}$
+void ?{}( S & @this@, int i ) { this{}; *this.ip = i; } $\C{// initializing constructor}$
+void ?{}( S & @this@, S s ) { this{ *s.ip }; } $\C{// copy constructor}$
 void ^?{}( S & @this@ ) { delete( this.ip ); } $\C{// destructor}\CRT$
 \end{cfa}
 Such basic examples use the @this@ address only to gain access to the values being managed.
+But the lifecycle logic can use the pointer generally, too.
+For example, they can add @this@ object to a collection at creation and remove it at destruction.
+\begin{cfa}
+// header
+struct T {
+But lifecycle logic can use the address, too, \eg add the @this@ object to a collection at creation and remove it at destruction.
+\begin{cfa}
+// header (.hfa)
+struct N { $\C[3in]{// list node}$
         // private
         inline dlink(T);
+        inline dlink( N );
 };
 void ?{}( T & ); $\C[3in]{// default constructor}$
 void ^?{}( T & ); $\C{// destructor}\CRT$
 // implementation
 static dlist(T) @all_T@;
 void ?{}( T & this ) { insert_last(all_T, @this@) }
 void ^?{}( T & this ) { remove(this); }
 \end{cfa}
 A module providing the @T@ type can traverse @all_T@ at relevant times, to keep the objects ``good.''
 Hence, declaring a @T@ not only ensures that it begins with an initially ``good'' value, but it also provides an implicit subscription to a service that keeps the value ``good'' during its lifetime.
+void ?{}( N & ); $\C{// default constructor}$
+void ^?{}( N & ); $\C{// destructor}\CRT$
+// implementation (.cfa)
+static dlist( N ) @list_N@;
+void ?{}( N & this ) { insert_last( list_N, @this@ ) }
+void ^?{}( N & this ) { remove( this ); }
+\end{cfa}
+A module providing the @N@ (node) type can traverse @list_N@ to manipulate the objects.
+Hence, declaring a @N@ not only ensures that it begins with an initially ``good'' value, but it also provides an implicit subscription to a service that keeps the value ``good'' during its lifetime.
 Again, both \CFA and \CC support this usage style.
 …
 In the parameter direction, the language's function-call handling must arrange for a copy-constructor call to happen, at a time near the control transfer into the callee. %, with the source as the caller's (sender's) version and the target as the callee's (receiver's) version.
 In the return direction, the roles are reversed and the copy-constructor call happens near the return of control.
 \CC supports this capability.% without qualification.
+\CC supports this capability. % without qualification.
 \CFA offers limited support;
 simple examples work, but implicit copying does not combine successfully with the other RAII capabilities discussed.
+simple examples work, but implicit copying does not combine successfully with other RAII capabilities.
 \CC also offers move constructors and return-value optimization~\cite{RVO20}.
 …
 \begin{enumerate}
 \item
+\label{p:feature1}
         Object provider implements lifecycle functions to manage a resource outside of the object.
 \item
+        Object provider implements lifecycle functions to store references back to the object, often originating from outside of it.
+\label{p:feature2}
+        Object provider implements lifecycle functions to store references to the object, often originating from outside of it.
 \item
+\label{p:feature3}
         Object user expects to pass (in either direction) an object by value for function calls.
 \end{enumerate}
+\CC supports all three simultaneously.  \CFA does not currently support \#2 and \#3 on the same object, though \#1 works along with either one of \#2 or \#3.  \CFA needs to be fixed to support all three simultaneously.
+The reason that \CFA does not support \#2 with \#3 is a holdover from how \CFA function calls lowered to C, before \CFA got references and RAII.
+At that time, adhering to a principal of minimal intervention, this code could always be treated as passthrough:
+\CC supports all three simultaneously.
+\CFA does not currently support \ref{p:feature2} and \ref{p:feature3} on the same object, though \ref{p:feature1} works along with either one of \ref{p:feature2} or \ref{p:feature3}.
+\CFA needs to be fixed to support all three simultaneously.
+The reason \CFA does not support \ref{p:feature2} with \ref{p:feature3} is a holdover from how \CFA lowered function calls to C, before \CFA got references and RAII.
+At that time, adhering to a principal of minimal intervention, this code was treated as a passthrough:
 \begin{cfa}
 struct U { ... };
 // RAII to go here
 void f( U u ) { F_BODY(u) }
+void f( U u ) { F_BODY( u ) }
 U x;
 f( x );
 \end{cfa}
+But adding custom RAII (at ``...go here'') changes things.
+The common \CC lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} proceeds differently than the present \CFA lowering.
+\begin{cquote}
+However, adding custom RAII (at ``...go here'') changes things.
+\VRef[Figure]{f:CodeLoweringRAII} shows the common \CC lowering~\cite[Sec. 3.1.2.3]{cxx:raii-abi} (right) proceeds differently than the present \CFA lowering (left).
+The current \CFA scheme is still using a by-value C call.
+C does a @memcpy@ on structures passed by value.
+And so, @F_BODY@ sees the bits of @__u_for_f@ occurring at an address that has never been presented to the @U@ lifecycle functions.
+If @U@ is trying to have a style- \ref{p:feature2} invariant, it shows up broken in @F_BODY@: references supposedly to @u@ are actually to @__u_for_f@.
+The \CC scheme does not have this problem because it constructs the @u@ copy in the correct location within @f@.
+Yet, the current \CFA scheme is sufficient to deliver style-\ref{p:feature1} invariants (in this style-\ref{p:feature3} use case) because this scheme still does the correct number of lifecycle calls, using correct values, at correct times.
+So, reference-counting or simple ownership applications get their invariants respected under call/return-by-value.
+\begin{figure}
+\centering
 \begin{tabular}{@{}l|l@{}}
+\begin{cfa}
+$\C[0.0in]{// \CC, \CFA future}\CRT$
+\multicolumn{1}{@{}c|}{\CFA today} & \multicolumn{1}{c@{}}{\CC, \CFA future} \\
+\begin{cfa}
+struct U {...};
+// RAII elided
+void f( U u ) {
+        F_BODY( u );
+}
+U x; // call default ctor
+{
+        @U __u_for_f = x;@  // call copy ctor
+        f( __u_for_f );
+        // call dtor, __u_for_f
+}
+// call dtor, x
+\end{cfa}
+&
+\begin{cfa}
 struct U {...};
 // RAII elided
 void f( U * __u_orig ) {
         U u = * __u_orig;  // call copy ctor
+        @U u = * __u_orig;@  // call copy ctor
         F_BODY( u );
         // call dtor, u
 …
 // call dtor, x
 \end{cfa}
+&
+\begin{cfa}
+$\C[0.0in]{// \CFA today}\CRT$
+struct U {...};
+// RAII elided
+void f( U u ) {
+        F_BODY( u );
+}
+U x; // call default ctor
+{
+        U __u_for_f = x;  // call copy ctor
+        f( __u_for_f );
+        // call dtor, __u_for_f
+}
+// call dtor, x
+\end{cfa}
+\end{tabular}
+\end{cquote}
+The current \CFA scheme is still using a by-value C call.
+C does a @memcpy@ on structures passed by value.
+And so, @F_BODY@ sees the bits of @__u_for_f@ occurring at an address that has never been presented to the @U@ lifecycle functions.
+If @U@ is trying to have a style-\#2 invariant, it shows up broken in @F_BODY@: references supposedly to @u@ are actually to @__u_for_f@.
+The \CC scheme does not have this problem because it constructs the for @f@ copy in the correct location within @f@.
+Yet, the current \CFA scheme is sufficient to deliver style-\#1 invariants (in this style-\#3 use case) because this scheme still does the correct number of lifecycle calls, using correct values, at correct times.
+So, reference-counting or simple ownership applications get their invariants respected under call/return-by-value.
+\end{tabular}
+\caption{Code Lowering for RAII}
+\label{f:CodeLoweringRAII}
+\end{figure}
 % [Mike is not currently seeing how distinguishing initialization from assignment is relevant]
 …
 % The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.
 The string API offers style \#3's pass-by-value in, \eg in the return of @"a" + "b"@.
 Its implementation uses the style-\#2 invariant of the string handles being linked to each other, helping to achieve high performance.
+The string API offers style \ref{p:feature3}'s pass-by-value, \eg in the return of @"a" + "b"@.
+Its implementation uses the style-\ref{p:feature2} invariant of the string handles being linked to each other, helping to achieve high performance.
 Since these two RAII styles cannot coexist, a workaround splits the API into two layers: one that provides pass-by-value, built upon the other with inter-linked handles.
 The layer with pass-by-value incurs a performance penalty, while the layer without delivers the desired runtime performance.
 …
 Both APIs present the same features, up to return-by-value operations being unavailable in LL and implemented via the workaround in HL.
 The intention is for most future code to target HL.
+When the RAII issue is fixed, the full HL feature set will be achievable using the LL-style lifetime management.
+Then, HL will be removed;
+LL's type will be renamed @string@ and programs written for current HL will run faster.
+When the RAII issue is fixed, the full HL feature set is achievable using the LL-style lifetime management.
+Then, HL can be removed, LL's type renamed to @string@, and programs generated with the current HL will run faster.
 In the meantime, performance-critical sections of applications must use LL.
 Subsequent performance experiments \see{\VRef{s:PerformanceAssessment}} use the LL API when comparing \CFA to other languages.
 This measurement gives a fair estimate of the goal state for \CFA.
 A separate measure of the HL overhead is also included.
 hence, \VRef[Section]{string-general-impl} us describing the goal state for \CFA.
 In present state, the type @string_res@ replaces its mention of @string@ as inter-linked handle.
+Hence, \VRef[Section]{string-general-impl} is describing the goal state for \CFA.
+In present state, the internal type @string_res@ replaces @string@ for an inter-linked handle.
 To use LL, a programmer rewrites invocations using pass-by-value APIs into invocations where resourcing is more explicit.
 Many invocations are unaffected, notably assignment and comparison.
+Of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only the following three cases need revisions.
+\begin{cquote}
+\begin{tabular}{ll}
+\VRef[Figure]{f:HL_LL_Lowering} shows, of the capabilities listed in \VRef[Figure]{f:StrApiCompare}, only three cases need revisions.
+The actual HL workaround wraps @string@ as a pointer to a uniquely owned, heap-allocated @string_res@.
+This arrangement has @string@ using style-\ref{p:feature1} RAII, which is compatible with pass-by-value.
+\begin{figure}
+\centering
+\begin{tabular}{@{}ll@{}}
 HL & LL \\
 \hline
 …
 \begin{cfa}
 string s = "abcde";
 string s2 = s(2, 3); // s2 == "cde"
 s(2,3) = "x"; // s == "abx" && s2 == "cde"
+string s2 = s(2, 3);   // s2 == "cde"
+s(2,3) = "x";   // s == "abx" && s2 == "cde"
 \end{cfa}
+&
 \begin{cfa}
 string_res sr = "abcde";
 string_res sr2 = {sr, 2, 3}; // sr2 == "cde"
+string_res sr2 = {sr, 2, 3};   // sr2 == "cde"
 string_res sr_mid = { sr, 2, 3, SHARE };
 sr_mid = "x"; // sr == "abx" && sr2 == "cde"
+sr_mid = "x";   // sr == "abx" && sr2 == "cde"
 \end{cfa}
 \\
 …
 string s = "abcde";
 s[2] = "xxx";  // s == "abxxxde"
+s[2] = "xxx";    // s == "abxxxde"
 \end{cfa}
+&
 …
 string_res sr = "abcde";
 string_res sr_mid = { sr, 2, 1, SHARE };
+mid = "xxx"; // sr == "abxxxde"
+\end{cfa}
+\end{tabular}
+\end{cquote}
+The actual HL workaround is having @string@ wrap a pointer to a uniquely owned, heap-allocated @string_res@.  This arrangement has @string@ being style-\#1 RAII, which is compatible with pass-by-value.
+mid = "xxx";   // sr == "abxxxde"
+\end{cfa}
+\end{tabular}
+\caption{HL to LL Lowering}
+\label{f:HL_LL_Lowering}
+\end{figure}
 …
 It might be possible to pack 16- or 32-bit Unicode characters within the same string buffer as 8-bit characters.
 Again, locations for identification flags must be found and checked along the fast path to select the correct actions.
 Handling utf8 (variable length), is more problematic because simple pointer arithmetic cannot be used to stride through the variable-length characters.
+Handling utf8 (variable length) is more problematic because simple pointer arithmetic cannot be used to stride through the variable-length characters.
 Trying to use a secondary array of fixed-sized pointers/offsets to the characters is possible, but raises the question of storage management for the utf8 characters themselves.
 …
 I assessed the \CFA string library's speed and memory usage against strings in \CC STL.
+Overall, this analysis shows that adding support for the features shown earlier in the chapter comes at no substantial cost in the performance of features common to both APIs.
+Moreover, the results support the \CFA string's position as a high-level enabler of simplified text processing.
+STL makes its user think about memory management.
+Overall, this analysis shows that features common to both APIs comes at no substantial cost in the performance.
+Moreover, the comparison shows that \CFA's high-level string features simplify text processing because the STL requires users to think more about memory management.
 When the user does, and is successful, STL's performance can be very good.
 But when the user fails to think through the consequences of the STL representation, performance becomes poor.
+But if a user does understand the consequences of the STL representation, performance becomes poor.
 The \CFA string lets the user work at the level of just putting the right text into the right variables, with corresponding performance degradations reduced or eliminated.
 …
 These tests use a \emph{corpus} of strings.
 Their lengths are important; the specific characters occurring in them are immaterial.
+In a result graph, a corpus's mean string length is often the independent variable shown on the X axis.
+In a result graph, a corpus's mean string-length is often the independent variable on the x-axis.
 When a corpus contains strings of different lengths, the lengths are drawn from a lognormal distribution.
 Therefore, strings much longer than the mean occur less often and strings slightly shorter than the mean occur most often.
 …
 To ensure comparable results, a common memory allocator is used for \CFA and \CC.
 \CFA runs the llheap allocator~\cite{Zulfiqar22}, which is also plugged into \CC.
+The llheap allocator is significantly better than the standard @glibc@ allocator.
 The operations being measured take dozens of nanoseconds, so a succession of many invocations is run and timed as a group.
 …
 \VRef[Figure]{fig:string-graph-peq-cppemu} shows the resulting performance.
 The two fresh (solid) lines and the two reuse (dash) lines are identical, except for lengths $\le$10, where the \CC SSO has a 40\% average and minimally 24\% advantage.
+The two fresh (solid spline lines) and the two reuse (dash spline lines) are identical, except for lengths $\le$10, where the \CC SSO has a 40\% average and minimally 24\% advantage.
 The gap between the fresh and reuse lines is the removal of the dynamic memory allocates and reuse of prior storage, \eg 100M allocations for fresh \vs 100 allocations for reuse across all experiments.
 While allocation reduction is huge, data copying dominates the cost, so the lines are still reasonably close together.
 …
 In earlier experiments, the choice of \CFA API among HL and LL had no impact on the functionality being tested.
 Here, however, the @+@ operation, which returns its result by value, is only available in HL.
+The \CFA @+@ number was obtained by inlining the HL implementation of @+@, which is done using LL's @+=@, into the test harness, while omitting the HL-inherent extra dynamic allocation.  The HL-upon-LL @+@ implementation, is:
+\begin{cfa}
+struct string {
+        string_res * inner;  // RAII manages malloc/free, simple ownership
+The \CFA @+=@ is obtained by inlining the HL implementation of @+@, which is done using LL's @+=@, into the test harness, while omitting the HL-inherent extra dynamic allocation.  The HL-upon-LL @+@ implementation, is:
+\begin{cquote}
+\setlength{\tabcolsep}{20pt}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+struct string {   // simple ownership
+        string_res * inner;  // RAII manages malloc/free
 };
 void ?+=?( string & s, string s2 ) {
         (*s.inner) += (*s2.inner);
+}
+\end{cfa}
+&
+\begin{cfa}
 string @?+?@( string lhs, string rhs ) {
         string ret = lhs;
 …
         return ret;
+}
+\end{cfa}
+\end{cfa}
+\end{tabular}
+\end{cquote}
 This @+@ implementation is also the goal implementation of @+@ once the HL/LL workaround is no longer needed.  Inlining the induced LL steps into the test harness gives:
 \begin{cquote}
 …
 So again, \CFA helps users who just want to treat strings as values, and not think about the resource management under the covers.
 While not a design goal, and not graphed, \CFA in STL-emulation mode outperformed STL in this case.
 User-managed allocation reuse did not affect either implementation in this case; only ``fresh'' results are shown.
+\PAB{Something is wrong with these sentences: While not a design goal, and not graphed, \CFA in STL-emulation mode outperformed STL in this case.
+User-managed allocation reuse did not affect either implementation in this case; only ``fresh'' results are shown.}
 …
 \end{cfa}
 With implicit sharing active, \CFA treats this operation as normal and supported.
+Again, an HL-LL difference requires an LL mockup.  This time, the fact to integrate into the test harness is that LL does not directly support pass-by-value.
+Again, an HL-LL difference requires a mockup as LL does not directly support pass-by-value.
 \begin{cquote}
 \setlength{\tabcolsep}{20pt}
 …
 The goal (HL) version gives the modified test harness, with a single loop.
 Each iteration uses a corpus item as the argument to the function call.
 These corpus items were imported to the string heap before beginning the timed run.
+These corpus items are imported to the string heap before beginning the timed run.
 \begin{figure}
 …
 \VRef[Figure]{fig:string-graph-pbv} shows the costs for calling a function that receives a string argument by value.
+STL's performance worsens uniformly as string length increases, while \CFA has the same performance at all sizes.
+Although the STL is better than \CFA until string length 10 because of the SSO.
+STL's performance worsens uniformly as string length increases, except for short strings due to SSO, while \CFA has the same performance at all sizes.
 While improved, the \CFA cost to pass a string is still nontrivial.
 The contributor is adding and removing the callee's string handle from the global list.

doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

r79ba50c	r8614140
139	139	Often, the array is part of the programming language, while linked lists are built from (recursive) pointer types, and strings from arrays and/or linked lists.
140	140	For all three types, languages and/or their libraries supply varying degrees of high-level mechanisms for manipulating these objects at the bulk and component levels, such as copying, slicing, extracting, and iterating among elements.
141		Unfortunately, typical solutions for the the ~~key types in C cause 60\%--70\% of the reported software vulnerabilities involving memory errors; 70\%--80\% of hacker attack~~ vectors target these types.
	141	Unfortunately, typical solutions for the these key types in C cause 60\%--70\% of the reported software vulnerabilities involving memory errors; 70\%--80\% of hacker attack-vectors target these types.
142	142	Therefore, hardening these three C types goes a long way to make the majority of C programs safer.
143	143

libcfa/src/collections/array.hfa

-              r79ba50c
+              r8614140
         //    types like size_t.  So trying to overload on ptrdiff_t vs int works in 64-bit mode
         //    but not in 32-bit mode.
+        // -  Given bug of Trac #247, CFA gives sizeof expressions type unsigned long int, when it
+        //    should give them type size_t.
+        //
+        //                          gcc -m32         cfa -m32 given bug         gcc -m64 (and cfa)
+        // ptrdiff_t                int              int                        long int
+        // size_t                   unsigned int     unsigned int               unsigned long int
+        // typeof( sizeof(42) )     unsigned int     unsigned long int          unsigned long int
+        // int                      int              int                        int
+        //
+        //                          cfa -m32 (and gcc)      cfa -m64 (and gcc)
+        // ptrdiff_t                int                     long int
+        // size_t                   unsigned int            unsigned long int
+        // typeof( sizeof(42) )     unsigned int            unsigned long int
+        // int                      int                     int
         //
         // So the solution must support types {zero_t, one_t, int, unsigned int, long int, unsigned long int}
 …
         // because assertion satisfaction requires types to match exacly.  Both higher-dimensional
         // subscripting and operations on slices use asserted subscript operators.  The test case
         // array-container/array-sbscr-cases covers the combinations.  Mike beleives that commenting out
+        // array-collections/array-sbscr-types covers the combinations.  Mike beleives that commenting out
         // any of the current overloads leads to one of those cases failing, either on 64- or 32-bit.
         // Mike is open to being shown a smaller set of overloads that still passes the test.
         static inline Timmed & ?[?]( arpk( N, S, Timmed, Tbase ) & a, zero_t ) {
 …
         return this[[ab0,ab1,ab2]][bc];
+}
+// Further form of -[-,-,-] that avoids using the trait system.
+// Above overloads work for any type with (recursively valid) subscript operator,
+// provided said subscript is passed as an assertion.
+// Below works only on arpk variations but never passes its subscript though an assertion.
+//
+// When arpk implements the trait used above,
+// the critical assertion is backed by a nontrivial thunk.
+// There is no "thunk problem" (lifetime) issue, when used as shown in the test suite.
+// But the optimizer has shown difficulty removing these thunks in cases where "it should,"
+// i.e. when all user code is in one compilation unit.
+// Not that every attempt at removing such a thunk fails; cases have been found going both ways.
+// Cases have been found with unnecessary bound-checks removed successfully,
+// on user code written against the overloads below,
+// but where these bound checks (which occur within `call`ed thunks) are not removed,
+// on user code written against the overloads above.
+//
+// The overloads below provide specializations of the above
+// that are a little harder to use than the ones above,
+// but where array API erasure has been seen to be more effective.
+// Note that the style below does not appeal to a case where thunk inlining is more effective;
+// rather, it simply does not rely on thunks in the first place.
+//
+// Both usage styles are shown in test array-md-sbscr-cases#numSubscrTypeCompatibility,
+// with the more general one above being "high abstraction,"
+// and the more performant one below being "mid abstraction" and "low abstraction."
+//
+// A breadth of index types is not given here (providing -[size_t,size_t,...] only)
+// because these declarations are not feeding a trait, so safe implicit arithmetic conversion kiks in.
+// Even so, there may still be an un-met need for accepting
+// either ptrdiff_t or size_t (signed or unsigned)
+// because Mike has seen the optimizer resist removing bound checks when sign-conversion is in play.
+// "Only size_t" is meeting today's need
+// and no solution is known that avoids 2^D overloads for D dimensions
+// while offering multiple subscript types and staying assertion-free.
+//
+// This approach, of avoiding traits entirely, is likely incompatible with the original desire
+// to have one recursive multidimensional subscript operator (TRY_BROKEN_DESIRED_MD_SUBSCRIPT).
+// To make a single declaration work,
+// we would probably have to get better at coaxing the optimizer into inlining thunks.
+forall( [N2], S2*, [N1], S1*, Timmed1, Tbase )
+static inline Timmed1 & ?[?]( arpk( N2, S2, arpk( N1, S1, Timmed1, Tbase ), Tbase ) & this, size_t ix2, size_t ix1 ) {
+        return this[ix2][ix1];
+}
+forall( [N3], S3*, [N2], S2*, [N1], S1*, Timmed1, Tbase )
+static inline Timmed1 & ?[?]( arpk( N3, S3, arpk( N2, S2, arpk( N1, S1, Timmed1, Tbase ), Tbase ), Tbase ) & this, size_t ix3, size_t ix2, size_t ix1 ) {
+        return this[ix3][ix2][ix1];
+}
+forall( [N4], S4*, [N3], S3*, [N2], S2*, [N1], S1*, Timmed1, Tbase )
+static inline Timmed1 & ?[?]( arpk( N4, S4, arpk( N3, S3, arpk( N2, S2, arpk( N1, S1, Timmed1, Tbase ), Tbase ), Tbase ), Tbase ) & this, size_t ix4, size_t ix3, size_t ix2, size_t ix1 ) {
+        return this[ix4][ix3][ix2][ix1];
+}
 #endif

tests/array-collections/array-md-sbscr-cases.cfa

-              r79ba50c
+              r8614140
+}
+// common function body, working on parameter wxyz, but for wxyz being different types
+#define CHECK_NUM_SUBSCR_TYPE_COMPAT                                         \
+    valExpected = getMagicNumber(2, 3, 4, 5);                                \
+    assert(( wxyz[2] [3] [4] [5] == valExpected ));                          \
+    assert(( wxyz[2,  3] [4] [5] == valExpected ));                          \
+    assert(( wxyz[2] [3,  4] [5] == valExpected ));                          \
+    assert(( wxyz[2] [3] [4,  5] == valExpected ));                          \
+    assert(( wxyz[2,  3,  4] [5] == valExpected ));                          \
+    assert(( wxyz[2] [3,  4,  5] == valExpected ));                          \
+    assert(( wxyz[2,  3,  4,  5] == valExpected ));                          \
+    for ( i; Nw ) {                                                          \
+        assert(( wxyz[ i, 3, 4, 5 ] == getMagicNumber(i, 3, 4, 5) ));        \
+    }                                                                        \
+    for ( i; Nx ) {                                                          \
+        assert(( wxyz[ 2, i, 4, 5 ] == getMagicNumber(2, i, 4, 5) ));        \
+    }                                                                        \
+    for ( i; Ny ) {                                                          \
+        assert(( wxyz[ 2, 3, i, 5 ] == getMagicNumber(2, 3, i, 5) ));        \
+    }                                                                        \
+    for ( i; Nz ) {                                                          \
+        assert(( wxyz[ 2, 3, 4, i ] == getMagicNumber(2, 3, 4, i) ));        \
+    }
+#define CHECK_NUM_SUBSCR_TYPE_COMPAT_ADDENDUM_RESHAPE                        \
+    for ( i; Nw ) {                                                          \
+        assert(( wxyz[ i, all, 4, 5 ][3] == getMagicNumber(i, 3, 4, 5) ));   \
+    }                                                                        \
+    for ( i; Nw ) {                                                          \
+        assert(( wxyz[ all, 3, 4, 5 ][i] == getMagicNumber(i, 3, 4, 5) ));   \
+    }
+// Low abstraction: simple declaration, cannot send a slice, can make a slice, runs fast
+forall( [Nw], [Nx], [Ny], [Nz] )
+void test_numSubscrTypeCompatibility_lo( array( float, Nw, Nx, Ny, Nz ) & wxyz ) {
+    CHECK_NUM_SUBSCR_TYPE_COMPAT
+    CHECK_NUM_SUBSCR_TYPE_COMPAT_ADDENDUM_RESHAPE
+}
+// Medium abstraction: complex declaration, can send or make a slice, runs fast
+forall( [Nw], Sw*
+      , [Nx], Sx*
+      , [Ny], Sy*
+      , [Nz], Sz* )
+void test_numSubscrTypeCompatibility_mid(
+        arpk( Nw, Sw,
+        arpk( Nx, Sx,
+        arpk( Ny, Sy,
+        arpk( Nz, Sz, float, float)
+                           , float)
+                           , float)
+                           , float) & wxyz
+    ) {
+    CHECK_NUM_SUBSCR_TYPE_COMPAT
+    CHECK_NUM_SUBSCR_TYPE_COMPAT_ADDENDUM_RESHAPE
+}
+// High abstraction: mid-complexity declaration, can send a slice or a non-arpk, cannot make a slice, may not run fast
+forall( [Nw], Awxyz &
+      , [Nx], Axyz &
+      , [Ny], Ayz &
+      , [Nz], Az &
+      | ar( Awxyz, Axyz, Nw )
+      | ar( Axyz, Ayz, Nx )
+      | ar( Ayz, Az, Ny )
+      | ar( Az, float, Nz ) )
+void test_numSubscrTypeCompatibility_hi( Awxyz & wxyz ) {
+    CHECK_NUM_SUBSCR_TYPE_COMPAT
+}
 forall( [Nw], [Nx], [Ny], [Nz] )
 void test_numSubscrTypeCompatibility( tag(Nw), tag(Nx), tag(Ny), tag(Nz) ) {
 …
     fillHelloData(wxyz);
+    valExpected = getMagicNumber(2, 3, 4, 5);
+    assert(( wxyz [2] [3] [4] [5]  == valExpected ));
+    assert(( wxyz[2,  3][4] [5]  == valExpected ));
+    assert(( wxyz [2][3,  4][5]  == valExpected ));
+    assert(( wxyz [2] [3][4,  5] == valExpected ));
+    assert(( wxyz[2,  3,  4][5]  == valExpected ));
+    assert(( wxyz [2][3,  4,  5] == valExpected ));
+    assert(( wxyz[2,  3,  4,  5] == valExpected ));
+    for ( i; Nw ) {
+        assert(( wxyz[ i, 3, 4, 5 ] == getMagicNumber(i, 3, 4, 5) ));
+    }
+    for ( i; Nx ) {
+        assert(( wxyz[ 2, i, 4, 5 ] == getMagicNumber(2, i, 4, 5) ));
+    }
+    for ( i; Ny ) {
+        assert(( wxyz[ 2, 3, i, 5 ] == getMagicNumber(2, 3, i, 5) ));
+    }
+    for ( i; Nz ) {
+        assert(( wxyz[ 2, 3, 4, i ] == getMagicNumber(2, 3, 4, i) ));
+    }
+    for ( i; Nw ) {
+        assert(( wxyz[ i, all, 4, 5 ][3] == getMagicNumber(i, 3, 4, 5) ));
+    }
+    for ( i; Nw ) {
+        assert(( wxyz[ all, 3, 4, 5 ][i] == getMagicNumber(i, 3, 4, 5) ));
+    }
+    test_numSubscrTypeCompatibility_lo ( wxyz );
+    test_numSubscrTypeCompatibility_mid( wxyz );
+    test_numSubscrTypeCompatibility_hi ( wxyz );
+}

Context Navigation

Legend:

doc/theses/mike_brooks_MMath/Makefile

doc/theses/mike_brooks_MMath/array.tex

doc/theses/mike_brooks_MMath/background.tex

doc/theses/mike_brooks_MMath/plots/list-zoomout-noshuf.gp

doc/theses/mike_brooks_MMath/plots/list-zoomout-shuf.gp

doc/theses/mike_brooks_MMath/plots/string-peq-cppemu.gp

doc/theses/mike_brooks_MMath/plots/string-peq-sharing.gp

doc/theses/mike_brooks_MMath/plots/string-pta-sharing.gp

doc/theses/mike_brooks_MMath/programs/hello-accordion.cfa

doc/theses/mike_brooks_MMath/programs/hello-array.cfa

doc/theses/mike_brooks_MMath/programs/school1

doc/theses/mike_brooks_MMath/programs/school1.out

doc/theses/mike_brooks_MMath/programs/school2

doc/theses/mike_brooks_MMath/programs/school2.out

doc/theses/mike_brooks_MMath/programs/sharing-demo.cfa

doc/theses/mike_brooks_MMath/string.tex

doc/theses/mike_brooks_MMath/uw-ethesis-frontpgs.tex

libcfa/src/collections/array.hfa

tests/array-collections/array-md-sbscr-cases.cfa

Download in other formats: