Ignore:
Timestamp:
Feb 28, 2019, 2:24:42 PM (6 years ago)
Author:
Aaron Moss <a3moss@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
7db48364
Parents:
d1b1063
Message:

thesis: ch.3 second draft

File:
1 edited

Legend:

Unmodified
Added
Removed
  • doc/theses/aaron_moss_PhD/phd/generic-types.tex

    rd1b1063 r58732d1  
    502502\section{Future Work}
    503503
    504 The generic types design presented here is already sufficiently expressive to implement a variety of useful library types.
     504The generic types presented here are already sufficiently expressive to implement a variety of useful library types.
    505505However, some other features based on this design could further improve \CFA{}.
    506506
    507507The most pressing addition is the ability to have non-type generic parameters.
    508 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.
    509 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.
    510 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.
    511 
    512 The implementation mechanisms behind this generic types design can also be used to add new features to \CFA{}.
    513 One such potential feature would be to add \emph{field assertions} to the existing function and variable assertions on polymorphic type variables.
     508C 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.
     509% 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.
     510% 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.
     511
     512The implementation mechanisms behind generic types can also be used to add new features to \CFA{}.
     513One such potential feature is \emph{field assertions}, an addition to the existing function and variable assertions on polymorphic type variables.
     514These assertions could be specified using this proposed syntax:
     515
     516\begin{cfa}
     517trait hasXY(dtype T) {
     518        int T.x;  $\C{// T has a field x of type int}$
     519        int T.y;  $\C{// T has a field y of type int}$
     520};
     521\end{cfa}
     522
    514523Implementation of these field assertions would be based on the same code that supports member access by dynamic offset calculation for dynamic generic types.
    515524Simulating 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.
    516 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{}.
    517 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.
    518 \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.
     525Of 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.
     526
     527If 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:
     528
     529\begin{cfa}
     530struct point { int x, y; };  $\C{// traitof(point) is equivalent to hasXY above}$
     531struct coloured_point { int x, y; enum { RED, BLACK } colour };
     532
     533// works for both point and coloured_point
     534forall(dtype T | traitof(point)(T) )
     535double hypot( T& p ) { return sqrt( p.x*p.x + p.y*p.y ); }
     536\end{cfa}
     537
     538\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.
    519539
    520540With 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.
    521 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.
    522 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.
    523 These approaches are not mutually exclusive and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
    524 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.
     541However, 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.
     542Two 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.
     543These approaches are complementary and allow performance optimizations to be applied only when necessary, without suffering global code bloat.
Note: See TracChangeset for help on using the changeset viewer.