Looking for RFC coauthors on "named impls"

language design
4

Very interesting! A few months ago I came up with basically the same idea on Reddit. Luckily I found this thread.

Rambling about motivation

I really like this general idea because it is very similar to how we treat name conflicts. As I said on Reddit:

[...] That would shift the problem of "no overlapping impls in the whole world" to "no overlapping impls in scope". Which is actually exactly what we do with names: same names are allowed to co-exist in the world as long as they are not in scope at the same time.

And having similar rules for different parts of the language always helps with learning and makes the language feel more consistent IMO.

Additionally, I think a solution is really needed. Today, we need to force crates to be coupled although they shouldn't need to know about one another. One typical example is chrono (time and date types) and diesel (database abstraction). diesel has traits like ToSql and FromSql that need to be implemented to store/load something from the database. So who is responsible for implementing diesel::ToSql for chrono::Date? Neither of those crates! But due to orphan rules, there doesn't exist a good solution. So right now, diesel has a chrono feature and implements all traits for chrono types if the feature is activated.

This coupling already lead to a couple of breakages across the webdev eco system. Also: what if a new chrono alternative comes along?

Having a named, importable impl in a third crate would solve this problem nicely.

Rambling about problems

Anyway, apparently many people already came up with that idea:

One main problem that is always brought up is basically the hashmap problem (as @withoutboats also brought up here): a hash map has to be able to assume that the Hash implementation for its key is always the same. At least it always has to be the same within one instance of a hash map. It would be fine to have two hash map instances where each instance uses a different hashing algorithm.

A possible solution that is often proposed is to store not only the type (of the key) but also its Hash impl in the hashmap type. So the compiler internal type wouldn't be HashMap<usize, String> but HashMap<<usize as Hash with $this_specific_hash_impl>, String>. That would make it possible to always use the same impl, regardless of what other impls are imported into scope later.

Sadly, this becomes complicated when the bound is not present at instance creation. For example:

let mut v = vec![0u32, 1, 2, 0]; // no bounds on `T` when creating a `Vec`

{
     use SomePartialEqImplForU32;
     v.dedup();
}
{
     use AnotherPartialEqImplForU32;
     v.dedup();
}

The Vec::dedup() method is in an impl<T: PartialEq> Vec<T> block. We don't know about this bound at object creation.

To solve this (always use the same impl of all traits for all generic types), one could:

  • Store a list of all trait impls of T that are in scope at creation time in the Vec type
  • Store the point of creation in the Vec type and lookup each trait impl lazily.

However, this doesn't sound too great.

Unfortunately, there are more problems. Consider the following function:

fn foo(v: &mut Vec<u32>) {
    v.dedup();
}

This function is not generic, so we would expect it to be compiled exactly once and result in only one version. But if we store more information about the impls in the type of a HashMap or Vec, functions like foo() would basically be generic.

Furthermore, this is spooky action at a distance: only looking at the foo definition, we might think we know exactly what's going on in the function. But that might not be the case, because we pass hidden "behavior" into the function. That's probably not a good idea.

So maybe it's not a good idea to store any information about specific impls in the type? Maybe that should always be resolved at call site?

I think my point is: given my text above and what @withoutboats said about unsafe code being able to assume coherence, I'm pretty sure that the only way to make named impls sound, backwards-compatible and not dangerous is by annotating the trait itself. In other words: the trait has to allow named impls. And by allowing named impls, the programmer is restricted in certain ways of using the trait.

I'd love to see development in this area as I honestly think Rust is too restrictive and thus lacking in this regard. However, while reading the other threads and writing this (too long, sorry!) post, I noticed that there are in fact quite a few problems. But I hope someone is willing to dive into this to find a solution.

As for being coauthor: I don't think I know remotely enough about type theory, the compiler internals or other languages like Haskell for this. And available time is also a problem. But I'll certainly keep an eye on this discussion :slight_smile:

1 Like