Pre-RFC: Trait Kind

language design
1

Currently, while lifetimes and types can be abstracted over, there is no way to abstract over traits. The closest options are building type 'doubles' for traits, or using dyn Trait to represent Trait. The former is rather silly and a lot of boilerplate. The latter doesn't currently work for non-object safe traits, and is also rather silly.

// Example of type 'doubles'/'proxies'
struct DebugRep;
struct IteratorRep<Item>;
trait MyTrait<Arg> {
	type AssociatedType;
	const ConstValue: u8;
}
struct MyTraitRep<Arg,AssociatedType,const ConstValue: u8>;

Unfortunately, these are linked only by convention. There is no way (without duplicating the trait hierarchy manually) to relate OrdRep and EqRep. The compiler has no idea of any meaning for any of these, so options like below can't work either.

While it rarely comes up, the ability to abstract over traits does have value. For example, it would be unsound for ! to impl everything that can be soundly implemented by an uninhabited type, because then it would have to impl both Iterator<Item=u8> and Iterator<Item=u16> which would imply that u8 and u16 are the same type, which would be very bad, even though an uninhabited type can easily impl its choice of such things.

A nice solution to this, which I brought up at `todo!()` should prevent "unused_variables" warning - #31 by soundlogic2236, would be something like this:

enum NeverForTrait<trait T> {}
impl<Item> Iterator for NeverForTrait<Iterator<Item=Item>> {
	type Item = Item;
	...
}

In fact, even better would be the ability to do the following:

impl<Item,trait T: Iterator<Item=Item>> Iterator for NeverForTrait<T> {
	type Item = Item;
	...
}

Where trait T: Iterator<Item=Item> means for any trait T such that implementing it implies implementing Iterator<Item=Item>.

This could then be used in things like defaulting to deal with cases like

fn some_iterator(arg: SomeArg) -> impl Iterator<Item=Widgets> {
	todo!()
}

This also gives nice meanings to various current facts about traits. If we allow 'metatraits' (traits which apply to traits, rather than types, similar to how we probably also want traits applied to const values [though that should be a separate post]), we can get neat things like the following:

metatrait DynSafe where
  dyn Self:Self {}
impl<trait T> DynSafe for T where dyn T : T {}

and

metatrait NeverSafe where
  NeverForTrait<Self>:Self {}
impl<trait T> NeverSafe for T where NeverForTrait<T> : T {}

While fancy type level programming would potentially love these, the metatrait requirement can be gotten around using what I call the trait to constraint trick, where we just always use () as the type and do everything real in type parameters and such.

Moving back on to more obviously practical matters though, a classic problem is the From<!>. A bit of compiler magic like the following could enable it:

[#lang = "..."]
trait Union<trait A, trait B> {}
//Union is a marker trait satisfied when `A` and/or `B` is satisfied
[#lang = "..."]
unsafe trait<T:?Sized> Reflexivity : ?Sized {}
//impl Reflexivity<A> for B only when A and B are the same type, and this is enforced for coherence. It may actually be possible to very awkwardly do this without compiler magic using associated types, but it is ugly and I'm not actually sure if coherence checking works with it.
impl<A, B: Union<Reflexivity<!>,Reflexivity<A>> From<B> for A {
    fn from(t: B) -> A {
	//SAFETY: Either A and B are the same type, and hence can be safely transmuted, or B is ! and hence this code is unreachable. Or both.
        unsafe { std::mem::transmute_copy::<B,A>(&t) }
    }
}

In fact, using similar tricks to what I used in Postmonomorphism Asserts and Bound Hiding - #2 by SkiFire13, we can make Union far more interesting:

trait CallbackWithConstraint<T: Sized, trait Trait> {
	type Output;
	fn go(self) -> Output where T: Trait;
}
trait Union<trait A, trait B> {
	//If Self:A and not Self:B, equivalent to onA.go()
	//If not Self:A and Self:B, equivalent to onB.go()
	//If Self:A and Self:B, selects one of onA.go() and onB.go() to be equivalent to. Which is selected is not guaranteed
	//If not Self:A and not Self:B, never behavior (as in the compiler must make sure this never happens, by not having this trait itself be satisfied)
	fn callback<Output>(onA : impl CallbackWithConstraint<Self,A,Output=Output>, onB : CallbackWithConstraint<Self,B,Output=Output>) -> Output {...}
}

Now in purely safe code we can fully use Union (though the ergonomics of manual closure creation via CallbackWithConstraint is less than stellar).

Now, there is one additional big question about this compared to ConstraintKind in haskell. Here trait T has T effectively of kind Type -> Constraint, rather than Constraint. This can be somewhat awkward. One can work around it by doing somewhat silly things like hanging all your other Constraint needs on (), or passing around the relevant type and the trait separately like in the last example, but that last CallbackWithConstraint would probably be cleaner as

trait CallbackWithConstraint<constraint C> {
	type Output;
	fn go(self) -> Output where C;
}
4 Likes