Proposal: Trait Derivation

[ANoobyBird]

Short story: rust should enable a specific flavor of supertrait-subtrait relationship, that is, when a trait B is implemented, trait A would also be derived as a supertrait.

A bit longer story: sometimes, it is only reasonable for certain methods of a supertrait A to be related to that of a subtrait B in certain ways. For a plausible example,

pub mod Graph {
    pub trait Graph {
        type Node; 
        fn adj(&self, node: Self::Node) -> Vec<Box<Self::Node>>; 
    }
}

pub mod tree { 
    // import Graph 

    pub trait Tree { 
        fn parent(&self) -> Option<Box<Self>>; 
        fn children(&self) -> Vec<Box<Self>>;
    } 

    // Now, it would be somewhat natural to do the following: 
    // imaginary syntax 
    derive Graph for Tree { 
        type Node = Self; 
        fn adj(&self, node: Self::Node) -> Vec<Box<Self::Node>> { 
            let mut result: Vec<Box<Self::Node>> = node.children(); 
            match node.parent() {
                Some(p) -> { result.push(p); }
                None -> {}
            }
            result
        } 
    } 
} 

Note that a blanket implementation is not what I'm suggesting, as it has necessary restrictions imposed by the orphan rule.

The reason for this, in a narrower sense, is that it is often perfectly natural to want to automatically derive some traits from one without manual implementation for each concrete type; and perhaps in a general and broader sense, is to extend the variety of the relationships between traits that is so far limited to plain supertrait-subtrait by injecting some dependence of the supertrait on the subtrait, while usually the dependence is that of the subtrait on the supertrait.

And btw I am a newbie in rust and a very inexperienced programmer, and I am open to any suggestions or corrections.

[Lythenas]

Couldn't you simply use impl<T> Graph for T where T: Tree?

E.g. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=98ac3a4912d67e4666280fe0022dd2bc

[SkiFire13]

Note that a blanket implementation is not what I'm suggesting, as it has necessary restrictions imposed by the orphan rule.

The orphan rule is there to prevent conflicting implementations, how does your proposal handle that? Consider for example:

// crate a
trait A {}
struct S;

// crate b, depends on a
trait B {}
derive a::A for B {}
impl B for a::S {}

// crate c, depends on a
trait C {}
derive a::A for C {}
impl C for a::S {}

// crate d, depends on b and c
// error: conflicting implementation of a::A for a::S

You need to add some restriction to avoid situations like this, though they don't necessarily have to be the same as the orphan rule. For example I can see this working with multiple derives for the same trait if the two traits where both local to the current crate.

In general I think there could an alternative to the orphan rule for blanket impls where the responsability of not creating overlapping implementations falls on the implementer of the trait bounding the blanket impl (e.g. the A in impl<T: A> B for T), though this means further limitations on the crate that defines that trait because now it should be considered as if it were foreign.

[ANoobyBird]

Couldn't you simply use impl<T> Graph for T where T: Tree?

E.g. https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=98ac3a4912d67e4666280fe0022dd2bc

Hi, @Lynthenas! Thank you for commenting!

I've attempted to make it work, however, it turned out that this works no longer in situations like the following:

pub mod graph { ... } 

pub mod tree { 
    pub trait Tree { ... } 

    // Implement Graph inside mod tree 
    impl<T> Graph for T where T: Tree { ... }
}

pub mod whatever { 
    pub trait Whatever { ... } 

    // Implement Graph inside mod whatever 
    impl<T> Graph for T where T: Whatever { ... }
}

Conflicting implementations would be reported, though the constraint T: Whatever is laid. The compiler seems to understand the T from T: Tree in the same way as that from T: Whatever as "all types". Note that the trait Graph, trait Tree and trait Whatever are in three different modules, and the implementations are held alongside the trait definitions respectively.

[ANoobyBird]

Note that a blanket implementation is not what I'm suggesting, as it has necessary restrictions imposed by the orphan rule.

The orphan rule is there to prevent conflicting implementations, how does your proposal handle that? Consider for example:

// crate a
trait A {}
struct S;

// crate b, depends on a
trait B {}
derive a::A for B {}
impl B for a::S {}

// crate c, depends on a
trait C {}
derive a::A for C {}
impl C for a::S {}

// crate d, depends on b and c
// error: conflicting implementation of a::A for a::S

You need to add some restriction to avoid situations like this, though they don't necessarily have to be the same as the orphan rule. For example I can see this working with multiple derives for the same trait if the two traits where both local to the current crate.

In general I think there could an alternative to the orphan rule for blanket impls where the responsability of not creating overlapping implementations falls on the implementer of the trait bounding the blanket impl (e.g. the A in impl<T: A> B for T), though this means further limitations on the crate that defines that trait because now it should be considered as if it were foreign.

Hi, @SkiFire13! Thank you for commenting!

It is indeed a problem which I haven't considered yet, thank you for your perspective! After reading the example you've made and thinking roughly for a little bit, so far I think that there might be two ways around the problem presented.

Solution 1, forbidding the implementation of C for S deriving A should there already be a B implemented which also derives A.

// crate a
trait A {}
struct S;

// crate b, depends on a
trait B {}
derive a::A for B {}
impl B for a::S {}

// crate c, depends on a
trait C {}
derive a::A for C {}
impl C for a::S {}  // Here, the compiler would throw an error.

Solution 2, make it so that a derivation towards A must be made explicit upon implementing a trait B which might derive A.

// crate a
trait A {}
struct S;

// crate b, depends on a
trait B {}
derive a::A for B {}

// Somehow tell the compiler explicitly that 
// we want B to derive A for S. Let's call this "derive A via B" for now.
#[derive(A)]
impl B for a::S {}

// crate c, depends on a
trait C {}
derive a::A for C {}
// This would still work, but the compiler will not automatically derive A.
// In fact, in this case, since there is already a derivation towards A via B, 
// another explicit declaration for a derivation via C would result in conflict.
impl C for a::S {} 

Essentially, two possible routes to A must be avoided, so any solution would have to pick just one "canonical" or "favored" path along a tree of derivations, for any given struct S. These are just two rough solutions I came up now, which are probably far from reasonable and natural. I'll post new solutions here should they ever occur to me.

[ANoobyBird]

And of course, a derivation of A via B is unique or nonexistent, or else there would definitely be conflicts. Additionally, it might be convenient that the derivations via a trait B should be hosted alongside B, in which case both the developer and the compiler would know exactly where to look for them.

And also, I cannot really claim to have grasped fully the orphan rule or actually any concept from rust, if there's anything I've misunderstood or missed, please point out as you may. And yes, there is always the possibility that the idea of derivation proposed here could eventually turn out to be just a special form of implementation. At the moment though, I would still consider the idea to be meaningful.

[SkiFire13]

Solution 1, forbidding the implementation of C for S deriving A should there already be a B implemented which also derives A.

This doesn't work because crate c doesn't know about crate b. The problem will manifest only when compiling a crate that uses both of them, and this is what needs to be prevented.

Solution 2, make it so that a derivation towards A must be made explicit upon implementing a trait B which might derive A.

What if crate c also used the #[derive(A)]? What implementation should be picked?

[ANoobyBird]

Solution 2, make it so that a derivation towards A must be made explicit upon implementing a trait B which might derive A.

What if crate c also used the #[derive(A)]? What implementation should be picked?

The compiler would throw an error in this case. In general, given any trait derivable A, a struct may only use one of its derivations. It is the responsibility of the implementer to keep the uniqueness of the derivations, and the compiler's to report should there be in any case more than one route of derivation towards any trait.

I should probably have specified the above when solution 2 is first written. But again, solution 2 itself may be extremely flawed.

Let's formalize the idea of derivation, say, consider traits as nodes in a tree, let's call it for now the Derivability Tree, and trait B is a child of A if A is derivable from B, then any struct S may derive A only via a path through a particular leaf trait, even though it may also implement other traits in the tree. For example, if B = T1, T2, .., Tn = A were such a path, then the following is a directed path in the Derivability Tree of A,

Tn -> ... -> T1 (A = Tn is the root)

And, we may write something like

#[derive(T1, T2, ..., Tn)] 
impl T1 for S { ... } 

Which would also conflict with any other such a derivation. This would also make the struct S the root of yet another tree, let's call it, um, the Derivation Tree of S, such that S the struct is the root, and its children are traits it implements, whose children are in turn traits that derives ultimately from S. And this would make the following a directed path in the Derivation Tree of S:

S -> T1 -> ... -> Tn (S is the root)

The stipulation that the Derivation Tree of a struct is actually a tree guarantees that there are no more than one path deriving to the same trait. And actually the compiler should check that both the Derivability Trees of all traits, respectively, and the Derivation Trees of all structs, respectively, are indeed all trees as they are defined in the above manner.

Hopefully that this is a constructive point and also that my expressions are clear and concise.

[ANoobyBird]

To be more specific, proceeding from the definition of Derivability Tree and Derivation Tree as laid above, an example where the compiler would throw an error would be, if A is any trait, and S is any struct, and that both A -> B -> C and A -> D are paths in the Derivability Tree of A, then

#[derive(C, B, D, A)] would result in an error.

Note that, however,

#[derive(C, B, D)] would not, at least judging from the given information, since the derivation of A is not made explicit, so A is not even derived for S, and so there are no paths attempting to cross each other.

This is all just speaking hypothetically.

[SkiFire13]

And actually the compiler should check that both the Derivability Trees of all traits, respectively, and the Derivation Trees of all structs, respectively, are indeed all trees as they are defined in the above manner.

Then we're back at the starting point because you can't check that when multiple crates are involved.

To be clear, the requirement is that if crate b and crate c each compile in isolation then they must not result in an overlapping implementation (and thus a compile error) when a third crate depends on both of them.

Note that this must result in the solution 2's example not compiling because there's no way to check that no other crate will derive A for S while compiling crate b.

[ANoobyBird]

To be clear, the requirement is that if crate b and crate c each compile in isolation then they must not result in an overlapping implementation (and thus a compile error) when a third crate depends on both of them.

Now that I see your point at the crate level where the compiler would not be able to sketch the trees, there seems to be no way around this indeed.

Thank you, I've learned a lot from this.

[ANoobyBird]

Then we're back at the starting point because you can't check that when multiple crates are involved.

But could there be a way to ensure that derivations remain internal to the crate where we define them, by adding layers of privacy to derivations alone (in effect I would imagine it to be like how traits and structs are when remain unexposed in a module, except that privacy inside the crate would be forced for derivations.) without damaging their usability inside the crate and also without infecting the publicity of the involved traits and structs? (Though the restriction imposed by this might more or less also limit the usefulness of derivations, since they would only be internal to crates.)

Again, this is just speaking hypothetically, and I haven't yet come up with a specific thing yet XD.

[SkiFire13]

This feels orthogonal to derivations though, you're pretty much proposing scoped trait implementations. It seems rust had them a long time ago (before the first stable release) but they were removed due to coherence problems. See for example https://mail.mozilla.org/pipermail/rust-dev/2011-December/001036.html

[ANoobyBird]

I think this coherence problem may be better represented by a more mathematical example, where we suppose that there is a trait for Groups, and the type isize forms a group in respect to either addition or multiplication.

pub trait Group { 
    type El; 
    fn prod(a: Self::El, b::Self::El) -> Self::El; 
}

// Additive group of the integers
impl Group for isize { 
    type El = Self; 
    fn prod(a: Self::El, b: Self::El) -> Self::El { a + b }
}

// Multiplicative group of the integers 
impl Group for isize { 
    type El = Self; 
    fn prod(a: Self::El, b: Self::El) -> Self::El { a * b }
}

Ifthe two impls above could somehow coexist in harmony, we would have solved the coherence problem. Now, a drastic solution might be to simply give the two impls different names -- we allow impls to have their own identifiers.

pub trait Group { 
    type El; 
    fn prod(a: Self::El, b::Self::El) -> Self::El; 
}

// Additive group of the integers
// Label this impl as AddGr
AddGr impl Group for isize { 
    type El = Self; 
    fn prod(a: Self::El, b: Self::El) -> Self::El { a + b }
}

// Multiplicative group of the integers 
// Label this impl as MulGr
MulGr impl Group for isize { 
    type El = Self; 
    fn prod(a: Self::El, b: Self::El) -> Self::El { a * b }
}

This will no doubt pose difficulties in coming up with a simple-enough syntax for invocation of an implemented method, since this suggests that any invocation must also specify which implementation it is from. I could think of something very exhausting to type like

<1 as MulGr>.prod(2) // evaluates to 2 
<1 as AddGr>.prod(2) // evaluates to 3 

In the long run, it might be beneficial, since, if I may understand like this, an implementation could be thought of as a proof that a piece of data(a struct) satisfies certain properties(a trait), and who says that a proof is the proof?

And if an impl could be named, then there is no need for a separate concept of derivation, for named blanket implementations would have it covered without causing any more conflicts. (but of course it wouldn't be absurd IMO to consider adding the keyword "derive" since there is a relevant conceptual difference between "derive" and "impl" in that, a derivation expresses relations between traits, whereas an implementation that between a concrete type and a trait. And if impls can be named, so can derives.)

Practically speaking though, naming an impl with an identifier would also inevitably break existent rust projects, and I admit that it could also be, in a sense, somewhat clumsy. I'll have to carefully read and think more about the material you posted and this frustrating coherence problem -- and I might probably not be able to come up with anything useful.

[ANoobyBird]

To sum up the idea above, we could turn an implementation into an identifiable entity, eliminating the need for scoped impls, which may also apply to a derivation, if we are to consider it as a separate concept from an implementation.

Practically speaking though, naming an impl with an identifier would also inevitably break existent rust projects,

And it just came to me that it doesn't necessarily break existent codebases, since we can also allow impls to be unnamed just as they have been: that is, for each struct S and each trait T, there could be AT MOST ONE unnamed implementation declared by impl T for S, the implemented methods in the unnamed impl may also be invoked without specifying the name of the impl (after all it is unnamed), thus preventing invalidating existent code. Apart from the one unnamed impl, if one attempts to implement an alternative implementation or alternative implementations of T for S, one would have to name it by declaring name impl T for S.