Function specialization

[jensnockert]

Code like this should work, preferably picking the most specialized function (and/or just picking a random one, or the first that matches &c. or just throw a warning)

pub fn abs<T: Signed>(value: T) -> T { value.abs() }
pub fn abs<T: Ord + Zero + Neg<T>>(v: T) -> T { if v < Zero::zero() { v.neg() } else { v } }

[bstrie]

Define "most specialized". The one with the highest number of generic bounds? Then when you refactor your code to collapse several bounds into one via trait inheritance, you've silently changed the meaning of the program. So then perhaps you could count the number of generic bounds by recursively expanding each trait into the ones it inherits from... but now fussing with traits anywhere higher in the inheritance chain can again silently change which function is selected, except arguably worse because it's action-at-a-distance.

"First that matches" also doesn't work, because non-closure functions have no concept of order. Note that this program works:

fn main() {
    foo();
    bar();

    fn bar() {
        foo();
        println("bar");
    }

    fn foo() {
        println("foo");
    }
}

I'm not necessarily opposed to this idea, but there needs to be a concrete proposal that considers these complications.

[jensnockert]

In this specific case it is quite obvious what would be the most specific trait, since Signed implies Ord, Zero, Neg and more.

I would consider the following rules something to start discussing,

1. Create a list of all generic fns with that name.
2. Remove all fns that don't match the signature of the call.
3. Remove from the list any fns with bounds that are implied by the bounds of another fn in the list.
4. If there is more than one fn, throw an error.

[catamorphism]

This is basically proposing something like the "most specific instance" rule in GHC when you pass in the -fallow-overlapping-instances flag. It may seem like a simple rule at first glance, but in GHC it has just caused more ambiguities (see http://web.cecs.pdx.edu/~jgmorris/pubs/morris-icfp2010-instances.pdf ). In general we should be paying attention to the trajectory of overlapping instances in Haskell when we consider these changes.

[thestinger]

I like the idea of specializing functions, but it seems like there are other ways to do it. Most of the time you just want a version for Bar + Foo and then Bar + !Foo. Are trait bound complements something we could have?

[jensnockert]

@thestinger Yeah, that is essentially the same thing as I want, just with different syntax.

[glaebhoerl]

In Haskell the reason it's impossible to have complements of constraints (or more generally to branch on the "otherwise" case in any way) is the open-world assumption. There's no way to rule out the possibility of an instance (impl for) being introduced in a different module. But this is tied in with the possibility of orphan instances in that language. Rust restricts impls for to the same crate as the trait or the same crate as the type, so if the compiler has full-crate knowledge of impls (alternately if they're restricted to same mod instead of same crate), it could determine with certainty when a trait is not implemented. This could in theory allow trait complements, and from there full boolean expressions on traits, because you can implement or with and and not. At that point it probably makes more sense to actually rename + to && and introduce ||.

What this ticket is asking for is actually more than that, because it's also asking for a kind of implicit C++-style overloading on functions. We already have implicit overloading for the self argument of method calls, so I can't really say "it's better to keep overloading restricted to traits", but in any case it's a separate issue.

Considering only the trait complements / boolean trait expressions half of it, obviously !Trait would not have any methods you could call, nor TraitA || TraitB. But it would still be useful:

• The impl for overlap checker could take bounds into consideration, which would both increase expressiveness and reduce confusion: in Haskell the absence of this regularly confuses newcomers. This is basically (with a bit more boilerplate) what would allow expressing the abs example in the OP. You could also do things like a maybe_to_str that uses ToStr if there's an impl for it and returns "couldn't describe" or None otherwise, or whatever. Or with the current Copy (for implicitly copyable types) vs Clone (for explicit copies) situation, it would allow you to actually write a default impl<T: Copy> Clone for T without conflicting with other impls of Clone for user-defined types that aren't implicitly copyable.
• || is useless for "normal" traits, but it has utility with built-in ones: there's a few places around RcMut, DeepClone, and such where either a Const or an Owned bound would suffice to rule out cycles, but you can't provide separate impls for both without conflicts. Here you could express it directly as T: Const || Owned.

Drawbacks:

• It adds more complexity to the language. Obviously.
• Checking for conflicts between generic impls -- whether both bounds can be satisfied at the same time -- seems to be the SAT problem, which is NP-complete. I don't know whether people would actually write impls complex enough that this becomes a problem in practice.

[huonw]

@bjz has a proposal for overlapping impl precedence; reproduced here for posterity:

One issue that limits the utility of traits is the fact that impling on the generic type T means that it is impossible to impl on anything else. Default methods will go some way to alleviating this, but it is still useful to have 'one impl to rule them all', then specialize on a per-type basis.

Precedence Hierarchy for Trait Impls

One option could be to have a precedence hierarchy for trait overloading. For example, in descending levels of precedence:

Precedence/Name	Examples
1. Concrete types	float, ~str, (int, int), Option<int>
2. Parameterized	Option<T>, (T, int), &[T]
3. Generic	T, &T, ~T, @T

This could lead to complex resolve issues however, which could lead to increased compile times, and thorny edge cases. It also might be hard for users to reason about which implementation is being used.

Errors

impl<T> Foo for (T, float, int) impl<T,U> Foo for (T, U, int) would be ok. impl<T,U> Foo for (T, float, U) impl<T,U> Foo for (T, U, int) would give an error.

Set operations for trait constraints?

Impls for T: Foo & !Bar, T: !Foo & Bar could co-exist? Might be hard for a human to reason about in a large codebase.

---

I think the arguments about overlapping instances in Haskell don't fully apply because Rust doesn't have the (entire) open world assumption like Haskell. In particular, I believe that, for any "pattern" that overlaps, Rust can see all of the possibilities at once, because at least one of the trait or type have to be defined in the current crate. E.g. you can't write

// crate1.rs
trait Foo {}
impl<T,U> Foo for (T,U) {}

// crate2.rs
impl<T> Foo for (T, int) {}

// crate3.rs
impl<U> Foo for (float, U) {}

and so you can never have the situation where importing crate3 (having imported crate2 previously) suddenly makes it not compile/behave different.

[chris-morgan]

My own specific desire with it is very simple, to do with augmented assignment (#5992).

Given a trait definition like this:

pub trait AddAssign<RHS> {
    #[inline]
    fn add_assign(&mut self, rhs: &RHS);
}

What I really want is simply this:

impl<LHS: Add<RHS, LHS>, RHS> AddAssign<RHS> for LHS {
    fn add_assign(&mut self, rhs: &RHS) {
        *self = *self + *rhs;
    }
}

This has the effect of making += work for any type where + works. But alas, this can't work at present.

A couple of ideas of mine:

• Have a priority attribute: it could have a default of 1, meaning that I could tack #[priority = 0] onto that impl block. Highest priority impl in scope wins—if there is more than one highest, you get an error indicating you can alter the priority to prefer one over the other where both are satisfied. This is explicit, which might be good or bad. I think it'd work fine and it would get implementers to think about it and be aware of it, but if abused it could lead to surprises for users. The original example shown could then be like this:

  #[priority=2]
  pub fn abs<T: Signed>(value: T) -> T { value.abs() }
  #[priority=1]
  pub fn abs<T: Ord + Zero + Neg<T>>(v: T) -> T { if v < Zero::zero() { v.neg() } else { v } }

  This also leaves scope for a more intelligent, automatic solution later if it were deemed appropriate (the existence of the attribute could then trigger an error indicating how it's changed).

• Use a boolean attribute #[default_impl], indicating that it can be overridden by an impl unadorned by #[default_impl]. My own feeling is that this would satisfy the majority of cases where specialisation is really really useful, but it's certainly not as powerful; it can't do the first example other than as a nasty hack.

[glaebhoerl]

@huonw, good point. I believe you could still have that situation when importing different modules from the same crate? But maybe that's no longer concern-worthy? The other criticism levelled in the SO answer still holds: if upstream adds a new, more specific impl, that could silently change the behaviour of downstream code. It seems like a good idea to preserve the property that merely adding something new can't change the behaviour of something that already exists. I think this will be a problem with any system where you have 'one impl to rule them all' that you can override on a per-case basis. Would it be so burdensome to have to write an empty impl Trait for Type { }, instead of it being fully automatic?

(Apropos, GHC has a feature called DefaultSignatures. Basically what that does is it lets you write a default implementation for a method with a more specific signature than the method itself (e.g. additional trait bounds), and the default is generated only if the more specific signature is satisfied. But you still have to declare the impl.)

FWIW I think a system with explicitly negated traits and strict-but-taking-bounds-into-consideration overlap checking would also allow similar problems:

trait Trait1 { ... }
trait Trait2 { ... }
impl<T: Trait1> Trait2 for T { ... }
impl<T: !Trait1> Trait2 for T { ... } // these cannot possibly overlap, so our hypothetical compiler accepts it

Now if you add an impl Trait1 for Foo, that could cause code using Foo: Trait2 to change behaviour. I'm not sure whether this is "less bad" in any way? (At least it's being somewhat more explicit about the logic...)

@chris-morgan, two questions:

• Would it be so awful if you had to write impl<RHS> AddAssign<RHS> for LHS { } for a given LHS that already impls Add?
• Would it be tolerable if the "default" AddAssign impl you propose would be allowed, and you could still add other impls, but only for types that don't impl Add (so there's no overlap)? I think this is basically what you could get with the explicit-negation-and-fine-grained-overlap-checking scheme... (though as above that doesn't seem to be free of problems either).

Your #[default_impl] idea would be similar to the GHC/Haskell status quo: what the OverlappingInstances language extension actually does is it sets a "this instance is overlappable" flag for the instances in that module. So it's opt-in, which is at least better than overlap being allowed globally. Might be the least-bad option if the use case is undeniable and we don't find a better solution.

I believe Rust used to have explicit import/export of impls, but that was dropped in favor of requiring global coherence. I'm wondering if some of the reasons behind that decision (which I'm not familiar with) might not also apply here?

[chris-morgan]

@glehel:

1. Is it so awful for people to need to write #[deriving(Clone,DeepClone,Eq,IForgetWhatElseShouldGoHere)]? There's argument about that, with many in favour of simplifying things because normally you will want these things automatically filled in. AddAssign is the same: it doesn't tend to make sense for x = x + y to work and x += y not to work.

   Also, it does not end up simply impl<RHS> AddAssign<RHS> for LHS;, as the trait cannot have a default implementation; it would need to include the fn add_assign(&mut self, rhs: &RHS) { *self = *self + *other; }. That's one of the problems I perceive with the current implementation of default trait implementations: often it's quite reasonable for a trait not to require constraints, but for a default implementation to require constraints; in this case, the best I can do for a default implementation is:

     pub trait AddAssign<RHS>: Add<RHS, Self> {
         #[inline]
         fn add_assign(&mut self, rhs: &RHS) {
             *self = *self + *rhs;
         }
     }

   ... but still, it is conceivable that one might have a type where they do not wish to implement Add (it might be an extremely expensive operation, and something like + would mask that) but do wish to implement AddAssign (as it can be implemented cheaply), so I don't like an implementation of AddAssign<RHS> to require an implementation of Add<RHS, Self>, where there can be no good reason for it beyond the convenience of the default method.

2. No, it would not be tolerable to only be able to overridde AddAssign if Add is not implemented. As a generalisation, if one is supported, both should be. (This isn't quite true, e.g. &str implements Add but cannot implement AddAssign, but if the bare type can be modified then it should be true.) However, while the default AddAssign impl will work in most cases, it will almost never be quite the most efficient way to do it, as AddAssign can be an in-place modification—e.g. for a struct MyInt{ i: int } one can do self.i += other.i rather than what effectively becomes *self = *MyInt { i: self.i + other.i }. As you can see, this could rapidly become more expensive.

[glaebhoerl]

@chris-morgan, wrt

That's one of the problems I perceive with the current implementation of default trait implementations: often it's quite reasonable for a trait not to require constraints, but for a default implementation to require constraints

that's exactly what GHC's DefaultSignatures allows. I'm not sure how it could be formulated for Rust; where in Haskell you'd write (try to ignore the IO noise):

class AddAssign rhs self where
    add_assign :: IORef self -> rhs -> IO () -- signature of method
    default add_assign :: Add rhs self self => IORef self -> rhs -> IO () -- signature for default
    add_assign self rhs = do
        self' <- readIORef self
        writeIORef self (add self' rhs)

if you try to translate that to Rust:

trait AddAssign<RHS> {
    fn add_assign(&mut self, rhs: &RHS); //method
    fn add_assign<???>(&mut self, rhs: &RHS) { *self = *self + *rhs; } //default
}

What goes in ???? Self: Add<RHS, Self>? But AFAIK you can only introduce new type variables there, not put constraints on existing ones. (Would be nice to have an explicit default too, or some other way to make the meaning more obvious, but Rust doesn't have it as a keyword.)

Anyways, the point is not to bikeshed syntax, I originally wanted to translate it into Rust to help explain what it does.

[huonw]

FWIW, both @thestinger and I have also found uses for implementing a default method when Self implements a certain trait, without having to inherit from that trait. (i.e. In some instances one can provide a useful default, but not always.)

[huonw]

This can & should be converted into a new-style RFC.

[japaric]

I've been playing with vectors, matrices and BLAS, and I've encounter this issue repeatedly. See this gist for an example.

I've independently reach the solutions formulated by @chris-morgan in his first comment. Namely:

• Annotate with #[fallback] the generic/weak implementation. This solves cases where two implementations collide, by ignoring the #[fallback] implementation.
• The above idea can be extended with priorities, to solve the collision of three or more implementations. (But I have yet to encounter this situation in practice)

[rust-highfive]

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