- Timestamp:
- Sep 25, 2018, 4:56:55 PM (7 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:
- 34a6b2e, a332d432
- Parents:
- 48b7085e (diff), 560812b (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:
-
- 2 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/bibliography/pl.bib
r48b7085e ra32346b 701 701 % B 702 702 703 @article{Michael13, 704 contributer = {pabuhr@plg}, 705 author = {Maged M. Michael}, 706 title = {The Balancing Act of Choosing Nonblocking Features}, 707 journal = cacm, 708 volume = 56, 709 number = 9, 710 month = sep, 711 year = 2013, 712 pages = {46--53}, 713 publisher = {ACM}, 714 address = {New York, NY, USA}, 715 } 716 703 717 @incollection{beta:old, 704 718 keywords = {beta, patterns, virtual types}, … … 908 922 909 923 @misc{Cforall, 924 contributer = {pabuhr@plg}, 910 925 key = {Cforall}, 911 title = {\textsf{C}{$\mathbf{\forall}$} Features},912 howpublished= {\ url{https://plg.uwaterloo.ca/~cforall/features}},926 author = {{\textsf{C}{$\mathbf{\forall}$} Features}}, 927 howpublished= {\href{https://plg.uwaterloo.ca/~cforall/features}{https://\-plg.uwaterloo.ca/\-~cforall/\-features}}, 913 928 optnote = {Accessed: 2018-01-01}, 914 929 } … … 926 941 927 942 @misc{CFAStackEvaluation, 943 contributer = {a3moss@plg}, 928 944 author = {Aaron Moss}, 929 945 title = {\textsf{C}$\mathbf{\forall}$ Stack Evaluation Programs}, … … 934 950 935 951 @article{Moss18, 936 keywords = { concurrency, C++},952 keywords = {type systems, tuples, Cforall}, 937 953 contributer = {pabuhr@plg}, 938 954 author = {Aaron Moss and Robert Schluntz and Peter A. Buhr}, … … 941 957 month = aug, 942 958 journal = spe, 943 note = { http://dx.doi.org/10.1002/spe.2624},959 note = {\href{http://dx.doi.org/10.1002/spe.2624}{http://\-dx.doi.org/\-10.1002/\-spe.2624}}, 944 960 } 945 961 … … 1417 1433 } 1418 1434 1435 @misc{NThreadCode13, 1436 keywords = {N-thread software-solution mutual exclusion}, 1437 contributer = {pabuhr@plg}, 1438 key = {concurrent locking}, 1439 author = {Peter A. Buhr and David Dice and Wim H. Hesselink}, 1440 title = {concurrent-locking}, 1441 howpublished= {\href{https://github.com/pabuhr/concurrent-locking}{https://\-github.com/\-pabuhr/\-concurrent-locking}}, 1442 optnote = {[Accessed April 2017]}, 1443 } 1444 1419 1445 @incollection{Reppy93, 1420 1446 keywords = {ML, concurrency, continuation passing}, … … 1490 1516 month = dec, 1491 1517 year = 2017, 1492 note = {\href{http ://plg.uwaterloo.ca/~usystem/pub/uSystem/u++-7.0.0.sh}{http://\-plg.\-uwaterloo.\-ca/\-$\sim$usystem/\-pub/\-uSystem/\-u++-7.0.0.sh}},1518 note = {\href{https://plg.uwaterloo.ca/~usystem/pub/uSystem/uC++.pdf}{https://\-plg.uwaterloo.ca/\-~usystem/\-pub/\-uSystem/uC++.pdf}}, 1493 1519 } 1494 1520 … … 1557 1583 } 1558 1584 1585 @mastersthesis{Sun15, 1586 author = {Sun, Xianda}, 1587 title = {Concurrent High-performance Persistent Hash Table In {J}ava}, 1588 school = {School of Computer Science, University of Waterloo}, 1589 year = 2015, 1590 optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, 1591 note = {\href{https://uwspace.uwaterloo.ca/handle/10012/10013}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-10013}}, 1592 } 1593 1559 1594 @book{Andrews91:book, 1560 1595 keywords = {concurrency}, … … 1581 1616 1582 1617 @mastersthesis{Delisle18, 1618 keywords = {concurrency, Cforall}, 1619 contributer = {pabuhr@plg}, 1583 1620 author = {Thierry Delisle}, 1584 1621 title = {Concurrency in \textsf{C}$\mathbf{\forall}$}, 1585 1622 school = {School of Computer Science, University of Waterloo}, 1586 1623 year = 2018, 1587 address = {Waterloo, Ontario, Canada, N2L 3G1},1624 optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, 1588 1625 note = {\href{https://uwspace.uwaterloo.ca/handle/10012/12888}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-12888}}, 1626 } 1627 1628 @article{Delisle18b, 1629 keywords = {concurrency, Cforall}, 1630 contributer = {pabuhr@plg}, 1631 author = {Thierry Delisle and Peter A. Buhr}, 1632 title = {Concurrency in \textsf{C}$\mathbf{\forall}$}, 1633 year = 2018, 1634 journal = spe, 1635 pages = {1-32}, 1636 note = {submitted}, 1589 1637 } 1590 1638 … … 2865 2913 keywords = {concurrency, mutual exclusion, performance experiment, software solutions}, 2866 2914 title = {Fast mutual exclusion by the {T}riangle algorithm}, 2867 author = {Wim H. Hesselink and Peter Buhr and David Dice},2915 author = {Wim H. Hesselink and Peter A. Buhr and David Dice}, 2868 2916 journal = ccpe, 2869 2917 volume = 30, … … 2872 2920 month = feb, 2873 2921 publisher = {John Wiley \& Sons}, 2874 note = {\ url{https://doi.org/10.1002/cpe.4183}}2922 note = {\href{https://doi.org/10.1002/cpe.4183}{https://\-doi.org/\-10.1002/\-cpe.4183}} 2875 2923 } 2876 2924 … … 3284 3332 edition = {{S}imon {M}arlow}, 3285 3333 year = 2010, 3286 note = {\href{https://haskell.org/definition/haskell2010.pdf}{https:// haskell.org/\-definition/\-haskell2010.pdf}},3334 note = {\href{https://haskell.org/definition/haskell2010.pdf}{https://\-haskell.org/\-definition/\-haskell2010.pdf}}, 3287 3335 } 3288 3336 … … 3358 3406 } 3359 3407 3360 @article{Hesselink17 ,3408 @article{Hesselink17b, 3361 3409 keywords = {concurrency, mutual exclusion, performance experiment, software solutions}, 3362 3410 title = {High-Contention Mutual Exclusion by Elevator Algorithms}, 3363 author = {Peter Buhr and David Dice and Wim H. Hesselink},3411 author = {Peter A. Buhr and David Dice and Wim H. Hesselink}, 3364 3412 journal = ccpe, 3365 3413 volume = 30, … … 3368 3416 month = sep, 3369 3417 publisher = {John Wiley \& Sons}, 3370 note = {\ url{https://doi-org.proxy.lib.uwaterloo.ca/10.1002/cpe.4475}}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}}, 3371 3419 } 3372 3420 … … 3846 3894 3847 3895 % K 3896 3897 @inproceedings{Buhr96b, 3898 author = {Peter A. Buhr and Martin Karsten and Jun Shih}, 3899 title = {{\small\textsf{KDB}}: A Multi-threaded Debugger for Multi-threaded Applications}, 3900 booktitle = {Proceedings of SPDT'96: SIGMETRICS Symposium on Parallel and Distributed Tools}, 3901 publisher = {ACM Press}, 3902 address = {Philadelphia, Pennsylvania, U.S.A.}, 3903 month = may, 3904 year = 1996, 3905 pages = {80-87}, 3906 } 3848 3907 3849 3908 @article{Duggan96, … … 4534 4593 % N 4535 4594 4595 @techreport{Drepper03, 4596 keywords = {NPTL, threading, 1:1 model}, 4597 contributer = {pabuhr@plg}, 4598 author = {Ulrich Drepper and Ingo Molnar}, 4599 title = {The Native POSIX Thread Library for Linux}, 4600 institution = {Red Hat}, 4601 year = 2003, 4602 note = {\href{http://www.cs.utexas.edu/~witchel/372/lectures/POSIX_Linux_Threading.pdf}{http://www.cs.utexas.edu/\-$\sim$witchel/\-372/\-lectures/\-POSIX\_Linux\_Threading.pdf}}, 4603 } 4604 4536 4605 @article{Haddon77, 4537 4606 keywords = {monitors, nested monitor calls}, … … 4657 4726 volume = 9, 4658 4727 pages = {157-164}, 4728 } 4729 4730 @misc{nginx, 4731 key = {nginx}, 4732 author = {{NGINX}}, 4733 howpublished= {\href{https://www.nginx.com}{https://\-www.nginx.com}}, 4659 4734 } 4660 4735 … … 4769 4844 @misc{obj-c-book, 4770 4845 keywords = {objective-c}, 4771 contributor = { a3moss@uwaterloo.ca},4846 contributor = {pabuhr@plg}, 4772 4847 key = {Objective-C}, 4773 title= {Objective-C},4848 author = {Objective-C}, 4774 4849 publisher = {Apple Inc.}, 4775 year = 201 5,4776 howpublished= {\href{https://developer.apple.com/library/ content/documentation/General/Conceptual/DevPedia-CocoaCore/ObjectiveC.html}{https://developer.apple.com/\-library/\-content/\-documentation/\-General/\-Conceptual/\-DevPedia-\-CocoaCore/\-ObjectiveC.html}},4850 year = 2014, 4851 howpublished= {\href{https://developer.apple.com/library/archive/documentation/Cocoa/Conceptual/ProgrammingWithObjectiveC}{https://\-developer.apple.com/\-library/archive/\-documentation/\-Cocoa/\-Conceptual/\-ProgrammingWithObjectiveC}}, 4777 4852 optnote = {Accessed: 2018-03} 4778 4853 } … … 4784 4859 title = {{X}code 7 Release Notes}, 4785 4860 year = 2015, 4786 howpublished= {\href{https://developer.apple.com/library/content/documentation/Xcode/Conceptual/RN-Xcode-Archive/Chapters/xc7_release_notes.html}{https:// developer.apple.com/\-library/\-content/\-documentation/\-Xcode/\-Conceptual/\-RN-Xcode-Archive/\-Chapters/\-xc7\_release\_notes.html}},4861 howpublished= {\href{https://developer.apple.com/library/content/documentation/Xcode/Conceptual/RN-Xcode-Archive/Chapters/xc7_release_notes.html}{https://\-developer.apple.com/\-library/\-content/\-documentation/\-Xcode/\-Conceptual/\-RN-Xcode-Archive/\-Chapters/\-xc7\_release\_notes.html}}, 4787 4862 optnote = {Accessed: 2017-04} 4788 4863 } … … 5284 5359 } 5285 5360 5361 @misc{perf, 5362 contributer = {pabuhr@plg}, 5363 key = {perf}, 5364 author = {perf}, 5365 howpublished= {\href{https://perf.wiki.kernel.org/index.php/Tutorial}{https://\-perf.wiki.kernel.org/\-index.php/\-Tutorial}}, 5366 } 5367 5368 @misc{Verch12, 5369 contributer = {pabuhr@plg}, 5370 author = {Shaun Verch}, 5371 title = {Performance Analysis of 64-Bit Capriccio}, 5372 month = may, 5373 year = 2012, 5374 howpublished= {\href{http://cs.brown.edu/research/pubs/theses/masters/2012/verch.pdf}{http://cs.brown.edu/\-research/\-pubs/\-theses/\-masters/\-2012/\-verch.pdf}}, 5375 optnote = {Accessed: 2013-10-4} 5376 } 5377 5286 5378 @article{Anderson90, 5287 5379 keywords = {spin locks, back off, performance}, … … 5504 5596 note = {Proceedings of the OOPSLA'89 Conference, Oct. 1--6, 1989, New Orleans, Lousiana}, 5505 5597 abstract = {}, 5598 } 5599 5600 @inproceedings{Buhr98, 5601 keywords = {profiling, monitoring, visualization}, 5602 contributer = {pabuhr@plg}, 5603 author = {Peter A. Buhr and Robert Denda}, 5604 title = {{$\mu$Profiler} : Profiling User-Level Threads in a Shared-Memory Programming Environment}, 5605 booktitle = {Proceedings of the Second International Symposium on Computing in Object-Oriented Parallel Environments (ISCOPE'98)}, 5606 series = {Lecture Notes in Computer Science}, 5607 publisher = {Springer-Verlag}, 5608 volume = 1505, 5609 opteditor = {Dennis Caromel and Rodney R. Oldehoeft and Marydell Tholburn}, 5610 address = {Santa Fe, New Mexico, U.S.A.}, 5611 month = dec, 5612 year = 1998, 5613 pages = {159-166}, 5506 5614 } 5507 5615 … … 5965 6073 } 5966 6074 6075 @article{Ronsse03, 6076 keywords = {profiling, replay}, 6077 contributer = {pabuhr@plg}, 6078 author = {Michiel Ronsse and De Bosschere, Koen and Mark Christiaens and Jacques Chassin de Kergommeaux and Dieter Kranzlm\"{u}ller}, 6079 title = {Record/Replay for Nondeterministic Program Executions}, 6080 journal = cacm, 6081 month = sep, 6082 year = 2003, 6083 volume = 46, 6084 number = 9, 6085 pages = {62-67}, 6086 } 6087 5967 6088 @article{Robinson48, 5968 6089 keywords = {recursion, Ackermann function}, … … 6003 6124 } 6004 6125 6126 @mastersthesis{Schuster99, 6127 author = {Oliver Schuster}, 6128 title = {Replay of Concurrent Shared-Memory Programs}, 6129 school = {Universit\"at Mannheim}, 6130 address = {Mannheim, Deutschland}, 6131 year = 1999, 6132 month = apr, 6133 type = {Diplomarbeit}, 6134 note = {\href{ftp://plg.uwaterloo.ca/pub/theses/SchusterThesis.ps.gz}{ftp://\-plg.uwaterloo.ca/\-pub/\-theses/\-SchusterThesis.ps.gz}}, 6135 } 6136 6005 6137 @article{Euclid, 6006 6138 keywords = {Euclid}, … … 6034 6166 school = {School of Computer Science, University of Waterloo}, 6035 6167 year = 2017, 6036 address = {Waterloo, Ontario, Canada, N2L 3G1},6168 optaddress = {Waterloo, Ontario, Canada, N2L 3G1}, 6037 6169 note = {\href{https://uwspace.uwaterloo.ca/handle/10012/11830}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-11830}}, 6038 6170 } … … 6861 6993 contributer = {pabuhr@plg}, 6862 6994 key = {TIOBE Index}, 6863 title = {{TIOBE} Index},6995 author = {{TIOBE Index}}, 6864 6996 howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}}, 6865 6997 optnote = {Accessed: 2018-09}, … … 7001 7133 year = 1980 7002 7134 } 7135 7136 @misc{TraceCompass, 7137 contributer = {pabuhr@plg}, 7138 key = {Trace Compass}, 7139 author = {{T}race {C}ompass}, 7140 howpublished= {\href{https://projects.eclipse.org/proposals/trace-compass}{https://\-projects.eclipse.org/\-proposals/\-trace-compass}}, 7141 } 7003 7142 7004 7143 @article{Leroy00, … … 7136 7275 title = {Usability Challenges in Exception Handling}, 7137 7276 booktitle = {5th International Workshop on Exception Handling (WEH)}, 7138 o rganization= {16th International Symposium on the Foundations of Software Engineering (FSE 16)},7277 optorganization= {16th International Symposium on the Foundations of Software Engineering (FSE 16)}, 7139 7278 address = {Zurich, Switzerland}, 7140 7279 month = jun, … … 7280 7419 } 7281 7420 7421 @inproceedings{vonBehren03, 7422 keywords = {threads, events, web server}, 7423 contributer = {pabuhr@plg}, 7424 author = {Rob von Behren and Jeremy Condit and Eric Brewer}, 7425 title = {Why Events Are a Bad Idea (for high-concurrency servers)}, 7426 booktitle = {HotOS IX: The 9th Workshop on Hot Topics in Operating Systems}, 7427 publisher = {USENIX Association}, 7428 address = {Lihue, Hawaii, U.S.A.}, 7429 month = may, 7430 year = 2003, 7431 pages = {19-24}, 7432 } 7433 7282 7434 @techreport{Moss90, 7283 7435 keywords = {Swizzling, database}, … … 7344 7496 year = 1986, 7345 7497 editor = {Norman Meyrowitz}, 7346 publisher = sigplan # " 21(11)",7498 publisher = sigplan, 7347 7499 organization= {Association for Computing Machinery}, 7348 7500 address = {Portland, Oregon}, 7349 month = sep # { 29}7501 month = sep, 7350 7502 } 7351 7503 … … 7356 7508 year = 1987, 7357 7509 editor = {Norman Meyrowitz}, 7358 publisher = sigplan # " 22(12)",7510 publisher = sigplan, 7359 7511 organization= {Association for Computing Machinery}, 7360 7512 address = {Orlando, Florida}, 7361 month = oct # { 4--8}7513 month = oct, 7362 7514 } 7363 7515 … … 7368 7520 year = 1988, 7369 7521 editor = {Norman Meyrowitz}, 7370 publisher = sigplan # " 23(11)",7522 publisher = sigplan, 7371 7523 organization= {Association for Computing Machinery}, 7372 7524 address = {San Diego, California}, 7373 month = sep # { 25--30}7525 month = sep, 7374 7526 } 7375 7527 … … 7380 7532 year = 1989, 7381 7533 editor = {Norman Meyrowitz}, 7382 publisher = sigplan # " 24(10)",7534 publisher = sigplan, 7383 7535 organization= {Association for Computing Machinery}, 7384 7536 address = {New Orleans, Louisiana}, 7385 month = oct # { 1--6}7537 month = oct, 7386 7538 } 7387 7539 … … 7392 7544 year = 1990, 7393 7545 editor = {Norman Meyrowitz}, 7394 publisher = sigplan # " 25(10)",7546 publisher = sigplan, 7395 7547 organization= {Association for Computing Machinery}, 7396 7548 address = {Ottawa, Canada}, 7397 month = oct # { 21--25}7549 month = oct, 7398 7550 } 7399 7551 … … 7404 7556 year = 1991, 7405 7557 editor = {Andreas Paepcke}, 7406 publisher = sigplan # " 26(11)",7558 publisher = sigplan, 7407 7559 organization= {Association for Computing Machinery}, 7408 7560 address = {Phoenix, Arizona}, 7409 month = oct # { 6--11}7410 } 7561 month = oct, 7562 } -
doc/proposals/virtual.txt
r48b7085e ra32346b 87 87 first polymorphic parameter). 88 88 89 Once a function in a trait has been marked as virtual it defines a new 90 function that takes in that trait's reference and then dynamically calls the 91 underlying type implementation. Hence a trait reference becomes a kind of 92 abstract type, cannot be directly instantiated but can still be used.89 Instances of a trait are created by wrapping an existing instance of a type 90 that implements that trait. This wrapper includes all the function pointers 91 and other values required to preform the dynamic look-up. These are chosen by 92 the normal look-up rules at the point of abstraction. 93 93 94 94 One of the limitations of this design is that it does not support double … … 98 98 is also restricted, initially forbidden, see extension. 99 99 100 Ownership of the underlying structure is also a bit of a trick. Considering 101 the use cases for trait object, it is probably best to have the underlying 102 object be heap allocated and owned by the trait object. 103 100 104 Extension: Multi-parameter Virtual Traits: 101 105 … … 157 161 context, for instance if the cast occurs on the right hand side of an 158 162 assignment. 163 164 Function look-up follows the same rules as relaxed (behavioural) inheritance. 165 Traits can be upcast and down cast without losing information unless the 166 trait is cast down to a structure. Here there are two options. 167 168 Abstraction Time Binding: The more efficient and consistant with other parts 169 of CFA. Only the trait types use dynamic look-up, if converveted back into a 170 structure the normal static look-up rules find the function at compile time. 171 Casting down to a structure type can then result in the loss of a set of 172 bindings. 173 Construction Time Binding: For more consistant handling of the virtual 174 structs, they are always considered wrapped. Functions are bound to the 175 instance the moment it is constructed and remain unchanged throughout its 176 lifetime, so down casting does not lose information. 177 178 (We will have to decide between one of these two.) 159 179 160 180 Extension: Multiple Parents … … 205 225 206 226 We have so far been silent on how the vtable is created, stored and accessed. 207 208 Creation happens at compile time. Function pointers are found by using the 209 same best match rules as elsewhere (additional rules for defaults from the 210 parent may or may not be required). For strict virtual this must happen at the 211 global scope and forbidding static functions, to ensure that a single unique 212 vtable is created. Similarly, there may have to be stricter matching rules 213 for the functions that go into the vtable, possibly requiring an exact match. 214 Relaxed virtual could relax both restrictions, if we allow different vtable 215 at different conversion (struct to trait reference) sites. If it is allowed 216 local functions being bound to a vtable could cause issues when they go out 217 of scope, however this should follow the lifetime rules most C programs 218 already follow implicitly. 219 220 Most vtables should be stored statically, the only exception being some of 221 the relaxed vtables that could have local function pointers. These may be able 222 to be stack allocated. All vtables should be immutable and require no manual 223 cleanup. 227 The vtables for the two types might be handled slightly differently and then 228 there is also the hierarchy data for virtual casts. 229 230 The hierarchy data is simple conceptually. A single (exactly one copy) pointer 231 for each type can act as the identity for it. The value of the pointer is 232 its parent type, with the root pointer being NULL. Additional meta-data 233 can accompany the parent pointer, such as a string name or the vtable fields. 234 235 They types of each vtable can be constructed from the definitions of the 236 traits (or internal nodes). The stand alone/base vtable is the same for both 237 kinds of inheritance. It may be argumented differently however (include parent 238 /this pointer in hierachal inheritance). 239 240 Creation of the actual vtable is tricky. For classical single implementation 241 semantics we would assemble the functions and create one vtable at compile 242 time. However, not only does this not give CFA-like behaviour, it is 243 impossible generally because types can satify assertions in different ways at 244 different times and stop satifying them. A special set of harder rules could 245 be used, instead we have decided to try creating multiple vtables for each 246 type. The different vtables will all implement the same type but not always 247 in the same way. 248 249 Storage has some issues from creation. If the contents of every vtable could 250 be determained at compile time they could all be created and stored 251 statically. However since thunks can be constructed on the stack and become 252 the best match, that isn't always possible. Those will have to be stored in 253 dynamic memory. Which means that all vtables must be stored dynamically or 254 there must be a way to determain which ones to free when the trait object is 255 destroyed. 224 256 225 257 Access has two main options:
Note: See TracChangeset
for help on using the changeset viewer.