I find the problem of ad hoc polymorphism so interesting. It’s clearly a desirable feature, but we’ve been trying for nearly fifty years and still don’t have a solution that everyone’s unambiguously happy with. Compare that to, like, lexical scoping or parametric polymorphism, which most languages just have by default at this point. They’re almost mathematical facts.
And you’d hope there’d be a way to do it. Parametric polymorphism feels underpowered if you can’t make any assumptions about the things you’re abstracting over. But it might be a Halting Problem-esque situation.
FWIW if a real, near-trade-off-free solution exists, I think it’ll require a bit of a Copernican revolution in how we approach things. I don’t have any real insight to offer there.
> Compare that to, like, lexical scoping or parametric polymorphism, which most languages just have by default at this point. They’re almost mathematical facts.
At one time it was thought that implementing lexical scoping for a lisp (with lambdas, etc) was not possible to do performantly and this is one of the reasons that lots of lisps had dynamic scoping. That said, scheme has lexical scoping and I think that predates GNU Emacs by a reasonable amount of time.
AFAIK, dynamic scoping is still the default because of compatibility: older extensions might rely on it. For any new extension, the author should turn it on from the get go.
Without a hierarchy, a class is just a group of functions that have a same first implicit argument called this.
But what if a file was a namespace? (i.e. a javascript/typescript module)
Then we can just create functions and they automatically belong to a group.
One or multiple constants and variables can contain the data.
But do we need a hierarchy let alone multi-inheritance/traits if we just know what function to call and what file to import it from? Isn't that the job of interfaces?
Isn't composition better than inheritance?
Sounds like Nim. Nim doesn't have objects but it has something it calls universal function call syntax/uniform call syntax which lets you prefix a function call with the first argument instead of putting it in the argument list. This makes it look like object oriented coding without having to put the structure definition in the same file as the methods that act on it. This means that new methods can be added without having to edit the source of the structure or inherit from it.
If I’m writing a hash map module that’s generic over what it accepts, and later someone else is going to want to use it with Foo keys, how am I able to write my hash map such that the hash function for Foos are in scope in my hash map module?
Files exist in a different universe of abstractions from language features. Heck a language should work in a universe where files don't exist at all.
A file is a stream of bytes that a process can get by giving the os a string (name) that has all sorts of encoding/decoding rules that rely on runtime state.
Sure, files are a detail. But, the concept of namespace doesn't need to be attached to a file, it can just be a convenient convention to attach a namespace to a file. In live environments like Smalltalk images, there are no files.
I think what /u/dominicrose is trying to get at was that OOP bundles together things which need not be and in doing so, one loses flexibility. OOP is Encapsulation(can also be done via namespaces/modules), Polymorphism(can be done by functions with a dispatch based on first argument) and Reuse/Extensibility(inheritance is a special case, there are many other ways to build a new class/data-type from older ones, composition being one).
Often, this is not recognized in discourse and we end up with a 'OOP vs FP' discussion [1] even though the issue is not im/mutability. In fact, the discussion in article of [1] is actually about what is being discussed in this article. Should one do polymorphism via named implementations like in ML or anonymous ones like in Haskell/Rust? Inheritance in standard OOP languages counts as named implementations as the subclass has a name. Named implementations require more annotation but also have certain advantages like more clarity in which implementation to use and don't expose type parameters to user of the library (which happens with typeclasses).
OK, but files are external to the system. Within the Smalltalk environment, everything is an object and files are required as the ambient OS works with files. You can say that some objects within the environment, containing program source are playing the same role as source files in usual programming. Even there, one can have a richer interface than text/binary files.
Yes, I do agree with you - live image programming has to be composable/comprehensible/reproducible, and crucial state shouldn't be in anonymous objects. (I've even thinking of replacing mutable objects with with pure functions modifying a a tree of data). Types is another direction and the work on Strongtalk has proved influential for popular VMs.
But, we dont need to go back from objects to files, except for the purpose of interacting with the OS. Richer structures actually help comprehensibility. For instance, revision control operating at a structural level. UNIX would have much nicer, if something like nushell had been adopted from the beginning, and the 'little pieces' used to build the system worked on structured data.
After 8 years of programming ~exclusively in Rust it’s easy for me to take this for granted by forgetting that linker errors even exist — until I am rudely reminded by occasional issues with C/C++ code that ends up in the dep tree.
This property is downstream of the orphan rules, and given the benefit I wouldn’t give them up.
Similar observation here. In a statically linked global problem it's the linkers job to enforce the theme of the old "Highlander" movie... there can be only one. So "global coherence" is not some problem brought about Rust or Traits, but it's a fact of life. And considering the author's own admittance of "Local Implicits" having a "Correctness problem", I don't see how it could even be considered as an alternative. I'll take correctness over convenience any day of the week and twice on Sunday.
For context, Haskell's story for orphan instances is currently as follows:
- orphan instances are allowed and emit a warning
- duplicate instances are not allowed
- overlapping instances where one is different from the other, are allowed
- incoherent instance use sites are not allowed (where 2+ instances match and neither is more specific than the other)
- but you can enable this by adding {-# INCOHERENT #-} to instances. You shouldn't do this though unless you really know why you need it (and perhaps even then there is a better way)
- a typical library sets all warnings as errors with -Wall, so you'll notice when you're adding orphans
- exceptions in specific files can be made by adding -fno-orphans to the file
- defining orphan instances in executables is not a problem as the only user of them will be the program itself
- this is what you do if you are writing a package which only provides instances: where both the data types and the type classes are implemented elsewhere and you have no other choice. These libraries should not be used in other libraries, but only in executables and tests
- a different instance can also be defined by wrapping the original type with a newtype (thus defining that new instance for this new type, thus not making an orphan)
- since newtypes have no runtime overhead, also, with DerivingVia, syntactic overhead is quite low. This is "the way" to override already defined instances.
IMO, all the above makes sense when you prefer correctness over flexibility. From the post, this appears to be Rust's choice as well.
The newtype pattern is a special case of type composition which is incredibly useful, has low complexity, and if done right almost no boilerplate overhead. It's much dumber and easier to reason about than type-acrobatics with generics, imo.
Do you mean `Generically`[1]? I've only ever vaguely seen its use - perhaps it can do something a `newtype` can't (or can, but with more boilerplate)? But don't have any first-hand experience currently to comment.
It kinda sucks in both! If you want to interact with your newtypes, you need to either unwrap it or reimplement each typeclass/trait. Haskell does make this a bit nicer with deriving strategies, and Rust with macros, but it's a lot of boilerplate. The article had this to say about the example:
> I’m sure it won’t take much to convince you; this is unsatisfying. It’s straightforward in our contrived example. In real world code, it is not always so straightforward to wrap a type. Even if it is, are we supposed to wrap every type for every trait implementation we might need? People love traits. That would be a stampede of new types.
> Wrapper types aren’t free either. a_crate has no idea A2 exists. We’ll have to unwrap our A2 back into an A anytime we want to pass it to code in a_crate. Now we have to maintain all this boilerplate just to add our innocent implementation.
> If you want to interact with your newtypes, you need to either unwrap it or reimplement each typeclass/trait
...or you could just e.g. implement Deref in Rust? In my experience that solves almost all use cases (with the edge case being when something wants to take ownership of the wrapped value, at which point I don't see the problem with unwrapping)
That gets us halfway there. It makes unwrapping easy, but you still need to remember to rewrap if you've implemented anything.
use std::ops::Deref;
trait Test {
fn test(&self);
}
#[derive(Debug)]
struct Wrap<T>(T);
impl<T> Test for Wrap<T> {
fn test(&self) {
()
}
}
impl<T> Deref for Wrap<T> {
type Target = T;
fn deref(&self) -> &Self::Target {
&self.0
}
}
fn main() {
let thing1 = Wrap(3_i32);
let thing2 = Wrap(5_i32);
let sum = *thing1 + *thing2;
thing1.test();
thing2.test();
sum.test(); // error[E0599]: no method named `test` found for type `i32` in the current scope
}
Also using newtypes to reimplement methods on the base type is frowned upon. I believe that this is why #[derive(Deref)] isn't included in the standard library. See below (emphasis mine):
> So, as a simple, first-order takeaway: if the wrapper is a trivial marker, then it can implement Deref. If the wrapper's entire purpose is to manage its inner type, without modifying the extant semantics of that type, it should implement Deref. If T behaves differently than Target when Target would compile with that usage, it shouldn't implement Deref.
There's a nod given to dependently-typed languages (where types live in the same namespace as values, so they can be passed-into and returned-from functions), but it's useful to note that in those languages this "local coherence" approach doesn't just "look like" lambda calculus, it is lambda calculus. For example, to insert a new element into a sorted list we might define a function like this:
insert: (t: Type) -> (o: Ord t) -> t -> List t -> List t
insert t o x xs = case xs of
Nil _ -> Cons t x (Nil t)
Cons _ y ys -> case lessThanOrEq t o x y of
True -> Cons t x xs
False -> Cons t y (insert t o x ys)
(Sure, we could also use a more specific type like 'SortedList t' or whatever; that's orthogonal to my point)
Notice that the first argument `t` is a `Type`, and the second argument `o` is an `Ord t` (where `Ord` must be a function which takes a type as argument and returns another type; presumably for a record of functions). It's literally just lambda calculus.
However, this obviously gets quite tedious; especially when there's so much repetition. For example, the third argument has type `t` and the fourth has type `List t`, so why do we need to pass around `t` itself as a separate argument; can't the computer work it out? Yes we can, and we usually do this with {braces} syntax, e.g.
insert: {t: Type} -> {o: Ord t} -> t -> List t -> List t
insert _ _ x xs = case xs of
Nil _ -> Cons x Nil
Cons _ y ys -> case lessThanOrEq x y of
True -> Cons x xs
False -> Cons y (insert x ys)
Here I've indicated that `t` and `o` can be worked out from the context; I've replaced their argument names with `_` and we're no longer passing them explicitly into the recursive call, or to `Cons`, `Nil` or `lessThanOrEq` (assuming that those functions/constructors have also marked their arguments as such).
This is why the feature is called "implicits", since it's leaving some arguments implicit, for the compiler to fill in using information that's in context. It works quite well for types themselves, but can get a bit iffy for values (as evidenced by this blog post; and I've seen all sorts of footguns in Scala, like defining some implicit String values and hoping the right ones get picked up in the right places...)
What an excellent write-up, and very entertaining at that.
I suspect that most devs will prefer the local maximum that traits are. Perhaps with a bit more help to ensure there's only ever one implementation of a given trait -- think of a trait registry. One might still allow multiple implementations, but with one single one chosen at final link-edit time or, if linking dynamically, at run time. To support something like that the registrations in the trait registry would have to be exacting as to each trait's semantics. A registry has its own cost: friction, and someone has to be a registrar, and registration might have a cost. But a registry has its advantages, and one could have namespaced traits, too, to enable multiple registries/registrars. Registries might feel like a hack, but so what, compared to the problems with implicits, they might be worthwhile.
Any trait implementations where the type and trait are not local are:
* Private, and cannot be exported from a crate
* The local trait implementation always overrides any external implementation
That would solve part of the problem right? Only crate libraries that want to offer trait implementations for external traits/types are not possible, but that might be a good thing.
The solution proposed by the author with implicits is quite complex, I can see why it wasn't chosen.
The problem is that, when you're implementing a foreign trait for a foreign type, you usually want that impl to then be visible to a foreign crate. Not just the local crate.
If it were good enough to only have that impl be visible to the local crate, then you could side step this whole problem by defining a local trait, which you can then impl for any type you like.
So maybe we relax the rules a bit such that only the local crate, and crates that it calls, can see the impl. But then what if a third, unrelated crate, depends on that same foreign crate your local crate depends on? We'd need to keep some sort of stack tracking which impls are visible at any given time to make sure that such foreign crate can only see our impl when that foreign crate is used from our local crate. Hmmm... this is starting to look a lot like dynamic scoping.
How about explicitly declaring orphan trait implementations as public (or not) and explicitly importing them (or not). Trait implementations are resolved at the point where a concrete type becomes generic, and the set of available traits can depend on that context.
This isn't exactly trivial, but it avoids coherence problems.
Crate A implements Hash(vA) for T
Crate B implements Hash(vB) for T
Crate C has a global HashSet<T>
Crates A and B can both put their T instance in the C::HashSet. They can do it in their private code. Their Hash overrides any external implementation. The trait is used, but not exported.
C::HashSet now has an inconsistent state. Boom!
Implementations are not exported or public at all: they are used in functions and those functions are exported. For correctness, you want those implementations to be resolved consistently (this is what coherence is). This post gives the example of unioning two sets: you need to know that they're ordered the same way for your algorithm to work.
So the problem isn't that the implementation is public, it's that its used somewhere by a function which is public (or called, transitively, by a public function). For a library, code which is not being used by a public function is dead code, so any impl that is actually used is inherently public.
You might say, okay, well can binaries define orphan impls? The problem here is that we like backward compatibility: when a new impl is added to your dependency, possibly in a point release, it could conflict with your orphan and break you. You could allow users, probably with some ceremony, to opt into orphan impls in binaries, with the caveat that they are accepting that updating any of their dependencies could cause a compilation failure. But that's it: if you allow this in libraries, downstream users could start seeing unsolvable, unpredictable compilation failures as point releases of their dependencies introduce conflicts with orphan impls in other dependencies.
It would still be consistent; everything with my crate resolves `impl Foo for Bar` to what I define, everything with other crate resolves `impl Foo for Bar` to what they defined, and any other crate would have a compilation error because those crates didn't `impl Foo for Bar`.
If I for some reason exported a method like `fn call_bar(foo: Foo) -> Bar` then I think it would use my `impl Foo for Bar` since the source code for the trait impl was within my crate. What happens if instead I export like `fn call_bar<F: Bar>(foo: F) -> Bar)` is probably a bit more up to debate as to whose trait impl should be used; probably whichever crate where F being Foo is originally known.
I think they did say binaries can define ophan impls; and the only way somebody should be able to break your code is by changing the trait definition or deleting the implementing type. Otherwise your implementation would override the changed implementation. This seems fine because even if I locally define `Foo` which lets me to `Foo impl Bar`; if you then delete Bar then my code breaks anyways.
Of course it can change, that's what removal of coherence does.
It seems to me to be a logical impossibility to allow orphan implementations, and allow crate updates, and not have trait implementations changing at the same time. It's a pick-two situation.
Your conclusion is correct. I'm very happy with the two that Rust picked and tired of people pretending that there will be a magical pick three option if we just keep talking about it.
I also think Rust has picked the right default, but I wouldn't mind having an opt in to the other pair of trade-offs. There are traits like `ToSql` that would be mostly harmless. Serde has tricks for customizing `Serialize` on foreign types, and this could be smoother with language support. Not every trait is equivalent to Hash.
Consider Java for example. In Java, interfaces are even more restrictive than traits: only the package which defines the class can implement them for that class, not even the package which defines the interface. But this is fine, because if you want to implement an interface for a foreign class, you create a new class which inherits from it, and it can be used like an instance of the foreign class except it also implements this interface.
In Rust, to the extent this is possible with the new type pattern it’s a lot of cruft. Making this more ergonomic would ease the burden of the orphan rule without giving up on the benefits the orphan rule provides.
I think Rust assumes that trait implementations are the same across the whole program. This avoids problems e.g. with inlining code or passing data structures between crates. I don't believe this is absolutely necessary though.
The problem seems to be that people want this to be implicit. If you have to call an explicit function to turn an instance of type A into an instance of BTrait anyone can define such a function anywhere.
That's not exactly what's done for functions. Scoping rules are always more complex than that.
But the good news is that the same rules are good for implicits too. You look back your tree to find a definition, and if it's defined only once on the most internal level, use that definition, otherwise require an explicit annotation. Add some way to annotate over the entire scope, and some way to export implicits globally for completeness.
This will lead to all kinds of problems with implicit imports that every other kind of named object has too. That's not a big deal, developers are used to those.
This post is written by a fan of implicits, so it frames it as "better" than traits, though at the end it admits it is in fact a complex trade off, which is the truth. In my opinion, the trade off favors traits, but others may feel differently.
The core difference between traits (also called type classes) and ML modules is that with traits the instance/implementation has no name, whereas for ML modules they do. The analogy here is between Rust/Haskell's traits/typeclasses and ML's signatures and between Rust/Haskell's impls/instances and ML's structures. In Rust/Haskell, implementations are looked up by a tuple of types and a trait to determine the implementation. The advantage of this is that you don't need to name the impl and then invoke that name every time you use it; since we usually don't think of "Hash for i32" as something which has a meaningful name beyond the relationship between Hash and i32, this is quite nice.
But coherence requires that instances resolve consistently: if I hash an integer in one code location to insert into a map and then hash it again in a different location to do a lookup on the same map, I need to hash integers the same way each time. If you care about coherence, and the correctness property it implies, you can't allow overlapping impls if impls aren't named, because otherwise you aren't guaranteed a consistent result every time you look up the impl.
This introduces another problem: you can't see all the impls in the universe at once. Two libraries could add impls for types/traits in their upstream dependencies, and the incoherence won't be discovered until they are compiled together later on. This problem, called "orphan impls," causes its own controversy: do you just let downstream users discover the error eventually, when they try to combine the two libraries, or do you prohibit all orphan impls early on? Rust and Haskell have chosen different horns of this dilemma, and the grass is always greener.
Of course with implicits, this author intends a different solution to the problem of resolving instances without naming them: just allow incoherence (which they re-brand as "local coherence"). Instead, incoherence impls are allowed and are selected in a manner based on proximity to code location.
As the post eventually admits, this does nothing to solve the correctness problem that coherence is meant to solve, because code with different nearest impls can be compiled together, and in Rust such a correctness problem could become a memory safety problem, and how you figure out if the impl you've found for this type is actually the nearest impl to your code is left as an exercise to your reader. But sure, since you've rebranded incoherence to "local coherence" you can do some juxtaposed wordplay to call coherence a "local maxima" because achieving it has the downside that you can't have arbitrary orphan impls.
I read through this, and thought to myself: "wow, what a response that elucidates the PL design tradeoff space while giving real world examples of languages that occupy various points on that space; all as concisely and economically as possible."
And then I read the user name. Of course it's boats!!
Thank you for all your work! I want to say that especially since I've noticed a lot of shallow dismissal of your work recently (shallow because the dismissal often doesn't engage with the tradeoffs of whatever alternative solution it proposes in the context of Rust, among other things), and would like you to know there's a lot of us who are very very grateful for all the productivity and empowerment you've enabled through your contribution to Rust.
Let's assume for the sake of argument that the standard library didn't implement Hash for i32.
You could then have two crates, A and B, with different implementations of Hash for i32, and both could instantiate HashMap<i32>.
This can be made to work if we recognize the HashMap<i32> in crate A as a different type than the HashMap<i32> in crate B.
This only really works if orphan implementations are exported and imported explicitly to resolve the conflict that arises from a crate C that depends on A and B.
If C wants to handle HashMap<i32>, it needs to decide whether to import the orphan implementation of Hash for i32 from crate A or B (or to define its own). Depending on the decision, values of type HashMap<i32> can move between these crates or not.
Basically, the "proximity to code location" is made explicit in a way the programmer can control.
This makes type checking more complex, so it's not clear whether the price is worth it, but it does allow orphan implementations without creating coherence problems.
Implementations are not imported at all because they are not named. Like I wrote, named implementations (ala ML modules) is a valid alternative, but one with a much greater annotation burden.
You could imagine having named impls that are allowed to be incoherent as an additional feature on top of coherent unnamed impls, but to use them you would need to make any code that depends on their behavior parameterized by the impl as well as the types. In fact, you can pretty trivially emulate that behavior in Rust today by adding a dummy type parameter to your type and traits.
Right, but what I'm describing is a tradeoff point that's between the extremes, where implementations are unnamed but can still be explicitly imported.
Making my example more explicit, you'd need syntax along the lines of
// inside crate C
use A::impl std::hash::Hash for i32;
This syntax would explicitly be limited to orphan implementations.
I suppose to further clarify, there's still some coherence requirement there in that crate C can't import the conflicting implementations from both A and B. Which could then perhaps be worked around by adding syntax to spell types along the lines of
HashMap<i32 + A::impl Hash, V>
Which you could argue is a form of naming implementations, I suppose? I'm not familiar with ML. You could maybe also think of it as a more ergonomic way of doing (more or less) those wrapper types.
In any case, the annotation burden only exists where it's actually needed to enable orphan implementations.
And either way, multiple different impls can safely coexist within the overall set of code that's linked together, with everything being statically checked at compile time.
I think rather than at odds with without.boats is saying, this is very much aligned with what they are suggesting. While not literally `use A::impl std::hash::Hash for i32` is for all intents and purposes naming the impl.
Similarly, `HashMap<i32 + A::impl Hash, V>` is what they are talking about when they refer to parameterizing code on the impl chosen.
Essentially, yes. What I don't see is their claim that it's a "much greater annotation burden". Compared to what? Rust today just doesn't allow this at all, and if you use a wrapper type to simulate it, you definitely end up with more "annotations" (boilerplate).
FWIW It's not at all clear to me how this requirement would be implemented in practice: "This syntax would explicitly be limited to orphan implementations."
Maybe I'm missing something, but the compiler can tell whether an implementation is an orphan. That's how you get an error message today if you try to write one. So I don't know what difficulty you have in mind.
Great write up, and you're absolutely right that implicits are moving towards ML modules. Quite possibly a production system would end up being synonymous with ML modules out of the need for named impls.
Small nit in terminology, the implicits described are coherent. Part of their value over previous implicit work is that they are coherent and stable. I have generally seen the property you're referring to called canonicity, which they do lack.
I'm pretty sure the article resolves the implicit dependencies at the point of the declaration. (Did I misunderstood it?)
So, you don't have a `data HashMap datatype`, you have a `data HashMap hashAlgo datatype`, where hashAlgo is decided implicitly by the context. That's the entire reason it's called "implicit".
Every other usage of the data knows how to hash your values because of that `hashAlgo` parameter. It doesn't matter where it happens.
I was building a memory manager for a database and I needed to know exactly how much space a deep data structure was using.
The servo project has the same problem and they built a library that contained a Sized trait (don't remember the name exactly) and then inplemented that trait for a bunch of stdlib and third party types and for all their types (easy to be done via a derive macro iirc).
I wanted to use that library but I also had other third party types that weren't covered by the library.
The quick solution I found was to basically copy the whole library into my project so that I could add my impls in the trait definition trait.
No. Good technical writing is about making the reader feel smart, not the writer. Using big words goes in the opposite direction. The real art is in explaining complex ideas in simple terms.
I think the idea is that the sentence introduces a contrived example, and so the author used roundabout words. Snake sentences sound sibilantly. It's a blog post.
The comment in your frobulate code suggests one is to forbulate, yet reading The code it is very clear that there will only be frobulation happening in the outlined proceedings. Perhaps a minor revision is required.
How often do you need to impl trait crate_a::A for a type crate_b::B? If it is allowed by the language, it would mean that behavior of crate_a or crate_b would change if they link one to another.
I really doubt that this is a wanted behavior. And Rust follows this logic, suggesting to use a new type to achieve the same, but not leak your impl into other crates.
This really amps up the composibility of a lot of systems and libraries. It would be awesome if there was a "free" way to do this. Unfortunately no one has found one yet; the posted article is a pretty good overview of that problem.
Also, bear in mind that no matter what solution you are looking at, it's generally crate_c that wants to create the implementation for crate_a's type using a trait in crate_b, so it isn't as bad as the "behavior of crate_a or crate_b would change if they link one to another", which would indeed be horrifying. crate_c has to be involved somehow in the build, without that crate_a and crate_b carry on completely normally. When it's the end-user application doing the trait, at least the end-user can manage it; the core problem arises when crate_c is third-party, and user wants to use that and also crate_d, which also implements a train from crate_b on crate_a's type. At that point you have a pretty big issue; I would characterize implicits as a way of managing the problem, but not really a "solution". It is not clear there is a "solution".
And there is clearly a problem; the Haskell community rammed into this problem decently hard a long time ago, back when they were smaller than they even are today, and certainly smaller back then than the Rust ecosystem as it stands today. The phase transition from theoretical problem to real problem happens in an ecosystem an order of magnitude or two smaller than the current Rust ecosystem, which is itself likely to grow yet by another order or two at least over its lifespan.
Love to see a problem from the frontline of computer science as an actual practical problem solution to which would greatly benefit languages' semantics.
Regarding conflicting impls in crate_c and crate_d: what is wrong with Haskell's approach of grading impls by their specialty (e.g. Show Int is more specific than Show a so prior instance would be used if matches) and only throwing an error if it's ambiguous to the compiler which instance to use?
I see that this is not sufficient, since crate_e can't do anything about conflicting impls in crate_c and crate_d. Having to explicitly import impls does not spark joy. The problem is more convoluted than I thought!
I'm very interested in this topic since I'm working on a language that features traits and thus have a chance to "fix" it.
"Regarding conflicting impls in crate_c and crate_d: what is wrong with Haskell's approach of grading impls by their specialty"
You can still get surprising errors later in crate_c and crate_d when crate_e adds something, which is suboptimal.
I'm not saying all solutions are equally good or bad, just that there isn't a known perfect solution yet. If you accept the principle that "Writing some more code into module E shouldn't cause new errors to appear in C and D", which is a reasonable thing to want in a system, then this isn't a perfect solution.
For example, if you want to serialize a type whose fields are all public but it doesn’t implement `serde::Serialize`. A lot of crates have an optional `serde` feature for this exact purpose, but not all.
Another use-case is if you want more abstraction than the standard library. There’s a crate named `cc-traits` that exports traits for collections like `Insert` and `Remove`, which are implemented for types on the standard library. But if you’re using a third-party collection library like `btree_vec`, its types don’t implement the `Insert` and `Remove` traits, and you could easily implement them manually except for the orphan rule.
I understand the orphan problem better now. It's not clear what compiler should do if you add two crates which have conflicting impls (where both implement the same foreign trait for the same foreign type)
The role of unification in type systems is interesting here, e.g. for the problem of incompatible set orderings we would like the type of `union` to be something like:
This allows any `O : Ord<T>` we like, as long as both `Set` values have the same one. However, it's not clear what "the same" would mean. A whole-program compiler could see whether both symbols unify (i.e. they point to the same thing); but separate compilation would require a system for referencing/naming each implementation, which would come with its own headaches (e.g. stability across versions, avoiding clashes, etc.). The article mentions an approach based on naming, which I assume is related. Maybe it's time to content-address our definitions like Unison does?
This. Traits and macros are two real problems with rust. Orphan rule is one, but also const, async and unnamable types (mostly closures). These barely work with traits or do not work at all. If rust did not have closures, it'd be a lot simpler to solve these. Is it so hard to just create a normal function instead of closure?
Perhaps we need to go back to the basics a bit? What is a trait?
1. A set of functions, associated types and generic types
2. A marker/tag (e.g. Send, Sync)
Orphan rules do not seem to be problem for marker traits. Library authors must be responsible for enforcing whether their types are Send/Sync, etc or not.
As for normal traits, it's too late for rust, but I'd just limit traits to being only sets of function definitions, e.g.
Then adding set operations (and, or, xor, not) for traits would be pretty easy, keeping most of power for defining generics.
More importantly traits could be just aliases and two traits with the same set of functions would be equal. This solves orphan problem - you would not need to import or export traits, it would be just normal resolution of functions. Do I call this function from crate A, or crate B? That's a solved problem.
The hard problem is not sharing the trait, but sharing the trait instance.
With your solution, if too modules define traits with identical type signatures but different implementations, it would be impossible for the compiler to decide which impl to use.
If there are two modules module_a and module_b, and each defines a function called foo, how does the compiler decide which foo should be used? It just checks whether you imported module_a::foo or module_b::foo.
Perhaps I should have been more clear. The point is you would not implement traits. You would just implement functions. You would not implemet traits, you would just write functions iter and len for your type.
When calling a function, compiler would check separately for existence of each function defined in the trait. That is a trait would be just like any other type alias so that you do not need to repeating complex function names everywhere:
Implicits are motivated, atleast in part, by a desire to improve upon this baseline. In the world of ML modules this is the current state. Typeclasses (as modules) have to be passed everywhere they're used explicitly and it's exhausting. I think with implicits you can keep that as a baseline but provide an implicit mechanism atop it to remove a lot of the obvious boilerplate for a win-win
The editorialized title is correct. The original article isn't saying that each trait is individually a local maximum. It's saying that the concept of Rust traits is one.
I'd propose just getting rid of the orphan rule and keeping global coherence. If a crate has multiple dependencies with the different implementations on the same trait/type, let that crate select or define one implementation that will override the others, even internally.
Then I'd trust library authors to write orphan implementations sparingly, making sure they're either "obvious" (there's no other reasonable implementation for the same trait/type) or their internals aren't relied on, just the fact that the trait/type has a reasonable implementation (like defining `Serialize` and `Deserialize` but only relying on both being inverses, so a dependent crate could override them with a different `Serialize` and `Deserialize` implementation and the library would still work).
I'd claim the libraries that define bad orphan instances must be poorly written, and you should only depend on well-written libraries. If you want to depend on libraries A and B which both rely on conflicting orphan implementations, don't bother trying to patch one of them, instead re-write the libraries in a better way to keep your codebase ideal.
...I still want that kind of system, but I expect it would fail catastrophically in the real world, where developers aren't perfect, important projects depend on badly-written npm packages, and Hyrum's law is pervasive.
---
So instead I propose something more reasonable. Keep global coherence and:
- Get rid of the orphan rule for applications. An application has no dependents, so the entire issue "two dependencies differently implement the same trait on the same type" doesn't apply.
- Next, create an opt-in category of libraries, "glue" libraries, which can only define orphan implementations (if they absolutely need a unique type, e.g. an associated type of a type/trait implementation, it can be put in another crate that is a third dependency of the glue library). Glue libraries can only be depended on by applications (not libraries, including other glue libraries). This allows orphan code reuse but still prevents the vast majority of code (the code in libraries) from depending on orphan implementations.
Library authors who really want to depend on orphan instances can still do ugly workarounds, like asking application developers to copy/paste the library's code, or putting all the library's functions in traits, then implementing all the traits in a separate "glue" library. But I suspect these workarounds won't be an issue in practice, because they require effort and ugly code, and I believe trying to avoid effort and ugly code is what would cause people to write bad orphan instances in the first place. Also note that library authors today have ugly workarounds: they can copy/paste the foreign trait or type into their library, and ask developers to "patch" other libraries that depend on the foreign crate to depend on their library (which can be done in `Cargo.toml` today). But nobody does that.
Ideally, a library that really needs an orphan implementation would use a better workaround: create a new trait, that has the foreign trait a supertrait, and methods that implement functionality of the foreign type, then use the new trait everywhere you would use the foreign type. I suspect this solves the global coherence problem, because an application could depend on the glue library that implements your library's trait on the foreign type, but it could alternatively depend on a different glue library that implements the trait on a wrapper, and if there's another library that requires a conflicting implementation of the foreign type, its trait would be implemented on a different wrapper.
It's because they've used the plural of "Trait" in an ungrammatical way, and so used the plural of "maxima". Traits aren't a local maxima - the trait design is a local maximum. Or traits are at a local maximum. The traits themselves aren't a maximum (or maxima (or maximae)).
based on the downvote this received i guess something is wrong with that sentence. but i am not an english native, and i can't tell what would be wrong with it. i am not bothered by the downvotes, if it is wrong then so be it, but i would like to know why it's wrong.
I find the problem of ad hoc polymorphism so interesting. It’s clearly a desirable feature, but we’ve been trying for nearly fifty years and still don’t have a solution that everyone’s unambiguously happy with. Compare that to, like, lexical scoping or parametric polymorphism, which most languages just have by default at this point. They’re almost mathematical facts.
And you’d hope there’d be a way to do it. Parametric polymorphism feels underpowered if you can’t make any assumptions about the things you’re abstracting over. But it might be a Halting Problem-esque situation.
FWIW if a real, near-trade-off-free solution exists, I think it’ll require a bit of a Copernican revolution in how we approach things. I don’t have any real insight to offer there.
> Compare that to, like, lexical scoping or parametric polymorphism, which most languages just have by default at this point. They’re almost mathematical facts.
FWIW emacs lisp (in)famously still defaults to dynamic scoping -- there's been a proposal to change that default earlier this month but interestingly, there's still pushback. See e.g. https://lists.gnu.org/archive/html/emacs-devel/2024-11/msg00...
At one time it was thought that implementing lexical scoping for a lisp (with lambdas, etc) was not possible to do performantly and this is one of the reasons that lots of lisps had dynamic scoping. That said, scheme has lexical scoping and I think that predates GNU Emacs by a reasonable amount of time.
AFAIK, dynamic scoping is still the default because of compatibility: older extensions might rely on it. For any new extension, the author should turn it on from the get go.
Without a hierarchy, a class is just a group of functions that have a same first implicit argument called this. But what if a file was a namespace? (i.e. a javascript/typescript module) Then we can just create functions and they automatically belong to a group. One or multiple constants and variables can contain the data.
But do we need a hierarchy let alone multi-inheritance/traits if we just know what function to call and what file to import it from? Isn't that the job of interfaces? Isn't composition better than inheritance?
Sounds like Nim. Nim doesn't have objects but it has something it calls universal function call syntax/uniform call syntax which lets you prefix a function call with the first argument instead of putting it in the argument list. This makes it look like object oriented coding without having to put the structure definition in the same file as the methods that act on it. This means that new methods can be added without having to edit the source of the structure or inherit from it.
If I’m writing a hash map module that’s generic over what it accepts, and later someone else is going to want to use it with Foo keys, how am I able to write my hash map such that the hash function for Foos are in scope in my hash map module?
With function overloading, templates and late static binding.
You just use a `hash` function in your library code and user has to implement a version of it that accepts the Foo type.
To resolve the scope problem, Nim uses templates[1] and a `mixin`[2] statement to bind user-defined hash procedure.
0 - https://github.com/nim-lang/Nim/lib/pure/collections/tables....
1 - https://github.com/nim-lang/Nim/blob/652edb229ae3ca736b19474...
2 - https://nim-lang.org/docs/manual.html#generics-mixin-stateme...
Files exist in a different universe of abstractions from language features. Heck a language should work in a universe where files don't exist at all.
A file is a stream of bytes that a process can get by giving the os a string (name) that has all sorts of encoding/decoding rules that rely on runtime state.
Sure, files are a detail. But, the concept of namespace doesn't need to be attached to a file, it can just be a convenient convention to attach a namespace to a file. In live environments like Smalltalk images, there are no files.
I think what /u/dominicrose is trying to get at was that OOP bundles together things which need not be and in doing so, one loses flexibility. OOP is Encapsulation(can also be done via namespaces/modules), Polymorphism(can be done by functions with a dispatch based on first argument) and Reuse/Extensibility(inheritance is a special case, there are many other ways to build a new class/data-type from older ones, composition being one).
Often, this is not recognized in discourse and we end up with a 'OOP vs FP' discussion [1] even though the issue is not im/mutability. In fact, the discussion in article of [1] is actually about what is being discussed in this article. Should one do polymorphism via named implementations like in ML or anonymous ones like in Haskell/Rust? Inheritance in standard OOP languages counts as named implementations as the subclass has a name. Named implementations require more annotation but also have certain advantages like more clarity in which implementation to use and don't expose type parameters to user of the library (which happens with typeclasses).
[1] https://news.ycombinator.com/item?id=41901577
> In live environments like Smalltalk images, there are no files.
Of course there are: image file, sources file, changes file.
And, of course, fileOuts to share code with others and to archive code -- so we can have a reproducible build process.
OK, but files are external to the system. Within the Smalltalk environment, everything is an object and files are required as the ambient OS works with files. You can say that some objects within the environment, containing program source are playing the same role as source files in usual programming. Even there, one can have a richer interface than text/binary files.
Long ago, Smalltalk's lack of explicit support for important aspects of programming was recognised:
"Programs consist of modules. Modules provide the units to divide the functional and organizational responsibility within a program."
"An Overview of Modular Smalltalk"
https://dl.acm.org/doi/pdf/10.1145/62083.62095
Yes, I do agree with you - live image programming has to be composable/comprehensible/reproducible, and crucial state shouldn't be in anonymous objects. (I've even thinking of replacing mutable objects with with pure functions modifying a a tree of data). Types is another direction and the work on Strongtalk has proved influential for popular VMs.
But, we dont need to go back from objects to files, except for the purpose of interacting with the OS. Richer structures actually help comprehensibility. For instance, revision control operating at a structural level. UNIX would have much nicer, if something like nushell had been adopted from the beginning, and the 'little pieces' used to build the system worked on structured data.
Rust just doesn’t really have linker errors.
After 8 years of programming ~exclusively in Rust it’s easy for me to take this for granted by forgetting that linker errors even exist — until I am rudely reminded by occasional issues with C/C++ code that ends up in the dep tree.
This property is downstream of the orphan rules, and given the benefit I wouldn’t give them up.
Similar observation here. In a statically linked global problem it's the linkers job to enforce the theme of the old "Highlander" movie... there can be only one. So "global coherence" is not some problem brought about Rust or Traits, but it's a fact of life. And considering the author's own admittance of "Local Implicits" having a "Correctness problem", I don't see how it could even be considered as an alternative. I'll take correctness over convenience any day of the week and twice on Sunday.
For context, Haskell's story for orphan instances is currently as follows:
- orphan instances are allowed and emit a warning
- duplicate instances are not allowed
- overlapping instances where one is different from the other, are allowed
- incoherent instance use sites are not allowed (where 2+ instances match and neither is more specific than the other)
- but you can enable this by adding {-# INCOHERENT #-} to instances. You shouldn't do this though unless you really know why you need it (and perhaps even then there is a better way)
- a typical library sets all warnings as errors with -Wall, so you'll notice when you're adding orphans
- exceptions in specific files can be made by adding -fno-orphans to the file
- defining orphan instances in executables is not a problem as the only user of them will be the program itself
- this is what you do if you are writing a package which only provides instances: where both the data types and the type classes are implemented elsewhere and you have no other choice. These libraries should not be used in other libraries, but only in executables and tests
- a different instance can also be defined by wrapping the original type with a newtype (thus defining that new instance for this new type, thus not making an orphan)
- since newtypes have no runtime overhead, also, with DerivingVia, syntactic overhead is quite low. This is "the way" to override already defined instances.
IMO, all the above makes sense when you prefer correctness over flexibility. From the post, this appears to be Rust's choice as well.
The newtype pattern is a special case of type composition which is incredibly useful, has low complexity, and if done right almost no boilerplate overhead. It's much dumber and easier to reason about than type-acrobatics with generics, imo.
Do you mean `Generically`[1]? I've only ever vaguely seen its use - perhaps it can do something a `newtype` can't (or can, but with more boilerplate)? But don't have any first-hand experience currently to comment.
[1] https://hackage.haskell.org/package/base/docs/GHC-Generics.h...
I meant in a general context (I know Go or Rust allows it in a decent way), not familiar enough with Haskell..
It's the same in Haskell as in Rust. Using the example from the article:
In Haskell that translates to: Unfortunately, I also share GP's confusion. Can you share an example of what you mean by "type acrobatics with generics"?If it's the same, what is the blog posts problem then?
It kinda sucks in both! If you want to interact with your newtypes, you need to either unwrap it or reimplement each typeclass/trait. Haskell does make this a bit nicer with deriving strategies, and Rust with macros, but it's a lot of boilerplate. The article had this to say about the example:
> I’m sure it won’t take much to convince you; this is unsatisfying. It’s straightforward in our contrived example. In real world code, it is not always so straightforward to wrap a type. Even if it is, are we supposed to wrap every type for every trait implementation we might need? People love traits. That would be a stampede of new types.
> Wrapper types aren’t free either. a_crate has no idea A2 exists. We’ll have to unwrap our A2 back into an A anytime we want to pass it to code in a_crate. Now we have to maintain all this boilerplate just to add our innocent implementation.
> If you want to interact with your newtypes, you need to either unwrap it or reimplement each typeclass/trait
...or you could just e.g. implement Deref in Rust? In my experience that solves almost all use cases (with the edge case being when something wants to take ownership of the wrapped value, at which point I don't see the problem with unwrapping)
That gets us halfway there. It makes unwrapping easy, but you still need to remember to rewrap if you've implemented anything.
Also using newtypes to reimplement methods on the base type is frowned upon. I believe that this is why #[derive(Deref)] isn't included in the standard library. See below (emphasis mine):> So, as a simple, first-order takeaway: if the wrapper is a trivial marker, then it can implement Deref. If the wrapper's entire purpose is to manage its inner type, without modifying the extant semantics of that type, it should implement Deref. If T behaves differently than Target when Target would compile with that usage, it shouldn't implement Deref.
https://users.rust-lang.org/t/should-you-implement-deref-for...
There's a nod given to dependently-typed languages (where types live in the same namespace as values, so they can be passed-into and returned-from functions), but it's useful to note that in those languages this "local coherence" approach doesn't just "look like" lambda calculus, it is lambda calculus. For example, to insert a new element into a sorted list we might define a function like this:
(Sure, we could also use a more specific type like 'SortedList t' or whatever; that's orthogonal to my point)Notice that the first argument `t` is a `Type`, and the second argument `o` is an `Ord t` (where `Ord` must be a function which takes a type as argument and returns another type; presumably for a record of functions). It's literally just lambda calculus.
However, this obviously gets quite tedious; especially when there's so much repetition. For example, the third argument has type `t` and the fourth has type `List t`, so why do we need to pass around `t` itself as a separate argument; can't the computer work it out? Yes we can, and we usually do this with {braces} syntax, e.g.
Here I've indicated that `t` and `o` can be worked out from the context; I've replaced their argument names with `_` and we're no longer passing them explicitly into the recursive call, or to `Cons`, `Nil` or `lessThanOrEq` (assuming that those functions/constructors have also marked their arguments as such).This is why the feature is called "implicits", since it's leaving some arguments implicit, for the compiler to fill in using information that's in context. It works quite well for types themselves, but can get a bit iffy for values (as evidenced by this blog post; and I've seen all sorts of footguns in Scala, like defining some implicit String values and hoping the right ones get picked up in the right places...)
What an excellent write-up, and very entertaining at that.
I suspect that most devs will prefer the local maximum that traits are. Perhaps with a bit more help to ensure there's only ever one implementation of a given trait -- think of a trait registry. One might still allow multiple implementations, but with one single one chosen at final link-edit time or, if linking dynamically, at run time. To support something like that the registrations in the trait registry would have to be exacting as to each trait's semantics. A registry has its own cost: friction, and someone has to be a registrar, and registration might have a cost. But a registry has its advantages, and one could have namespaced traits, too, to enable multiple registries/registrars. Registries might feel like a hack, but so what, compared to the problems with implicits, they might be worthwhile.
What is wrong with the following solution?
Any trait implementations where the type and trait are not local are:
* Private, and cannot be exported from a crate
* The local trait implementation always overrides any external implementation
That would solve part of the problem right? Only crate libraries that want to offer trait implementations for external traits/types are not possible, but that might be a good thing.
The solution proposed by the author with implicits is quite complex, I can see why it wasn't chosen.
The problem is that, when you're implementing a foreign trait for a foreign type, you usually want that impl to then be visible to a foreign crate. Not just the local crate.
If it were good enough to only have that impl be visible to the local crate, then you could side step this whole problem by defining a local trait, which you can then impl for any type you like.
So maybe we relax the rules a bit such that only the local crate, and crates that it calls, can see the impl. But then what if a third, unrelated crate, depends on that same foreign crate your local crate depends on? We'd need to keep some sort of stack tracking which impls are visible at any given time to make sure that such foreign crate can only see our impl when that foreign crate is used from our local crate. Hmmm... this is starting to look a lot like dynamic scoping.
How about explicitly declaring orphan trait implementations as public (or not) and explicitly importing them (or not). Trait implementations are resolved at the point where a concrete type becomes generic, and the set of available traits can depend on that context.
This isn't exactly trivial, but it avoids coherence problems.
This doesn't solve the hashtable problem:
Implementations are not exported or public at all: they are used in functions and those functions are exported. For correctness, you want those implementations to be resolved consistently (this is what coherence is). This post gives the example of unioning two sets: you need to know that they're ordered the same way for your algorithm to work.
So the problem isn't that the implementation is public, it's that its used somewhere by a function which is public (or called, transitively, by a public function). For a library, code which is not being used by a public function is dead code, so any impl that is actually used is inherently public.
You might say, okay, well can binaries define orphan impls? The problem here is that we like backward compatibility: when a new impl is added to your dependency, possibly in a point release, it could conflict with your orphan and break you. You could allow users, probably with some ceremony, to opt into orphan impls in binaries, with the caveat that they are accepting that updating any of their dependencies could cause a compilation failure. But that's it: if you allow this in libraries, downstream users could start seeing unsolvable, unpredictable compilation failures as point releases of their dependencies introduce conflicts with orphan impls in other dependencies.
It would still be consistent; everything with my crate resolves `impl Foo for Bar` to what I define, everything with other crate resolves `impl Foo for Bar` to what they defined, and any other crate would have a compilation error because those crates didn't `impl Foo for Bar`.
If I for some reason exported a method like `fn call_bar(foo: Foo) -> Bar` then I think it would use my `impl Foo for Bar` since the source code for the trait impl was within my crate. What happens if instead I export like `fn call_bar<F: Bar>(foo: F) -> Bar)` is probably a bit more up to debate as to whose trait impl should be used; probably whichever crate where F being Foo is originally known.
I think they did say binaries can define ophan impls; and the only way somebody should be able to break your code is by changing the trait definition or deleting the implementing type. Otherwise your implementation would override the changed implementation. This seems fine because even if I locally define `Foo` which lets me to `Foo impl Bar`; if you then delete Bar then my code breaks anyways.
How about downgrading duplicate implementation in the binary to a warning?
SQL has CREATE TABLE IF NOT EXISTS. Rust could have `impl Trait if not already implemented`.
This is a bad solution because now method resolution is suddenly unpredictable and can change out from under you based on changes to remote crates
Of course it can change, that's what removal of coherence does.
It seems to me to be a logical impossibility to allow orphan implementations, and allow crate updates, and not have trait implementations changing at the same time. It's a pick-two situation.
Your conclusion is correct. I'm very happy with the two that Rust picked and tired of people pretending that there will be a magical pick three option if we just keep talking about it.
I also think Rust has picked the right default, but I wouldn't mind having an opt in to the other pair of trade-offs. There are traits like `ToSql` that would be mostly harmless. Serde has tricks for customizing `Serialize` on foreign types, and this could be smoother with language support. Not every trait is equivalent to Hash.
The problem is people want to write glue code that adds foreign traits to types they don't own.
For example they need to implement diesel trait on a type from crate they don't own (e.g. matrix)
Is it possible to square that circle? Perhaps not through traits, but something else?
Better newtypes are the answer.
Consider Java for example. In Java, interfaces are even more restrictive than traits: only the package which defines the class can implement them for that class, not even the package which defines the interface. But this is fine, because if you want to implement an interface for a foreign class, you create a new class which inherits from it, and it can be used like an instance of the foreign class except it also implements this interface.
In Rust, to the extent this is possible with the new type pattern it’s a lot of cruft. Making this more ergonomic would ease the burden of the orphan rule without giving up on the benefits the orphan rule provides.
I think Rust assumes that trait implementations are the same across the whole program. This avoids problems e.g. with inlining code or passing data structures between crates. I don't believe this is absolutely necessary though.
It's been a while now, but I believe Ed Kmett covers some of this in his talk "Typeclasses vs The World"
https://m.youtube.com/watch?v=hIZxTQP1ifo
The problem seems to be that people want this to be implicit. If you have to call an explicit function to turn an instance of type A into an instance of BTrait anyone can define such a function anywhere.
Alternatively do what's done for functions in other languages (I don't use Rust) and use the most recently defined one.
That could lead to different results if you change include/import order but hey if you don't want that then just be explicit.
That's not exactly what's done for functions. Scoping rules are always more complex than that.
But the good news is that the same rules are good for implicits too. You look back your tree to find a definition, and if it's defined only once on the most internal level, use that definition, otherwise require an explicit annotation. Add some way to annotate over the entire scope, and some way to export implicits globally for completeness.
This will lead to all kinds of problems with implicit imports that every other kind of named object has too. That's not a big deal, developers are used to those.
This post is written by a fan of implicits, so it frames it as "better" than traits, though at the end it admits it is in fact a complex trade off, which is the truth. In my opinion, the trade off favors traits, but others may feel differently.
The core difference between traits (also called type classes) and ML modules is that with traits the instance/implementation has no name, whereas for ML modules they do. The analogy here is between Rust/Haskell's traits/typeclasses and ML's signatures and between Rust/Haskell's impls/instances and ML's structures. In Rust/Haskell, implementations are looked up by a tuple of types and a trait to determine the implementation. The advantage of this is that you don't need to name the impl and then invoke that name every time you use it; since we usually don't think of "Hash for i32" as something which has a meaningful name beyond the relationship between Hash and i32, this is quite nice.
But coherence requires that instances resolve consistently: if I hash an integer in one code location to insert into a map and then hash it again in a different location to do a lookup on the same map, I need to hash integers the same way each time. If you care about coherence, and the correctness property it implies, you can't allow overlapping impls if impls aren't named, because otherwise you aren't guaranteed a consistent result every time you look up the impl.
This introduces another problem: you can't see all the impls in the universe at once. Two libraries could add impls for types/traits in their upstream dependencies, and the incoherence won't be discovered until they are compiled together later on. This problem, called "orphan impls," causes its own controversy: do you just let downstream users discover the error eventually, when they try to combine the two libraries, or do you prohibit all orphan impls early on? Rust and Haskell have chosen different horns of this dilemma, and the grass is always greener.
Of course with implicits, this author intends a different solution to the problem of resolving instances without naming them: just allow incoherence (which they re-brand as "local coherence"). Instead, incoherence impls are allowed and are selected in a manner based on proximity to code location.
As the post eventually admits, this does nothing to solve the correctness problem that coherence is meant to solve, because code with different nearest impls can be compiled together, and in Rust such a correctness problem could become a memory safety problem, and how you figure out if the impl you've found for this type is actually the nearest impl to your code is left as an exercise to your reader. But sure, since you've rebranded incoherence to "local coherence" you can do some juxtaposed wordplay to call coherence a "local maxima" because achieving it has the downside that you can't have arbitrary orphan impls.
I read through this, and thought to myself: "wow, what a response that elucidates the PL design tradeoff space while giving real world examples of languages that occupy various points on that space; all as concisely and economically as possible."
And then I read the user name. Of course it's boats!!
Thank you for all your work! I want to say that especially since I've noticed a lot of shallow dismissal of your work recently (shallow because the dismissal often doesn't engage with the tradeoffs of whatever alternative solution it proposes in the context of Rust, among other things), and would like you to know there's a lot of us who are very very grateful for all the productivity and empowerment you've enabled through your contribution to Rust.
I'm not convinced by your example of hashing.
Let's assume for the sake of argument that the standard library didn't implement Hash for i32.
You could then have two crates, A and B, with different implementations of Hash for i32, and both could instantiate HashMap<i32>.
This can be made to work if we recognize the HashMap<i32> in crate A as a different type than the HashMap<i32> in crate B.
This only really works if orphan implementations are exported and imported explicitly to resolve the conflict that arises from a crate C that depends on A and B.
If C wants to handle HashMap<i32>, it needs to decide whether to import the orphan implementation of Hash for i32 from crate A or B (or to define its own). Depending on the decision, values of type HashMap<i32> can move between these crates or not.
Basically, the "proximity to code location" is made explicit in a way the programmer can control.
This makes type checking more complex, so it's not clear whether the price is worth it, but it does allow orphan implementations without creating coherence problems.
Implementations are not imported at all because they are not named. Like I wrote, named implementations (ala ML modules) is a valid alternative, but one with a much greater annotation burden.
You could imagine having named impls that are allowed to be incoherent as an additional feature on top of coherent unnamed impls, but to use them you would need to make any code that depends on their behavior parameterized by the impl as well as the types. In fact, you can pretty trivially emulate that behavior in Rust today by adding a dummy type parameter to your type and traits.
Again, it's all a set of trade offs.
Right, but what I'm describing is a tradeoff point that's between the extremes, where implementations are unnamed but can still be explicitly imported.
Making my example more explicit, you'd need syntax along the lines of
This syntax would explicitly be limited to orphan implementations.I suppose to further clarify, there's still some coherence requirement there in that crate C can't import the conflicting implementations from both A and B. Which could then perhaps be worked around by adding syntax to spell types along the lines of
Which you could argue is a form of naming implementations, I suppose? I'm not familiar with ML. You could maybe also think of it as a more ergonomic way of doing (more or less) those wrapper types.In any case, the annotation burden only exists where it's actually needed to enable orphan implementations.
And either way, multiple different impls can safely coexist within the overall set of code that's linked together, with everything being statically checked at compile time.
I think rather than at odds with without.boats is saying, this is very much aligned with what they are suggesting. While not literally `use A::impl std::hash::Hash for i32` is for all intents and purposes naming the impl.
Similarly, `HashMap<i32 + A::impl Hash, V>` is what they are talking about when they refer to parameterizing code on the impl chosen.
Essentially, yes. What I don't see is their claim that it's a "much greater annotation burden". Compared to what? Rust today just doesn't allow this at all, and if you use a wrapper type to simulate it, you definitely end up with more "annotations" (boilerplate).
FWIW It's not at all clear to me how this requirement would be implemented in practice: "This syntax would explicitly be limited to orphan implementations."
Maybe I'm missing something, but the compiler can tell whether an implementation is an orphan. That's how you get an error message today if you try to write one. So I don't know what difficulty you have in mind.
Great write up, and you're absolutely right that implicits are moving towards ML modules. Quite possibly a production system would end up being synonymous with ML modules out of the need for named impls.
Small nit in terminology, the implicits described are coherent. Part of their value over previous implicit work is that they are coherent and stable. I have generally seen the property you're referring to called canonicity, which they do lack.
I'm pretty sure the article resolves the implicit dependencies at the point of the declaration. (Did I misunderstood it?)
So, you don't have a `data HashMap datatype`, you have a `data HashMap hashAlgo datatype`, where hashAlgo is decided implicitly by the context. That's the entire reason it's called "implicit".
Every other usage of the data knows how to hash your values because of that `hashAlgo` parameter. It doesn't matter where it happens.
I wanted this feature exactly once:
I was building a memory manager for a database and I needed to know exactly how much space a deep data structure was using.
The servo project has the same problem and they built a library that contained a Sized trait (don't remember the name exactly) and then inplemented that trait for a bunch of stdlib and third party types and for all their types (easy to be done via a derive macro iirc).
I wanted to use that library but I also had other third party types that weren't covered by the library.
The quick solution I found was to basically copy the whole library into my project so that I could add my impls in the trait definition trait.
Anybody knows a better solution?
> We can elucidate our woes by conjuring some contrived Rust code
I need to work on my English vocabulary..
No. Good technical writing is about making the reader feel smart, not the writer. Using big words goes in the opposite direction. The real art is in explaining complex ideas in simple terms.
I think the idea is that the sentence introduces a contrived example, and so the author used roundabout words. Snake sentences sound sibilantly. It's a blog post.
but i think i understand the sentence, and so reading it makes me feel very smart ;-)
That ones on me. I blog as a way to practice writing, and right now I'm working on picking more interesting verbs.
I have a usage of `proselytize` later on that is outright smarmy.
Related nitpick: “maxima” is the plural form, “maximum” is the singular.
The comment in your frobulate code suggests one is to forbulate, yet reading The code it is very clear that there will only be frobulation happening in the outlined proceedings. Perhaps a minor revision is required.
Since you care about the quality of your writing: you almost certainly meant "one's" or "one is", not "ones".
"Outright smarmy" is spicy, I give you that :)
How often do you need to impl trait crate_a::A for a type crate_b::B? If it is allowed by the language, it would mean that behavior of crate_a or crate_b would change if they link one to another.
I really doubt that this is a wanted behavior. And Rust follows this logic, suggesting to use a new type to achieve the same, but not leak your impl into other crates.
A lot. You're not seeing it precisely because it isn't under the streetlight, because it is currently impossible: https://en.wikipedia.org/wiki/Streetlight_effect
This really amps up the composibility of a lot of systems and libraries. It would be awesome if there was a "free" way to do this. Unfortunately no one has found one yet; the posted article is a pretty good overview of that problem.
Also, bear in mind that no matter what solution you are looking at, it's generally crate_c that wants to create the implementation for crate_a's type using a trait in crate_b, so it isn't as bad as the "behavior of crate_a or crate_b would change if they link one to another", which would indeed be horrifying. crate_c has to be involved somehow in the build, without that crate_a and crate_b carry on completely normally. When it's the end-user application doing the trait, at least the end-user can manage it; the core problem arises when crate_c is third-party, and user wants to use that and also crate_d, which also implements a train from crate_b on crate_a's type. At that point you have a pretty big issue; I would characterize implicits as a way of managing the problem, but not really a "solution". It is not clear there is a "solution".
And there is clearly a problem; the Haskell community rammed into this problem decently hard a long time ago, back when they were smaller than they even are today, and certainly smaller back then than the Rust ecosystem as it stands today. The phase transition from theoretical problem to real problem happens in an ecosystem an order of magnitude or two smaller than the current Rust ecosystem, which is itself likely to grow yet by another order or two at least over its lifespan.
Love to see a problem from the frontline of computer science as an actual practical problem solution to which would greatly benefit languages' semantics.
Regarding conflicting impls in crate_c and crate_d: what is wrong with Haskell's approach of grading impls by their specialty (e.g. Show Int is more specific than Show a so prior instance would be used if matches) and only throwing an error if it's ambiguous to the compiler which instance to use?
I see that this is not sufficient, since crate_e can't do anything about conflicting impls in crate_c and crate_d. Having to explicitly import impls does not spark joy. The problem is more convoluted than I thought!
I'm very interested in this topic since I'm working on a language that features traits and thus have a chance to "fix" it.
P.S. found another good article on this topic: https://www.michaelpj.com/blog/2020/10/29/your-orphans-are-f...
"Regarding conflicting impls in crate_c and crate_d: what is wrong with Haskell's approach of grading impls by their specialty"
You can still get surprising errors later in crate_c and crate_d when crate_e adds something, which is suboptimal.
I'm not saying all solutions are equally good or bad, just that there isn't a known perfect solution yet. If you accept the principle that "Writing some more code into module E shouldn't cause new errors to appear in C and D", which is a reasonable thing to want in a system, then this isn't a perfect solution.
For example, if you want to serialize a type whose fields are all public but it doesn’t implement `serde::Serialize`. A lot of crates have an optional `serde` feature for this exact purpose, but not all.
Another use-case is if you want more abstraction than the standard library. There’s a crate named `cc-traits` that exports traits for collections like `Insert` and `Remove`, which are implemented for types on the standard library. But if you’re using a third-party collection library like `btree_vec`, its types don’t implement the `Insert` and `Remove` traits, and you could easily implement them manually except for the orphan rule.
I understand the orphan problem better now. It's not clear what compiler should do if you add two crates which have conflicting impls (where both implement the same foreign trait for the same foreign type)
The role of unification in type systems is interesting here, e.g. for the problem of incompatible set orderings we would like the type of `union` to be something like:
This allows any `O : Ord<T>` we like, as long as both `Set` values have the same one. However, it's not clear what "the same" would mean. A whole-program compiler could see whether both symbols unify (i.e. they point to the same thing); but separate compilation would require a system for referencing/naming each implementation, which would come with its own headaches (e.g. stability across versions, avoiding clashes, etc.). The article mentions an approach based on naming, which I assume is related. Maybe it's time to content-address our definitions like Unison does?That was fascinating, but you can see why the Rust designers decided not to go with that approach.
The singular of ‘maxima’ is ‘maximum’.
Is there a relationship between this and delegation? Delegation feels to me that it's essentially a "named instance/impl".
This. Traits and macros are two real problems with rust. Orphan rule is one, but also const, async and unnamable types (mostly closures). These barely work with traits or do not work at all. If rust did not have closures, it'd be a lot simpler to solve these. Is it so hard to just create a normal function instead of closure?
Perhaps we need to go back to the basics a bit? What is a trait? 1. A set of functions, associated types and generic types 2. A marker/tag (e.g. Send, Sync)
Orphan rules do not seem to be problem for marker traits. Library authors must be responsible for enforcing whether their types are Send/Sync, etc or not.
As for normal traits, it's too late for rust, but I'd just limit traits to being only sets of function definitions, e.g.
trait Iterator = fn next<T>(&mut self) -> Option<T> + fn len(&self) -> usize
Then adding set operations (and, or, xor, not) for traits would be pretty easy, keeping most of power for defining generics.
More importantly traits could be just aliases and two traits with the same set of functions would be equal. This solves orphan problem - you would not need to import or export traits, it would be just normal resolution of functions. Do I call this function from crate A, or crate B? That's a solved problem.
The hard problem is not sharing the trait, but sharing the trait instance.
With your solution, if too modules define traits with identical type signatures but different implementations, it would be impossible for the compiler to decide which impl to use.
If there are two modules module_a and module_b, and each defines a function called foo, how does the compiler decide which foo should be used? It just checks whether you imported module_a::foo or module_b::foo.
The instance could be defined in module c.
Perhaps I should have been more clear. The point is you would not implement traits. You would just implement functions. You would not implemet traits, you would just write functions iter and len for your type.
When calling a function, compiler would check separately for existence of each function defined in the trait. That is a trait would be just like any other type alias so that you do not need to repeating complex function names everywhere:
You could write:
but that would be just syntactic sugar for this: Basically removing traits alltogether, just relying on functions.So you define your filter function by saying it can use anything that has the next and the len functions. Cool.
If a type A defined in module_a doesn’t have the functions defined in its module, should it still be filterable?
If the required function is defined in a module_b should A be filterable?
> trait Iterator = fn next<T>(&mut self) -> Option<T> + fn len(&self) -> usize
This is why I don’t have interest in learning rust. When I see people write c++ code like this I wonder why they feel the need to be so clever.
That is an abysmal thing to maintain.
Nope, just because you lack familiarity with the symbols, it doesn't make that declaration complex.
It's not even "clever". It's completely plain, and the bare minimum and obvious definition of what an "iterator" should be.
That isn’t real Rust code, though it’s made up of valid bits of Rust syntax.
Oh, ok that’s fair. I guess I should at least learn the grammar better before commenting more on rust.
I mean, C#'s IEnumerator is equivalent and is way more complex. You just don't need to think about it much.
There's also the option of using the fact that functions are values, to simply create traitlike values and pass them as arguments to functions (a la SYT: https://www.haskellforall.com/2012/05/scrap-your-type-classe...)
Implicits are motivated, atleast in part, by a desire to improve upon this baseline. In the world of ML modules this is the current state. Typeclasses (as modules) have to be passed everywhere they're used explicitly and it's exhausting. I think with implicits you can keep that as a baseline but provide an implicit mechanism atop it to remove a lot of the obvious boilerplate for a win-win
The title here on HN says maximum, and on the article it says maxima.
I seem to remember maximum is singular where maxima is plural.
The editorialized title is correct. The original article isn't saying that each trait is individually a local maximum. It's saying that the concept of Rust traits is one.
Random number joke is borrowed from XKCD: https://xkcd.com/221/.
I'd propose just getting rid of the orphan rule and keeping global coherence. If a crate has multiple dependencies with the different implementations on the same trait/type, let that crate select or define one implementation that will override the others, even internally.
Then I'd trust library authors to write orphan implementations sparingly, making sure they're either "obvious" (there's no other reasonable implementation for the same trait/type) or their internals aren't relied on, just the fact that the trait/type has a reasonable implementation (like defining `Serialize` and `Deserialize` but only relying on both being inverses, so a dependent crate could override them with a different `Serialize` and `Deserialize` implementation and the library would still work).
I'd claim the libraries that define bad orphan instances must be poorly written, and you should only depend on well-written libraries. If you want to depend on libraries A and B which both rely on conflicting orphan implementations, don't bother trying to patch one of them, instead re-write the libraries in a better way to keep your codebase ideal.
...I still want that kind of system, but I expect it would fail catastrophically in the real world, where developers aren't perfect, important projects depend on badly-written npm packages, and Hyrum's law is pervasive.
---
So instead I propose something more reasonable. Keep global coherence and:
- Get rid of the orphan rule for applications. An application has no dependents, so the entire issue "two dependencies differently implement the same trait on the same type" doesn't apply.
- Next, create an opt-in category of libraries, "glue" libraries, which can only define orphan implementations (if they absolutely need a unique type, e.g. an associated type of a type/trait implementation, it can be put in another crate that is a third dependency of the glue library). Glue libraries can only be depended on by applications (not libraries, including other glue libraries). This allows orphan code reuse but still prevents the vast majority of code (the code in libraries) from depending on orphan implementations.
Library authors who really want to depend on orphan instances can still do ugly workarounds, like asking application developers to copy/paste the library's code, or putting all the library's functions in traits, then implementing all the traits in a separate "glue" library. But I suspect these workarounds won't be an issue in practice, because they require effort and ugly code, and I believe trying to avoid effort and ugly code is what would cause people to write bad orphan instances in the first place. Also note that library authors today have ugly workarounds: they can copy/paste the foreign trait or type into their library, and ask developers to "patch" other libraries that depend on the foreign crate to depend on their library (which can be done in `Cargo.toml` today). But nobody does that.
Ideally, a library that really needs an orphan implementation would use a better workaround: create a new trait, that has the foreign trait a supertrait, and methods that implement functionality of the foreign type, then use the new trait everywhere you would use the foreign type. I suspect this solves the global coherence problem, because an application could depend on the glue library that implements your library's trait on the foreign type, but it could alternatively depend on a different glue library that implements the trait on a wrapper, and if there's another library that requires a conflicting implementation of the foreign type, its trait would be implemented on a different wrapper.
> ...I still want that kind of system, but I expect it would fail catastrophically in the real world
Julia has its own version of the orphan rule called Type Piracy, which is merely discouraged instead of disallowed: https://viralinstruction.com/posts/latency/#a_brief_primer_o...
It's not a net gain, but rather a different tradeoff.
*local maximum. Maxima is plural, maximum is singular.
/pedantic
Now I'll read the actual article
> Maxima is plural
In Latin. I am surprised this word hasn't been internalised enough to just use the regular English plural marker. Maximum / maximums.
It's because they've used the plural of "Trait" in an ungrammatical way, and so used the plural of "maxima". Traits aren't a local maxima - the trait design is a local maximum. Or traits are at a local maximum. The traits themselves aren't a maximum (or maxima (or maximae)).
(the concept of) traits is a local maximum
based on the downvote this received i guess something is wrong with that sentence. but i am not an english native, and i can't tell what would be wrong with it. i am not bothered by the downvotes, if it is wrong then so be it, but i would like to know why it's wrong.
If one squints, this is the heart of the article: scope.
The lust to get to a final, complete set of types across all projects for the system for all time will never be satisfied.
The question moves to who has the preferred shims.