What kind of typeclass coherence should we support? #17918
Replies: 28 comments
-
I don't think any discussion of coherence would be complete without a link to the Cochis paper, as even if we don't want to consider applying that algorithm the Related Work section is a good summary of the different approaches 😄 |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Not sure if this is possible, but I think having uncheck global coherence (as a default) and a keyword to specify that a certain typeclass requires coherence. For some typeclasses you definitely wan't coherence, i.e. the principled typeclasses (stuff like Not sure what the syntax of typeclasses is going to be, but something like this is what I would image // default case, not coherent typeclass Semigroup[A]{defcombine(l: A)(r: A):A }vs // coherent typeclasses, i.e. Haskell style coherent typeclass Semigroup[A]{defcombine(l: A)(r: A):A }Or something along these lines. Note that the above is for illustrative reasons, for |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
I wrote a blog post about a possible solution (with added compiler support) to global coherence which is optional on both the declaration and use sites. It could be a starting point for solution ideas. |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Another critical design question for checked global coherence are orphan instances. Haskell allows them, and there are good use cases for them since they reduce dependencies on library modules. The price to pay is that coherence errors might persist until link time. For Scala on the JVM with lazy loading this means that coherence errors might only be detected at runtime, and only in rare cases (say an exception path causes a new library to be loaded which causes a program crash due to a coherence error -- not what you want!) Rust disallows them, it requires all instances to be defined "in the vicinity" of either the instance type or the implemented trait. What "in the vicinity" means is complicated and has evolved over the Rust releases. |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
IMHO orphan instances should definitely be allowed, they are a useful design tool. I think they only pose a problem when only one unique type class instance is allowed (like in Haskell). My proposed solution linked above allows multiple instances to be defined, but adds extra type information which can be used to uniquely identify each one (or rather a group of semantically equivalent ones). In each use site one can then choose to either use a specific instance or any instance implementing the type class interface. |
BetaWas this translation helpful?Give feedback.
-
Any (known) use case for orphan instances for coherent typeclasses? If not, I'd allow orphans for coherent typeclasses and disallow them otherwise.
I agree, but the issue with incoherence people keep mentioning involves ordering and dictionaries. I 100% think that, in Scala like in ML, one appropriate solution should ensure the type of dictionaries depends on the ordering, so that dictionaries with different orderings have incompatible types. See https://github.com/chrisokasaki/scads/blob/master/design/heaps.md for a sketch, though that shows some issues. |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
@Blaisorblade Are you sure Scala doesn't support applicative functors? You can share types trivially: importscala.reflect.runtime.universeimportscala.reflect.api.UniversetraitBig{self =>valu:Universevalcollab1:Collab1{valu: self.u.type } valcollab2:Collab2{valu: self.u.type; valcollab1: self.collab1.type } deftpe: u.Type={valcustom: collab1.MyCustomType= collab2.myCustomType valt: u.Type= custom.tpe t } } traitCollab2{self =>valu:Universevalcollab1:Collab1{valu: self.u.type } defmyCustomType: collab1.MyCustomType= collab1.MyCustomType(u.weakTypeOf[this.type]) } traitCollab1{valu:UniversecaseclassMyCustomType(tpe: u.Type) } objectBig{defapply (u0: Universe) (collab10: Collab1{valu: u0.type }) (collab20: Collab2{valu: u0.type; valcollab1: collab10.type }) =newBig{self =>finalvalu: u0.type= u0 finalvalcollab1: collab10.type= collab10 finalvalcollab2: collab20.type= collab20 } } objectMainextendsApp{self =>finalvalcollab1=newCollab1{finalvalu: universe.type= universe } finalvalcollab2=newCollab2{finalvalu: universe.type= universe; finalvalcollab1= self.collab1 } println(Big(universe)(collab1)(collab2).tpe) }What else is missing? |
BetaWas this translation helpful?Give feedback.
-
Your example doesn’t show an applicative functor, but since BIg.apply is fully transparent, the distinction between applicative and generative disappears. Applicative functors must work even when the functor’s return signature contains abstract interfaces. Here’s an example inspired from Derek Dreyer’s slides: traitSetModule[Elem]{typeSet } // we’d want this to be an applicative functor:implicitdefmkTreeSet[T:Ord]:SetModule[T] =newSetModule{/* ... */ } //object TreeSet{def apply[T](x: T): SetModule[T] = mkTreedefsingleton[T](x: T)(implicitsm: SetModule[T]): sm.Setdefmerge[T](implicitsm: SetModule[T])(ts1: sm.Set, ts2: sm.Set): sm.Set merge(singleton(1), singleton(2)) // won’t typecheck, but it could with applicative functors, because each implicit call to mkTreeSet[Int] will produce a distinct Set member, tho they will all be in fact the sameMost Scala programmers would also dispute “trivially”, but that’s a separate issue. |
BetaWas this translation helpful?Give feedback.
-
Here might be a possible scheme to support local coherence: In a context bound like classListFunctorextendsFunctor[F[_]]{defmap ... } implicitobjectListFunctorextendsListFunctorimplicitobjectListMonadextendsListFunctor ... implicitobjectListTraverseextendsListFunctor ...In a setup like this, the compiler can check that It's an open question whether local coherence should be required for all context bounds |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Another question would be – should a user be able to call a coherent-bound function with incoherent instances via NB: Odersky's proposal above was possibly derived by my recent comment in dotty / contributors (lampepfl/dotty-feature-requests#4 (comment)) (https://contributors.scala-lang.org/t/dotty-type-classes/2241/40) |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
@Kaishh I agree, coherence needs to be enforced for explicit as well as implicit arguments. But there is already a way to avoid coherence: use implicit parameters directly: |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
How then would you express the following bound: give me the context bound for Then what about two coherent pairs of Or, maybe, such kind of bounds are never needed in practice? |
BetaWas this translation helpful?Give feedback.
-
@Blaisorblade @odersky deff[F[_]:Traverse](implicitME:MonadError[F, Throwable])e.g.: deff[F[_]:Traverse](implicitME:Coherent[MonadError[F, Throwable]])@buzden |
BetaWas this translation helpful?Give feedback.
-
You can use context bounds for In Scala 2 too, strictly speaking... |
BetaWas this translation helpful?Give feedback.
-
Hmm, I find it a bit counter intuitive that under this proposal Not sure what to do in the case of |
BetaWas this translation helpful?Give feedback.
-
Yes, that's a downside. So maybe using a special syntax for coherent context bounds is preferable, after all. |
BetaWas this translation helpful?Give feedback.
-
What about using a marker trait like in your original proposal instead? |
BetaWas this translation helpful?Give feedback.
-
I am not sure what that would look like? |
BetaWas this translation helpful?Give feedback.
-
After thinking some more, I'm now in favor of making local coherence default for both context bounds and parameter sections, and requiring user to request incoherence explicitly via some syntax, e.g. defx[F[_]](implicitF:Monad[F] withIncoherent)or defx[F[_]](implicitF:Incoherent[Monad[F]])Also, the list of base classes checked for coherence should obviously exclude |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
What I mean by that is that if you use traits that extend the marker trait |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
I think we should never assume coherence without proof. If it's not checked, it's not there. If one absolutely needs an escape hatch, it could be via an I am reluctant to introduce more marker traits to signify a property that is not strictly speaking a type. We did that with Finally, I am not convinced that the best way to model coherence is as a property between a class and its base class. That would flag any type class that overrides a method in its base class as incoherent. I think that would conflict with common idioms like |
BetaWas this translation helpful?Give feedback.
-
As far as I understand, we should never talk about blind assuming when we are talking about local coherence, since it can be checked locally each time it is used, i.e. if a function with context-bounded parameters requires local coherence, we can check it at each use of this function. The need of this is clear and practical: it allows such a function to use different functions from required typeclass instances without worrying about incompatibility between their implementations. Solution seems to be existing: we need some syntax to distinguish whether function requires local coherence or not and we need to define clearly semantics and defaults. Maybe, other solutions exists too. But if we talk about assuming, we are talking about global coherence. Are there any practical usages of it (except the fact that for some type there only one typeclass instance implementation exists that follows all the restrictions for the typeclass)? Sorry, if this question seems dumb. |
BetaWas this translation helpful?Give feedback.
-
I'm sorry, I worded that badly, what I meant was that coherence should always be checked in those cases.
That's fair. My preference would be to have that property be defined at the declaration-site instead of at the use-site. I think an explicit opt-out via |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Ah, ok, I see what you mean now 😄
I don't see how that could work. At the declaration site you'd be effectively checking global coherence, with all the problems that come with it. Local coherence is inherently a use site property. If I pass a type |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
Uh oh!
There was an error while loading. Please reload this page.
-
Right, sorry again, I was talking about the syntactical property not the semantical. The check should still be done at use-site. I was just trying to voice, that in the event that we can't check local coherence by default, my preference would be something like this: traitFunctor[F[_]]{... } // Setting the "local coherence flag" at declaration-sitetraitApplicative[F[_]] extendsFunctor[F] withCoherentInheritance{... } traitTraverse[F[_]] extendsFunctor[F] withCoherentInheritance{... } defFoo[F[_]:Traverse:Applicative] = ...Over traitFunctor[F[_]]{... } traitApplicative[F[_]] extendsFunctor[F]{... } traitTraverse[F[_]] extendsFunctor[F]{... } // Setting the "local coherence flag" at the use-sitedefFoo[F[_]:Traverse&Applicative] = ...I hope that we don't have to do either and can do the checking by default and allow opting as had been mentioned earlier. :) |
BetaWas this translation helpful?Give feedback.
-
IMHO an annotation on a type at use site seems to be the least intrusive way of activating the escape hatch. deffoo[F[_]](implicitF:Functor[F] @uncheckedCoherence) |
BetaWas this translation helpful?Give feedback.
-
@rkrzewski Fully agreed 👍 |
BetaWas this translation helpful?Give feedback.
-
@odersky Is there any update on this? :) |
BetaWas this translation helpful?Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
-
Scala does not have a global coherence requirement for its implicits.
#2046 contains a discussion whether this should be changed and section 9 of #4153 contains another proposal to have local, instead of global coherence.
We should arrive at a decision what we want to do:
BetaWas this translation helpful?Give feedback.
All reactions