Index: doc/theses/aaron_moss_PhD/phd/generic-types.tex =================================================================== --- doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision d1b1063587a3db7fe1dd54342b9e0a8b6017475b) +++ doc/theses/aaron_moss_PhD/phd/generic-types.tex (revision 58732d140485035d0ea401fb1315d9cf484c30ab) @@ -502,23 +502,42 @@ \section{Future Work} -The generic types design presented here is already sufficiently expressive to implement a variety of useful library types. +The generic types presented here are already sufficiently expressive to implement a variety of useful library types. However, some other features based on this design could further improve \CFA{}. The most pressing addition is the ability to have non-type generic parameters. -C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters, and allowing \CFA{} users the capability to build similar types is a requested feature. -More exotically, the ability to have these non-type parameters depend on dynamic runtime values rather than static compile-time constants opens up interesting opportunities for type-checking problematic code patterns. -For example, if a collection iterator was parameterized over the pointer to the collection it was drawn from, then a sufficiently powerful static analysis pass could ensure that that iterator was only used for that collection, eliminating one source of hard-to-find bugs. - -The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}. -One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables. +C already supports fixed-length array types, \eg{} !int[10]!; these types are essentially generic types with unsigned integer parameters (\ie{} array dimension), and allowing \CFA{} users the capability to build similar types is a requested feature. +% More exotically, the ability to have these non-type parameters depend on dynamic runtime values rather than static compile-time constants opens up interesting opportunities for type-checking problematic code patterns. +% For example, if a collection iterator was parameterized over the pointer to the collection it was drawn from, then a sufficiently powerful static analysis pass could ensure that that iterator was only used for that collection, eliminating one source of hard-to-find bugs. + +The implementation mechanisms behind generic types can also be used to add new features to \CFA{}. +One such potential feature is \emph{field assertions}, an addition to the existing function and variable assertions on polymorphic type variables. +These assertions could be specified using this proposed syntax: + +\begin{cfa} +trait hasXY(dtype T) { + int T.x; $\C{// T has a field x of type int}$ + int T.y; $\C{// T has a field y of type int}$ +}; +\end{cfa} + Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types. Simulating field access can already be done more flexibly in \CFA{} by declaring a trait containing an accessor function to be called from polymorphic code, but these accessor functions impose some overhead both to write and call, and directly providing field access via an implicit offset parameter would be both more concise and more efficient. -Of course, there are language design trade-offs to such an approach, notably that providing the two similar features of field and function assertions would impose a burden of choice on programmers writing traits, with field assertions more efficient, but function assertions more general; given this open design question we have deferred a decision on field assertions until we have more experience using \CFA{}. -If field assertions are included in the language, a natural extension would be to provide a structural inheritance mechanism for every !struct! type that simply turns the list of !struct! fields into a list of field assertions, allowing monomorphic functions over that type to be generalized to polymorphic functions over other similar types with added or reordered fields. -\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- the layout function would need to be re-written, but nothing in the use of the offset arrays implies that the field offsets need be monotonically increasing. +Of course, there are language design trade-offs to such an approach, notably that providing the two similar features of field and function assertions would impose a burden of choice on programmers writing traits, with field assertions more efficient, but function assertions more general; given this open design question a decision on field assertions is deferred until \CFA{} is more mature. + +If field assertions are included in the language, a natural extension would be to provide a structural inheritance mechanism for every !struct! type that simply turns the list of !struct! fields into a list of field assertions, allowing monomorphic functions over that type to be generalized to polymorphic functions over other similar types with added or reordered fields, for example: + +\begin{cfa} +struct point { int x, y; }; $\C{// traitof(point) is equivalent to hasXY above}$ +struct coloured_point { int x, y; enum { RED, BLACK } colour }; + +// works for both point and coloured_point +forall(dtype T | traitof(point)(T) ) +double hypot( T& p ) { return sqrt( p.x*p.x + p.y*p.y ); } +\end{cfa} + +\CFA{} could also support a packed or otherwise size-optimized representation for generic types based on a similar mechanism --- nothing in the use of the offset arrays implies that the field offsets need to be monotonically increasing. With respect to the broader \CFA{} polymorphism design, the experimental results in Section~\ref{generic-performance-sec} demonstrate that though the runtime impact of \CFA{}'s dynamic virtual dispatch is low, it is not as low as the static dispatch of \CC{} template inlining. -However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, we are considering more targeted mechanisms for performance-sensitive code. -Two promising approaches are are an !inline! annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing a different !inline! annotation on polymorphic function definitions to instantiate a specialized version of the function for some set of types. -These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat. -In general, the \CFA{} team believes that separate compilation works well with loaded hardware caches by producing smaller code, which may offset the benefit of larger inlined code. +However, rather than subject all \CFA{} users to the compile-time costs of ubiquitous template expansion, it is better to target performance-sensitive code more precisely. +Two promising approaches are an !inline! annotation at polymorphic function call sites to create a template specialization of the function (provided the code is visible) or placing a different !inline! annotation on polymorphic function definitions to instantiate a specialized version of the function for some set of types. +These approaches are complementary and allow performance optimizations to be applied only when necessary, without suffering global code bloat.