source: doc/proposals/associated_types.md @ f898983

## Associated Types ##

In Cforall today, traits can denote the relationship between two types, e.g:

        trait points_to(otype pointer, dtype element) {
                element& *?(pointer);
        }

In many such cases, some subset of the trait parameters will (almost-)always uniquely determine the others (for instance, the iterator type of a generic collection is typically determined by the combination of the collection and element types). In this case, it may be excessively verbose to list the constrained types as type parameters, as well as introducing new type variables (and possibly further resolution overhead). This proposal introduces _associated types_ to address this issue.

An associated type would be a new sort of type assertion, indicating that a unique best type exists to satisfy the remainder of the trait, given the remaining trait parameters, as in the following example:

        trait pointer_like(otype pointer) {
                dtype element;  // associated type, inferred from *? below

                element& *?(pointer);
        };

To resolve an assertion like `pointer_like(P)`, the Cforall compiler would find all interpretations of `E& *?(P)`, binding `element` to the `E` from the lowest-cost alternative (no alternative means a resolution failure, multiple min-cost alternatives is an ambiguous result, as usual). If there was more than one trait assertion involving `element`, the cost would be summed over interpretations of all relevant traits. The associated type could be named as `pointer_like(P).element` (similarly to nested types in structs).

Information about associated types would be passed to polymorphic functions the same way information about existing type parameters is passed.

Note that associated types could interact quite cleanly with fully-explicit traits, as in this equivalent formulation of `pointer_like`:

        trait pointer_like(otype pointer) {
                dtype element | points_to(pointer, element);
        };

### Disambiguation ###

If there is no unique best interpretation of an associated type, or if the programmer wants to specify an alternate interpretation in a local scope, the following syntax can be used to explicitly bind an associated type:

        struct list_node {
                int val;
                list_node* next;
        };
        
        int& *?(list_node* n) { return n->val; }

        trait pointer_like(list_node*) {
                dtype element = int;
        };

These explicit specializations could likely be placed under a `forall` clause to be more general:

        forall(otype T) trait forward_iterator(vector_iter(T)) {
                otype element = T;
        };

### Nominal Inheritance ###

This trait specialization syntax could also be used, with a new annotation on the traits, to provide nominal inheritance of traits, e.g:

        extern trait random_access_iterator(otype I | forward_iterator(I)) {};

        forall(otype T) random_access_iterator(vector_iter(T)) {};

I used `extern` here to not add a new keyword, I think it fits the idea of "the definition is somewhere else" of the existing meaning of `extern`. Other options include a zero-arg pseudo-trait `nominal()` that could go in the trait's constraint list.