Changeset e99e43f for doc

Timestamp:

Jan 10, 2019, 3:50:34 PM (7 years ago)

Author:

Aaron Moss <a3moss@…>

Branches:

ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, stuck-waitfor-destruct

Children:

d97c3a4

Parents:

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

git-author:

Aaron Moss <a3moss@…> (01/10/19 14:46:09)

git-committer:

Aaron Moss <a3moss@…> (01/10/19 15:50:34)

Message:

Merge remote-tracking branch 'plg/master' into deferred_resn

Location:

doc

Files:

• bibliography/pl.bib (modified) (21 diffs)
• papers/concurrency/Paper.tex (modified) (14 diffs)
• proposals/flags.md (modified) (2 diffs)
• proposals/vtable.md (added)
• theses/aaron_moss_PhD/phd/Makefile (modified) (4 diffs)
• theses/aaron_moss_PhD/phd/evaluation/generic-timing.dat (added)
• theses/aaron_moss_PhD/phd/evaluation/generic-timing.gp (added)
• theses/aaron_moss_PhD/phd/generic-types.tex (modified) (5 diffs)
• theses/aaron_moss_PhD/phd/introduction.tex (modified) (1 diff)
• theses/aaron_moss_PhD/phd/macros.tex (modified) (2 diffs)
• theses/aaron_moss_PhD/phd/thesis.tex (modified) (3 diffs)
• theses/aaron_moss_PhD/phd/type-environment.tex (modified) (1 diff)
• theses/lynn_tran_SE499/Bibliography.bib (added)
• theses/lynn_tran_SE499/Chapters/CFA.tex (added)
• theses/lynn_tran_SE499/Chapters/Conclusion.tex (added)
• theses/lynn_tran_SE499/Chapters/Demangler.tex (added)
• theses/lynn_tran_SE499/Chapters/Extensions.tex (added)
• theses/lynn_tran_SE499/Chapters/GDB.tex (added)
• theses/lynn_tran_SE499/Chapters/Introduction.tex (added)
• theses/lynn_tran_SE499/Chapters/uCPP.tex (added)
• theses/lynn_tran_SE499/LICENSE (added)
• theses/lynn_tran_SE499/SE499-master.zip (added)
• theses/lynn_tran_SE499/SE499-master/.gdbinit (added)
• theses/lynn_tran_SE499/SE499-master/README.md (added)
• theses/lynn_tran_SE499/SE499-master/test.cc (added)
• theses/lynn_tran_SE499/SE499-master/utils-gdb.gdb (added)
• theses/lynn_tran_SE499/SE499-master/utils-gdb.py (added)
• theses/lynn_tran_SE499/SE499-master/utils.cpp (added)
• theses/lynn_tran_SE499/Thesis.cls (added)
• theses/lynn_tran_SE499/lstpatch.sty (added)
• theses/lynn_tran_SE499/se499-report.tex (added)
• theses/lynn_tran_SE499/uContext_stack.png (added)
• theses/lynn_tran_SE499/vector.sty (added)
• user/Makefile (modified) (1 diff)
• user/user.tex (modified) (45 diffs)
• working/exception/impl/nopic.s (added)
• working/exception/impl/pic.s (added)
• working/exception/impl/test.c (added)

doc/bibliography/pl.bib

@@ -21 +21 @@
 %  toplas: ACM Trans. on Prog. Lang. & Sys.
 %  tcs: Theoretical Computer Science
-@string{ieeepds="IEEE Transactions on Parallel and Distributed Systems"}
-% @string{ieeepds="IEEE Trans. Parallel Distrib. Syst."}
-@string{ieeese="IEEE Transactions on Software Engineering"}
-% @string{ieeese="IEEE Trans. Softw. Eng."}
-@string{spe="Software---\-Practice and Experience"}
-% @string{spe="Softw. Pract. Exp."}
-@string{ccpe="Concurrency and Computation: Practice and Experience"}
-% @string{ccpe="Concurrency Comput: Pract Experience"}
-@string{sigplan="SIGPLAN Notices"}
-% @string{sigplan="SIGPLAN Not."}
-@string{joop="Journal of Object-Oriented Programming"}
-% @string{joop="J. of Object-Oriented Program."}
+
+string{ieeepds="IEEE Transactions on Parallel and Distributed Systems"}
+@string{ieeepds="IEEE Trans. Parallel Distrib. Syst."}
+string{ieeese="IEEE Transactions on Software Engineering"}
+@string{ieeese="IEEE Trans. Softw. Eng."}
+string{spe="Software---\-Practice and Experience"}
+@string{spe="Softw. Pract. Exper."}
+string{ccpe="Concurrency and Computation: Practice and Experience"}
+@string{ccpe="Concurrency Comput.: Pract. Exper."}
+string{sigplan="SIGPLAN Notices"}
+@string{sigplan="SIGPLAN Not."}
+string{joop="Journal of Object-Oriented Programming"}
+@string{joop="J. of Object-Oriented Program."}
 @string{popl="Conference Record of the ACM Symposium on Principles of Programming Languages"}
 @string{osr="Operating Systems Review"}
 @string{pldi="Programming Language Design and Implementation"}
 @string{toplas="Transactions on Programming Languages and Systems"}
-@string{mathann="Mathematische Annalen"}
-% @string{mathann="Math. Ann."}
+string{mathann="Mathematische Annalen"}
+@string{mathann="Math. Ann."}
 
 % A
@@ -566 +567 @@
 }
 
+@inproceedings {Qin18,
+    author      = {Henry Qin and Qian Li and Jacqueline Speiser and Peter Kraft and John Ousterhout},
+    title       = {Arachne: Core-Aware Thread Management},
+    booktitle   = {13th {USENIX} Symp. on Oper. Sys. Design and Impl. ({OSDI} 18)},
+    year        = {2018},
+    address     = {Carlsbad, CA},
+    pages       = {145-160},
+    publisher   = {{USENIX} Association},
+    note        = {\href{https://www.usenix.org/conference/osdi18/presentation/qin}{https://\-www.usenix.org/\-conference/\-osdi18/\-presentation/\-qin}},
+}
+
 @article{Kessels82,
     keywords    = {concurrency, critical section},
@@ -653 +665 @@
     author      = {Joung, Yuh-Jzer},
     title       = {Asynchronous group mutual exclusion},
-    journal     = {Distributed Computing},
+    journal     = {Dist. Comput.},
+    optjournal  = {Distributed Computing},
     year        = {2000},
     month       = {Nov},
@@ -796 +809 @@
         time computable inheritance hierarchy.
     },
-    comment = {
+    comment     = {
         Classes are predicates; if object {\tt o} is in class {\tt C}, then
         {\tt C} is true of {\tt o}.  Classes are combined with {\tt :AND},
@@ -950 +963 @@
 
 @article{Moss18,
-    keywords    = {type systems, tuples, Cforall},
+    keywords    = {type systems, polymorphism, tuples, Cforall},
     contributer = {pabuhr@plg},
     author      = {Aaron Moss and Robert Schluntz and Peter A. Buhr},
     title       = {\textsf{C}$\mathbf{\forall}$ : Adding Modern Programming Language Features to C},
+    journal     = spe,
+    volume      = 48,
+    number      = 12,
+    month       = dec,
     year        = 2018,
-    month       = aug,
-    journal     = spe,
+    pages       = {2111-2146},
     note        = {\href{http://dx.doi.org/10.1002/spe.2624}{http://\-dx.doi.org/\-10.1002/\-spe.2624}},
 }
@@ -989 +1005 @@
     journal     = {Dr. Dobb's Journal of Software Tools},
     year        = 1989,
-    month       = feb, volume = 14, number = 2, pages = {45-51},
+    month       = feb,
+    volume      = 14,
+    number      = 2,
+    pages       = {45-51},
     comment     = {
        A light-weight multitasking kernel for MS-DOS.  A task\_control
@@ -1507 +1526 @@
 }
 
-@techreport{uC++,
+@manual{uC++,
     keywords    = {C++, concurrency, light-weight process, shared memory},
     contributer = {pabuhr@plg},
+    key         = {uC++},
     author      = {Peter A. Buhr},
     title       = {$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Annotated Reference Manual, Version 7.0.0},
-    institution = {School of Computer Science, University of Waterloo},
-    address     = {Waterloo, Ontario, Canada, N2L 3G1},
-    month       = dec,
-    year        = 2017,
+    organization= {University of Waterloo},
+    month       = sep,
+    year        = 2018,
     note        = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}},
 }
@@ -1586 +1605 @@
     author      = {Sun, Xianda},
     title       = {Concurrent High-performance Persistent Hash Table In {J}ava},
-    school      = {School of Computer Science, University of Waterloo},
+    school      = {School of Computer Sc., University of Waterloo},
     year        = 2015,
     optaddress  = {Waterloo, Ontario, Canada, N2L 3G1},
@@ -1936 +1955 @@
     note        = {Svensk Standard SS 63 61 14},
     year        = 1987,
-    abstract    = {
-        Standard for the programming language SIMULA.  Written in English.
-    }
+    abstract    = {Standard for the programming language SIMULA. Written in English.}
+}
+
+@article{Galil91,
+    keywords    = {union-find},
+    contributer = {a3moss@uwaterloo.ca},
+    title       = {Data structures and algorithms for disjoint set union problems},
+    author      = {Galil, Zvi and Italiano, Giuseppe F},
+    journal     = {ACM Computing Surveys (CSUR)},
+    volume      = 23,
+    number      = 3,
+    pages       = {319--344},
+    year        = 1991,
+    publisher   = {ACM},
 }
 
@@ -2078 +2108 @@
     year        = {1998},
     pages       = {393-407},
+}
+
+@book{Aho74,
+    keywords    = {algorithms, textbook, union-find},
+    contributer = {a3moss@uwaterloo.ca},
+    title       = {The Design and Analysis of Computer Algorithms},
+    author      = {Aho, Alfred V and Hopcroft, John E and Ullman, Jeffrey D},
+    year        = {1974},
+    publisher   = {Addison-Wesley},
+    address     = {Reading, MA, USA}
 }
 
@@ -2880 +2920 @@
 }
 
+@inproceedings{Patwary10,
+    keywords    = {union-find},
+    contributer = {a3moss@uwaterloo.ca},
+    author      = {Patwary, Md. Mostofa Ali and Blair, Jean and Manne, Fredrik},
+    editor      = {Festa, Paola},
+    title       = {Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure},
+    booktitle   = {Experimental Algorithms},
+    year        = 2010,
+    publisher   = {Springer Berlin Heidelberg},
+    address     = {Berlin, Heidelberg},
+    pages       = {411--423},
+    isbn        = {978-3-642-13193-6}
+}
+
 % F
 
@@ -3223 +3277 @@
     keywords    = {Go programming language},
     contributer = {pabuhr@plg},
+    author      = {Robert Griesemer and Rob Pike and Ken Thompson},
     title       = {{Go} Programming Language},
-    author      = {Robert Griesemer and Rob Pike and Ken Thompson},
     organization= {Google},
     year        = 2009,
@@ -3416 +3470 @@
     month       = sep,
     publisher   = {John Wiley \& Sons},
-    note        = {\href{https://doi-org.proxy.lib.uwaterloo.ca/10.1002/cpe.4475}{https://\-doi-org.proxy.lib.uwaterloo.ca/\-10.1002/\-cpe.4475}},
+    note        = {\href{https://doi.org/10.1002/cpe.4475}{https://\-doi.org/\-10.1002/\-cpe.4475}},
 }
 
@@ -3554 +3608 @@
     publisher   = {ACM Press},
     address     = {New York, NY, USA},
+}
+
+@article{Galler64,
+    keywords    = {union-find, original},
+    contributer = {a3moss@uwaterloo.ca},
+    title       = {An improved equivalence algorithm},
+    author      = {Galler, Bernard A and Fisher, Michael J},
+    journal     = {Communications of the ACM},
+    volume      = {7},
+    number      = {5},
+    pages       = {301--303},
+    year        = {1964},
+    publisher   = {ACM}
 }
 
@@ -3898 +3965 @@
     author      = {Peter A. Buhr and Martin Karsten and Jun Shih},
     title       = {{\small\textsf{KDB}}: A Multi-threaded Debugger for Multi-threaded Applications},
-    booktitle   = {Proceedings of SPDT'96: SIGMETRICS Symposium on Parallel and Distributed Tools},
+    booktitle   = {Proc. of SPDT'96: SIGMETRICS Symp. on Parallel and Distributed Tools},
     publisher   = {ACM Press},
     address     = {Philadelphia, Pennsylvania, U.S.A.},
@@ -5389 +5456 @@
 }
 
+@inproceedings{Conchon07,
+    keywords    = {persistent array, union-find},
+    contributer = {a3moss@uwaterloo.ca},
+    title       = {A persistent union-find data structure},
+    author      = {Conchon, Sylvain and Filli{\^a}tre, Jean-Christophe},
+    booktitle   = {Proceedings of the 2007 workshop on Workshop on ML},
+    pages       = {37--46},
+    year        = {2007},
+    organization= {ACM}
+}
+
 @article{poly,
     keywords    = {Poly, Standard ML, Russell, persistence},
@@ -5603 +5681 @@
     author      = {Peter A. Buhr and Robert Denda},
     title       = {{$\mu$Profiler} : Profiling User-Level Threads in a Shared-Memory Programming Environment},
-    booktitle   = {Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE'98)},
+    booktitle   = {Proc. of 2nd Inter. Symp. on Computing in Object-Oriented Parallel Environments},
     series      = {Lecture Notes in Computer Science},
     publisher   = {Springer-Verlag},
@@ -5974 +6052 @@
     issn        = {0164-0925},
     pages       = {429-475},
-    url         = {http://doi.acm.org.proxy.lib.uwaterloo.ca/10.1145/1133651.1133653},
+    url         = {http://doi.acm.org/10.1145/1133651.1133653},
     doi         = {10.1145/1133651.1133653},
     acmid       = {1133653},
@@ -6241 +6319 @@
     contributer = {pabuhr@plg},
     key         = {Rust},
-    title       = {The {R}ust Programming Language},
-    address     = {The Rust Project Developers},
+    title       = {{R}ust Programming Language},
+    optaddress  = {Rust Project Developers},
     year        = 2015,
     note        = {\href{https://doc.rust-lang.org/reference.html}{https://\-doc.rust-lang\-.org/\-reference.html}},
@@ -6308 +6386 @@
     publisher   = {Springer},
     note        = {Lecture Notes in Computer Science v. 173},
+}
+
+@article{Baker78,
+    keywords    = {Algol display, FUNARG's, Lisp 1.5, deep binding, environment trees, multiprogramming, shallow binding},
+    contributer = {a3moss@uwaterloo.ca},
+    author      = {Baker,Jr., Henry G.},
+    title       = {Shallow Binding in Lisp 1.5},
+    journal     = {Commun. ACM},
+    issue_date  = {July 1978},
+    volume      = 21,
+    number      = 7,
+    month       = jul,
+    year        = 1978,
+    issn        = {0001-0782},
+    pages       = {565--569},
+    numpages    = {5},
+    url         = {http://doi.acm.org/10.1145/359545.359566},
+    doi         = {10.1145/359545.359566},
+    acmid       = {359566},
+    publisher   = {ACM},
+    address     = {New York, NY, USA}
+}
+
+@article{Baker91,
+    keywords    = {shallow binding, functional arrays},
+    contributer = {a3moss@uwaterloo.ca},
+    author      = {Baker, Henry G.},
+    title       = {Shallow Binding Makes Functional Arrays Fast},
+    journal     = {SIGPLAN Not.},
+    issue_date  = {Aug. 1991},
+    volume      = 26,
+    number      = 8,
+    month       = aug,
+    year        = 1991,
+    issn        = {0362-1340},
+    pages       = {145--147},
+    numpages    = {3},
+    url         = {http://doi.acm.org/10.1145/122598.122614},
+    doi         = {10.1145/122598.122614},
+    acmid       = {122614},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
 }
 
@@ -7476 +7596 @@
 }
 
+@article{Tarjan84,
+    keywords    = {union-find},
+    contributer = {a3moss@uwaterloo.ca},
+    author      = {Tarjan, Robert E. and van Leeuwen, Jan},
+    title       = {Worst-case Analysis of Set Union Algorithms},
+    journal     = {J. ACM},
+    issue_date  = {April 1984},
+    volume      = 31,
+    number      = 2,
+    month       = mar,
+    year        = 1984,
+    issn        = {0004-5411},
+    pages       = {245--281},
+    numpages    = {37},
+    url         = {http://doi.acm.org/10.1145/62.2160},
+    doi         = {10.1145/62.2160},
+    acmid       = {2160},
+    publisher   = {ACM},
+    address     = {New York, NY, USA},
+} 
+
 % X
 

doc/papers/concurrency/Paper.tex

@@ -686 +686 @@
         Fib f1, f2;
         for ( int i = 1; i <= 10; i += 1 ) {
-                sout | next( f1 ) | next( f2 ) | endl;
+                sout | next( f1 ) | next( f2 );
         }
 }
@@ -772 +772 @@
                         sout | "  ";               // separator
                 }
-                sout | endl;
+                sout | nl;
         }
 }
 void ?{}( Format & fmt ) { `resume( fmt );` }
 void ^?{}( Format & fmt ) with( fmt ) {
-        if ( g != 0 || b != 0 ) sout | endl;
+        if ( g != 0 || b != 0 ) sout | nl;
 }
 void format( Format & fmt ) {
@@ -855 +855 @@
         for ( int i = 0; i < N; i += 1 ) {
                 int p1 = random( 100 ), p2 = random( 100 );
-                sout | p1 | " " | p2 | endl;
+                sout | p1 | " " | p2;
                 int status = delivery( c, p1, p2 );
-                sout | " $" | money | endl | status | endl;
+                sout | " $" | money | nl | status;
                 receipt += 1;
         }
         stop( c );
-        sout | "prod stops" | endl;
+        sout | "prod stops";
 }
 int payment( Prod & prod, int money ) {
@@ -895 +895 @@
         int money = 1, receipt;
         for ( ; ! done; ) {
-                sout | p1 | " " | p2 | endl | " $" | money | endl;
+                sout | p1 | " " | p2 | nl | " $" | money;
                 status += 1;
                 receipt = payment( p, money );
-                sout | " #" | receipt | endl;
+                sout | " #" | receipt;
                 money += 1;
         }
-        sout | "cons stops" | endl;
+        sout | "cons stops";
 }
 int delivery( Cons & cons, int p1, int p2 ) {
@@ -1099 +1099 @@
 
 void main(foo & this) {
-        sout | "Hello World!" | endl;
+        sout | "Hello World!";
 }
 \end{cfa}
@@ -1124 +1124 @@
 
 void hello(/*unused*/ int) {
-        sout | "Hello World!" | endl;
+        sout | "Hello World!";
 }
 
@@ -1141 +1141 @@
 thread World {};
 void main( World & this ) {
-        sout | "World!" | endl;
+        sout | "World!";
 }
 int main() {
         World w`[10]`;                                                  $\C{// implicit forks after creation}$
-        sout | "Hello " | endl;                                 $\C{// "Hello " and 10 "World!" printed concurrently}$
+        sout | "Hello ";                                        $\C{// "Hello " and 10 "World!" printed concurrently}$
 }                                                                                       $\C{// implicit joins before destruction}$
 \end{cfa}
@@ -1193 +1193 @@
                 total += subtotals[r];                          $\C{// total subtotal}$
     }
-    sout | total | endl;
+    sout | total;
 }
 \end{cfa}
@@ -2192 +2192 @@
         BENCH(
                 for ( size_t i = 0; i < N; i += 1 ) { @resume( c );@ } )
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 \end{cfa}
@@ -2205 +2205 @@
         BENCH(
                 for ( size_t i = 0; i < N; i += 1 ) { @yield();@ } )
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 \end{cfa}
@@ -2244 +2244 @@
 int main() {
         BENCH( for( size_t i = 0; i < N; i += 1 ) { @do_call( m1/*, m2, m3, m4*/ );@ } )
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 \end{cfa}
@@ -2305 +2305 @@
         BENCH( for ( size_t i = 0; i < N; i += 1 ) { @wait( c );@ } );
         go = 0; // stop other thread
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 int main() {
@@ -2356 +2356 @@
         BENCH( for ( size_t i = 0; i < N; i += 1 ) { @waitfor( do_call, m );@ } )
         go = 0; // stop other thread
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 int main() {
@@ -2391 +2391 @@
 int main() {
         BENCH( for ( size_t i = 0; i < N; i += 1 ) { @MyThread m;@ } )
-        sout | result`ns | endl;
+        sout | result`ns;
 }
 \end{cfa}

doc/proposals/flags.md

@@ -60 +60 @@
         ```
         FunFlags f = some_val();
-        if ( f ) { sout | "f has some flag(s) set" | endl; }
-        if ( f & FOO ) { sout | "f has FOO set" | endl; }
+        if ( f ) { sout | "f has some flag(s) set"; }
+        if ( f & FOO ) { sout | "f has FOO set"; }
         f |= FOO; // set FOO
         f -= FOO; // unset FOO
@@ -88 +88 @@
         ```
         FunFlags f = some_val();
-        if ( f.FOO ) { sout | "f has FOO set" | endl; }
+        if ( f.FOO ) { sout | "f has FOO set"; }
         f.FOO = true;    // set FOO
         f.FOO = false;   // unset FOO

doc/theses/aaron_moss_PhD/phd/Makefile

@@ -1 +1 @@
 BUILD = build
 BIBDIR = ../../../bibliography
+EVALDIR = evaluation
 TEXLIB = .:${BUILD}:${BIBDIR}:
 
-LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction= -output-directory=${BUILD}
+# LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && pdflatex -interaction=nonstopmode -halt-on-error -output-directory=${BUILD}
+LATEX = TEXINPUTS=${TEXLIB} && export TEXINPUTS && latex -halt-on-error -output-directory=${BUILD}
 BIBTEX = BIBINPUTS=${TEXLIB} && export BIBINPUTS && bibtex
+
+VPATH = ${EVALDIR}
 
 BASE = thesis
@@ -23 +27 @@
 }
 
+GRAPHS = ${addsuffix .tex, \
+generic-timing \
+}
+
 .PHONY : all rebuild-refs clean wc
 
@@ -33 +41 @@
         wc ${SOURCES}
 
-${DOCUMENT} : ${SOURCES} ${BUILD}
-        ${LATEX} ${BASE}
-        ${LATEX} ${BASE}
+${DOCUMENT} : ${BASE}.ps
+        ps2pdf ${BUILD}/$<
 
-rebuild-refs : ${SOURCES} ${BIBFILE} ${BUILD}
+${BASE}.ps : ${BASE}.dvi
+        dvips ${BUILD}/$< -o ${BUILD}/$@
+
+${BASE}.dvi : Makefile ${SOURCES} ${GRAPHS} ${BIBFILE} ${BUILD}
         ${LATEX} ${BASE}
         ${BIBTEX} ${BUILD}/${BASE}
@@ -43 +53 @@
         ${LATEX} ${BASE}
 
+${GRAPHS} : generic-timing.gp generic-timing.dat ${BUILD}
+        gnuplot -e BUILD="'${BUILD}/'" ${EVALDIR}/generic-timing.gp
+
 ${BUILD}: 
         mkdir -p ${BUILD}

doc/theses/aaron_moss_PhD/phd/generic-types.tex

@@ -135 +135 @@
 
 \CC{}, Java, and other languages use \emph{generic types} to produce type-safe abstract data types. 
-Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18}. 
+Design and implementation of generic types for \CFA{} is the first major contribution of this thesis, a summary of which is published in \cite{Moss18} and from which this chapter is closely based. 
 \CFA{} generic types integrate efficiently and naturally with the existing polymorphic functions in \CFA{}, while retaining backward compatibility with C in layout and support for separate compilation. 
 A generic type can be declared in \CFA{} by placing a !forall! specifier on a !struct! or !union! declaration, and instantiated using a parenthesized list of types after the generic name. 
@@ -179 +179 @@
 \subsection{Related Work}
 
-One approach to the design of generic types is that taken by \CC{} templates\cit{}. 
+One approach to the design of generic types is that taken by \CC{} templates\cite{C++}. 
 The template approach is closely related to the macro-expansion approach to C polymorphism demonstrated in Figure~\ref{macro-generic-fig}, but where the macro-expansion syntax has been given first-class language support. 
 Template expansion has the benefit of generating code with near-optimal runtime efficiency, as distinct optimizations can be applied for each instantiation of the template. 
@@ -185 +185 @@
 The most significant restriction of the \CC{} template model is that it breaks separate compilation and C's translation-unit-based encapsulation mechanisms. 
 Because a \CC{} template is not actually code, but rather a sort of ``recipe'' to generate code, template code must be visible at its call site to be used. 
+Furthermore, \CC{} template code cannot be type-checked without instantiating it, a time consuming process with no hope of improvement until \CC{} concepts\cite{C++Concepts} are standardized in \CCtwenty{}.
 C code, by contrast, only needs a !struct! or function declaration to call that function or use (by-pointer) values of that type, a desirable property to maintain for \CFA{}.
 
-Java\cit{} has another prominent implementation for generic types, based on a significantly different approach than \CC{}. 
+Java\cite{Java8} has another prominent implementation for generic types, introduced in Java~5 and based on a significantly different approach than \CC{}. 
 The Java approach has much more in common with the !void*!-polymorphism shown in Figure~\ref{void-generic-fig}; since in Java nearly all data is stored by reference, the Java approach to polymorphic data is to store pointers to arbitrary data and insert type-checked implicit casts at compile-time. 
 This process of \emph{type erasure} has the benefit of allowing a single instantiation of polymorphic code, but relies heavily on Java's object model and garbage collector. 
 To use this model, a more C-like language such as \CFA{} would be required to dynamically allocate internal storage for variables, track their lifetime, and properly clean them up afterward. 
 
-\TODO{Talk about Go, maybe Rust, Swift, etc. as well; specifically mention ``fat pointer'' polymorphism}
-
-\TODO{Talk about Cyclone as well, and why my generics are more powerful}
+Cyclone\cite{Grossman06} is another language extending C, and also provides capabilities for polymorphic functions and existential types, similar to \CFA{}'s !forall! functions and generic types. 
+Cyclone existential types can include function pointers in a construct similar to a virtual function table, but these pointers must be explicitly initialized at some point in the code, which is tedious and error-prone compared to \CFA{}'s implicit assertion satisfaction. 
+Furthermore, Cyclone's polymorphic functions and types are restricted to abstraction over types with the same layout and calling convention as !void*!, \ie{} only pointer types and !int!. 
+In the \CFA{} terminology discussed in Section~\ref{generic-impl-sec}, all Cyclone polymorphism must be dtype-static. 
+While the Cyclone polymorphism design provides the efficiency benefits discussed in Section~\ref{dtype-static-sec} for dtype-static polymorphism, it is more restrictive than the more general model of \CFA{}. 
+
+Many other languages include some form of generic types. 
+As a brief survey, ML\cite{ML} was the first language to support parameteric polymorphism, but unlike \CFA{} does not support the use of assertions and traits to constrain type arguments. 
+Haskell\cite{Haskell10} combines ML-style polymorphism with the notion of type classes, similar to \CFA{} traits, but requiring an explicit association with their implementing types, unlike \CFA{}. 
+Objective-C\cite{obj-c-book} is an extension to C which has had some industrial success; however, it did not support type-checked generics until recently\cite{xcode7}, and it's garbage-collected, message-passing object-oriented model is a radical departure from C.
+Go\cite{Go}, and Rust\cite{Rust} are modern compiled languages with abstraction features similar to \CFA{} traits, \emph{interfaces} in Go and \emph{traits} in Rust. 
+Go has implicit interface implementation and uses a ``fat pointer'' construct to pass polymorphic objects to functions, similar in principle to \CFA{}'s implicit forall paramters. 
+Go does not, however, allow user code to define generic types, restricting Go programmers to the small set of generic types defined by the compiler. 
+Rust has powerful abstractions for generic programming, including explicit implemenation of traits and options for both separately-compiled virtual dispatch and template-instantiated static dispatch in functions. 
+On the other hand, the safety guarantees of Rust's \emph{lifetime} abstraction and borrow checker impose a distinctly idiosyncratic programming style and steep learning curve; \CFA{}, with its more modest safety features, allows direct ports of C code while maintaining the idiomatic style of the original source. 
 
 \subsection{\CFA{} Generics}
@@ -212 +225 @@
 
 In this example, !with_len! is defined at the same scope as !pair!, but it could be called from any context that can see the definition of !pair! and a declaration of !with_len!. 
-If its return type was !pair(const char*, int)*!, callers of !with_len! would only need the declaration !forall(otype R, otype S) struct pair;! to call it, in accordance with the usual C rules for opaque types.
+If its return type was !pair(const char*, int)*!, callers of !with_len! would only need the declaration !forall(otype R, otype S) struct pair! to call it, in accordance with the usual C rules for opaque types.
 
 !with_len! is itself a monomorphic function, returning a type that is structurally identical to !struct { const char* first; int second; }!, and as such could be called from C given an appropriate redeclaration and demangling flags. 
@@ -234 +247 @@
 \end{cfa}
 
-\section{Implementation}
-
-% forall constraints on struct/union constrain default constructor (TODO check with Rob)
-
-% TODO discuss layout function algorithm, application to separate compilation
-% TODO put a static const field in for _n_fields for each generic, describe utility for separate compilation (actually no, you need to be able to see the type for it to be sized)
-
-% mention that tuples are implemented on top of a per-arity generic type
-
-\section{Performance Experiments}
-
-% TODO pull benchmarks from Moss et al.
+\CFA{} generic types also support the type constraints from !forall! functions. 
+For example, the following declaration of a sorted set type ensures that the set key implements equality and relational comparison:
+
+\begin{cfa}
+forall(otype Key | { int ?==?(Key, Key); int ?<?(Key, Key); }) struct sorted_set;
+\end{cfa}
+
+These constraints are implemented by applying equivalent constraints to the compiler-generated constructors for this type.
+
+\section{Implementation} \label{generic-impl-sec}
+
+The ability to use generic types in polymorphic contexts means that the \CFA{} implementation in \CFACC{} must support a mechanism for accessing fields of generic types dynamically at runtime. 
+While \CFACC{} could in principle use this same mechanism for accessing fields of all generic types, such an approach would throw away compiler knowledge of static types and impose an unnecessary runtime cost, limiting the utility of the generic type design. 
+Instead, my design for generic type support in \CFACC{} distinguishes between \emph{concrete} generic types that have a fixed memory layout regardless of type parameters and \emph{dynamic} generic types that may vary in memory layout depending on their type parameters.
+A \emph{dtype-static} type has polymorphic parameters but is still concrete. 
+Polymorphic pointers are an example of dtype-static types; given some type variable !T!, T is a polymorphic type, but !T*! has a fixed size and can therefore be represented by a !void*! in code generation. 
+In particular, generic types where all parameters are un-!sized! (\ie{} they do not conform to the built-in !sized! trait because the compiler does not know their size and alignment) are always concrete, as there is no possibility for their layout to vary based on type parameters of unknown size and alignment. 
+More precisely, a type is concrete if and only if all of its !sized! type parameters are concrete, and a concrete type is dtype-static if any of its type parameters are (possibly recursively) polymorphic. 
+To illustrate, the following code using the !pair! type from above \TODO{test this} has each use of !pair! commented with its class:
+
+\begin{cfa}
+//dynamic, layout varies based on T
+forall(otype T) T value( pair(const char*, T) p ) { return p.second; }
+
+// dtype-static, F* and T* are concrete but recursively polymorphic
+forall(dtype F, otype T) T value( pair(F*, T*) ) { return *p.second; }
+
+pair(const char*, int) p = {"magic", 42}; $\C[2.5in]{// concrete}$
+int i = value(p);
+pair(void*, int*) q = {0, &p.second}; $\C[2.5in]{// concrete}$
+i = value(q);
+double d = 1.0;
+pair(double*, double*) r = {&d, &d}; $\C[2.5in]{// concrete}$
+d = value(r);
+\end{cfa}
+
+\subsection{Concrete Generic Types}
+
+The \CFACC{} translator template expands concrete generic types into new structure types, affording maximal inlining. 
+To enable interoperation among equivalent instantiations of a generic type, \CFACC{} saves the set of instantiations currently in scope and reuses the generated structure declarations where appropriate. 
+In particular, tuple types are implemented as a single compiler-generated generic type definition per tuple arity, and can be instantiated and reused according to the usual rules for generic types. 
+A function declaration that accepts or returns a concrete generic type produces a declaration for the instantiated structure in the same scope, which all callers may reuse. 
+As an example, the concrete instantiation for !pair(const char*, int)! is\footnote{This omits the field name mangling performed by \CFACC{} for overloading purposes.\label{mangle-foot}}
+
+\begin{cfa}
+struct _pair_conc0 { const char * first; int second; };
+\end{cfa}
+
+A concrete generic type with dtype-static parameters is also expanded to a structure type, but this type is used for all matching instantiations. 
+In the example above, the !pair(F*, T*)! parameter to !value! is such a type; its expansion is below\footref{mangle-foot}, and it is used as the type of the variables !q! and !r! as well, with casts for member access where appropriate.
+
+\begin{cfa}
+struct _pair_conc1 { void* first; void* second; };
+\end{cfa}
+
+\subsection{Dynamic Generic Types}
+
+In addition to this efficient implementation of concrete generic types, \CFA{} also offers flexibility with powerful support for dynamic generic types. 
+In the pre-existing compiler design, !otype! (and all !sized!) type parameters come with implicit size and alignment parameters provided by the caller. 
+The design for generic types presented here adds an \emph{offset array} containing structure-member offsets for dynamic generic !struct! types. 
+A dynamic generic !union! needs no such offset array, as all members are at offset 0, but size and alignment are still necessary. 
+Access to members of a dynamic structure is provided at runtime via base displacement addressing the structure pointer and the member offset (similar to the !offsetof! macro), moving a compile-time offset calculation to runtime. 
+
+the offset arrays are statically generated where possible. 
+If a dynamic generic type is passed or returned by value from a polymorphic function, \CFACC{} can safely assume that the generic type is complete (\ie{} has a known layout) at any call site, and the offset array is passed from the caller; if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C !offsetof! macro. 
+As an example, the body of the second !value! function above is implemented as 
+
+\begin{cfa}
+_assign_T( _retval, p + _offsetof_pair[1] ); $\C[2in]{// return *p.second}$
+\end{cfa}
+
+Here, !_assign_T! is passed in as an implicit parameter from !otype T! and takes two !T*! (!void*! in the generated code), a destination and a source, and !_retval! is the pointer to a caller-allocated buffer for the return value, the usual \CFA{} method to handle dynamically-sized return types. 
+!_offsetof_pair! is the offset array passed into !value!; this array is generated at the call site as
+
+\begin{cfa}
+size_t _offsetof_pair[] = {offsetof(_pair_conc0, first),  offsetof(_pair_conc0, second)};
+\end{cfa}
+
+\subsubsection{Layout Functions}
+
+In some cases, the offset arrays cannot be statically generated. 
+For instance, modularity is generally provided in C by including an opaque forward declaration of a structure and associated accessor and mutator functions in a header file, with the actual implementations in a separately-compiled \texttt{.c} file. 
+\CFA{} supports this pattern for generic types, implying that the caller of a polymorphic function may not know the actual layout or size of a dynamic generic type and only holds it by pointer. 
+\CFACC{} automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed into a function from that functions's caller. 
+These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all !sized! parameters to the generic structure. 
+Un!sized! parameters not passed because they are forbidden from being used in a context that affects layout by C's usual rules about incomplete types. 
+Similarly, the layout function can only safely be called from a context where the generic type definition is visible, because otherwise the caller will not know how large to allocate the array of member offsets. 
+
+The C standard does not specify a memory layout for structs, but the POSIX ABI for x86\cit{} does; this memory layout is common for C implementations, but is a platform-specific issue for porting \CFA{}. 
+This algorithm, sketched below in pseudo-\CFA{}, is a straightforward mapping of consecutive fields into the first properly-aligned offset in the !struct! layout; layout functions for !union! types omit the offset array and simply calculate the maximum size and alignment over all union variants. 
+Since \CFACC{} generates a distinct layout function for each type, constant-folding and loop unrolling are applied.
+
+\begin{cfa}
+forall(dtype T1, dtype T2, ... | sized(T1) | sized(T2) | ...)
+void layout(size_t* size, size_t* align, size_t* offsets) {
+        // initialize values
+        *size = 0; *align = 1;
+        // set up members
+        for ( int i = 0; i < n_fields; ++i ) {
+                // pad to alignment
+                size_t off_align = *size % alignof(field[i]);
+                if ( off_align != 0 ) { *size += alignof(field[i]) - off_align; }
+                // mark member, increase size, and fix alignment
+                offsets[i] = *size;
+                *size += sizeof(field[i]);
+                if ( *align < alignof(field[i]) ) { *align = alignof(field[i]); }
+        }
+        // final padding to alignment
+        size_t off_align = *size % *align;
+        if ( off_align != 0 ) { *size += *align - off_align; }
+}
+\end{cfa}
+
+Results of layout function calls are cached so that they are only computed once per type per function. 
+Layout functions also allow generic types to be used in a function definition without reflecting them in the function signature, an important implemenation-hiding constraint of the design. 
+For instance, a function that strips duplicate values from an unsorted !list(T)! likely has a reference to the list as its only explicit parameter, but uses some sort of !set(T)! internally to test for duplicate values. 
+This function could acquire the layout for !set(T)! by calling its layout function, providing as an argument the layout of !T! implicitly passed into that function.
+
+Whether a type is concrete, dtype-static, or dynamic is decided solely on the basis of the type arguments and !forall! clause type paramters. 
+This design allows opaque forward declarations of generic types, \eg{} !forall(otype T) struct Box;! like in C, all uses of $Box(T)$ can be separately compiled, and callers from other translation units know the proper calling conventions to use. 
+In an alternate design where the definition of a structure type is included in deciding whether a generic type is dynamic or concrete, some further types may be recognized as dtype-static --- \eg{} !Box! could be defined with a body !{ T* p; }!, and would thus not depend on !T! for its layout. 
+However, the existence of an !otype! parameter !T! means that !Box! \emph{could} depend on !T! for its layout if this definition is not visible, and we judged preserving separate compilation (and the associated C compatibility) in the implemented design to be an acceptable trade-off.
+
+\subsection{Applications of Dtype-static Types} \label{dtype-static-sec}
+
+The reuse of dtype-static structure instantiations enables useful programming patterns at zero runtime cost. 
+The most important such pattern is using !forall(dtype T) T*! as a type-checked replacement for !void*!, \eg{} creating a lexicographic comparison function for pairs of pointers.
+
+\begin{cfa}
+forall(dtype T)
+int lexcmp( pair(T*, T*)* a, pair(T*, T*)* b, int (*cmp)(T*, T*) ) {
+        int c = cmp( a->first, b->first );
+        return c ? c : cmp( a->second, b->second );
+}
+\end{cfa}
+
+Since !pair(T*, T*)! is a concrete type, there are no implicit parameters passed to !lexcmp!; hence, the generated code is identical to a function written in standard C using !void*!, yet the \CFA{} version is type-checked to ensure members of both pairs and arguments to the comparison function match in type.
+
+Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \emph{tag structures}. 
+Sometimes, information is only used for type checking and can be omitted at runtime. 
+In the example below, !scalar! is a dtype-static type; hence, all uses have a single structure definition containing !unsigned long! and can share the same implementations of common functions like !?+?!. 
+These implementations may even be separately compiled, unlike \CC{} template functions.
+However, the \CFA{} type checker ensures matching types are used by all calls to !?+?!, preventing nonsensical computations like adding a length to a volume.
+
+\begin{cfa}
+forall(dtype Unit) struct scalar { unsigned long value; };
+struct metres {};
+struct litres {};
+
+forall(dtype U) scalar(U) ?+?(scalar(U) a, scalar(U) b) {
+        return (scalar(U)){ a.value + b.value };
+}
+
+scalar(metres) half_marathon = { 21098 };
+scalar(litres) pool = { 2500000 };
+scalar(metres) marathon = half_marathon + half_marathon;
+`marathon + pool;` $\C[4in]{// compiler ERROR, mismatched types}$
+\end{cfa}
+
+\section{Performance Experiments} \label{generic-performance-sec}
+
+To validate the practicality of this generic type design I have conducted microbenchmark-based tests against a number of comparable code designs in C and \CC{}, first published in \cite{Moss18}. 
+Since all these languages are compiled with the same compiler backend and share a subset essentially comprising standard C, maximal-performance benchmarks should show little runtime variance, differing only in length and clarity of source code. 
+A more illustrative comparison measures the costs of idiomatic usage of each language's features. 
+The code below shows the \CFA{} benchmark tests for a generic stack based on a singly-linked list; the test suite is equivalent for the other other languages. 
+The experiment uses element types !int! and !pair(short, char)! and pushes $N = 40M$ elements on a generic stack, copies the stack, clears one of the stacks, and finds the maximum value in the other stack.
+
+\begin{cfa}
+int main() {
+        int max = 0, val = 42;
+        stack( int ) si, ti;
+
+        REPEAT_TIMED( "push_int", N, push( si, val ); )
+        TIMED( "copy_int", ti{ si }; )
+        TIMED( "clear_int", clear( si ); )
+        REPEAT_TIMED( "pop_int", N, int x = pop( ti ); if ( x > max ) max = x; )
+
+        pair( short, char ) max = { 0h, '\0' }, val = { 42h, 'a' };
+        stack( pair( short, char ) ) sp, tp;
+
+        REPEAT_TIMED( "push_pair", N, push( sp, val ); )
+        TIMED( "copy_pair", tp{ sp }; )
+        TIMED( "clear_pair", clear( sp ); )
+        REPEAT_TIMED( "pop_pair", N, pair(short, char) x = pop( tp ); 
+                if ( x > max ) max = x; )
+}
+\end{cfa}
+
+The four versions of the benchmark implemented are C with !void*!-based polymorphism, \CFA{} with parameteric polymorphism, \CC{} with templates, and \CC{} using only class inheritance for polymorphism, denoted \CCV{}. 
+The \CCV{} variant illustrates an alternative object-oriented idiom where all objects inherit from a base !object! class, mimicking a Java-like interface; in particular, runtime checks are necessary to safely downcast objects. 
+The most notable difference among the implementations is the memory layout of generic types: \CFA{} and \CC{} inline the stack and pair elements into corresponding list and pair nodes, while C and \CCV{} lack such capability and, instead, must store generic objects via pointers to separately allocated objects. 
+Note that the C benchmark uses unchecked casts as C has no runtime mechanism to perform such checks, whereas \CFA{} and \CC{} provide type safety statically.
+
+Figure~\ref{generic-eval-fig} and Table~\ref{generic-eval-table} show the results of running the described benchmark. 
+The graph plots the median of five consecutive runs of each program, with an initial warm-up run omitted. 
+All code is compiled at \texttt{-O2} by gcc or g++ 6.4.0, with all \CC{} code compiled as \CCfourteen{}. 
+The benchmarks are run on an Ubuntu 16.04 workstation with 16 GB of RAM and a 6-core AMD FX-6300 CPU with 3.5 GHz maximum clock frequency. 
+I conjecture that these results scale across most uses of generic types, given the constant underlying polymorphism implementation. 
+
+\begin{figure}
+\centering
+\input{generic-timing}
+\caption{Benchmark timing results (smaller is better)} \label{generic-eval-fig}
+\end{figure}
+
+\begin{table}
+\caption{Properties of benchmark code} \label{generic-eval-table}
+\centering
+\newcommand{\CT}[1]{\multicolumn{1}{c}{#1}}
+\begin{tabular}{lrrrr}
+                                                                        & \CT{C}        & \CT{\CFA}     & \CT{\CC}      & \CT{\CCV}             \\
+maximum memory usage (MB)                       & 10\,001       & 2\,502        & 2\,503        & 11\,253               \\
+source code size (lines)                        & 201           & 191           & 125           & 294                   \\
+redundant type annotations (lines)      & 27            & 0                     & 2                     & 16                    \\
+binary size (KB)                                        & 14            & 257           & 14            & 37                    \\
+\end{tabular}
+\end{table}
+
+The C and \CCV{} variants are generally the slowest and have the largest memory footprint, due to their less-efficient memory layout and the pointer indirection necessary to implement generic types in those languages; this inefficiency is exacerbated by the second level of generic types in the pair benchmarks. 
+By contrast, the \CFA{} and \CC{} variants run in roughly equivalent time for both the integer and pair because of the equivalent storage layout, with the inlined libraries (\ie{} no separate compilation) and greater maturity of the \CC{} compiler contributing to its lead. 
+\CCV{} is slower than C largely due to the cost of runtime type checking of downcasts (implemented with !dynamic_cast!); the outlier for \CFA{}, pop !pair!, results from the complexity of the generated-C polymorphic code. 
+The gcc compiler is unable to optimize some dead code and condense nested calls; a compiler designed for \CFA{} could more easily perform these optimizations. 
+Finally, the binary size for \CFA{} is larger because of static linking with \CFA{} libraries.
+
+\CFA{} is also competitive in terms of source code size, measured as a proxy for programmer effort. 
+The line counts in Table~\ref{generic-eval-table} include implementations of !pair! and !stack! types for all four languages for purposes of direct comparison, although it should be noted that \CFA{} and \CC{} have prewritten data structures in their standard libraries that programmers would generally use instead. 
+Use of these standard library types has minimal impact on the performance benchmarks, but shrinks the \CFA{} and \CC{} code to 39 and 42 lines, respectively. 
+The difference between the \CFA{} and \CC{} line counts is primarily declaration duplication to implement separate compilation; a header-only \CFA{} library is similar in length to the \CC{} version. 
+On the other hand, due to the language shortcomings mentioned at the beginning of the chapter, C does not have a generic collections library in its standard distribution, resulting in frequent reimplementation of such collection types by C programmers. 
+\CCV{} does not use the \CC{} standard template library by construction, and, in fact, includes the definition of !object! and wrapper classes for !char!, !short!, and !int! in its line count, which inflates this count somewhat, as an actual object-oriented language would include these in the standard library. 
+I justify the given line count by noting that many object-oriented languages do not allow implementing new interfaces on library types without subclassing or wrapper types, which may be similarly verbose. 
+
+Line count is a fairly rough measure of code complexity; another important factor is how much type information the programmer must specify manually, especially where that information is not type-checked. 
+Such unchecked type information produces a heavier documentation burden and increased potential for runtime bugs and is much less common in \CFA{} than C, with its manually specified function pointer arguments and format codes, or \CCV{}, with its extensive use of un-type-checked downcasts, \eg{} !object! to !integer! when popping a stack. 
+To quantify this manual typing, the ``redundant type annotations'' line in Table~\ref{generic-eval-table} counts the number of lines on which the known type of a variable is respecified, either as a format specifier, explicit downcast, type-specific function, or by name in a !sizeof!, !struct! literal, or !new! expression. 
+The \CC{} benchmark uses two redundant type annotations to create new stack nodes, whereas the C and \CCV{} benchmarks have several such annotations spread throughout their code. 
+The \CFA{} benchmark is able to eliminate \emph{all} redundant type annotations through use of the return-type polymorphic !alloc! function in the \CFA{} standard library. 
 
 \section{Future Work}
 
-% mention future work adding non-type generic parameters, like ints
-
-% taking advantage of generic layout functions to provide field assertions in forall qualifiers
-
-% mention packed generic layouts (significantly more complex layout function, but possible)
+The generic types design presented here is already sufficiently expressive to implement a variety of useful library types. 
+However, some other features based on this design could further improve \CFA{}. 
+
+The most pressing addition is the ability to have non-type generic parameters. 
+C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters, and allowing \CFA{} users the capability to build similar types is a requested feature. 
+More exotically, the ability to have these non-type parameters depend on dynamic runtime values rather than static compile-time constants opens up interesting opportunities for type-checking problematic code patterns. 
+For example, if a collection iterator was parameterized over the pointer to the collection it was drawn from, then a sufficiently powerful static analysis pass could ensure that that iterator was only used for that collection, eliminating one source of hard-to-find bugs. 
+
+The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}. 
+One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables. 
+Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types. 
+Simulating field access can already be done more flexibly in \CFA{} by declaring a trait containing an accessor function to be called from polymorphic code, but these accessor functions impose some overhead both to write and call, and directly providing field access via an implicit offset parameter would be both more concise and more efficient. 
+Of course, there are language design trade-offs to such an approach, notably that providing the two similar features of field and function assertions would impose a burden of choice on programmers writing traits, with field assertions more efficient, but function assertions more general; given this open design question we have deferred a decision on field assertions until we have more experience using \CFA{}.
+If field assertions are included in the language, a natural extension would be to provide a structural inheritance mechanism for every !struct! type that simply turns the list of !struct! fields into a list of field assertions, allowing monomorphic functions over that type to be generalized to polymorphic functions over other similar types with added or reordered fields.
+\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- the layout function would need to be re-written, but nothing in the use of the offset arrays implies that the field offsets need be monotonically increasing.
+
+With respect to the broader \CFA{} polymorphism design, the experimental results in Section~\ref{generic-performance-sec} demonstrate that though the runtime impact of \CFA{}'s dynamic virtual dispatch is low, it is not as low as the static dispatch of \CC{} template inlining. 
+However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, we are considering more targeted mechanisms for performance-sensitive code. 
+Two promising approaches are are an !inline! annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing a different !inline! annotation on polymorphic function definitions to instantiate a specialized version of the function for some set of types. 
+These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat. 
+In general, the \CFA{} team believes that separate compilation works well with loaded hardware caches by producing smaller code, which may offset the benefit of larger inlined code. 

doc/theses/aaron_moss_PhD/phd/introduction.tex

@@ -5 +5 @@
 
 \begin{table}[h]
-\label{tiobe-table}
-\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years}
+\caption[TIOBE index over time]{Current top 5 places in the TIOBE index averaged over years} \label{tiobe-table}
 
 \centering

doc/theses/aaron_moss_PhD/phd/macros.tex

@@ -12 +12 @@
 \newcommand{\CCseventeen}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}17} % C++17 symbolic name
 \newcommand{\CCtwenty}{\textrm{C}\kern-.1em\hbox{+\kern-.25em+}20} % C++20 symbolic name
+\newcommand{\CCV}{\rm C\kern-.1em\hbox{+\kern-.25em+}obj} % C++ virtual symbolic name
 \newcommand{\Csharp}{C\raisebox{-0.7ex}{\Large$^\sharp$}} % C# symbolic name
 
@@ -19 +20 @@
 \newcommand{\etal}{\textit{et~al.}}
 
+\newcommand{\myset}[1]{\left\{#1\right\}}
+
 \newcommand{\TODO}[1]{\textbf{TODO:} \textit{#1}}
 \newcommand{\cit}{\textsuperscript{[citation needed]}}

doc/theses/aaron_moss_PhD/phd/thesis.tex

@@ -21 +21 @@
 
 \usepackage{amsmath,amssymb,amstext} % Lots of math symbols and environments
-\usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver 
+% \usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver 
+\usepackage{graphicx}
+
+\usepackage{amsthm} % for theorem environment
+\newtheorem{theorem}{Theorem}
+
+\usepackage{footmisc} % for double refs to the same footnote
 
 % Hyperlinks make it very easy to navigate an electronic document.
@@ -28 +34 @@
 % Use the "hyperref" package 
 % N.B. HYPERREF MUST BE THE LAST PACKAGE LOADED; ADD ADDITIONAL PKGS ABOVE
-\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options
+%\usepackage[pdftex,pagebackref=false]{hyperref} % with basic options
+\usepackage[pagebackref=false]{hyperref}
 % N.B. pagebackref=true provides links back from the References to the body text. This can cause trouble for printing.
 
@@ -120 +127 @@
 \input{background}
 \input{generic-types}
+\input{resolution-heuristics}
 \input{type-environment}
-\input{resolution-heuristics}
 \input{conclusion}
 

doc/theses/aaron_moss_PhD/phd/type-environment.tex

@@ -2 +2 @@
 \label{env-chap}
 
-Talk about the type environment data structure. Pull from your presentation.
+One key data structure for expression resolution is the \emph{type environment}. 
+As discussed in Chapter~\ref{resolution-chap}, being able to efficiently determine which type variables are bound to which concrete types or whether two type environments are compatible is a core requirement of the resolution algorithm. 
+Furthermore, expression resolution involves a search through many related possible solutions, so being able to re-use shared subsets of type environment data and to switch between environments quickly is desirable for performance. 
+In this chapter I discuss and empirically compare a number of type environment data structure variants, including some novel variations on the union-find\cite{Galler64} data structure introduced in this thesis.
+
+\section{Definitions} \label{env-defn-sec}
+
+For purposes of this chapter, a \emph{type environment} $T$ is a set of \emph{type classes} $\myset{T_1, T_2, \cdots, T_{|T|}}$. 
+Each type class $T_i$ contains a set of \emph{type variables} $\myset{v_{i,1}, v_{i,2}, \cdots, v_{i,|T_i|}}$; note that the sets of variables contained in two distinct classes in the same environment must be disjoint. 
+Each individual type class $T_i$ may also be associated with a \emph{bound}, $b_i$; this bound contains the \emph{bound type} which the variables in the type class are replaced with, but also includes other information in \CFACC{}, including whether type conversions are permissible on the bound type and what sort of type variables are contained in the class (data types, function types, or variadic tuples). 
+
+\begin{table}
+\caption[Type environment operation summary]{Summary of type environment operations.}
+\label{env-op-table}
+\centering
+\begin{tabular}{r@{\hskip 0.25em}ll}
+        $find(T, v_{i,j})$ & $\rightarrow T_i | \bot$           & Locate class for variable             \\
+        $report(T_i)$ & $\rightarrow \{ v_{i,j} \cdots \}$      & List variables for class              \\
+        $bound(T_i)$ & $\rightarrow b_i | \bot$                         & Get bound for class                   \\
+        $insert(v_{i,1})$ &                                                                     & New single-variable class             \\
+        $add(T_i, v_{i,j})$ &                                                           & Add variable to class                 \\
+        $bind(T_i, b_i)$ &                                                                      & Set or update class bound             \\
+        $unify(T, T_i, T_j)$ & $\rightarrow \top | \bot$        & Combine two type classes              \\
+        $split(T, T_i)$ & $\rightarrow T'$                                      & Revert the last $unify$ operation on $T_i$            \\
+        $combine(T, T')$ & $\rightarrow \top | \bot$            & Merge two environments                \\
+        $save(T)$ & $\rightarrow H$                                                     & Get handle for current state  \\
+        $backtrack(T, H)$ &                                                                     & Return to handle state
+\end{tabular}
+\end{table}
+
+Given this basic structure, type environments in \CFACC{} need to support eleven basic operations, summarized in Table~\ref{env-op-table}. 
+The first seven operations are straightforward queries and updates on these data structures: 
+The lookup operation $find(T, v_{i,j})$ produces $T_i$, the type class in $T$ which contains variable $v_{i,j}$, or an invalid sentinel value for no such class. 
+The other two query operations act on type classes, where $report(T_i)$ produces the set $\myset{v_{i,1}, v_{i,2}, \cdots, v_{i,|T_i|}}$ of all type variables in a class $T_i$ and $bound(T_i)$ produces the bound $b_i$ of that class, or a sentinel indicating no bound is set. 
+
+The update operation $insert(T, v_{i,1})$ creates a new type class $T_i$ in $T$ that contains only the variable $v_{i,1}$ and no bound; due to the disjointness property $v_{i,1}$ cannot belong to any other type class in $T$. 
+The $add(T_i, v_{i,j})$ operation adds a new type variable $v_{i,j}$ to class $T_i$; again, $v_{i,j}$ cannot exist elsewhere in $T$.
+$bind(T_i, b_i)$ mutates the bound for a type class, setting or updating the current bound. 
+
+The $unify$ operation is the fundamental non-trivial operation a type environment data structure must support. 
+$unify(T, T_i, T_j)$ merges a type class $T_j$ into another $T_i$, producing a failure result and leaving $T$ in an invalid state if this merge fails. 
+It is always possible to unify the type variables of both classes by simply taking the union of both sets; given the disjointness property, no checks for set containment are required, and the variable sets can simply be concatenated if supported by the underlying data structure. 
+$unify$ depends on an internal $unifyBound$ operation which may fail. 
+In \CFACC{}, $unifyBound(b_i, b_j) \rightarrow b'_i|\bot$ checks that the type classes contain the same sort of variable, takes the tighter of the two conversion permissions, and checks if the bound types can be unified. 
+If the bound types cannot be unified (\eg{} !struct A! with !int*!), then $unifyBound$ fails, while other combinations of bound types may result in recursive calls. 
+For instance, unifying !R*! with !S*! for type variables !R! and !S! will result in a call to $unify(T, find($!R!$), find($!S!$))$, while unifying !R*! with !int*! will result in a call to $unifyBound$ on !int! and the bound type of the class containing !R!.
+As such, a call to $unify(T, T_i, T_j)$ may touch every type class in $T$, not just $T_i$ and $T_j$, collapsing the entirety of $T$ into a single type class in extreme cases. 
+For more information on \CFA{} unification, see \cite{Bilson03}.
+The inverse of $unify$ is $split(T, T_i)$, which produces a new environment $T'$ which is the same as $T$ except that $T_i$ has been replaced by two classes corresponding to the arguments to the previous call to $unify$ on $T_i$. 
+If there has been no call to $unify$ on $T_i$ (\ie{} $T_i$ is a single-element class) $T_i$ is absent in $T'$.
+
+Given the nature of the expression resolution problem as backtracking search, caching and concurrency are both useful tools to decrease runtime. 
+However, both of these approaches may produce multiple distinct descendants of the same initial type environment, which have possibly been mutated in incompatible ways. 
+As such, to effectively employ either concurrency or caching, the type environment data structure must support an efficient method to check if two type environments are compatible and merge them if so. 
+$combine(T,T')$ attempts to merge an environment $T'$ into another environment $T$, producing $\top$ if successful or leaving $T$ in an invalid state and producing $\bot$ otherwise. 
+The invalid state of $T$ on failure is not important, given that a combination failure will result in the resolution algorithm backtracking to a different environment. 
+$combine$ proceeds by calls to $insert$, $add$, and $unify$ as needed, and can be roughly thought of as calling $unify$ on every pair of classes in $T$ that have variables $v'_{i,j}$ and $v'_{i,k}$ in the same class $T'_i$ in $T'$. 
+Like $unify$, $combine$ can always find a mutually-consistent partition of type variables into classes (in the extreme case, all type variables from $T$ and $T'$ in a single type class), but may fail due to inconsistent bounds on merged type classes. 
+
+Finally, the backtracking access patterns of the compiler can be exploited to reduce memory usage or runtime through use of an appropriately designed data structure. 
+The set of mutations to a type environment across the execution of the resolution algorithm produce an implicit tree of related environments, and the backtracking search typically focuses only on one leaf of the tree at once, or at most a small number of closely-related nodes as arguments to $combine$.
+As such, the ability to save and restore particular type environment states is useful, and supported by the $save(T) \rightarrow H$ and $backtrack(T, H)$ operations, which produce a handle for the current environment state and mutate an environment back to a previous state, respectively. 
+These operations can be naively implemented by a deep copy of $T$ into $H$ and vice versa, but have more efficient implementations in persistency-aware data structures.
+
+\section{Approaches}
+
+\subsection{Na\"{\i}ve}
+
+The type environment data structure used in Bilson's\cite{Bilson03} original implementation of \CFACC{} is a straightforward translation of the definitions in Section~\ref{env-defn-sec} to \CC{} code; a !TypeEnvironment! contains a list of !EqvClass! type equivalence classes, each of which contains the type bound information and a tree-based sorted set of type variables. 
+This approach has the benefit of being easy to understand and not imposing life-cycle or inheritance constraints on its use, but, as can be seen in Table~\ref{env-bounds-table}, does not support many of the desired operations with any particular efficiency.
+Some variations on this structure may improve performance somewhat; for instance, replacing the !EqvClass! variable storage with a hash-based set would reduce search and update times from $O(\log n)$ to amortized $O(1)$, while adding an index for the type variables in the entire environment would remove the need to check each type class individually to maintain the disjointness property. 
+These improvements do not change the fundamental issues with this data structure, however.
+
+\subsection{Incremental Inheritance}
+
+One more invasive modification to this data structure which I investigated is to support swifter combinations of closely-related environments in the backtracking tree by storing a reference to a \emph{parent} environment within each environment, and having that environment only store type classes which have been modified with respect to the parent. 
+This approach provides constant-time copying of environments, as a new environment simply consists of an empty list of type classes and a reference to its (logically identical) parent; since many type environments are no different than their parent, this speeds backtracking in this common case. 
+Since all mutations made to a child environment are by definition compatible with the parent environment, two descendants of a common ancestor environment can be combined by iteratively combining the changes made in one environment then that environment's parent until the common ancestor is reached, again re-using storage and reducing computation in many cases. 
+
+For this environment I also employed a lazily-generated index of type variables to their containing class, which could be in either the current environment or an ancestor. 
+Any mutation of a type class in an ancestor environment would cause that class to be copied into the current environment before mutation, as well as added to the index, ensuring that all local changes to the type environment are listed in its index.
+However, not adding type variables to the index until lookup or mutation preserves the constant-time environment copy operation in the common case in which the copy is not mutated from its parent during its life-cycle.
+
+This approach imposes some performance penalty on $combine$ if related environments are not properly linked together, as the entire environment needs to be combined rather than just the diff, but is correct as long as the ``null parent'' base case is properly handled. 
+The life-cycle issues are somewhat more complex, as many environments may descend from a common parent, and all of these need their parent to stay alive for purposes of lookup. 
+These issues can be solved by ``flattening'' parent nodes into their children before the parents leave scope, but given the tree structure of the inheritance graph it is more straightforward to store the parent nodes in reference-counted or otherwise automatically garbage-collected heap storage.
+
+\subsection{Union-Find} \label{env-union-find-approach}
+
+Given the nature of the classes of type variables as disjoint sets, another natural approach to implementing a type environment is the union-find disjoint set data structure\cite{Galler64}. 
+Union-find efficiently implements two operations over a partition of a collection of elements into disjoint sets; $find(x)$ locates the \emph{representative} of $x$, the element which canonically names its set, while $union(r, s)$ merges two sets represented by $r$ and $s$, respectively. 
+The union-find data structure is based on providing each element with a reference to its parent element, such that the root of a tree of elements is the representative of the set of elements contained in the tree. 
+$find$ is then implemented by a search up to the parent, generally combined with a \emph{path compression} step that links nodes more directly to their ancestors to speed up subsequent searches. 
+$union$ involves making the representative of one set a child of the representative of the other, generally employing a rank- or size-based heuristic to ensure that the tree remains somewhat balanced. 
+If both path compression and a balancing heuristic are employed, both $union$ and $find$ run in amortized $O(\alpha(n))$ worst-case time; this bound by the inverse Ackermann function is a small constant for all practical values of $n$.
+
+The union-find $find$ and $union$ operations have obvious applicability to the $find$ and $unify$ type environment operations in Table~\ref{env-op-table}, but the union-find data structure must be augmented to fully implement the type environment operations. 
+In particular, the type class bound cannot be easily included in the union-find data structure, as the requirement to make it the class representative breaks the balancing properties of $union$, and requires too-close integration of the type environment $unifyBound$ internal operation. 
+This issue can be solved by including a side map from class representatives to the type class bound. 
+If placeholder values are inserted in this map for type classes without bounds than this also has the useful property that the key set of the map provides an easily obtainable list of all the class representatives, a list which cannot be derived from the union-find data structure without a linear search for class representatives through all elements.
+
+\subsection{Union-Find with Classes} \label{env-union-find-classes-approach}
+
+Another type environment operation not supported directly by the union-find data structure is $report$, which lists the type variables in a given class, and similarly $split$, which reverts a $unify$ operation. 
+Since the union-find data structure stores only links from children to parents and not vice-versa, there is no way to reconstruct a class from one of its elements without a linear search over the entire data structure, with $find$ called on each element to check its membership in the class. 
+The situation is even worse for the $split$ operation, which would require extra information to maintain the order that each child was added to its parent node. 
+Unfortunately, the literature\cite{Tarjan84,Galil91,Patwary10} on union-find does not present a way to keep references to children without breaking the asymptotic time bounds of the algorithm; I have discovered a method to do so which, despite its simplicity, seems to be novel.
+
+\TODO{port figure from slideshow}
+
+The core idea of this ``union-find with classes'' data structure and algorithm is to keep the members of each class stored in a circularly-linked list. 
+Aho, Hopcroft, and Ullman also include a circularly-linked list in their 1974 textbook~\cite{Aho74}.
+However, the algorithm presented by Aho~\etal{} has an entirely flat class hierarchy, where all elements are direct children of the representative, giving constant-time $find$ at the cost of linear-time $union$ operations. 
+In my version, the list data structure does not affect the layout of the union-find tree, maintaining the same asymptotic bounds as union-find. 
+In more detail, each element is given a !next! pointer to another element in the same class; this !next! pointer initially points to the element itself. 
+When two classes are unified, the !next! pointers of the representatives of those classes are swapped, splicing the two circularly-linked lists together. 
+Importantly, though this approach requires an extra pointer per element, it does maintain the linear space bound of union-find, and because it only requires updating the two root nodes in $union$ it does not asymptotically increase runtime either. 
+The basic approach is compatible with all path-compression techniques, and allows the members of any class to be retrieved in time linear in the size of the class simply by following the !next! pointers from any element. 
+
+If the path-compression optimization is abandoned, union-find with classes also encodes a reversible history of all the $union$ operations applied to a given class. 
+Theorem~\ref{env-reverse-thm} demonstrates that the !next! pointer of the representative of a class always points to a leaf from the last-added subtree. 
+This property is sufficient to reverse the most-recent $union$ operation by finding the ancestor of that leaf that is an immediate child of the representative, breaking its parent link, and swapping the !next! pointers back\footnote{Union-by-size may be a more appropriate approach than union-by-rank in this instance, as adding two known sizes is a reversible operation, but the rank increment operation cannot be reliably reversed.}. 
+Once the $union$ operation has been reversed, Theorem~\ref{env-reverse-thm} still holds for the reduced class, and the process can be repeated recursively until the entire set is split into its component elements.
+
+\begin{theorem} \label{env-reverse-thm}
+The !next! pointer of a class representative in the union-find with classes algorithm without path compression points to a leaf from the most-recently-added subtree. 
+\end{theorem}
+
+\begin{proof}
+        By induction on the height of the tree. \\
+        \emph{Base case:} A height 1 tree by definition includes only a single item. In such a case, the representative's !next! pointer points to itself by construction, and the representative is the most-recently-added (and only) leaf in the tree. \\
+        \emph{Inductive case:} By construction, a tree $T$ of height greater than 1 has children of the root (representative) node that were representative nodes of classes merged by $union$. By definition, the most-recently-added subtree $T'$ has a smaller height than $T$, thus by the inductive hypothesis before the most-recent $union$ operation the !next! pointer of the root of $T'$ pointed to one of the leaf nodes of $T'$; by construction the !next! pointer of the root of $T$ points to this leaf after the $union$ operation.
+\end{proof}
+
+On its own, union-find, like the na\"{\i}ve approach, has no special constraints on life-cycle or inheritance, but it can be used as a building block in more sophisticated type environment data structures. 
+
+\subsection{Persistent Union-Find}
+
+Given the backtracking nature of the resolution algorithm discussed in Section~\ref{env-defn-sec}, the abilities to quickly switch between related versions of a type environment and to de-duplicate shared data between environments are both assets to performance. 
+Conchon and Filli\^{a}tre~\cite{Conchon07} present a persistent union-find data structure based on the persistent array of Baker~\cite{Baker78,Baker91}.
+
+\TODO{port figure from slideshow}
+
+In Baker's persistent array, an array reference contains either a pointer to the array or a pointer to an \emph{edit node}; these edit nodes contain an array index, the value in that index, and another array reference pointing either to the array or a different edit node. 
+In this manner, a tree of edits is formed, rooted at the actual array. 
+Read from the actual array at the root can be performed in constant time, as with a non-persistent array. 
+The persistent array can be mutated in constant time by directly modifying the underlying array, then replacing its array reference with an edit node containing the mutated index, the previous value at that index, and a reference to the mutated array. If the current array reference is not the root, mutation consists simply of constructing a new edit node encoding the change and referring to the current array reference.  
+The mutation algorithm at the root is in some sense a special case of the key operation on persistent arrays, $reroot$.
+
+A rerooting operation takes any array reference and makes it the root node of the array. 
+This is accomplished by tracing the path from some edit node to the root node of the array (always the underlying array), recursively applying the edits to the underlying array and replacing each edit node's successor with the inverse edit. 
+In this way, any previous state of the persistent array can be restored in time proportional to the number of edits to the current state of the array. 
+While $reroot$ does maintain the same value mapping in every version of the persistent array, the internal mutations it performs means that it is not thread-safe, and must be used behind a lock in a concurrent context. 
+Also, the root node with the actual array may in principle be anywhere in the tree, and does not provide information to report its leaf nodes, so some form of automatic garbage collection is generally required for the data structure. 
+Since the graph of edit nodes is tree-structured, reference counting approaches suffice for garbage collection; Conchon and Filli\^{a}tre~\cite{Conchon07} also observe that if the only $reroot$ operations are for backtracking then the tail of inverse edit nodes may be elided, suggesting the possibility of stack-based memory management. 
+
+While Conchon and Filli\^{a}tre~\cite{Conchon07} implement their persistent union-find data structure over a universe of integer elements in the fixed range $[1,N]$, the type environment problem needs more flexibility. 
+In particular, an arbitrary number of type variables must be added to the environment. 
+As such, a persistent hash table is a more suitable structure than a persistent array, providing the same expected asymptotic time bounds while allowing a dynamic number of elements. 
+Besides replacing the underlying array with a hash table, the other major change in this approach is to replace the two types of array references, !Array! and !Edit!, with four node types, !Table!,  !Edit!, !Add!, and !Remove!, where !Add! adds a new key-value pair, !Remove! removes a key, and !Edit! mutates an existing key-value pair.
+In this variant of \CFACC{}, this persistent hash table is used as the side map discussed in Section~\ref{env-union-find-approach} for class bounds.
+The actual union-find data structure is slightly modified from this approach, with a !Base! node containing the root union-find data structure, !Add! nodes adding new elements, !AddTo! nodes defining the union of two type classes, and !Remove! and !RemoveFrom! nodes as inverses of the previous two elements, for purposes of maintaining the edit list. 
+Making !AddTo! and !RemoveFrom! single nodes shortens the edit path for improved performance, while also providing semantic information missing from the raw array updates in Conchon and Filli\^{a}tre's data structure. 
+The single-node approach, does, however, break under most path-compression algorithms; !RemoveFrom! can be applied to the underlying data structure using the ``leaf of last union'' approach discussed in in Section~\ref{env-union-find-classes-approach}; this was judged an acceptable trade-off for the added semantic information and shortened paths.
+
+Maintaining explicit information on $union$ operations in the persistent union-find edit tree in the form of !AddTo! and !RemoveFrom! nodes exposes a new option for combining type environments. 
+If the type environments are part of the same edit tree, one environment $T'$ can be combined with another $T$ by only testing the edits on the path from $T'$ to $T$ in both the persistent union-find data structure describing the classes and the persistent hash table containing the class bounds. 
+This is generally more efficient than testing the compatibility of all type classes in $T'$, as only those that are actually different than those in $T$ must be considered.
+
+The procedure for $combine(T, T')$ based on edit paths is as follows: 
+The shared edit trees for classes and bindings are rerooted at $T$, and the path from $T'$ to $T$ is followed to create a list of actual edits. 
+By tracking the state of each element, redundant changes such as an !Edit! followed by an !Edit! can be reduced to their form in $T'$ by dropping the later (more like $T$) !Edit! for the same key; !Add! and !Remove! cancel similarly. 
+This procedure is repeated for both the class edit tree and the binding edit tree.
+When the list of net changes to the environment has been produced, the additive changes are applied to $T$. 
+For example, if a type class exists in $T'$ but not $T$, the corresponding !Add! edit will be applied to $T$, but in the reverse situation the !Remove! edit will not be applied to $T$, as the intention is to produce a new environment representing the union of the two sets of type classes; similarly, !AddTo! edits are applied to unify type-classes in $T$ that are united in $T'$, but !RemoveFrom! edits that split type classes are not. 
+The new environment, $T''$ can always be constructed with a consistent partitioning of type variables; in the extreme case, all variables from both $T$ and $T'$ will be united in a single type class in $T''$. 
+Where $combine$ can fail is in unifying the bound types; if any class in $T'$ has a class bound which does not unify with the merged class in $T''$ than $combine$ fails.
+
+\section{Analysis}
+
+In this section I present asymptotic analyses of the various approaches to a type environment data structure discussed in the previous section. 
+
+\begin{table}
+\caption[Type environment operation bounds]{Worst-case analysis of type environment operations. $n$ is the number of type classes, $m$ the maximum size of a type class, and $p$ the edit distance between two environments or a single environment and the empty environment; $u(n)$ captures the recursive cost of class unification.}
+\label{env-bounds-table}
+\centering
+\begin{tabular}{rllll}
+        \hline
+                                & \textbf{Na\"{\i}ve}   & \textbf{Incremental}  & \textbf{Union-Find}           & \textbf{U-F with Classes}             \\
+        \hline
+        $find$          & $O(n)$                                & $O(p)$                                & $O(\alpha(m))$                        & $O(\log m)$                                   \\
+        $report$        & $O(m)$                                & $O(m)$                                & $O(n \log m)$                         & $O(m)$                                                \\
+        $bound$         & $O(1)$                                & $O(1)$                                & $O(1)$                                        & $O(1)$                                                \\
+        $insert$        & $O(1)$                                & $O(1)$                                & $O(1)$                                        & $O(1)$                                                \\
+        $add$           & $O(1)$                                & $O(1)$                                & $O(1)$                                        & $O(1)$                                                \\
+        $bind$          & $O(1)$                                & $O(1)$                                & $O(1)$                                        & $O(1)$                                                \\
+        $unify$         & $O(m + u(n))$                 & $O(m + u(n))$                 & $O(\log m + u(n))$            & $O(\log m + u(n))$                    \\
+        $split$         & ---                                   & ---                                   & ---                                           & $O(\log m)$                                   \\
+        $combine$       & $O(nm \cdot u(n))$    & $O(pm \cdot u(n))$    & $O(n \log m \cdot u(n))$      & $O(p \log m \cdot u(n))$              \\
+        $save$          & $O(nm)$                               & $O(1)$                                & $O(nm)$                                       & $O(1)$                                                \\
+        $backtrack$     & $O(nm)$                               & $O(pm)$                               & $O(nm)$                                       & $O(p)$                                                \\
+        \hline
+\end{tabular}
+\end{table}
+
+% Future work: design multi-threaded version of C&F persistent map --- core idea is some sort of thread-boundary edit node

doc/user/Makefile

@@ -79 +79 @@
 ## Define the default recipes.
 
-${Build}:
+${Build} :
         mkdir -p ${Build}
 

doc/user/user.tex

@@ -11 +11 @@
 %% Created On       : Wed Apr  6 14:53:29 2016
 %% Last Modified By : Peter A. Buhr
-%% Last Modified On : Fri Aug 31 07:54:50 2018
-%% Update Count     : 3396
+%% Last Modified On : Tue Dec 11 23:19:26 2018
+%% Update Count     : 3400
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
@@ -178 +178 @@
 int main( void ) {
         int x = 0, y = 1, z = 2;
-        ®sout | x | y | z | endl;®§\indexc{sout}§
+        ®sout | x | y | z;®§\indexc{sout}§
 }
 \end{cfa}
@@ -513 +513 @@
 Floating exponentiation\index{exponentiation!floating} is performed using \Index{logarithm}s\index{exponentiation!logarithm}, so the base cannot be negative.
 \begin{cfa}
-sout | 2 ®\® 8u | 4 ®\® 3u | -4 ®\® 3u | 4 ®\® -3 | -4 ®\® -3 | 4.0 ®\® 2.1 | (1.0f+2.0fi) ®\® (3.0f+2.0fi) | endl;
+sout | 2 ®\® 8u | 4 ®\® 3u | -4 ®\® 3u | 4 ®\® -3 | -4 ®\® -3 | 4.0 ®\® 2.1 | (1.0f+2.0fi) ®\® (3.0f+2.0fi);
 256 64 -64 0.015625 -0.015625 18.3791736799526 0.264715-1.1922i
 \end{cfa}
@@ -547 +547 @@
 
 
-%\subsection{\texorpdfstring{\protect\lstinline@for@ Statement}{for Statement}}
-\subsection{\texorpdfstring{\LstKeywordStyle{for} Statement}{for Statement}}
+\subsection{Loop Control}
 
 The ©for©/©while©/©do-while© loop-control allows empty or simplified ranges.
@@ -557 +556 @@
 the down-to range ©-~=©\index{-~=@©-~=©} means inclusive range [N,M].
 ©0© is the implicit start value;
-©1© is the implicit increment value for an up-to range and ©-1© for an implicit down-to range.
+©1© is the implicit increment value.
+The up-to range uses ©+=© for increment;
+the down-to range uses ©-=© for decrement.
 The loop index is polymorphic in the type of the start value or comparison value when start is implicitly ©0©.
 \begin{cquote}
 \begin{tabular}{@{}ll|l@{}}
-\multicolumn{2}{c|}{for control} & \multicolumn{1}{c}{output} \\
+\multicolumn{2}{c|}{loop control} & \multicolumn{1}{c}{output} \\
 \hline
 \begin{cfa}
@@ -571 +572 @@
 for ( ®10® ) { sout | "A"; }
 for ( ®1 ~= 10 ~ 2® ) { sout | "B"; }
-for ( ®10 -~= 1 ~ -2® ) { sout | "C"; }
+for ( ®10 -~= 1 ~ 2® ) { sout | "C"; }
 for ( ®0.5 ~ 5.5® ) { sout | "D"; }
 for ( ®5.5 -~ 0.5® ) { sout | "E"; }
 for ( ®i; 10® ) { sout | i; }
 for ( ®i; 1 ~= 10 ~ 2® ) { sout | i; }
-for ( ®i; 10 -~= 1 ~ -2® ) { sout | i; }
+for ( ®i; 10 -~= 1 ~ 2® ) { sout | i; }
 for ( ®i; 0.5 ~ 5.5® ) { sout | i; }
 for ( ®i; 5.5 -~ 0.5® ) { sout | i; }
 for ( ®ui; 2u ~= 10u ~ 2u® ) { sout | ui; }
-for ( ®ui; 10u -~= 2u ~ -2u® ) { sout | ui; }
-int start = 3, comp = 10, inc = 2;
+for ( ®ui; 10u -~= 2u ~ 2u® ) { sout | ui; }
+enum { N = 10 };
+for ( ®N® ) { sout | "N"; }
+for ( ®i; N® ) { sout | i; }
+for ( ®i; N -~ 0® ) { sout | i; }
+const int start = 3, comp = 10, inc = 2;
 for ( ®i; start ~ comp ~ inc + 1® ) { sout | i; }
 \end{cfa}
 &
 \begin{cfa}
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-sout | endl;
-
-sout | endl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | "zero" | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl;
+sout | nl | nl;
+
+sout | nl;
+sout | nl;
+sout | nl | nl;
+
+sout | nl;
 \end{cfa}
 &
@@ -611 +620 @@
 empty
 empty
-
+zero
 A
 A A A A A A A A A A
@@ -625 +634 @@
 2 4 6 8 10
 10 8 6 4 2
+
+N N N N N N N N N N
+0 1 2 3 4 5 6 7 8 9
+10 9 8 7 6 5 4 3 2 1
 
 3 6 9
@@ -2446 +2459 @@
         int bar( int p ) {
                 ®i® += 1;                               §\C{// dependent on local variable}§
-                sout | ®i® | endl;
+                sout | ®i®;
         }
         return bar;                                     §\C{// undefined because of local dependence}§
@@ -2452 +2465 @@
 int main() {
         * [int]( int ) fp = foo();      §\C{// int (* fp)( int )}§
-        sout | fp( 3 ) | endl;
+        sout | fp( 3 );
 }
 \end{cfa}
@@ -3218 +3231 @@
 \begin{cfa}
 int x = 1, y = 2, z = 3;
-sout | x ®|® y ®|® z | endl;
+sout | x ®|® y ®|® z;
 \end{cfa}
 &
@@ -3239 +3252 @@
 \begin{cfa}
 [int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ];
-sout | t1 | t2 | endl;                                  §\C{// print tuples}§
+sout | t1 | t2;                                         §\C{// print tuples}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt]
@@ -3251 +3264 @@
 &
 \begin{cfa}
-sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
+sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2);
 \end{cfa}
 \\
@@ -3277 +3290 @@
 A separator does not appear at the start or end of a line.
 \begin{cfa}[belowskip=0pt]
-sout | 1 | 2 | 3 | endl;
+sout | 1 | 2 | 3;
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3286 +3299 @@
 A separator does not appear before or after a character literal or variable.
 \begin{cfa}
-sout | '1' | '2' | '3' | endl;
+sout | '1' | '2' | '3';
 123
 \end{cfa}
@@ -3293 +3306 @@
 A separator does not appear before or after a null (empty) C string.
 \begin{cfa}
-sout | 1 | "" | 2 | "" | 3 | endl;
+sout | 1 | "" | 2 | "" | 3;
 123
 \end{cfa}
@@ -3303 +3316 @@
 \begin{cfa}[mathescape=off]
 sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥"
-                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;
+                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10;
 \end{cfa}
 %$
@@ -3317 +3330 @@
 \begin{cfa}[belowskip=0pt]
 sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x"
-                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;
+                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x";
 \end{cfa}
 \begin{cfa}[basicstyle=\tt,showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3327 +3340 @@
 A seperator does not appear before or after a C string begining/ending with the \Index*{ASCII} quote or whitespace characters: \lstinline[basicstyle=\tt,showspaces=true]@`'": \t\v\f\r\n@
 \begin{cfa}[belowskip=0pt]
-sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;
+sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx";
 \end{cfa}
 \begin{cfa}[basicstyle=\tt,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt]
@@ -3336 +3349 @@
 If a space is desired before or after one of the special string start/end characters, simply insert a space.
 \begin{cfa}[belowskip=0pt]
-sout | "x (§\color{red}\texttt{\textvisiblespace}§" | 1 | "§\color{red}\texttt{\textvisiblespace}§) x" | 2 | "§\color{red}\texttt{\textvisiblespace}§, x" | 3 | "§\color{red}\texttt{\textvisiblespace}§:x:§\color{red}\texttt{\textvisiblespace}§" | 4 | endl;
+sout | "x (§\color{red}\texttt{\textvisiblespace}§" | 1 | "§\color{red}\texttt{\textvisiblespace}§) x" | 2 | "§\color{red}\texttt{\textvisiblespace}§, x" | 3 | "§\color{red}\texttt{\textvisiblespace}§:x:§\color{red}\texttt{\textvisiblespace}§" | 4;
 \end{cfa}
 \begin{cfa}[basicstyle=\tt,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt]
@@ -3353 +3366 @@
 \begin{cfa}[mathescape=off,belowskip=0pt]
 sepSet( sout, ", $" );                                          §\C{// set separator from " " to ", \$"}§
-sout | 1 | 2 | 3 | " \"" | ®sep® | "\"" | endl;
+sout | 1 | 2 | 3 | " \"" | ®sep® | "\"";
 \end{cfa}
 %$
@@ -3362 +3375 @@
 \begin{cfa}[belowskip=0pt]
 sepSet( sout, " " );                                            §\C{// reset separator to " "}§
-sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\"" | endl;
+sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\"";
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt]
@@ -3372 +3385 @@
 strcpy( store, sepGet( sout ) );                          §\C{// copy current separator}§
 sepSet( sout, "_" );                                            §\C{// change separator to underscore}§
-sout | 1 | 2 | 3 | endl;
+sout | 1 | 2 | 3;
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3379 +3392 @@
 \begin{cfa}[belowskip=0pt]
 sepSet( sout, store );                                          §\C{// change separator back to original}§
-sout | 1 | 2 | 3 | endl;
+sout | 1 | 2 | 3;
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt]
@@ -3390 +3403 @@
 \begin{cfa}[belowskip=0pt]
 sepSetTuple( sout, " " );                                       §\C{// set tuple separator from ", " to " "}§
-sout | t1 | t2 | " \"" | ®sepTuple® | "\"" | endl;
+sout | t1 | t2 | " \"" | ®sepTuple® | "\"";
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt]
@@ -3397 +3410 @@
 \begin{cfa}[belowskip=0pt]
 sepSetTuple( sout, ", " );                                      §\C{// reset tuple separator to ", "}§
-sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\"" | endl;
+sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\"";
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt]
@@ -3407 +3420 @@
 Manipulators \Indexc{sepDisable}\index{manipulator!sepDisable@©sepDisable©} and \Indexc{sepEnable}\index{manipulator!sepEnable@©sepEnable©} \emph{globally} toggle printing the separator, \ie the seperator is adjusted with respect to all subsequent printed items.
 \begin{cfa}[belowskip=0pt]
-sout | sepDisable | 1 | 2 | 3 | endl;           §\C{// globally turn off implicit separator}§
+sout | sepDisable | 1 | 2 | 3;                  §\C{// globally turn off implicit separator}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3413 +3426 @@
 \end{cfa}
 \begin{cfa}[belowskip=0pt]
-sout | sepEnable | 1 | 2 | 3 | endl;            §\C{// globally turn on implicit separator}§
+sout | sepEnable | 1 | 2 | 3;           §\C{// globally turn on implicit separator}§
 \end{cfa}
 \begin{cfa}[mathescape=off,showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3422 +3435 @@
 Manipulators \Indexc{sepOn}\index{manipulator!sepOn@©sepOn©} and \Indexc{sepOff}\index{manipulator!sepOff@©sepOff©} \emph{locally} toggle printing the separator, \ie the seperator is adjusted only with respect to the next printed item.
 \begin{cfa}[belowskip=0pt]
-sout | 1 | sepOff | 2 | 3 | endl;                       §\C{// locally turn off implicit separator}§
+sout | 1 | sepOff | 2 | 3;                      §\C{// locally turn off implicit separator}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3428 +3441 @@
 \end{cfa}
 \begin{cfa}[belowskip=0pt]
-sout | sepDisable | 1 | sepOn | 2 | 3 | endl; §\C{// locally turn on implicit separator}§
+sout | sepDisable | 1 | sepOn | 2 | 3; §\C{// locally turn on implicit separator}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3435 +3448 @@
 The tuple separator also responses to being turned on and off.
 \begin{cfa}[belowskip=0pt]
-sout | t1 | sepOff | t2 | endl;                         §\C{// locally turn on/off implicit separator}§
+sout | t1 | sepOff | t2;                                §\C{// locally turn on/off implicit separator}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3443 +3456 @@
 use ©sep© to accomplish this functionality.
 \begin{cfa}[belowskip=0pt]
-sout | sepOn | 1 | 2 | 3 | sepOn | endl ;       §\C{// sepOn does nothing at start/end of line}§
+sout | sepOn | 1 | 2 | 3 | sepOn;       §\C{// sepOn does nothing at start/end of line}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3449 +3462 @@
 \end{cfa}
 \begin{cfa}[belowskip=0pt]
-sout | sep | 1 | 2 | 3 | sep | endl ;           §\C{// use sep to print separator at start/end of line}§
+sout | sep | 1 | 2 | 3 | sep ;          §\C{// use sep to print separator at start/end of line}§
 \end{cfa}
 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt]
@@ -3462 +3475 @@
 int main( void ) {
         int x = 1, y = 2, z = 3;
-        sout | x | y | z | endl;
+        sout | x | y | z;
         [int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ];
-        sout | t1 | t2 | endl;                                          // print tuples
-        sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;
-        sout | 1 | 2 | 3 | endl;
-        sout | '1' | '2' | '3' | endl;
-        sout | 1 | "" | 2 | "" | 3 | endl;
+        sout | t1 | t2;                                         // print tuples
+        sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2);
+        sout | 1 | 2 | 3;
+        sout | '1' | '2' | '3';
+        sout | 1 | "" | 2 | "" | 3;
         sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥"
-                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;
+                | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10;
         sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x"
-                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;
-        sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;
-        sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4 | endl;
+                | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x";
+        sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx";
+        sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4;
 
         sepSet( sout, ", $" );                                          // set separator from " " to ", $"
-        sout | 1 | 2 | 3 | " \"" | sep | "\"" | endl;
+        sout | 1 | 2 | 3 | " \"" | sep | "\"";
         sepSet( sout, " " );                                            // reset separator to " "
-        sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\"" | endl;
+        sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\"";
 
         char store[sepSize];
         strcpy( store, sepGet( sout ) );
         sepSet( sout, "_" );
-        sout | 1 | 2 | 3 | endl;
+        sout | 1 | 2 | 3;
         sepSet( sout, store );
-        sout | 1 | 2 | 3 | endl;
+        sout | 1 | 2 | 3;
 
         sepSetTuple( sout, " " );                                       // set tuple separator from ", " to " "
-        sout | t1 | t2 | " \"" | sepTuple | "\"" | endl;
+        sout | t1 | t2 | " \"" | sepTuple | "\"";
         sepSetTuple( sout, ", " );                                      // reset tuple separator to ", "
-        sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\"" | endl;
-
-        sout | sepDisable | 1 | 2 | 3 | endl;           // globally turn off implicit separator
-        sout | sepEnable | 1 | 2 | 3 | endl;            // globally turn on implicit separator
-
-        sout | 1 | sepOff | 2 | 3 | endl;                       // locally turn on implicit separator
-        sout | sepDisable | 1 | sepOn | 2 | 3 | endl; // globally turn off implicit separator
+        sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\"";
+
+        sout | sepDisable | 1 | 2 | 3;          // globally turn off implicit separator
+        sout | sepEnable | 1 | 2 | 3;           // globally turn on implicit separator
+
+        sout | 1 | sepOff | 2 | 3;                      // locally turn on implicit separator
+        sout | sepDisable | 1 | sepOn | 2 | 3; // globally turn off implicit separator
         sout | sepEnable;
-        sout | t1 | sepOff | t2 | endl;                         // locally turn on/off implicit separator
-
-        sout | sepOn | 1 | 2 | 3 | sepOn | endl ;       // sepOn does nothing at start/end of line
-        sout | sep | 1 | 2 | 3 | sep | endl ;           // use sep to print separator at start/end of line
+        sout | t1 | sepOff | t2;                                // locally turn on/off implicit separator
+
+        sout | sepOn | 1 | 2 | 3 | sepOn ;      // sepOn does nothing at start/end of line
+        sout | sep | 1 | 2 | 3 | sep ;          // use sep to print separator at start/end of line
 }
 
@@ -4167 +4180 @@
         Fibonacci f1, f2;
         for ( int i = 1; i <= 10; i += 1 ) {
-                sout | next( &f1 ) | ' ' | next( &f2 ) | endl;
+                sout | next( &f1 ) | ' ' | next( &f2 );
         } // for
 }
@@ -4233 +4246 @@
                 MyThread f[4];
         }
-        sout | global.value | endl;
+        sout | global.value;
 }
 \end{cfa}
@@ -4311 +4324 @@
 void main( First * this ) {
         for ( int i = 0; i < 10; i += 1 ) {
-                sout | "First : Suspend No." | i + 1 | endl;
+                sout | "First : Suspend No." | i + 1;
                 yield();
         }
@@ -4320 +4333 @@
         wait( this->lock );
         for ( int i = 0; i < 10; i += 1 ) {
-                sout | "Second : Suspend No." | i + 1 | endl;
+                sout | "Second : Suspend No." | i + 1;
                 yield();
         }
@@ -4327 +4340 @@
 int main( void ) {
         signal_once lock;
-        sout | "User main begin" | endl;
+        sout | "User main begin";
         {
                 processor p;
@@ -4335 +4348 @@
                 }
         }
-        sout | "User main end" | endl;
+        sout | "User main end";
 }
 \end{cfa}
@@ -5032 +5045 @@
 void ?{}( Line * l ) {
         l->lnth = 0.0;
-        sout | "default" | endl;
+        sout | "default";
 }
 
@@ -5039 +5052 @@
 void ?{}( Line * l, float lnth ) {
         l->lnth = lnth;
-        sout | "lnth" | l->lnth | endl;
+        sout | "lnth" | l->lnth;
 
 }
@@ -5045 +5058 @@
 // destructor
 void ^?() {
-        sout | "destroyed" | endl;
+        sout | "destroyed";
         l.lnth = 0.0;
 }
@@ -5791 +5804 @@
 In particular, output of ©char© variable now print a character rather than the decimal ASCII value of the character.
 \begin{cfa}
-sout | 'x' | " " | (int)'x' | endl;
+sout | 'x' | " " | (int)'x';
 x 120
 \end{cfa}
@@ -7021 +7034 @@
 #include <gmp>§\indexc{gmp}§
 int main( void ) {
-        sout | "Factorial Numbers" | endl;
+        sout | "Factorial Numbers";
         Int fact = 1;
 
-        sout | 0 | fact | endl;
+        sout | 0 | fact;
         for ( unsigned int i = 1; i <= 40; i += 1 ) {
                 fact *= i;
-                sout | i | fact | endl;
+                sout | i | fact;
         }
 }