Changeset 41cd57c0 for doc/generic_types/generic_types.tex
- Timestamp:
- Mar 27, 2017, 9:00:38 PM (8 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:
- c1fb1f2f, f32a013
- Parents:
- 626da644
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
doc/generic_types/generic_types.tex
r626da644 r41cd57c0 139 139 \item Extensions introduced by \CFA{} must be translated in the most efficient way possible. 140 140 \end{enumerate} 141 The purpose of these goals is to ensure that existing C codebases can be converted to \CFA{} incrementally and with minimal effort, and that programmers who already know C can productively produce \CFA{} code without extensive training beyond the extension features they wish to employ. 141 The purpose of these goals is to ensure that existing C codebases can be converted to \CFA{} incrementally and with minimal effort, and that programmers who already know C can productively produce \CFA{} code without extensive training beyond the extension features they wish to employ. In its current implementation, \CFA{} is compiled by translating it to GCC-dialect C, allowing it to leverage the portability and code optimizations provided by GCC, meeting goals (1)-(3). 142 142 143 143 \CFA{} has been previously extended with polymorphic functions and name overloading (including operator overloading) \citep{Bilson03}, and deterministically-executed constructors and destructors \citep{Schluntz17}. This paper describes how generic and tuple types are designed and implemented in \CFA{} in accordance with both the backward compatibility goals and existing features described above. … … 178 178 \end{lstlisting} 179 179 This version of @twice@ works for any type @S@ that has an addition operator defined for it, and it could have been used to satisfy the type assertion on @four_times@. 180 The compiler accomplishes this by creating a wrapper function calling @twice // (2)@ with @S@ bound to @double@, then providing this wrapper function to @four_times@\footnote{\lstinline@twice // (2)@ could also have had a type parameter named \lstinline@T@; \CFA{} specifies renaming of the type parameters, which would avoid the name conflict with the type variable \lstinline@T@ of \lstinline@four_times@.}.180 The translator accomplishes this by creating a wrapper function calling @twice // (2)@ with @S@ bound to @double@, then providing this wrapper function to @four_times@\footnote{\lstinline@twice // (2)@ could also have had a type parameter named \lstinline@T@; \CFA{} specifies renaming of the type parameters, which would avoid the name conflict with the type variable \lstinline@T@ of \lstinline@four_times@.}. 181 181 182 182 \subsection{Traits} … … 299 299 \CFA{} classifies generic types as either \emph{concrete} or \emph{dynamic}. Dynamic generic types vary in their in-memory layout depending on their type parameters, while concrete generic types have a fixed memory layout regardless of type parameters. A type may have polymorphic parameters but still be concrete; \CFA{} refers to such types as \emph{dtype-static}. Polymorphic pointers are an example of dtype-static types -- @forall(dtype T) T*@ is a polymorphic type, but for any @T@ chosen, @T*@ will have exactly the same in-memory representation as a @void*@, and can therefore be represented by a @void*@ in code generation. 300 300 301 The \CFA{} compiler instantiates concrete generic types by template-expanding them to fresh struct types; concrete generic types can therefore be used with zero runtime overhead. To enable interoperation between equivalent instantiations of a generic type, the compiler saves the set of instantiations currently in scope and re-uses the generated struct declarations where appropriate. As an example, the concrete instantiation for @pair(const char*, int)@ would look something like this: 301 \subsection{Concrete Generic Types} 302 303 The \CFA{} translator instantiates concrete generic types by template-expanding them to fresh struct types; concrete generic types can therefore be used with zero runtime overhead. To enable interoperation between equivalent instantiations of a generic type, the translator saves the set of instantiations currently in scope and re-uses the generated struct declarations where appropriate. As an example, the concrete instantiation for @pair(const char*, int)@ would look something like this: 302 304 \begin{lstlisting} 303 305 struct _pair_conc1 { … … 315 317 \end{lstlisting} 316 318 319 \subsection{Dynamic Generic Types} 320 317 321 Though \CFA{} implements concrete generic types efficiently, it also has a fully-general system for computing with dynamic generic types. As mentioned in Section~\ref{sec:poly-fns}, @otype@ function parameters (in fact all @sized@ polymorphic parameters) come with implicit size and alignment parameters provided by the caller. Dynamic generic structs also come with an \emph{offset array} which contains the offsets of each member of the struct\footnote{Dynamic generic unions need no such offset array, as all members are at offset 0.}. Access to members\footnote{The \lstinline@offsetof@ macro is implmented similarly.} of a dynamic generic struct is provided by adding the corresponding member of the offset array to the struct pointer at runtime, essentially moving a compile-time offset calculation to runtime where neccessary. 318 322 319 These offset arrays are staticly generated where possible. If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the compiler can safely assume that the generic type is complete (that is, has a known layout) at any call-site, and the offset array is passed from the caller; if the generic type is concrete at the call site this offset array can even be statically generated using the C @offsetof@ macro. As an example, @p.second@ in the @value@ function above is implemented as @*(p + _offsetof_pair[1])@, where @p@ is a @void*@, and @_offsetof_pair@ is the offset array passed in to @value@ for @pair(const char*, T)@. The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) };@.320 321 In some cases the offset arrays cannot be staticly generated. For instance, modularity is generally produced in C by including an opaque forward-declaration of a struct and associated accessor and mutator routines in a header file, with the actual implementations in a separately-compiled \texttt{.c} file. \CFA{} supports this pattern for generic types, and in tis instance the caller does not know the actual layout or size of the dynamic generic type, and only holds it by pointer. The \CFA{} compiler automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed in to a function from that function's caller. These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic struct (un-@sized@ parameters are forbidden from the language from being used in a context which affects layout). Results of these layout functions are cached so that they are only computed once per type per function.%, as in the example below for @pair@.323 These offset arrays are staticly generated where possible. If a dynamic generic type is declared to be passed or returned by value from a polymorphic function, the translator can safely assume that the generic type is complete (that is, has a known layout) at any call-site, and the offset array is passed from the caller; if the generic type is concrete at the call site this offset array can even be statically generated using the C @offsetof@ macro. As an example, @p.second@ in the @value@ function above is implemented as @*(p + _offsetof_pair[1])@, where @p@ is a @void*@, and @_offsetof_pair@ is the offset array passed in to @value@ for @pair(const char*, T)@. The offset array @_offsetof_pair@ is generated at the call site as @size_t _offsetof_pair[] = { offsetof(_pair_conc1, first), offsetof(_pair_conc1, second) };@. 324 325 In some cases the offset arrays cannot be staticly generated. For instance, modularity is generally produced in C by including an opaque forward-declaration of a struct and associated accessor and mutator routines in a header file, with the actual implementations in a separately-compiled \texttt{.c} file. \CFA{} supports this pattern for generic types, and in tis instance the caller does not know the actual layout or size of the dynamic generic type, and only holds it by pointer. The \CFA{} translator automatically generates \emph{layout functions} for cases where the size, alignment, and offset array of a generic struct cannot be passed in to a function from that function's caller. These layout functions take as arguments pointers to size and alignment variables and a caller-allocated array of member offsets, as well as the size and alignment of all @sized@ parameters to the generic struct (un-@sized@ parameters are forbidden from the language from being used in a context which affects layout). Results of these layout functions are cached so that they are only computed once per type per function.%, as in the example below for @pair@. 322 326 % \begin{lstlisting} 323 327 % static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair, … … 348 352 Whether a type is concrete, dtype-static, or dynamic is decided based solely on the type parameters and @forall@ clause on the struct declaration. This allows opaque forward declarations of generic types like @forall(otype T) struct Box;@ -- like in C, all uses of @Box(T)@ can be in a separately compiled translation unit, and callers from other translation units will know the proper calling conventions to use. If the definition of a struct type was included in the determination of dynamic or concrete, some further types may be recognized as dtype-static (\eg, @forall(otype T) struct unique_ptr { T* p };@ does not depend on @T@ for its layout, but the existence of an @otype@ parameter means that it \emph{could}.), but preserving separate compilation (and the associated C compatibility) in this way is judged to be an appropriate trade-off. 349 353 354 \subsection{Applications} 355 350 356 The re-use of dtype-static struct instantiations enables some useful programming patterns at zero runtime cost. The most important such pattern is using @forall(dtype T) T*@ as a type-checked replacement for @void*@, as in this example, which takes a @qsort@ or @bsearch@-compatible comparison routine and creates a similar lexicographic comparison for pairs of pointers: 351 357 \begin{lstlisting} … … 567 573 Note that a cast is not a function call in \CFA{}, so flattening and structuring conversions do not occur for cast expressions\footnote{User-defined conversions have been considered, but for compatibility with C and the existing use of casts as type ascription, any future design for such conversions would require more precise matching of types than allowed for function arguments and parameters.}. As such, (4) is invalid because the cast target type contains 4 components, while the source type contains only 3. Similarly, (5) is invalid because the cast @([int, int, int])(g().1)@ is invalid. That is, it is invalid to cast @[int, int]@ to @[int, int, int]@. 568 574 569 \TODO{} 570 571 In \CFA{}, functions can be declared to return multiple values with an extension to the function declaration syntax. Multiple return values are declared as a comma-separated list of types in square brackets in the same location that the return type appears in standard C function declarations. The ability to return multiple values from a function requires a new syntax for the @return@ statement. For consistency, the @return@ statement in \CFA{} accepts a comma-separated list of expressions in square brackets. The expression resolution phase of the \CFA{} compiler ensures that the correct form is used depending on the values being returned and the return type of the current function. A multiple-returning function with return type @T@ can return any expression that is implicitly convertible to @T@. As an example, a function returning the most frequent character in a string and its frequency can be written in \CFA{} as: 572 \begin{lstlisting} 573 [int, char] most_frequent(const char * str) { // tuple return type 574 char freqs [26] = { 0 }; 575 int ret_freq = 0; 576 char ret_ch = 'a'; 577 for (int i = 0; str[i] != '\0'; ++i) { 578 if (isalpha(str[i])) { // only count letters 579 int ch = tolower(str[i]); // convert to lower case 580 int idx = ch-'a'; 581 if (++freqs[idx] > ret_freq) { // update on new max 582 ret_freq = freqs[idx]; 583 ret_ch = ch; 584 } 585 } 586 } 587 return [ret_freq, ret_ch]; // return tuple expression 588 } 589 \end{lstlisting} 590 This approach provides the benefits of compile-time checking for appropriate return statements as in aggregation, but without the required verbosity of declaring a new named type. 591 592 The addition of multiple-return-value functions necessitates a syntax for accepting multiple values at the call-site. The simplest mechanism for retaining a return value in C is variable assignment. By assigning the return value into a variable, its value can be retrieved later at any point in the program. As such, \CFA{} allows assigning multiple values from a function into multiple variables, using a square-bracketed list of lvalue expressions on the left side. 593 \begin{lstlisting} 594 const char * str = "hello world"; 595 int freq; 596 char ch; 597 [freq, ch] = most_frequent(str); // assign into multiple variables 598 printf("%s -- %d %c\n", str, freq, ch); 599 \end{lstlisting} 600 601 It is also common to use a function's output as the input to another function. \CFA{} also allows this case, without any new syntax. When a function call is passed as an argument to another call, the expression resolver attempts to find the best match of actual arguments to formal parameters given all of the possible expression interpretations in the current scope \citep{Bilson03}. For example, 602 \begin{lstlisting} 603 void process(int); // (1) 604 void process(char); // (2) 605 void process(int, char); // (3) 606 void process(char, int); // (4) 607 608 process(most_frequent("hello world")); // selects (3) 609 \end{lstlisting} 610 In this case, there is only one option for a function named @most_frequent@ that takes a string as input. This function returns two values, one @int@ and one @char@. There are four options for a function named @process@, but only two which accept two arguments, and of those the best match is (3), which is also an exact match. This expression first calls @most_frequent("hello world")@, which produces the values @3@ and @'l'@, which are fed directly to the first and second parameters of (3), respectively. 611 612 575 \subsection{Polymorphism} 576 577 Tuples also integrate with \CFA{} polymorphism as a special sort of generic type. 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. 578 \begin{lstlisting} 579 forall(otype T, dtype U) 580 void f(T x, U * y); 581 582 f([5, "hello"]); 583 \end{lstlisting} 584 In this example, @[5, "hello"]@ is flattened, so that the argument list appears as @5, "hello"@. The argument matching algorithm binds @T@ to @int@ and @U@ to @const char@, and calls the function as normal. 585 586 Tuples, however, can contain polymorphic components. For example, a plus operator can be written to add two triples of a type together. 587 \begin{lstlisting} 588 forall(otype T | { T ?+?(T, T); }) 589 [T, T, T] ?+?([T, T, T] x, [T, T, T] y) { 590 return [x.0+y.0, x.1+y.1, x.2+y.2]; 591 } 592 [int, int, int] x; 593 int i1, i2, i3; 594 [i1, i2, i3] = x + ([10, 20, 30]); 595 \end{lstlisting} 596 597 Flattening and restructuring conversions are also applied to tuple types in polymorphic type assertions. Previously in \CFA{}, it has been assumed that assertion arguments must match the parameter type exactly, modulo polymorphic specialization (\ie{}, no implicit conversions are applied to assertion arguments). In the example below: 598 \begin{lstlisting} 599 int f([int, double], double); 600 forall(otype T, otype U | { T f(T, U, U); }) 601 void g(T, U); 602 g(5, 10.21); 603 \end{lstlisting} 604 If assertion arguments must match exactly, then the call to @g@ cannot be resolved, since the expected type of @f@ is flat, while the only @f@ in scope requires a tuple type. Since tuples are fluid, this requirement reduces the usability of tuples in polymorphic code. To ease this pain point, function parameter and return lists are flattened for the purposes of type unification, which allows the previous example to pass expression resolution. 605 606 This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \citet{Bilson03}. Now, whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function: 607 \begin{lstlisting} 608 int _thunk(int _p0, double _p1, double _p2) { 609 return f([_p0, _p1], _p2); 610 } 611 \end{lstlisting} 612 Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism. 613 614 \subsection{Variadic Tuples} 615 616 To define variadic functions, \CFA{} adds a new kind of type parameter, @ttype@. Matching against a @ttype@ parameter consumes all remaining argument components and packages them into a tuple, binding to the resulting tuple of types. In a given parameter list, there should be at most one @ttype@ parameter that must occur last, otherwise the call can never resolve, given the previous rule. This idea essentially matches normal variadic semantics, with a strong feeling of similarity to \CCeleven{} variadic templates. As such, @ttype@ variables will also be referred to as \emph{argument packs}. 617 618 Like variadic templates, the main way to manipulate @ttype@ polymorphic functions is through recursion. Since nothing is known about a parameter pack by default, assertion parameters are key to doing anything meaningful. Unlike variadic templates, @ttype@ polymorphic functions can be separately compiled. 619 620 For example, the C @sum@ function at the beginning of this section could be written using @ttype@ as: 621 \begin{lstlisting} 622 int sum(){ return 0; } // (0) 623 forall(ttype Params | { int sum(Params); }) 624 int sum(int x, Params rest) { // (1) 625 return x+sum(rest); 626 } 627 sum(10, 20, 30); 628 \end{lstlisting} 629 Since (0) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@. 630 In order to call (1), @10@ is matched with @x@, and the argument resolution moves on to the argument pack @rest@, which consumes the remainder of the argument list and @Params@ is bound to @[20, 30]@. 631 In order to finish the resolution of @sum@, an assertion parameter which matches @int sum(int, int)@ is required. 632 Like in the previous iteration, (0) is not a valid candiate, so (1) is examined with @Params@ bound to @[int]@, requiring the assertion @int sum(int)@. 633 Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@. 634 Finally, (0) matches and (1) fails, which terminates the recursion. 635 Effectively, this traces as @sum(10, 20, 30)@ $\rightarrow$ @10+sum(20, 30)@ $\rightarrow$ @10+(20+sum(30))@ $\rightarrow$ @10+(20+(30+sum()))@ $\rightarrow$ @10+(20+(30+0))@. 636 637 A point of note is that this version does not require any form of argument descriptor, since the \CFA{} type system keeps track of all of these details. It might be reasonable to take the @sum@ function a step further to enforce a minimum number of arguments, which could be done simply: 638 \begin{lstlisting} 639 int sum(int x, int y){ 640 return x+y; 641 } 642 forall(ttype Params | { int sum(int, Params); }) 643 int sum(int x, int y, Params rest) { 644 return sum(x+y, rest); 645 } 646 sum(10, 20, 30); 647 \end{lstlisting} 648 649 One more iteration permits the summation of any summable type, as long as all arguments are the same type: 650 \begin{lstlisting} 651 trait summable(otype T) { 652 T ?+?(T, T); 653 }; 654 forall(otype R | summable(R)) 655 R sum(R x, R y){ 656 return x+y; 657 } 658 forall(otype R, ttype Params 659 | summable(R) 660 | { R sum(R, Params); }) 661 R sum(R x, R y, Params rest) { 662 return sum(x+y, rest); 663 } 664 sum(3, 10, 20, 30); 665 \end{lstlisting} 666 Unlike C, it is not necessary to hard code the expected type. This is naturally open to extension, in that any user-defined type with a @?+?@ operator is automatically able to be used with the @sum@ function. That is to say, the programmer who writes @sum@ does not need full program knowledge of every possible data type, unlike what is necessary to write an equivalent function using the standard C mechanisms. Summing arbitrary heterogeneous lists is possible with similar code by adding the appropriate type variables and addition operators. 667 668 It is possible to write a type-safe variadic print routine, which can replace @printf@ 669 \begin{lstlisting} 670 struct S { int x, y; }; 671 forall(otype T, ttype Params | 672 { void print(T); void print(Params); }) 673 void print(T arg, Params rest) { 674 print(arg); 675 print(rest); 676 } 677 void print(char * x) { printf("%s", x); } 678 void print(int x) { printf("%d", x); } 679 void print(S s) { print("{ ", s.x, ",", s.y, " }"); } 680 print("s = ", (S){ 1, 2 }, "\n"); 681 \end{lstlisting} 682 This example routine showcases a variadic-template-like decomposition of the provided argument list. The individual @print@ routines allow printing a single element of a type. The polymorphic @print@ allows printing any list of types, as long as each individual type has a @print@ function. The individual print functions can be used to build up more complicated @print@ routines, such as for @S@, which is something that cannot be done with @printf@ in C. 683 684 It is also possible to use @ttype@ polymorphism to provide arbitrary argument forwarding functions. For example, it is possible to write @new@ as a library function: 685 \begin{lstlisting} 686 struct Pair(otype R, otype S); 687 forall(otype R, otype S) 688 void ?{}(Pair(R, S) *, R, S); // (1) 689 690 forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); }) 691 T * new(Params p) { 692 return ((T*)malloc( sizeof(T) )){ p }; // construct into result of malloc 693 } 694 Pair(int, char) * x = new(42, '!'); 695 \end{lstlisting} 696 The @new@ function provides the combination of type-safe @malloc@ with a constructor call, so that it becomes impossible to forget to construct dynamically allocated objects. This provides the type-safety of @new@ in \CC{}, without the need to specify the allocated type, thanks to return-type inference. 697 698 In the call to @new@, @Pair(double, char)@ is selected to match @T@, and @Params@ is expanded to match @[double, char]@. To satisfy the assertion, a constructor with an interface compatible with @void ?{}(Pair(int, char) *, int, char)@ must exist in the current scope, which (1) may be specialized to match. 613 699 614 700 \TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so). 615 701 702 \subsection{Implementation} 703 704 Tuples are implemented in the \CFA{} translator via a transformation into generic types. For each $N$, the first time an $N$-tuple is seen in a scope a generic type with $N$ type parameters is generated. For example: 705 \begin{lstlisting} 706 [int, int] f() { 707 [double, double] x; 708 [int, double, int] y; 709 } 710 \end{lstlisting} 711 Is transformed into: 712 \begin{lstlisting} 713 forall(dtype T0, dtype T1 | sized(T0) | sized(T1)) 714 struct _tuple2 { // generated before the first 2-tuple 715 T0 field_0; 716 T1 field_1; 717 }; 718 _tuple2_(int, int) f() { 719 _tuple2_(double, double) x; 720 forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2)) 721 struct _tuple3 { // generated before the first 3-tuple 722 T0 field_0; 723 T1 field_1; 724 T2 field_2; 725 }; 726 _tuple3_(int, double, int) y; 727 } 728 \end{lstlisting} 729 730 Tuple expressions are then simply converted directly into compound literals: 731 \begin{lstlisting} 732 [5, 'x', 1.24]; 733 \end{lstlisting} 734 Becomes: 735 \begin{lstlisting} 736 (_tuple3_(int, char, double)){ 5, 'x', 1.24 }; 737 \end{lstlisting} 738 739 Since tuples are essentially structures, tuple indexing expressions are just field accesses: 740 \begin{lstlisting} 741 void f(int, [double, char]); 742 [int, double] x; 743 744 x.0+x.1; 745 printf("%d %g\n", x); 746 f(x, 'z'); 747 \end{lstlisting} 748 Is transformed into: 749 \begin{lstlisting} 750 void f(int, _tuple2_(double, char)); 751 _tuple2_(int, double) x; 752 753 x.field_0+x.field_1; 754 printf("%d %g\n", x.field_0, x.field_1); 755 f(x.field_0, (_tuple2){ x.field_1, 'z' }); 756 \end{lstlisting} 757 Note that due to flattening, @x@ used in the argument position is converted into the list of its fields. In the call to @f@, a the second and third argument components are structured into a tuple argument. Similarly, tuple member expressions are recursively expanded into a list of member access expressions. 758 759 Expressions which may contain side effects are made into \emph{unique expressions} before being expanded by the flattening conversion. Each unique expression is assigned an identifier and is guaranteed to be executed exactly once: 760 \begin{lstlisting} 761 void g(int, double); 762 [int, double] h(); 763 g(h()); 764 \end{lstlisting} 765 Interally, this is converted to two variables and an expression: 766 \begin{lstlisting} 767 void g(int, double); 768 [int, double] h(); 769 770 _Bool _unq0_finished_ = 0; 771 [int, double] _unq0; 772 g( 773 (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0, 774 (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1, 775 ); 776 \end{lstlisting} 777 Since argument evaluation order is not specified by the C programming language, this scheme is built to work regardless of evaluation order. The first time a unique expression is executed, the actual expression is evaluated and the accompanying boolean is true to true. Every subsequent evaluation of the unique expression then results in an access to the stored result of the actual expression. Tuple member expressions also take advantage of unique expressions in the case of possible impurity. 778 779 Currently, the \CFA{} translator has a very broad, imprecise definition of impurity, where any function call is assumed to be impure. This notion could be made more precise for certain intrinsic, autogenerated, and builtin functions, and could analyze function bodies when they are available to recursively detect impurity, to eliminate some unique expressions. 780 781 The various kinds of tuple assignment, constructors, and destructors generate GNU C statement expressions. A variable is generated to store the value produced by a statement expression, since its fields may need to be constructed with a non-trivial constructor and it may need to be referred to multiple time, \eg{} in a unique expression. The use of statement expressions allows the translator to arbitrarily generate additional temporary variables as needed, but binds the implementation to a non-standard extension of the C language. However, there are other places where the \CFA{} translator makes use of GNU C extensions, such as its use of nested functions, so this is not a new restriction. 782 783 Type assertions in \CFA{} generally require exact matching of parameter and return types, with no implicit conversions allowed. Tuple flattening and restructuring is an exception to this, however, allowing functions to match assertions without regard to the presence of tuples; this is particularly useful for structuring trailing arguments to match a @ttype@ parameter or flattening assertions based on @ttype@ type variables to match programmer-defined functions. This relaxation is made possible by extending the existing thunk generation scheme, as described by Bilson \citet{Bilson03}. Whenever a candidate's parameter structure does not exactly match the formal parameter's structure, a thunk is generated to specialize calls to the actual function, as in this conversion from a function @f@ with signature @int (*)(int, char, char)@ to another with signature @int (*)([int, char], char)@: 784 \begin{lstlisting} 785 int _thunk(int _p0, char _p1, char _p2) { 786 return f([_p0, _p1], _p2); 787 } 788 \end{lstlisting} 789 These thunks take advantage of GCC C nested functions to produce closures that have the usual function pointer signature. 790 616 791 \section{Related Work} 617 792 … … 622 797 \section{Conclusion \& Future Work} 623 798 624 In conclusion, the authors' design for generic types and tuples imposes minimal runtime overhead while still supporting a full range of C features, including separately-compiled modules. There is ongoing work on a wide range of \CFA{} feature extensions, including reference types, exceptions, and concurent programming primitives. In addition to this work, there are some interesting future directions the polymorphism design could take. Notably, \CC{} template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. \CFA{} polymorphic functions, by contrast, use an approach which is essentially dynamic virtual dispatch. The runtime overhead of this approach is low, but not as low as \CC{} template functions, and it may be beneficial to provide a mechanism for particularly performance-sensitive code to close this gap. Further research is needed, but two promising approaches are to allow an annotation on polymorphic function call sites that tells the compiler to create a template-specialization of the function (provided the code is visible in the current translation unit) or placing an annotation on polymorphic function definitions that instantiates a version of the polymorphic function specialized to some set of types. These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unneccessary.799 In conclusion, the authors' design for generic types and tuples imposes minimal runtime overhead while still supporting a full range of C features, including separately-compiled modules. There is ongoing work on a wide range of \CFA{} feature extensions, including reference types, exceptions, and concurent programming primitives. In addition to this work, there are some interesting future directions the polymorphism design could take. Notably, \CC{} template functions trade compile time and code bloat for optimal runtime of individual instantiations of polymorphic functions. \CFA{} polymorphic functions, by contrast, use an approach which is essentially dynamic virtual dispatch. The runtime overhead of this approach is low, but not as low as \CC{} template functions, and it may be beneficial to provide a mechanism for particularly performance-sensitive code to close this gap. Further research is needed, but two promising approaches are to allow an annotation on polymorphic function call sites that tells the translator to create a template-specialization of the function (provided the code is visible in the current translation unit) or placing an annotation on polymorphic function definitions that instantiates a version of the polymorphic function specialized to some set of types. These approaches are not mutually exclusive, and would allow these performance optimizations to be applied only where most useful to increase performance, without suffering the code bloat or loss of generality of a template expansion approach where it is unneccessary. 625 800 626 801 \bibliographystyle{ACM-Reference-Format}
Note: See TracChangeset
for help on using the changeset viewer.