Changeset 10a9479d for doc/theses

Timestamp:

Nov 23, 2024, 8:28:37 PM (14 months ago)

Author:

JiadaL <j82liang@…>

Branches:

master

Children:

956b389

Parents:

b006c51e (diff), de7b7a5 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.

Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

Location:

doc/theses

Files:

• fangren_yu_MMath/content1.tex (modified) (19 diffs)
• mike_brooks_MMath/Makefile (modified) (5 diffs)
• mike_brooks_MMath/array.tex (modified) (48 diffs)
• mike_brooks_MMath/background.tex (modified) (8 diffs)
• mike_brooks_MMath/pictures/memmgr-basic.pdf (added)
• mike_brooks_MMath/pictures/memmgr-basic.vsdx (added)
• mike_brooks_MMath/programs/hello-accordion.cfa (modified) (3 diffs)
• mike_brooks_MMath/programs/hello-array.cfa (modified) (1 diff)
• mike_brooks_MMath/programs/sharectx.run.cfa (moved) (moved from doc/theses/mike_brooks_MMath/programs/sharectx-demo.cfa )
• mike_brooks_MMath/programs/sharing-demo.cfa (modified) (23 diffs)
• mike_brooks_MMath/string.tex (modified) (13 diffs)
• mike_brooks_MMath/uw-ethesis.bib (modified) (2 diffs)
• mike_brooks_MMath/uw-ethesis.tex (modified) (2 diffs)

doc/theses/fangren_yu_MMath/content1.tex

@@ -1 @@
-\chapter{Recent Features Introduced to \CFA}
+\chapter{\CFA Features and Type System Interactions}
 \label{c:content1}
 
-This chapter discusses some recent additions to the \CFA language and their interactions with the type system.
+This chapter discusses \CFA feature introduced over time by multiple people and their interactions with the type system.
 
 
@@ -17 +17 @@
 Succinctly, if the address changes often, use a pointer;
 if the value changes often, use a reference.
-Note, \CC made its reference address immutable starting a \emph{belief} that immutability is a fundamental aspect of a reference's pointer.
-The results is asymmetry semantics between the pointer and reference.
+Java has mutable references but no pointers.
+\CC has mutable pointers but immutable references;
+hence, references match with functional programming.
+However, the consequence is asymmetry semantics between the pointer and reference.
 \CFA adopts a uniform policy between pointers and references where mutability is a separate property made at the declaration.
 
@@ -36 +38 @@
 Like pointers, reference can be cascaded, \ie a reference to a reference, \eg @&& r2@.\footnote{
 \CC uses \lstinline{&&} for rvalue reference, a feature for move semantics and handling the \lstinline{const} Hell problem.}
-Usage of a reference variable automatically performs the same number of dereferences as the number of references in its declaration, \eg @r3@ becomes @***r3@.
+Usage of a reference variable automatically performs the same number of dereferences as the number of references in its declaration, \eg @r2@ becomes @**r2@.
 Finally, to reassign a reference's address needs a mechanism to stop the auto-referencing, which is accomplished by using a single reference to cancel all the auto-dereferencing, \eg @&r3 = &y@ resets @r3@'s address to point to @y@.
 \CFA's reference type (including multi-de/references) is powerful enough to describe the lvalue rules in C by types only.
@@ -66 +68 @@
 int x = 3; $\C{// mutable}$
 const int cx = 5; $\C{// immutable}$
-int * const cp = &x, $\C{// immutable pointer}$
+int * const cp = &x, $\C{// immutable pointer pointer/reference}$
         & const cr = cx;
-const int * const ccp = &cx, $\C{// immutable value and pointer}$
+const int * const ccp = &cx, $\C{// immutable value and pointer/reference}$
                         & const ccr = cx;
-// pointer
+\end{cfa}
+\begin{cquote}
+\setlength{\tabcolsep}{26pt}
+\begin{tabular}{@{}lll@{}}
+pointer & reference & \\
+\begin{cfa}
 *cp = 7;
-cp = &x; $\C{// error, assignment of read-only variable}$
-*ccp = 7; $\C{// error, assignment of read-only location}$
-ccp = &cx; $\C{// error, assignment of read-only variable}$
-// reference
+cp = &x;
+*ccp = 7;
+ccp = &cx;
+\end{cfa}
+&
+\begin{cfa}
 cr = 7;
-cr = &x; $\C{// error, assignment of read-only variable}$
-*ccr = 7; $\C{// error, assignment of read-only location}$
-ccr = &cx; $\C{// error, assignment of read-only variable}$
-\end{cfa}
+cr = &x;
+*ccr = 7;
+ccr = &cx;
+\end{cfa}
+&
+\begin{cfa}
+// allowed
+// error, assignment of read-only variable
+// error, assignment of read-only location
+// error, assignment of read-only variable
+\end{cfa}
+\end{tabular}
+\end{cquote}
 Interestingly, C does not give a warning/error if a @const@ pointer is not initialized, while \CC does.
-Hence, type @& const@ is similar to \CC reference, but \CFA does not preclude initialization with a non-variable address.
+Hence, type @& const@ is similar to a \CC reference, but \CFA does not preclude initialization with a non-variable address.
 For example, in system's programming, there are cases where an immutable address is initialized to a specific memory location.
 \begin{cfa}
@@ -96 +114 @@
 However, there is an inherent ambiguity for auto-dereferencing: every argument expression involving a reference variable can potentially mean passing the reference's value or address.
 Without any restrictions, this ambiguity limits the behaviour of reference types in \CFA polymorphic functions, where a type @T@ can bind to a reference or non-reference type.
-This ambiguity prevents the type system treating reference types the same way as other types in many cases even if type variables could be bound to reference types.
+This ambiguity prevents the type system treating reference types the same way as other types, even if type variables could be bound to reference types.
 The reason is that \CFA uses a common \emph{object trait}\label{p:objecttrait} (constructor, destructor and assignment operators) to handle passing dynamic concrete type arguments into polymorphic functions, and the reference types are handled differently in these contexts so they do not satisfy this common interface.
 
 Moreover, there is also some discrepancy in how the reference types are treated in initialization and assignment expressions.
-For example, in line 3 of the previous example code \see{\VPageref{p:refexamples}}:
+For example, in line 3 of the example code on \VPageref{p:refexamples}:
 \begin{cfa}
 int @&@ r1 = x,  @&&@ r2 = r1,   @&&&@ r3 = r2; $\C{// references to x}$
@@ -129 +147 @@
 vector( int @&@ ) vec; $\C{// vector of references to ints}$
 \end{cfa}
-While it is possible to write a reference type as the argument to a generic type, it is disallowed in assertion checking, if the generic type requires the object trait \see{\VPageref{p:objecttrait}} for the type argument (a fairly common use case).
+While it is possible to write a reference type as the argument to a generic type, it is disallowed in assertion checking, if the generic type requires the object trait \see{\VPageref{p:objecttrait}} for the type argument, a fairly common use case.
 Even if the object trait can be made optional, the current type system often misbehaves by adding undesirable auto-dereference on the referenced-to value rather than the reference variable itself, as intended.
 Some tweaks are necessary to accommodate reference types in polymorphic contexts and it is unclear what can or cannot be achieved.
-Currently, there are contexts where \CFA programmer must use pointer types, giving up the benefits of auto-dereference operations and better syntax with reference types.
+Currently, there are contexts where \CFA programmer is forced to use a pointer type, giving up the benefits of auto-dereference operations and better syntax with reference types.
 
 
@@ -165 +183 @@
 Along with making returning multiple values a first-class feature, tuples were extended to simplify a number of other common context that normally require multiple statements and/or additional declarations, all of which reduces coding time and errors.
 \begin{cfa}
-[x, y, z] = 3; $\C[2in]{// x = 3; y = 3; z = 3, where types are different}$
+[x, y, z] = 3; $\C[2in]{// x = 3; y = 3; z = 3, where types may be different}$
 [x, y] = [y, x]; $\C{// int tmp = x; x = y; y = tmp;}$
 void bar( int, int, int );
@@ -212 +230 @@
 bar( t2 );                      $\C{// bar defined above}$
 \end{cfa}
-\VRef[Figure]{f:Nesting} shows The difference is nesting of structures and tuples.
+\VRef[Figure]{f:Nesting} shows the difference is nesting of structures and tuples.
 The left \CC nested-structure is named so it is not flattened.
 The middle C/\CC nested-structure is unnamed and flattened, causing an error because @i@ and @j@ are duplication names.
@@ -220 +238 @@
 
 \begin{figure}
-\setlength{\tabcolsep}{15pt}
+\setlength{\tabcolsep}{20pt}
 \begin{tabular}{@{}ll@{\hspace{90pt}}l@{}}
 \multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{C/\CC} & \multicolumn{1}{c}{tuple} \\
@@ -273 +291 @@
 As noted, tradition languages manipulate multiple values by in/out parameters and/or structures.
 K-W C adopted the structure for tuple values or variables, and as needed, the fields are extracted by field access operations.
-As well, For the tuple-assignment implementation, the left-hand tuple expression is expanded into assignments of each component, creating temporary variables to avoid unexpected side effects.
-For example, the tuple value returned from @foo@ is a structure, and its fields are individually assigned to a left-hand tuple, @x@, @y@, @z@, or copied directly into a corresponding tuple variable.
+As well, for the tuple-assignment implementation, the left-hand tuple expression is expanded into assignments of each component, creating temporary variables to avoid unexpected side effects.
+For example, the tuple value returned from @foo@ is a structure, and its fields are individually assigned to a left-hand tuple, @x@, @y@, @z@, \emph{or} copied directly into a corresponding tuple variable.
 
 In the second implementation of \CFA tuples by Rodolfo Gabriel Esteves~\cite{Esteves04}, a different strategy is taken to handle MVR functions.
@@ -286 +304 @@
 [x, y] = gives_two();
 \end{cfa}
-The Till K-W C implementation translates the program to:
+\VRef[Figure]{f:AlternateTupleImplementation} shows the two implementation approaches.
+In the left approach, the return statement is rewritten to pack the return values into a structure, which is returned by value, and the structure fields are indiviually assigned to the left-hand side of the assignment.
+In the right approach, the return statement is rewritten as direct assignments into the passed-in argument addresses.
+The right imlementation looks more concise and saves unnecessary copying.
+The downside is indirection within @gives_two@ to access values, unless values get hoisted into registers for some period of time, which is common.
+
+\begin{figure}
+\begin{cquote}
+\setlength{\tabcolsep}{20pt}
+\begin{tabular}{@{}ll@{}}
+Till K-W C implementation & Rodolfo \CFA implementation \\
 \begin{cfa}
 struct _tuple2 { int _0; int _1; }
-struct _tuple2 gives_two() { ... struct _tuple2 ret = { r1, r2 }, return ret; }
+struct _tuple2 gives_two() {
+        ... struct _tuple2 ret = { r1, r2 };
+        return ret;
+}
 int x, y;
 struct _tuple2 _tmp = gives_two();
 x = _tmp._0; y = _tmp._1;
 \end{cfa}
-while the Rodolfo implementation translates it to:
-\begin{cfa}
-void gives_two( int * r1, int * r2 ) { ... *r1 = ...; *r2 = ...; return; }
+&
+\begin{cfa}
+
+void gives_two( int * r1, int * r2 ) {
+        ... *r1 = ...; *r2 = ...;
+        return;
+}
 int x, y;
+
 gives_two( &x, &y );
 \end{cfa}
-and inside the body of the function @gives_two@, the return statement is rewritten as assignments into the passed-in argument addresses.
-This implementation looks more concise, and in the case of returning values having nontrivial types, \eg aggregates, this implementation saves unnecessary copying.
-For example,
-\begin{cfa}
-[ x, y ] gives_two();
-int x, y;
-[ x, y ] = gives_two();
-\end{cfa}
-becomes
-\begin{cfa}
-void gives_two( int &, int & );
-int x, y;
-gives_two( x, y );
-\end{cfa}
-eliminiating any copying in or out of the call.
-The downside is indirection within @gives_two@ to access values, unless values get hoisted into registers for some period of time, which is common.
+\end{tabular}
+\end{cquote}
+\caption{Alternate Tuple Implementation}
+\label{f:AlternateTupleImplementation}
+\end{figure}
 
 Interestingly, in the third implementation of \CFA tuples by Robert Schluntz~\cite[\S~3]{Schluntz17}, the MVR functions revert back to structure based, where it remains in the current version of \CFA.
 The reason for the reversion was to have a uniform approach for tuple values/variables making tuples first-class types in \CFA, \ie allow tuples with corresponding tuple variables.
-This extension was possible, because in parallel with Schluntz's work, generic types were being added independently by Moss~\cite{Moss19}, and the tuple variables leveraged the same implementation techniques as the generic variables.
+This extension was possible, because in parallel with Schluntz's work, generic types were added independently by Moss~\cite{Moss19}, and the tuple variables leveraged the same implementation techniques as the generic variables.
 \PAB{I'm not sure about the connection here. Do you have an example of what you mean?}
 
@@ -339 +364 @@
 \begin{cfa}
 void f( int, int );
-void f( [int, int] );
+void f( @[@ int, int @]@ );
 f( 3, 4 );  // ambiguous call
 \end{cfa}
@@ -358 +383 @@
 the call to @f@ can be interpreted as @T = [1]@ and @U = [2, 3, 4, 5]@, or @T = [1, 2]@ and @U = [3, 4, 5]@, and so on.
 The restriction ensures type checking remains tractable and does not take too long to compute.
-Therefore, tuple types are never present in any fixed-argument function calls.
-
-Finally, a type-safe variadic argument signature was added by Robert Schluntz~\cite[\S~4.1.2]{Schluntz17} using @forall@ and a new tuple parameter-type, denoted by the keyword @ttype @ in Schluntz's implementation, but changed to the ellipsis syntax similar to \CC's template parameter pack.
+Therefore, tuple types are never present in any fixed-argument function calls, because of the flattening.
+
+Finally, a type-safe variadic argument signature was added by Robert Schluntz~\cite[\S~4.1.2]{Schluntz17} using @forall@ and a new tuple parameter-type, denoted by the keyword @ttype@ in Schluntz's implementation, but changed to the ellipsis syntax similar to \CC's template parameter pack.
 For C variadics, \eg @va_list@, the number and types of the arguments must be conveyed in some way, \eg @printf@ uses a format string indicating the number and types of the arguments.
 \VRef[Figure]{f:CVariadicMaxFunction} shows an $N$ argument @maxd@ function using the C untyped @va_list@ interface.
@@ -370 +395 @@
 \begin{figure}
 \begin{cfa}
-double maxd( int @count@, ... ) {
+double maxd( int @count@, @...@ ) { // ellipse parameter
     double max = 0;
     va_list args;
@@ -566 +591 @@
 struct U u;  u.k;  u.l;
 \end{cfa}
-and the hoisted type names can clash with global types names.
+and the hoisted type names can clash with global type names.
 For good reasons, \CC chose to change this semantics:
 \begin{cquote}
@@ -584 +609 @@
 \end{cfa}
 \CFA chose to adopt the \CC non-compatible change for nested types, since \CC's change has already forced certain coding changes in C libraries that must be parsed by \CC.
+\CFA also added the ability to access from a variable through a type to a field.
+\begin{cfa}
+struct S s;  @s.T@.i;  @s.U@.k;
+\end{cfa}
 
 % https://gcc.gnu.org/onlinedocs/gcc/Unnamed-Fields.html
@@ -604 +633 @@
 \end{cfa}
 Note, the position of the substructure is normally unimportant, unless there is some form of memory or @union@ overlay.
-Like the anonymous nested types, the aggregate field names are hoisted into @struct S@, so there is direct access, \eg @s.x@ and @s.i@.
-However, like the implicit C hoisting of nested structures, the field names must be unique and the type names are now at a different scope level, unlike type nesting in \CC.
-In addition, a pointer to a structure is automatically converted to a pointer to an anonymous field for assignments and function calls, providing containment inheritance with implicit subtyping, \ie @U@ $\subset$ @S@ and @W@ $\subset$ @S@.
-For example:
+Like an anonymous nested type, a named nested Plan-9 type has its field names hoisted into @struct S@, so there is direct access, \eg @s.x@ and @s.i@.
+Hence, the field names must be unique, unlike \CC nested types, but the type names are at a nested scope level, unlike type nesting in C.
+In addition, a pointer to a structure is automatically converted to a pointer to an anonymous field for assignments and function calls, providing containment inheritance with implicit subtyping, \ie @U@ $\subset$ @S@ and @W@ $\subset$ @S@, \eg:
 \begin{cfa}
 void f( union U * u );
 void g( struct W * );
-union U * up;
-struct W * wp;
-struct S * sp;
-up = sp; $\C{// assign pointer to U in S}$
-wp = sp; $\C{// assign pointer to W in S}$
+union U * up;   struct W * wp;   struct S * sp;
+up = &s; $\C{// assign pointer to U in S}$
+wp = &s; $\C{// assign pointer to W in S}$
 f( &s ); $\C{// pass pointer to U in S}$
 g( &s ); $\C{// pass pointer to W in S}$
 \end{cfa}
-
-\CFA extends the Plan-9 substructure by allowing polymorphism for values and pointers.
-The extended substructure is denoted using @inline@, allowing backwards compatibility to existing Plan-9 features.
+Note, there is no value assignment, such as, @w = s@, to copy the @W@ field from @S@.
+
+Unfortunately, the Plan-9 designers did not lookahead to other useful features, specifically nested types.
+This nested type compiles in \CC and \CFA.
+\begin{cfa}
+struct R {
+        @struct T;@             $\C[2in]{// forward declaration, conflicts with Plan-9 syntax}$
+        struct S {              $\C{// nested types, mutually recursive reference}\CRT$
+                S * sp;   T * tp;  ...
+        };
+        struct T {
+                S * sp;   T * tp;  ...
+        };
+};
+\end{cfa}
+Note, the syntax for the forward declaration conflicts with the Plan-9 declaration syntax.
+
+\CFA extends the Plan-9 substructure by allowing polymorphism for values and pointers, where the extended substructure is denoted using @inline@.
 \begin{cfa}
 struct S {
-        @inline@ W;  $\C{// extended Plan-9 substructure}$
+        @inline@ struct W;  $\C{// extended Plan-9 substructure}$
         unsigned int tag;
         @inline@ U;  $\C{// extended Plan-9 substructure}$
 } s;
 \end{cfa}
-Note, like \CC, \CFA allows optional prefixing of type names with their kind, \eg @struct@, @union@, and @enum@, unless there is ambiguity with variable names in the same scope.
-The following shows both value and pointer polymorphism.
+Note, the declaration of @U@ is not prefixed with @union@.
+Like \CC, \CFA allows optional prefixing of type names with their kind, \eg @struct@, @union@, and @enum@, unless there is ambiguity with variable names in the same scope.
+In addition, a semi-non-compatible change is made so that Plan-9 syntax means a forward declaration in a nested type.
+Since the Plan-9 extension is not part of C and rarely used, this change has minimal impact.
+Hence, all Plan-9 semantics are denoted by the @inline@ qualifier, which good ``eye-candy'' when reading a structure definition to spot Plan-9 definitions.
+Finally, the following code shows the value and pointer polymorphism.
 \begin{cfa}
 void f( U, U * ); $\C{// value, pointer}$
 void g( W, W * ); $\C{// value, pointer}$
-U u, * up;
-S s, * sp;
-W w, * wp;
-u = s;  up = sp; $\C{// value, pointer}$
-w = s;  wp = sp; $\C{// value, pointer}$
+U u, * up;   S s, * sp;   W w, * wp;
+u = s;   up = sp; $\C{// value, pointer}$
+w = s;   wp = sp; $\C{// value, pointer}$
 f( s, &s ); $\C{// value, pointer}$
 g( s, &s ); $\C{// value, pointer}$
@@ -645 +688 @@
 In general, non-standard C features (@gcc@) do not need any special treatment, as they are directly passed through to the C compiler.
 However, the Plan-9 semantics allow implicit conversions from the outer type to the inner type, which means the \CFA type resolver must take this information into account.
-Therefore, the \CFA translator must implement the Plan-9 features and insert necessary type conversions into the translated code output.
+Therefore, the \CFA resolver must implement the Plan-9 features and insert necessary type conversions into the translated code output.
 In the current version of \CFA, this is the only kind of implicit type conversion other than the standard C conversions.
 
-Since variable overloading is possible in \CFA, \CFA's implementation of Plan-9 polymorphism allows duplicate field names.
-When an outer field and an embedded field have the same name and type, the inner field is shadowed and cannot be accessed directly by name.
-While such definitions are allowed, duplicate field names is not good practice in general and should be avoided if possible.
-Plan-9 fields can be nested, and a struct definition can contain multiple Plan-9 embedded fields.
-In particular, the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91}  can occur and result in a nested field to be embedded twice.
+Plan-9 polymorphism can result in duplicate field names.
+For example, the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91} can result in nested fields being embedded twice.
 \begin{cfa}
 struct A { int x; };
@@ -658 +698 @@
 struct C { inline A; };
 struct D {
-        inline B;
-        inline C;
-};
-D d;
-\end{cfa}
-In the above example, the expression @d.x@ becomes ambiguous, since it can refer to the indirectly embedded field either from @B@ or from @C@.
-It is still possible to disambiguate the expression by first casting the outer struct to one of the directly embedded type, such as @((B)d).x@.
+        inline B;  // B.x
+        inline C;  // C.x
+} d;
+\end{cfa}
+Because the @inline@ structures are flattened, the expression @d.x@ is ambiguous, as it can refer to the embedded field either from @B@ or @C@.
+@gcc@ generates a syntax error about the duplicate member @x@.
+The equivalent \CC definition compiles:
+\begin{c++}
+struct A { int x; };
+struct B : public A {};
+struct C : public A {};
+struct D : @public B, C@ {  // multiple inheritance
+} d;
+\end{c++}
+and again the expression @d.x@ is ambiguous.
+While \CC has no direct syntax to disambiguate @x@, \ie @d.B.x@ or @d.C.x@, it is possible with casts, @((B)d).x@ or @((C)d).x@.
+Like \CC, \CFA compiles the Plan-9 version and provides direct syntax and casts to disambiguate @x@.
+While ambiguous definitions are allowed, duplicate field names is poor practice and should be avoided if possible.
+However, when a programmer does not control all code, this problem can occur and a naming workaround should exist.

doc/theses/mike_brooks_MMath/Makefile

@@ -10 +10 @@
 TeXSRC = ${wildcard *.tex}
 PicSRC = ${notdir ${wildcard ${Pictures}/*.png}}
-DemoSRC = ${notdir ${wildcard ${Programs}/*-demo.cfa}}
+DemoPgmSRC = ${notdir ${wildcard ${Programs}/*-demo.cfa}}
 PgmSRC = ${notdir ${wildcard ${Programs}/*}}
 RunPgmSRC = ${notdir ${wildcard ${Programs}/*.run.*}}
@@ -24 +24 @@
 BASE = ${basename ${DOCUMENT}}                  # remove suffix
 
-DemoTex = ${DemoSRC:%.cfa=${Build}/%.tex} 
 RunPgmExe = ${addprefix ${Build}/,${basename ${basename ${RunPgmSRC}}}}
 RunPgmOut = ${RunPgmExe:%=%.out}
+DemoPgmExe = ${addprefix ${Build}/,${basename ${basename ${DemoPgmSRC}}}}
+DemoPgmOut = ${DemoPgmExe:%=%.out}
 
 # Commands
@@ -38 +39 @@
 # Rules and Recipes
 
-.PHONY : all fragments_ran clean                        # not file names
-.PRECIOUS : ${Build}/% ${Build}/%-demo      # don't delete intermediates
+.PHONY : all clean                              # not file names
+.SECONDARY:
+#.PRECIOUS : ${Build}/%                         # don't delete intermediates
 .ONESHELL :
 
-all : fragments_ran ${DOCUMENT}
-
-fragments_ran : $(RunPgmOut)
+all : ${DOCUMENT}
 
 clean :
@@ -51 +51 @@
 # File Dependencies
 
-%.pdf : ${TeXSRC} ${DemoTex} ${PicSRC} ${PgmSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
+%.pdf : ${TeXSRC} $(RunPgmOut) ${DemoPgmOut} ${PicSRC} ${BibSRC} ${BibRep}/pl.bib ${LaTMac}/common.tex Makefile | ${Build}
         ${LaTeX} ${BASE}
         ${BibTeX} ${Build}/${BASE}
@@ -64 +64 @@
         mkdir -p $@
 
-%-demo.tex: %-demo | ${Build}
-        $< > $@
+${Build}/%-demo: ${Programs}/%-demo.cfa | ${Build}
+        ${CFA} $< -o $@
 
-${Build}/%-demo: ${Programs}/%-demo.cfa | ${Build}
+${Build}/%: ${Programs}/%-demo.cfa | ${Build}
         ${CFA} $< -o $@
 

doc/theses/mike_brooks_MMath/array.tex

@@ -2 +2 @@
 \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.
+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}.
+
+Offering the @array@ type, as a distinct alternative to the C array, is consistent with \CFA's goal of backwards compatibility, \ie virtually all existing C (@gcc@) programs can be compiled by \CFA with only a small number of changes, similar to \CC (@g++@).
+However, a few compatibility-breaking changes to the behaviour of the C array are necessary, both as an implementation convenience and to fix C's lax treatment of arrays.
+Hence, the @array@ type is an opportunity to start from a clean slate and show a cohesive selection of features, making it unnecessary to deal with every inherited complexity of the C array.
+
 
 \section{Introduction}
 \label{s:ArrayIntro}
 
-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.
-This chapter describes the new \CFA language and library features that introduce a length-checked array type to the \CFA standard library~\cite{Cforall}.
-
-Specifically, a new \CFA array is declared by instantiating the generic @array@ type,
-much like instantiating any other standard-library generic type (such as @dlist@),
+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.
 \begin{cfa}
@@ -16 +20 @@
 \end{cfa}
 Here, the arguments to the @array@ type are @float@ (element type) and @99@ (length).
-When this type is used as a function parameter, the type-system requires that a call's argument matches, down to the length.
+When this type is used as a function parameter, the type-system requires that a call's argument is a perfect match.
 \begin{cfa}
 void f( @array( float, 42 )@ & p ) {}   $\C{// p accepts 42 floats}$
-f( x );                                                                 $\C{// statically rejected: types are different, 99 != 42}$
+f( x );                                                                 $\C{// statically rejected: type lengths are different, 99 != 42}$
 
 test2.cfa:3:1 error: Invalid application of existing declaration(s) in expression.
@@ -25 +29 @@
 \end{cfa}
 Here, the function @f@'s parameter @p@ is declared with length 42.
-The call @f( x )@, with the argument being the previously-declared object, is invalid, because the @array@ lengths @99@ and @42@ do not match.
-
-A function declaration can be polymorphic over these @array@ arguments by using the @forall@ declaration prefix.
-This function @g@'s takes arbitrary type parameter @T@ (familiar) and \emph{dimension parameter} @N@ (new).
-A dimension paramter represents a to-be-determined count of elements, managed by the type system.
+However, the call @f( x )@ is invalid, because @x@'s length is @99@, which does not match @42@.
+
+A function declaration can be polymorphic over these @array@ arguments by using the \CFA @forall@ declaration prefix.
 \begin{cfa}
 forall( T, @[N]@ )
@@ -40 +42 @@
 Cforall Runtime error: subscript 1000 exceeds dimension range [0,99) $for$ array 0x555555558020.
 \end{cfa}
+Function @g@ takes an arbitrary type parameter @T@ and a \emph{dimension parameter} @N@.
+A dimension parameter represents a to-be-determined count of elements, managed by the type system.
 The call @g( x, 0 )@ is valid because @g@ accepts any length of array, where the type system infers @float@ for @T@ and length @99@ for @N@.
-Inferring values for @T@ and @N@ is implicit, without programmer involvement.
+Inferring values for @T@ and @N@ is implicit.
 Furthermore, in this case, the runtime subscript @x[0]@ (parameter @i@ being @0@) in @g@ is valid because 0 is in the dimension range $[0,99)$ of argument @x@.
-The call @g( x, 1000 )@ is also accepted through compile time;
+However, the call @g( x, 1000 )@ is also accepted through compile time;
 however, this case's subscript, @x[1000]@, generates an error, because @1000@ is outside the dimension range $[0,99)$ of argument @x@.
+In general, the @forall( ..., [N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and within a function.
+The syntactic form is chosen to parallel other @forall@ forms:
+\begin{cfa}
+forall( @[N]@ ) ...     $\C[1.5in]{// dimension}$
+forall( T ) ...         $\C{// value datatype (formerly, "otype")}$
+forall( T & ) ...       $\C{// opaque datatype (formerly, "dtype")}\CRT$
+\end{cfa}
+% The notation @array(thing, N)@ is a single-dimensional case, giving a generic type instance.
 
 The generic @array@ type is comparable to the C array type, which \CFA inherits from C.
 Their runtime characteristics are often identical, and some features are available in both.
-For example, assume a caller instantiates @N@ with 42 (discussion about how to follow) in:
+For example, assume a caller has an argument that instantiates @N@ with 42.
 \begin{cfa}
 forall( [N] )
-void declDemo() {
+void declDemo( ... ) {
         float x1[N];                                            $\C{// built-in type ("C array")}$
         array(float, N) x2;                                     $\C{// type from library}$
@@ -59 +71 @@
 The two variables have identical size and layout; they both encapsulate 42-float stack allocations, with no additional ``bookkeeping'' allocations or headers.
 Providing this explicit generic approach requires a significant extension to the \CFA type system to support a full-feature, safe, efficient (space and time) array-type, which forms the foundation for more complex array forms in \CFA.
-
-Admittedly, the @array@ library type (type for @x2@) is syntactically different from its C counterpart.
-A future goal (TODO xref) is to provide the new features upon a built-in type whose syntax approaches C's (declaration style of @x1@).
+In all following discussion, ``C array'' means the types like that of @x@ and ``\CFA array'' means the standard-library @array@ type (instantiations), like the type of @x2@.
+
+Admittedly, the @array@ library type for @x2@ is syntactically different from its C counterpart.
+A future goal (TODO xref) is to provide the new @array@ features with syntax approaching C's (declaration style of @x1@).
 Then, the library @array@ type could be removed, giving \CFA a largely uniform array type.
-At present, the C-syntax array gets partial support for the new features, so the generic @array@ is used exclusively when introducing features;
+At present, the C-syntax @array@ is only partially supported, so the generic @array@ is used exclusively in the thesis;
 feature support and C compatibility are revisited in Section ? TODO.
-
-Offering the @array@ type, as a distinct alternative to the C array, is consistent with \CFA's goal of backwards compatibility, \ie virtually all existing C (@gcc@) programs can be compiled by \CFA with only a small number of changes, similar to \CC (@g++@).
-However, a few compatibility-breaking changes to the behaviour of the C array are necessary, both as an implementation convenience and to fix C's lax treatment of arrays.
-Hence, the @array@ type is an opportunity to start from a clean slate and show a cohesive selection of features, making it unnecessary to deal with every inherited complexity of the C array.
-
-In all discussion following, ``C array'' means the types like that of @x@ and ``\CFA array'' means the standard-library @array@ type (instantiations), like the type of @x2@.
 
 My contributions in this chapter are:
@@ -83 +90 @@
 
 
-\section{Definitions and design considerations}
-
-
-\subsection{Dependent typing}
-
-
-
-General dependent typing allows the type system to encode arbitrary predicates (e.g. behavioural specifications for functions),
+\section{Dependent typing}
+
+General dependent typing allows the type system to encode arbitrary predicates (\eg behavioural specifications for functions),
 which is an anti-goal for my work.
 Firstly, this application is strongly associated with pure functional languages,
@@ -101 +103 @@
 
 
-
 \section{Features added}
 
@@ -109 +110 @@
 By declaring type variables at the front of object declarations, an array dimension is lexically referenceable where it is needed.
 For example, a declaration can share one length, @N@, among a pair of parameters and the return,
-meaning that it requires both input arrays to be of the same length, and guarantees that the result with be of that length as well.
+meaning that it requires both input arrays to be of the same length, and guarantees that the result is of that length as well.
 \lstinput{10-17}{hello-array.cfa}
-This function @f@ does a pointwise comparison of its two input arrays, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated @bool@ array.
-The dynamic allocation of the @ret@ array by preexisting @alloc@ uses the parameterized dimension information implicitly within its @sizeof@ determination, and casts the return type.
-Note that alloc only sees one whole type for its @T@ (which is @f@'s @array(bool, N)@); this type's size is a computation based on @N@.
-\begin{cfa}
-// simplification
-static inline forall( T & | sized(T) )
+Function @f@ does a pointwise comparison of its two input arrays, checking if each pair of numbers is within half a percent of each other, returning the answers in a newly allocated @bool@ array.
+The dynamic allocation of the @ret@ array, by the library @alloc@ function,
+\begin{cfa}
+forall( T & | sized(T) )
 T * alloc() {
-        return (T *)malloc( sizeof(T) );
-}
-\end{cfa}
-This example illustrates how the new @array@ type plugs into existing \CFA behaviour by implementing necessary @sized@ assertions needed by other types.
-(@sized@ implies a concrete \vs abstract type with a runtime-available size, exposed as @sizeof@.)
+        return @(T *)@malloc( @sizeof(T)@ );
+}
+\end{cfa}
+uses the parameterized dimension information implicitly within its @sizeof@ determination, and casts the return type.
+Note that @alloc@ only sees one whole type for its @T@ (which is @f@'s @array(bool, N)@); this type's size is a computation based on @N@.
+This example illustrates how the new @array@ type plugs into existing \CFA behaviour by implementing necessary \emph{sized} assertions needed by other types.
+(\emph{sized} implies a concrete \vs abstract type with a runtime-available size, exposed as @sizeof@.)
 As a result, there is significant programming safety by making the size accessible and implicit, compared with C's @calloc@ and non-array supporting @memalign@, which take an explicit length parameter not managed by the type system.
 
@@ -142 +143 @@
 The result is a significant improvement in safety and usability.
 
-In general, the @forall( ..., [N] )@ participates in the user-relevant declaration of the name @N@, which becomes usable in parameter/return declarations and within a function.
-The syntactic form is chosen to parallel other @forall@ forms:
-\begin{cfa}
-forall( @[N]@ ) ...     $\C[1.5in]{// dimension}$
-forall( T & ) ...       $\C{// opaque datatype (formerly, "dtype")}$
-forall( T ) ...         $\C{// value datatype (formerly, "otype")}\CRT$
-\end{cfa}
-% The notation @array(thing, N)@ is a single-dimensional case, giving a generic type instance.
 In summary:
 \begin{itemize}
@@ -168 +161 @@
 % agreed, though already said
 \item
-\CC does not allow a template function to be nested, while \CFA lests its polymorphic functions to be nested.
+\CC does not allow a template function to be nested, while \CFA lets its polymorphic functions to be nested.
 % why is this important?
 \item
@@ -227 +220 @@
 \end{cfa}
 \end{tabular}
-\caption{\lstinline{N}-style paramters, for \CC template \vs \CFA generic type }
+\caption{\lstinline{N}-style parameters, for \CC template \vs \CFA generic type }
 \label{f:TemplateVsGenericType}
 \end{figure}
 
 Just as the first example in \VRef[Section]{s:ArrayIntro} shows a compile-time rejection of a length mismatch,
-so are length mismatches stopped when they invlove dimension parameters.
+so are length mismatches stopped when they involve dimension parameters.
 While \VRef[Figure]{f:fHarness} shows successfully calling a function @f@ expecting two arrays of the same length,
 \begin{cfa}
 array( bool, N ) & f( array( float, N ) &, array( float, N ) & );
 \end{cfa}
-a static rejection occurs when attempting to call @f@ with arrays of potentially differing lengths.
+a static rejection occurs when attempting to call @f@ with arrays of differing lengths.
 \lstinput[tabsize=1]{70-74}{hello-array.cfa}
 When the argument lengths themselves are statically unknown,
@@ -252 +245 @@
 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 for element types.
+Preexisting \CFA allowed aggregate types to be generalized with type parameters, enabling parameterizing of element types.
 Now, \CFA also allows parameterizing them by length.
 Doing so gives a refinement of C's ``flexible array member'' pattern[TODO: cite ARM 6.7.2.1 pp18]\cite{arr:gnu-flex-mbr}.
@@ -259 +252 @@
 This flexibility, in turn, allows for multiple array members.
 \lstinput{10-15}{hello-accordion.cfa}
-This structure's layout has the starting offset of @studentIds@ varying according to the generic parameter @C@, and the offset of @preferences@ varying according to both generic parameters.
-
-The school example has the data structure capturing many students' course-preference forms.
-It has course- and student-level metadata (their respective display names) and a position-based preferecens' matrix.
-The input files in \VRef[Figure]{f:checkHarness} give example data.
-
-When a function operates on a @School@ structure, the type system handles its memory layout transparently.
-\lstinput{30-37}{hello-accordion.cfa}
-In the running example, this @getPref@ function answers,
-for the student at position @sIx@, what is the position of its @pref@\textsuperscript{th}-favoured class?
-
-\VRef[Figure]{f:checkHarness} shows the @School@ harness and results with different array sizes.
-This example program prints the courses in each student's preferred order, all using the looked-up display names.
-Note the declaration of the @school@ variable.
+The structure has course- and student-level metatdata (their respective field names) and a position-based preferences' matrix.
+Its layout has the starting offset of @studentIds@ varying according to the generic parameter @C@, and the offset of @preferences@ varying according to both generic parameters.
+
+\VRef[Figure]{f:checkHarness} shows a program main using @School@ and results with different array sizes.
+The @school@ variable holds many students' course-preference forms.
 It is on the stack and its initialization does not use any casting or size arithmetic.
 Both of these points are impossible with a C flexible array member.
@@ -280 +264 @@
 \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.
+The example program prints the courses in each student's preferred order, all using the looked-up display names.
 
 \begin{figure}
-% super hack to get this to line up
-\begin{tabular}{@{}ll@{\hspace{25pt}}l@{}}
-\begin{tabular}{@{}p{3.25in}@{}}
+\begin{cquote}
 \lstinput{50-55}{hello-accordion.cfa}
-\vspace*{-3pt}
 \lstinput{90-98}{hello-accordion.cfa}
-\end{tabular}
-&
-\raisebox{0.32\totalheight}{%
-}%
-&
-\end{tabular}
-
-TODO: Get Peter's layout help
-
-\$ cat school1
-
+\ \\
+@$ cat school1@
 \lstinput{}{school1}
 
-\$ ./a.out < school1
-
+@$ ./a.out < school1@
 \lstinput{}{school1.out}
 
-\$ cat school2
-
+@$ cat school2@
 \lstinput{}{school2}
 
-\$ ./a.out < school2
-
+@$ ./a.out < school2@
 \lstinput{}{school2.out}
+\end{cquote}
 
 \caption{\lstinline{School} harness, input and output}
 \label{f:checkHarness}
 \end{figure}
+
+When a function operates on a @School@ structure, the type system handles its memory layout transparently.
+\lstinput{30-37}{hello-accordion.cfa}
+In the example, this @getPref@ function answers, for the student at position @is@, what is the position of its @pref@\textsuperscript{th}-favoured class?
 
 
@@ -333 +308 @@
 But simplifications close enough for the present discussion are:
 \begin{cfa}
-        forall( [N] )
-        struct array_1d_float {
-                float items[N];
-        };
-        forall( T, [N] )
-        struct array_1d {
-                T items[N];
-        };
-\end{cfa}
-This structure pattern, plus a subscript operator, is all that @array@ provides.
+forall( [N] )
+struct array_1d_float {
+        float items[N];
+};
+forall( T, [N] )
+struct array_1d_T {
+        T items[N];
+};
+\end{cfa}
+These two structure patterns, plus a subscript operator, is all that @array@ provides.
 
 My main work is letting a programmer define
-such a structre (one whose type is parameterized by @[N]@)
+such a structure (one whose type is parameterized by @[N]@)
 and functions that operate on it (these being similarly parameterized).
 
@@ -351 +326 @@
 \begin{itemize}
 \item
-        The resolver, providing values for a used declaration's type-system variables,
+        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.
         Notably, it conveys the size of a type @foo@ as a @__sizeof_foo@ parameter,
-        and rewrites the @sizeof(foo)@ expression as @__sizeof_foo@, i.e. a use of the parameter.
+        and rewrites the @sizeof(foo)@ expression as @__sizeof_foo@, \ie a use of the parameter.
 \end{itemize}
 
@@ -364 +338 @@
 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.
-The discussion following explains the desugaring and how correct lowered code results.
-
-An even simpler structure, and a toy function on it, demonstrate what's needed for the encoding.
-\begin{cfa}
-        forall( [@N@] ) { // [1]
-                struct thing {};
-                void f( thing(@N@) ) { sout | @N@; } // [2], [3]
-        }
-        int main() {
-                thing( @10@ ) x;  f(x);  // prints 10, [4]
-                thing( 100 ) y;  f(y);  // prints 100
-                return 0;
-        }
+The following discussion explains the desugaring and how correctly lowered code results.
+
+A simpler structure, and a toy function on it, demonstrate what is needed for the encoding.
+\begin{cfa}
+forall( [@N@] ) { $\C{// [1]}$
+        struct thing {};
+        void f( thing(@N@) ) { sout | @N@; } $\C{// [2], [3]}$
+}
+int main() {
+        thing( @10@ ) x;  f( x );  $\C{// prints 10, [4]}$
+        thing( 100 ) y;  f( y );  $\C{// prints 100}$
+        return 0;
+}
 \end{cfa}
 This example has:
@@ -389 +363 @@
         A value like 10 being used as an argument to the parameter @N@.
 \end{enumerate}
-The chosen solution being to encode the value @N@ \emph{as a type}, items 1 and 2 are immediately available for free.
+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 4 needs a way to produce a type that encodes the given value.
@@ -400 +374 @@
 \item
         Given a dimension expression $e$, produce type @char[@$e$@]@ to represent it.
-        If $e$ evaluates to $n$ then the endoded type has size $n$.
+        If $e$ evaluates to $n$ then the encoded type has size $n$.
 \item
         Given a type $T$ (produced by these rules), recover the value that it represents with the expression @sizeof(@$T$@)@.
@@ -410 +384 @@
 The running example is lowered to:
 \begin{cfa}
-        forall( @N*@ ) { // [1]
-                struct thing {};
-                void f( thing(@N@) ) { sout | @sizeof(N)@; } // [2], [3]
-        }
-        int main() {
-                thing( char[@10@] ) x;  f(x);  // prints 10, [4]
-                thing( char[100] ) y;  f(y);  // prints 100
-                return 0;
-        }
+forall( @N *@ ) { $\C{// [1]}$
+        struct thing {};
+        void f( thing(@N@) ) { sout | @sizeof(N)@; } $\C{// [2], [3]}$
+}
+int main() {
+        thing( char[@10@] ) x;  f( x );  $\C{// prints 10, [4]}$
+        thing( char[100] ) y;  f( y );  $\C{// prints 100}$
+        return 0;
+}
 \end{cfa}
 Observe:
@@ -430 +404 @@
         The @sout...@ expression (being an application of the @?|?@ operator) has a second argument that is an ordinary expression.
 \item
-        The type of variable @x@ is another @thing(-)@ type;  the argument to the generic @thing@ is a type (array type).
+        The type of variable @x@ is another @thing(-)@ type; the argument to the generic @thing@ is a type (array type of bytes, @char@).
 \end{enumerate}
 
 From this point, preexisting \CFA compilation takes over lowering it the rest of the way to C.
-Inspecting the result shows what the above translation achieves.
-A form that shows only the relevant changes of the box pass (as informed by the resolver), leaving the rest unadulterated, is:
-\begin{cfa}
-        // [1]
-        void f( size_t __sizeof_N, @void *@ ) { sout | @__sizeof_N@; } // [2], [3]
-        int main() {
-                struct __conc_thing_10 {} x;  f(@10@, &x);  // prints 10, [4]
-                struct __conc_thing_100 {} y;  f(@100@, &y);  // prints 100
-                return 0;
-        }
+Here the result shows only the relevant changes of the box pass (as informed by the resolver), leaving the rest unadulterated:
+\begin{cfa}
+// [1]
+void f( size_t __sizeof_N, @void *@ ) { sout | @__sizeof_N@; } $\C{// [2], [3]}$
+int main() {
+        struct __conc_thing_10 {} x;  f( @10@, &x );  $\C{// prints 10, [4]}$
+        struct __conc_thing_100 {} y;  f( @100@, &y );  $\C{// prints 100}$
+        return 0;
+}
 \end{cfa}
 Observe:
@@ -452 +425 @@
         The type @thing(N)@ is (replaced by @void *@, but thereby effectively) gone.
 \item
-        The @sout...@ expression (being an application of the @?|?@ operator) has a second argument that is a regular variable (parameter) usage.
+        The @sout...@ expression (being an application of the @?|?@ operator) has a regular variable (parameter) usage for its second argument.
 \item
         Information about the particular @thing@ instantiation (value 10) has moved, from the type, to a regular function-call argument.
 \end{enumerate}
-At the end of the desugaring and downstream processing, the original C idiom of ``pass both a pointer and a length parameter'' has been reconstructed.
-In the programmer-written form, only the thing is passed.
+At the end of the desugaring and downstream processing, the original C idiom of ``pass both a length parameter and a pointer'' has been reconstructed.
+In the programmer-written form, only the @thing@ is passed.
 The compiler's action produces the more complex form, which if handwritten, would be error-prone.
 
-Back at the very front end, the parsing changes, AST schema extensions, and validation rules for enabling the sugared user input are:
+Back at the compiler front end, the parsing changes AST schema extensions and validation rules for enabling the sugared user input.
 \begin{itemize}
 \item
@@ -467 +440 @@
         Have the new brand of type-variable, \emph{Dimension}, in the AST form of a type-variable, to represent one parsed from @[-]@.
 \item
-        Allow a type variable to occur in expression position.  Validate (after parsing) that only dimension-branded type variables are used here.
+        Allow a type variable to occur in an expression.  Validate (after parsing) that only dimension-branded type variables are used here.
 \item
         Allow an expression to occur in type-argument position.  Brand the resulting type argument as a dimension.
@@ -473 +446 @@
         Validate (after parsing), on a generic-type usage, \eg the type part of the declaration
         \begin{cfa}
-                @array_1d( foo, bar ) x;@
+        array_1d( foo, bar ) x;
         \end{cfa}
+        \vspace*{-10pt}
         that the brands on the generic arguments match the brands of the declared type variables.
         Here, that @foo@ is a type and @bar@ is a dimension.
@@ -488 +462 @@
 from one party who knows it, to another who is willing to work with any given length.
 For scenarios where the concern is a mishandled length,
-the interaction is between two parties who both claim to know (something about) it.
-Such a scenario occurs in this pure C fragment, wich today's C compilers accept:
-\begin{cfa}
-        int n = @42@;
-        float x[n];
-        float (*xp)[@999@] = &x;
-        (*xp)[@500@];  // in "bound"?
-\end{cfa}
-
+the interaction is between two parties who both claim to know something about it.
+Such a scenario occurs in this pure C fragment, which today's C compilers accept:
+\begin{cfa}
+int n = @42@;
+float x[n];
+float (*xp)[@999@] = &x;
+(*xp)[@500@]; $\C{// in "bound"?}$
+\end{cfa}
 Here, the array @x@ has length 42, while a pointer to it (@xp@) claims length 999.
 So, while the subscript of @xp@ at position 500 is out of bound of its referent @x@,
@@ -505 +478 @@
 The \CFA new-array rejects the analogous case:
 \begin{cfa}
-        int n = @42@;
-        array(float, n) x;
-        array(float, 999) * xp = x; // static rejection here
-        (*xp)[@500@]; // runtime check vs len 999
-\end{cfa}
-
-% TODO: kill the vertical whitespace around these lists
-% nothing from https://stackoverflow.com/questions/1061112/eliminate-space-before-beginitemize is working
-
-The way the \CFA array is implemented,
-the type analysis of this \CFA case reduces to a case similar to the earlier C version.
+int n = @42@;
+array(float, n) x;
+array(float, 999) * xp = x; $\C{// static rejection here}$
+(*xp)[@500@]; $\C{// runtime check vs len 999}$
+\end{cfa}
+The way the \CFA array is implemented, the type analysis of this case reduces to a case similar to the earlier C version.
 The \CFA compiler's compatibility analysis proceeds as:
-\begin{itemize}[noitemsep,partopsep=-\parskip,parsep=0pt,leftmargin=4em]
+\begin{itemize}[parsep=0pt]
 \item
         Is @array(float, 999)@ type-compatible with @array(float, n)@?
 \item
-        Is @arrayX(float, char[999])@ type-compatible with @arrayX(float, char[n])@?
-        \footnote{Here, \lstinline{arrayX} represents the type that results
+        Is @arrayX(float, char[999])@ type-compatible with @arrayX(float, char[n])@?\footnote{
+                Here, \lstinline{arrayX} represents the type that results
                 from desugaring the \lstinline{array} type
                 into a type whose generic parameters are all types.
@@ -531 +499 @@
         Is @char[999]@ type-compatible with @char[n]@?
 \end{itemize}
-
-I chose to achieve the necessary rejection of the \CFA case
-by adding a rejection of the corresponding C case.
-
-This decision is not backward compatible.
+To achieve the necessary \CFA rejections meant rejecting the corresponding C case, which is not backward compatible.
 There are two complementary mitigations for this incompatibility.
 
@@ -542 +506 @@
 This situation might arise if @n@ were known to be 999,
 rather than 42, as in the introductory examples.
-The programmer can add a cast, as in:
-\begin{cfa}
-        xp = ( float (*)[999] ) & x;
-\end{cfa}
-This addition causes \CFA to accept, beacause now, the programmer has accepted blame.
+The programmer can add a cast in the \CFA code.
+\begin{cfa}
+xp = @(float (*)[999])@ &x;
+\end{cfa}
+This addition causes \CFA to accept, because now, the programmer has accepted blame.
 This addition is benign in plain C, because the cast is valid, just unnecessary there.
 Moreover, the addition can even be seen as appropriate ``eye candy,''
@@ -556 +520 @@
 Second, the incompatibility only affects types like pointer-to-array,
 which are are infrequently used in C.
-The more common C idiom for aliasing an array is to use the pointer-to-first-element type,
-which does not participate in the \CFA array's length checking.
-\footnote{Notably, the desugaring of the \lstinline{array@} type,
-        avoids letting any \lstinline{-[-]} type decay,
-        in order to preserve the length information that powers runtime bound checking.}
-Therefore, the frequency of needing to upgrade wild C code (as discussed in the first mitigation)
+The more common C idiom for aliasing an array is to use a pointer-to-first-element type,
+which does not participate in the \CFA array's length checking.\footnote{
+        Notably, the desugaring of the \lstinline{array} type avoids letting any \lstinline{-[-]} type decay,
+        in order to preserve the length information that powers runtime bound-checking.}
+Therefore, the frequency of needing to upgrade legacy C code (as discussed in the first mitigation)
 is anticipated to be low.
 
 Because the incompatibility represents a low cost to a \CFA onboarding effort
 (with a plausible side benefit of linting the original code for a missing annotation),
-I elected not to add special measures to retain the compatibility.
+no special measures were added to retain the compatibility.
 It would be possible to flag occurrences of @-[-]@ types that come from @array@ desugaring,
 treating those with stricter \CFA rules, while treating others with classic C rules.
@@ -573 +536 @@
 
 Having allowed that both the initial C example's check
-\begin{itemize}[noitemsep,partopsep=-\parskip,parsep=0pt,leftmargin=4em]
+\begin{itemize}
         \item
                 Is @float[999]@ type-compatible with @float[n]@?
 \end{itemize}
-and the second \CFA exmple's induced check
-\begin{itemize}[noitemsep,partopsep=-\parskip,parsep=0pt,leftmargin=4em]
+and the second \CFA example's induced check
+\begin{itemize}
         \item
                 Is @char[999]@ type-compatible with @char[n]@?
@@ -587 +550 @@
 To implement the new \CFA rules, I took the syntactic recursion a step further, obtaining,
 in both cases:
-\begin{itemize}[noitemsep,partopsep=-\parskip,parsep=0pt,leftmargin=4em]
+\begin{itemize}
         \item
-                Is @999@ TBD-compatible with @n@?
+                Is @999@ compatible with @n@?
 \end{itemize}
-This compatibility question applies to a pair of expressions, where the earlier ones were to types.
+This compatibility question applies to a pair of expressions, where the earlier implementation were to types.
 Such an expression-compatibility question is a new addition to the \CFA compiler.
-These questions only arise in the context of dimension expressions on (C) array types.
+Note, these questions only arise in the context of dimension expressions on (C) array types.
 
 TODO: ensure these compiler implementation matters are treated under \CFA compiler background:
@@ -600 +563 @@
 GenPoly.
 
-The relevant technical component of the \CFA compiler is,
-within the type resolver, the type unification procedure.
+The relevant technical component of the \CFA compiler is the type unification procedure within the type resolver.
 I added rules for continuing this unification into expressions that occur within types.
 It is still fundamentally doing \emph{type} unification
@@ -607 +569 @@
 and not participating in binding any variables that stand in for expression fragments
 (for there is no such sort of variable in \CFA's analysis.)
-
 An unfortunate fact about the \CFA compiler's preexisting implementation is that
 type unification suffers from two forms of duplication.
@@ -613 +574 @@
 The first duplication has (many of) the unification rules stated twice.
 As a result, my additions for dimension expressions are stated twice.
-The extra statement of the rules occurs in the GenPoly module,
+The extra statement of the rules occurs in the @GenPoly@ module,
 where concrete types like @array(int, 5)@\footnote{
         Again, the presentation is simplified
-        by leaving the \lstinline{array} macro unexpanded}
+        by leaving the \lstinline{array} macro unexpanded.}
 are lowered into corresponding C types @struct __conc_array_1234@ (the suffix being a generated index).
-In this case, the struct's definition gives fields that hardcode the argument values of @float@ and @5@.
-The next time an @array(-,-)@ concrete instance is encountered,
-is the previous @struct __conc_array_1234@ suitable for it?
-Yes, for another occurrance of @array(int, 5)@;
+In this case, the struct's definition contains fields that hardcode the argument values of @float@ and @5@.
+The next time an @array(-,-)@ concrete instance is encountered, it checks if the previous @struct __conc_array_1234@ is suitable for it.
+Yes, for another occurrence of @array(int, 5)@;
 no, for either @array(rational(int), 5)@ or @array(int, 42)@.
 By the last example, this phase must ``reject''
@@ -630 +590 @@
 In the program
 \begin{cfa}
-        void f( double );
-        forall( T & ) void f( T & );
-        void g( int n ) {
-                array( float, n + 1 ) x;
-                f(x);
-        }
-\end{cfa}
-when resolving the function call, the first unification stage
-compares the types @T@, of the parameter, with @array( float, n + 1 )@, of the argument.
+void @f@( double );
+forall( T & ) void @f@( T & );
+void g( int n ) {
+        array( float, n + 1 ) x;
+        f(x);   // overloaded
+}
+\end{cfa}
+when resolving the function call, @g@, the first unification stage
+compares the type @T@ of the parameter with @array( float, n + 1 )@, of the argument.
 TODO: finish.
 
@@ -647 +607 @@
         TODO: 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 will evaluate the
-same result, while a ``no'' can tolerate ``they might, but we're not sure,'
+So, a ``yes'' answer must represent a guarantee that both expressions evaluate the
+same result, while a ``no'' can tolerate ``they might, but we're not sure'',
 provided that practical recourses are available
-to let programmers express their better knowledge.
-The specific rule-set that I offer with the current release is, in fact, extremely conservative.
+to let programmers express better knowledge.
+The new rule-set in the current release is, in fact, extremely conservative.
 I chose to keep things simple,
-and allow real future needs do drive adding additional complexity,
-within the framework that I laid out.
+and allow future needs to drive adding additional complexity, within the new framework.
 
 For starters, the original motivating example's rejection
@@ -662 +621 @@
 Rather, the analysis assumes a variable's value can be anything,
 and so there can be no guarantee that its value is 999.
-So, a variable use and a literal can never match.
+So, a variable and a literal can never match.
 
 Two occurrences of the same literal value are obviously a fine match.
-For two occurrences of the same varialbe, more information is needed.
+For two occurrences of the same variable, more information is needed.
 For example, this one is fine
 \begin{cfa}
-        void f( const int n ) {
-                float x[n];
-                float (*xp)[n] = x; // accept
-        }
+void f( const int n ) {
+        float x[n];
+        float (*xp)[n] = x;   // accept
+}
 \end{cfa}
 while this one is not:
 \begin{cfa}
-        void f() {
-                int n = 42;
-                float x[n];
-                n = 999;
-                float (*xp)[n] = x; // reject
-        }
+void f() {
+        int n = 42;
+        float x[n];
+        n = 999;
+        float (*xp)[n] = x;   // reject
+}
 \end{cfa}
 Furthermore, the fact that the first example sees @n@ as @const@
-is not actually a sufficent basis.
+is not actually sufficient.
 In this example, @f@'s length expression's declaration is as @const@ as it can be,
 yet its value still changes between the two invocations:
-\begin{cfa}
-        // compile unit 1
-        void g();
-        void f( const int & const nr ) {
-                float x[nr];
-                g();
-                float (*xp)[nr] = x; // reject
-        }
-        // compile unit 2
-        static int n = 42;
-        void g() {
-                n = 99;
-        }
-        void f( const int & );
-        int main () {
-                f(n);
-                return 0;
-        }
-\end{cfa}
-The issue in this last case is,
-just because you aren't able to change something doesn't mean someone else can't.
-
-My rule set also respects a feature of the C tradition.
-In spite of the several limitations of the C rules
+\begin{cquote}
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}ll@{}}
+\begin{cfa}
+// compile unit 1
+void g();
+void f( const int & const nr ) {
+        float x[nr];
+        g();    // change n
+        @float (*xp)[nr] = x;@   // reject
+}
+\end{cfa}
+&
+\begin{cfa}
+// compile unit 2
+static int n = 42;
+void g() {
+        n = 99;
+}
+
+f( n );
+\end{cfa}
+\end{tabular}
+\end{cquote}
+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.
+
+My rule set also respects a traditional C feature: In spite of the several limitations of the C rules
 accepting cases that produce different values, there are a few mismatches that C stops.
-C is quite precise when working with two static values:
-\begin{cfa}
-        enum { fortytwo = 42 };
-        float x[fortytwo];
-        float (*xp1)[42] = &x; // accept
-        float (*xp2)[999] = &x; // reject
+C is quite precise when working with two static values.
+\begin{cfa}
+enum { fortytwo = 42 };
+float x[fortytwo];
+float (*xp1)[42] = &x;    // accept
+float (*xp2)[999] = &x;   // reject
 \end{cfa}
 My \CFA rules agree with C's on these cases.
 
-My rules classify expressions into three groups:
+In summary, the new rules classify expressions into three groups:
 \begin{description}
 \item[Statically Evaluable]
         Expressions for which a specific value can be calculated (conservatively)
         at compile-time.
-        A preexisting \CFA compiler module defines which expressions qualify,
+        A preexisting \CFA compiler module defines which literals, enumerators, and expressions qualify,
         and evaluates them.
-        Includes literals and enumeration values.
 \item[Dynamic but Stable]
-        The value of a variable declared as @const@.
-        Includes a @const@ parameter.
+        The value of a variable declared as @const@, including a @const@ parameter.
 \item[Potentially Unstable]
         The catch-all category.  Notable examples include:
-        any function-call result (@float x[foo()];@),
-        the particular function-call result that is a pointer dereference (@void f(const int * n) { float x[*n]; }@), and
+        any function-call result, @float x[foo()];@,
+        the particular function-call result that is a pointer dereference, @void f(const int * n)@ @{ float x[*n]; }@, and
         any use of a reference-typed variable.
 \end{description}
-
-My \CFA rules are:
+Within these groups, my \CFA rules are:
 \begin{itemize}
 \item
@@ -744 +704 @@
         Notably, this rule allows a literal to match with an enumeration value, based on the value.
 \item
-        Accept a Dynamic but Stable pair, if both expressions are written out the same, e.g. refers to same variable declaration.
+        Accept a Dynamic but Stable pair, if both expressions are written out the same, \eg refers to the same variable declaration.
 \item
         Otherwise, reject.
-        Notably, reject all pairs from the Potentially Unstable group.
-        Notably, reject all pairs that cross groups.
+        Notably, reject all pairs from the Potentially Unstable group and all pairs that cross groups.
 \end{itemize}
-
 The traditional C rules are:
 \begin{itemize}
@@ -759 +717 @@
 \end{itemize}
 
-
-\newcommand{\falsealarm}{{\color{orange}\small{*}}}
-\newcommand{\allowmisuse}{{\color{red}\textbf{!}}}
-\newcommand{\cmark}{\ding{51}} % from pifont
-\newcommand{\xmark}{\ding{55}}
 \begin{figure}
+        \newcommand{\falsealarm}{{\color{blue}\small{*}}}
+        \newcommand{\allowmisuse}{{\color{red}\textbf{!}}}
+        \newcommand{\cmark}{\ding{51}} % from pifont
+        \newcommand{\xmark}{\ding{55}}
+
         \begin{tabular}{@{}l@{\hspace{16pt}}c@{\hspace{8pt}}c@{\hspace{16pt}}c@{\hspace{8pt}}c@{\hspace{16pt}}c}
          & \multicolumn{2}{c}{\underline{Values Equal}}
@@ -778 +736 @@
         \end{tabular}
 
-        \vspace{12pt}
-        \noindent\textbf{Legend:}
-        \begin{itemize}
+        \medskip
+        \noindent\textbf{Legend}
+        \begin{itemize}[leftmargin=*]
         \item
                 Each row gives the treatment of a test harness of the form
                 \begin{cfa}
-                        float x[ expr1 ];
-                        float (*xp)[ expr2 ] = &x;
+                float x[ expr1 ];
+                float (*xp)[ expr2 ] = &x;
                 \end{cfa}
-                where \lstinline{expr1} and \lstinline{expr2} are metavariables varying according to the row's Case.
+                \vspace*{-10pt}
+                where \lstinline{expr1} and \lstinline{expr2} are meta-variables varying according to the row's Case.
                 Each row's claim applies to other harnesses too, including,
                 \begin{itemize}
                 \item
-                        calling a function with a paramter like \lstinline{x} and an argument of the \lstinline{xp} type,
+                        calling a function with a parameter like \lstinline{x} and an argument of the \lstinline{xp} type,
                 \item
                         assignment in place of initialization,
@@ -801 +760 @@
         \item
                 Each case's claim is symmetric (swapping \lstinline{expr1} with \lstinline{expr2} has no effect),
-                even though most test harnesses are asymetric.
+                even though most test harnesses are asymmetric.
         \item
                 The table treats symbolic identity (Same/Different on rows)
-                apart from value eqality (Equal/Unequal on columns).
+                apart from value equality (Equal/Unequal on columns).
                 \begin{itemize}
                 \item
@@ -819 +778 @@
                 while every Accept under Values Unequal is an allowed misuse (\allowmisuse).
         \end{itemize}
-        \caption{Case comparison for array type compatibility, given pairs of dimension expressions.
-                TODO: get Peter's LaTeX help on overall appearance, probably including column spacing/centering and bullet indentation.}
+
+        \caption{Case comparison for array type compatibility, given pairs of dimension expressions.}
         \label{f:DimexprRuleCompare}
 \end{figure}
@@ -826 +785 @@
 
 Figure~\ref{f:DimexprRuleCompare} gives a case-by-case comparison of the consequences of these rule sets.
-It demonstrates that the \CFA false alarms occur in the same cases as C treats unsafely.
-It also shows that C-incompatibilities only occur in cases that C treats unsafely.
+It demonstrates that the \CFA false alarms occur in the same cases as C treats unsafe.
+It also shows that C-incompatibilities only occur in cases that C treats unsafe.
 
 
@@ -837 +796 @@
 whose reuses are rejected by the blunt current-state rules:
 \begin{cfa}
-        void f( int & nr, const int nv ) {
-                float x[nr];
-                float (*xp)[nr] = & x; // reject: nr varying (no references)
-                float y[nv + 1];
-                float (*yp)[nv + 1] = & y; // reject: ?+? unpredicable (no functions)
-        }
+void f( int & nr, const int nv ) {
+        float x[nr];
+        float (*xp)[nr] = &x;   // reject: nr varying (no references)
+        float y[nv + 1];
+        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
+The @nr@ reference is never written, not volatile
 and control does not leave the function between the uses.
-The name @?+?@ resolves to a function that is quite predictable.)
-The programmer here can add the constant declarations:
-\begin{cfa}
-        void f( int & nr, const int nv ) {
-                @const int nx@ = nr;
-                float x[nx];
-                float (*xp)[nx] = & x; // acept
-                @const int ny@ = nv + 1;
-                float y[ny];
-                float (*yp)[ny] = & y; // accept
-        }
+The name @?+?@ resolves to a function that is quite predictable.
+Here, the programmer can add the constant declarations (cast does not work):
+\begin{cfa}
+void f( int & nr, const int nv ) {
+        @const int nx@ = nr;
+        float x[nx];
+        float (*xp)[nx] = & x;   // accept
+        @const int ny@ = nv + 1;
+        float y[ny];
+        float (*yp)[ny] = & y;   // accept
+}
 \end{cfa}
 The result is the originally intended semantics,
@@ -863 +822 @@
 
 The snapshotting trick is also used by the translation, though to achieve a different outcome.
-Rather obviously, every array must be subscriptable, even a bizzarre one:
-\begin{cfa}
-        array( float, rand(10) ) x;
-        x[0];  // 10% chance of bound-check failure
+Rather obviously, every array must be subscriptable, even a bizarre one:
+\begin{cfa}
+array( float, rand(10) ) x;
+x[0];  // 10% chance of bound-check failure
 \end{cfa}
 Less obvious is that the mechanism of subscripting is a function call,
@@ -874 +833 @@
 Adjusting the example to make the function's use of length more explicit:
 \begin{cfa}
-        forall ( T * )
-        void f( T * x ) { sout | sizeof(*x); }
-        float x[ rand(10) ];
-        f( x );
+forall ( T * )
+void f( T * x ) { sout | sizeof(*x); }
+float x[ rand(10) ];
+f( x );
 \end{cfa}
 Considering that the partly translated function declaration is, loosely,
 \begin{cfa}
-        void f( size_t __sizeof_T, void * x ) { sout | __sizeof_T; }
-\end{cfa}
-the translated call must not go like:
-\begin{cfa}
-        float x[ rand(10) ];
-        f( rand(10), &x );
-\end{cfa}
-Rather, its actual translation is like:
-\begin{cfa}
-        size_t __dim_x = rand(10);
-        float x[ __dim_x ];
-        f( __dim_x, &x );
-\end{cfa}
-The occurrence of this dimension hoisting during translation was present in the preexisting \CFA compiler.
-But its cases were buggy, particularly with determining, ``Can hoisting be skipped here?''
-For skipping this hoisting is clearly desirable in some cases,
-not the least of which is when the programmer has already done so manually.
-My work includes getting these cases right, harmonized with the accept/reject criteria, and tested.
-
-
+void f( size_t __sizeof_T, void * x ) { sout | __sizeof_T; }
+\end{cfa}
+the translation must call the dimension argument twice:
+\begin{cfa}
+float x[ rand(10) ];
+f( rand(10), &x );
+\end{cfa}
+Rather, the translation is:
+\begin{cfa}
+size_t __dim_x = rand(10);
+float x[ __dim_x ];
+f( __dim_x, &x );
+\end{cfa}
+The occurrence of this dimension hoisting during translation was in the preexisting \CFA compiler.
+But its cases were buggy, particularly with determining, ``Can hoisting the expression be skipped here?'', for skipping this hoisting is clearly desirable in some cases.
+For example, when the programmer has already done so manually. \PAB{I don't know what this means.}
+In the new implementation, these cases are correct, harmonized with the accept/reject criteria.
 
 TODO: Discuss the interaction of this dimension hoisting with the challenge of extra unification for cost calculation
 
 
-\section{Multidimensional Arrays}
-\label{toc:mdimpl}
-
-% TODO: introduce multidimensional array feature and approaches
-
-When working with arrays, \eg linear algebra, array dimensions are referred to as ``rows'' and ``columns'' for a matrix, adding ``planes'' for a cube.
-(There is little terminology for higher dimensional arrays.)
-For example, an acrostic poem\footnote{A type of poetry where the first, last or other letters in a line spell out a particular word or phrase in a vertical column.}
-can be treated as a grid of characters, where the rows are the text and the columns are the embedded keyword(s).
-Within a poem, there is the concept of a \newterm{slice}, \eg a row is a slice for the poem text, a column is a slice for a keyword.
-In general, the dimensioning and subscripting for multidimensional arrays has two syntactic forms: @m[r,c]@ or @m[r][c]@.
-
-Commonly, an array, matrix, or cube, is visualized (especially in mathematics) as a contiguous row, rectangle, or block.
-This conceptualization is reenforced by subscript ordering, \eg $m_{r,c}$ for a matrix and $c_{p,r,c}$ for a cube.
-Few programming languages differ from the mathematical subscript ordering.
-However, computer memory is flat, and hence, array forms are structured in memory as appropriate for the runtime system.
-The closest representation to the conceptual visualization is for an array object to be contiguous, and the language structures this memory using pointer arithmetic to access the values using various subscripts.
-This approach still has degrees of layout freedom, such as row or column major order, \ie juxtaposed rows or columns in memory, even when the subscript order remains fixed.
-For example, programming languages like MATLAB, Fortran, Julia and R store matrices in column-major order since they are commonly used for processing column-vectors in tabular data sets but retain row-major subscripting.
-In general, storage layout is hidden by subscripting, and only appears when passing arrays among different programming languages or accessing specific hardware.
-
-\VRef[Figure]{f:FixedVariable} shows two C90 approaches for manipulating a contiguous matrix.
-Note, C90 does not support VLAs.
-The fixed-dimension approach (left) uses the type system;
-however, it requires all dimensions except the first to be specified at compile time, \eg @m[][6]@, allowing all subscripting stride calculations to be generated with constants.
-Hence, every matrix passed to @fp1@ must have exactly 6 columns but the row size can vary.
-The variable-dimension approach (right) ignores (violates) the type system, \ie argument and parameters types do not match, and subscripting is performed manually using pointer arithmetic in the macro @sub@.
-
-\begin{figure}
-\begin{tabular}{@{}l@{\hspace{40pt}}l@{}}
-\multicolumn{1}{c}{\textbf{Fixed Dimension}} & \multicolumn{1}{c}{\textbf{Variable Dimension}} \\
-\begin{cfa}
-
-void fp1( int rows, int m[][@6@] ) {
-        ...  printf( "%d ", @m[r][c]@ );  ...
-}
-int fm1[4][@6@], fm2[6][@6@]; // no VLA
-// initialize matrixes
-fp1( 4, fm1 ); // implicit 6 columns
-fp1( 6, fm2 );
-\end{cfa}
-&
-\begin{cfa}
-#define sub( m, r, c ) *(m + r * sizeof( m[0] ) + c)
-void fp2( int rows, int cols, int *m ) {
-        ...  printf( "%d ", @sub( m, r, c )@ );  ...
-}
-int vm1[@4@][@4@], vm2[@6@][@8@]; // no VLA
-// initialize matrixes
-fp2( 4, 4, vm1 );
-fp2( 6, 8, vm2 );
-\end{cfa}
-\end{tabular}
-\caption{C90 Fixed \vs Variable Contiguous Matrix Styles}
-\label{f:FixedVariable}
-\end{figure}
-
-Many languages allow multidimensional arrays-of-arrays, \eg in Pascal or \CC.
-\begin{cquote}
-\begin{tabular}{@{}ll@{}}
-\begin{pascal}
-var m : array[0..4, 0..4] of Integer;  (* matrix *)
-type AT = array[0..4] of Integer;  (* array type *)
-type MT = array[0..4] of AT;  (* array of array type *)
-var aa : MT;  (* array of array variable *)
-m@[1][2]@ := 1;   aa@[1][2]@ := 1 (* same subscripting *)
-\end{pascal}
-&
-\begin{c++}
-int m[5][5];
-
-typedef vector< vector<int> > MT;
-MT vm( 5, vector<int>( 5 ) );
-m@[1][2]@ = 1;  aa@[1][2]@ = 1;
-\end{c++}
-\end{tabular}
-\end{cquote}
-The language decides if the matrix and array-of-array are laid out the same or differently.
-For example, an array-of-array may be an array of row pointers to arrays of columns, so the rows may not be contiguous in memory nor even the same length (triangular matrix).
-Regardless, there is usually a uniform subscripting syntax masking the memory layout, even though a language could differentiated between the two forms using subscript syntax, \eg @m[1,2]@ \vs @aa[1][2]@.
-Nevertheless, controlling memory layout can make a difference in what operations are allowed and in performance (caching/NUMA effects).
-
-C also provides non-contiguous arrays-of-arrays.
-\begin{cfa}
-int m[5][5];                                                    $\C{// contiguous}$
-int * aa[5];                                                    $\C{// non-contiguous}$
-\end{cfa}
-both with different memory layout using the same subscripting, and both with different degrees of issues.
-The focus of this work is on the contiguous multidimensional arrays in C.
-The reason is that programmers are often forced to use the more complex array-of-array form when a contiguous array would be simpler, faster, and safer.
-Nevertheless, the C array-of-array form is still important for special circumstances.
-
-\VRef[Figure]{f:ContiguousNon-contiguous} shows the extensions made in C99 for manipulating contiguous \vs non-contiguous arrays.\footnote{C90 also supported non-contiguous arrays.}
-First, VLAs are supported.
-Second, for contiguous arrays, C99 conjoins one or more of the parameters as a downstream dimension(s), \eg @cols@, implicitly using this parameter to compute the row stride of @m@.
-If the declaration of @fc@ is changed to:
-\begin{cfa}
-void fc( int rows, int cols, int m[@rows@][@cols@] ) ...
-\end{cfa}
-it is possible for C to perform bound checking across all subscripting, but it does not.
-While this contiguous-array capability is a step forward, it is still the programmer's responsibility to manually manage the number of dimensions and their sizes, both at the function definition and call sites.
-That is, the array does not automatically carry its structure and sizes for use in computing subscripts.
-While the non-contiguous style in @faa@ looks very similar to @fc@, the compiler only understands the unknown-sized array of row pointers, and it relies on the programmer to traverse the columns in a row correctly with a correctly bounded loop index.
-Specifically, there is no requirement that the rows are the same length, like a poem with different length lines.
-
-\begin{figure}
-\begin{tabular}{@{}ll@{}}
-\multicolumn{1}{c}{\textbf{Contiguous}} & \multicolumn{1}{c}{\textbf{ Non-contiguous}} \\
-\begin{cfa}
-void fc( int rows, @int cols@, int m[ /* rows */ ][@cols@] ) {
-        ...  printf( "%d ", @m[r][c]@ );  ...
-}
-int m@[5][5]@;
-for ( int r = 0; r < 5; r += 1 ) {
-
-        for ( int c = 0; c < 5; c += 1 )
-                m[r][c] = r + c;
-}
-fc( 5, 5, m );
-\end{cfa}
-&
-\begin{cfa}
-void faa( int rows, int cols, int * m[ @/* cols */@ ] ) {
-        ...  printf( "%d ", @m[r][c]@ );  ...
-}
-int @* aa[5]@;  // row pointers
-for ( int r = 0; r < 5; r += 1 ) {
-        @aa[r] = malloc( 5 * sizeof(int) );@ // create rows
-        for ( int c = 0; c < 5; c += 1 )
-                aa[r][c] = r + c;
-}
-faa( 5, 5, aa );
-\end{cfa}
-\end{tabular}
-\caption{C99 Contiguous \vs Non-contiguous Matrix Styles}
-\label{f:ContiguousNon-contiguous}
-\end{figure}
-
-
-\subsection{Multidimensional array implementation}
+\section{Multidimensional array implementation}
 \label{s:ArrayMdImpl}
 
@@ -1221 +1038 @@
         S & | sized(S),                 $\C{// masquerading-as}$
         Timmed &,                               $\C{// immediate element, often another array}$
-        Tbase &                                 $\C{// base element, e.g. float, never array}$
+        Tbase &                                 $\C{// base element, \eg float, never array}$
 ) { // distribute forall to each element
         struct arpk {
@@ -1274 +1091 @@
 
 
-
-
+\section{Array lifecycle}
+
+An array is an aggregate, like a structure;
+both are containers wrapping subordinate objects.
+Any arbitrary object type, like @string@, can be an array element or structure member.
+A consequence is that the lifetime of the container must match with its subordinate objects: all elements and members must be initialized/uninitialized implicitly as part of the container's allocation/deallocation.
+Modern programming languages implicitly perform these operations via a type's constructor and destructor.
+Therefore, \CFA must assure that an array's subordinate objects' lifetime operations are called.
+
+Preexisting \CFA mechanisms achieve this requirement, but with poor performance.
+Furthermore, advanced array users need an exception to the basic mechanism, which does not occur with other aggregates.
+Hence, arrays introduce subleties in supporting an element's lifecycle.
+
+The preexisting \CFA support for contained-element lifecycle is based on recursive occurrences of the object-type (@otype@) pseudo-trait.
+A type is an @otype@, if it provides a default (parameterless) constructor, copy constructor, assignment operator, and destructor (like \CC).
+When declaring a structure with @otype@ members, the compiler implicitly generates implementations of the four @otype@ functions for the outer structure.
+Then the generated default constructor for the outer structure calls the default constructor for each member, and the other @otype@ functions work similarly.
+For a member that is a C array, these calls occur in a loop for each array element, which even works for VLAs.
+This logic works the same, whether the member is a concrete type (that happens to be an @otype@) or if the member is a polymorphic type asserted to be an @otype@ (which is implicit in the syntax, @forall(T)@).
+The \CFA array has the simplified form (similar to one seen before):
+\begin{cfa}
+forall( T * )   // non-otype element, no lifecycle functions
+// forall( T )  // otype element, lifecycle functions asserted
+struct array5 {
+        T __items[ 5 ];
+};
+\end{cfa}
+Being a structure with a C-array member, using the otype-form declaration for @T@ causes @array5(float)@ to implement @otype@ too.
+
+But this @otype@-recursion pattern has a performance issue.
+For example, in a cube of @float@:
+\begin{cfa}
+array5( array5( array5( float ) ) )
+\end{cfa}
+the first few steps of the compiler's work to find the lifecycle functions, under the @otype@-recursion pattern, are shown in \VRef[Figure]{f:OtypeRecursionBlowup}.
+All the work needed for the full @float@-cube would have 256 leaves.
+
+%array5(T) offers
+%1 parameterless ctor, which asks for T to have
+%       1 parameterless ctor
+%       2 copy ctor
+%       3 asgt
+%       4 dtor
+%2 copy ctor, which asks for T to have
+%       1 parameterless ctor
+%       2 copy ctor
+%       3 asgt
+%       4 dtor
+%3 asgt, which asks for T to have
+%       1 parameterless ctor
+%       2 copy ctor
+%       3 asgt
+%       4 dtor
+%4 dtor, which asks for T to have
+%       1 parameterless ctor
+%       2 copy ctor
+%       3 asgt
+%       4 dtor
+
+\begin{figure}
+\centering
+\setlength{\tabcolsep}{15pt}
+\begin{tabular}{@{}lll@{}}
+\begin{cfa}[deletekeywords={default}]
+float offers
+1 default ctor
+2 copy ctor
+3 asgt
+4 dtor
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+\end{cfa}
+&
+\begin{cfa}[deletekeywords={default}]
+array5(float) has
+1 default ctor, using float's
+        1 default ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+2 copy ctor, using float's
+        1 default ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+3 asgt, using float's
+        1 default ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+4 dtor, using float's
+        1 default ctor
+        2 copy ctor
+        3 asgt
+        4 dtor
+
+
+
+
+
+
+
+
+\end{cfa}
+&
+\begin{cfa}[deletekeywords={default}]
+array5(array5(float)) has
+1 default ctor, using array5(float)'s
+        1 default ctor, using float's
+                1 default ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        2 copy ctor, using float's
+                1 default ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        3 asgt, using float's
+                1 default ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+        4 dtor, using float's
+                1 default ctor
+                2 copy ctor
+                3 asgt
+                4 dtor
+2 copy ctor, using array5(float)'s
+        ... 4 children, 16 leaves
+3 asgt, using array5(float)'s
+        ... 4 children, 16 leaves
+4 dtor, using array5(float)'s
+        ... 4 children, 16 leaves
+(64 leaves)
+\end{cfa}
+\end{tabular}
+\caption{Exponential thunk generation under the otype-recursion pattern.
+        Each time that one type's function (\eg ctor) uses another type's function, the \CFA compiler generates a thunk, to capture the used function's dependencies, presented according to the using function's need.
+        So, each non-leaf line represents a generated thunk and every line represents a search request for the resolver to find a satisfying function.}
+\label{f:OtypeRecursionBlowup}
+\end{figure}
+
+So the @otype@-recursion pattern seeks a quantity of helper functions, and generates a quantity of thunks, that are exponential in the number of dimensions.
+Anecdotal experience with this solution found the resulting compile times annoyingly slow at three dimensions, and unusable at four.
+
+The issue is that the otype-recursion pattern uses more assertions than needed.
+Consider how @array5(float)@'s default constructor is getting all four lifecycle assertions about the element type, @float@.
+It only needs @float@'s default constructor;
+the full set of operations is never used.
+Current work by the \CFA team aims to improve this situation.
+Therefore, a workaround is needed for now.
+
+The workaround is to provide a default constructor, copy constructor and destructor, defined with lean, bespoke assertions:
+\begin{cquote}
+\begin{tabular}{@{}l@{\hspace{0.5in}}l@{}}
+\begin{cfa}
+// autogenerated for otype-recursion:
+forall( T )
+void ?{}( array5(T) & this ) {
+        for (i; 5) { ( this[i] ){}; }
+}
+forall( T )
+void ?{}( array5(T) & this, array5(T) & src ) {
+        for (i; 5) { ( this[i] ){ src[i] }; }
+}
+forall( T )
+void ^?{}( array5(T) & this ) {
+        for (i; 5) { ^( this[i] ){}; }
+}
+\end{cfa}
+&
+\begin{cfa}
+// lean, bespoke:
+forall( T* | { void @?{}( T & )@; } )
+void ?{}( array5(T) & this ) {
+        for (i; 5) { ( this[i] ){}; }
+}
+forall( T* | { void @?{}( T &, T )@; } )
+void ?{}( array5(T) & this, array5(T) & src ) {
+        for (i; 5) { ( this[i] ){ src[i] }; }
+}
+forall( T* | { void @?{}( T & )@; } )
+void ^?{}( array5(T) & this ) {
+        for (i; 5) { ^( this[i] ){}; }
+}
+\end{cfa}
+\end{tabular}
+\end{cquote}
+Moreover, the assignment operator is skipped, to avoid hitting a lingering growth case.
+Skipping assignment is tolerable because array assignment is not a common operation.
+With this solution, the critical lifecycle functions are available, with no growth in thunk creation.
+
+Finally, the intuition that a programmer using an array always wants the elements' default constructor called \emph{automatically} is simplistic.
+Arrays exist to store different values at each position.
+So, array initialization needs to let the programmer provide different constructor arguments to each element.
+\begin{cfa}
+thread worker { int id; };
+void ?{}( worker & ) = void; // remove default constructor
+void ?{}( worker &, int id );
+array( worker, 5 ) ws = @{}@; // rejected; but desire is for no initialization yet
+for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread, giving id
+\end{cfa}
+Note the use of the \CFA explicit constructor call, analogous to \CC's placement-@new@.
+This call is where initialization is desired, and not at the declaration of @ws@.
+The attempt to initialize from nothing (equivalent to dropping @= {}@ altogether) is invalid because the @worker@ type removes the default constructor.
+The @worker@ type is designed this way to work with the threading system.
+A thread type forks a thread at the end of each constructor and joins with it at the start of each destructor.
+But a @worker@ cannot begin its forked-thead work without knowing its @id@.
+Therefore, there is a conflict between the implicit actions of the builtin @thread@ type and a user's desire to defer these actions.
+
+Another \CFA feature may, at first, seem viable for initializing the array @ws@, though on closer inspection, it is not.
+C initialization, \lstinline|array(worker, 5) ws @= {};|, ignores all \CFA lifecycle management and uses C empty initialization.
+This option does achieve the desired semantics on the construction side.
+But on destruction side, the desired semantics is for implicit destructor calls to continue, to keep the join operation tied to lexical scope.
+C initialization disables \emph{all} implicit lifecycle management, but the goal is to disable only the implicit construction.
+
+To fix this problem, I enhanced the \CFA standard library to provide the missing semantics, available in either form:
+\begin{cfa}
+array( @uninit@(worker), 5 ) ws1;
+array( worker, 5) ws2 = { @delay_init@ };
+\end{cfa}
+Both cause the @ws@-construction-time implicit call chain to stop before reaching a @worker@ constructor, while leaving the implicit destruction calls intact.
+Two forms are available, to parallel the development of this feature in \uCpp.
+Originally \uCpp offered only the @ws1@ form, using the class-template @uNoCtor@ equivalent to \CFA's @uninit@.
+More recently, \uCpp was extended with the declaration macro, @uArray@, with usage similar to the @ws2@ case.
+Based on experience piloting @uArray@ as a replacement of @uNoCtor@, it might be possible to remove the first option.
+
+% note to Mike, I have more fragments on some details available in push24\fragments\uNoCtor.txt
 
 \section{Comparison with other arrays}

doc/theses/mike_brooks_MMath/background.tex

@@ -178 +178 @@
 \lstinput{34-34}{bkgd-carray-arrty.c}
 The inspection begins by using @sizeof@ to provide program semantics for the intuition of an expression's type.
-An architecture with 64-bit pointer size is used, to keep irrelevant details fixed.
+An architecture with 64-bit pointer size is used, to remove irrelevant details.
 \lstinput{35-36}{bkgd-carray-arrty.c}
 Now consider the @sizeof@ expressions derived from @ar@, modified by adding pointer-to and first-element (and including unnecessary parentheses to avoid any confusion about precedence).
@@ -215 +215 @@
 
 My observation is recognizing:
-\begin{itemize}[leftmargin=*,topsep=0pt,itemsep=0pt]
+\begin{itemize}[leftmargin=*,itemsep=0pt]
         \item There is value in using a type that knows its size.
         \item The type pointer to the (first) element does not.
@@ -302 +302 @@
 
 In summary, when a function is written with an array-typed parameter,
-\begin{itemize}[leftmargin=*,topsep=0pt]
+\begin{itemize}[leftmargin=*]
         \item an appearance of passing an array by value is always an incorrect understanding,
         \item a dimension value, if any is present, is ignored,
@@ -532 +532 @@
 \subsection{Array Parameter Declaration}
 
-Passing an array along with a function call is obviously useful.
-Let us say that a parameter is an array parameter when the called function intends to subscript it.
-This section asserts that a more satisfactory/formal characterization does not exist in C, surveys the ways that C API authors communicate ``@p@ has zero or more @T@s,'' and calls out the minority cases where the C type system is using or verifying such claims.
-
-A C function's parameter declarations look different, from the caller's and callee's perspectives.
+Passing an array as an argument to a function is necessary.
+Assume a parameter is an array when the function intends to subscript it.
+This section asserts that a more satisfactory/formal characterization does not exist in C, surveys the ways that C API authors communicate ``@p@ has zero or more dimensions'' and calls out the minority cases where the C type system is using or verifying such claims.
+
+A C parameter declarations look different, from the caller's and callee's perspectives.
 Both perspectives consist of the text read by a programmer and the semantics enforced by the type system.
-The caller's perspecitve is available from a mere function declaration (which allow definition-before-use and separate compilation), but can also be read from (the non-body part of) a function definition.
+The caller's perspective is available from a function declaration, which allow definition-before-use and separate compilation, but can also be read from (the non-body part of) a function definition.
 The callee's perspective is what is available inside the function.
 \begin{cfa}
-        int foo( int, float, char );                            $\C{// declaration, names optional}$
-        int bar( int i, float f, char c ) {             $\C{// definition, names mandatory}$
-                $/* caller's perspective of foo's; callee's perspective of bar's */$
-                ...
-        }
-        $/* caller's persepectives of foo's and bar's */$
-\end{cfa}
-The caller's perspective is more limited.
-The example shows, so far, that parameter names (by virtue of being optional) are really comments in the caller's perspective, while they are semantically significant in the callee's perspective.
+int foo( int, float, char );                            $\C{// declaration, names optional}$
+int bar( int i, float f, char c ) {             $\C{// definition, names mandatory}$
+        // caller's perspective of foo; callee's perspective of bar
+}
+// caller's perspectives of foo's and bar's
+\end{cfa}
+In caller's perspective, the parameter names (by virtue of being optional) are really comments;
+in the callee's perspective, parameter names are semantically significant.
 Array parameters introduce a further, subtle, semantic difference and considerable freedom to comment.
 
-At the semantic level, there is no such thing as an array parameter, except for one case (@T[static 5]@) discussed shortly.
+At the semantic level, there is no such thing as an array parameter, except for one case (@T [static 5]@) discussed shortly.
 Rather, there are only pointer parameters.
-This fact probably shares considerable responsibility for the common sense of ``an array is just a pointer,'' wich has been refuted in non-parameter contexts.
+This fact probably shares considerable responsibility for the common sense of ``an array is just a pointer,'' which has been refuted in non-parameter contexts.
 This fact holds in both the caller's and callee's perspectives.
-However, a parameter's type can include ``array of.''
-For example, the type ``pointer to array of 5 ints'' (@T(*)[5]@) is a pointer type, a fully meaningful parameter type (in the sense that this description does not contain any information that the type system ignores), and a type that appears the same in the caller's \vs callee's perspectives.
-The outermost type constructor (syntactically first dimension) is really the one that determines the flavour of parameter.
+However, a parameter's type can include ``array of.'', \eg the type ``pointer to array of 5 ints'' (@T (*)[5]@) is a pointer type.
+This type is fully meaningful in the sense that its description does not contain any information that the type system ignores, and the type appears the same in the caller's \vs callee's perspectives.
+In fact, the outermost type constructor (syntactically first dimension) is really the one that determines the flavour of parameter.
+
+Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
+An array parameter declaration can specify the outermost dimension with a dimension value, @[10]@ (which is ignored), an empty dimension list, @[ ]@, or a pointer, @*@, as seen in \VRef[Figure]{f:ArParmEquivDecl}.
+The rationale for rejecting the first ``invalid'' row follows shortly, while the second ``invalid'' row is simple nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
 
 \begin{figure}
@@ -596 +599 @@
 \end{tabular}
 \end{cquote}
-\caption{Multiple ways to declare an arrray parameter.  Across a valid row, every declaration is equivalent.  Each column gives a declaration style.  Really, the style can be read from the first row only.  The second row shows how the style extends to multiple dimensions, with the rows thereafter providing context for the choice of which second-row \lstinline{[]}receives the column-style variation.}
+\caption{Multiple ways to declare an array parameter.
+Across a valid row, every declaration is equivalent.
+Each column gives a declaration style, where the style for that column is read from the first row.
+The second row begins the style for multiple dimensions, with the rows thereafter providing context for the choice of which second-row \lstinline{[]} receives the column-style variation.}
 \label{f:ArParmEquivDecl}
 \end{figure}
 
-Yet, C allows array syntax for the outermost type constructor, from which comes the freedom to comment.
-An array parameter declaration can specify the outermost dimension with a dimension value, @[10]@ (which is ignored), an empty dimension list, @[ ]@, or a pointer, @*@, as seen in \VRef[Figure]{f:ArParmEquivDecl}.  The rationale for rejecting the first ``invalid'' row follows shortly, while the second ``invalid'' row is simple nonsense, included to complete the pattern; its syntax hints at what the final row actually achieves.
-
-In the lefmost style, the typechecker ignores the actual value in most practical cases.
-This value is allowed to be a dynamic expression, so it is \emph{possible} to use the leftmost style in many practical cases.
+In the leftmost style, the typechecker ignores the actual value in most practical cases.
+This value is allowed to be a dynamic expression, and then it has practical cases.
+\begin{cfa}
+void foo( int @n@ ) {
+        float _42( float @a[n]@ ) {    // nested function
+                a[0] = 42;
+        }
+        float b[n];
+        _42( b );
+}
+\end{cfa}
+
 
 % To help contextualize the matrix part of this example, the syntaxes @float [5][]@, @float [][]@ and @float (*)[]@ are all rejected, for reasons discussed shortly.
 % So are @float[5]*@, @float[]*@ and @float (*)*@.  These latter ones are simply nonsense, though they hint at ``1d array of pointers'', whose equivalent syntax options are, @float *[5]@, @float *[]@, and @float **@.
 
-It is a matter of taste as to whether a programmer should use a form as far left as possible (getting the most out of syntactically integrated comments), sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript this one'').
-
-Note that this equivalence of pointer and array declarations is special to paramters.
+It is a matter of taste as to whether a programmer should use a form as far left as possible (getting the most out of possible subscripting and dimension sizes), sticking to the right (avoiding false comfort from suggesting the typechecker is checking more than it is), or compromising in the middle (reducing unchecked information, yet clearly stating, ``I will subscript).
+
+Note that this equivalence of pointer and array declarations is special to parameters.
 It does not apply to local variables, where true array declarations are possible.
 \begin{cfa}
@@ -626 +639 @@
 float sum( float v[] );
 float arg = 3.14;
-sum( &arg );                                                            $\C{// accepted, v := \&arg}$
+sum( &arg );                                                            $\C{// accepted, v = \&arg}$
 \end{cfa}
 
@@ -672 +685 @@
 Here, the distance between the first and second elements of each array depends on the inner dimension size.
 
-The last observation is a fact of the callee's perspective.
-There is little type-system checking, in the caller's perspective, that what is being passed, matches.
-\begin{cfa}
-void f( float [][10] );
-int n = 100;
-float a[100], b[n];
-f(&a); // reject
-f(&b); // accept
-\end{cfa}
-This size is therefore, a callee's assumption.
-
-Finally, to handle higher-dimensional VLAs, C repurposed the @*@ \emph{within} the dimension in a declaration to mean that the callee will have make an assumption about the size here, but no (unchecked, possibly wrong) information about this assumption is included for the caller-programmer's benefit/overconfidence.
+This significance of an inner dimension's length is a fact of the callee's perspective.
+In the caller's perspective, the type sytem is quite lax.
+Here, there is (some, but) little checking that what is being passed, matches.
+% void f( float [][10] );
+% int n = 100;
+% float a[100], b[n];
+% f(&a); // reject
+% f(&b); // accept
+\begin{cfa}
+void foo() {
+        void f( float [][10] );
+        int n = 100;
+        float a[100], b[3][12], c[n], d[n][n];
+        f( a );
+        f( b );    $\C{// reject: inner dimension 12 for 10}$
+        f( c );
+        f( @d@ );  $\C{// accept with inner dimension n for 10}$
+        f( &a );   $\C{// reject: inner dimension 100 for 10}$
+        f( &b );
+        f( @&c@ ); $\C{// accept with inner dimension n for 10}$
+        f( &d );
+}
+\end{cfa}
+The cases without comments are rejections, but simply because the array ranks do not match; in the commented cases, the ranks match and the rules being discussed apply.
+The cases @f(b)@ and @f(&a)@ show where some length checking occurs.
+But this checking misses the cases @f(d)@ and @f(&c)@, allowing the calls with mismatched lengths, actually 100 for 10.
+The C checking rule avoids false alarms, at the expense of safety, by allowing any combinations that involve dynamic values.
+Ultimately, an inner dimension's size is a callee's \emph{assumption} because the type system uses declaration details in the callee's perspective that it does not enforce in the caller's perspective.
+
+Finally, to handle higher-dimensional VLAs, C repurposed the @*@ \emph{within} the dimension in a declaration to mean that the callee has make an assumption about the size, but no (unchecked, possibly wrong) information about this assumption is included for the caller-programmer's benefit/over-confidence.
 \begin{cquote}
 @[@ \textit{type-qualifier-list$_{opt}$} @* ]@
@@ -1162 +1193 @@
 with all the variance being due to the (inevitable) cache status of the nodes being managed.
 
+
 \section{String}
+\label{s:String}
 
 A string is a sequence of symbols, where the form of a symbol can vary significantly: 7/8-bit characters (ASCII/Latin-1), or 2/4/8-byte (UNICODE) characters/symbols or variable length (UTF-8/16/32) characters.

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

@@ -30 +30 @@
 forall( [C], [S] )
 int getPref( @School( C, S ) & school@, int is, int pref ) {
-    for ( ic; C ) {
-        int curPref = @school.preferences@[ic][is];   $\C{// offset calculation implicit}$
+        for ( ic; C ) {
+                int curPref = @school.preferences@[ic][is];   $\C{// offset calculation implicit}$
                 if ( curPref == pref ) return ic;
         }
-    assert( false );
+        assert( false );
 }
 
@@ -59 +59 @@
 
         {       string sv;
-        int iv;
-        // headers' row
-        sin | "\nc\\s";
-        for ( is ; ns ) {
-            // column label
-            sin | sv;
-            school.student_ids[is] = sv;
-        }
-        // body rows
-        for ( ic ; nc ) {
-            // row label
-            sin | sv;
-            school.course_codes[ic] = sv;
-            for ( is ; ns ) {
-                // matrix item
-                sin | iv;
-                school.preferences[ic][is] = iv;
-            }
-        }
-    }
+                int iv;
+                // headers' row
+                sin | "\nc\\s";
+                for ( is ; ns ) {
+                        // column label
+                        sin | sv;
+                        school.student_ids[is] = sv;
+                }
+                // body rows
+                for ( ic ; nc ) {
+                        // row label
+                        sin | sv;
+                        school.course_codes[ic] = sv;
+                        for ( is ; ns ) {
+                                // matrix item
+                                sin | iv;
+                                school.preferences[ic][is] = iv;
+                        }
+                }
+        }
 
 
@@ -91 +91 @@
                 sout | school.student_ids[is] | ": " | nonl;
                 for ( pref; 1 ~= nc ) {
-            int ic = getPref(school, is, pref);
-            sout | school.course_codes[ ic ] | nonl;
+                        int ic = getPref(school, is, pref);
+                        sout | school.course_codes[ ic ] | nonl;
                 }
                 sout | nl;

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

@@ -114 +114 @@
         f( y, y );              $\C{// ok}$
         if ( M == N )
-                f( x, @(array( float, M ) &)@y ); $\C{// ok}$
+                f( x, @(array( float, M ) &)@y ); $\C{// ok}\CRT$
 }
 

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

@@ -5 +5 @@
 #define str(s) #s
 
+ofstream outfile;
+
 void demo1() {
         sout | sepOff;
-        sout | "Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
+//      sout | "Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@.";
 
         #define S1 string s1  = "abc"
@@ -21 +20 @@
         assert( s1a == "abc" );
         assert( s2 == "abc" );
-        sout | xstr(S1) | "\t\\\\";
-        sout | xstr(S1A) | "\t\\\\";
-        sout | xstr(S2) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-        sout | "Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
-        sout | "\t\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+
+        open( outfile, "build/sharing1.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{@{}llll@{}}";
+        outfile | "\t\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
+        outfile | xstr(S1) | "\t\\\\";
+        outfile | xstr(S1A) | "\t\\\\";
+        outfile | xstr(S2) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.";
+        open( outfile, "build/sharing2.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{@{}llll@{}}";
+        outfile | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1s1 s1 [1] = '+'
         S1s1;
         assert( s1 == "a+c" );
-        sout | xstr(S1s1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1s1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1As1 s1a[1] = '-'
         S1As1;
         assert( s1a == "a-c" );
-        sout | xstr(S1As1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1As1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S2s1 s2 [1] = '|'
         S2s1;
         assert( s2 == "a|c" );
-        sout | xstr(S2s1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-        sout | "Assignment of a value is just a modificiation."
-                   "\nThe aliasing relationship is established at construction and is unaffected by assignment of a value.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
-        sout | "\t\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S2s1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Assignment of a value is just a modificiation."
+//                 "\nThe aliasing relationship is established at construction and is unaffected by assignment of a value.";
+        open( outfile, "build/sharing3.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llll}";
+        outfile | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1qrs s1  = "qrs"
         S1qrs;
         assert( s1 == "qrs" );
-        sout | xstr(S1qrs) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1qrs) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1Atuv s1a = "tuv"
         S1Atuv;
         assert( s1a == "tuv" );
-        sout | xstr(S1Atuv) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1Atuv) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S2wxy s2  = "wxy"
         S2wxy;
         assert( s2 == "wxy" );
-        sout | xstr(S2wxy) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-        sout | "Assignment from a string is just assignment of a value."
-                   "\nWhether of not the RHS participates in aliasing is irrelevant.  Any aliasing of the LHS is unaffected.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
-        sout | "\t\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S2wxy) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2;
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Assignment from a string is just assignment of a value."
+//                 "\nWhether of not the RHS participates in aliasing is irrelevant.  Any aliasing of the LHS is unaffected.";
+        open( outfile, "build/sharing4.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llll}";
+        outfile | "\t\t& @s1@\t& @s1a@\t& @s2@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1S2 s1  = s2
@@ -86 +96 @@
         assert( s1a == "wxy" );
         assert( s2 == "wxy" );
-        sout | xstr(S1S2) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1S2) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S1aaa s1  = "aaa"
@@ -93 +103 @@
         assert( s1a == "aaa" );
         assert( s2 == "wxy" );
-        sout | xstr(S1aaa) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S1aaa) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S2S1 s2  = s1
@@ -100 +110 @@
         assert( s1a == "aaa" );
         assert( s2 == "aaa" );
-        sout | xstr(S2S1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S2S1) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S2bbb s2  = "bbb"
@@ -107 +117 @@
         assert( s1a == "aaa" );
         assert( s2 == "bbb" );
-        sout | xstr(S2bbb) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
-      
-    #define S2S1a s2  = s1a
+        outfile | xstr(S2bbb) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+
+        #define S2S1a s2  = s1a
         S2S1a;
         assert( s1 == "aaa" );
         assert( s1a == "aaa" );
         assert( s2 == "aaa" );
-        sout | xstr(S2S1a) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(S2S1a) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
 
         #define S2ccc s2  = "ccc"
@@ -121 +131 @@
         assert( s1a == "aaa" );
         assert( s2 == "ccc" );
-        sout | xstr(S2ccc) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
-      
+        outfile | xstr(S2ccc) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+
         #define S1xxx s1  = "xxx"
         S1xxx;
@@ -128 +138 @@
         assert( s1a == "xxx" );
         assert( s2 == "ccc" );
-        sout | xstr(S1xxx) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par";
+        outfile | xstr(S1xxx) | "\t& " | s1 | "\t& " | s1a | "\t& " | s2 | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
 }
 
 
 void demo2() {
-        sout | "Consider new strings @s1_mid@ being an alias for a run in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
+//      sout | "Consider new strings @s1_mid@ being an alias for a run in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.";
+        open( outfile, "build/sharing5.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
 
         #define D2_s1_abcd string s1     = "abcd"
         D2_s1_abcd;
-        sout | xstr(D2_s1_abcd) | "\t\\\\";
+        outfile | xstr(D2_s1_abcd) | "\t\\\\";
 
         #define D2_s1mid_s1 string s1_mid = s1(1,2)`shareEdits
         D2_s1mid_s1;
-        sout | xstr(D2_s1mid_s1) | "\t\\\\";
+        outfile | xstr(D2_s1mid_s1) | "\t\\\\";
 
         #define D2_s2_s1 string s2     = s1(1,2)
-        D2_s2_s1;      
+        D2_s2_s1;
         assert( s1 == "abcd" );
         assert( s1_mid == "bc" );
         assert( s2 == "bc" );
-        sout | xstr(D2_s2_s1) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-    sout | "Again, @`shareEdits@ passes changes in both directions; copy does not.  Note the difference in index values, with the \\emph{b} position being 1 in the longer string and 0 in the shorter strings.  In the case of s1 aliasing with @s1_mid@, the very same character is being accessed by different postitions.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
-        sout | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(D2_s2_s1) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Again, @`shareEdits@ passes changes in both directions; copy does not.  Note the difference in index values, with the \\emph{b} position being 1 in the longer string and 0 in the shorter strings.  In the case of s1 aliasing with @s1_mid@, the very same character is being accessed by different postitions.";
+        open( outfile, "build/sharing6.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
 
         #define D2_s1_plus s1    [1] = '+'
@@ -168 +182 @@
         assert( s1_mid == "+c" );
         assert( s2 == "bc" );
-        sout | xstr(D2_s1_plus) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(D2_s1_plus) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
 
         #define D2_s1mid_minus s1_mid[0] = '-'
@@ -175 +189 @@
         assert( s1_mid == "-c" );
         assert( s2 == "bc" );
-        sout | xstr(D2_s1mid_minus) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
-      
-    #define D2_s2_pipe s2    [0] = '|'
+        outfile | xstr(D2_s1mid_minus) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+
+        #define D2_s2_pipe s2    [0] = '|'
         D2_s2_pipe;
         assert( s1 == "a-cd" );
         assert( s1_mid == "-c" );
         assert( s2 == "|c" );
-        sout | xstr(D2_s2_pipe) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-    sout | "Once again, assignment of a value is a modificiation that flows through the aliasing relationship, without affecting its structure.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
-        sout | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | xstr(D2_s2_pipe) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Once again, assignment of a value is a modificiation that flows through the aliasing relationship, without affecting its structure.";
+        open( outfile, "build/sharing7.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_mid@\t& @s2@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
 
         #define D2_s1mid_ff s1_mid = "ff"
@@ -197 +213 @@
         assert( s1_mid == "ff" );
         assert( s2 == "|c" );
-        sout | xstr(D2_s1mid_ff) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
-      
+        outfile | xstr(D2_s1mid_ff) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+
         #define D2_s2_gg s2     = "gg"
         D2_s2_gg;
@@ -204 +220 @@
         assert( s1_mid == "ff" );
         assert( s2 == "gg" );
-        sout | xstr(D2_s2_gg) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-    sout | "In the \\emph{ff} step, which is a positive example of flow across an aliasing relationship, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).  The following rules for edits through aliasing substrings will guide how to flow in the opposite direction.";
-        sout | "\\par";
-
-
-    sout | "Growth and shrinkage are natural extensions.  An empty substring is a real thing, at a well-defined location, whose meaning is extrapolated from the examples so far.  The intended metaphor is to operating a GUI text editor.  Having an aliasing substring is like using the mouse to select a few words.  Assigning onto an aliasign substring is like typing from having a few words selected:  depending how much you type, the file being edited can get shorter or longer.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{lll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_mid@\t\\\\";
-        sout | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+        outfile | xstr(D2_s2_gg) | "\t& " | s1 | "\t& " | s1_mid | "\t& " | s2 | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "In the \\emph{ff} step, which is a positive example of flow across an aliasing relationship, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).  The following rules for edits through aliasing substrings will guide how to flow in the opposite direction.";
+//      sout | "\\par";
+
+
+//      sout | "Growth and shrinkage are natural extensions.  An empty substring is a real thing, at a well-defined location, whose meaning is extrapolated from the examples so far.  The intended metaphor is to operating a GUI text editor.  Having an aliasing substring is like using the mouse to select a few words.  Assigning onto an aliasign substring is like typing from having a few words selected:  depending how much you type, the file being edited can get shorter or longer.";
+        open( outfile, "build/sharing8.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{lll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_mid@\t\\\\";
+        outfile | "\\multicolumn{1}{r}{initial} & " | s1 | "\t& " | s1_mid | "\t\\\\";
 
         assert( s1 == "affd" );
-//      assert( s1_mid == "fc" );                                                     // ????????? bug?
-        sout | xstr(D2_s2_gg) | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+//      assert( s1_mid == "fc" );                                                                                                        // ????????? bug?
+        outfile | xstr(D2_s2_gg) | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
 
         #define D2_s1mid_hhhh s1_mid = "hhhh"
@@ -226 +244 @@
         assert( s1 == "ahhhhd" );
         assert( s1_mid == "hhhh" );
-        sout  | xstr(D2_s1mid_hhhh)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
-      
+        outfile  | xstr(D2_s1mid_hhhh)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+
         #define D2_s1mid_i s1_mid = "i"
         D2_s1mid_i;
         assert( s1 == "aid" );
         assert( s1_mid == "i" );
-        sout  | xstr(D2_s1mid_i)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+        outfile  | xstr(D2_s1mid_i)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
 
         #define D2_s1mid_empty s1_mid = ""
@@ -238 +256 @@
         assert( s1 == "ad" );
         // assert( s1_mid == "" );    ------ Should be so, but fails
-        sout  | xstr(D2_s1mid_empty)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+        outfile  | xstr(D2_s1mid_empty)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
 
         #define D2_s1mid_jj s1_mid = "jj"
@@ -244 +262 @@
         assert( s1 == "ajjd" );
         assert( s1_mid == "jj" );
-        sout  | xstr(D2_s1mid_jj)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-    sout | "Multiple portions can be aliased.  When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.  I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{lllll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_bgn@\t& @s1_mid@\t& @s1_end@\t\\\\";
+        outfile  | xstr(D2_s1mid_jj)  | "\t& " | s1 | "\t& " | s1_mid | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "Multiple portions can be aliased.  When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.  I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else.";
+        open( outfile, "build/sharing9.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{lllll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_bgn@\t& @s1_mid@\t& @s1_end@\t\\\\";
 
         #define D2_s1bgn_s1     string s1_bgn = s1(0, 1)`shareEdits
         D2_s1bgn_s1;
-        sout  | xstr(D2_s1bgn_s1)  | "\t\\\\";
+        outfile  | xstr(D2_s1bgn_s1)  | "\t\\\\";
 
         #define D2_s1end_s1 string s1_end = s1(3, 1)`shareEdits
@@ -263 +283 @@
         assert( s1_mid == "jj" );
         assert( s1_end == "d" );
-        sout  | xstr(D2_s1end_s1)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
-      
+        outfile  | xstr(D2_s1end_s1)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
+
         #define D1_s1bgn_zzz s1_bgn = "zzzz"
         D1_s1bgn_zzz;
@@ -271 +291 @@
         assert( s1_mid == "jj" );
         assert( s1_end == "d" );
-        sout  | xstr(D1_s1bgn_zzz)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-
-    sout | "When an edit happens on an aliasing substring that overlaps another, an effect is unavoidable.  Here, the passive party sees its selection shortened, to exclude the characters that were not part of the original selection.";
-        sout | "\\par\\noindent";
-        sout | "\\begin{tabular}{llllll}";
-        sout | "\t\t\t\t& @s1@\t& @s1_bgn@\t& @s1_crs@\t& @s1_mid@\t& @s1_end@\t\\\\";
+        outfile  | xstr(D1_s1bgn_zzz)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+//      sout | "When an edit happens on an aliasing substring that overlaps another, an effect is unavoidable.  Here, the passive party sees its selection shortened, to exclude the characters that were not part of the original selection.";
+        open( outfile, "build/sharing10.tex" );
+        outfile | "\\begin{cquote}";
+        outfile | "\\begin{tabular}{llllll}";
+        outfile | "\t\t\t\t& @s1@\t& @s1_bgn@\t& @s1_crs@\t& @s1_mid@\t& @s1_end@\t\\\\";
 
         #define D2_s1crs_s1 string s1_crs = s1(3, 2)`shareEdits
@@ -286 +308 @@
         assert( s1_crs == "zj" );
         assert( s1_mid == "jj" );
-        assert( s1_end == "d" );  
-        sout  | xstr(D2_s1crs_s1)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_crs | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
+        assert( s1_end == "d" );
+        outfile  | xstr(D2_s1crs_s1)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_crs | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
 
         #define D2_s1crs_ppp s1_crs = "+++"
@@ -296 +318 @@
         assert( s1_mid == "j" );
         assert( s1_end == "d" );
-        sout  | xstr(D2_s1crs_ppp)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_crs | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
-        sout | "\\end{tabular}";
-        sout | "\\par\\noindent";
-        sout | "TODO: finish typesetting the demo";
-
-    // "This shortening behaviour means that a modification has to occur entirely inside a substring, to show up in that substring.  Sharing changes through the intersection of partially overlapping aliases is still possible, so long as the receiver's boundary is not inside the edit."
+        outfile  | xstr(D2_s1crs_ppp)  | "\t& " | s1 | "\t& " | s1_bgn | "\t& " | s1_crs | "\t& " | s1_mid | "\t& " | s1_end | "\t\\\\";
+        outfile | "\\end{tabular}";
+        outfile | "\\end{cquote}";
+        close( outfile );
+
+        // "This shortening behaviour means that a modification has to occur entirely inside a substring, to show up in that substring.  Sharing changes through the intersection of partially overlapping aliases is still possible, so long as the receiver's boundary is not inside the edit."
 
         string word = "Phi";
@@ -309 +331 @@
         assert( consonants == "Ph" );
         assert( miniscules == "hi" );
-      
+
         consonants[1] = 's';
         assert( word == "Psi" );
@@ -321 +343 @@
         string greet_bgn = all(10,1)`shareEdits;
         string greet_end = all(14,1)`shareEdits;
-      
+
         assert( all == "They said hello again" );
         assert( greet == "hello" );
         assert( greet_bgn == "h" );
         assert( greet_end == "o" );
-      
+
 
         greet = "sup";
@@ -333 +355 @@
         // assert( greet_bgn == "" );    ------ Should be so, but fails
         // assert( greet_end == "" );
-      
-
-  
-
-  
-    /* As in the earlier step where \emph{aj} becomes \emph{ajjd}, such empty substrings maintain their places in the total string, and can be used for filling it.  Because @greet_bgn@ was orginally at the start of the edit, in the outcome, the empty @greet_bgn@ sits just before the written value.  Similarly @greed_end@ goes after.  Though not shown, an overwritten substring at neither side goes arbitrarily to the before side. */
-  
-
-  
-
-        greet_bgn = "what"; 
-      
-      
+
+
+
+
+
+        /* As in the earlier step where \emph{aj} becomes \emph{ajjd}, such empty substrings maintain their places in the total string, and can be used for filling it.  Because @greet_bgn@ was orginally at the start of the edit, in the outcome, the empty @greet_bgn@ sits just before the written value.  Similarly @greed_end@ goes after.  Though not shown, an overwritten substring at neither side goes arbitrarily to the before side. */
+
+
+
+
+        greet_bgn = "what";
+
+
         assert( all == "They said whatsup again" );
-      
+
         assert( greet == "sup" );
-      
+
         assert( greet_bgn == "what" );
         // assert( greet_end == "" );    ------ Should be so, but fails
-      
-
-        greet_end = "..."; 
-      
-      
+
+
+        greet_end = "...";
+
+
         assert( all == "They said whatsup... again" );
-      
+
         assert( greet == "sup" );
-      
+
         assert( greet_bgn == "what" );
-      
+
         assert( greet_end == "..." );
-      
-
-  
-
-  
-    /* Though these empty substrings hold their places in the total string, an empty string only belongs to bigger strings when it occurs completely inside them.  There is no such state as including an empty substring at an edge.  For this reason, @word@ gains the characters added by assigning to @greet_bgn@ and @greet_end@, but the string @greet@ does not. */
-  
+
+
+
+
+
+        /* Though these empty substrings hold their places in the total string, an empty string only belongs to bigger strings when it occurs completely inside them.  There is no such state as including an empty substring at an edge.  For this reason, @word@ gains the characters added by assigning to @greet_bgn@ and @greet_end@, but the string @greet@ does not. */
+
 
 }
@@ -377 +399 @@
 int main(int argc, char ** argv) {
 
-    demo1();
-    demo2();
-    printf("%% %s done running\n", argv[0]);
+        demo1();
+        demo2();
+//      printf("%% %s done running\n", argv[0]);
 }

doc/theses/mike_brooks_MMath/string.tex

@@ -5 +5 @@
 
 
-\section{Logical overlap}
-
-\input{sharing-demo.tex}
+\section{String Operations}
+
+To prepare for the following discussion, a simple comparison among C, \CC, and \CFA basic string operation is presented.
+\begin{cquote}
+\begin{tabular}{@{}l|l|l@{}}
+C @char [ ]@                    &  \CC @string@                 & \CFA @string@ \\
+\hline
+@strcpy@, @strncpy@             & @=@                                   & @=@   \\
+@strcat@, @strncat@             & @+@                                   & @+@   \\
+@strcmp@, @strncmp@             & @==@, @!=@, @<@, @<=@, @>@, @>=@ & @==@, @!=@, @<@, @<=@, @>@, @>=@ \\
+@strlen@                                & @length@                              & @size@        \\
+@[ ]@                                   & @[ ]@                                 & @[ ]@ \\
+                                                & @substr@                              & @substr@      \\
+                                                & @replace@                             & @=@ \emph{(on a substring)}\\
+@strstr@                                & @find@, @rfind@               & @find@, MISSING \\
+@strcspn@                               & @find_first_of@, @find_last_of@ & @include@, MISSING \\
+@strspn@                                & @find_first_not_of@, @find_last_not_of@ & @exclude@, MISSING \\
+                                                & @c_str@                               & MISSING \\
+\end{tabular}
+\end{cquote}
+The key commonality is that operations work on groups of characters for assigning. copying, scanning, and updating.
+Because a C string is null terminated and requires explicit storage management \see{\VRef{s:String}}, most of its group operations are error prone and expensive.
+Most high-level string libraries use a separate length field and specialized storage management to support group operations.
+\CC strings retain null termination to interface with library functions requiring C strings.
+\begin{cfa}
+int open( const char * pathname, int flags );
+string fname{ "test.cc" );
+open( fname.@c_str()@ );
+\end{cfa}
+The function @c_str@ does not create a new null-terminated C string from the \CC string, as that requires passing ownership of the C string to the caller for eventual deletion.\footnote{
+C functions like \lstinline{strdup} do return allocated storage that must be freed by the caller.}
+Instead, each \CC string is null terminator just in case it might be needed for this purpose.
+Providing this backwards compatibility with C has a ubiquitous performance and storage cost.
+
+
+\section{Storage Management}
+
+This section discusses issues related to storage management of strings.
+Specifically, it is common for strings to logically overlap completely or partially.
+\begin{cfa}
+string s1 = "abcdef";
+string s2 = s1; $\C{// complete overlap, s2 == "abcdef"}$
+string s3 = s1.substr( 0, 3 ); $\C{// partial overlap, s3 == "abc"}$
+\end{cfa}
+This raises the question of how strings behave when an overlapping component is changed,
+\begin{cfa}
+s3[1] = 'w'; $\C{// what happens to s1 and s2?}$
+\end{cfa}
+This question is the notion of mutable or immutable strings.
+For example, Java has immutable strings that are copied when any overlapping string changes.
+Note, the notion of underlying string mutability is not specified by @const@, \eg:
+\begin{cfa}
+const string s1 = "abc";
+\end{cfa}
+Here, @const@ applies to the @s1@ pointer to @"abc"@, and @"abc"@ is an immutable constant that is \emph{copied} into the string's storage.
+Hence, @s1@ is not pointing at an immutable constant, meaning its underlying string is always mutable, unless some other designation is specified, such as Java's global rule.
+
+
+\subsection{Logical overlap}
+
+\CFA provides a dynamic mechanism to indicate mutable or immutable as an assignment attribute: @`shareEdits@.
 
 Consider two strings @s1@ and @s1a@ that are in an aliasing relationship, and a third, @s2@, made by a simple copy from @s1@.
-\par\noindent
-\begin{tabular}{llll}
-                                & @s1@  & @s1a@ & @s2@  \\
-%\input{sharing-demo1.tex}
-\end{tabular}
-\par\noindent
+Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.
+\input{sharing1.tex}
+
+Aliasing (@`shareEdits@) means that changes flow in both directions; with a simple copy, they do not.
+\input{sharing2.tex}
+
+Assignment of a value is just a modification.
+The aliasing relationship is established at construction and is unaffected by assignment of a value.
+\input{sharing3.tex}
+
+Assignment from a string is just assignment of a value.
+Whether of not the RHS participates in aliasing is irrelevant.  Any aliasing of the LHS is unaffected.
+\input{sharing4.tex}
+
+Consider new strings @s1_mid@ being an alias for a run in the middle of @s1@, along with @s2@, made by a simple copy from the middle of @s1@.
+\input{sharing5.tex}
+
+Again, @`shareEdits@ passes changes in both directions; copy does not.
+Note the difference in index values, with the \emph{b} position being 1 in the longer string and 0 in the shorter strings.
+In the case of s1 aliasing with @s1_mid@, the very same character is being accessed by different positions.
+\input{sharing6.tex}
+
+Once again, assignment of a value is a modification that flows through the aliasing relationship, without affecting its structure.
+\input{sharing7.tex}
+
+In the \emph{ff} step, which is a positive example of flow across an aliasing relationship, the result is straightforward to accept because the flow direction is from contained (small) to containing (large).
+The following rules for edits through aliasing substrings will guide how to flow in the opposite direction.
+
+Growth and shrinkage are natural extensions.
+An empty substring is a real thing, at a well-defined location, whose meaning is extrapolated from the examples so far.
+The intended metaphor is to operating a GUI text editor.
+Having an aliasing substring is like using the mouse to select a few words.
+Assigning onto an aliasing substring is like typing from having a few words selected: depending how much you type, the file being edited can get shorter or longer.
+\input{sharing8.tex}
+
+Multiple portions can be aliased.
+When there are several aliasing substrings at once, the text editor analogy becomes an online multi-user editor.
+I should be able to edit a paragraph in one place (changing the document's length), without my edits affecting which letters are within a mouse-selection that you had made previously, somewhere else.
+\input{sharing9.tex}
+
+When an edit happens on an aliasing substring that overlaps another, an effect is unavoidable.
+Here, the passive party sees its selection shortened, to exclude the characters that were not part of the original selection.
+\input{sharing10.tex}
+
+TODO: finish typesetting the demo
+
+%\input{sharing-demo.tex}
 
 
 \subsection{RAII limitations}
 
-Earlier work on \CFA [to cite Schluntz] implemented the feature of constructors and destructors.  A constructor is a user-defined function that runs implicitly, when control passes an object's declaration, while a destructor runs at the exit of the declaration's lexical scope.  The feature allows programmers to assume that, whenever a runtime object of a certain type is accessible, the system called one of the programmer's constructor functions on that object, and a matching destructor call will happen in the future.  The feature helps programmers know that their programs' invariants obtain.
-
-The purposes of such invariants go beyond ensuring authentic values for the bits inside the object.   These invariants can track occurrences of the managed objects in other data structures.  Reference counting is a typical application of the latter invariant type.  With a reference-counting smart pointer, the constructor and destructor \emph{of the pointer type} track the life cycles of occurrences of these pointers, by incrementing and decrementing a counter (usually) on the referent object, that is, they maintain a that is state separate from the objects to whose life cycles they are attached.  Both the \CC and \CFA RAII systems ares powerful enough to achieve such reference counting.
-
-The \CC RAII system supports a more advanced application.  A life cycle function has access to the object under management, by location; constructors and destuctors receive a @this@ parameter providing its memory address.  A lifecycle-function implementation can then add its objects to a collection upon creation, and remove them at destruction.  A modulue that provides such objects, by using and encapsulating such a collection, can traverse the collection at relevant times, to keep the objects ``good.''  Then, if you are the user of such an module, declaring an object of its type means not only receiving an authentically ``good'' value at initialization, but receiving a subscription to a service that will keep the value ``good'' until you are done with it.
-
-In many cases, the relationship between memory location and lifecycle is simple.  But with stack-allocated objects being used as parameters and returns, there is a sender version in one stack frame and a receiver version in another.  \CC is able to treat those versions as distinct objects and guarantee a copy-constructor call for communicating the value from one to the other.  This ability has implications on the language's calling convention.  Consider an ordinary function @void f( Vehicle x )@, which receives an aggregate by value.  If the type @Vehicle@ has custom lifecycle functions, then a call to a user-provided copy constructor occurs, after the caller evaluates its argument expression, after the callee's stack frame exists, with room for its variable @x@ (which is the location that the copy-constructor must target), but before the user-provided body of @f@ begins executing.  \CC achieves this ordering by changing the function signature, in the compiled form, to pass-by-reference and having the callee invoke the copy constructor in its preamble.  On the other hand, if @Vehicle@ is a simple structure then the C calling convention is applied as the code originally appeared, that is, the callsite implementation code performs a bitwise copy from the caller's expression result, into the callee's x.
-
-TODO: learn correction to fix inconcsistency: this discussion says the callee invokes the copy constructor, but only the caller knows which copy constructor to use!
-
-TODO: discuss the return-value piece of this pattern
-
-The \CFA RAII system has limited support for using lifecycle functions to provide a ``stay good'' service.  It works in restricted settings, including on dynamically allocated objects.  It does not work for communicating arguments and returns by value because the system does not produce a constructor call that tracks the implied move from a sender frame to a reciver frame.  This limitation does not prevent a typical reference-counting design from using call-with-value/return-of-value, because the constructor--destructor calls are correctly balanced.  But it impedes a ``stay-good'' service from supporting call-with-value/return-of-value, because the lifecycles presented to the constructor/destor calls do not keep stable locations.  A ``stay-good'' service is acheivable so long as call-with-value/return-of-value do not occur.  The original presentation [to cite Schluntz section] acknoweledges this limitiation; the present discussion makes its consequences more apparent.
-
-The \CFA team sees this limitation as part of a tactical interem state that should some day be improved.  The \CFA compiler is currently a source-to-source translator that targets relativly portable C.  Several details of its features are provisionally awkward or under-performant until finer control of its code generation is feasible.  In the present state, all calls that appear in \CFA source code as call-with-value/return-of-value are emitted this way to the underlying C calling convention.  SO WHAT?
-
-The present string-API contribution has both the ``stay good'' promise and call-with-value/return-of-value being essential.  The main string API uses a work-around to acheive the full feature set, at a runtime performance penalty.  An alternative API sacrifices call-with-value/return-of-value functionality to recover full runtime performance.  These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL).  They present the same features, up to lifecycle management, with call-with-value/return-of-value being disabled in LL and implemented with the workaround in HL.  The intention is for most future code to target HL.  In a more distant future state, where \CFA has an RAII system that can handle the problematic quadrant, the HL layer can be abolished, the LL can be renamed to match today's HL, and LL can have its call-with-value/return-of-value permission reenabled.  Then, programs written originally against HL will simply run faster.  In the meantime, two use cases of LL exist.  Performance-critical sections of applications have LL as an option.  Within [Xref perf experiments], though HL-v-LL penalties are measured, typcial comparisons of the contributed string libary vs similar systems are made using LL.  This measurement gives a fair estimate of the goal state for \CFA while it is an evloving work in progress.
-
+Earlier work on \CFA~\cite[ch.~2]{Schluntz17} implemented object constructors and destructors for all types (basic and user defined).
+A constructor is a user-defined function run implicitly \emph{after} an object's declaration-storage is created, and a destructor is a user-defined function run \emph{before} an object's declaration-storage is deleted.
+This feature, called RAII~\cite[p.~389]{Stroustrup94}, guarantees pre invariants for users before accessing an object and post invariants for the programming environment after an object terminates.
+
+The purposes of these invariants goes beyond ensuring authentic values inside an object.
+Invariants can also track occurrences of managed objects in other data structures.
+For example, reference counting is a typical application of an invariant outside of the data values.
+With a reference-counting smart-pointer, the constructor and destructor \emph{of a pointer type} tracks the life cycle of the object it points to.
+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.
+The lifecycle implementation can then add this object to a collection at creation and remove it at destruction.
+A module providing lifecycle semantics can traverse the collection at relevant times to keep the objects ``good.''
+Hence, declaring such an object not only ensures ``good'' authentic values, but also an implicit subscription to a service that keeps the value ``good'' across its lifetime.
+
+In many cases, the relationship between memory location and lifecycle is straightforward.
+For example, stack-allocated objects being used as parameters and returns, with a sender version in one stack frame and a receiver version in another, as opposed to assignment where sender and receiver are in the same stack frame.
+What is crucial for lifecycle management is knowing if the receiver is initialized or uninitialized, \ie an object is or is not currently associated with management.
+To provide this knowledge, languages differentiate between initialization and assignment to a left-hand side.
+\begin{cfa}
+Obj obj2 = obj1;  // initialization, obj2 is uninitialized
+obj2 = obj1;        // assignment, obj2 must be initialized for management to work
+\end{cfa}
+Initialization occurs at declaration by value, parameter by argument, return temporary by function call.
+Hence, it is necessary to have two kinds of constructors: by value or object.
+\begin{cfa}
+Obj obj1{ 1, 2, 3 };  // by value, management is initialized
+Obj obj2 = obj1;     // by obj, management is updated
+\end{cfa}
+When no object management is required, initialization copies the right-hand value.
+Hence, the calling convention remains uniform, where the unmanaged case uses @memcpy@ as the initialization constructor and managed uses the specified initialization constructor.
+
+The \CFA RAII system supports lifecycle functions, except for returning a value from a function to a temporary.
+For example, in \CC:
+\begin{cfa}
+struct S {...};
+S identity( S s ) { return s; }
+S s;
+s = identity( s ); // S temp = identity( s ); s = temp;
+\end{cfa}
+the generated code for the function call created a temporary with initialization from the function call, and then assigns the temporary to the receiver.
+This two step approach means extra storage for the temporary and two copies to get the result into the receiver variable.
+\CC{17} introduced return value-optimization (RVO)~\cite{RVO20} to ``avoid copying an object that a function returns as its value, including avoiding creation of a temporary object''.
+\CFA uses C semantics for function return giving direct value-assignment, which eliminates unnecessary code, but skips an essential feature needed by lifetime management.
+The following discusses the consequences of this semantics with respect to lifetime management of \CFA strings.
+
+The present string-API contribution provides lifetime management with initialization semantics on function return.
+The workaround to achieve the full lifetime semantics does have a runtime performance penalty.
+An alternative API sacrifices return initialization semantics to recover full runtime performance.
+These APIs are layered, with the slower, friendlier High Level API (HL) wrapping the faster, more primitive Low Level API (LL).
+Both API present the same features, up to lifecycle management, with return initialization being disabled in LL and implemented with the workaround in HL.
+The intention is for most future code to target HL.
+When \CFA becomes a full compiler, it can provide return initialization with RVO optimizations.
+Then, programs written with the HL API will simply run faster.
+In the meantime, performance-critical sections of applications use LL.
+Subsequent performance experiments~\VRef{s:PerformanceAssessment} with other string libraries has \CFA strings using the LL API.
+These measurement gives a fair estimate of the goal state for \CFA.
 
 
 \subsection{Memory management}
 
-A centrepriece of the string module is its memory manager.  The managment scheme defines a large shared buffer for strings' text.  Allocation in this buffer is always bump-pointer; the buffer is compacted and/or relocated with growth when it fills.  A string is a smart pointer into this buffer.
-
-This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC).  A few differences are noteworthy.  First, in a general purpose manager, the objects of allocation contain pointers to other such objects, making the transitive reachability of these objects be a critical property.  Here, the allocations are of buffers of text, never pointers, so one allocation never keeps another one alive.  Second, in a general purpose manager, where the handle that keeps an allocation alive is the same as the program's general-purpose inter-object reference, an extremely lean representation of this reference is required.  Here, a fatter representation is acceptable because [why??].
-
-
-Figure [memmgr-basix.vsdx] shows the representation.  A heap header, with its text buffer, defines a sharing context.  Often, one global sharing context is appropriate for an entire program; exceptions are discussed in [xref TBD].  Strings are handles into the buffer.  They are members of a linked list whose order matches the order of their buffer fragments (exactly, where there is no overlapping, and approximately, where there is).  The header maintains a next-allocation pointer (alloc, in the figure) after the last live allocation of the buffer.  No external references into the buffer are allowed and the management procedure relocates the text allocations as needed.  The string handles contain explicit length fields, null termination characters are not used and all string text is kept in contiguous storage.  When strings (the inter-linked hanldes) are allocated on the program's call stack, a sustained period with no use of the program's dynamic memory allocator can ensue, during which the program nonetheless creates strings, destroys them, and runs length-increasing modifications on existing ones.  
-
-Compaction happens when the heap fills.  It is the first of two uses of the linked list.  The list allows discovering all live string handles, and from them, the ranges of the character buffer that are in use.  With these ranges known, their total character count gives the amount of space in use.  When that amount is small, compared with the current buffer size, an in-place compaction occurs, which enatils copying the in-use ranges, to be adjacent, at the font of the buffer.  When the in-use amount is large, a larger buffer is allocated (using the program's general-purpose dynamic allcator), the in-use strings are copied to be adjacent at the front of it, and the original buffer is freed back to the program's general allocator.  Either way, navigating the links between the handles provides the pointers into the buffer, first read, to find the source fragment, then written with the location of the resultant fragment.  This linkage across the structure is unaffected during a compaction; only the pointers from the handles to the buffer are modified.  This modification, along with the grooming/provisioning of the text storage resouce that it represents, is an example, in the language of [xref RAII limitations] of the string module providing a ``stay good'' service.
-
-Object lifecycle events are the subscription-management triggers in such a service.  There are two fundamental string-creation routines:  importing from external text like a C-string, and initialization from an existing \CFA string.  When importing, a fresh allocation at the free end fo the buffer occurs, into which the text is copied.  The resultant handle is therefore inserted into the list at the position after the incumbent last handle, a position given by the heap manager's ``last handle'' pointer.  When initializing from text already on the \CFA heap, the resultant handle is a second reference onto the original run of characters.  In this case, the resultant handle's linked-list position is beside the original handle.  Both string initialization styles preserve the string module's internal invriant that the linked-list order match the buffer order.  For string destruction, the list being doubly linked provides for easy removal of the disappearing handle.
-
-While a string handle is live, it accepts modification operations, some of which make it reference a different portion of the underlying buffer, and accordingly, move the handle to a different position in the inter-handle list.   While special cases have more optimal handling, the general case requires a fresh buffer run.  In this case, the new run is allocated at the bump-pointer end and filled with the required value.  Then, handles that originally referenced the old location and need to see the new value are pointed at the new buffer location, unlinked from their original positions in the handles' list, and linked in at the end of the list.  An optimal case, when the target is not a substring of something larger, and the source is text from elsewhere in the managed buffer, allows the target to be re-pointed at the source characters, and accordingly, move list position to be beside the source.  Cases where in-place editing happens, addressed further in [xref: TBD], leave affected handles in their original list positions.  In analogy to the two cases of string initialization, the two cases of realizing assignment by moving either to a fresh buffer run, or to overlap references with the source, maintain the invariant of linked list order matching buffer order.
-
-
-To explain: GCing allocator doing bump-pointer with compaction
-
-
-
-At the level of the memory manager, these modifications can aways be explained as assignments; for example, an append is an assignemnt into the empty substring at the end. 
-
-While favourable conditions allow for in-place editing, the general case requires a fresh buffer run.  For example, if the new value does not fit in the old place, or if other handles are still using the old value, then the new value will use a fresh buffer run.
+A centrepiece of the string module is its memory manager.
+The management scheme defines a shared buffer for string text.
+Allocation in this buffer is via a bump-pointer;
+the buffer is compacted and/or relocated with growth when it fills.
+A string is a smart pointer into this buffer.
+
+This cycle of frequent cheap allocations, interspersed with infrequent expensive compactions, has obvious similarities to a general-purpose memory manager based on garbage collection (GC).
+A few differences are noteworthy.
+First, in a general purpose manager, the objects of allocation contain pointers to other such objects, making the transitive reachability of these objects be a critical property.
+Here, the allocations are text, so one allocation never keeps another alive.
+Second, in a general purpose manager, the handle that keeps an allocation alive is just a lean pointer.
+For strings, a fatter representation is acceptable because there are fewer string head pointers versus chained pointers within nodes as for linked containers.
+
+\begin{figure}
+\includegraphics{memmgr-basic}
+\caption{String memory-management data structures}
+\label{f:memmgr-basic}
+\end{figure}
+
+\VRef[Figure]{f:memmgr-basic} shows the representation.
+A heap header and its text buffer, defines a sharing context.
+Normally, one global sharing context is appropriate for an entire program;
+exceptions are discussed in [xref TBD].
+A string is a handle into the buffer and linked into a list.
+The list is doubly linked for $O(1)$ insertion and removal at any location.
+Strings are orders n the list by text-buffer address, where there is no overlapping, and approximately, where there is.
+The header maintains a next-allocation pointer, @alloc@, pointing to the last live allocation of the buffer.
+No external references point into the buffer and the management procedure relocates the text allocations as needed.
+A string handle contains an explicit string, while its string is contiguous and not null terminated.
+The length sets an upper limit on the string size, but is large (4 or 8 bytes).
+String handles can be allocated in the stack or heap, while the text buffer is large enough with good management so that only one dynamic allocation is necessary for it during program execution.
+During this period strings can vary in size dynamically.
+
+When the text buffer fills, \ie the next new string allocation causes @alloc@ to point beyond the end of the buffer, the strings are compacted.
+The linked handles define all live strings in the buffer, which indirectly defines the allocated and free space in the buffer.
+Since the string handles are in (roughly) sorted order, the handle list can be traversed copying the first text to the start of the buffer and subsequent strings after each over.
+After compaction, if the amount of free storage is still less than the new string allocation, a larger text buffer is heap allocated, the current buffer is copies into the new buffer, and the original buffer is freed.
+Note, the list of string handles is unaffected during a compaction;
+only the string pointers are modified to new buffer locations.
+
+Object lifecycle events are the subscription-management triggers in such a service.
+There are two fundamental string-creation routines: 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 resultant handle is inserted at the end of the handle list to maintain ordering.
+When initializing from text already in the text 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.
+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.
+
+Certain string operations can results in a subset (substring) of another string.
+The resulting handle is then place in the correct sorted position in the list, possible with a short linear search to locate the position.
+For string operations resulting in a new string, that string is allocated at the end of the buffer.
+For shared-edit strings, handles that originally referenced containing locations need to see the new value at the new buffer location.
+These strings are moved to appropriate locations at the end of the list (addressed further in [xref: TBD].
+For nonshared-edit strings, a containing string can be moved and the nonshared strings can remain in the same position.
+String assignment words similarly to string initialization, maintain the invariant of linked list order matching buffer order.
+
+At the level of the memory manager, these modifications can always be explained as assignments; for example, an append is an assignment into the empty substring at the end. 
+
+While favourable conditions allow for in-place editing, the general case requires a fresh buffer run.
+For example, if the new value does not fit in the old place, or if other handles are still using the old value, then the new value will use a fresh buffer run.
 
 where there is room for the resulting value in the original buffer location, and where all handles referring to the original buffer location should see the new value, 
 
-
-always boiled down to assignment and appendment.  Assignment has special cases that happen in-place, but in the general case, it is implemented as a sequence of appends onto a fresh allocation at the end of the buffer.  (The sequence has multiple steps when the assignment target is a substring: old before, new middle, old after.)  Similarly, an append request can be serviced in-place when there is room, or as a pair of appends 
-
+always boiled down to assignment and appendment.
+Assignment has special cases that happen in-place, but in the general case, it is implemented as a sequence of appends onto a fresh allocation at the end of the buffer.
+(The sequence has multiple steps when the assignment target is a substring: old before, new middle, old after.)
+Similarly, an append request can be serviced in-place when there is room, or as a pair of appends.
 
 
 \subsection{Sharing implementation}
 
-The \CFA string module has two manners in which serveral string handles can share an unerlying run of characters.  
-
-The first type of sharing is user-requested, following the [xref Logical Overlap].  Here, the user requests, explicitly, that both handles be views of the same logical, modifiable string.  This state is typically prodecd by the substring operation.  In a typical substring call, the source string-handle is referencing an entire string, and the resluting, newly made, string handle is referencing a portion of the orignal.  In this state, a subsequent modification made by either is visible in both.
-
-The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization.  This state is typically produced by constructing a new string, using an original string as its intialization source.  In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different runs within the buffer, holding distinct values.
+The \CFA string module has two manners in which several string handles can share an underlying run of characters.  
+
+The first type of sharing is user-requested, following the [xref Logical Overlap].  Here, the user requests, explicitly, that both handles be views of the same logical, modifiable string.  This state is typically produced by the substring operation.  In a typical substring call, the source string-handle is referencing an entire string, and the resulting, newly made, string handle is referencing a portion of the original.  In this state, a subsequent modification made by either is visible in both.
+
+The second type of sharing happens when the system implicitly delays the physical execution of a logical \emph{copy} operation, as part of its copy-on-write optimization.  This state is typically produced by constructing a new string, using an original string as its initialization source.  In this state, a subsequent modification done on one handle triggers the deferred copy action, leaving the handles referencing different runs within the buffer, holding distinct values.
 
 A further abstraction, in the string module's implementation, helps distinguish the two senses of sharing.  A share-edit set (SES) is an equivalence class over string handles, being the reflexive, symmetric and transitive closure of the relationship of one being constructed from the other, with the ``share edits'' opt-in given.  It is represented by a second linked list among the handles.  A string that shares edits with no other is in a SES by itself.  Inside a SES, a logical modification of one substring portion may change the logical value in another, depending on whether the two actually overlap.  Conversely, no logical value change can flow outside of a SES.  Even if a modification on one string handle does not reveal itself \emph{logically} to anther handle in the same SES (because they don't overlap), if the modification is length-changing, completing the modification requires visiting the second handle to adjust its location in the sliding text.
@@ -84 +263 @@
 \subsection{Avoiding implicit sharing}
 
-There are tradeoffs associated with the copy-on-write mechanism.  Several quatitative matters are detailed in the [xref: Performance Assessment] section and the qualitiative issue of multi-threaded support is introduced here.  The \CFA sting library provides a switch to disable the sharing mechanism for situtations where it is inappropriate.
+There are tradeoffs associated with the copy-on-write mechanism.  Several qualitative matters are detailed in the [xref: Performance Assessment] section and the qualitative issue of multi-threaded support is introduced here.  The \CFA sting library provides a switch to disable the sharing mechanism for situations where it is inappropriate.
 
 Because of the inter-linked string handles, any participant managing one string is also managing, directly, the neighbouring strings, and from there, a data structure of the ``set of all strings.''  This data structure is intended for sequential access.  A negative consequence of this decision is that multiple threads using strings need to be set up so that they avoid attempting to modify (concurrently) an instance of this structure.  A positive consequence is that a single-threaded program, or a program with several independent threads, can use the sharing context without an overhead from locking.
 
-The \CFA sting library provides the @string_sharectx@ type to control an ambient sharing context for the current thread.  It allows two adjustments: to opt out of sharing entirely, or to begin sharing within a private context.  Either way, the chosen mode applies to the current thread, for the duration of the lifetime of the created  @string_sharectx@ object, up to being suspended by child liftimes of different contexts.  The indended use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that don't create their own contexts.
-\lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx-demo.cfa}
+The \CFA sting library provides the @string_sharectx@ type to control an ambient sharing context for the current thread.  It allows two adjustments: to opt out of sharing entirely, or to begin sharing within a private context.  Either way, the chosen mode applies to the current thread, for the duration of the lifetime of the created  @string_sharectx@ object, up to being suspended by child lifetimes of different contexts.  The indented use is with stack-managed lifetimes, in which the established context lasts until the current function returns, and affects all functions called that don't create their own contexts.
+\lstinputlisting[language=CFA, firstline=20, lastline=34]{sharectx.run.cfa}
 In this example, the single-letter functions are called in alphabetic order.  The functions @a@ and @d@ share string character ranges within themselves, but not with each other.  The functions @b@, @c@ and @e@ never share anything.
 
 [ TODO: true up with ``is thread local'' (implement that and expand this discussion to give a concurrent example, or adjust this wording) ]
 
-When the string library is running with sharing disabled, it runs without implicit thread-safety challenges (which same as the STL) and with performance goals similar to the STL's.  This thread-safety quality means concurrent users of one string object must still bring their own mutual exlusion, but the string libary will not add any cross thread uses that were not apparent in the user's code.
+When the string library is running with sharing disabled, it runs without implicit thread-safety challenges (which same as the STL) and with performance goals similar to the STL's.  This thread-safety quality means concurrent users of one string object must still bring their own mutual exclusion, but the string library will not add any cross thread uses that were not apparent in the user's code.
 
 Running with sharing disabled can be thought of as STL-emulation mode.
@@ -107 +286 @@
 
 
-\subsection{Performance assessment}
-
-I assessed the CFA string library's speed and memory usage.  I present these results ineven quivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality.  They also show the benefits and tradeoffs, as >100\% effects, of switching to CFA, with the tradeoff points quantified.  The final test shows the overall win of the CFA text-sharing mechanism.  It exercises several operations together, showing CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.
-
-To discuss: general goal of ... while STL makes you think about memory management, all the time, and if you do your performance can be great ... CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory mamangement.  [Does this position cover all of it?]
+\section{Performance assessment}
+\label{s:PerformanceAssessment}
+
+I assessed the \CFA string library's speed and memory usage.  I present these results in even equivalent cases, due to either micro-optimizations foregone, or fundamental costs of the added functionality.  They also show the benefits and tradeoffs, as >100\% effects, of switching to \CFA, with the tradeoff points quantified.  The final test shows the overall win of the \CFA text-sharing mechanism.  It exercises several operations together, showing \CFA enabling clean user code to achieve performance that STL requires less-clean user code to achieve.
+
+To discuss: general goal of ... while STL makes you think about memory management, all the time, and if you do your performance can be great ... \CFA sacrifices this advantage modestly in exchange for big wins when you're not thinking about memory management.  [Does this position cover all of it?]
 
 To discuss: revisit HL v LL APIs
 
-To discuss: revisit nosharing as STL emulation modes
+To discuss: revisit no-sharing as STL emulation modes
 
 These tests use randomly generated text fragments of varying lengths.  A collection of such fragments is a \emph{corpus}.  The mean length of a fragment from corpus is a typical explanatory variable.  Such a length is used in one of three modes:
@@ -121 +301 @@
     \item [Fixed-size] means all string fragments are of the stated size
     \item [Varying from 1] means string lengths are drawn from a geometric distribution with the stated mean, and all lengths occur
-    \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and obove occur; thus, the stated mean will be above 16.
+    \item [Varying from 16] means string lengths are drawn from a geometric distribution with the stated mean, but only lengths 16 and above occur; thus, the stated mean will be above 16.
 \end{description}
-The geometric distribution implies that lengths much longer than the mean occur frequently.  The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [todo: write and cross-ref future-work SSO]), currently not implmented in \CFA.  When success notwithstanding SSO is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side.  In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins.
+The geometric distribution implies that lengths much longer than the mean occur frequently.  The special treatment of length 16 deals with comparison to STL, given that STL has short-string optimization (see [TODO: write and cross-ref future-work SSO]), currently not implemented in \CFA.  When success notwithstanding SSO is illustrated, a fixed-size or from-16 distribution ensures that extra-optimized cases are not part of the mix on the STL side.  In all experiments that use a corpus, its text is generated and loaded into the SUT before the timed phase begins.
 
 To discuss: vocabulary for reused case variables
@@ -136 +316 @@
 \subsubsection{Test: Append}
 
-This test measures the speed of appending fragments of text onto a growing string.  Its subcases include both CFA being similar to STL, and their designs offering a tradeoff.
-
-One experimental variable is the user's operation being @a = a + b@ vs. @a += b@.  While experienced programmers expect the latter to be ``what you obviously should do,'' controling the penatly of the former both helps the API be accessible to beginners and also helps offer confidence that when a user tries to compose operations, the forms that are most natural to the user's composition are viable.
-
-Another experimental variable is whether the user's logical allocation is fresh vs reused.  Here, \emph{reusing a logical allocation}, means that the prgram variable, into which the user is concatenating, previously held a long string:\\
+This test measures the speed of appending fragments of text onto a growing string.  Its subcases include both \CFA being similar to STL, and their designs offering a tradeoff.
+
+One experimental variable is the user's operation being @a = a + b@ vs. @a += b@.  While experienced programmers expect the latter to be ``what you obviously should do,'' controlling the penalty of the former both helps the API be accessible to beginners and also helps offer confidence that when a user tries to compose operations, the forms that are most natural to the user's composition are viable.
+
+Another experimental variable is whether the user's logical allocation is fresh vs reused.  Here, \emph{reusing a logical allocation}, means that the program variable, into which the user is concatenating, previously held a long string:\\
 \begin{tabular}{ll}
     Logical allocation fresh                   & Logical allocation reused                  \\
@@ -150 +330 @@
     @ } @                                      & @ } @
 \end{tabular}\\
-These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.''  It is sensible to doubt that a user should have to care about this difference, yet the STL performs differently in these cases.  Concretly, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length.  For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while CFA-sharing hides such a cost entirely.  The reuse-vs-fresh distinction is only relevant in the currrent \emph{append} tests.
-
-The \emph{append} tests use the varying-from-1 corpus construction; that is they do not assume away the STL's advantage from small-string opitimization.
-
-To discuss: any other case variables intruduced in the performance intro
+These benchmark drivers have an outer loop for ``until a sample-worthy amount of execution has happened'' and an inner loop for ``build up the desired-length string.''  It is sensible to doubt that a user should have to care about this difference, yet the STL performs differently in these cases.  Concretely, both cases incur the cost of copying characters into the target string, but only the allocation-fresh case incurs a further reallocation cost, which is generally paid at points of doubling the length.  For the STL, this cost includes obtaining a fresh buffer from the memory allocator and copying older characters into the new buffer, while \CFA-sharing hides such a cost entirely.  The reuse-vs-fresh distinction is only relevant in the current \emph{append} tests.
+
+The \emph{append} tests use the varying-from-1 corpus construction; that is they do not assume away the STL's advantage from small-string optimization.
+
+To discuss: any other case variables introduced in the performance intro
 
 \begin{figure}
@@ -162 +342 @@
 \end{figure}
 
-Figure \ref{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode.  \CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case.  This penatly characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state.  The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings.
+Figure \ref{fig:string-graph-peq-cppemu} shows this behaviour, by the STL and by \CFA in STL emulation mode.  \CFA reproduces STL's performance, up to a 15\% penalty averaged over the cases shown, diminishing with larger strings, and 50\% in the worst case.  This penalty characterizes the amount of implementation fine tuning done with STL and not done with \CFA in present state.  The larger inherent penalty, for a user mismanaging reuse, is 40\% averaged over the cases shown, is minimally 24\%, shows up consistently between the STL and \CFA implementations, and increases with larger strings.
 
 \begin{figure}
@@ -170 +350 @@
 \end{figure}
 
-In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in Figure \ref{fig:string-graph-peq-sharing}.  At append lengths 5 and above, CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode.
+In sharing mode, \CFA makes the fresh/reuse difference disappear, as shown in Figure \ref{fig:string-graph-peq-sharing}.  At append lengths 5 and above, \CFA not only splits the two baseline STL cases, but its slowdown of 16\% over (STL with user-managed reuse) is close to the \CFA-v-STL implementation difference seen with \CFA in STL-emulation mode.
 
 \begin{figure}
@@ -178 +358 @@
 \end{figure}
 
-When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in Figure \ref{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while CFA's (with sharing) is under $2 \times$, averaged across the cases shown here.  Moreover, the STL's gap increases with string size, while \CFA's converges.
+When the user takes a further step beyond the STL's optimal zone, by running @x = x + y@, as in Figure \ref{fig:string-graph-pta-sharing}, the STL's penalty is above $15 \times$ while \CFA's (with sharing) is under $2 \times$, averaged across the cases shown here.  Moreover, the STL's gap increases with string size, while \CFA's converges.
 
 \subsubsection{Test: Pass argument}
@@ -184 +364 @@
 To have introduced:  STL string library forces users to think about memory management when communicating values across a function call
 
-STL charges a prohibitive penalty for passing a string by value.  With implicit sharing active, \CFA treats this operation as normal and supported.  This test illustrates a main adjantage of the \CFA sharing algorithm.  It also has a case in which STL's small-string optimization provides a successful mitigation.
+STL charges a prohibitive penalty for passing a string by value.  With implicit sharing active, \CFA treats this operation as normal and supported.  This test illustrates a main advantage of the \CFA sharing algorithm.  It also has a case in which STL's small-string optimization provides a successful mitigation.
 
 \begin{figure}
@@ -201 +381 @@
 This test directly compares the allocation schemes of the \CFA string with sharing, compared with the STL string.  It treats the \CFA scheme as a form of garbage collection, and the STL scheme as an application of malloc-free.  The test shows that \CFA enables faster speed at a cost in memory usage.
 
-A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an ammortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects.  (In the case of the mini-allocator powering the \CFA string library, objects are runs of text.)  Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light.  A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure.
+A garbage collector, afforded the freedom of managed memory, often runs faster than malloc-free (in an amortized analysis, even though it must occasionally stop to collect) because it is able to use its collection time to move objects.  (In the case of the mini-allocator powering the \CFA string library, objects are runs of text.)  Moving objects lets fresh allocations consume from a large contiguous store of available memory; the ``bump pointer'' book-keeping for such a scheme is very light.  A malloc-free implementation without the freedom to move objects must, in the general case, allocate in the spaces between existing objects; doing so entails the heavier book-keeping to navigate and maintain a linked structure.
 
 A garbage collector keeps allocations around for longer than the using program can reach them.  By contrast, a program using malloc-free (correctly) releases allocations exactly when they are no longer reachable.  Therefore, the same harness will use more memory while running under garbage collection.  A garbage collector can minimize the memory overhead by searching for these dead allocations aggressively, that is, by collecting more often.  Tuned in this way, it spends a lot of time collecting, easily so much as to overwhelm its speed advantage from bump-pointer allocation.  If it is tuned to collect rarely, then it leaves a lot of garbage allocated (waiting to be collected) but gains the advantage of little time spent doing collection.
@@ -215 +395 @@
 \begin{figure}
     \includegraphics[width=\textwidth]{string-graph-allocn.png}
-    \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (emph{Fixed-size} corpus construction.  [MISSING] The identified clusters are for the default fraction-live target, which is 30\%.  MISSING: STL results, typically just below the 0.5--0.9 CFA segment.  All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.}
+    \caption{Space and time performance, under varying fraction-live targets, for the five string lengths shown, at (\emph{Fixed-size} corpus construction.  [MISSING] The identified clusters are for the default fraction-live target, which is 30\%.  MISSING: STL results, typically just below the 0.5--0.9 \CFA segment.  All runs keep an average of 836 strings live, and the median string lifetime is ?? allocations.}
     \label{fig:string-graph-allocn}
 \end{figure}
 
-Figure \ref{fig:string-graph-allocn} shows the results of this experiemnt.  At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL.  At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint.
+Figure \ref{fig:string-graph-allocn} shows the results of this experiment.  At all string sizes, varying the liveness threshold gives offers speed-for-space tradeoffs relative to STL.  At the default liveness threshold, all measured string sizes see a ??\%--??\% speedup for a ??\%--??\% increase in memory footprint.
 
 
@@ -225 +405 @@
 \subsubsection{Test: Normalize}
 
-This test is more applied than the earlier ones.  It combines the effects of several operations.  It also demonstrates a case of the CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity.
+This test is more applied than the earlier ones.  It combines the effects of several operations.  It also demonstrates a case of the \CFA API allowing user code to perform well, while being written without overt memory management, while achieving similar performance in STL requires adding memory-management complexity.
 
 To motivate: edits being rare

doc/theses/mike_brooks_MMath/uw-ethesis.bib

@@ -124 +124 @@
 }
 
-
 @misc{Mendio24,
     contributer = {pabuhr@plg},
@@ -132 +131 @@
     howpublished= {\url{https://www.mend.io/most-secure-programming-languages}},
 }
+
+@misc{RVO20,
+    contributer = {pabuhr@plg},
+    title       = {Return value optimization ({RVO})},
+    author      = {Special Interest Group on {C++}},
+    year        = 2020,
+    month       = jun,
+    howpublished= {\url{https://sigcpp.github.io/2020/06/08/return-value-optimization}},
+}

doc/theses/mike_brooks_MMath/uw-ethesis.tex

@@ -102 +102 @@
 \input{common}
 %\usepackage{common}
+
 \CFAStyle                                               % CFA code-style
 \lstset{language=cfa,belowskip=-1pt} % set default language to CFA
@@ -108 +109 @@
 \lstnewenvironment{java}[1][]{\lstset{language=java,escapechar=\$,moredelim=**[is][\color{red}]{@}{@},}\lstset{#1}}{}
 \lstset{inputpath={programs}}
+\lstset{xleftmargin=1\parindentlnth}
 
 \newcommand{\uCpp}{$\mu$\CC}