Changeset e61de5b
- Timestamp:
- Mar 8, 2018, 11:33:03 AM (7 years ago)
- Branches:
- ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
- Children:
- 70969f8
- Parents:
- ab0203df (diff), 4c11fce (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. - File:
-
- 1 edited
-
doc/papers/general/Paper.tex (modified) (32 diffs)
Legend:
- Unmodified
- Added
- Removed
-
doc/papers/general/Paper.tex
rab0203df re61de5b 267 267 int m = max( max, -max ); $\C{// uses (3) and (1) twice, by matching return type}$ 268 268 \end{cfa} 269 269 270 \CFA maximizes the ability to reuse names to aggressively address the naming problem. 270 271 In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction. … … 285 286 286 287 287 \subsection{\texorpdfstring{\ LstKeywordStyle{forall} Functions}{forall Functions}}288 \subsection{\texorpdfstring{\protect\lstinline{forall} Functions}{forall Functions}} 288 289 \label{sec:poly-fns} 289 290 … … 435 436 One approach is to write bespoke data-structures for each context in which they are needed. 436 437 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. 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.438 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. 438 439 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. 439 440 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. … … 508 509 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; 509 510 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. 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.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. 515 516 @_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as: 516 517 \begin{cfa} 517 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first), offsetof(_pair_conc0, second) }518 size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) } 518 519 \end{cfa} 519 520 … … 539 540 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@: 540 541 \begin{cfa} 541 forall( dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {542 forall( dtype T ) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) { 542 543 return cmp( a->first, b->first ) ? : cmp( a->second, b->second ); 543 544 } 544 545 \end{cfa} 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.546 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. 546 547 547 548 Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}. 548 549 Sometimes information is only used for type-checking and can be omitted at runtime, \eg: 549 550 \begin{cfa} 550 forall( dtype Unit) struct scalar { unsigned long value; };551 forall( dtype Unit ) struct scalar { unsigned long value; }; 551 552 struct metres {}; 552 553 struct litres {}; 553 554 554 forall( dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {555 forall( dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) { 555 556 return (scalar(U)){ a.value + b.value }; 556 557 } … … 807 808 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: 808 809 \begin{cfa} 809 forall( otype T, dtype U) void f( T x, U * y );810 forall( otype T, dtype U ) void f( T x, U * y ); 810 811 f( [5, "hello"] ); 811 812 \end{cfa} … … 814 815 For example, a plus operator can be written to add two triples together. 815 816 \begin{cfa} 816 forall( otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {817 forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) { 817 818 return [x.0 + y.0, x.1 + y.1, x.2 + y.2]; 818 819 } … … 825 826 \begin{cfa} 826 827 int f( [int, double], double ); 827 forall( otype T, otype U | { T f( T, U, U ); }) void g( T, U );828 forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U ); 828 829 g( 5, 10.21 ); 829 830 \end{cfa} … … 852 853 \begin{cfa} 853 854 int sum$\(_0\)$() { return 0; } 854 forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {855 forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) { 855 856 return x + sum( rest ); 856 857 } … … 865 866 \begin{cfa} 866 867 int sum( int x, int y ) { return x + y; } 867 forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {868 forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) { 868 869 return sum( x + y, rest ); 869 870 } … … 871 872 One more step permits the summation of any summable type with all arguments of the same type: 872 873 \begin{cfa} 873 trait summable( otype T) {874 trait summable( otype T ) { 874 875 T ?+?( T, T ); 875 876 }; 876 forall( otype R | summable( R ) ) R sum( R x, R y ) {877 forall( otype R | summable( R ) ) R sum( R x, R y ) { 877 878 return x + y; 878 879 } 879 forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {880 forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) { 880 881 return sum( x + y, rest ); 881 882 } … … 888 889 \begin{cfa} 889 890 struct S { int x, y; }; 890 forall( otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {891 forall( otype T, ttype Params | { void print(T); void print(Params); } ) void print(T arg, Params rest) { 891 892 print(arg); print(rest); 892 893 } … … 927 928 is transformed into: 928 929 \begin{cfa} 929 forall( dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {930 forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 { 930 931 T0 field_0; $\C{// generated before the first 2-tuple}$ 931 932 T1 field_1; … … 933 934 _tuple2(int, int) f() { 934 935 _tuple2(double, double) x; 935 forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) struct _tuple3 {936 forall( dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2) ) struct _tuple3 { 936 937 T0 field_0; $\C{// generated before the first 3-tuple}$ 937 938 T1 field_1; … … 941 942 } 942 943 \end{cfa} 943 \begin{sloppypar} 944 {\sloppy 944 945 Tuple expressions are then simply converted directly into compound literals, \eg @[5, 'x', 1.24]@ becomes @(_tuple3(int, char, double)){ 5, 'x', 1.24 }@. 945 \ end{sloppypar}946 \par}% 946 947 947 948 \begin{comment} … … 1007 1008 1008 1009 1009 \subsection{\texorpdfstring{\ LstKeywordStyle{if} Statement}{if Statement}}1010 \subsection{\texorpdfstring{\protect\lstinline{if} Statement}{if Statement}} 1010 1011 1011 1012 The @if@ expression allows declarations, similar to @for@ declaration expression: … … 1019 1020 1020 1021 1021 \subsection{\texorpdfstring{\ LstKeywordStyle{switch} Statement}{switch Statement}}1022 \subsection{\texorpdfstring{\protect\lstinline{switch} Statement}{switch Statement}} 1022 1023 1023 1024 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. … … 1090 1091 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}; 1091 1092 @case@ clauses are made disjoint by the @break@ statement. 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. 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. 1096 1095 1097 1096 \begin{figure} … … 1137 1136 \end{figure} 1138 1137 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}} 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}} 1164 1175 1165 1176 While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure. … … 1270 1281 \subsection{Exception Handling} 1271 1282 1272 The following framework for \CFA exception handling is in place, excluding some run -time type-information and dynamic casts.1283 The following framework for \CFA exception handling is in place, excluding some runtime type-information and virtual functions. 1273 1284 \CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}. 1274 1285 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. … … 1340 1351 catch ( IOError err ) { ... } $\C{// handler error from other files}$ 1341 1352 \end{cfa} 1342 where the throw inserts the failing file-handle in the I/O exception.1353 where the throw inserts the failing file-handle into the I/O exception. 1343 1354 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.. 1344 1355 … … 1348 1359 resume( $\emph{alternate-stack}$ ) 1349 1360 \end{cfa} 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.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 handler returns. 1363 1364 To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation. 1354 1365 The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks: 1355 1366 \begin{cquote} … … 1358 1369 \begin{cfa} 1359 1370 enable $\emph{exception-type-list}$ { 1360 // allow non-local r esumption1371 // allow non-local raise 1361 1372 } 1362 1373 \end{cfa} … … 1364 1375 \begin{cfa} 1365 1376 disable $\emph{exception-type-list}$ { 1366 // disallow non-local r esumption1377 // disallow non-local raise 1367 1378 } 1368 1379 \end{cfa} … … 1375 1386 Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled. 1376 1387 \begin{cfa} 1377 void main( mytask & c) { $\C{// thread starts here}$1388 void main( mytask & t ) { $\C{// thread starts here}$ 1378 1389 // non-local exceptions disabled 1379 1390 try { $\C{// establish handles for non-local exceptions}$ … … 1401 1412 1402 1413 1403 \subsection{\texorpdfstring{\ LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}1414 \subsection{\texorpdfstring{\protect\lstinline{with} Clause / Statement}{with Clause / Statement}} 1404 1415 \label{s:WithClauseStatement} 1405 1416 … … 2724 2735 user defined: D, Objective-C 2725 2736 2737 2726 2738 \section{Conclusion and Future Work} 2727 2739 … … 2736 2748 Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable. 2737 2749 2738 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.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. 2739 2751 (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.) 2740 2752 In addition, there are interesting future directions for the polymorphism design. … … 2771 2783 \CFA 2772 2784 \begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt] 2773 forall( otype T) struct stack_node;2774 forall( otype T) struct stack {2785 forall( otype T ) struct stack_node; 2786 forall( otype T ) struct stack { 2775 2787 stack_node(T) * head; 2776 2788 }; 2777 forall( otype T) struct stack_node {2789 forall( otype T ) struct stack_node { 2778 2790 T value; 2779 2791 stack_node(T) * next; 2780 2792 }; 2781 forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }2782 forall( otype T) void ?{}( stack(T) & s, stack(T) t ) {2793 forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; } 2794 forall( otype T) void ?{}( stack(T) & s, stack(T) t ) { 2783 2795 stack_node(T) ** crnt = &s.head; 2784 2796 for ( stack_node(T) * next = t.head; next; next = next->next ) { … … 2791 2803 *crnt = 0; 2792 2804 } 2793 forall( otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {2805 forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) { 2794 2806 if ( s.head == t.head ) return s; 2795 2807 clear( s ); … … 2797 2809 return s; 2798 2810 } 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 ) {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 ) { 2802 2814 stack_node(T) * new_node = ((stack_node(T)*)malloc()); 2803 2815 (*new_node){ value, s.head }; /***/ 2804 2816 s.head = new_node; 2805 2817 } 2806 forall( otype T) T pop( stack(T) & s ) {2818 forall( otype T ) T pop( stack(T) & s ) { 2807 2819 stack_node(T) * n = s.head; 2808 2820 s.head = n->next; … … 2811 2823 return v; 2812 2824 } 2813 forall( otype T) void clear( stack(T) & s ) {2825 forall( otype T ) void clear( stack(T) & s ) { 2814 2826 for ( stack_node(T) * next = s.head; next; ) { 2815 2827 stack_node(T) * crnt = next;
Note: See TracChangeset
for help on using the changeset viewer.
