Changes in / [e61de5b:ab0203df]
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Paper.tex
re61de5b rab0203df 267 267 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}$ 268 268 \end{cfa} 269 270 269 \CFA maximizes the ability to reuse names to aggressively address the naming problem. 271 270 In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction. … … 286 285 287 286 288 \subsection{\texorpdfstring{\ protect\lstinline{forall} Functions}{forall Functions}}287 \subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}} 289 288 \label{sec:poly-fns} 290 289 … … 436 435 One approach is to write bespoke data-structures for each context in which they are needed. 437 436 While this approach is flexible and supports integration with the C type-checker and tooling, it is also tedious and error-prone, especially for more complex data structures. 438 A second approach is to use @void *@ 437 A second approach is to use @void *@--based polymorphism, \eg the C standard-library functions @bsearch@ and @qsort@, which allow reuse of code with common functionality. 439 438 However, basing all polymorphism on @void *@ eliminates the type-checker's ability to ensure that argument types are properly matched, often requiring a number of extra function parameters, pointer indirection, and dynamic allocation that is not otherwise needed. 440 439 A third approach to generic code is to use preprocessor macros, which does allow the generated code to be both generic and type-checked, but errors may be difficult to interpret. … … 509 508 If a dynamic generic-type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume the generic type is complete (\ie has a known layout) at any call-site, and the offset array is passed from the caller; 510 509 if the generic type is concrete at the call site, the elements of this offset array can even be statically generated using the C @offsetof@ macro. 511 As an example, the body of the second @value@ function is implemented as:512 \begin{cfa} 513 _assign_T( _retval, p + _offsetof_pair[1]); $\C{// return *p.second}$514 \end{cfa} 515 @_assign_T@ is passed in as an implicit parameter from @otype T@, and takes two @T *@ (@void*@ in the generated code), a destination and a source; @_retval@ is the pointer to a caller-allocated buffer for the return value, the usual \CFA method to handle dynamically-sized return types.510 As an example, the body of the second @value@ function is implemented like this: 511 \begin{cfa} 512 _assign_T(_retval, p + _offsetof_pair[1]); $\C{// return *p.second}$ 513 \end{cfa} 514 @_assign_T@ is passed in as an implicit parameter from @otype T@, and takes two @T*@ (@void*@ in the generated code), a destination and a source; @_retval@ is the pointer to a caller-allocated buffer for the return value, the usual \CFA method to handle dynamically-sized return types. 516 515 @_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as: 517 516 \begin{cfa} 518 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second) }517 size_t _offsetof_pair[] = { offsetof(_pair_conc0, first), offsetof(_pair_conc0, second) } 519 518 \end{cfa} 520 519 … … 540 539 The most important such pattern is using @forall(dtype T) T *@ as a type-checked replacement for @void *@, \eg creating a lexicographic comparison for pairs of pointers used by @bsearch@ or @qsort@: 541 540 \begin{cfa} 542 forall( dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {541 forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) { 543 542 return cmp( a->first, b->first ) ? : cmp( a->second, b->second ); 544 543 } 545 544 \end{cfa} 546 Since @pair( 545 Since @pair(T *, T * )@ is a concrete type, there are no implicit parameters passed to @lexcmp@, so the generated code is identical to a function written in standard C using @void *@, yet the \CFA version is type-checked to ensure the fields of both pairs and the arguments to the comparison function match in type. 547 546 548 547 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}. 549 548 Sometimes information is only used for type-checking and can be omitted at runtime, \eg: 550 549 \begin{cfa} 551 forall( dtype Unit) struct scalar { unsigned long value; };550 forall(dtype Unit) struct scalar { unsigned long value; }; 552 551 struct metres {}; 553 552 struct litres {}; 554 553 555 forall( 554 forall(dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) { 556 555 return (scalar(U)){ a.value + b.value }; 557 556 } … … 808 807 Due to the implicit flattening and structuring conversions involved in argument passing, @otype@ and @dtype@ parameters are restricted to matching only with non-tuple types, \eg: 809 808 \begin{cfa} 810 forall( otype T, dtype U) void f( T x, U * y );809 forall(otype T, dtype U) void f( T x, U * y ); 811 810 f( [5, "hello"] ); 812 811 \end{cfa} … … 815 814 For example, a plus operator can be written to add two triples together. 816 815 \begin{cfa} 817 forall( otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {816 forall(otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) { 818 817 return [x.0 + y.0, x.1 + y.1, x.2 + y.2]; 819 818 } … … 826 825 \begin{cfa} 827 826 int f( [int, double], double ); 828 forall( otype T, otype U | { T f( T, U, U ); }) void g( T, U );827 forall(otype T, otype U | { T f( T, U, U ); }) void g( T, U ); 829 828 g( 5, 10.21 ); 830 829 \end{cfa} … … 853 852 \begin{cfa} 854 853 int sum$\(_0\)$() { return 0; } 855 forall( 854 forall(ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) { 856 855 return x + sum( rest ); 857 856 } … … 866 865 \begin{cfa} 867 866 int sum( int x, int y ) { return x + y; } 868 forall( 867 forall(ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) { 869 868 return sum( x + y, rest ); 870 869 } … … 872 871 One more step permits the summation of any summable type with all arguments of the same type: 873 872 \begin{cfa} 874 trait summable( otype T) {873 trait summable(otype T) { 875 874 T ?+?( T, T ); 876 875 }; 877 forall( 876 forall(otype R | summable( R ) ) R sum( R x, R y ) { 878 877 return x + y; 879 878 } 880 forall( 879 forall(otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) { 881 880 return sum( x + y, rest ); 882 881 } … … 889 888 \begin{cfa} 890 889 struct S { int x, y; }; 891 forall( otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {890 forall(otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) { 892 891 print(arg); print(rest); 893 892 } … … 928 927 is transformed into: 929 928 \begin{cfa} 930 forall( dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {929 forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 { 931 930 T0 field_0; $\C{// generated before the first 2-tuple}$ 932 931 T1 field_1; … … 934 933 _tuple2(int, int) f() { 935 934 _tuple2(double, double) x; 936 forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {935 forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 { 937 936 T0 field_0; $\C{// generated before the first 3-tuple}$ 938 937 T1 field_1; … … 942 941 } 943 942 \end{cfa} 944 {\sloppy 943 \begin{sloppypar} 945 944 Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@. 946 \ par}%945 \end{sloppypar} 947 946 948 947 \begin{comment} … … 1008 1007 1009 1008 1010 \subsection{\texorpdfstring{\ protect\lstinline{if} Statement}{if Statement}}1009 \subsection{\texorpdfstring{\LstKeywordStyle{if} Statement}{if Statement}} 1011 1010 1012 1011 The @if@ expression allows declarations, similar to @for@ declaration expression: … … 1020 1019 1021 1020 1022 \subsection{\texorpdfstring{\ protect\lstinline{switch} Statement}{switch Statement}}1021 \subsection{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}} 1023 1022 1024 1023 There are a number of deficiencies with the C @switch@ statements: enumerating @case@ lists, placement of @case@ clauses, scope of the switch body, and fall through between case clauses. … … 1091 1090 C @switch@ provides multiple entry points into the statement body, but once an entry point is selected, control continues across \emph{all} @case@ clauses until the end of the @switch@ body, called \newterm{fall through}; 1092 1091 @case@ clauses are made disjoint by the @break@ statement. 1093 While fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in errors from missing @break@ statements. 1094 For backwards compatibility, \CFA provides a \emph{new} control structure, @choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}), similar to Go. 1092 While the ability to fall through \emph{is} a useful form of control flow, it does not match well with programmer intuition, resulting in many errors from missing @break@ statements. 1093 For backwards compatibility, \CFA provides a \emph{new} control structure, @choose@, which mimics @switch@, but reverses the meaning of fall through (see Figure~\ref{f:ChooseSwitchStatements}). 1094 1095 Collectively, these enhancements reduce programmer burden and increase readability and safety. 1095 1096 1096 1097 \begin{figure} … … 1136 1137 \end{figure} 1137 1138 1138 Finally, @fallthrough@ may appear in contexts other than terminating a @case@ clause, and have an explicit transfer label allowing separate cases but common final-code for a set of cases: 1139 \begin{cquote} 1140 \lstDeleteShortInline@% 1141 \begin{tabular}{@{}l@{\hspace{2\parindentlnth}}l@{}} 1142 \multicolumn{1}{c@{\hspace{2\parindentlnth}}}{\textbf{non-terminator}} & \multicolumn{1}{c}{\textbf{target label}} \\ 1143 \begin{cfa} 1144 choose ( ... ) { 1145 case 3: 1146 if ( ... ) { 1147 ... `fallthrough;` // goto case 4 1148 } else { 1149 ... 1150 } 1151 // implicit break 1152 case 4: 1153 \end{cfa} 1154 & 1155 \begin{cfa} 1156 choose ( ... ) { 1157 case 3: 1158 ... `fallthrough common;` 1159 case 4: 1160 ... `fallthrough common;` 1161 common: 1162 ... // common code for cases 3 and 4 1163 // implicit break 1164 case 4: 1165 \end{cfa} 1166 \end{tabular} 1167 \lstMakeShortInline@% 1168 \end{cquote} 1169 The target label may be case @default@. 1170 1171 Collectively, these control-structure enhancements reduce programmer burden and increase readability and safety. 1172 1173 1174 \subsection{\texorpdfstring{Labelled \protect\lstinline{continue} / \protect\lstinline{break}}{Labelled continue / break}} 1139 \begin{comment} 1140 Forgotten @break@ statements at the end of @switch@ cases are a persistent sort of programmer error in C, and the @break@ statements themselves introduce visual clutter and an un-C-like keyword-based block delimiter. 1141 \CFA addresses this error by introducing a @choose@ statement, which works identically to a @switch@ except that its default end-of-case behaviour is to break rather than to fall through for all non-empty cases. 1142 Since empty cases like @case 7:@ in @case 7: case 11:@ still have fall-through semantics and explicit @break@ is still allowed at the end of a @choose@ case, many idiomatic uses of @switch@ in standard C can be converted to @choose@ statements by simply changing the keyword. 1143 Where fall-through is desired for a non-empty case, it can be specified with the new @fallthrough@ statement, making @choose@ equivalently powerful to @switch@, but more concise in the common case where most non-empty cases end with a @break@ statement, as in the example below: 1144 1145 \begin{cfa} 1146 choose( i ) { 1147 case 2: 1148 printf("even "); 1149 fallthrough; 1150 case 3: case 5: case 7: 1151 printf("small prime\n"); 1152 case 4,6,8,9: 1153 printf("small composite\n"); 1154 case 13~19: 1155 printf("teen\n"); 1156 default: 1157 printf("something else\n"); 1158 } 1159 \end{cfa} 1160 \end{comment} 1161 1162 1163 \subsection{\texorpdfstring{Labelled \LstKeywordStyle{continue} / \LstKeywordStyle{break}}{Labelled continue / break}} 1175 1164 1176 1165 While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure. … … 1281 1270 \subsection{Exception Handling} 1282 1271 1283 The following framework for \CFA exception handling is in place, excluding some run time type-information and virtual functions.1272 The following framework for \CFA exception handling is in place, excluding some run-time type-information and dynamic casts. 1284 1273 \CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}. 1285 1274 Both mechanisms provide dynamic call to a handler using dynamic name-lookup, where fix-up has dynamic return and recovery has static return from the handler. … … 1351 1340 catch ( IOError err ) { ... } $\C{// handler error from other files}$ 1352 1341 \end{cfa} 1353 where the throw inserts the failing file-handle in tothe I/O exception.1342 where the throw inserts the failing file-handle in the I/O exception. 1354 1343 Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible.. 1355 1344 … … 1359 1348 resume( $\emph{alternate-stack}$ ) 1360 1349 \end{cfa} 1361 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task \footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.}~\cite{Delisle18}.1362 Nonlocal raise is restricted to resumption to provide the exception handler the greatest flexibility because processing the exception does not unwind its stack, allowing it to continue after the handle rreturns.1363 1364 To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.1350 These overloads of @resume@ raise the specified exception or the currently propagating exception (reresume) at another \CFA coroutine or task~\cite{Delisle18}.\footnote{\CFA coroutine and concurrency features are discussed in a separately submitted paper.} 1351 Nonlocal raise is restricted to resumption to provide the exception handler the greatest flexibility because processing the exception does not unwind its stack, allowing it to continue after the handle returns. 1352 1353 To facilitate nonlocal exception, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation. 1365 1354 The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks: 1366 1355 \begin{cquote} … … 1369 1358 \begin{cfa} 1370 1359 enable $\emph{exception-type-list}$ { 1371 // allow non-local r aise1360 // allow non-local resumption 1372 1361 } 1373 1362 \end{cfa} … … 1375 1364 \begin{cfa} 1376 1365 disable $\emph{exception-type-list}$ { 1377 // disallow non-local r aise1366 // disallow non-local resumption 1378 1367 } 1379 1368 \end{cfa} … … 1386 1375 Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled. 1387 1376 \begin{cfa} 1388 void main( mytask & t) { $\C{// thread starts here}$1377 void main( mytask & c ) { $\C{// thread starts here}$ 1389 1378 // non-local exceptions disabled 1390 1379 try { $\C{// establish handles for non-local exceptions}$ … … 1412 1401 1413 1402 1414 \subsection{\texorpdfstring{\ protect\lstinline{with} Clause / Statement}{with Clause / Statement}}1403 \subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}} 1415 1404 \label{s:WithClauseStatement} 1416 1405 … … 2735 2724 user defined: D, Objective-C 2736 2725 2737 2738 2726 \section{Conclusion and Future Work} 2739 2727 … … 2748 2736 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 2749 2737 2750 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, runtime type-information, virtual functions,user-defined conversions, concurrent primitives, and modules.2738 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules. 2751 2739 (While all examples in the paper compile and run, a public beta-release of \CFA will take another 8--12 months to finalize these additional extensions.) 2752 2740 In addition, there are interesting future directions for the polymorphism design. … … 2783 2771 \CFA 2784 2772 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2785 forall( otype T) struct stack_node;2786 forall( otype T) struct stack {2773 forall(otype T) struct stack_node; 2774 forall(otype T) struct stack { 2787 2775 stack_node(T) * head; 2788 2776 }; 2789 forall( otype T) struct stack_node {2777 forall(otype T) struct stack_node { 2790 2778 T value; 2791 2779 stack_node(T) * next; 2792 2780 }; 2793 forall( 2794 forall( 2781 forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2782 forall(otype T) void ?{}( stack(T) & s, stack(T) t ) { 2795 2783 stack_node(T) ** crnt = &s.head; 2796 2784 for ( stack_node(T) * next = t.head; next; next = next->next ) { … … 2803 2791 *crnt = 0; 2804 2792 } 2805 forall( otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {2793 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) { 2806 2794 if ( s.head == t.head ) return s; 2807 2795 clear( s ); … … 2809 2797 return s; 2810 2798 } 2811 forall( otype T) void ^?{}( stack(T) & s) { clear( s ); }2812 forall( otype T) _Bool empty( const stack(T) & s ) { return s.head == 0; }2813 forall( otype T) void push( stack(T) & s, T value ) {2799 forall(otype T) void ^?{}( stack(T) & s) { clear( s ); } 2800 forall(otype T) _Bool empty( const stack(T) & s ) { return s.head == 0; } 2801 forall(otype T) void push( stack(T) & s, T value ) { 2814 2802 stack_node(T) * new_node = ((stack_node(T)*)malloc()); 2815 2803 (*new_node){ value, s.head }; /***/ 2816 2804 s.head = new_node; 2817 2805 } 2818 forall( otype T) T pop( stack(T) & s ) {2806 forall(otype T) T pop( stack(T) & s ) { 2819 2807 stack_node(T) * n = s.head; 2820 2808 s.head = n->next; … … 2823 2811 return v; 2824 2812 } 2825 forall( otype T) void clear( stack(T) & s ) {2813 forall(otype T) void clear( stack(T) & s ) { 2826 2814 for ( stack_node(T) * next = s.head; next; ) { 2827 2815 stack_node(T) * crnt = next;
Note: See TracChangeset
for help on using the changeset viewer.