Changeset a32346b for doc


Ignore:
Timestamp:
Sep 25, 2018, 4:56:55 PM (4 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
aaron-thesis, arm-eh, 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:
48b7085 (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.
Message:

Merge branch 'master' of plg2.cs.uwaterloo.ca:software/cfa/cfa-cc

Location:
doc
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • doc/bibliography/pl.bib

    r48b7085 ra32346b  
    701701% B
    702702
     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
    703717@incollection{beta:old,
    704718    keywords    = {beta, patterns, virtual types},
    … …  
    908922
    909923@misc{Cforall,
     924    contributer = {pabuhr@plg},
    910925    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}},
    913928    optnote     = {Accessed: 2018-01-01},
    914929}
    … …  
    926941
    927942@misc{CFAStackEvaluation,
     943    contributer = {a3moss@plg},
    928944    author      = {Aaron Moss},
    929945    title       = {\textsf{C}$\mathbf{\forall}$ Stack Evaluation Programs},
    … …  
    934950
    935951@article{Moss18,
    936     keywords    = {concurrency, C++},
     952    keywords    = {type systems, tuples, Cforall},
    937953    contributer = {pabuhr@plg},
    938954    author      = {Aaron Moss and Robert Schluntz and Peter A. Buhr},
    … …  
    941957    month       = aug,
    942958    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}},
    944960}
    945961
    … …  
    14171433}
    14181434
     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
    14191445@incollection{Reppy93,
    14201446    keywords    = {ML, concurrency, continuation passing},
    … …  
    14901516    month       = dec,
    14911517    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}},
    14931519}
    14941520
    … …  
    15571583}
    15581584
     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
    15591594@book{Andrews91:book,
    15601595    keywords    = {concurrency},
    … …  
    15811616
    15821617@mastersthesis{Delisle18,
     1618    keywords    = {concurrency, Cforall},
     1619    contributer = {pabuhr@plg},
    15831620    author      = {Thierry Delisle},
    15841621    title       = {Concurrency in \textsf{C}$\mathbf{\forall}$},
    15851622    school      = {School of Computer Science, University of Waterloo},
    15861623    year        = 2018,
    1587     address     = {Waterloo, Ontario, Canada, N2L 3G1},
     1624    optaddress  = {Waterloo, Ontario, Canada, N2L 3G1},
    15881625    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},
    15891637}
    15901638
    … …  
    28652913    keywords    = {concurrency, mutual exclusion, performance experiment, software solutions},
    28662914    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},
    28682916    journal     = ccpe,
    28692917    volume      = 30,
    … …  
    28722920    month       = feb,
    28732921    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}}
    28752923}
    28762924
    … …  
    32843332    edition     = {{S}imon {M}arlow},
    32853333    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}},
    32873335}
    32883336
    … …  
    33583406}
    33593407
    3360 @article{Hesselink17,
     3408@article{Hesselink17b,
    33613409    keywords    = {concurrency, mutual exclusion, performance experiment, software solutions},
    33623410    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},
    33643412    journal     = ccpe,
    33653413    volume      = 30,
    … …  
    33683416    month       = sep,
    33693417    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}},
    33713419}
    33723420
    … …  
    38463894
    38473895% 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}
    38483907
    38493908@article{Duggan96,
    … …  
    45344593% N
    45354594
     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
    45364605@article{Haddon77,
    45374606    keywords    = {monitors, nested monitor calls},
    … …  
    46574726    volume      = 9,
    46584727    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}},
    46594734}
    46604735
    … …  
    47694844@misc{obj-c-book,
    47704845    keywords    = {objective-c},
    4771     contributor = {a3moss@uwaterloo.ca},
     4846    contributor = {pabuhr@plg},
    47724847    key         = {Objective-C},
    4773     title       = {Objective-C},
     4848    author      = {Objective-C},
    47744849    publisher   = {Apple Inc.},
    4775     year        = 2015,
    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}},
    47774852    optnote     = {Accessed: 2018-03}
    47784853}
    … …  
    47844859    title       = {{X}code 7 Release Notes},
    47854860    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}},
    47874862    optnote     = {Accessed: 2017-04}
    47884863}
    … …  
    52845359}
    52855360
     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
    52865378@article{Anderson90,
    52875379    keywords    = {spin locks, back off, performance},
    … …  
    55045596    note        = {Proceedings of the OOPSLA'89 Conference, Oct. 1--6, 1989, New Orleans, Lousiana},
    55055597    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},
    55065614}
    55075615
    … …  
    59656073}
    59666074
     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
    59676088@article{Robinson48,
    59686089    keywords    = {recursion, Ackermann function},
    … …  
    60036124}
    60046125
     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
    60056137@article{Euclid,
    60066138    keywords    = {Euclid},
    … …  
    60346166    school      = {School of Computer Science, University of Waterloo},
    60356167    year        = 2017,
    6036     address     = {Waterloo, Ontario, Canada, N2L 3G1},
     6168    optaddress  = {Waterloo, Ontario, Canada, N2L 3G1},
    60376169    note        = {\href{https://uwspace.uwaterloo.ca/handle/10012/11830}{https://\-uwspace.uwaterloo.ca/\-handle/\-10012/\-11830}},
    60386170}
    … …  
    68616993    contributer = {pabuhr@plg},
    68626994    key         = {TIOBE Index},
    6863     title       = {{TIOBE} Index},
     6995    author      = {{TIOBE Index}},
    68646996    howpublished= {\href{http://www.tiobe.com/tiobe_index}{http://\-www.tiobe.com/\-tiobe\_index}},
    68656997    optnote     = {Accessed: 2018-09},
    … …  
    70017133    year        = 1980
    70027134}
     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}
    70037142 
    70047143@article{Leroy00,
    … …  
    71367275    title       = {Usability Challenges in Exception Handling},
    71377276    booktitle   = {5th International Workshop on Exception Handling (WEH)},
    7138     organization= {16th International Symposium on the Foundations of Software Engineering (FSE 16)},
     7277    optorganization= {16th International Symposium on the Foundations of Software Engineering (FSE 16)},
    71397278    address     = {Zurich, Switzerland},
    71407279    month       = jun,
    … …  
    72807419}
    72817420
     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
    72827434@techreport{Moss90,
    72837435    keywords    = {Swizzling, database},
    … …  
    73447496    year        = 1986,
    73457497    editor      = {Norman Meyrowitz},
    7346     publisher   = sigplan # " 21(11)",
     7498    publisher   = sigplan,
    73477499    organization= {Association for Computing Machinery},
    73487500    address     = {Portland, Oregon},
    7349     month       = sep # { 29}
     7501    month       = sep,
    73507502}
    73517503
    … …  
    73567508    year        = 1987,
    73577509    editor      = {Norman Meyrowitz},
    7358     publisher   = sigplan # " 22(12)",
     7510    publisher   = sigplan,
    73597511    organization= {Association for Computing Machinery},
    73607512    address     = {Orlando, Florida},
    7361     month       = oct # { 4--8}
     7513    month       = oct,
    73627514}
    73637515
    … …  
    73687520    year        = 1988,
    73697521    editor      = {Norman Meyrowitz},
    7370     publisher   = sigplan # " 23(11)",
     7522    publisher   = sigplan,
    73717523    organization= {Association for Computing Machinery},
    73727524    address     = {San Diego, California},
    7373     month       = sep # { 25--30}
     7525    month       = sep,
    73747526}
    73757527
    … …  
    73807532    year        = 1989,
    73817533    editor      = {Norman Meyrowitz},
    7382     publisher   = sigplan # " 24(10)",
     7534    publisher   = sigplan,
    73837535    organization= {Association for Computing Machinery},
    73847536    address     = {New Orleans, Louisiana},
    7385     month       = oct # { 1--6}
     7537    month       = oct,
    73867538}
    73877539
    … …  
    73927544    year        = 1990,
    73937545    editor      = {Norman Meyrowitz},
    7394     publisher   = sigplan # " 25(10)",
     7546    publisher   = sigplan,
    73957547    organization= {Association for Computing Machinery},
    73967548    address     = {Ottawa, Canada},
    7397     month       = oct # { 21--25}
     7549    month       = oct,
    73987550}
    73997551
    … …  
    74047556    year        = 1991,
    74057557    editor      = {Andreas Paepcke},
    7406     publisher   = sigplan # " 26(11)",
     7558    publisher   = sigplan,
    74077559    organization= {Association for Computing Machinery},
    74087560    address     = {Phoenix, Arizona},
    7409     month       = oct # { 6--11}
    7410 }
     7561    month       = oct,
     7562}

  • doc/proposals/virtual.txt

    r48b7085 ra32346b  
    8787first polymorphic parameter).
    8888
    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.
     89Instances of a trait are created by wrapping an existing instance of a type
     90that implements that trait. This wrapper includes all the function pointers
     91and other values required to preform the dynamic look-up. These are chosen by
     92the normal look-up rules at the point of abstraction.
    9393
    9494One of the limitations of this design is that it does not support double
    … …  
    9898is also restricted, initially forbidden, see extension.
    9999
     100Ownership of the underlying structure is also a bit of a trick. Considering
     101the use cases for trait object, it is probably best to have the underlying
     102object be heap allocated and owned by the trait object.
     103
    100104Extension: Multi-parameter Virtual Traits:
    101105
    … …  
    157161context, for instance if the cast occurs on the right hand side of an
    158162assignment.
     163
     164Function look-up follows the same rules as relaxed (behavioural) inheritance.
     165Traits can be upcast and down cast without losing information unless the
     166trait is cast down to a structure. Here there are two options.
     167
     168  Abstraction Time Binding: The more efficient and consistant with other parts
     169of CFA. Only the trait types use dynamic look-up, if converveted back into a
     170structure the normal static look-up rules find the function at compile time.
     171Casting down to a structure type can then result in the loss of a set of
     172bindings.
     173  Construction Time Binding: For more consistant handling of the virtual
     174structs, they are always considered wrapped. Functions are bound to the
     175instance the moment it is constructed and remain unchanged throughout its
     176lifetime, so down casting does not lose information.
     177
     178(We will have to decide between one of these two.)
    159179
    160180Extension: Multiple Parents
    … …  
    205225
    206226We 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.
     227The vtables for the two types might be handled slightly differently and then
     228there is also the hierarchy data for virtual casts.
     229
     230The hierarchy data is simple conceptually. A single (exactly one copy) pointer
     231for each type can act as the identity for it. The value of the pointer is
     232its parent type, with the root pointer being NULL. Additional meta-data
     233can accompany the parent pointer, such as a string name or the vtable fields.
     234
     235They types of each vtable can be constructed from the definitions of the
     236traits (or internal nodes). The stand alone/base vtable is the same for both
     237kinds of inheritance. It may be argumented differently however (include parent
     238/this pointer in hierachal inheritance).
     239
     240Creation of the actual vtable is tricky. For classical single implementation
     241semantics we would assemble the functions and create one vtable at compile
     242time. However, not only does this not give CFA-like behaviour, it is
     243impossible generally because types can satify assertions in different ways at
     244different times and stop satifying them. A special set of harder rules could
     245be used, instead we have decided to try creating multiple vtables for each
     246type. The different vtables will all implement the same type but not always
     247in the same way.
     248
     249Storage has some issues from creation. If the contents of every vtable could
     250be determained at compile time they could all be created and stored
     251statically. However since thunks can be constructed on the stack and become
     252the best match, that isn't always possible. Those will have to be stored in
     253dynamic memory. Which means that all vtables must be stored dynamically or
     254there must be a way to determain which ones to free when the trait object is
     255destroyed.
    224256
    225257Access has two main options:
Note: See TracChangeset for help on using the changeset viewer.