Changes in / [c699602:49510db]

Files:

• doc/bibliography/pl.bib (modified) (2 diffs)
• doc/papers/llheap/Paper.tex (modified) (19 diffs)
• doc/theses/fangren_yu_MMath/.gitignore (modified) (1 diff)
• doc/theses/fangren_yu_MMath/content1.tex (modified) (27 diffs)
• doc/theses/fangren_yu_MMath/intro.tex (modified) (28 diffs)
• tools/cforall.el (deleted)

doc/bibliography/pl.bib

@@ -1 @@
-
 % Conventions: uncross-referenced entries appear first, then
 %    cross-referenced entries.  In both groups, entries are sorted by their
@@ -3931 +3930 @@
 
 @article{Boehm88,
-    keywords    = {conservative garbage collection, C},
+    keywords    = {conservative garbage collection, C, storage management, debugging},
     contributer = {gjditchfield@plg},
     author      = {Hans-Juergen Boehm and Mark Weiser},

doc/papers/llheap/Paper.tex

@@ -187 +187 @@
 \author[1]{Peter A. Buhr*}
 \author[2]{Bryan Chan}
+\author[3]{Dave Dice}
 \authormark{ZULFIQAR \textsc{et al.}}
 
 \address[1]{\orgdiv{Cheriton School of Computer Science}, \orgname{University of Waterloo}, \orgaddress{\state{Waterloo, ON}, \country{Canada}}}
 \address[2]{\orgdiv{Huawei Compiler Lab}, \orgname{Huawei}, \orgaddress{\state{Markham, ON}, \country{Canada}}}
+\address[3]{\orgdiv{Oracle Labs}, \orgname{Oracle}, \orgaddress{\state{Burlington, MA}, \country{USA}}}
+
 
 \corres{*Peter A. Buhr, Cheriton School of Computer Science, University of Waterloo, 200 University Avenue West, Waterloo, ON N2L 3G1, Canada. \email{pabuhr{\char`\@}uwaterloo.ca}}
@@ -201 +204 @@
 llheap extends the feature set of existing C allocation by remembering zero-filled (\lstinline{calloc}) and aligned properties (\lstinline{memalign}) in an allocation.
 These properties can be queried, allowing programmers to write safer programs by preserving these properties in future allocations.
-As well, \lstinline{realloc} preserves these properties when adjusting storage size, again increasing future allocation safety.
+As well, \lstinline{realloc}/\lstinline{reallocarray} preserve these properties when adjusting storage size, again increasing future allocation safety.
 llheap also extends the C allocation API with \lstinline{aalloc}, \lstinline{amemalign}, \lstinline{cmemalign}, \lstinline{resize}, and extended \lstinline{realloc}, providing orthogonal access to allocation features;
 hence, programmers do have to code missing combinations.
@@ -226 +229 @@
 \section{Introduction}
 
-Memory management services a series of program allocation/deallocation requests and attempts to satisfy them from a variable-sized block of memory, while minimizing total memory usage.
-A general-purpose dynamic-allocation algorithm cannot anticipate allocation requests so its time and space performance is rarely optimal.
-However, allocators take advantage of regular allocation patterns in typical programs to produce excellent results, both in time and space (similar to LRU paging).
-Allocators use a number of similar techniques, but each optimizes specific allocation patterns.
-Nevertheless, allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific program-request patterns.
+Memory management services a series of program allocation/deallocation requests and attempts to satisfy them from a variable-sized block(s) of memory, while minimizing total memory usage.
+A general-purpose dynamic-allocation algorithm cannot anticipate allocation requests so its time and space performance is rarely optimal (bin packing).
+However, allocators take advantage of allocation patterns in typical programs (heuristics) to produce excellent results, both in time and space (similar to LRU paging).
+Allocators use similar techniques, but each optimizes specific allocation patterns.
+Nevertheless, allocators are a series of compromises, occasionally with some static or dynamic tuning parameters to optimize specific request patterns.
 
 
@@ -283 +286 @@
 \begin{enumerate}[leftmargin=*,itemsep=0pt]
 \item
-Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions for the concurrent languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading).
+Implementation of a new stand-alone concurrent low-latency memory-allocator ($\approx$1,400 lines of code) for C/\CC programs using kernel threads (1:1 threading), and specialized versions for the concurrent languages \uC~\cite{uC++} and \CFA~\cite{Moss18,Delisle21} using user-level threads running on multiple kernel threads (M:N threading).
 
 \item
@@ -289 +292 @@
 
 \item
-Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ to zero-fill and align when storage is extended or copied.
+Use the preserved zero fill and alignment as \emph{sticky} properties for @realloc@ and @reallocarray@ to zero-fill and align when storage is extended or copied.
 Without this extension, it is unsafe to @realloc@ storage these allocations if the properties are not preserved when copying.
 This silent problem is unintuitive to programmers and difficult to locate because it is transient.
@@ -295 +298 @@
 \item
 Provide additional heap operations to make allocation properties orthogonally accessible.
-\begin{itemize}[topsep=2pt,itemsep=2pt,parsep=0pt]
-\item
-@aalloc( dim, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled.
-\item
-@amemalign( alignment, dim, elemSize )@ same as @aalloc@ with memory alignment.
-\item
-@cmemalign( alignment, dim, elemSize )@ same as @calloc@ with memory alignment.
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
+\item
+@aalloc( dimension, elemSize )@ same as @calloc@ except memory is \emph{not} zero filled, which is significantly faster than @calloc@.
+\item
+@amemalign( alignment, dimension, elemSize )@ same as @aalloc@ with memory alignment.
+\item
+@cmemalign( alignment, dimension, elemSize )@ same as @calloc@ with memory alignment.
 \item
 @resize( oaddr, size )@ re-purpose an old allocation for a new type \emph{without} preserving fill or alignment.
 \item
-@resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
-\item
-@realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
+@aligned_resize( oaddr, alignment, size )@ re-purpose an old allocation with new alignment but \emph{without} preserving fill.
+\item
+@aligned_realloc( oaddr, alignment, size )@ same as @realloc@ but adding or changing alignment.
+\item
+@aligned_reallocarray( oaddr, alignment, dimension, elemSize )@ same as @reallocarray@ but adding or changing alignment.
 \end{itemize}
 
 \item
 Provide additional query operations to access information about an allocation:
-\begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
 \item
 @malloc_alignment( addr )@ returns the alignment of the allocation.
 If the allocation is not aligned or @addr@ is @NULL@, the minimal alignment is returned.
 \item
-@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory is allocated with zero fill, e.g., by @calloc@/@cmemalign@.
+@malloc_zero_fill( addr )@ returns a boolean result indicating if the memory is allocated with zero fill, \eg by @calloc@/@cmemalign@.
 \item
 @malloc_size( addr )@ returns the size of the memory allocation.
 \item
-@malloc_usable_size( addr )@ returns the usable (total) size of the memory, i.e., the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
+@malloc_usable_size( addr )@ returns the usable (total) size of the memory, \ie the bin size containing the allocation, where @malloc_size( addr )@ $\le$ @malloc_usable_size( addr )@.
 \end{itemize}
 
 \item
 Provide optional extensive, fast, and contention-free allocation statistics to understand allocation behaviour, accessed by:
-\begin{itemize}[topsep=3pt,itemsep=2pt,parsep=0pt]
+\begin{itemize}[topsep=0pt,itemsep=0pt,parsep=0pt]
 \item
 @malloc_stats()@ print memory-allocation statistics on the file-descriptor set by @malloc_stats_fd@ (default @stderr@).
@@ -359 +364 @@
 The management goals are to make allocation/deallocation operations as fast as possible while densely packing objects to make efficient use of memory.
 Since objects in C/\CC cannot be moved to aid the packing process, only adjacent free storage can be \newterm{coalesced} into larger free areas.
-The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage via operating-system calls, such as @mmap@ or @sbrk@ in UNIX.
+The allocator grows or shrinks the dynamic-allocation zone to obtain storage for objects and reduce memory usage via OS calls, such as @mmap@ or @sbrk@ in UNIX.
 
 
@@ -984 +989 @@
 That is, rather than requesting new storage for a single object, an entire buffer is requested from which multiple objects are allocated later.
 Any heap may use an allocation buffer, resulting in allocation from the buffer before requesting objects (containers) from the global heap or OS, respectively.
-The allocation buffer reduces contention and the number of global/operating-system calls.
+The allocation buffer reduces contention and the number of global/OS calls.
 For coalescing, a buffer is split into smaller objects by allocations, and recomposed into larger buffer areas during deallocations.
 
@@ -1021 +1026 @@
 
 
-\section{Allocator}
-\label{c:Allocator}
-
-This section presents a new stand-alone concurrent low-latency memory-allocator ($\approx$1,200 lines of code), called llheap (low-latency heap), for C/\CC programs using kernel threads (1:1 threading), and specialized versions of the allocator for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
-The new allocator fulfills the GNU C Library allocator API~\cite{GNUallocAPI}.
-
-
-\subsection{llheap}
-
-The primary design objective for llheap is low-latency across all allocator calls independent of application access-patterns and/or number of threads, \ie very seldom does the allocator have a delay during an allocator call.
+\section{llheap}
+
+This section presents our new stand-alone, concurrent, low-latency memory-allocator, called llheap (low-latency heap), fulfilling the GNU C Library allocator API~\cite{GNUallocAPI} for C/\CC programs using kernel threads (1:1 threading), with specialized versions for the programming languages \uC and \CFA using user-level threads running over multiple kernel threads (M:N threading).
+The primary design objective for llheap is low-latency across all allocator calls independent of application access-patterns and/or number of threads, \ie very seldom does the allocator delay during an allocator call.
 Excluded from the low-latency objective are (large) allocations requiring initialization, \eg zero fill, and/or data copying, which are outside the allocator's purview.
 A direct consequence of this objective is very simple or no storage coalescing;
 hence, llheap's design is willing to use more storage to lower latency.
-This objective is apropos because systems research and industrial applications are striving for low latency and computers have huge amounts of RAM memory.
+This objective is apropos because systems research and industrial applications are striving for low latency and modern computers have huge amounts of RAM memory.
 Finally, llheap's performance should be comparable with the current best allocators, both in space and time (see performance comparison in Section~\ref{c:Performance}).
 
-% The objective of llheap's new design was to fulfill following requirements:
-% \begin{itemize}
-% \item It should be concurrent and thread-safe for multi-threaded programs.
-% \item It should avoid global locks, on resources shared across all threads, as much as possible.
-% \item It's performance (FIX ME: cite performance benchmarks) should be comparable to the commonly used allocators (FIX ME: cite common allocators).
-% \item It should be a lightweight memory allocator.
-% \end{itemize}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
 \subsection{Design Choices}
 
-% Some of the rejected designs are discussed because they show the path to the final design (see discussion in Section~\ref{s:MultipleHeaps}).
-% Note, a few simple tests for a design choice were compared with the current best allocators to determine the viability of a design.
-
-
-% \paragraph{T:1 model}
-% Figure~\ref{f:T1SharedBuckets} shows one heap accessed by multiple kernel threads (KTs) using a bucket array, where smaller bucket sizes are shared among N KTs.
-% This design leverages the fact that usually the allocation requests are less than 1024 bytes and there are only a few different request sizes.
-% When KTs $\le$ N, the common bucket sizes are uncontented;
-% when KTs $>$ N, the free buckets are contented and latency increases significantly.
-% In all cases, a KT must acquire/release a lock, contented or uncontented, along the fast allocation path because a bucket is shared.
-% Therefore, while threads are contending for a small number of buckets sizes, the buckets are distributed among them to reduce contention, which lowers latency;
-% however, picking N is workload specific.
-% 
-% \begin{figure}
-% \centering
-% \input{AllocDS1}
-% \caption{T:1 with Shared Buckets}
-% \label{f:T1SharedBuckets}
-% \end{figure}
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a KT is created/destroyed to assign/unassign a shared bucket-number from the memory allocator.
-% \item
-% When no thread is assigned a bucket number, its free storage is unavailable.
-% \item
-% All KTs contend for the global-pool lock for initial allocations, before free-lists get populated.
-% \end{itemize}
-% Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
-
-% \paragraph{T:H model}
-% Figure~\ref{f:THSharedHeaps} shows a fixed number of heaps (N), each a local free pool, where the heaps are sharded (distributed) across the KTs.
-% A KT can point directly to its assigned heap or indirectly through the corresponding heap bucket.
-% When KT $\le$ N, the heaps might be uncontented;
-% when KTs $>$ N, the heaps are contented.
-% In all cases, a KT must acquire/release a lock, contented or uncontented along the fast allocation path because a heap is shared.
-% By increasing N, this approach reduces contention but increases storage (time versus space);
-% however, picking N is workload specific.
-% 
-% \begin{figure}
-% \centering
-% \input{AllocDS2}
-% \caption{T:H with Shared Heaps}
-% \label{f:THSharedHeaps}
-% \end{figure}
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a KT is created/destroyed to assign/unassign a heap from the memory allocator.
-% \item
-% When no thread is assigned to a heap, its free storage is unavailable.
-% \item
-% Ownership issues arise (see Section~\ref{s:Ownership}).
-% \item
-% All KTs contend for the local/global-pool lock for initial allocations, before free-lists get populated.
-% \end{itemize}
-% Tests showed having locks along the allocation fast-path produced a significant increase in allocation costs and any contention among KTs produces a significant spike in latency.
-
-% \paragraph{T:H model, H = number of CPUs}
-% This design is the T:H model but H is set to the number of CPUs on the computer or the number restricted to an application, \eg via @taskset@.
-% (See Figure~\ref{f:THSharedHeaps} but with a heap bucket per CPU.)
-% Hence, each CPU logically has its own private heap and local pool.
-% A memory operation is serviced from the heap associated with the CPU executing the operation.
-% This approach removes fastpath locking and contention, regardless of the number of KTs mapped across the CPUs, because only one KT is running on each CPU at a time (modulo operations on the global pool and ownership).
-% This approach is essentially an M:N approach where M is the number if KTs and N is the number of CPUs.
-% 
-% Problems:
-% \begin{itemize}
-% \item
-% Need to know when a CPU is added/removed from the @taskset@.
-% \item
-% Need a fast way to determine the CPU a KT is executing on to access the appropriate heap.
-% \item
-% Need to prevent preemption during a dynamic memory operation because of the \newterm{serially-reusable problem}.
-% \begin{quote}
-% A sequence of code that is guaranteed to run to completion before being invoked to accept another input is called serially-reusable code.~\cite{SeriallyReusable}\label{p:SeriallyReusable}
-% \end{quote}
-% If a KT is preempted during an allocation operation, the OS can schedule another KT on the same CPU, which can begin an allocation operation before the previous operation associated with this CPU has completed, invalidating heap correctness.
-% Note, the serially-reusable problem can occur in sequential programs with preemption, if the signal handler calls the preempted function, unless the function is serially reusable.
-% Essentially, the serially-reusable problem is a race condition on an unprotected critical subsection, where the OS is providing the second thread via the signal handler.
-% 
-% Library @librseq@~\cite{librseq} was used to perform a fast determination of the CPU and to ensure all memory operations complete on one CPU using @librseq@'s restartable sequences, which restart the critical subsection after undoing its writes, if the critical subsection is preempted.
-% \end{itemize}
-% Tests showed that @librseq@ can determine the particular CPU quickly but setting up the restartable critical-subsection along the allocation fast-path produced a significant increase in allocation costs.
-% Also, the number of undoable writes in @librseq@ is limited and restartable sequences cannot deal with user-level thread (UT) migration across KTs.
-% For example, UT$_1$ is executing a memory operation by KT$_1$ on CPU$_1$ and a time-slice preemption occurs.
-% The signal handler context switches UT$_1$ onto the user-level ready-queue and starts running UT$_2$ on KT$_1$, which immediately calls a memory operation.
-% Since KT$_1$ is still executing on CPU$_1$, @librseq@ takes no action because it assumes KT$_1$ is still executing the same critical subsection.
-% Then UT$_1$ is scheduled onto KT$_2$ by the user-level scheduler, and its memory operation continues in parallel with UT$_2$ using references into the heap associated with CPU$_1$, which corrupts CPU$_1$'s heap.
-% If @librseq@ had an @rseq_abort@ which:
-% \begin{enumerate}
-% \item
-% Marked the current restartable critical-subsection as cancelled so it restarts when attempting to commit.
-% \item
-% Do nothing if there is no current restartable critical subsection in progress.
-% \end{enumerate}
-% Then @rseq_abort@ could be called on the backside of a  user-level context-switching.
-% A feature similar to this idea might exist for hardware transactional-memory.
-% A significant effort was made to make this approach work but its complexity, lack of robustness, and performance costs resulted in its rejection.
-
-% \subsubsection{Allocation Fastpath}
-% \label{s:AllocationFastpath}
-
-llheap's design was reviewed and changed multiple times during its development, with the final choices are discussed here.
-(See~\cite{Zulfiqar22} for a discussion of alternate choices and reasons for rejecting them.)
-All designs were analyzed for the allocation/free \newterm{fastpath}, \ie when an allocation can immediately return free storage or returned storage is not coalesced.
-The heap model chosen is 1:1, which is the T:H model with T = H, where there is one thread-local heap for each KT.
+llheap's design was reviewed and changed multiple times during its development, with the final choices discussed here.
+All designs focused on the allocation/free \newterm{fastpath}, \ie the shortest code path for the most common operations, \eg when an allocation can immediately return free storage or returned storage is not coalesced.
+The model chosen is 1:1, so there is one thread-local heap for each KT.
 (See Figure~\ref{f:THSharedHeaps} but with a heap bucket per KT and no bucket or local-pool lock.)
 Hence, immediately after a KT starts, its heap is created and just before a KT terminates, its heap is (logically) deleted.
-Heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap, modulo operations on the global pool and ownership.
+Therefore, heaps are uncontended for a KTs memory operations as every KT has its own thread-local heap, modulo operations on the global pool and ownership.
 
 Problems:
@@ -1205 +1089 @@
 For the T:1 and T:H models, locking must exist along the allocation fastpath because the buckets or heaps might be shared by multiple threads, even when KTs $\le$ N.
 For the T:H=CPU and 1:1 models, locking is eliminated along the allocation fastpath.
-However, T:H=CPU has poor operating-system support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
+However, T:H=CPU has poor OS support to determine the CPU id (heap id) and prevent the serially-reusable problem for KTs.
 More OS support is required to make this model viable, but there is still the serially-reusable problem with user-level threading.
-So the 1:1 model had no atomic actions along the fastpath and no special operating-system support requirements.
+So the 1:1 model had no atomic actions along the fastpath and no special OS support requirements.
 The 1:1 model still has the serially-reusable problem with user-level threading, which is addressed in Section~\ref{s:UserlevelThreadingSupport}, and the greatest potential for heap blowup for certain allocation patterns.
 
@@ -1241 +1125 @@
 A primary goal of llheap is low latency, hence the name low-latency heap (llheap).
 Two forms of latency are internal and external.
-Internal latency is the time to perform an allocation, while external latency is time to obtain/return storage from/to the OS.
+Internal latency is the time to perform an allocation, while external latency is time to obtain or return storage from or to the OS.
 Ideally latency is $O(1)$ with a small constant.
 
-To obtain $O(1)$ internal latency means no searching on the allocation fastpath and largely prohibits coalescing, which leads to external fragmentation.
-The mitigating factor is that most programs have well behaved allocation patterns, where the majority of allocation operations can be $O(1)$, and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
-
-To obtain $O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
-Excluding real-time operating-systems, operating-system operations are unbounded, and hence some external latency is unavoidable.
-The mitigating factor is that operating-system calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
-Furthermore, while operating-system calls are unbounded, many are now reasonably fast, so their latency is tolerable and infrequent.
+$O(1)$ internal latency means no open searching on the allocation fastpath, which largely prohibits coalescing.
+The mitigating factor is that most programs have a small, fixed, allocation pattern, where the majority of allocation operations can be $O(1)$ and heap blowup does not occur without coalescing (although the allocation footprint may be slightly larger).
+Modern computers have large memories so a slight increase in program footprint is not a problem.
+
+$O(1)$ external latency means obtaining one large storage area from the OS and subdividing it across all program allocations, which requires a good guess at the program storage high-watermark and potential large external fragmentation.
+Excluding real-time OSs, OS operations are unbounded, and hence some external latency is unavoidable.
+The mitigating factor is that OS calls can often be reduced if a programmer has a sense of the storage high-watermark and the allocator is capable of using this information (see @malloc_expansion@ \pageref{p:malloc_expansion}).
+Furthermore, while OS calls are unbounded, many are now reasonably fast, so their latency is tolerable because it occurs infrequently.
 
 
@@ -1392 +1277 @@
 \subsubsection{Alignment}
 
-Most dynamic memory allocations have a minimum storage alignment for the contained object(s).
-Often the minimum memory alignment, M, is the bus width (32 or 64-bit) or the largest register (double, long double) or largest atomic instruction (DCAS) or vector data (MMMX).
-In general, the minimum storage alignment is 8/16-byte boundary on 32/64-bit computers.
-For consistency, the object header is normally aligned at this same boundary.
-Larger alignments must be a power of 2, such as page alignment (4/8K).
-Any alignment request, N, $\le$ the minimum alignment is handled as a normal allocation with minimal alignment.
-
-For alignments greater than the minimum, the obvious approach for aligning to address @A@ is: compute the next address that is a multiple of @N@ after the current end of the heap, @E@, plus room for the header before @A@ and the size of the allocation after @A@, moving the end of the heap to @E'@.
-\begin{center}
-\input{Alignment1}
-\end{center}
-The storage between @E@ and @H@ is chained onto the appropriate free list for future allocations.
-The same approach is used for sufficiently large free blocks, where @E@ is the start of the free block, and any unused storage before @H@ or after the allocated object becomes free storage.
-In this approach, the aligned address @A@ is the same as the allocated storage address @P@, \ie @P@ $=$ @A@ for all allocation routines, which simplifies deallocation.
-However, if there are a large number of aligned requests, this approach leads to memory fragmentation from the small free areas around the aligned object.
-As well, it does not work for large allocations, where many memory allocators switch from program @sbrk@ to operating-system @mmap@.
-The reason is that @mmap@ only starts on a page boundary, and it is difficult to reuse the storage before the alignment boundary for other requests.
-Finally, this approach is incompatible with allocator designs that funnel allocation requests through @malloc@ as it directly manipulates management information within the allocator to optimize the space/time of a request.
-
-Instead, llheap alignment is accomplished by making a \emph{pessimistic} allocation request for sufficient storage to ensure that \emph{both} the alignment and size request are satisfied, \eg:
+Allocators have a different minimum storage alignment from the hardware's basic types.
+Often the minimum allocator alignment, $M$, is the bus width (32 or 64-bit), the largest register (double, long double), largest atomic instruction (DCAS), or vector data (MMMX).
+The reason for this larger requirement is the lack of knowledge about the data type occupying the allocation.
+Hence, an allocator assumes the worst-case scenario for the start of data and the compiler correctly aligns items within this data because it knows their types.
+Often the minimum storage alignment is an 8/16-byte boundary on a 32/64-bit computer.
+Alignments larger than $M$ are normally a power of 2, such as page alignment (4/8K).
+Any alignment less than $M$ is raised to the minimal alignment.
+
+llheap aligns its header at the $M$ boundary and its size is $M$;
+hence, data following the header is aligned at $M$.
+This pattern means there is no minimal alignment computation along the allocation fastpath, \ie new storage and reused storage is always correctly aligned.
+An alignment $N$ greater than $M$ is accomplished with a \emph{pessimistic} request for storage that ensures \emph{both} the alignment and size request are satisfied, \eg:
 \begin{center}
 \input{Alignment2}
 \end{center}
-The amount of storage necessary is @alignment - M + size@, which ensures there is an address, @A@, after the storage returned from @malloc@, @P@, that is a multiple of @alignment@ followed by sufficient storage for the data object.
-The approach is pessimistic because if @P@ already has the correct alignment @N@, the initial allocation has already requested sufficient space to move to the next multiple of @N@.
-For this special case, there is @alignment - M@ bytes of unused storage after the data object, which subsequently can be used by @realloc@.
-
-Note, the address returned is @A@, which is subsequently returned to @free@.
-However, to correctly free the allocated object, the value @P@ must be computable, since that is the value generated by @malloc@ and returned within @memalign@.
-Hence, there must be a mechanism to detect when @P@ $\neq$ @A@ and how to compute @P@ from @A@.
-
-The llheap approach uses two headers:
-the \emph{original} header associated with a memory allocation from @malloc@, and a \emph{fake} header within this storage before the alignment boundary @A@, which is returned from @memalign@, e.g.:
+The amount of storage necessary is $alignment - M + size$, which ensures there is an address, $A$, after the storage returned from @malloc@, $P$, that is a multiple of $alignment$ followed by sufficient storage for the data object.
+The approach is pessimistic if $P$ happens to have the correct alignment $N$, and the initial allocation has requested sufficient space to move to the next multiple of $N$.
+In this case, there is $alignment - M$ bytes of unused storage after the data object, which could be used by @realloc@.
+Note, the address returned by the allocation is $A$, which is subsequently returned to @free@.
+To correctly free the object, the value $P$ must be computable from $A$, since that is the actual start of the allocation, from which $H$ can be computed $P - M$.
+Hence, there must be a mechanism to detect when $P$ $\neq$ $A$ and then compute $P$ from $A$.
+
+To detect and perform this computation, llheap uses two headers:
+the \emph{original} header $H$ associated with the allocation, and a \emph{fake} header $F$ within this storage before the alignment boundary $A$, e.g.:
 \begin{center}
 \input{Alignment2Impl}
 \end{center}
-Since @malloc@ has a minimum alignment of @M@, @P@ $\neq$ @A@ only holds for alignments greater than @M@.
-When @P@ $\neq$ @A@, the minimum distance between @P@ and @A@ is @M@ bytes, due to the pessimistic storage-allocation.
-Therefore, there is always room for an @M@-byte fake header before @A@.
-
-The fake header must supply an indicator to distinguish it from a normal header and the location of address @P@ generated by @malloc@.
+Since every allocation is aligned at $M$, $P$ $\neq$ $A$ only holds for alignments greater than $M$.
+When $P$ $\neq$ $A$, the minimum distance between $P$ and $A$ is $M$ bytes, due to the pessimistic storage-allocation.
+Therefore, there is always room for an $M$-byte fake header before $A$.
+The fake header must supply an indicator to distinguish it from a normal header and the location of address $P$ generated by the allocation.
 This information is encoded as an offset from A to P and the initialize alignment (discussed in Section~\ref{s:ReallocStickyProperties}).
 To distinguish a fake header from a normal header, the least-significant bit of the alignment is used because the offset participates in multiple calculations, while the alignment is just remembered data.
@@ -1443 +1318 @@
 \label{s:ReallocStickyProperties}
 
-The allocation routine @realloc@ provides a memory-management pattern for shrinking/enlarging an existing allocation, while maintaining some or all of the object data, rather than performing the following steps manually.
+The allocation routine @realloc@ provides a memory-management pattern for shrinking/enlarging an existing allocation, while maintaining some or all of the object data.
+The realloc pattern is simpler than the suboptimal manually steps.
 \begin{flushleft}
 \begin{tabular}{ll}
@@ -1455 +1331 @@
 &
 \begin{lstlisting}
-T * naddr = (T *)malloc( newSize ); $\C[2.4in]{// new storage}$
+T * naddr = (T *)malloc( newSize ); $\C[2in]{// new storage}$
 memcpy( naddr, addr, oldSize );  $\C{// copy old bytes}$
 free( addr );                           $\C{// free old storage}$
@@ -1462 +1338 @@
 \end{tabular}
 \end{flushleft}
-The realloc pattern leverages available storage at the end of an allocation due to bucket sizes, possibly eliminating a new allocation and copying.
-This pattern is not used enough to reduce storage management costs.
-In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc@, so even the initial @malloc@ can be a @realloc@ for consistency in the allocation pattern.
-
-The hidden problem for this pattern is the effect of zero fill and alignment with respect to reallocation.
-Are these properties transient or persistent (``sticky'')?
-For example, when memory is initially allocated by @calloc@ or @memalign@ with zero fill or alignment properties, respectively, what happens when those allocations are given to @realloc@ to change size?
-That is, if @realloc@ logically extends storage into unused bucket space or allocates new storage to satisfy a size change, are initial allocation properties preserved?
-Currently, allocation properties are not preserved, so subsequent use of @realloc@ storage may cause inefficient execution or errors due to lack of zero fill or alignment.
-This silent problem is unintuitive to programmers and difficult to locate because it is transient.
-To prevent these problems, llheap preserves initial allocation properties for the lifetime of an allocation and the semantics of @realloc@ are augmented to preserve these properties, with additional query routines.
-This change makes the realloc pattern efficient and safe.
+The manual steps are suboptimal because there may be sufficient internal fragmentation at the end of the allocation due to bucket sizes.
+If this storage is large enough, it eliminates a new allocation and copying.
+Alternatively, if the storage is made smaller, there may be a reasonable crossover point, where just increasing the internal fragmentation eliminates a new allocation and copying.
+This pattern should be used more frequently to reduce storage management costs.
+In fact, if @oaddr@ is @nullptr@, @realloc@ does a @malloc( newSize)@, and if @newSize@ is 0, @realloc@ does a @free( oaddr )@, so all allocation/deallocation can be done with @realloc@.
+
+The hidden problem with this pattern is the effect of zero fill and alignment with respect to reallocation.
+For safety, we argue these properties should be persistent (``sticky'') and not transient.
+For example, when memory is initially allocated by @calloc@ or @memalign@ with zero fill or alignment properties, any subsequent reallocations of this storage must preserve these properties.
+Currently, allocation properties are not preserved nor is it possible to query an allocation to maintain these properties manually.
+Hence, subsequent use of @realloc@ storage that assumes any initially properties may cause errors.
+This silent problem is unintuitive to programmers, can cause catastrophic failure, and is difficult to debug because it is transient.
+To prevent these problems, llheap preserves initial allocation properties within an allocation, allowing them to be queried, and the semantics of @realloc@ preserve these properties on any storage change.
+As a result, the realloc pattern is efficient and safe.
 
 
 \subsubsection{Header}
 
-To preserve allocation properties requires storing additional information with an allocation,
-The best available option is the header, where Figure~\ref{f:llheapNormalHeader} shows the llheap storage layout.
-The header has two data field sized appropriately for 32/64-bit alignment requirements.
-The first field is a union of three values:
+To preserve allocation properties requires storing additional information about an allocation.
+Figure~\ref{f:llheapHeader} shows llheap captures this information in the header, which has two fields (left/right) sized appropriately for 32/64-bit alignment requirements.
+
+\begin{figure}
+\centering
+\input{Header}
+\caption{llheap Header}
+\label{f:llheapHeader}
+\end{figure}
+
+The left field is a union of three values:
 \begin{description}
 \item[bucket pointer]
-is for allocated storage and points back to the bucket associated with this storage requests (see Figure~\ref{f:llheapStructure} for the fields accessible in a bucket).
+is for deallocated of heap storage and points back to the bucket associated with this storage requests (see Figure~\ref{f:llheapStructure} for the fields accessible in a bucket).
 \item[mapped size]
-is for mapped storage and is the storage size for use in unmapping.
+is for deallocation of mapped storage and is the storage size for unmapping.
 \item[next free block]
-is for free storage and is an intrusive pointer chaining same-size free blocks onto a bucket's free stack.
+is for freed storage and is an intrusive pointer chaining same-size free blocks onto a bucket's stack of free objects.
 \end{description}
-The second field remembers the request size versus the allocation (bucket) size, \eg request 42 bytes which is rounded up to 64 bytes.
+The low-order 3-bits of this field are unused for any stored values as these values are at least 8-byte aligned.
+The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
+Note, the zero-filled/mapped bits are only used in the normal header and the alignment bit in the fake header.
+This implementation allows a fast test if any of the lower 3-bits are on (@&@ and compare).
+If no bits are on, it implies a basic allocation, which is handled quickly in the fastpath for allocation and free;
+otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
+
+The right field remembers the request size versus the allocation (bucket) size, \eg request of 42 bytes is rounded up to 64 bytes.
 Since programmers think in request sizes rather than allocation sizes, the request size allows better generation of statistics or errors and also helps in memory management.
 
-\begin{figure}
-\centering
-\input{Header}
-\caption{llheap Normal Header}
-\label{f:llheapNormalHeader}
-\end{figure}
-
-The low-order 3-bits of the first field are \emph{unused} for any stored values as these values are 16-byte aligned by default, whereas the second field may use all of its bits.
-The 3 unused bits are used to represent mapped allocation, zero filled, and alignment, respectively.
-Note, the alignment bit is not used in the normal header and the zero-filled/mapped bits are not used in the fake header.
-This implementation allows a fast test if any of the lower 3-bits are on (@&@ and compare).
-If no bits are on, it implies a basic allocation, which is handled quickly;
-otherwise, the bits are analysed and appropriate actions are taken for the complex cases.
-Since most allocations are basic, they will take significantly less time as the memory operations will be done along the allocation and free fastpath.
-
 
 \subsection{Statistics and Debugging}
 
-llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand allocation behaviour.
+llheap can be built to accumulate fast and largely contention-free allocation statistics to help understand dynamic-memory behaviour.
 Incrementing statistic counters must appear on the allocation fastpath.
 As noted, any atomic operation along the fastpath produces a significant increase in allocation costs.
@@ -1741 +1618 @@
 
 \medskip\noindent
-\lstinline{void * aalloc( size_t dim, size_t elemSize )}
+\lstinline{void * aalloc( size_t dimension, size_t elemSize )}
 extends @calloc@ for allocating a dynamic array of objects with total size @dim@ $\times$ @elemSize@ but \emph{without} zero-filling the memory.
 @aalloc@ is significantly faster than @calloc@, which is the only alternative given by the standard memory-allocation routines for array allocation.
@@ -1753 +1630 @@
 
 \medskip\noindent
-\lstinline{void * amemalign( size_t alignment, size_t dim, size_t elemSize )}
+\lstinline{void * amemalign( size_t alignment, size_t dimension, size_t elemSize )}
 extends @aalloc@ and @memalign@ for allocating a dynamic array of objects with the starting address on the @alignment@ boundary.
 Sets sticky alignment property.
@@ -1759 +1636 @@
 
 \medskip\noindent
-\lstinline{void * cmemalign( size_t alignment, size_t dim, size_t elemSize )}
+\lstinline{void * cmemalign( size_t alignment, size_t dimension, size_t elemSize )}
 extends @amemalign@ with zero fill and has the same usage as @amemalign@.
 Sets sticky zero-fill and alignment property.
@@ -1881 +1758 @@
 
 \medskip\noindent
-\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dim, ... )}
+\lstinline{T * alloc( ... )} or \lstinline{T * alloc( size_t dimension, ... )}
 is overloaded with a variable number of specific allocation operations, or an integer dimension parameter followed by a variable number of specific allocation operations.
 These allocation operations can be passed as named arguments when calling the \lstinline{alloc} routine.

doc/theses/fangren_yu_MMath/.gitignore

@@ -1 @@
-# Intermediate Results:
-build/
-
-# Final Files:
+# generated by latex
+build/*
 *.pdf
 *.ps
 
-# The Makefile here is not generated.
-!Makefile
+# generated by xfig
+*.bak

doc/theses/fangren_yu_MMath/content1.tex

@@ -2 +2 @@
 \label{c:content1}
 
-This chapter discusses \CFA feature introduced over time by multiple people and their interactions with the type system.
+This chapter discusses \CFA features introduced over time by multiple people and their interactions with the type system.
 
 
@@ -19 +19 @@
 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.
+here, references match with functional programming.
+However, the consequence is asymmetric semantics between pointer and reference.
 \CFA adopts a uniform policy between pointers and references where mutability is a separate property made at the declaration.
 
@@ -64 +64 @@
 The call applies an implicit dereference once to @x@ so the call is typed @f( int & )@ with @T = int@, rather than with @T = int &@.
 
-As for a pointer type, a reference type may have qualifiers, where @const@ is most interesting.
+As for a pointer type, a reference type may have qualifiers, where @const@ is most common.
 \begin{cfa}
 int x = 3; $\C{// mutable}$
@@ -113 +113 @@
 In the initial \CFA reference design, the goal was to make the reference type a \emph{real} data type \vs a restricted \CC reference, which is mostly used for choosing the argument-passing method, \ie by-value or by-reference.
 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.
+For example, in
+\begin{cfa}
+int & x;
+forall( T ) void foo( T );
+forall( T ) void bar( T & );
+foo( x ); $\C{// means pass by value}$
+bar( x ); $\C{// means pass by reference}$
+\end{cfa}
+the call to @foo@ must pass @x@ by value, implying auto-dereference, while the call to @bar@ must pass @x@ by reference, implying no auto-dereference.
 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, even if type variables could be bound to reference types.
@@ -150 +159 @@
 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 is forced to use a pointer type, giving up the benefits of auto-dereference operations and better syntax with reference types.
+Currently, there are contexts where the \CFA programmer is forced to use a pointer type, giving up the benefits of auto-dereference operations and better syntax with reference types.
 
 
@@ -162 +171 @@
 \begin{tabular}{@{}l@{\hspace{20pt}}l@{}}
 \begin{cfa}
-
-int foo( int &p2, int &p3 );  // in/out parameters
+int foo( int &p1, int &p2 );  // in/out parameters
 int x, y = 3, z = 4;
-x = foo( y, z );  // return 3 values
+x = foo( y, z );  // return 3 values: 1 out, 2 in/out
 \end{cfa}
 &
 \begin{cfa}
-struct Ret { int x, y, z; };
-Ret foo( int p2, int p3 );  // multiple return values
-Ret ret = { .y = 3, .z = 4 };
-ret = foo( ret.y, ret.z );  // return 3 values
+struct Ret { int x, y, z; } ret;
+Ret foo( int p1, int p2 );  // return structure
+ret = foo( 3, 4 );  // return 3 values: 3 out
 \end{cfa}
 \end{tabular}
 \end{cquote}
-K-W C allows direct return of multiple values into a tuple.
-\begin{cfa}
-@[int, int, int]@ foo( int p2, int p3 );
-@[x, y, z]@ = foo( y, z );  // return 3 values into a tuple
+Like Go, K-W C allows direct return of multiple values into a tuple.
+\begin{cfa}
+@[int, int, int]@ foo( int p1, int p2 );
+@[x, y, z]@ = foo( 3, 4 );  // return 3 values into a tuple
 \end{cfa}
 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.
@@ -205 +212 @@
 bar( @foo@( 3 ), @foo@( 3 ) );
 \end{cfa}
-The type resolver only has the tuple return types to resolve the call to @bar@ as the @foo@ parameters are identical, which involves unifying the flattened @foo@ return values with @bar@'s parameter list.
+The type resolver only has the tuple return types to resolve the call to @bar@ as the @foo@ parameters are identical.
+The resultion involves unifying the flattened @foo@ return values with @bar@'s parameter list.
 However, no combination of @foo@s is an exact match with @bar@'s parameters;
 thus, the resolver applies C conversions to obtain a best match.
 The resulting minimal cost expression is @bar( foo@$_1$@( 3 ), foo@$_2$@( 3 ) )@, where the two possible coversions are (@int@, {\color{red}@int@}, @double@) to (@int@, {\color{red}@double@}, @double@) with a safe (widening) conversion from @int@ to @double@ versus ({\color{red}@double@}, {\color{red}@int@}, {\color{red}@int@}) to ({\color{red}@int@}, {\color{red}@double@}, {\color{red}@double@}) with one unsafe (narrowing) conversion from @double@ to @int@ and two safe conversions from @int@ to @double@.
-The programming language Go provides a similar but simplier tuple mechanism, as it does not have overloaded functions.
+Go provides a simplified mechanism where only one tuple returning function call is allowed and there are no implicit type conversions.
+\begin{lstlisting}[language=Go]
+func foo( int ) ( int, int, int ) { return 3, 7, 8 }
+func bar( int, int, int ) { ... } // types must match
+bar( foo( 3 ) ) // only one tuple returning call 
+\end{lstlisting}
+Hence, programers cannot take advantage of the full power of tuples but type match is straightforward.
 
 K-W C also supported tuple variables, but with a strong distinction between tuples and tuple values/variables.
@@ -305 +319 @@
 \end{cfa}
 \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 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 individually 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 upside of the right implementation is consistence and no 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.
 
@@ -314 +328 @@
 \setlength{\tabcolsep}{20pt}
 \begin{tabular}{@{}ll@{}}
-Till K-W C implementation & Rodolfo \CFA implementation \\
+Till K-W C implementation & Esteves \CFA implementation \\
 \begin{cfa}
 struct _tuple2 { int _0; int _1; }
@@ -343 +357 @@
 
 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 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?}
+The reason for the reversion is a uniform approach for tuple values/variables making tuples first-class types in \CFA, \ie allow tuples with corresponding tuple variables.
+This reversion 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 for generic variables~\cite[\S~3.7]{Schluntz17}.
+For example, these two tuples:
+\begin{cfa}
+[double, double] x;
+[int, double, int] y;
+\end{cfa}
+are transformed internally into two generic structures:
+\begin{cfa}
+forall( T0 &, & T1 | sized( T0 ) | sized( T1 ) )
+struct _tuple2_ {
+        T0 field_0 ;   T1 field_1 ;
+};
+forall( T0 &, T1 &, T2 & | sized( T0 ) | sized( T1 ) | sized( T2 ) )
+struct _tuple3_ {
+        T0 field_0 ;   T1 field_1 ;   T2 field_2 ;
+};
+\end{cfa}
+and the declarations become instances of these generic structure types:
+\begin{cfa}
+_tuple2_( double, double ) x;
+_tuple3_( int, double, int ) y;
+\end{cfa}
+Now types @_tuple2_@ and @_tuple3_@ are available for any further 2 or 3 tuple-types in the translation unit, simplifying internal code transformations by memoizing a small set of tuple structures.
+Ultimately, these generic types are lowered to specific C structures during code generation.
+Scala, like \CC, provides tuple types through a library using this structural expansion, \eg Scala provides tuple sizes 1 through 22 via hand-coded generic data-structures.
 
 However, after experience gained building the \CFA runtime system, making tuple-types first-class seems to add little benefit.
@@ -361 +398 @@
 Furthermore, since operator overloading in \CFA is implemented by treating operators as overloadable functions, tuple types are very rarely used in a structured way.
 When a tuple-type expression appears in a function call (except assignment expressions, which are handled differently by mass- or multiple-assignment expansions), it is always flattened, and the tuple structure of function parameter is not considered a part of the function signatures.
-For example,
+For example, these two prototypes for @foo@:
 \begin{cfa}
 void f( int, int );
@@ -367 +404 @@
 f( 3, 4 );  // ambiguous call
 \end{cfa}
-the two prototypes for @foo@ have the same signature (a function taking two @int@s and returning nothing), and therefore invalid overloads.
+have the same signature (a function taking two @int@s and returning nothing), and therefore invalid overloads.
 Note, the ambiguity error occurs at the call rather than at the second declaration of @f@, because it is possible to have multiple equivalent prototype definitions of a function.
 Furthermore, ordinary polymorphic type-parameters are not allowed to have tuple types.
@@ -385 +422 @@
 Therefore, tuple types are never present in any fixed-argument function calls, because of the flattening.
 
+\begin{comment}
+Date: Mon, 13 Jan 2025 10:09:06 -0500
+Subject: Re: structure / tuple
+To: "Peter A. Buhr" <pabuhr@uwaterloo.ca>
+CC: Andrew Beach <ajbeach@uwaterloo.ca>,
+        Michael Brooks <mlbrooks@uwaterloo.ca>,
+        Fangren Yu <f37yu@uwaterloo.ca>, Jiada Liang <j82liang@uwaterloo.ca>,
+        Alvin Zhang <alvin.zhang@uwaterloo.ca>,
+        Kyoung Seo <lseo@plg.uwaterloo.ca>
+From: Gregor Richards <gregor.richards@uwaterloo.ca>
+
+Languages support tuples to abbreviate syntax where the meaning of several
+values is obvious from context, such as returns from functions, or where the
+effort of creating a dedicated type is not worth the reward of using that type
+in exactly one location. The positions always have meanings which could be
+given names, and are only not given names for brevity. Whether that brevity is
+a good idea or not is the programmer's problem to deal with. I don't think
+there's any pragmatic value to tuples beyond brevity. (From a theoretical
+perspective, having the empty tuple is useful for type-theoretical reasons, and
+tuples are usually easier to reason about than structures, but that only
+applies to theoretical reasoning, not to actual programming.)
+
+Your distinction unstructured tuples could just as well be made for structs as
+well, if you had named arguments (or named returns?).  Personally, I think that
+having these be a syntactic distinction is a mistake. Other languages return
+fully codified tuples, and if you immediately destructure them, even the most
+naive optimizer will manage to never create an actual tuple in memory. In my
+opinion, since tuples are for brevity, they should always be declared with your
+"unstructured" syntax, and it's up to the optimizer to realize when you've
+never stored them. But, you live closer to the metal in CFA than most
+languages, so perhaps communicating that intent is of sufficient value.
+
+The only value of tuples beyond that is to make it possible for annoying
+students to use std::pair in place of ever creating their own class hierarchy
+or naming things. Then again, I hear that that is one of the hard problems in
+computer science.
+
+With valediction,
+  - Gregor Richards
+
+On 1/13/25 09:11, Peter A. Buhr wrote:
+> The CFA team has been discussing the difference between a structure and
+> tuple.  Basically, a structure has named fields and a tuple has anonymous
+> fields. As a result, structure access uses field names and tuple access uses
+> position.
+>
+>    struct S { int i, j, k ; };
+>    S s;
+>    s.i; s.j; // field access
+>
+>    tuple T { int, int };
+>    T t;
+>    t.0; t.1; // position access, zero origin
+>    t[0]; t[1]; // alternate access
+>
+> Hence the difference is small.
+>
+> In CFA, we differentiate between unstructured and structured tuples. An
+> unstructured tuple is a lexical grouping of potentially disjoint variables.
+>
+>    [ int, int, int ] f();
+>    void g( int, int, int );
+>    x, y, z = f(); // Go unstructured tuple, flatten tuple
+>    g( foo() ); // flatten tuple
+>
+> Here, the tuple returned from f is flattened into disjoint variables.  A
+> structured tuple is like above and has contiguous memory.
+>
+> CFA has fancy unstructured stuff like
+>
+>    s.[i,k] += 1; // add 1 to each field
+>    t.[1,0] = 1; // don't think this works but could
+>
+> which is just an unstructured tuple access (sugar).
+>
+> What is your opinion of structures and tuples since the difference is
+> small. Why do many languages support both features? Are we missing some
+> important aspect of tuples that differentiates them from structures?  Is CFA
+> unique in having both unstructured and structured tuples?
+\end{comment}
+
 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.
+\begin{cfa}
+int printf( const char * format, ${\color{red}\LARGE ...}$ );  // variadic list of variables to print
+\end{cfa}
 \VRef[Figure]{f:CVariadicMaxFunction} shows an $N$ argument @maxd@ function using the C untyped @va_list@ interface.
 In the example, the first argument is the number of following arguments, and the following arguments are assumed to be @double@;
@@ -396 +517 @@
 \begin{cfa}
 double maxd( int @count@, @...@ ) { // ellipse parameter
-    double max = 0;
-    va_list args;
-    va_start( args, count );
-    for ( int i = 0; i < count; i += 1 ) {
-        double num = va_arg( args, double );
-        if ( num > max ) max = num;
-    }
-    va_end(args);
-    return max;
+        double max = 0;
+        va_list args;
+        va_start( args, count );
+        for ( int i = 0; i < count; i += 1 ) {
+                double num = va_arg( args, double );
+                if ( num > max ) max = num;
+        }
+        va_end(args);
+        return max;
 }
 printf( "%g\n", maxd( @4@, 25.0, 27.3, 26.9, 25.7 ) );
@@ -412 +533 @@
 \end{figure}
 
-There are two common patterns for using the variadic functions in \CFA.
+There are two common patterns for using variadic functions in \CFA.
 \begin{enumerate}[leftmargin=*]
 \item
@@ -430 +551 @@
 Structural recursion for processing the argument-pack values one at a time, \eg:
 \begin{cfa}
-forall( T | { int ?>?( T, T ); } )
-T max( T v1, T v2 ) { return v1 > v2 ? v1 : v2; }
+forall( T | { int ?<?( T, T ); } )
+T max( T v1, T v2 ) { return v1 < v2 ? v2 : v1; }
 $\vspace{-10pt}$
 forall( T, TT ... | { T max( T, T ); T max( TT ); } )
 T max( T arg, TT args ) { return max( arg, max( args ) ); }
 \end{cfa}
-The first non-recursive @max@ function is the polymorphic base-case for the recursion, \ie, find the maximum of two identically typed values with a greater-than (@>@) operator.
-The second recursive @max@ function takes two parameters, a @T@ and a @TT@ tuple pack, handling all argument lengths greater than two.
+The first non-recursive @max@ function is the polymorphic base-case for the recursion, \ie, find the maximum of two identically typed values with a less-than (@<@) operator.
+The second recursive @max@ function takes two parameters, @T@ and the @TT@ tuple pack, handling all argument lengths greater than two.
 The recursive function computes the maximum for the first argument and the maximum value of the rest of the tuple pack.
 The call of @max@ with one argument is the recursive call, where the tuple pack is converted into two arguments by taking the first value (lisp @car@) from the tuple pack as the first argument (flattening) and the remaining pack becomes the second argument (lisp @cdr@).
@@ -452 +573 @@
 And because \CFA compiles polymorphic functions versus template expansion, many wrapper functions are generated to implement both user-defined generic-types and polymorphism with variadics.
 Fortunately, the only permitted operations on polymorphic function parameters are given by the list of assertion (trait) functions.
-Nevertheless, this small set of functions eventually need to be called with flattened tuple arguments.
+Nevertheless, this small set of functions eventually needs to be called with flattened tuple arguments.
 Unfortunately, packing the variadic arguments into a rigid @struct@ type and generating all the required wrapper functions is significant work and largely wasted because most are never called.
 Interested readers can refer to pages 77-80 of Robert Schluntz's thesis to see how verbose the translator output is to implement a simple variadic call with 3 arguments.
 As the number of arguments increases, \eg a call with 5 arguments, the translator generates a concrete @struct@ types for a 4-tuple and a 3-tuple along with all the polymorphic type data for them.
 An alternative approach is to put the variadic arguments into an array, along with an offset array to retrieve each individual argument.
-This method is similar to how the C @va_list@ object is used (and how \CFA accesses polymorphic fields in a generic type), but the \CFA variadics generate the required type information to guarantee type safety.
-For example, given the following heterogeneous, variadic, typed @print@ and usage.
+This method is similar to how the C @va_list@ object is used (and how \CFA accesses polymorphic fields in a generic type), but the \CFA variadics generate the required type information to guarantee type safety (like the @printf@ format string).
+For example, given the following heterogeneous, variadic, typed @print@ and usage:
 \begin{cquote}
 \begin{tabular}{@{}ll@{}}
@@ -487 +608 @@
 }
 \end{cfa}
-where the fixed-arg polymorphism for @T@ can be handled by the standard @void *@-based \CFA polymorphic calling conventions, and the type information can all be deduced at the call site.
+where the fixed-arg polymorphism for @T@ can be handled by the standard @void *@-based \CFA polymorphic calling conventions, and the type information can be deduced at the call site.
 Note, the variadic @print@ supports heterogeneous types because the polymorphic @T@ is not returned (unlike variadic @max@), so there is no cascade of type relationships.
 
 Turning tuples into first-class values in \CFA does have a few benefits, namely allowing pointers to tuples and arrays of tuples to exist.
-However, it seems unlikely that these types have realistic use cases that cannot be achieved without them.
+However, it seems unlikely that these types have realistic use cases that cannot be achieved with structures.
 And having a pointer-to-tuple type potentially forbids the simple offset-array implementation of variadic polymorphism.
 For example, in the case where a type assertion requests the pointer type @TT *@ in the above example, it forces the tuple type to be a @struct@, and thus incurring a high cost.
 My conclusion is that tuples should not be structured (first-class), rather they should be unstructured.
-This agrees with Rodolfo's original describes
+This agrees with Rodolfo's original description:
 \begin{quote}
 As such, their [tuples] use does not enforce a particular memory layout, and in particular, does not guarantee that the components of a tuple occupy a contiguous region of memory.~\cite[pp.~74--75]{Esteves04}
@@ -509 +630 @@
 However, this forces the programer to use a tuple variable and possibly a tuple type to support a constructor, when they actually want separate variables with separate constructors.
 And as stated previously, type variables (structured tuples) are rare in general \CFA programming so far.
-To address this issue, while retaining the ability to leverage constructors, the following new tuple-like declaration syntax is proposed.
+To address this issue, while retaining the ability to leverage constructors, I proposed the following new tuple-like declaration syntax.
 \begin{cfa}
 [ int x, int y ] = gives_two();
@@ -521 +642 @@
 \end{cfa}
 and the implementation performs as much copy elision as possible.
+Currently, this new declaration form is parsed by \CFA, showing its syntax is viable, but it is unimplemented because of downstream resolver issues.
 
 
@@ -526 +648 @@
 \label{s:inlineSubstructure}
 
-As mentioned \see{\VRef[Figure]{f:Nesting}}, C allows an anonymous aggregate type (@struct@ or @union@) to be embedded (nested) within another one, \eg a tagged union.
+As mentioned, C allows an anonymous aggregate type (@struct@ or @union@) to be embedded (nested) within another one \see{\VRef[Figure]{f:Nesting}}, \eg a tagged union.
 \begin{cfa}
 struct S {
         unsigned int tag;
-        union { $\C{// anonymous nested aggregate}$
+        union { // anonymous nested aggregate
                 int x;  double y;  char z;
         };
 } s;
 \end{cfa}
-The @union@ field-names are hoisted into the @struct@, so there is direct access, \eg @s.x@;
-hence, field names must be unique.
-For a nested anonymous @struct@, both field names and values are hoisted.
+Here, the @union@ combines its field into a common block of storage, and because there is no variable-name overloading in C, all of the union field names must be unique.
+Furthermore, because the union is unnamed, these field-names are hoisted into the @struct@, giving direct access, \eg @s.x@;
+hence, the union field names must be unique with the structure field names.
+The same semantics applies to a nested anonymous @struct@:
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{35pt}}l@{}}
@@ -556 +679 @@
 \end{tabular}
 \end{cquote}
-
-As an aside, C nested \emph{named} aggregates behave in a (mysterious) way because the nesting is allowed but there is no ability to use qualification to access an inner type, like the \CC type operator `@::@'.
-\emph{In fact, all named nested aggregates are hoisted to global scope, regardless of the nesting depth.}
+However, unlike the union which provides storage sharing, there is no semantic difference between the nested anonymous structure and its rewritten counterpart.
+Hence, the nested anonymous structure provides no useful capability.
+
+Nested \emph{named} aggregates are allowed in C but there is no qualification operator, like the \CC type operator `@::@', to access an inner type.
+\emph{To compensate for the missing type operator, all named nested aggregates are hoisted to global scope, regardless of the nesting depth, and type usages within the nested type are replaced with global type name.}
+Hoisting nested types can result in name collisions among types at the global level, which defeats the purpose of nesting the type.
+\VRef[Figure]{f:NestedNamedAggregate} shows the nested type @T@ is hoisted to the global scope and the declaration rewrites within structure @S@.
+Hence, the possible accesses are:
+\begin{cfa}
+struct S s;
+s.i = 1;
+s.t.i = 2;
+s.w = (struct T){ 7, 8 };
+struct T x = { 5, 6 }; // use (un)nested type name
+s.t = (struct T){ 2, 3 };
+\end{cfa}
+where @T@ is used without qualification even though it is nested in @S@.
+It is for these reasons that nested types are not used in C, and if used, are extremely confusing.
+
+\begin{figure}
 \begin{cquote}
 \begin{tabular}{@{}l@{\hspace{35pt}}l@{}}
@@ -564 +704 @@
 \begin{cfa}
 struct S {
-        struct T {
+        @struct T@ {
                 int i, j;
-        };
-        struct U {
-                int k, l;
-        };
-};
+        } t; // warning without declaration
+        struct T w;
+        int k;
+};
+
 \end{cfa}
 &
 \begin{cfa}
-struct T {
+@struct T@ {
         int i, j;
 };
-struct U {
-        int k, l;
-};
 struct S {
+        @struct T t@;
+        struct T w;
+        int k;
 };
 \end{cfa}
 \end{tabular}
 \end{cquote}
-Hence, the possible accesses are:
-\begin{cfa}
-struct S s; // s cannot access any fields
-struct T t;  t.i;  t.j;
-struct U u;  u.k;  u.l;
-\end{cfa}
-and the hoisted type names can clash with global type names.
+\caption{Nested Named Aggregate}
+\label{f:NestedNamedAggregate}
+\end{figure}
+
 For good reasons, \CC chose to change this semantics:
 \begin{cquote}
@@ -604 +741 @@
 \hfill ISO/IEC 14882:1998 (\CC Programming Language Standard)~\cite[C.1.2.3.3]{ANSI98:C++}
 \end{cquote}
-However, there is no syntax to access from a variable through a type to a field.
-\begin{cfa}
-struct S s;  @s::T@.i;  @s::U@.k;
-\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}
+struct S s;  @s.i@;  @s.T@.i;
+\end{cfa}
+See the use case for this feature at the end of this section.
 
 % https://gcc.gnu.org/onlinedocs/gcc/Unnamed-Fields.html
 
-A polymorphic extension to nested aggregates appears in the Plan-9 C dialect, used in the Bell Labs' Plan-9 research operating system.
+A polymorphic extension to nested aggregates appears in the Plan-9 C dialect, used in the Bell Labs' Plan-9 research operating-system.
 The feature is called \newterm{unnamed substructures}~\cite[\S~3.3]{Thompson90new}, which continues to be supported by @gcc@ and @clang@ using the extension (@-fplan9-extensions@).
-The goal is to provided the same effect of the nested aggregate with the aggregate type defined elsewhere, which requires it be named.
+The goal is to provided the same effect as a nested aggregate with the aggregate type defined elsewhere, which requires it be named.
 \begin{cfa}
 union U {  $\C{// unnested named}$
@@ -633 +767 @@
 \end{cfa}
 Note, the position of the substructure is normally unimportant, unless there is some form of memory or @union@ overlay.
-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@.
+Like an anonymous nested type, a named Plan-9 nested 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:
@@ -689 +823 @@
 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 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.
+In the current version of \CFA, this is the only kind of implicit type conversion other than the standard C arithmetic conversions.
 
 Plan-9 polymorphism can result in duplicate field names.
@@ -714 +848 @@
 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@.
+Like \CC, \CFA compiles the Plan-9 version and provides direct qualification 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.
+However, when a programmer does not control all code, this problem can occur and a naming workaround must exist.

doc/theses/fangren_yu_MMath/intro.tex

@@ -6 +6 @@
 \begin{cfa}
 T sum( T a[$\,$], size_t size ) {
-        @T@ total = { @0@ };  // size, 0 for type T
+        @T@ total = { @0@ };  $\C[1.75in]{// size, 0 for type T}$
         for ( size_t i = 0; i < size; i += 1 )
-                total @+=@ a@[@i@]@; // + and subscript for T
+                total @+=@ a@[@i@]@; $\C{// + and subscript for T}\CRT$
         return total;
 }
@@ -22 +22 @@
 All computers have multiple types because computer architects optimize the hardware around a few basic types with well defined (mathematical) operations: boolean, integral, floating-point, and occasionally strings.
 A programming language and its compiler present ways to declare types that ultimately map into the ones provided by the underlying hardware.
-These language types are thrust upon programmers, with their syntactic and semantic rules and restrictions.
-These rules are used to transform a language expression to a hardware expression.
+These language types are thrust upon programmers with their syntactic/semantic rules and restrictions.
+These rules are then used to transform a language expression to a hardware expression.
 Modern programming-languages allow user-defined types and generalize across multiple types using polymorphism.
 Type systems can be static, where each variable has a fixed type during execution and an expression's type is determined once at compile time, or dynamic, where each variable can change type during execution and so an expression's type is reconstructed on each evaluation.
@@ -31 +31 @@
 \section{Overloading}
 
-Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files.
 \begin{quote}
 There are only two hard things in Computer Science: cache invalidation and \emph{naming things}. --- Phil Karlton
 \end{quote}
+Overloading allows programmers to use the most meaningful names without fear of name clashes within a program or from external sources, like include files.
 Experience from \CC and \CFA developers is that the type system implicitly and correctly disambiguates the majority of overloaded names, \ie it is rare to get an incorrect selection or ambiguity, even among hundreds of overloaded (variables and) functions.
 In many cases, a programmer has no idea there are name clashes, as they are silently resolved, simplifying the development process.
-Depending on the language, any ambiguous cases are resolved using some form of qualification and/or casting.
+Depending on the language, any ambiguous cases are resolved explicitly using some form of qualification and/or cast.
 
 
@@ -45 +45 @@
 Like \CC, \CFA maps operators to named functions and allows these operators to be overloaded with user-defined types.
 The syntax for operator names uses the @'?'@ character to denote a parameter, \eg left and right unary operators: @?++@ and @++?@, and binary operators @?+?@ and @?<=?@.
-Here, a user-defined type is extended with an addition operation with the same syntax as builtin types.
+Here, a user-defined type is extended with an addition operation with the same syntax as a builtin type.
 \begin{cfa}
 struct S { int i, j };
@@ -55 +55 @@
 The type system examines each call site and selects the best matching overloaded function based on the number and types of arguments.
 If there are mixed-mode operands, @2 + 3.5@, the type system attempts (safe) conversions, like in C/\CC, converting the argument type(s) to the parameter type(s).
-Conversions are necessary because the hardware rarely supports mix-mode operations, so both operands must be the same type.
-Note, without implicit conversions, programmers must write an exponential number of functions covering all possible exact-match cases among all possible types.
+Conversions are necessary because the hardware rarely supports mix-mode operations, so both operands must be converted to a common type.
+Like overloading, the majority of mixed-mode conversions are silently resolved, simplifying the development process.
+Without implicit conversions, programmers must write an exponential number of functions covering all possible exact-match cases among all possible types.
 This approach does not match with programmer intuition and expectation, regardless of any \emph{safety} issues resulting from converted values.
+Depending on the language, mix-mode conversions can be explicitly controlled using some form of cast.
 
 
@@ -81 +83 @@
 double d = f( 3 );              $\C{// select (2)}\CRT$
 \end{cfa}
-Alternatively, if the type system looks at the return type, there is an exact match for each call, which again matches with programmer intuition and expectation.
-This capability can be taken to the extreme, where there are no function parameters.
+Alternatively, if the type system uses the return type, there is an exact match for each call, which again matches with programmer intuition and expectation.
+This capability can be taken to the extreme, where the only differentiating factor is the return type.
 \begin{cfa}
 int random( void );             $\C[2in]{// (1); overloaded on return type}$
@@ -90 +92 @@
 \end{cfa}
 Again, there is an exact match for each call.
-If there is no exact match, a set of minimal, safe conversions can be added to find a best match, as for operator overloading.
+As for operator overloading, if there is no exact match, a set of minimal, an implicit conversion can be added to find a best match.
+\begin{cfa}
+short int = random();   $\C[2in]{// select (1), unsafe}$
+long double = random(); $\C{// select (2), safe}\CRT$
+\end{cfa}
 
 
@@ -96 +102 @@
 
 Unlike most programming languages, \CFA has variable overloading within a scope, along with shadow overloading in nested scopes.
-(Shadow overloading is also possible for functions, if a language supports nested function declarations, \eg \CC named, nested, lambda functions.)
+Shadow overloading is also possible for functions, in languages supporting nested-function declarations, \eg \CC named, nested, lambda functions.
 \begin{cfa}
 void foo( double d );
@@ -109 +115 @@
 \end{cfa}
 It is interesting that shadow overloading is considered a normal programming-language feature with only slight software-engineering problems.
-However, variable overloading within a scope is often considered extremely dangerous, without any evidence to corroborate this claim.
+However, variable overloading within a scope is considered extremely dangerous, without any evidence to corroborate this claim.
 In contrast, function overloading in \CC occurs silently within the global scope from @#include@ files all the time without problems.
 
-In \CFA, the type system simply treats overloaded variables as an overloaded function returning a value with no parameters.
-Hence, no significant effort is required to support this feature by leveraging the return type to disambiguate as variables have no parameters.
+In \CFA, the type system simply treats an overloaded variable as an overloaded function returning a value with no parameters.
+Hence, no effort is required to support this feature as it is available for differentiating among overloaded functions with no parameters.
 \begin{cfa}
 int MAX = 2147483647;   $\C[2in]{// (1); overloaded on return type}$
@@ -125 +131 @@
 The result is a significant reduction in names to access typed constants.
 
-As an aside, C has a separate namespace for type and variables allowing overloading between the namespaces, using @struct@ (qualification) to disambiguate.
+As an aside, C has a separate namespace for types and variables allowing overloading between the namespaces, using @struct@ (qualification) to disambiguate.
 \begin{cfa}
 void S() {
@@ -133 +139 @@
 }
 \end{cfa}
+Here the name @S@ is an aggregate type and field, and a variable and parameter of type @S@.
 
 
@@ -145 +152 @@
 for ( ; x; --x )   =>    for ( ; x @!= 0@; x @-= 1@ )
 \end{cfa}
-To generalize this feature, both constants are given types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly work with the special @0@ and @1@ contexts.
+To generalize this feature, both constants are given types @zero_t@ and @one_t@ in \CFA, which allows overloading various operations for new types that seamlessly work within the special @0@ and @1@ contexts.
 The types @zero_t@ and @one_t@ have special builtin implicit conversions to the various integral types, and a conversion to pointer types for @0@, which allows standard C code involving @0@ and @1@ to work.
 \begin{cfa}
@@ -176 +183 @@
 \end{cfa}
 For type-only, the programmer specifies the initial type, which remains fixed for the variable's lifetime in statically typed languages.
-For type-and-initialization, the specified and initialization types may not agree.
+For type-and-initialization, the specified and initialization types may not agree requiring an implicit/explicit conversion.
 For initialization-only, the compiler may select the type by melding programmer and context information.
 When the compiler participates in type selection, it is called \newterm{type inferencing}.
-Note, type inferencing is different from type conversion: type inferencing \emph{discovers} a variable's type before setting its value, whereas conversion has two typed values and performs a (possibly lossy) action to convert one value to the type of the other variable.
+Note, type inferencing is different from type conversion: type inferencing \emph{discovers} a variable's type before setting its value, whereas conversion has two typed variables and performs a (possibly lossy) value conversion from one type to the other.
 Finally, for assignment, the current variable and expression types may not agree.
 Discovering a variable or function type is complex and has limitations.
-The following covers these issues, and why some schemes are not amenable with the \CFA type system.
+The following covers these issues, and why this scheme is not amenable with the \CFA type system.
 
 One of the first and powerful type-inferencing system is Hindley--Milner~\cite{Damas82}.
@@ -203 +210 @@
 \end{cfa}
 In both overloads of @f@, the type system works from the constant initializations inwards and/or outwards to determine the types of all variables and functions.
-Note, like template meta programming, there could be a new function generated for the second @f@ depending on the types of the arguments, assuming these types are meaningful in the body of @f@.
+Like template meta-programming, there can be a new function generated for the second @f@ depending on the types of the arguments, assuming these types are meaningful in the body of @f@.
 Inferring type constraints, by analysing the body of @f@ is possible, and these constraints must be satisfied at each call site by the argument types;
 in this case, parametric polymorphism can allow separate compilation.
@@ -246 +253 @@
 This issue is exaggerated with \CC templates, where type names are 100s of characters long, resulting in unreadable error messages.
 \item
-Ensuring the type of secondary variables, match a primary variable(s).
+Ensuring the type of secondary variables, match a primary variable.
 \begin{cfa}
 int x; $\C{// primary variable}$
@@ -252 +259 @@
 \end{cfa}
 If the type of @x@ changes, the type of the secondary variables correspondingly updates.
+There can be strong software-engineering reasons for binding the types of these variables.
 \end{itemize}
 Note, the use of @typeof@ is more restrictive, and possibly safer, than general type-inferencing.
@@ -269 +277 @@
 
 A restriction is the conundrum in type inferencing of when to \emph{brand} a type.
-That is, when is the type of the variable/function more important than the type of its initialization expression.
-For example, if a change is made in an initialization expression, it can cause cascading type changes and/or errors.
-At some point, a variable's type needs to remain constant and the initializing expression needs to be modified or in error when it changes.
+That is, when is the type of the variable/function more important than the type of its initialization expression(s).
+For example, if a change is made in an initialization expression, it can cascade type changes producing many other changes and/or errors.
+At some point, a variable's type needs to remain constant and the initializing expression needs to be modified or be in error when it changes.
 Often type-inferencing systems allow restricting (\newterm{branding}) a variable or function type, so the complier can report a mismatch with the constant initialization.
 \begin{cfa}
@@ -283 +291 @@
 In Haskell, it is common for programmers to brand (type) function parameters.
 
-A confusion is large blocks of code where all declarations are @auto@, as is now common in \CC.
+A confusion is blocks of code where all declarations are @auto@, as is now common in \CC.
 As a result, understanding and changing the code becomes almost impossible.
 Types provide important clues as to the behaviour of the code, and correspondingly to correctly change or add new code.
@@ -299 +307 @@
 In this situation, having the type name or its short alias is essential.
 
-The \CFA's type system tries to prevent type-resolution mistakes by relying heavily on the type of the left-hand side of assignment to pinpoint the right types within an expression.
+\CFA's type system tries to prevent type-resolution mistakes by relying heavily on the type of the left-hand side of assignment to pinpoint the right types within an expression.
 Type inferencing defeats this goal because there is no left-hand type.
 Fundamentally, type inferencing tries to magic away variable types from the programmer.
@@ -308 +316 @@
 The entire area of Computer-Science data-structures is obsessed with time and space, and that obsession should continue into regular programming.
 Understanding space and time issues is an essential part of the programming craft.
-Given @typedef@ and @typeof@ in \CFA, and the strong desire to use the left-hand type in resolution, implicit type-inferencing is unsupported.
-Should a significant need arise, this feature can be revisited.
+Given @typedef@ and @typeof@ in \CFA, and the strong desire to use the left-hand type in resolution, the decision was made not to support implicit type-inferencing in the type system.
+Should a significant need arise, this decision can be revisited.
 
 
@@ -334 +342 @@
 
 To constrain polymorphic types, \CFA uses \newterm{type assertions}~\cite[pp.~37-44]{Alphard} to provide further type information, where type assertions may be variable or function declarations that depend on a polymorphic type variable.
-For example, the function @twice@ works for any type @T@ with a matching addition operator.
+Here, the function @twice@ works for any type @T@ with a matching addition operator.
 \begin{cfa}
 forall( T @| { T ?+?(T, T); }@ ) T twice( T x ) { return x @+@ x; }
 int val = twice( twice( 3 ) );  $\C{// val == 12}$
 \end{cfa}
-For example. parametric polymorphism and assertions occurs in existing type-unsafe (@void *@) C @qsort@ to sort an array.
+Parametric polymorphism and assertions occur in existing type-unsafe (@void *@) C functions, like @qsort@ for sorting an array of unknown values.
 \begin{cfa}
 void qsort( void * base, size_t nmemb, size_t size, int (*cmp)( const void *, const void * ) );
@@ -386 +394 @@
 }
 // select type and size from left-hand side
-int * ip = malloc();  double * dp = malloc();  $@$[aligned(64)] struct S {...} * sp = malloc();
+int * ip = malloc();  double * dp = malloc();  [[aligned(64)]] struct S {...} * sp = malloc();
 \end{cfa}
 The @sized@ assertion passes size and alignment as a data object has no implicit assertions.
 Both assertions are used in @malloc@ via @sizeof@ and @_Alignof@.
-
-These mechanism are used to construct type-safe wrapper-libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions.
-Hence, existing C legacy code is leveraged as much as possible;
+In practise, this polymorphic @malloc@ is unwrapped by the C compiler and the @if@ statement is elided producing a type-safe call to @malloc@ or @memalign@.
+
+This mechanism is used to construct type-safe wrapper-libraries condensing hundreds of existing C functions into tens of \CFA overloaded functions.
+Here, existing C legacy code is leveraged as much as possible;
 other programming languages must build supporting libraries from scratch, even in \CC.
 
@@ -422 +431 @@
 \end{tabular}
 \end{cquote}
-Traits are simply flatten at the use point, as if written in full by the programmer, where traits often contain overlapping assertions, \eg operator @+@.
+Traits are implemented by flatten them at use points, as if written in full by the programmer.
+Flattening often results in overlapping assertions, \eg operator @+@.
 Hence, trait names play no part in type equivalence.
-Note, the type @T@ is an object type, and hence, has the implicit internal trait @otype@.
+In the example, type @T@ is an object type, and hence, has the implicit internal trait @otype@.
 \begin{cfa}
 trait otype( T & | sized(T) ) {
@@ -433 +443 @@
 };
 \end{cfa}
-The implicit routines are used by the @sumable@ operator @?+=?@ for the right side of @?+=?@ and return.
+These implicit routines are used by the @sumable@ operator @?+=?@ for the right side of @?+=?@ and return.
 
 If the array type is not a builtin type, an extra type parameter and assertions are required, like subscripting.
@@ -445 +455 @@
 \begin{enumerate}[leftmargin=*]
 \item
-Write bespoke data structures for each context they are needed.
+Write bespoke data structures for each context.
 While this approach is flexible and supports integration with the C type checker and tooling, it is tedious and error prone, especially for more complex data structures.
 \item
@@ -452 +462 @@
 \item
 Use preprocessor macros, similar to \CC @templates@, to generate code that is both generic and type checked, but errors may be difficult to interpret.
-Furthermore, writing and using preprocessor macros is difficult and inflexible.
+Furthermore, writing and using complex preprocessor macros is difficult and inflexible.
 \end{enumerate}
 
 \CC, Java, and other languages use \newterm{generic types} to produce type-safe abstract data-types.
 \CFA generic types integrate efficiently and naturally with the existing polymorphic functions, while retaining backward compatibility with C and providing separate compilation.
-However, for known concrete parameters, the generic-type definition can be inlined, like \CC templates.
+For concrete parameters, the generic-type definition can be inlined, like \CC templates, if its definition appears in a header file (\eg @static inline@).
 
 A generic type can be declared by placing a @forall@ specifier on a @struct@ or @union@ declaration and instantiated using a parenthesized list of types after the type name.
@@ -484 +494 @@
 \end{cquote}
 \CFA generic types are \newterm{fixed} or \newterm{dynamic} sized.
-Fixed-size types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on their type parameters.
+Fixed-size types have a fixed memory layout regardless of type parameters, whereas dynamic types vary in memory layout depending on the type parameters.
 For example, the type variable @T *@ is fixed size and is represented by @void *@ in code generation;
 whereas, the type variable @T@ is dynamic and set at the point of instantiation.
 The difference between fixed and dynamic is the complexity and cost of field access.
 For fixed, field offsets are computed (known) at compile time and embedded as displacements in instructions.
-For dynamic, field offsets are computed at compile time at the call site, stored in an array of offset values, passed as a polymorphic parameter, and added to the structure address for each field dereference within a polymorphic routine.
+For dynamic, field offsets are compile-time computed at the call site, stored in an array of offset values, passed as a polymorphic parameter, and added to the structure address for each field dereference within a polymorphic routine.
 See~\cite[\S~3.2]{Moss19} for complete implementation details.
 
@@ -517 +527 @@
 \section{Contributions}
 
+The \CFA compiler performance and type capability have been greatly improved through my development work.
 \begin{enumerate}
-\item The \CFA compiler performance and capability have been greatly improved through recent development. The compilation time of various \CFA library units and test programs have been reduced from the order of minutes down to 10-20 seconds, which made it possible to develop and test more complicated \CFA programs that utilize sophisticated type system features. The details of compiler optimization work are covered in a previous technical report.
-\item The thesis presents a systematic review of the new features that have been added to the \CFA language and its type system. Some of the more recent inclusions to \CFA such as tuples and generic structure types were not well tested when they were being developed, due to the limitation of compiler performance. Several issues coming from the interactions of various language features are identified and discussed in this thesis; some of them are now fully resolved, while others are given temporary fixes and need to be reworked in the future.
-\item Finally, this thesis provides constructive ideas of fixing the outstanding issues in \CFA language design and implementation, and gives a path for future improvements to \CFA language and compiler.
+\item
+The compilation time of various \CFA library units and test programs has been reduced by an order of magnitude, from minutes to seconds \see{\VRef[Table]{t:SelectedFileByCompilerBuild}}, which made it possible to develop and test more complicated \CFA programs that utilize sophisticated type system features.
+The details of compiler optimization work are covered in a previous technical report~\cite{Yu20}, which essentially forms part of this thesis.
+\item
+The thesis presents a systematic review of the new features added to the \CFA language and its type system.
+Some of the more recent inclusions to \CFA, such as tuples and generic structure types, were not well tested during development due to the limitation of compiler performance.
+Several issues coming from the interactions of various language features are identified and discussed in this thesis;
+some of them I have resolved, while others are given temporary fixes and need to be reworked in the future.
+\item
+Finally, this thesis provides constructive ideas for fixing a number of high-level issues in the \CFA language design and implementation, and gives a path for future improvements to the language and compiler.
 \end{enumerate}