Traits are a local maximum

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.<p>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.<p>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.

Rust just doesn’t really have linker errors.<p>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&#x2F;C++ code that ends up in the dep tree.<p>This property is downstream of the orphan rules, and given the benefit I wouldn’t give them up.

For context, Haskell&#x27;s story for orphan instances is currently as follows:<p>- orphan instances are allowed and emit a warning<p>- duplicate instances are not allowed<p>- overlapping instances where one is different from the other, are allowed<p>- incoherent instance use sites are not allowed (where 2+ instances match and neither is more specific than the other)<p>- but you can enable this by adding {-# INCOHERENT #-} to instances. You shouldn&#x27;t do this though unless you really know why you need it (and perhaps even then there is a better way)<p>- a typical library sets all warnings as errors with -Wall, so you&#x27;ll notice when you&#x27;re adding orphans<p>- exceptions in specific files can be made by adding -fno-orphans to the file<p>- defining orphan instances in executables is not a problem as the only user of them will be the program itself<p>- 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<p>- 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)<p>- since newtypes have no runtime overhead, also, with DerivingVia, syntactic overhead is quite low. This is &quot;the way&quot; to override already defined instances.<p>IMO, all the above makes sense when you prefer correctness over flexibility. From the post, this appears to be Rust&#x27;s choice as well.

There&#x27;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&#x27;s useful to note that in those languages this &quot;local coherence&quot; approach doesn&#x27;t just &quot;look like&quot; lambda calculus, it <i>is</i> lambda calculus. For example, to insert a new element into a sorted list we might define a function like this:<p><pre><code> insert: (t: Type) -&gt; (o: Ord t) -&gt; t -&gt; List t -&gt; List t insert t o x xs = case xs of Nil _ -&gt; Cons t x (Nil t) Cons _ y ys -&gt; case lessThanOrEq t o x y of True -&gt; Cons t x xs False -&gt; Cons t y (insert t o x ys) </code></pre> (Sure, we could also use a more specific type like &#x27;SortedList t&#x27; or whatever; that&#x27;s orthogonal to my point)<p>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&#x27;s literally just lambda calculus.<p>However, this obviously gets quite tedious; especially when there&#x27;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&#x27;t the computer work it out? Yes we can, and we usually do this with {braces} syntax, e.g.<p><pre><code> insert: {t: Type} -&gt; {o: Ord t} -&gt; t -&gt; List t -&gt; List t insert _ _ x xs = case xs of Nil _ -&gt; Cons x Nil Cons _ y ys -&gt; case lessThanOrEq x y of True -&gt; Cons x xs False -&gt; Cons y (insert x ys) </code></pre> Here I&#x27;ve indicated that `t` and `o` can be worked out from the context; I&#x27;ve replaced their argument names with `_` and we&#x27;re no longer passing them explicitly into the recursive call, or to `Cons`, `Nil` or `lessThanOrEq` (assuming that those functions&#x2F;constructors have also marked their arguments as such).<p>This is why the feature is called &quot;implicits&quot;, since it&#x27;s leaving some arguments implicit, for the compiler to fill in using information that&#x27;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&#x27;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 is wrong with the following solution?<p>Any trait implementations where the type and trait are not local are:<p>* Private, and cannot be exported from a crate<p>* The local trait implementation always overrides any external implementation<p>That would solve part of the problem right? Only crate libraries that want to offer trait implementations for external traits&#x2F;types are not possible, but that might be a good thing.<p>The solution proposed by the author with implicits is quite complex, I can see why it wasn&#x27;t chosen.

What an excellent write-up, and very entertaining at that.<p>I suspect that most devs will prefer the local maximum that traits are. Perhaps with a bit more help to ensure there&#x27;s only ever one implementation of a given trait -- think of a trait <i>registry</i>. 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&#x27;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&#x2F;registrars. Registries might feel like a hack, but so what, compared to the problems with implicits, they might be worthwhile.

It&#x27;s been a while now, but I believe Ed Kmett covers some of this in his talk &quot;Typeclasses vs The World&quot;<p><a href="https:&#x2F;&#x2F;m.youtube.com&#x2F;watch?v=hIZxTQP1ifo" rel="nofollow">https:&#x2F;&#x2F;m.youtube.com&#x2F;watch?v=hIZxTQP1ifo</a>

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.

This post is written by a fan of implicits, so it frames it as &quot;better&quot; 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.<p>The core difference between traits (also called type classes) and ML modules is that with traits the instance&#x2F;implementation has no name, whereas for ML modules they do. The analogy here is between Rust&#x2F;Haskell&#x27;s traits&#x2F;typeclasses and ML&#x27;s signatures and between Rust&#x2F;Haskell&#x27;s impls&#x2F;instances and ML&#x27;s structures. In Rust&#x2F;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&#x27;t need to name the impl and then invoke that name every time you use it; since we usually don&#x27;t think of &quot;Hash for i32&quot; as something which has a meaningful name beyond the relationship between Hash and i32, this is quite nice.<p>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&#x27;t allow overlapping impls if impls aren&#x27;t named, because otherwise you aren&#x27;t guaranteed a consistent result every time you look up the impl.<p>This introduces another problem: you can&#x27;t see all the impls in the universe at once. Two libraries could add impls for types&#x2F;traits in their upstream dependencies, and the incoherence won&#x27;t be discovered until they are compiled together later on. This problem, called &quot;orphan impls,&quot; 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.<p>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 &quot;local coherence&quot;). Instead, incoherence impls are allowed and are selected in a manner based on proximity to code location.<p>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&#x27;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&#x27;ve rebranded incoherence to &quot;local coherence&quot; you can do some juxtaposed wordplay to call coherence a &quot;local maxima&quot; because achieving it has the downside that you can&#x27;t have arbitrary orphan impls.

&gt; We can elucidate our woes by conjuring some contrived Rust code<p>I need to work on my English vocabulary..

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.<p>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.

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:<p><pre><code> union&lt;T, O : Ord&lt;T&gt;&gt;: Set&lt;T, O&gt; -&gt; Set&lt;T, O&gt; -&gt; Set&lt;T, O&gt; </code></pre> This allows any `O : Ord&lt;T&gt;` we like, as long as both `Set` values have the same one. However, it&#x27;s not clear what &quot;the same&quot; 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&#x2F;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&#x27;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.

I wanted this feature exactly once:<p>I was building a memory manager for a database and I needed to know exactly how much space a deep data structure was using.<p>The servo project has the same problem and they built a library that contained a Sized trait (don&#x27;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).<p>I wanted to use that library but I also had other third party types that weren&#x27;t covered by the library.<p>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.<p>Anybody knows a better solution?

The singular of ‘maxima’ is ‘maximum’.

Is there a relationship between this and delegation? Delegation feels to me that it&#x27;s essentially a &quot;named instance&#x2F;impl&quot;.

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&#x27;d be a lot simpler to solve these. Is it so hard to just create a normal function instead of closure?<p>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&#x2F;tag (e.g. Send, Sync)<p>Orphan rules do not seem to be problem for marker traits. Library authors must be responsible for enforcing whether their types are Send&#x2F;Sync, etc or not.<p>As for normal traits, it&#x27;s too late for rust, but I&#x27;d just limit traits to being only sets of function definitions, e.g.<p>trait Iterator = fn next&lt;T&gt;(&amp;mut self) -&gt; Option&lt;T&gt; + fn len(&amp;self) -&gt; usize<p>Then adding set operations (and, or, xor, not) for traits would be pretty easy, keeping most of power for defining generics.<p>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&#x27;s a solved problem.

There&#x27;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: <a href="https:&#x2F;&#x2F;www.haskellforall.com&#x2F;2012&#x2F;05&#x2F;scrap-your-type-classes.html" rel="nofollow">https:&#x2F;&#x2F;www.haskellforall.com&#x2F;2012&#x2F;05&#x2F;scrap-your-type-classe...</a>)

Random number joke is borrowed from XKCD: <a href="https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;" rel="nofollow">https:&#x2F;&#x2F;xkcd.com&#x2F;221&#x2F;</a>.

The title here on HN says maximum, and on the article it says maxima.<p>I seem to remember maximum is singular where maxima is plural.

I&#x27;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&#x2F;type, let that crate select or define one implementation that will override the others, even internally.<p>Then I&#x27;d trust library authors to write orphan implementations sparingly, making sure they&#x27;re either &quot;obvious&quot; (there&#x27;s no other reasonable implementation for the same trait&#x2F;type) or their internals aren&#x27;t relied on, just the fact that the trait&#x2F;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).<p>I&#x27;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 <i>rely on</i> conflicting orphan implementations, don&#x27;t bother trying to patch one of them, instead re-write the libraries in a better way to keep your codebase ideal.<p>...I still <i>want</i> that kind of system, but I expect it would fail catastrophically in the real world, where developers aren&#x27;t perfect, important projects depend on badly-written npm packages, and Hyrum&#x27;s law is pervasive.<p>---<p>So instead I propose something more reasonable. Keep global coherence and:<p>- Get rid of the orphan rule for <i>applications</i>. An application has no dependents, so the entire issue &quot;two dependencies differently implement the same trait on the same type&quot; doesn&#x27;t apply.<p>- Next, create an opt-in category of libraries, &quot;glue&quot; libraries, which can <i>only</i> define orphan implementations (if they absolutely need a unique type, e.g. an associated type of a type&#x2F;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.<p>Library authors who <i>really</i> want to depend on orphan instances can still do ugly workarounds, like asking application developers to copy&#x2F;paste the library&#x27;s code, or putting all the library&#x27;s functions in traits, then implementing all the traits in a separate &quot;glue&quot; library. But I suspect these workarounds won&#x27;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 <i>today</i> have ugly workarounds: they can copy&#x2F;paste the foreign trait or type into their library, and ask developers to &quot;patch&quot; 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.<p>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&#x27;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&#x27;s another library that requires a conflicting implementation of the foreign type, its trait would be implemented on a different wrapper.

*local maximum. Maxima is plural, maximum is singular.<p>&#x2F;pedantic<p>Now I&#x27;ll read the actual article