Context Navigation

-                      r626da644
+                      r41cd57c0
 \item Extensions introduced by \CFA{} must be translated in the most efficient way possible.
 \end{enumerate}
 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.
+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).
 \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.
 …
 \end{lstlisting}
 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@.
 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@.}.
+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@.}.
 \subsection{Traits}
 …
 \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.
+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:
+\subsection{Concrete Generic Types}
+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:
 \begin{lstlisting}
 struct _pair_conc1 {
 …
 \end{lstlisting}
+\subsection{Dynamic Generic Types}
 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.
 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) };@.
 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@.
+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) };@.
+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@.
 % \begin{lstlisting}
 % static inline void _layoutof_pair(size_t* _szeof_pair, size_t* _alignof_pair, size_t* _offsetof_pair,
 …
 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.
+\subsection{Applications}
 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:
 \begin{lstlisting}
 …
 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]@.
+\TODO{}
+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:
+\begin{lstlisting}
+[int, char] most_frequent(const char * str) {  // tuple return type
+  char freqs [26] = { 0 };
+  int ret_freq = 0;
+  char ret_ch = 'a';
+  for (int i = 0; str[i] != '\0'; ++i) {
+    if (isalpha(str[i])) {  // only count letters
+      int ch = tolower(str[i]);  // convert to lower case
+      int idx = ch-'a';
+      if (++freqs[idx] > ret_freq) {  // update on new max
+        ret_freq = freqs[idx];
+        ret_ch = ch;
+      }
+    }
+  }
+  return [ret_freq, ret_ch];  // return tuple expression
+}
+\end{lstlisting}
+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.
+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.
+\begin{lstlisting}
+const char * str = "hello world";
+int freq;
+char ch;
+[freq, ch] = most_frequent(str);  // assign into multiple variables
+printf("%s -- %d %c\n", str, freq, ch);
+\end{lstlisting}
+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,
+\begin{lstlisting}
+void process(int);       // (1)
+void process(char);      // (2)
+void process(int, char); // (3)
+void process(char, int); // (4)
+process(most_frequent("hello world"));  // selects (3)
+\end{lstlisting}
+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.
+\subsection{Polymorphism}
+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.
+\begin{lstlisting}
+forall(otype T, dtype U)
+void f(T x, U * y);
+f([5, "hello"]);
+\end{lstlisting}
+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.
+Tuples, however, can contain polymorphic components. For example, a plus operator can be written to add two triples of a type together.
+\begin{lstlisting}
+forall(otype T | { T ?+?(T, T); })
+[T, T, T] ?+?([T, T, T] x, [T, T, T] y) {
+  return [x.0+y.0, x.1+y.1, x.2+y.2];
+}
+[int, int, int] x;
+int i1, i2, i3;
+[i1, i2, i3] = x + ([10, 20, 30]);
+\end{lstlisting}
+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:
+\begin{lstlisting}
+int f([int, double], double);
+forall(otype T, otype U | { T f(T, U, U); })
+void g(T, U);
+g(5, 10.21);
+\end{lstlisting}
+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.
+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:
+\begin{lstlisting}
+int _thunk(int _p0, double _p1, double _p2) {
+  return f([_p0, _p1], _p2);
+}
+\end{lstlisting}
+Essentially, this provides flattening and structuring conversions to inferred functions, improving the compatibility of tuples and polymorphism.
+\subsection{Variadic Tuples}
+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}.
+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.
+For example, the C @sum@ function at the beginning of this section could be written using @ttype@ as:
+\begin{lstlisting}
+int sum(){ return 0; }        // (0)
+forall(ttype Params | { int sum(Params); })
+int sum(int x, Params rest) { // (1)
+  return x+sum(rest);
+}
+sum(10, 20, 30);
+\end{lstlisting}
+Since (0) does not accept any arguments, it is not a valid candidate function for the call @sum(10, 20, 30)@.
+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]@.
+In order to finish the resolution of @sum@, an assertion parameter which matches @int sum(int, int)@ is required.
+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)@.
+Next, (0) fails, and to satisfy (1) @Params@ is bound to @[]@, requiring an assertion @int sum()@.
+Finally, (0) matches and (1) fails, which terminates the recursion.
+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))@.
+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:
+\begin{lstlisting}
+int sum(int x, int y){
+  return x+y;
+}
+forall(ttype Params | { int sum(int, Params); })
+int sum(int x, int y, Params rest) {
+  return sum(x+y, rest);
+}
+sum(10, 20, 30);
+\end{lstlisting}
+One more iteration permits the summation of any summable type, as long as all arguments are the same type:
+\begin{lstlisting}
+trait summable(otype T) {
+  T ?+?(T, T);
+};
+forall(otype R | summable(R))
+R sum(R x, R y){
+  return x+y;
+}
+forall(otype R, ttype Params
+  | summable(R)
+  | { R sum(R, Params); })
+R sum(R x, R y, Params rest) {
+  return sum(x+y, rest);
+}
+sum(3, 10, 20, 30);
+\end{lstlisting}
+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.
+It is possible to write a type-safe variadic print routine, which can replace @printf@
+\begin{lstlisting}
+struct S { int x, y; };
+forall(otype T, ttype Params |
+  { void print(T); void print(Params); })
+void print(T arg, Params rest) {
+  print(arg);
+  print(rest);
+}
+void print(char * x) { printf("%s", x); }
+void print(int x) { printf("%d", x);  }
+void print(S s) { print("{ ", s.x, ",", s.y, " }"); }
+print("s = ", (S){ 1, 2 }, "\n");
+\end{lstlisting}
+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.
+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:
+\begin{lstlisting}
+struct Pair(otype R, otype S);
+forall(otype R, otype S)
+void ?{}(Pair(R, S) *, R, S);  // (1)
+forall(dtype T, ttype Params | sized(T) | { void ?{}(T *, Params); })
+T * new(Params p) {
+  return ((T*)malloc( sizeof(T) )){ p }; // construct into result of malloc
+}
+Pair(int, char) * x = new(42, '!');
+\end{lstlisting}
+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.
+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.
 \TODO{} Check if we actually can use ttype parameters on generic types (if they set the complete flag, it should work, or nearly so).
+\subsection{Implementation}
+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:
+\begin{lstlisting}
+[int, int] f() {
+  [double, double] x;
+  [int, double, int] y;
+}
+\end{lstlisting}
+Is transformed into:
+\begin{lstlisting}
+forall(dtype T0, dtype T1 | sized(T0) | sized(T1))
+struct _tuple2 {  // generated before the first 2-tuple
+  T0 field_0;
+  T1 field_1;
+};
+_tuple2_(int, int) f() {
+  _tuple2_(double, double) x;
+  forall(dtype T0, dtype T1, dtype T2 | sized(T0) | sized(T1) | sized(T2))
+  struct _tuple3 {  // generated before the first 3-tuple
+    T0 field_0;
+    T1 field_1;
+    T2 field_2;
+  };
+  _tuple3_(int, double, int) y;
+}
+\end{lstlisting}
+Tuple expressions are then simply converted directly into compound literals:
+\begin{lstlisting}
+[5, 'x', 1.24];
+\end{lstlisting}
+Becomes:
+\begin{lstlisting}
+(_tuple3_(int, char, double)){ 5, 'x', 1.24 };
+\end{lstlisting}
+Since tuples are essentially structures, tuple indexing expressions are just field accesses:
+\begin{lstlisting}
+void f(int, [double, char]);
+[int, double] x;
+x.0+x.1;
+printf("%d %g\n", x);
+f(x, 'z');
+\end{lstlisting}
+Is transformed into:
+\begin{lstlisting}
+void f(int, _tuple2_(double, char));
+_tuple2_(int, double) x;
+x.field_0+x.field_1;
+printf("%d %g\n", x.field_0, x.field_1);
+f(x.field_0, (_tuple2){ x.field_1, 'z' });
+\end{lstlisting}
+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.
+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:
+\begin{lstlisting}
+void g(int, double);
+[int, double] h();
+g(h());
+\end{lstlisting}
+Interally, this is converted to two variables and an expression:
+\begin{lstlisting}
+void g(int, double);
+[int, double] h();
+_Bool _unq0_finished_ = 0;
+[int, double] _unq0;
+g(
+  (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).0,
+  (_unq0_finished_ ? _unq0 : (_unq0 = f(), _unq0_finished_ = 1, _unq0)).1,
+);
+\end{lstlisting}
+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.
+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.
+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.
+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)@:
+\begin{lstlisting}
+int _thunk(int _p0, char _p1, char _p2) {
+  return f([_p0, _p1], _p2);
+}
+\end{lstlisting}
+These thunks take advantage of GCC C nested functions to produce closures that have the usual function pointer signature.
 \section{Related Work}
 …
 \section{Conclusion \& Future Work}
 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.
+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.
 \bibliographystyle{ACM-Reference-Format}

Note: See TracChangeset for help on using the changeset viewer.

Context Navigation

Changeset 41cd57c0 for doc/generic_types

Legend:

doc/generic_types/generic_types.tex

Download in other formats: