RFC: trait-declared associated type synonyms

[pnkfelix]

Rust's type system reflects many advances in the state of the art.

However, there is one feature (offered by C++ and ML) that is not present in Rust: The ability to declare within a trait a named type (and then each impl item would be obligated to bind that name to an appropriate type for the implementation).

Related work: See Garcia et al. 2003, especially section 6.2, 10.2, and 10.3. Another useful reference is Chakravarty et al 2005

The Haskell community calls such a construct an "associated type synonym."

Here is an small example to illustrate the idea.

First, the easy part: how such a feature would look at the level of trait and impl items:

trait Graph {
  pub type Node;   // Graphs are composed of vertices
  pub type Edge;   // and arcs between the vertices.
  pub fn src(&self, edge: Edge) -> Node;
  pub fn tgt(&self, edge: Edge) -> Node;
}


// A vector of (source,target) pairs is a graph where the edges
// indices into the vector
impl<T : Copy> &[(T,T)] : Graph {
  pub type Node = T;    // Here we satisfy the obligation to provide Node
  pub type Edge = uint;  // and Edge implementation types.
  pub fn src(&self, edge: Edge) -> Node { let (s,_) = self[edge]; s }
  pub fn tgt(&self, edge: Edge) -> Node { let (_,t) = self[edge]; t }
}

Ideally one would extract the type from a trait by using a path, using a type parameter as a path component. So for example:

trait IncidenceGraph : Graph {
  pub fn out_degree(&self, node: self::Node) -> uint;
  pub fn out_edges(&self, node: self::Node, it: fn(self::Edge) -> bool);
}

fn children<G:IncidenceGraph>(&g:G, &n: G::Node) -> ~[G::Node] {
  let result = ~[];
  for g.out_edges(n) |e| {
    ret.push(g.tgt(n))
  }
  ret
}

Note: I am aware that one can express currently express type synonyms in much the same way that one does in Java (or C#, or Eiffel; see Garcia et al paper): by making them a type-parameter of the trait itself. Rust's type-inference system does make that workaround more palatable, but it seems natural to enable the developer to express what they mean more directly: These types are obligations of the implementation, much like the functions declared in the trait, and thus it makes sense to express them the same way.

---

There are various issues to consider: e.g.:

• Do we allow bounds on the type declarations in the trait,
• Is there is any potential ambiguity with module names introduced by allowing traits (or rather, type parameters implementing a trait) to appear as path components in paths that are used in a type-expression context.
• Are there any gotcha's or generalizations that have been uncovered by the broader PL community that we would want to address. (For example, GHC has indexed data families, with which I am not familiar but seem to be a generalization with some potential gotchas. Caveat: I am not a Haskell programmer.)

Despite the above issues, this seems like a relatively straightforward change to the language (especially since one can already encode the pattern, so adding it should not inject e..g any type soundness bugs, right?).

[nikomatsakis]

I don't think it's altogether straightforward :) --- but I do think it's something we should try and do.

I'd like to discuss this and related issues at the work week.

[nikomatsakis]

Related blog posts:

http://smallcultfollowing.com/babysteps/blog/2013/04/02/associated-items/
http://smallcultfollowing.com/babysteps/blog/2013/04/03/associated-items-continued/

cc #5527

[pnkfelix]

Related blog post:

http://blog.pnkfx.org/blog/2013/04/22/designing-syntax-for-associated-items-in-rust/

[bluss]

External iterators in traits may tie in to this issue as well:

12:22 < engla> An unmentioned(?) issue so far with external iterators is traits: We
               can't replace fn each, fn each_key etc in the Map trait, because we'd
               either need to specify a concrete iterator type as return value, or add
               a type variable for each iterator method in the trait
12:24 < engla> possibly the Map trait can afford to have one type variable for an
               .iter() method and let that be all
12:27 < engla> ah, the solution should of course be associated items

[pnkfelix]

Related bug: #6894. Though the various proposals may represent some divergence at this point.

[bstrie]

Nominating for Backwards-Compatible.

[bblum]

Did not mean to do that. Meant to remark on the similarity between this and ML signatures.

[graydon]

accepted for backwards-compatible milestone

[graydon]

(This carries backwards compatibility risk in terms of APIs changing; but we're not decided on whether to take it. it's something we need to discuss in full detail in a work-week or roadmap meeting.)

[erickt]

Has this been discussed in one of the meetings yet?

[nikomatsakis]

We discussed the general matter at our last retreat but I think the
decisions didn't "stick", we'll need to discuss more.

[pcwalton]

Nominating because I believe this is out of scope for 1.0.

[pnkfelix]

switching to P-high.

[rust-highfive]

This issue has been moved to the RFCs repo: rust-lang/rfcs#313