Changeset 87555b7 for doc/papers


Ignore:
Timestamp:
Mar 8, 2018, 9:33:30 AM (4 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
4c11fce
Parents:
fb11446e
Message:

more changes

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/papers/general/Paper.tex

    rfb11446e r87555b7  
    267267int m = max( max, -max );                                       $\C{// uses (3) and (1) twice, by matching return type}$
    268268\end{cfa}
     269
    269270\CFA maximizes the ability to reuse names to aggressively address the naming problem.
    270271In some cases, hundreds of names can be reduced to tens, resulting in a significant cognitive reduction.
     
    285286
    286287
    287 \subsection{\texorpdfstring{\LstKeywordStyle{forall} Functions}{forall Functions}}
     288\subsection{\texorpdfstring{\protect\lstinline{forall} Functions}{forall Functions}}
    288289\label{sec:poly-fns}
    289290
     
    435436One approach is to write bespoke data-structures for each context in which they are needed.
    436437While 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.
     438A 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.
    438439However, 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.
    439440A 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.
     
    508509If 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;
    509510if 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.
     511As 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.
    515516@_offsetof_pair@ is the offset array passed into @value@; this array is generated at the call site as:
    516517\begin{cfa}
    517 size_t _offsetof_pair[] = { offsetof(_pair_conc0, first), offsetof(_pair_conc0, second) }
     518size_t _offsetof_pair[] = { offsetof( _pair_conc0, first ), offsetof( _pair_conc0, second ) }
    518519\end{cfa}
    519520
     
    539540The 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@:
    540541\begin{cfa}
    541 forall(dtype T) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
     542forall( dtype T ) int lexcmp( pair( T *, T * ) * a, pair( T *, T * ) * b, int (* cmp)( T *, T * ) ) {
    542543        return cmp( a->first, b->first ) ? : cmp( a->second, b->second );
    543544}
    544545\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.
     546Since @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.
    546547
    547548Another useful pattern enabled by reused dtype-static type instantiations is zero-cost \newterm{tag-structures}.
    548549Sometimes information is only used for type-checking and can be omitted at runtime, \eg:
    549550\begin{cfa}
    550 forall(dtype Unit) struct scalar { unsigned long value; };
     551forall( dtype Unit ) struct scalar { unsigned long value; };
    551552struct metres {};
    552553struct litres {};
    553554
    554 forall(dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
     555forall( dtype U) scalar(U) ?+?( scalar(U) a, scalar(U) b ) {
    555556        return (scalar(U)){ a.value + b.value };
    556557}
     
    807808Due 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:
    808809\begin{cfa}
    809 forall(otype T, dtype U) void f( T x, U * y );
     810forall( otype T, dtype U ) void f( T x, U * y );
    810811f( [5, "hello"] );
    811812\end{cfa}
     
    814815For example, a plus operator can be written to add two triples together.
    815816\begin{cfa}
    816 forall(otype T | { T ?+?( T, T ); }) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
     817forall( otype T | { T ?+?( T, T ); } ) [T, T, T] ?+?( [T, T, T] x, [T, T, T] y ) {
    817818        return [x.0 + y.0, x.1 + y.1, x.2 + y.2];
    818819}
     
    825826\begin{cfa}
    826827int f( [int, double], double );
    827 forall(otype T, otype U | { T f( T, U, U ); }) void g( T, U );
     828forall( otype T, otype U | { T f( T, U, U ); } ) void g( T, U );
    828829g( 5, 10.21 );
    829830\end{cfa}
     
    852853\begin{cfa}
    853854int sum$\(_0\)$() { return 0; }
    854 forall(ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
     855forall( ttype Params | { int sum( Params ); } ) int sum$\(_1\)$( int x, Params rest ) {
    855856        return x + sum( rest );
    856857}
     
    865866\begin{cfa}
    866867int sum( int x, int y ) { return x + y; }
    867 forall(ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
     868forall( ttype Params | { int sum( int, Params ); } ) int sum( int x, int y, Params rest ) {
    868869        return sum( x + y, rest );
    869870}
     
    871872One more step permits the summation of any summable type with all arguments of the same type:
    872873\begin{cfa}
    873 trait summable(otype T) {
     874trait summable( otype T ) {
    874875        T ?+?( T, T );
    875876};
    876 forall(otype R | summable( R ) ) R sum( R x, R y ) {
     877forall( otype R | summable( R ) ) R sum( R x, R y ) {
    877878        return x + y;
    878879}
    879 forall(otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
     880forall( otype R, ttype Params | summable(R) | { R sum(R, Params); } ) R sum(R x, R y, Params rest) {
    880881        return sum( x + y, rest );
    881882}
     
    888889\begin{cfa}
    889890struct S { int x, y; };
    890 forall(otype T, ttype Params | { void print(T); void print(Params); }) void print(T arg, Params rest) {
     891forall( otype T, ttype Params | { void print(T); void print(Params); } ) void print(T arg, Params rest) {
    891892        print(arg);  print(rest);
    892893}
     
    927928is transformed into:
    928929\begin{cfa}
    929 forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) struct _tuple2 {
     930forall( dtype T0, dtype T1 | sized(T0) | sized(T1) ) struct _tuple2 {
    930931        T0 field_0;                                                             $\C{// generated before the first 2-tuple}$
    931932        T1 field_1;
     
    933934_tuple2(int, int) f() {
    934935        _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 {
    936937                T0 field_0;                                                     $\C{// generated before the first 3-tuple}$
    937938                T1 field_1;
     
    941942}
    942943\end{cfa}
    943 \begin{sloppypar}
     944{\sloppy
    944945Tuple 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}%
    946947
    947948\begin{comment}
     
    10071008
    10081009
    1009 \subsection{\texorpdfstring{\LstKeywordStyle{if} Statement}{if Statement}}
     1010\subsection{\texorpdfstring{\protect\lstinline{if} Statement}{if Statement}}
    10101011
    10111012The @if@ expression allows declarations, similar to @for@ declaration expression:
     
    10191020
    10201021
    1021 \subsection{\texorpdfstring{\LstKeywordStyle{switch} Statement}{switch Statement}}
     1022\subsection{\texorpdfstring{\protect\lstinline{switch} Statement}{switch Statement}}
    10221023
    10231024There 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.
     
    10901091C @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};
    10911092@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.
     1093While 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.
     1094For 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.
    10961095
    10971096\begin{figure}
     
    11371136\end{figure}
    11381137
    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}}
     1138Finally, @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}
     1144choose ( ... ) {
     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}
     1156choose ( ... ) {
     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}
     1169The target label may be case @default@.
     1170
     1171Collectively, 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}}
    11641175
    11651176While C provides @continue@ and @break@ statements for altering control flow, both are restricted to one level of nesting for a particular control structure.
     
    12701281\subsection{Exception Handling}
    12711282
    1272 The following framework for \CFA exception handling is in place, excluding some run-time type-information and dynamic casts.
     1283The following framework for \CFA exception handling is in place, excluding some runtime type-information and virtual functions.
    12731284\CFA provides two forms of exception handling: \newterm{fix-up} and \newterm{recovery} (see Figure~\ref{f:CFAExceptionHandling})~\cite{Buhr92b,Buhr00a}.
    12741285Both 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.
     
    13401351   catch ( IOError err ) { ... }                        $\C{// handler error from other files}$
    13411352\end{cfa}
    1342 where the throw inserts the failing file-handle in the I/O exception.
     1353where the throw inserts the failing file-handle into the I/O exception.
    13431354Conditional catch cannot be trivially mimicked by other mechanisms because once an exception is caught, handler clauses in that @try@ statement are no longer eligible..
    13441355
     
    13481359resume( $\emph{alternate-stack}$ )
    13491360\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.
     1361These 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}.
     1362Nonlocal 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
     1364To facilitate nonlocal raise, \CFA provides dynamic enabling and disabling of nonlocal exception-propagation.
    13541365The constructs for controlling propagation of nonlocal exceptions are the @enable@ and the @disable@ blocks:
    13551366\begin{cquote}
     
    13581369\begin{cfa}
    13591370enable $\emph{exception-type-list}$ {
    1360         // allow non-local resumption
     1371        // allow non-local raise
    13611372}
    13621373\end{cfa}
     
    13641375\begin{cfa}
    13651376disable $\emph{exception-type-list}$ {
    1366         // disallow non-local resumption
     1377        // disallow non-local raise
    13671378}
    13681379\end{cfa}
     
    13751386Coroutines and tasks start with non-local exceptions disabled, allowing handlers to be put in place, before non-local exceptions are explicitly enabled.
    13761387\begin{cfa}
    1377 void main( mytask & c ) {                                       $\C{// thread starts here}$
     1388void main( mytask & t ) {                                       $\C{// thread starts here}$
    13781389        // non-local exceptions disabled
    13791390        try {                                                                   $\C{// establish handles for non-local exceptions}$
     
    14011412
    14021413
    1403 \subsection{\texorpdfstring{\LstKeywordStyle{with} Clause / Statement}{with Clause / Statement}}
     1414\subsection{\texorpdfstring{\protect\lstinline{with} Clause / Statement}{with Clause / Statement}}
    14041415\label{s:WithClauseStatement}
    14051416
     
    27242735user defined: D, Objective-C
    27252736
     2737
    27262738\section{Conclusion and Future Work}
    27272739
     
    27362748Finally, we demonstrate that \CFA performance for some idiomatic cases is better than C and close to \CC, showing the design is practically applicable.
    27372749
    2738 There is ongoing work on a wide range of \CFA feature extensions, including arrays with size, user-defined conversions, concurrent primitives, and modules.
     2750There 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.
    27392751(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.)
    27402752In addition, there are interesting future directions for the polymorphism design.
     
    27712783\CFA
    27722784\begin{cfa}[xleftmargin=2\parindentlnth,aboveskip=0pt,belowskip=0pt]
    2773 forall(otype T) struct stack_node;
    2774 forall(otype T) struct stack {
     2785forall( otype T ) struct stack_node;
     2786forall( otype T ) struct stack {
    27752787        stack_node(T) * head;
    27762788};
    2777 forall(otype T) struct stack_node {
     2789forall( otype T ) struct stack_node {
    27782790        T value;
    27792791        stack_node(T) * next;
    27802792};
    2781 forall(otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
    2782 forall(otype T) void ?{}( stack(T) & s, stack(T) t ) {
     2793forall( otype T) void ?{}( stack(T) & s ) { (s.head){ 0 }; }
     2794forall( otype T) void ?{}( stack(T) & s, stack(T) t ) {
    27832795        stack_node(T) ** crnt = &s.head;
    27842796        for ( stack_node(T) * next = t.head; next; next = next->next ) {
     
    27912803        *crnt = 0;
    27922804}
    2793 forall(otype T) stack(T) ?=?( stack(T) & s, stack(T) t ) {
     2805forall( otype T ) stack(T) ?=?( stack(T) & s, stack(T) t ) {
    27942806        if ( s.head == t.head ) return s;
    27952807        clear( s );
     
    27972809        return s;
    27982810}
    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 ) {
     2811forall( otype T ) void ^?{}( stack(T) & s) { clear( s ); }
     2812forall( otype T ) _Bool empty( const stack(T) & s ) { return s.head == 0; }
     2813forall( otype T ) void push( stack(T) & s, T value ) {
    28022814        stack_node(T) * new_node = ((stack_node(T)*)malloc());
    28032815        (*new_node){ value, s.head }; /***/
    28042816        s.head = new_node;
    28052817}
    2806 forall(otype T) T pop( stack(T) & s ) {
     2818forall( otype T ) T pop( stack(T) & s ) {
    28072819        stack_node(T) * n = s.head;
    28082820        s.head = n->next;
     
    28112823        return v;
    28122824}
    2813 forall(otype T) void clear( stack(T) & s ) {
     2825forall( otype T ) void clear( stack(T) & s ) {
    28142826        for ( stack_node(T) * next = s.head; next; ) {
    28152827                stack_node(T) * crnt = next;
Note: See TracChangeset for help on using the changeset viewer.