- Timestamp:
- Dec 12, 2018, 3:52:19 PM (5 years ago)
- 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
- Children:
- 1b8f13f0
- Parents:
- cdc02f2 (diff), 85acec94 (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. - Location:
- doc
- Files:
-
- 6 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/bibliography/pl.bib
rcdc02f2 r515a037 21 21 % toplas: ACM Trans. on Prog. Lang. & Sys. 22 22 % tcs: Theoretical Computer Science 23 @string{ieeepds="IEEE Transactions on Parallel and Distributed Systems"} 24 % @string{ieeepds="IEEE Trans. Parallel Distrib. Syst."} 25 @string{ieeese="IEEE Transactions on Software Engineering"} 26 % @string{ieeese="IEEE Trans. Softw. Eng."} 27 @string{spe="Software---\-Practice and Experience"} 28 % @string{spe="Softw. Pract. Exp."} 29 @string{ccpe="Concurrency and Computation: Practice and Experience"} 30 % @string{ccpe="Concurrency Comput: Pract Experience"} 31 @string{sigplan="SIGPLAN Notices"} 32 % @string{sigplan="SIGPLAN Not."} 33 @string{joop="Journal of Object-Oriented Programming"} 34 % @string{joop="J. of Object-Oriented Program."} 23 24 string{ieeepds="IEEE Transactions on Parallel and Distributed Systems"} 25 @string{ieeepds="IEEE Trans. Parallel Distrib. Syst."} 26 string{ieeese="IEEE Transactions on Software Engineering"} 27 @string{ieeese="IEEE Trans. Softw. Eng."} 28 string{spe="Software---\-Practice and Experience"} 29 @string{spe="Softw. Pract. Exper."} 30 string{ccpe="Concurrency and Computation: Practice and Experience"} 31 @string{ccpe="Concurrency Comput.: Pract. Exper."} 32 string{sigplan="SIGPLAN Notices"} 33 @string{sigplan="SIGPLAN Not."} 34 string{joop="Journal of Object-Oriented Programming"} 35 @string{joop="J. of Object-Oriented Program."} 35 36 @string{popl="Conference Record of the ACM Symposium on Principles of Programming Languages"} 36 37 @string{osr="Operating Systems Review"} 37 38 @string{pldi="Programming Language Design and Implementation"} 38 39 @string{toplas="Transactions on Programming Languages and Systems"} 39 @string{mathann="Mathematische Annalen"}40 %@string{mathann="Math. Ann."}40 string{mathann="Mathematische Annalen"} 41 @string{mathann="Math. Ann."} 41 42 42 43 % A … … 566 567 } 567 568 569 @inproceedings {Qin18, 570 author = {Henry Qin and Qian Li and Jacqueline Speiser and Peter Kraft and John Ousterhout}, 571 title = {Arachne: Core-Aware Thread Management}, 572 booktitle = {13th {USENIX} Symp. on Oper. Sys. Design and Impl. ({OSDI} 18)}, 573 year = {2018}, 574 address = {Carlsbad, CA}, 575 pages = {145-160}, 576 publisher = {{USENIX} Association}, 577 note = {\href{https://www.usenix.org/conference/osdi18/presentation/qin}{https://\-www.usenix.org/\-conference/\-osdi18/\-presentation/\-qin}}, 578 } 579 568 580 @article{Kessels82, 569 581 keywords = {concurrency, critical section}, … … 653 665 author = {Joung, Yuh-Jzer}, 654 666 title = {Asynchronous group mutual exclusion}, 655 journal = {Distributed Computing}, 667 journal = {Dist. Comput.}, 668 optjournal = {Distributed Computing}, 656 669 year = {2000}, 657 670 month = {Nov}, … … 796 809 time computable inheritance hierarchy. 797 810 }, 798 comment 811 comment = { 799 812 Classes are predicates; if object {\tt o} is in class {\tt C}, then 800 813 {\tt C} is true of {\tt o}. Classes are combined with {\tt :AND}, … … 950 963 951 964 @article{Moss18, 952 keywords = {type systems, tuples, Cforall},965 keywords = {type systems, polymorphism, tuples, Cforall}, 953 966 contributer = {pabuhr@plg}, 954 967 author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, 955 968 title = {\textsf{C}$\mathbf{\forall}$ : Adding Modern Programming Language Features to C}, 969 journal = spe, 970 volume = 48, 971 number = 12, 972 month = dec, 956 973 year = 2018, 957 month = aug, 958 journal = spe, 974 pages = {2111-2146}, 959 975 note = {\href{http://dx.doi.org/10.1002/spe.2624}{http://\-dx.doi.org/\-10.1002/\-spe.2624}}, 960 976 } … … 989 1005 journal = {Dr. Dobb's Journal of Software Tools}, 990 1006 year = 1989, 991 month = feb, volume = 14, number = 2, pages = {45-51}, 1007 month = feb, 1008 volume = 14, 1009 number = 2, 1010 pages = {45-51}, 992 1011 comment = { 993 1012 A light-weight multitasking kernel for MS-DOS. A task\_control … … 1507 1526 } 1508 1527 1509 @ techreport{uC++,1528 @manual{uC++, 1510 1529 keywords = {C++, concurrency, light-weight process, shared memory}, 1511 1530 contributer = {pabuhr@plg}, 1531 key = {uC++}, 1512 1532 author = {Peter A. Buhr}, 1513 1533 title = {$\mu${C}{\kern-.1em\hbox{\large\texttt{+\kern-.25em+}}} Annotated Reference Manual, Version 7.0.0}, 1514 institution = {School of Computer Science, University of Waterloo}, 1515 address = {Waterloo, Ontario, Canada, N2L 3G1}, 1516 month = dec, 1517 year = 2017, 1534 organization= {University of Waterloo}, 1535 month = sep, 1536 year = 2018, 1518 1537 note = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-$\sim$usystem/\-pub/\-uSystem/uC++.pdf}}, 1519 1538 } … … 1586 1605 author = {Sun, Xianda}, 1587 1606 title = {Concurrent High-performance Persistent Hash Table In {J}ava}, 1588 school = {School of Computer Sc ience, University of Waterloo},1607 school = {School of Computer Sc., University of Waterloo}, 1589 1608 year = 2015, 1590 1609 optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, … … 1936 1955 note = {Svensk Standard SS 63 61 14}, 1937 1956 year = 1987, 1938 abstract = { 1939 Standard for the programming language SIMULA. Written in English. 1940 } 1957 abstract = {Standard for the programming language SIMULA. Written in English.} 1958 } 1959 1960 @article{Galil91, 1961 keywords = {union-find}, 1962 contributer = {a3moss@uwaterloo.ca}, 1963 title = {Data structures and algorithms for disjoint set union problems}, 1964 author = {Galil, Zvi and Italiano, Giuseppe F}, 1965 journal = {ACM Computing Surveys (CSUR)}, 1966 volume = 23, 1967 number = 3, 1968 pages = {319--344}, 1969 year = 1991, 1970 publisher = {ACM}, 1941 1971 } 1942 1972 … … 2078 2108 year = {1998}, 2079 2109 pages = {393-407}, 2110 } 2111 2112 @book{Aho74, 2113 keywords = {algorithms, textbook, union-find}, 2114 contributer = {a3moss@uwaterloo.ca}, 2115 title = {The Design and Analysis of Computer Algorithms}, 2116 author = {Aho, Alfred V and Hopcroft, John E and Ullman, Jeffrey D}, 2117 year = {1974}, 2118 publisher = {Addison-Wesley}, 2119 address = {Reading, MA, USA} 2080 2120 } 2081 2121 … … 2880 2920 } 2881 2921 2922 @inproceedings{Patwary10, 2923 keywords = {union-find}, 2924 contributer = {a3moss@uwaterloo.ca}, 2925 author = {Patwary, Md. Mostofa Ali and Blair, Jean and Manne, Fredrik}, 2926 editor = {Festa, Paola}, 2927 title = {Experiments on Union-Find Algorithms for the Disjoint-Set Data Structure}, 2928 booktitle = {Experimental Algorithms}, 2929 year = 2010, 2930 publisher = {Springer Berlin Heidelberg}, 2931 address = {Berlin, Heidelberg}, 2932 pages = {411--423}, 2933 isbn = {978-3-642-13193-6} 2934 } 2935 2882 2936 % F 2883 2937 … … 3223 3277 keywords = {Go programming language}, 3224 3278 contributer = {pabuhr@plg}, 3279 author = {Robert Griesemer and Rob Pike and Ken Thompson}, 3225 3280 title = {{Go} Programming Language}, 3226 author = {Robert Griesemer and Rob Pike and Ken Thompson},3227 3281 organization= {Google}, 3228 3282 year = 2009, … … 3416 3470 month = sep, 3417 3471 publisher = {John Wiley \& Sons}, 3418 note = {\href{https://doi -org.proxy.lib.uwaterloo.ca/10.1002/cpe.4475}{https://\-doi-org.proxy.lib.uwaterloo.ca/\-10.1002/\-cpe.4475}},3472 note = {\href{https://doi.org/10.1002/cpe.4475}{https://\-doi.org/\-10.1002/\-cpe.4475}}, 3419 3473 } 3420 3474 … … 3554 3608 publisher = {ACM Press}, 3555 3609 address = {New York, NY, USA}, 3610 } 3611 3612 @article{Galler64, 3613 keywords = {union-find, original}, 3614 contributer = {a3moss@uwaterloo.ca}, 3615 title = {An improved equivalence algorithm}, 3616 author = {Galler, Bernard A and Fisher, Michael J}, 3617 journal = {Communications of the ACM}, 3618 volume = {7}, 3619 number = {5}, 3620 pages = {301--303}, 3621 year = {1964}, 3622 publisher = {ACM} 3556 3623 } 3557 3624 … … 3898 3965 author = {Peter A. Buhr and Martin Karsten and Jun Shih}, 3899 3966 title = {{\small\textsf{KDB}}: A Multi-threaded Debugger for Multi-threaded Applications}, 3900 booktitle = {Proc eedings of SPDT'96: SIGMETRICS Symposiumon Parallel and Distributed Tools},3967 booktitle = {Proc. of SPDT'96: SIGMETRICS Symp. on Parallel and Distributed Tools}, 3901 3968 publisher = {ACM Press}, 3902 3969 address = {Philadelphia, Pennsylvania, U.S.A.}, … … 5389 5456 } 5390 5457 5458 @inproceedings{Conchon07, 5459 keywords = {persistent array, union-find}, 5460 contributer = {a3moss@uwaterloo.ca}, 5461 title = {A persistent union-find data structure}, 5462 author = {Conchon, Sylvain and Filli{\^a}tre, Jean-Christophe}, 5463 booktitle = {Proceedings of the 2007 workshop on Workshop on ML}, 5464 pages = {37--46}, 5465 year = {2007}, 5466 organization= {ACM} 5467 } 5468 5391 5469 @article{poly, 5392 5470 keywords = {Poly, Standard ML, Russell, persistence}, … … 5603 5681 author = {Peter A. Buhr and Robert Denda}, 5604 5682 title = {{$\mu$Profiler} : Profiling User-Level Threads in a Shared-Memory Programming Environment}, 5605 booktitle = {Proc eedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE'98)},5683 booktitle = {Proc. of 2nd Inter. Symp. on Computing in Object-Oriented Parallel Environments}, 5606 5684 series = {Lecture Notes in Computer Science}, 5607 5685 publisher = {Springer-Verlag}, … … 5974 6052 issn = {0164-0925}, 5975 6053 pages = {429-475}, 5976 url = {http://doi.acm.org .proxy.lib.uwaterloo.ca/10.1145/1133651.1133653},6054 url = {http://doi.acm.org/10.1145/1133651.1133653}, 5977 6055 doi = {10.1145/1133651.1133653}, 5978 6056 acmid = {1133653}, … … 6241 6319 contributer = {pabuhr@plg}, 6242 6320 key = {Rust}, 6243 title = { The{R}ust Programming Language},6244 address = {TheRust Project Developers},6321 title = {{R}ust Programming Language}, 6322 optaddress = {Rust Project Developers}, 6245 6323 year = 2015, 6246 6324 note = {\href{https://doc.rust-lang.org/reference.html}{https://\-doc.rust-lang\-.org/\-reference.html}}, … … 6308 6386 publisher = {Springer}, 6309 6387 note = {Lecture Notes in Computer Science v. 173}, 6388 } 6389 6390 @article{Baker78, 6391 keywords = {Algol display, FUNARG's, Lisp 1.5, deep binding, environment trees, multiprogramming, shallow binding}, 6392 contributer = {a3moss@uwaterloo.ca}, 6393 author = {Baker,Jr., Henry G.}, 6394 title = {Shallow Binding in Lisp 1.5}, 6395 journal = {Commun. ACM}, 6396 issue_date = {July 1978}, 6397 volume = 21, 6398 number = 7, 6399 month = jul, 6400 year = 1978, 6401 issn = {0001-0782}, 6402 pages = {565--569}, 6403 numpages = {5}, 6404 url = {http://doi.acm.org/10.1145/359545.359566}, 6405 doi = {10.1145/359545.359566}, 6406 acmid = {359566}, 6407 publisher = {ACM}, 6408 address = {New York, NY, USA} 6409 } 6410 6411 @article{Baker91, 6412 keywords = {shallow binding, functional arrays}, 6413 contributer = {a3moss@uwaterloo.ca}, 6414 author = {Baker, Henry G.}, 6415 title = {Shallow Binding Makes Functional Arrays Fast}, 6416 journal = {SIGPLAN Not.}, 6417 issue_date = {Aug. 1991}, 6418 volume = 26, 6419 number = 8, 6420 month = aug, 6421 year = 1991, 6422 issn = {0362-1340}, 6423 pages = {145--147}, 6424 numpages = {3}, 6425 url = {http://doi.acm.org/10.1145/122598.122614}, 6426 doi = {10.1145/122598.122614}, 6427 acmid = {122614}, 6428 publisher = {ACM}, 6429 address = {New York, NY, USA}, 6310 6430 } 6311 6431 … … 7476 7596 } 7477 7597 7598 @article{Tarjan84, 7599 keywords = {union-find}, 7600 contributer = {a3moss@uwaterloo.ca}, 7601 author = {Tarjan, Robert E. and van Leeuwen, Jan}, 7602 title = {Worst-case Analysis of Set Union Algorithms}, 7603 journal = {J. ACM}, 7604 issue_date = {April 1984}, 7605 volume = 31, 7606 number = 2, 7607 month = mar, 7608 year = 1984, 7609 issn = {0004-5411}, 7610 pages = {245--281}, 7611 numpages = {37}, 7612 url = {http://doi.acm.org/10.1145/62.2160}, 7613 doi = {10.1145/62.2160}, 7614 acmid = {2160}, 7615 publisher = {ACM}, 7616 address = {New York, NY, USA}, 7617 } 7618 7478 7619 % X 7479 7620 -
doc/papers/concurrency/Paper.tex
rcdc02f2 r515a037 686 686 Fib f1, f2; 687 687 for ( int i = 1; i <= 10; i += 1 ) { 688 sout | next( f1 ) | next( f2 ) | endl;688 sout | next( f1 ) | next( f2 ); 689 689 } 690 690 } … … 772 772 sout | " "; // separator 773 773 } 774 sout | endl;774 sout | nl; 775 775 } 776 776 } 777 777 void ?{}( Format & fmt ) { `resume( fmt );` } 778 778 void ^?{}( Format & fmt ) with( fmt ) { 779 if ( g != 0 || b != 0 ) sout | endl;779 if ( g != 0 || b != 0 ) sout | nl; 780 780 } 781 781 void format( Format & fmt ) { … … 855 855 for ( int i = 0; i < N; i += 1 ) { 856 856 int p1 = random( 100 ), p2 = random( 100 ); 857 sout | p1 | " " | p2 | endl;857 sout | p1 | " " | p2; 858 858 int status = delivery( c, p1, p2 ); 859 sout | " $" | money | endl | status | endl;859 sout | " $" | money | nl | status; 860 860 receipt += 1; 861 861 } 862 862 stop( c ); 863 sout | "prod stops" | endl;863 sout | "prod stops"; 864 864 } 865 865 int payment( Prod & prod, int money ) { … … 895 895 int money = 1, receipt; 896 896 for ( ; ! done; ) { 897 sout | p1 | " " | p2 | endl | " $" | money | endl;897 sout | p1 | " " | p2 | nl | " $" | money; 898 898 status += 1; 899 899 receipt = payment( p, money ); 900 sout | " #" | receipt | endl;900 sout | " #" | receipt; 901 901 money += 1; 902 902 } 903 sout | "cons stops" | endl;903 sout | "cons stops"; 904 904 } 905 905 int delivery( Cons & cons, int p1, int p2 ) { … … 1099 1099 1100 1100 void main(foo & this) { 1101 sout | "Hello World!" | endl;1101 sout | "Hello World!"; 1102 1102 } 1103 1103 \end{cfa} … … 1124 1124 1125 1125 void hello(/*unused*/ int) { 1126 sout | "Hello World!" | endl;1126 sout | "Hello World!"; 1127 1127 } 1128 1128 … … 1141 1141 thread World {}; 1142 1142 void main( World & this ) { 1143 sout | "World!" | endl;1143 sout | "World!"; 1144 1144 } 1145 1145 int main() { 1146 1146 World w`[10]`; $\C{// implicit forks after creation}$ 1147 sout | "Hello " | endl; $\C{// "Hello " and 10 "World!" printed concurrently}$1147 sout | "Hello "; $\C{// "Hello " and 10 "World!" printed concurrently}$ 1148 1148 } $\C{// implicit joins before destruction}$ 1149 1149 \end{cfa} … … 1193 1193 total += subtotals[r]; $\C{// total subtotal}$ 1194 1194 } 1195 sout | total | endl;1195 sout | total; 1196 1196 } 1197 1197 \end{cfa} … … 2192 2192 BENCH( 2193 2193 for ( size_t i = 0; i < N; i += 1 ) { @resume( c );@ } ) 2194 sout | result`ns | endl;2194 sout | result`ns; 2195 2195 } 2196 2196 \end{cfa} … … 2205 2205 BENCH( 2206 2206 for ( size_t i = 0; i < N; i += 1 ) { @yield();@ } ) 2207 sout | result`ns | endl;2207 sout | result`ns; 2208 2208 } 2209 2209 \end{cfa} … … 2244 2244 int main() { 2245 2245 BENCH( for( size_t i = 0; i < N; i += 1 ) { @do_call( m1/*, m2, m3, m4*/ );@ } ) 2246 sout | result`ns | endl;2246 sout | result`ns; 2247 2247 } 2248 2248 \end{cfa} … … 2305 2305 BENCH( for ( size_t i = 0; i < N; i += 1 ) { @wait( c );@ } ); 2306 2306 go = 0; // stop other thread 2307 sout | result`ns | endl;2307 sout | result`ns; 2308 2308 } 2309 2309 int main() { … … 2356 2356 BENCH( for ( size_t i = 0; i < N; i += 1 ) { @waitfor( do_call, m );@ } ) 2357 2357 go = 0; // stop other thread 2358 sout | result`ns | endl;2358 sout | result`ns; 2359 2359 } 2360 2360 int main() { … … 2391 2391 int main() { 2392 2392 BENCH( for ( size_t i = 0; i < N; i += 1 ) { @MyThread m;@ } ) 2393 sout | result`ns | endl;2393 sout | result`ns; 2394 2394 } 2395 2395 \end{cfa} -
doc/proposals/flags.md
rcdc02f2 r515a037 60 60 ``` 61 61 FunFlags f = some_val(); 62 if ( f ) { sout | "f has some flag(s) set" | endl; }63 if ( f & FOO ) { sout | "f has FOO set" | endl; }62 if ( f ) { sout | "f has some flag(s) set"; } 63 if ( f & FOO ) { sout | "f has FOO set"; } 64 64 f |= FOO; // set FOO 65 65 f -= FOO; // unset FOO … … 88 88 ``` 89 89 FunFlags f = some_val(); 90 if ( f.FOO ) { sout | "f has FOO set" | endl; }90 if ( f.FOO ) { sout | "f has FOO set"; } 91 91 f.FOO = true; // set FOO 92 92 f.FOO = false; // unset FOO -
doc/theses/aaron_moss_PhD/phd/thesis.tex
rcdc02f2 r515a037 23 23 % \usepackage[pdftex]{graphicx} % For including graphics N.B. pdftex graphics driver 24 24 \usepackage{graphicx} 25 26 \usepackage{amsthm} % for theorem environment 27 \newtheorem{theorem}{Theorem} 25 28 26 29 \usepackage{footmisc} % for double refs to the same footnote -
doc/theses/aaron_moss_PhD/phd/type-environment.tex
rcdc02f2 r515a037 5 5 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. 6 6 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. 7 In this chapter I discuss and empirically compare a number of type environment data structure variants, including some novel variations on the union-find\cit {} data structure introduced in this thesis.8 9 \section{Definitions} 7 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. 8 9 \section{Definitions} \label{env-defn-sec} 10 10 11 11 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|}}$. … … 24 24 $add(T_i, v_{i,j})$ & & Add variable to class \\ 25 25 $bind(T_i, b_i)$ & & Set or update class bound \\ 26 $remove(T, T_i)$ & & Remove class from environment \\27 26 $unify(T, T_i, T_j)$ & $\rightarrow \top | \bot$ & Combine two type classes \\ 27 $split(T, T_i)$ & $\rightarrow T'$ & Revert the last $unify$ operation on $T_i$ \\ 28 28 $combine(T, T')$ & $\rightarrow \top | \bot$ & Merge two environments \\ 29 29 $save(T)$ & $\rightarrow H$ & Get handle for current state \\ … … 40 40 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$. 41 41 $bind(T_i, b_i)$ mutates the bound for a type class, setting or updating the current bound. 42 The final basic mutation operation is $remove(T, T_i)$, which removes a class $T_i$ and all its type variables from an environment $T$.43 42 44 43 The $unify$ operation is the fundamental non-trivial operation a type environment data structure must support. 45 44 $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. 46 45 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. 47 $unify$ depends on an internal $unify _bound$ operation which may fail.48 In \CFACC{}, $unify _bound(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.49 If the bound types cannot be unified (\eg{} !struct A! with !int*!), then $unify _bound$ fails, while other combinations of bound types may result in recursive calls.50 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 $unify _bound$ on !int! and the bound type of the class containing !R!.46 $unify$ depends on an internal $unifyBound$ operation which may fail. 47 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. 48 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. 49 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!. 51 50 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. 51 For more information on \CFA{} unification, see \cite{Bilson03}. 52 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$. 53 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'$. 52 54 53 55 Given the nature of the expression resolution problem as backtracking search, caching and concurrency are both useful tools to decrease runtime. … … 57 59 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. 58 60 $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'$. 59 Like for $unify$, $combine$ can always find a mutually-consistent division 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.61 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. 60 62 61 63 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. 62 64 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$. 63 65 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. 64 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. 66 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. 67 68 \section{Approaches} 69 70 \subsection{Na\"{\i}ve} 71 72 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. 73 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. 74 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. 75 These improvements do not change the fundamental issues with this data structure, however. 76 77 \subsection{Incremental Inheritance} 78 79 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. 80 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. 81 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. 82 83 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. 84 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. 85 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. 86 87 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. 88 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. 89 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. 90 91 \subsection{Union-Find} \label{env-union-find-approach} 92 93 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}. 94 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. 95 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. 96 $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. 97 $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. 98 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$. 99 100 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. 101 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. 102 This issue can be solved by including a side map from class representatives to the type class bound. 103 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. 104 105 \subsection{Union-Find with Classes} \label{env-union-find-classes-approach} 106 107 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. 108 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. 109 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. 110 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. 111 112 \TODO{port figure from slideshow} 113 114 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. 115 Aho, Hopcroft, and Ullman also include a circularly-linked list in their 1974 textbook~\cite{Aho74}. 116 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. 117 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. 118 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. 119 When two classes are unified, the !next! pointers of the representatives of those classes are swapped, splicing the two circularly-linked lists together. 120 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. 121 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. 122 123 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. 124 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. 125 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.}. 126 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. 127 128 \begin{theorem} \label{env-reverse-thm} 129 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. 130 \end{theorem} 131 132 \begin{proof} 133 By induction on the height of the tree. \\ 134 \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. \\ 135 \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. 136 \end{proof} 137 138 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. 139 140 \subsection{Persistent Union-Find} 141 142 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. 143 Conchon and Filli\^{a}tre~\cite{Conchon07} present a persistent union-find data structure based on the persistent array of Baker~\cite{Baker78,Baker91}. 144 145 \TODO{port figure from slideshow} 146 147 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. 148 In this manner, a tree of edits is formed, rooted at the actual array. 149 Read from the actual array at the root can be performed in constant time, as with a non-persistent array. 150 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. 151 The mutation algorithm at the root is in some sense a special case of the key operation on persistent arrays, $reroot$. 152 153 A rerooting operation takes any array reference and makes it the root node of the array. 154 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. 155 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. 156 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. 157 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. 158 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. 159 160 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. 161 In particular, an arbitrary number of type variables must be added to the environment. 162 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. 163 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. 164 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. 165 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. 166 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. 167 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. 168 169 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. 170 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. 171 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. 172 173 The procedure for $combine(T, T')$ based on edit paths is as follows: 174 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. 175 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. 176 This procedure is repeated for both the class edit tree and the binding edit tree. 177 When the list of net changes to the environment has been produced, the additive changes are applied to $T$. 178 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. 179 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''$. 180 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. 181 182 \section{Analysis} 183 184 In this section I present asymptotic analyses of the various approaches to a type environment data structure discussed in the previous section. 185 186 \begin{table} 187 \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.} 188 \label{env-bounds-table} 189 \centering 190 \begin{tabular}{rllll} 191 \hline 192 & \textbf{Na\"{\i}ve} & \textbf{Incremental} & \textbf{Union-Find} & \textbf{U-F with Classes} \\ 193 \hline 194 $find$ & $O(n)$ & $O(p)$ & $O(\alpha(m))$ & $O(\log m)$ \\ 195 $report$ & $O(m)$ & $O(m)$ & $O(n \log m)$ & $O(m)$ \\ 196 $bound$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 197 $insert$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 198 $add$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 199 $bind$ & $O(1)$ & $O(1)$ & $O(1)$ & $O(1)$ \\ 200 $unify$ & $O(m + u(n))$ & $O(m + u(n))$ & $O(\log m + u(n))$ & $O(\log m + u(n))$ \\ 201 $split$ & --- & --- & --- & $O(\log m)$ \\ 202 $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))$ \\ 203 $save$ & $O(nm)$ & $O(1)$ & $O(nm)$ & $O(1)$ \\ 204 $backtrack$ & $O(nm)$ & $O(pm)$ & $O(nm)$ & $O(p)$ \\ 205 \hline 206 \end{tabular} 207 \end{table} 65 208 66 209 % Future work: design multi-threaded version of C&F persistent map --- core idea is some sort of thread-boundary edit node -
doc/user/user.tex
rcdc02f2 r515a037 11 11 %% Created On : Wed Apr 6 14:53:29 2016 12 12 %% Last Modified By : Peter A. Buhr 13 %% Last Modified On : Fri Aug 31 07:54:50201814 %% Update Count : 3 39613 %% Last Modified On : Tue Dec 11 23:19:26 2018 14 %% Update Count : 3400 15 15 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 16 16 … … 178 178 int main( void ) { 179 179 int x = 0, y = 1, z = 2; 180 ®sout | x | y | z | endl;®§\indexc{sout}§180 ®sout | x | y | z;®§\indexc{sout}§ 181 181 } 182 182 \end{cfa} … … 513 513 Floating exponentiation\index{exponentiation!floating} is performed using \Index{logarithm}s\index{exponentiation!logarithm}, so the base cannot be negative. 514 514 \begin{cfa} 515 sout | 2 ®\® 8u | 4 ®\® 3u | -4 ®\® 3u | 4 ®\® -3 | -4 ®\® -3 | 4.0 ®\® 2.1 | (1.0f+2.0fi) ®\® (3.0f+2.0fi) | endl;515 sout | 2 ®\® 8u | 4 ®\® 3u | -4 ®\® 3u | 4 ®\® -3 | -4 ®\® -3 | 4.0 ®\® 2.1 | (1.0f+2.0fi) ®\® (3.0f+2.0fi); 516 516 256 64 -64 0.015625 -0.015625 18.3791736799526 0.264715-1.1922i 517 517 \end{cfa} … … 547 547 548 548 549 %\subsection{\texorpdfstring{\protect\lstinline@for@ Statement}{for Statement}} 550 \subsection{\texorpdfstring{\LstKeywordStyle{for} Statement}{for Statement}} 549 \subsection{Loop Control} 551 550 552 551 The ©for©/©while©/©do-while© loop-control allows empty or simplified ranges. … … 557 556 the down-to range ©-~=©\index{-~=@©-~=©} means inclusive range [N,M]. 558 557 ©0© is the implicit start value; 559 ©1© is the implicit increment value for an up-to range and ©-1© for an implicit down-to range. 558 ©1© is the implicit increment value. 559 The up-to range uses ©+=© for increment; 560 the down-to range uses ©-=© for decrement. 560 561 The loop index is polymorphic in the type of the start value or comparison value when start is implicitly ©0©. 561 562 \begin{cquote} 562 563 \begin{tabular}{@{}ll|l@{}} 563 \multicolumn{2}{c|}{ forcontrol} & \multicolumn{1}{c}{output} \\564 \multicolumn{2}{c|}{loop control} & \multicolumn{1}{c}{output} \\ 564 565 \hline 565 566 \begin{cfa} … … 571 572 for ( ®10® ) { sout | "A"; } 572 573 for ( ®1 ~= 10 ~ 2® ) { sout | "B"; } 573 for ( ®10 -~= 1 ~ -2® ) { sout | "C"; }574 for ( ®10 -~= 1 ~ 2® ) { sout | "C"; } 574 575 for ( ®0.5 ~ 5.5® ) { sout | "D"; } 575 576 for ( ®5.5 -~ 0.5® ) { sout | "E"; } 576 577 for ( ®i; 10® ) { sout | i; } 577 578 for ( ®i; 1 ~= 10 ~ 2® ) { sout | i; } 578 for ( ®i; 10 -~= 1 ~ -2® ) { sout | i; }579 for ( ®i; 10 -~= 1 ~ 2® ) { sout | i; } 579 580 for ( ®i; 0.5 ~ 5.5® ) { sout | i; } 580 581 for ( ®i; 5.5 -~ 0.5® ) { sout | i; } 581 582 for ( ®ui; 2u ~= 10u ~ 2u® ) { sout | ui; } 582 for ( ®ui; 10u -~= 2u ~ -2u® ) { sout | ui; } 583 int start = 3, comp = 10, inc = 2; 583 for ( ®ui; 10u -~= 2u ~ 2u® ) { sout | ui; } 584 enum { N = 10 }; 585 for ( ®N® ) { sout | "N"; } 586 for ( ®i; N® ) { sout | i; } 587 for ( ®i; N -~ 0® ) { sout | i; } 588 const int start = 3, comp = 10, inc = 2; 584 589 for ( ®i; start ~ comp ~ inc + 1® ) { sout | i; } 585 590 \end{cfa} 586 591 & 587 592 \begin{cfa} 588 sout | endl; 589 sout | endl; 590 sout | endl; 591 sout | endl; 592 sout | endl; 593 sout | endl; 594 sout | endl; 595 sout | endl; 596 sout | endl; 597 sout | endl; 598 sout | endl; 599 sout | endl; 600 sout | endl; 601 sout | endl; 602 sout | endl; 603 sout | endl; 604 sout | endl; 605 606 sout | endl; 593 sout | nl; 594 sout | nl; 595 sout | nl; 596 sout | "zero" | nl; 597 sout | nl; 598 sout | nl; 599 sout | nl; 600 sout | nl; 601 sout | nl; 602 sout | nl; 603 sout | nl; 604 sout | nl; 605 sout | nl; 606 sout | nl; 607 sout | nl; 608 sout | nl; 609 sout | nl | nl; 610 611 sout | nl; 612 sout | nl; 613 sout | nl | nl; 614 615 sout | nl; 607 616 \end{cfa} 608 617 & … … 611 620 empty 612 621 empty 613 622 zero 614 623 A 615 624 A A A A A A A A A A … … 625 634 2 4 6 8 10 626 635 10 8 6 4 2 636 637 N N N N N N N N N N 638 0 1 2 3 4 5 6 7 8 9 639 10 9 8 7 6 5 4 3 2 1 627 640 628 641 3 6 9 … … 2446 2459 int bar( int p ) { 2447 2460 ®i® += 1; §\C{// dependent on local variable}§ 2448 sout | ®i® | endl;2461 sout | ®i®; 2449 2462 } 2450 2463 return bar; §\C{// undefined because of local dependence}§ … … 2452 2465 int main() { 2453 2466 * [int]( int ) fp = foo(); §\C{// int (* fp)( int )}§ 2454 sout | fp( 3 ) | endl;2467 sout | fp( 3 ); 2455 2468 } 2456 2469 \end{cfa} … … 3218 3231 \begin{cfa} 3219 3232 int x = 1, y = 2, z = 3; 3220 sout | x ®|® y ®|® z | endl;3233 sout | x ®|® y ®|® z; 3221 3234 \end{cfa} 3222 3235 & … … 3239 3252 \begin{cfa} 3240 3253 [int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ]; 3241 sout | t1 | t2 | endl;§\C{// print tuples}§3254 sout | t1 | t2; §\C{// print tuples}§ 3242 3255 \end{cfa} 3243 3256 \begin{cfa}[showspaces=true,aboveskip=0pt] … … 3251 3264 & 3252 3265 \begin{cfa} 3253 sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;3266 sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2); 3254 3267 \end{cfa} 3255 3268 \\ … … 3277 3290 A separator does not appear at the start or end of a line. 3278 3291 \begin{cfa}[belowskip=0pt] 3279 sout | 1 | 2 | 3 | endl;3292 sout | 1 | 2 | 3; 3280 3293 \end{cfa} 3281 3294 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3286 3299 A separator does not appear before or after a character literal or variable. 3287 3300 \begin{cfa} 3288 sout | '1' | '2' | '3' | endl;3301 sout | '1' | '2' | '3'; 3289 3302 123 3290 3303 \end{cfa} … … 3293 3306 A separator does not appear before or after a null (empty) C string. 3294 3307 \begin{cfa} 3295 sout | 1 | "" | 2 | "" | 3 | endl;3308 sout | 1 | "" | 2 | "" | 3; 3296 3309 123 3297 3310 \end{cfa} … … 3303 3316 \begin{cfa}[mathescape=off] 3304 3317 sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥" 3305 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;3318 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10; 3306 3319 \end{cfa} 3307 3320 %$ … … 3317 3330 \begin{cfa}[belowskip=0pt] 3318 3331 sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x" 3319 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;3332 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x"; 3320 3333 \end{cfa} 3321 3334 \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@ 3328 3341 \begin{cfa}[belowskip=0pt] 3329 sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;3342 sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx"; 3330 3343 \end{cfa} 3331 3344 \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. 3337 3350 \begin{cfa}[belowskip=0pt] 3338 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;3351 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; 3339 3352 \end{cfa} 3340 3353 \begin{cfa}[basicstyle=\tt,showspaces=true,showtabs=true,aboveskip=0pt,belowskip=0pt] … … 3353 3366 \begin{cfa}[mathescape=off,belowskip=0pt] 3354 3367 sepSet( sout, ", $" ); §\C{// set separator from " " to ", \$"}§ 3355 sout | 1 | 2 | 3 | " \"" | ®sep® | "\"" | endl;3368 sout | 1 | 2 | 3 | " \"" | ®sep® | "\""; 3356 3369 \end{cfa} 3357 3370 %$ … … 3362 3375 \begin{cfa}[belowskip=0pt] 3363 3376 sepSet( sout, " " ); §\C{// reset separator to " "}§ 3364 sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\"" | endl;3377 sout | 1 | 2 | 3 | " \"" | ®sepGet( sout )® | "\""; 3365 3378 \end{cfa} 3366 3379 \begin{cfa}[showspaces=true,aboveskip=0pt] … … 3372 3385 strcpy( store, sepGet( sout ) ); §\C{// copy current separator}§ 3373 3386 sepSet( sout, "_" ); §\C{// change separator to underscore}§ 3374 sout | 1 | 2 | 3 | endl;3387 sout | 1 | 2 | 3; 3375 3388 \end{cfa} 3376 3389 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3379 3392 \begin{cfa}[belowskip=0pt] 3380 3393 sepSet( sout, store ); §\C{// change separator back to original}§ 3381 sout | 1 | 2 | 3 | endl;3394 sout | 1 | 2 | 3; 3382 3395 \end{cfa} 3383 3396 \begin{cfa}[showspaces=true,aboveskip=0pt] … … 3390 3403 \begin{cfa}[belowskip=0pt] 3391 3404 sepSetTuple( sout, " " ); §\C{// set tuple separator from ", " to " "}§ 3392 sout | t1 | t2 | " \"" | ®sepTuple® | "\"" | endl;3405 sout | t1 | t2 | " \"" | ®sepTuple® | "\""; 3393 3406 \end{cfa} 3394 3407 \begin{cfa}[showspaces=true,aboveskip=0pt] … … 3397 3410 \begin{cfa}[belowskip=0pt] 3398 3411 sepSetTuple( sout, ", " ); §\C{// reset tuple separator to ", "}§ 3399 sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\"" | endl;3412 sout | t1 | t2 | " \"" | ®sepGetTuple( sout )® | "\""; 3400 3413 \end{cfa} 3401 3414 \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. 3408 3421 \begin{cfa}[belowskip=0pt] 3409 sout | sepDisable | 1 | 2 | 3 | endl;§\C{// globally turn off implicit separator}§3422 sout | sepDisable | 1 | 2 | 3; §\C{// globally turn off implicit separator}§ 3410 3423 \end{cfa} 3411 3424 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3413 3426 \end{cfa} 3414 3427 \begin{cfa}[belowskip=0pt] 3415 sout | sepEnable | 1 | 2 | 3 | endl; §\C{// globally turn on implicit separator}§3428 sout | sepEnable | 1 | 2 | 3; §\C{// globally turn on implicit separator}§ 3416 3429 \end{cfa} 3417 3430 \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. 3423 3436 \begin{cfa}[belowskip=0pt] 3424 sout | 1 | sepOff | 2 | 3 | endl; §\C{// locally turn off implicit separator}§3437 sout | 1 | sepOff | 2 | 3; §\C{// locally turn off implicit separator}§ 3425 3438 \end{cfa} 3426 3439 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3428 3441 \end{cfa} 3429 3442 \begin{cfa}[belowskip=0pt] 3430 sout | sepDisable | 1 | sepOn | 2 | 3 | endl; §\C{// locally turn on implicit separator}§3443 sout | sepDisable | 1 | sepOn | 2 | 3; §\C{// locally turn on implicit separator}§ 3431 3444 \end{cfa} 3432 3445 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3435 3448 The tuple separator also responses to being turned on and off. 3436 3449 \begin{cfa}[belowskip=0pt] 3437 sout | t1 | sepOff | t2 | endl; §\C{// locally turn on/off implicit separator}§3450 sout | t1 | sepOff | t2; §\C{// locally turn on/off implicit separator}§ 3438 3451 \end{cfa} 3439 3452 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3443 3456 use ©sep© to accomplish this functionality. 3444 3457 \begin{cfa}[belowskip=0pt] 3445 sout | sepOn | 1 | 2 | 3 | sepOn | endl; §\C{// sepOn does nothing at start/end of line}§3458 sout | sepOn | 1 | 2 | 3 | sepOn; §\C{// sepOn does nothing at start/end of line}§ 3446 3459 \end{cfa} 3447 3460 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3449 3462 \end{cfa} 3450 3463 \begin{cfa}[belowskip=0pt] 3451 sout | sep | 1 | 2 | 3 | sep | endl; §\C{// use sep to print separator at start/end of line}§3464 sout | sep | 1 | 2 | 3 | sep ; §\C{// use sep to print separator at start/end of line}§ 3452 3465 \end{cfa} 3453 3466 \begin{cfa}[showspaces=true,aboveskip=0pt,belowskip=0pt] … … 3462 3475 int main( void ) { 3463 3476 int x = 1, y = 2, z = 3; 3464 sout | x | y | z | endl;3477 sout | x | y | z; 3465 3478 [int, [ int, int ] ] t1 = [ 1, [ 2, 3 ] ], t2 = [ 4, [ 5, 6 ] ]; 3466 sout | t1 | t2 | endl; // print tuples3467 sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2) | endl;3468 sout | 1 | 2 | 3 | endl;3469 sout | '1' | '2' | '3' | endl;3470 sout | 1 | "" | 2 | "" | 3 | endl;3479 sout | t1 | t2; // print tuples 3480 sout | x * 3 | y + 1 | z << 2 | x == y | (x | y) | (x || y) | (x > z ? 1 : 2); 3481 sout | 1 | 2 | 3; 3482 sout | '1' | '2' | '3'; 3483 sout | 1 | "" | 2 | "" | 3; 3471 3484 sout | "x (" | 1 | "x [" | 2 | "x {" | 3 | "x =" | 4 | "x $" | 5 | "x £" | 6 | "x ¥" 3472 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10 | endl;3485 | 7 | "x ¡" | 8 | "x ¿" | 9 | "x «" | 10; 3473 3486 sout | 1 | ", x" | 2 | ". x" | 3 | "; x" | 4 | "! x" | 5 | "? x" | 6 | "% x" 3474 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x" | endl;3475 sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx" | endl;3476 sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4 | endl;3487 | 7 | "¢ x" | 8 | "» x" | 9 | ") x" | 10 | "] x" | 11 | "} x"; 3488 sout | "x`" | 1 | "`x'" | 2 | "'x\"" | 3 | "\"x:" | 4 | ":x " | 5 | " x\t" | 6 | "\tx"; 3489 sout | "x ( " | 1 | " ) x" | 2 | " , x" | 3 | " :x: " | 4; 3477 3490 3478 3491 sepSet( sout, ", $" ); // set separator from " " to ", $" 3479 sout | 1 | 2 | 3 | " \"" | sep | "\"" | endl;3492 sout | 1 | 2 | 3 | " \"" | sep | "\""; 3480 3493 sepSet( sout, " " ); // reset separator to " " 3481 sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\"" | endl;3494 sout | 1 | 2 | 3 | " \"" | sepGet( sout ) | "\""; 3482 3495 3483 3496 char store[sepSize]; 3484 3497 strcpy( store, sepGet( sout ) ); 3485 3498 sepSet( sout, "_" ); 3486 sout | 1 | 2 | 3 | endl;3499 sout | 1 | 2 | 3; 3487 3500 sepSet( sout, store ); 3488 sout | 1 | 2 | 3 | endl;3501 sout | 1 | 2 | 3; 3489 3502 3490 3503 sepSetTuple( sout, " " ); // set tuple separator from ", " to " " 3491 sout | t1 | t2 | " \"" | sepTuple | "\"" | endl;3504 sout | t1 | t2 | " \"" | sepTuple | "\""; 3492 3505 sepSetTuple( sout, ", " ); // reset tuple separator to ", " 3493 sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\"" | endl;3494 3495 sout | sepDisable | 1 | 2 | 3 | endl; // globally turn off implicit separator3496 sout | sepEnable | 1 | 2 | 3 | endl; // globally turn on implicit separator3497 3498 sout | 1 | sepOff | 2 | 3 | endl; // locally turn on implicit separator3499 sout | sepDisable | 1 | sepOn | 2 | 3 | endl; // globally turn off implicit separator3506 sout | t1 | t2 | " \"" | sepGetTuple( sout ) | "\""; 3507 3508 sout | sepDisable | 1 | 2 | 3; // globally turn off implicit separator 3509 sout | sepEnable | 1 | 2 | 3; // globally turn on implicit separator 3510 3511 sout | 1 | sepOff | 2 | 3; // locally turn on implicit separator 3512 sout | sepDisable | 1 | sepOn | 2 | 3; // globally turn off implicit separator 3500 3513 sout | sepEnable; 3501 sout | t1 | sepOff | t2 | endl; // locally turn on/off implicit separator3502 3503 sout | sepOn | 1 | 2 | 3 | sepOn | endl; // sepOn does nothing at start/end of line3504 sout | sep | 1 | 2 | 3 | sep | endl; // use sep to print separator at start/end of line3514 sout | t1 | sepOff | t2; // locally turn on/off implicit separator 3515 3516 sout | sepOn | 1 | 2 | 3 | sepOn ; // sepOn does nothing at start/end of line 3517 sout | sep | 1 | 2 | 3 | sep ; // use sep to print separator at start/end of line 3505 3518 } 3506 3519 … … 4167 4180 Fibonacci f1, f2; 4168 4181 for ( int i = 1; i <= 10; i += 1 ) { 4169 sout | next( &f1 ) | ' ' | next( &f2 ) | endl;4182 sout | next( &f1 ) | ' ' | next( &f2 ); 4170 4183 } // for 4171 4184 } … … 4233 4246 MyThread f[4]; 4234 4247 } 4235 sout | global.value | endl;4248 sout | global.value; 4236 4249 } 4237 4250 \end{cfa} … … 4311 4324 void main( First * this ) { 4312 4325 for ( int i = 0; i < 10; i += 1 ) { 4313 sout | "First : Suspend No." | i + 1 | endl;4326 sout | "First : Suspend No." | i + 1; 4314 4327 yield(); 4315 4328 } … … 4320 4333 wait( this->lock ); 4321 4334 for ( int i = 0; i < 10; i += 1 ) { 4322 sout | "Second : Suspend No." | i + 1 | endl;4335 sout | "Second : Suspend No." | i + 1; 4323 4336 yield(); 4324 4337 } … … 4327 4340 int main( void ) { 4328 4341 signal_once lock; 4329 sout | "User main begin" | endl;4342 sout | "User main begin"; 4330 4343 { 4331 4344 processor p; … … 4335 4348 } 4336 4349 } 4337 sout | "User main end" | endl;4350 sout | "User main end"; 4338 4351 } 4339 4352 \end{cfa} … … 5032 5045 void ?{}( Line * l ) { 5033 5046 l->lnth = 0.0; 5034 sout | "default" | endl;5047 sout | "default"; 5035 5048 } 5036 5049 … … 5039 5052 void ?{}( Line * l, float lnth ) { 5040 5053 l->lnth = lnth; 5041 sout | "lnth" | l->lnth | endl;5054 sout | "lnth" | l->lnth; 5042 5055 5043 5056 } … … 5045 5058 // destructor 5046 5059 void ^?() { 5047 sout | "destroyed" | endl;5060 sout | "destroyed"; 5048 5061 l.lnth = 0.0; 5049 5062 } … … 5791 5804 In particular, output of ©char© variable now print a character rather than the decimal ASCII value of the character. 5792 5805 \begin{cfa} 5793 sout | 'x' | " " | (int)'x' | endl;5806 sout | 'x' | " " | (int)'x'; 5794 5807 x 120 5795 5808 \end{cfa} … … 7021 7034 #include <gmp>§\indexc{gmp}§ 7022 7035 int main( void ) { 7023 sout | "Factorial Numbers" | endl;7036 sout | "Factorial Numbers"; 7024 7037 Int fact = 1; 7025 7038 7026 sout | 0 | fact | endl;7039 sout | 0 | fact; 7027 7040 for ( unsigned int i = 1; i <= 40; i += 1 ) { 7028 7041 fact *= i; 7029 sout | i | fact | endl;7042 sout | i | fact; 7030 7043 } 7031 7044 }
Note: See TracChangeset
for help on using the changeset viewer.