Changeset e1107ec for doc/theses/mike_brooks_MMath

Timestamp:

Nov 7, 2024, 10:11:31 AM (6 weeks ago)

Author:

Peter A. Buhr <pabuhr@…>

Branches:

master

Children:

04c6340

Parents:

174a11a

Message:

proofread section Array lifecycle

File:

• doc/theses/mike_brooks_MMath/array.tex (modified) (3 diffs)

doc/theses/mike_brooks_MMath/array.tex

@@ -1091 +1091 @@
 
 
-
 \section{Array lifecycle}
 
-An array is an aggregate, like a struct.
-Both wrap subordinate objects.
-An arbitrary other type, like @string@, can be used as a struct member or an array element.
-When it is, that type's lifecycle assumptions must be respected.
-In the case of @string@, it would be disasterous to start calling string-management functions on uninitialized storage.
-The @string@ type provides its constructors and destructor;
-\CFA is supposed to provide a reasonable assurance that they will be called, even if the string is wrapped in something else, even if the user-programmer isn't thinking about it.
-
-Preexisting \CFA mechanisms achieve this requirement in correctness, but not with reasonable performance.
-Furthermore, advanced users of arrays need an exception to the bluntly-stated requirement, which does not come up when working with other aggregates.
-So the \CFA array has subtleties in its support for element lifecycle.
-
-The preexisting \CFA support for contained-element lifecycle is based on a recursive implementation of the object-type (otype) pseudo-trait.
-A type is an otype if it provides a parameterless constructor, copy constructor, assignment operator and destructor.
-When declaring a struct whose members are all otypes, the compiler generates implementations of the four otype functions for the outer struct.
-The generated parameterless constructor for the outer struct calls the parameterless constructor for each memeber, and the other otype functions work similarly.
-For a member that is a C array, these calls occur in loops, which work correctly for dynamic bounds.
-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 variable asserted to be an otype (which is implicit in the default syntax, @forall(T)@).
+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.
+For example, 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 these lifetime operations are called, regardless of the lexical nesting depth of containers and their components.
+
+Preexisting \CFA mechanisms achieve this requirement, but with poor performance (discussed shortly).
+Furthermore, advanced array users need an exception to the basic mechanism, which does not occur with other aggregates.
+Hence, there are subtleties in supporting an element's lifecycle with arrays.
+
+The preexisting \CFA support for contained-element lifecycle is based on a recursive implementation of the object-type (@otype@) pseudo-trait.
+A type is an @otype@, if it provides a parameterless (default) 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 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 * )   // non-otype element, no lifecycle functions
 // forall( T )  // otype element, lifecycle functions asserted
 struct array5 {
@@ -1120 +1119 @@
 };
 \end{cfa}
-Being a struct 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.
-A cube of @float@ is, in the running simplification:
+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}
-Its lifecycle functions, under the otype-recursion pattern, would be:
-\begin{cfa}
-TODO: rework this crude exposition into a readable figure
-
+its lifecycle functions, under the @otype@-recursion pattern, is shown in \VRef[Figure]{}, where
+\begin{cfa}
+array5(array5(array5(float)))
+\end{cfa}
+has 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 parameterless ctor
+1 default ctor
 2 copy ctor
 3 asgt
 4 dtor
 
-array5(T) offers
-1 parameterless ctor, which asks for T to have
-        1 parameterless ctor
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+\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, which asks for T to have
-        1 parameterless ctor
+2 copy ctor, using float's
+        1 default ctor
         2 copy ctor
         3 asgt
         4 dtor
-3 asgt, which asks for T to have
-        1 parameterless ctor
+3 asgt, using float's
+        1 default ctor
         2 copy ctor
         3 asgt
         4 dtor
-4 dtor, which asks for T to have
-        1 parameterless ctor
+4 dtor, using float's
+        1 default ctor
         2 copy ctor
         3 asgt
         4 dtor
 
-array5(float) has
-1 parameterless ctor, which gets float's
-        1 parameterless ctor
-        2 copy ctor
-        3 asgt
-        4 dtor
-2 copy ctor, which gets float's
-        1 parameterless ctor
-        2 copy ctor
-        3 asgt
-        4 dtor
-3 asgt, which gets float's
-        1 parameterless ctor
-        2 copy ctor
-        3 asgt
-        4 dtor
-4 dtor, which gets float's
-        1 parameterless ctor
-        2 copy ctor
-        3 asgt
-        4 dtor
-
+
+
+
+
+
+
+
+\end{cfa}
+&
+\begin{cfa}[deletekeywords={default}]
 array5(array5(float)) has
-1 parameterless ctor, which gets array5(float)'s
-        1 parameterless ctor, which gets float's
-                1 parameterless ctor
+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, which gets float's
-                1 parameterless ctor
+        2 copy ctor, using float's
+                1 default ctor
                 2 copy ctor
                 3 asgt
                 4 dtor
-        3 asgt, which gets float's
-                1 parameterless ctor
+        3 asgt, using float's
+                1 default ctor
                 2 copy ctor
                 3 asgt
                 4 dtor
-        4 dtor, which gets float's
-                1 parameterless ctor
+        4 dtor, using float's
+                1 default ctor
                 2 copy ctor
                 3 asgt
                 4 dtor
-2 copy ctor, which gets array5(float)'s
+2 copy ctor, using array5(float)'s
         ... 4 children, 16 leaves
-3 asgt, which gets array5(float)'s
+3 asgt, using array5(float)'s
         ... 4 children, 16 leaves
-4 dtor, which gets array5(float)'s
+4 dtor, using array5(float)'s
         ... 4 children, 16 leaves
 (64 leaves)
-
-array5(array5(array5(float))) has
-...(256 leaves)
-\end{cfa}
+\end{cfa}
+\end{tabular}
+\caption{write a caption}
+\end{figure}
 
 Each xxx corresponds to a generated thunk.
-So the otype-recursion pattern generates a quantity of thunks that is exponential in the number of dimensions.
-Anecdotal experience with this solutuion found the resulting compile times annoying at three dimensions, and unusable at four.
-
-But the otype-recursion pattern uses more assertions than are really needed.
-Consider how @array5(float)@'s parameterless constructor is getting all four lifecycle assertions about the element type, @float@.
-It only needs @float@'s parameterless constructor; it is getting a destructor (among others) and never using it.
-The same idea applies to the copy constructor and the destructor.
-For the assignment operator, it turns out that today's RAII pattern has it using a copy constructor, assignment operator and destructor.
-Concurrent work on the \CFA team aims to improve this whole situation.
-A workaround is needed for now.
-
-The workaround is to provide parameterless constructor, copy constructor and destructor, defined with lean, bespoke assertions:
-
-\noindent
+So the @otype@-recursion pattern generates a quantity of thunks that is 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;
+all the operations are never used.
+%For the assignment operator, it turns out that today's RAII pattern has it using a copy constructor, assignment operator and destructor.
+Current 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}
@@ -1263 +1304 @@
 \end{cfa}
 \end{tabular}
+\end{cquote}
 Moreover, the assignment operator is skipped, because array assignment is not a common operation.
 This way, the critical lifecycle functions are available, with no growth in thunk creation.
 
-Finally, the intuition that a programmer using an array always wants element constructors called \emph{automatically} is simplistic.
+Finally, the intuition that a programmer using an array always wants element's default constructor called \emph{automatically} is simplistic.
 Arrays exist to store different values at each position.
-So, an array initialization, in general, needs to let the prorammer provide different constructor arguments to each element.
-\begin{cfa}
-thread worker;
-void ?{}( worker & ) = void;
-void ?{}( worker &, int worker_num );
-array(worker, 5) ws @= ???@;
-for (i; 5) ( ws[i] ){ @i@ };
-\end{cfa}
+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 = {}; // no initialization
+for (i; 5) (ws[i]){ @i@ }; // explicitly initialize each thread's id
+\end{cfa}
+Note the ability to explicitly call a constructor in \CFA, unlike in \CC.
 
 Two \CFA features may, at first, seem viable for initializing the array @ws@, but on closer inspection, they are not.
 \begin{itemize}
 \item
-        Empty initializer / default constructor: \lstinline{array(worker, 5) ws;}.
-        This option does not work with the semantics of a thread: it has forked as soon as the constructor returns.
-        The type does not provide a parameterless constructor because it is not possible to fork the thread until the @worker_num@ parameter is received.
-\item
-        C initialization: \lstinline{array(worker, 5) ws AT EQUALS OPEN CLOSE;} (TODO: typeset at-equals).
+        Empty initializer / elided default constructor.
+        The problem is that a thread type needs to fork a thread at the \emph{end} of each constructor and join with a thread at the \emph{start} of each destructor.
+        Therefore, there is a conflict between the implicit actions by a builtin @thread@ type and a user's desire to remove actions with respect to allocation/deallocation.
+\item
+        C initialization: \lstinline|array(worker, 5) ws @= {};|, which ignores all \CFA initialization and uses C empty initialization.
         This option does achieve the desired semantics on the construction side.
-        But destruction side, the desired semantics is for implicit destructor calls to continue, because with threads, the destructor is a join operation.
-        C initialization disables \emph{all} implicit lifecycle management; here, the goal is to disable only the implicit construction.
+        But on destruction side, the desired semantics is for implicit destructor calls to continue for the join operation.
+        C initialization disables \emph{all} implicit lifecycle management; whereas, the goal is to disable only the implicit construction.
 \end{itemize}
 
-So, 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@ };
+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, there with the class-tempate @uNoCtor@ replacing \CFA's @uninit@.
-More recently, \uCpp got a declaration-helping macro, @uArray@, whose usage similar to the @ws2@ case.
-Based on results of piloting @uArray@ (as a replacement of @uNoCtor@), future work may choose to remove one of the options.
+Originally \uCpp offered only the @ws1@ form, using the class-template @uNoCtor@ equivalent to \CFA's @uninit@.
+More recently, \uCpp was extended with 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