Repository navigation
RFC: trait-declared associated type synonyms #5033
Description
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?).
Activity
nikomatsakis commentedon Mar 7, 2013
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 commentedon Apr 5, 2013
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 commentedon May 2, 2013
Related blog post:
http://blog.pnkfx.org/blog/2013/04/22/designing-syntax-for-associated-items-in-rust/
bluss commentedon Jun 18, 2013
External iterators in traits may tie in to this issue as well:
pnkfelix commentedon Jun 18, 2013
Related bug: #6894. Though the various proposals may represent some divergence at this point.
bstrie commentedon Jul 18, 2013
Nominating for Backwards-Compatible.
bblum commentedon Jul 25, 2013
Did not mean to do that. Meant to remark on the similarity between this and ML signatures.
graydon commentedon Aug 8, 2013
accepted for backwards-compatible milestone
graydon commentedon Aug 8, 2013
(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 commentedon Aug 29, 2013
Has this been discussed in one of the meetings yet?
nikomatsakis commentedon Aug 29, 2013
We discussed the general matter at our last retreat but I think the
decisions didn't "stick", we'll need to discuss more.
pcwalton commentedon Nov 22, 2013
Nominating because I believe this is out of scope for 1.0.
pnkfelix commentedon Dec 19, 2013
switching to P-high.
rust-highfive commentedon Sep 24, 2014
This issue has been moved to the RFCs repo: rust-lang/rfcs#313
Auto merge of rust-lang#5033 - JohnTitor:split-use-self, r=flip1995
Merge pull request rust-lang#5033 from RalfJung/ci
Merge rust-lang#5033