source: doc/proposals/

Last change on this file was f7b9faf, checked in by Aaron Moss <a3moss@…>, 5 years ago

Updated associated types working doc

  • Property mode set to 100644
File size: 3.0 KB
1## Associated Types ##
3In Cforall today, traits can denote the relationship between two types, e.g:
5        trait points_to(otype pointer, dtype element) {
6                element& *?(pointer);
7        }
9In 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.
11An 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:
13        trait pointer_like(otype pointer) {
14                dtype element;  // associated type, inferred from *? below
16                element& *?(pointer);
17        };
19To 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).
21Information about associated types would be passed to polymorphic functions the same way information about existing type parameters is passed.
23Note that associated types could interact quite cleanly with fully-explicit traits, as in this equivalent formulation of `pointer_like`:
25        trait pointer_like(otype pointer) {
26                dtype element | points_to(pointer, element);
27        };
29### Disambiguation ###
31If 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:
33        struct list_node {
34                int val;
35                list_node* next;
36        };
38        int& *?(list_node* n) { return n->val; }
40        trait pointer_like(list_node*) {
41                dtype element = int;
42        };
44These explicit specializations could likely be placed under a `forall` clause to be more general:
46        forall(otype T) trait forward_iterator(vector_iter(T)) {
47                otype element = T;
48        };
50### Nominal Inheritance ###
52This trait specialization syntax could also be used, with a new annotation on the traits, to provide nominal inheritance of traits, e.g:
54        extern trait random_access_iterator(otype I | forward_iterator(I)) {};
56        forall(otype T) random_access_iterator(vector_iter(T)) {};
58I 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.
Note: See TracBrowser for help on using the repository browser.