Negative bounds & mutually exclusive traits


#1

I’ve been reading through the discussions of trait specialization and negative bounds (particularly RFC #586). I am working on a library which impls a spec which would require some kind of negative trait bound to be implemented correctly (the spec in question is the transit format; the issue concerns the division between scalar and composite types).

I think I have a solution to the problem presented in the prior RFC discussion, & I’d like to hear feedback on its feasibility:

  1. For every trait Foo there exists a ‘negative trait’ !Foo, which has no methods or associated types. !Foo is implicitly defined whenever Foo is defined (and cannot be explicitly defined), and is imported whenever Foo is imported, but it is not implemented implicitly when Foo is not; it must be explicitly implemented.
  2. Foo and !Foo are mutually exclusive. It is a coherence violation for a type to impl both Foo and !Foo.

In reifying !Foo as a “real trait” like this, the semantics of negative bounds become much simpler and much less dangerous: the negative bound T: !Foo does not mean that T does not impl Foo, but that it impls !Foo. Thus, adding new trait impls to types is not a backwards compatibility hazard. In fact, negative traits work exactly the same way as positive traits: adding an additional bound is incompatible, removing a bound is not; removing an impl is incompatible, adding one is not.

Negative impls and bounds could be added to the std library and associated libraries where two traits are not intended to cohere in a single type. To take examples from the the num crate, Integer could be bound !Float, and Float could be bound !Integer, while the Unsigned marker trait could be removed and types which would impl it could instead impl !Signed. std library types like String and Vec<T> could impl !Num, given that they are not numeric types.

Introduing this mutual exclusivity would enable newly defined traits in third party libraries to piggy-back on standard traits. As a trivial example, a crate introducing additional mathematical functions with the trait Foo could now impl<T> Foo for T where T: Integer and impl<T> Foo for T where T: Float, and there would be no coherence conflict, because it would be incoherent for a trait to simultaneously impl those two traits according to their bounds.

This ability to implement blanket impls for different traits is the primary benefit of this change, though it is also has the subsidiary benefit of enabling the definition of traits as exclusive for the purpose of ensuring that client programs do not implement both traits for a single type, which would be logically incoherent but not restricted by the type system at present (such as Signed and Unsigned).


#2

I think it is a bad idea to make !Foo mean such a weird thing. It’s more logical to just somehow explicitly declare 2 traits as mutually exclusive.

Another problem is that this proposal does not solve specialization.


#3

Could you elaborate on this? I don’t know what you mean when you say this would make !Foo mean something weird, and it makes me think I didn’t explain the concept well. In terms of impl !Foo, this is really what it means right now (though it can only be applied to built-in traits currently). In terms of bounds, it means exactly what it says in the text: T: !Foo must impl !Foo.

I don’t know how it would be possible to declare two traits as mutually exclusive except through a mechanism like this: this is declaring two traits to be mutually exclusive (by bounding one to the negative impl of the the other).

What this does is make negative bounds more explicit: a trait only meets a negative bound if it is explicitly declared not to impl that trait, to resolve the backwards compat hazard of the prior proposal. It also makes negative bounds much simpler conceptually by only adding one new coherence rule: that Foo and !Foo are mutually exclusive traits.

No but it isn’t intended to. Specialization & negative bounds are different.


#4

So this introduces a third ‘in-between’ state, where a type may be T: Foo, T: !Foo and T? Basing an example on this comment, what would the final step be in exhaustively implement the following trait for all types?

trait IsShow { fn number(&self) -> i32 }

impl<T: !Debug> IsShow for T {
    fn number(&self) -> i32 { -1 }
}
impl<T: Debug> IsShow for T {
    fn number(&self) -> i32 { 1 }
}

#5

It would be intentional that you could not exhaustively impl a trait for all types dependent on its impl of another trait. That seems like a misfeature, given that it would make adding an impl a backwards incompatible change.

It would still be possible to impl a trait for all types with impl Foo for .. {}, though that would be overriden like it currently is by impl !Foo for Bar {}. Adding a negative impl of a trait universally impl’d is already a backwards incompatible change, and wouldn’t change. Symmetry would imply that one could also impl !Foo for .. {}, which I don’t think (?) is currently possible.


#6

@td_ I think you misunderstood something. For example:

  • impl Foo for .. {} does not implement a trait for all types impl<T: ?Sized> Foo for T {} does that.
  • impl Foo for Bar {} overrides impl !Foo for Bar {}
  • impl !Foo for Bar {} is possible only if you have impl Foo for .. {}

Read this for more info

Note: negative impl and negative bounds are very different


#7

I have read the OIBIT RFC, and I understand the difference between negative bounds and negative traits. We seem to be mis-communicating.

A default impl does impl the trait for any type that does not have a negative impl (and for which no member has a negative impl). If my prior statements have implied I don’t understand that it is possible to override default impls, I was not being clear and I apologize.

This is not true. These impls conflict.


Let me try to restate the idea of this thread to see if it’ll be clearer.

New rules (the first and third are generalizations of current rules, the second is the only new concept):

  • Allow negative impls for every traits, not only traits which have a default impl.
  • Allow types to be bound negatively, meaning that that the trait has been negatively implemented for that type, not that that trait is not implemented for that type.
  • (Optionally) allow negative default impls of trait as well as positive ones (which would be overridden by positive impls the same way that positive default impls are overriden by negative impls).

Everything else stays the same; pertinent rules that help elucidate the benefits of this change:

  • Negative and positive impls of a trait conflict.
  • Impls for T: Foo do not conflict with impls for types which are !Foo.

From these small changes to the type system, it becomes possible for traits to be declared mutually exclusive, for types to be declared not some trait (which is currently possible only for some traits), and for negative bounds to be implemented in a way which avoids backwards compatibility hazards.