- Timestamp:
- Apr 5, 2026, 9:25:22 AM (22 hours ago)
- Branches:
- master
- Parents:
- e78d969
- File:
-
- 1 edited
-
doc/theses/mike_brooks_MMath/list.tex (modified) (29 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/theses/mike_brooks_MMath/list.tex
re78d969 rbb9897c 30 30 In the example, there are implicit conversions from @S@ to @U@ and @S@ to @W@, extracting the appropriate value or pointer for the substructure. 31 31 \VRef[Figure]{f:DiamondInheritancePattern} shows complex multiple inheritance patterns are possible, like the \newterm{diamond pattern}~\cite[\S~6.1]{Stroustrup89}\cite[\S~4]{Cargill91}. 32 Currently, \CFA type-system does not support @virtual@ inheritance.32 Currently, the \CFA type-system does not support @virtual@ inheritance. 33 33 34 34 \begin{figure} … … 55 55 struct R : @public B@ { int r, w; }; 56 56 struct T : @public L, R@ { int t; }; 57 57 T 58 B L B R 58 59 T t = { { { 5 }, 3, 4 }, { { 8 }, 6, 7 }, 3 }; 59 60 t.t = 42; … … 68 69 struct R { @inline B;@ int r, w; }; 69 70 struct T { @inline L; inline R;@ int t; }; 70 71 T 72 B L B R 71 73 T t = { { { 5 }, 3, 4 }, { { 8 }, 6, 7 }, 3 }; 72 74 t.t = 42; … … 88 90 \subsection{Core Design Issues} 89 91 90 The doubly-linked list attaches links intrusively , supports multiple link axes, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head.92 The doubly-linked list attaches links intrusively in a node, allows a node to appear on multiple lists (axes) simultaneously, integrates with user code via the type system, treats its ends uniformly, and identifies a list using an explicit head. 91 93 This design covers system and data management issues stated in \VRef{toc:lst:issue}. 92 94 … … 128 130 \end{figure} 129 131 130 \VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node can be on one or more lists simultaneously (axes).132 \VRef[Figure]{fig:lst-features-multidir} shows how the \CFA library supports multi-inline links, so a node has multiple axes. 131 133 The declaration of @req@ has two inline-inheriting @dlink@ occurrences. 132 134 The first of these gives a type named @req.by_pri@, @req@ inherits from it, and it inherits from @dlink@. … … 135 137 136 138 The declarations of the list-head objects, @reqs_pri@, @reqs_rqr_42@, @reqs_rqr_17@, and @reqs_rqr_99@, bind which link nodes in @req@ are used by this list. 137 Hence, the type of the variable @reqs_pri@, @dlist(req, req.by_pri)@, means operations calledon @reqs_pri@ implicitly select (disambiguate) the correct @dlink@s, \eg the calls @insert_first(reqs_pri, ...)@ imply, ``here, we are working by priority.''139 Hence, the type of the variable @reqs_pri@, @dlist(req, req.by_pri)@, means operations on @reqs_pri@ implicitly select (disambiguate) the correct @dlink@s, \eg the calls @insert_first(reqs_pri, ...)@ imply, ``here, we are working by priority.'' 138 140 As in \VRef[Figure]{fig:lst-issues-multi-static}, three lists are constructed, a priority list containing all nodes, a list with only nodes containing the value 42, and a list with only nodes containing the value 17. 139 141 140 142 \begin{figure} 141 143 \centering 144 142 145 \begin{tabular}{@{}ll@{}} 143 \begin{tabular}{@{}l@{}} 144 \lstinput{20-31}{lst-features-multidir.run.cfa} \\ 145 \lstinput{43-71}{lst-features-multidir.run.cfa} 146 \end{tabular} 147 & 148 \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c} 146 \multicolumn{1}{c}{\CFA} & \multicolumn{1}{c}{C} \\ 147 \begin{tabular}{@{}l@{}} 148 \lstinput{20-31}{lst-features-multidir.run.cfa} \\ 149 \lstinput{43-71}{lst-features-multidir.run.cfa} 149 150 \end{tabular} 151 & 152 \lstinput[language=C++]{20-60}{lst-issues-multi-static.run.c} 153 \end{tabular} 150 154 151 155 \caption{ 152 153 154 155 156 156 Demonstration of multiple static link axes done in the \CFA list library. 157 The right example is from \VRef[Figure]{fig:lst-issues-multi-static}. 158 The left \CFA example does the same job. 159 } 160 \label{fig:lst-features-multidir} 157 161 \end{figure} 158 162 … … 200 204 Finally, the library is separately compiled from the usage code, modulo inlining. 201 205 202 The \CFA library works in headed and headless modes.203 \PAB{TODO: elaborate.}204 205 206 206 207 \section{List API} … … 209 210 \begin{itemize}[leftmargin=*] 210 211 \item 211 @ isListed@ returns true if the node is an element of a list and false otherwise.212 \item 213 @ isEmpty@ returns true if the list has no nodes and false otherwise.212 @listed@ returns true if the node is an element of a list and false otherwise. 213 \item 214 @empty@ returns true if the list has no nodes and false otherwise. 214 215 \item 215 216 @first@ returns a reference to the first node of the list without removing it or @0p@ if the list is empty. … … 231 232 @advance@ returns true if the iterator cursor is advanced to the next (successor, towards last) node after the prior cursor node and false otherwise. 232 233 \item 233 @ isFirst@ returns true if the node is the first node in the list and false otherwise.234 \item 235 @ isLast@ returns true if the node is the last node in the list and false otherwise.234 @first@ returns true if the node is the first node in the list and false otherwise. 235 \item 236 @last@ returns true if the node is the last node in the list and false otherwise. 236 237 \item 237 238 @pred@ returns a reference to the previous (predecessor, towards first) node before a specified node or @0p@ if a specified node is the first node in the list. … … 252 253 The node must be in the @from@ list. 253 254 \end{itemize} 255 For operations @insert_*@, @insert@, and @remove@, a variable-sized list of nodes can be specified using \CFA's tuple type~\cite[\S~4.7]{Moss18} (not discussed), \eg @insert( list, n1, n2, n3 )@, recursively invokes @insert( list, n@$_i$@ )@.\footnote{ 256 Currently, a resolver bug between tuple types and references means tuple routines must use pointer parameters. 257 Nevertheless, the imaginary reference versions are used here as the code is cleaner, \eg no \lstinline{&} on call arguments.} 254 258 255 259 \begin{figure} 256 260 \begin{cfa} 257 E & isListed( E & node );258 E & isEmpty( dlist( E ) & list );261 E & listed( E & node ); 262 E & empty( dlist( E ) & list ); 259 263 E & first( dlist( E ) & list ); 260 264 E & last( dlist( E ) & list ); … … 265 269 bool advance( E && refx ); 266 270 bool recede( E && refx ); 267 bool isFirst( E & node );268 bool isLast( E & node );271 bool first( E & node ); 272 bool last( E & node ); 269 273 E & prev( E & node ); 270 274 E & next( E & node ); 271 275 E & insert_first( dlist( E ) & list, E & node ); 272 E & insert_last( dlist( E ) & list, E & node ); 276 E & insert_last( dlist( E ) & list, E & node ); // synonym insert 273 277 E & remove_first( dlist( E ) & list ); 274 278 E & remove_last( dlist( E ) & list ); … … 284 288 285 289 It is possible to iterate through a list manually or using a set of standard macros. 286 \VRef[Figure]{f:Iterator Temple} shows the iterator template, managing a list of nodes, used throughout the following iterator examples.290 \VRef[Figure]{f:IteratorDriver} shows the iterator outline, managing a list of nodes, used throughout the following iterator examples. 287 291 Each example assumes its loop body prints the value in the current node. 288 292 … … 291 295 #include <fstream.hfa> 292 296 #include <list.hfa> 293 294 297 struct node { 295 298 int v; … … 299 302 dlist(node) list; 300 303 node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 }; 301 insert( list, n1 ); insert( list, n2 ); insert( list, n3 ); insert( list, n4 );304 insert( list, n1, n2, n3, n4 ); $\C{// insert in any order}$ 302 305 sout | nlOff; 303 for ( ... ) @sout | it.v | ","; sout | nl;@ // iterator examples in text304 remove( n1 ); remove( n2 ); remove( n3 ); remove( n4 );306 @for ( ... )@ sout | it.v | ","; sout | nl; $\C{// iterator examples in text}$ 307 remove( n1, n2, n3, n4 ); $\C{// remove in any order}$ 305 308 } 306 309 \end{cfa} 307 \caption{Iterator Temple}308 \label{f:Iterator Temple}310 \caption{Iterator Driver} 311 \label{f:IteratorDriver} 309 312 \end{figure} 310 313 … … 361 364 \end{tabular} 362 365 \end{cquote} 363 Iterating forward and reverse through the entire list using the shorthand start at the list head and pick a axis.366 Iterating forward and reverse through the entire list using the shorthand start at the list head and pick an axis. 364 367 In this case, @advance@ and @recede@ return a boolean, like \CC @while ( cin >> i )@. 365 368 \begin{cquote} … … 496 499 With this change, both @begin ~ end@ and @end@ (in context of the latter ``two-place for'' expression) parse as \emph{ranges}, and the loop syntax becomes, simply: 497 500 \begin{cfa} 498 501 for( elem; rangeExpr ) 499 502 \end{cfa} 500 503 The expansion and underlying API are under discussion. … … 517 520 518 521 522 \section[C++ Lists]{\CC Lists} 523 524 It is worth addressing two API issues in \CC lists avoided in \CFA. 525 First, \CC lists require two steps to remove a node versus one in \CFA. 526 \begin{cquote} 527 \begin{tabular}{@{}ll@{}} 528 \multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{\CFA} \\ 529 \begin{c++} 530 list<node> li; 531 node n = li.first(); // assignment could raise exception 532 li.pop_front(); 533 \end{c++} 534 & 535 \begin{cfa} 536 dlist(node) list; 537 node n = remove_first( list ); 538 539 \end{cfa} 540 \end{tabular} 541 \end{cquote} 542 The argument for two steps is exception safety: returning an unknown T by value/move might throw an exception from T's copy/move constructor. 543 Hence, to be \emph{exception safe}, all internal list operations must complete before the copy/move so the list is consistent should the return fail. 544 This coding style can result in contrived code, but is usually possible; 545 however, it requires the container designer to anticipate the potential throw. 546 (Note, this anticipation issue is pervasive in exception systems, not just with containers.) 547 The solution moves the coding complexity from the container designer to the programer~\cite[ch~10, part 3]{Sutter99}. 548 First, obtain the node, which might fail, but the container is unmodified. 549 Second, remove the node, which modifies the container without the possibly of an exception. 550 This movement of responsibility increases the cognitive effort for programmers. 551 Unfortunately, this \emph{single-responsibility principle}, \ie preferring separate operations, is often repeated as a necessary requirement rather an an optional one. 552 Separate operations should always be available, but their composition should also be available. 553 Interestingly, this issue does not apply to intrusive lists, because the node data is never copied/moved in or out of a list; 554 only the link fields are accessed in list operations. 555 556 Second, \VRef[Figure]{f:CCvsCFAListIssues} shows an example where a \CC list operation is $O(N$) rather than $O(1)$ in \CFA. 557 This issue is inherent to wrapped (non-intrusive) lists. 558 Specifically, to remove a node requires access to the links that materialize its membership. 559 In a wrapped list, there is no access from node to links, and for abstract reasons, no direct pointers to wrapped nodes, so the links must be found indirectly by navigating the list. 560 The \CC iterator is the abstraction to navigate wrapped links. 561 So an iterator is needed, not because it offers go-next, but for managing the list membership. 562 Note, attempting to keep an array of iterators to each node requires high-complexity to ensure the list and array are harmonized. 563 564 \begin{figure} 565 \begin{tabular}{@{}ll@{}} 566 \multicolumn{1}{c}{\CC} & \multicolumn{1}{c}{\CFA} \\ 567 \begin{c++} 568 list<node *> list; 569 node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 }; 570 list.push_back( &n1 ); list.push_back( &n2 ); 571 list.push_back( &n3 ); list.push_back( &n4 ); 572 list<node *>::iterator it; 573 for ( it = list.begin(); it != list.end(); it ++ ) 574 if ( *it == &n3 ) { dl.erase( it ); break; } 575 \end{c++} 576 & 577 \begin{cfa} 578 dlist(node) list; 579 node n1 = { 1 }, n2 = { 2 }, n3 = { 3 }, n4 = { 4 }; 580 insert( list, n1, n2, n3, n4 ); 581 582 583 584 remove( list, n3 ); 585 \end{cfa} 586 \end{tabular} 587 \caption{\CC \vs \CFA List Issues} 588 \label{f:CCvsCFAListIssues} 589 \end{figure} 590 591 \begin{comment} 592 Dave Dice: 593 There are what I'd call the "dark days" of C++, where the language \& libraries seemed to be getting progressively uglier - requiring more tokens to express something simple, and lots of arcana. 594 But over time, somehow, they seem to have mostly righted the ship and now I can write C++ code that's fairly terse, like python, by ignoring all the old constructs. 595 (They carry around the legacy baggage, of course, but seemed to have found a way to evolve away from it). 596 597 If you just want to traverse a std::list, then, using modern "for" loops, you never need to see an iterator. 598 I try hard never to need to write X.begin() or X.end(). 599 (There are situations where I'll expose iterators for my own types, however, to enable modern "for" loops). 600 If I'm implementing simple linked lists, I'll usually skip std:: collections and do it myself, as it's less grief. 601 I just don't get that much advantage from std::list. And my code is certainly not any shorter. 602 On the other hand, @std::map@, @unordered_map@, @set@, and friends, are terrific, and I can usually still avoid seeing any iterators, which are blight to the eye. 603 So those are a win and I get to move up an abstraction level, and write terse but easily understood code that still performs well. 604 (One slight concern here is that all the C++ collection/container code is templated and lives in include files, and not traditional libraries. 605 So the only way to replace something - say with a better algorithm, or you have a bug in the collections code - is to boil the oceans and recompile everything. 606 But on the other hand the compiler can specialize to the specific use case, which is often a nice performance win). 607 608 And yeah, the method names are pretty terrible. I think they boxed themselves in early with a set of conventions that didn't age well, and they tried to stick with it and force regularity over the collection types. 609 610 I've never seen anything written up about the history, although lots of the cppcon talks make note of the "bad old days" idea and how collection \& container library design evolved. The issue is certainly recognized. 611 \end{comment} 612 613 519 614 \section{Implementation} 520 615 521 \VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, nowshowing the \CFA list library's internal representation.616 \VRef[Figure]{fig:lst-impl-links} continues the running @req@ example, showing the \CFA list library's internal representation. 522 617 The @dlink@ structure contains exactly two pointers: @next@ and @prev@, which are opaque. 523 Even though the user-facing list model is linear, the CFA library implements all listing as circular. 524 This choice helps achieve uniform end treatment and \PAB{TODO finish summarizing benefit}. 618 Even though the user-facing list model is linear, the \CFA library implements all listing as circular. 619 This choice helps achieve uniform end treatment. 620 % and \PAB{TODO finish summarizing benefit}. 525 621 A link pointer targets a neighbouring @dlink@ structure, rather than a neighbouring @req@. 526 622 (Recall, the running example has the user putting a @dlink@ within a @req@.) … … 530 626 \includegraphics[width=\textwidth]{lst-impl-links.pdf} 531 627 \caption{ 532 \CFA list library representations for the cases under discussion.628 \CFA list library representations for headed and headless lists. 533 629 } 534 630 \label{fig:lst-impl-links} … … 540 636 Hence, the tags are set on the links that a user cannot navigate. 541 637 638 The \CFA library works in headed and headless modes. 542 639 In a headed list, the list head (@dlist(req)@) acts as an extra element in the implementation-level circularly-linked list. 543 640 The content of a @dlist@ header is a (private) @dlink@, with the @next@ pointer to the first element, and the @prev@ pointer to the last element. … … 567 664 568 665 This experiment takes the position that: 569 \begin{itemize} 570 571 666 \begin{itemize}[leftmargin=*] 667 \item The total time to add and remove is relevant \vs individual times for add and remove. 668 Adds without removes quickly fill memory; 572 669 removes without adds is meaningless. 573 670 \item A relevant breakdown ``by operation'' is: 574 671 \begin{description} 575 672 \item[movement] 576 673 Is the add/remove applied to a stack, queue, or something else? 577 674 \item[polarity] 578 675 In which direction does the action apply? … … 580 677 For a stack, is the first or last end used for adding and removing? 581 678 \item[accessor] 582 Is an add/remove location given by a list head's ``first''/``last'', or by a reference to an individual element?679 Is an add/remove location given by a list head's first/last, or by a reference to an individual element? 583 680 \end{description} 584 585 681 \item Speed differences caused by the host machine's memory hierarchy need to be identified and explained, 682 but do not represent advantages of one linked-list implementation over another. 586 683 \end{itemize} 587 684 … … 592 689 The experiment is sensitive enough to show: 593 690 \begin{itemize} 594 595 691 \item intrusive lists performing (majorly) differently than wrapped lists, 692 \item a space of (minor) performance differences among the intrusive lists. 596 693 \end{itemize} 597 694 … … 637 734 To test list operations, the experiment performs the inserts/removes in different patterns, \eg insert and remove from front, insert from front and remove from back, random insert and remove, \etc. 638 735 Unfortunately, the @std::list@ does \emph{not} support direct insert/remove from a node without an iterator, \ie no @erase( node )@, even though the list is doubly-linked. 639 To eliminate the iterator, a trick is used for random insertions without replacement .736 To eliminate the iterator, a trick is used for random insertions without replacement, which takes advantage of the array nature of the nodes. 640 737 The @i@ fields in each node are initialized from @0..n-1@. 641 738 These @i@ values are then shuffled in the nodes, and the @i@ value is used to represent an indirection to that node for insertion. … … 761 858 & 762 859 \subfloat[Linear List Nodes, AMD]{\label{f:Linear-swift} 763 764 860 \hspace*{-0.75in} 861 \includegraphics{plot-list-zoomout-noshuf-swift.pdf} 765 862 } % subfigure 766 863 & 767 864 \subfloat[Linear List Nodes, Intel]{\label{f:Linear-java} 768 865 \includegraphics{plot-list-zoomout-noshuf-java.pdf} 769 866 } % subfigure 770 867 \\ 771 868 & 772 869 \subfloat[Shuffled List Nodes, AMD]{\label{f:Shuffled-swift} 773 774 870 \hspace*{-0.75in} 871 \includegraphics{plot-list-zoomout-shuf-swift.pdf} 775 872 } % subfigure 776 873 & 777 874 \subfloat[Shuffled List Nodes, Intel]{\label{f:Shuffled-java} 778 875 \includegraphics{plot-list-zoomout-shuf-java.pdf} 779 876 } % subfigure 780 877 \end{tabular} … … 868 965 & 869 966 \subfloat[Absolute Time, AMD]{\label{f:AbsoluteTime-swift} 870 871 967 \hspace*{-0.75in} 968 \includegraphics{plot-list-zoomin-abs-swift.pdf} 872 969 } % subfigure 873 970 & 874 971 \subfloat[Absolute Time, Intel]{\label{f:AbsoluteTime-java} 875 972 \includegraphics{plot-list-zoomin-abs-java.pdf} 876 973 } % subfigure 877 974 \\ 878 975 & 879 976 \subfloat[Relative Time, AMD]{\label{f:RelativeTime-swift} 880 881 977 \hspace*{-0.75in} 978 \includegraphics{plot-list-zoomin-rel-swift.pdf} 882 979 } % subfigure 883 980 & 884 981 \subfloat[Relative Time, Intel]{\label{f:RelativeTime-java} 885 982 \includegraphics{plot-list-zoomin-rel-java.pdf} 886 983 } % subfigure 887 984 \end{tabular} … … 914 1011 & 915 1012 \subfloat[Supersets, AMD]{\label{f:Superset-swift} 916 917 1013 \hspace*{-0.75in} 1014 \includegraphics{plot-list-cmp-exout-swift.pdf} 918 1015 } % subfigure 919 1016 & 920 1017 \subfloat[Supersets, Intel]{\label{f:Superset-java} 921 1018 \includegraphics{plot-list-cmp-exout-java.pdf} 922 1019 } % subfigure 923 1020 \\ 924 1021 & 925 1022 \subfloat[1st Level Slice, AMD]{\label{f:1stLevelSlice-swift} 926 927 1023 \hspace*{-0.75in} 1024 \includegraphics{plot-list-cmp-survey-swift.pdf} 928 1025 } % subfigure 929 1026 & 930 1027 \subfloat[1st Level Slice, Intel]{\label{f:1stLevelSlice-java} 931 1028 \includegraphics{plot-list-cmp-survey-java.pdf} 932 1029 } % subfigure 933 1030 \end{tabular} … … 981 1078 982 1079 \begin{comment} 983 \subsection{Result: CFA cost attribution}1080 \subsection{Result: \CFA cost attribution} 984 1081 985 1082 This comparison loosely itemizes the reasons that the \CFA implementation runs 15--20\% slower than LQ. … … 1078 1175 \label{toc:lst:futwork} 1079 1176 1080 The \CFA list examples elide the \lstinline{P9_EMBEDDED} annotations that (TODO: xref P9E future work) proposes to obviate. 1177 Not discussed in the chapter is an issue in the \CFA type system with Plan-9 @inline@ declarations. 1178 It implements the trait 'embedded' for the derived-base pair named in the arguments. 1179 This trait defines a pseudo conversion called backtick-inner, from derived to base (the safe direction). 1180 Such a real conversion exists for the concrete types, due to our compiler having the p9 language feature. 1181 But when trying to be polymorphic over the types, there is no way to access this built-in conversion, so my macro stands in until Fangren does more with conversions. 1182 1183 An API author has decided that the intended user experience is: 1184 \begin{itemize} 1185 \item 1186 offer the user an opaque type that abstracts the API's internal state 1187 \item 1188 tell the user to extend this type 1189 \item 1190 provide functions with a ``user's type in, user's type out'' style 1191 \end{itemize} 1192 Fig XXX shows several attempts to provide this experience. 1193 The types in (a) give the setup, achieving the first two points, while the pair of function declarations and calls of (b) are unsuccessful attempts at achieving the third point. 1194 Both functions @f1@ and @f2@ allow calls of the form @f( d )@, but @f1@ has the wrong return type (@Base@) for initializing a @Derived@. 1195 The @f1@ signature fails to meet ``user's type out;'' this signature does not give the \emph{user} a usable type. 1196 On the other hand, the signature @f2@ offers the desired user experience, so the API author proceeds with trying to implement it. 1197 1198 \begin{figure} 1199 \begin{cfa} 1200 #ifdef SHOW_ERRS 1201 #define E(...) __VA_ARGS__ 1202 #else 1203 #define E(...) 1204 #endif 1205 1206 // (a) 1207 struct Base { /*...*/ }; // system offers 1208 struct Derived { /*...*/ inline Base; }; // user writes 1209 1210 // (b) 1211 // system offers 1212 Base & f1( Base & ); 1213 forall( T ) T & f2( T & ); 1214 // user writes 1215 void to_elide1() { 1216 Derived & d /* = ... */; 1217 f1( d ); 1218 E( Derived & d1 = f1( d ); ) // error: return is not Derived 1219 Derived & d2 = f2( d ); 1220 1221 // (d), user could write 1222 Base & b = d; 1223 } 1224 1225 // (c), system has 1226 static void helper( Base & ); 1227 forall( T ) T & f2( T & param ) { 1228 E( helper( param ); ) // error: param is not Base 1229 return param; 1230 } 1231 static void helper( Base & ) {} 1232 1233 #include <list2.hfa> 1234 // (e) 1235 // system offers, has 1236 forall( T | embedded(T, Base, Base) ) 1237 T & f3( T & param ) { 1238 helper( param`inner ); // ok 1239 return param; 1240 } 1241 // user writes 1242 struct DerivedRedux { /*...*/ inline Base; }; 1243 P9_EMBEDDED( DerivedRedux, Base ) 1244 void to_elide2() { 1245 DerivedRedux & dr /* = ... */; 1246 DerivedRedux & dr3 = f3( dr ); 1247 1248 // (f) 1249 // user writes 1250 Derived & xxx /* = ... */; 1251 E( Derived & yyy = f3( xxx ); ) // error: xxx is not embedded 1252 } 1253 \end{cfa} 1254 \end{figure} 1255 1256 1257 The \CFA list examples elide the @P9_EMBEDDED@ annotations that (TODO: xref P9E future work) proposes to obviate. 1081 1258 Thus, these examples illustrate a to-be state, free of what is to be historic clutter. 1082 1259 The elided portions are immaterial to the discussion and the examples work with the annotations provided. … … 1110 1287 P9_EMBEDDED(fred.yours, dlink(fred)) 1111 1288 \end{cfa} 1289 1290 1291 The function definition in (c) gives this system-implementation attempt. 1292 The system needs to operate on its own data, stored in the @Base@ part of the user's @d@, now called @param@. 1293 Calling @helper@ represents this attempt to look inside. 1294 It fails, because the @f2@ signature does not state that @param@ has any relationship to @Base@; 1295 this signature does not give the \emph{system} a usable type. 1296 The fact that the user's argument can be converted to @Base@ is lost when going through this signature. 1297 1298 Moving forward needs an @f@ signature that conveys the relationship that the argument @d@ has to @Base@. 1299 \CFA conveys type abilities, from caller to callee, by way of traits; so the challenge is to state the right trait member. 1300 As initialization (d) illustrates, the @d@--@Base@ capability is an implicit conversion. 1301 Unfortunately, in present state, \CFA does not have a first-class representation of an implicit conversion, the way operator @?{}@ (which is a value), done with the right overload, is arguably an explicit conversion. 1302 So \CFA cannot directly convey ``@T@ compatible with @Base@'' in a trait. 1303 1304 This work contributes a stand-in for such an ability, tunneled through the present-state trait system, shown in (e). 1305 On the declaration/system side, the trait @embedded@, and its member, @`inner@, convey the ability to recover the @Base@, and thereby call @helper@. 1306 On the user side, the @P9_EMBEDDED@ macro accompanies type definitions that work with @f3@-style declarations. 1307 An option is presemt-state-available to compiler-emit @P9_EMBEDDED@ annotations automatically, upon each occurrence of an `inline` member. 1308 The choice not to is based on conversions in \CFA being a moving target because of separate, ongoing work. 1309 1310 An intended finished state for this area is achieved if \CFA's future efforts with conversions include: 1311 \begin{itemize} 1312 \item 1313 treat conversion as operator(s), \ie values 1314 \item 1315 re-frame the compiler's current Plan-9 ``magic'' as seeking an implicit conversion operator, rather than seeking an @inline@ member 1316 \item 1317 make Plan-9 syntax cause an implementation of implicit conversion to exist (much as @struct@ syntax causes @forall(T)@ compliance to exist) 1318 \end{itemize} 1319 To this end, the contributed @P9_EMBEDDED@ expansion shows how to implement this conversion. 1320 1321 1112 1322 like in tests/list/dlist-insert-remove. 1113 1323 Future work should autogen those @P9_EMBEDDED@ declarations whenever it sees a plan-9 declaration.
Note:
See TracChangeset
for help on using the changeset viewer.
