Allow implicit precedence to be controlled by an `@implicitWeight` annotation

[paulp]

...or any way of controlling implicit precedence which doesn't require creating ridiculous inheritance hierarchies. https://github.com/scala/scala/commit/c01e44786d

[propensive]

I tested this out this patch in old fork a few months ago. @paulp's not lying when he implies it works.

[puffnfresh]

:+1:

[tixxit]

:+1:!!

[non]

:+1: this would be incredibly useful

[gabro]

+1, the LowPriority trait dance is madness!

[puffnfresh]

Reminds me of the CSS z-index mess, though. Can't wait to see @implicitWeight(9999).

[paulp]

@puffnfresh Your reservations are warranted. My enthusiasm for a better mechanism exceeds my enthusiasm for this mechanism. But at the moment I don't have a better idea.

[paulp]

As an aside, it's funny how many of our problems come down to composition.

[Blaisorblade]

:+1:

As an aside, it's funny how many of our problems come down to composition.

Composition is a major PL problem, and Scala's goal is to have progress on this.

Can you spell out requirements on the order structure of weights? In short, if I'm guessing requirements correctly, floating point weights might be an improvement, though not perfect.

Floating point would satisfy the requirement that :

1. between any two weights there's always another weight.

Another advantage is that we have two infinities, so that we can write @implicitWeight(Double.PositiveInfinity). Requirement:

there's a least weight and a biggest weight (like in a complete lattice).

However, I'm talking about the mathematical set of rationals extended with both infinities — also because I believe that's the level the discussion should happen at. Doubles have extra stuff we don't care for — two different zeros, and NaN. We would rule NaNs out and declare zeros equal.

Also, do we want a total ordering? I don't really buy that; I think you want some complete lattice. (Though I can't think of an interesting complete lattice which is dense and not a total order).

1. If the ordering of weights is partial, we have the possibility to express ambiguity.
2. Choosing sensible weights globally can't be modular. In fact, what's modular is to order weights within a single library. But if you have conflicting implicits from two libraries, it doesn't make sense that one or the other libraries prevails because e.g. the first libraries uses weights 1 and 2 and the second chooses weights 1000 and 2000: you really want them to conflict. So you need weights to form a partial order; in this scenario, only weights from the same library should be comparable. One should be able to resolve the ambiguity by writing some glue code, by reexporting the implicits with different priorities. (Should the need arise, one might design support for this glue code). Sth. like:

@implicitWeight(100) implicit val reexportFoo = lib1.foo _;
@implicitWeight(120) implicit val reexportFoz = lib1.foz _;
@implicitWeight(200) implicit val reexportBar = lib2.bar _;
@implicitWeight(300) implicit val reexportBaz = lib2.baz _;

A problem is that I know no sensible definition of "module" or "library" for use here.

[Blaisorblade]

As a counterpoint to what I wrote: we should be careful with letting perfect be the enemy of good; in particular, we should try to satisfy requirements we actually have, not just stuff we imagine is important.

[paulp]

@Blaisorblade that's definitely the spirit of the actually written patch. You can see the immediate payoff in nearby commits, and I have no doubt everyone here has a project which would also see immediate benefits.

[non]

I agree with @paulp -- weights would be a huge payoff.

If the cost of specifying weight as a Double is small, it might be worth changing to make it harder to create two weights with no weight in between them. (Note: harder, not impossible.) But I don't want to bike shed this to death (despite my previous statements about how attractive a turquoise shed would be).

[milessabin]

I share @Blaisorblade's concerns here. I'm also not convinced that the benefits are that great once we've dealt with the headline cases. Does anyone have an estimate of the LoC reduction this would win for Scalaz?

[propensive]

So, my instinct is to agree with @Blaisorblade and @milessabin about the lack of modularity, though I think the benefits of the "simple" solution would be significant. But let's not rush into this.

Here's an alternative suggestion I just came up with. In the event of finding ambiguous implicits, could we have some sort of adjudicator (disambiguator?) -- itself defined as an implicit, and resolved by the same rules, but only in the event of a tie -- determine the winner?

Open questions:

• How do you define such an adjudicator?
• In particular, if you have a tie between 2 (or n) implicits, possibly from different libraries, how do we specify in the adjudicator definition how we match which implicits we're disambiguating between? We could have the adjudicator describe an order (partial or total?) on which implicits it should use first, but how would we refer to those implicits?
• If we find an adjudicator which doesn't reference one or more of the ambiguous implicits, do we ignore it because we consider that it doesn't know enough?
• Adjudicators would probably need to compose
• What happens if we have ambiguous adjudicators? (I actually don't think this matters; we solve it the same way.)
• If we introduced such a new concept, what other (unintended, possibly evil) possibilities could it introduce?

This all sounds quite complicated. I suspect it has to be, because we're working in the realm of implicit search, but (as you can see) my ideas are vague at best right now. Hopefully some sense can be made out of all this...

[paulp]

@propensive Please see this thread in particular this message about inference guidance.

trait Guidance {
  def inferrable(tpe: Universe#Type): Boolean
}
object NoGuidance extends Guidance {
  def inferrable(tpe: Universe#Type) = true
}
object NoAnyGuidance extends Guidance {
  def inferrable(tpe: Universe#Type): Boolean = !(tpe exists (tp => tp.typeSymbol.fullName.toString == "scala.Any"))
}

Anything like this is so much more complicated than the implicitWeight annotation it's not even in the same sphere of discussion. You guys will have to decide between some of your taller ambitions and maintaining compatibility, because you won't do both.

[non]

In Spire we have a particular situation where we end up with 8 traits instead of 1 due to this issue.

Here's a quick histogram of the number of InstanceX traits Spire currently has in the core project:

• Instances0: 8
• Instances1: 6
• Instances2: 5
• Instances3: 4
• Instances4: 1
• Instances5: 1
• Instances6: 1
• Instances7: 1
• Instances8: 1

I've had to explain to people what this code was doing before, and it would be really nice to not need this kind of artificial structure, IMO.

[gabro]

I've seen something very similar in anorm: https://github.com/playframework/playframework/blob/master/framework/src/anorm/src/main/scala/anorm/TupleFlattener.scala#L7, where 21 useless traits are created with the only purpose of prioritizing the implicits.

[aloiscochard]

-1 from ne, this thing feel like a type level GOTO statement (I intentionally exaggerated, but I think that can affect readability when miss used).

OTOH, I understand Erik needs in spire.

What about an annotation that when define on trait/class/... means that all the implicits in it are prioritise by order of definition?

[Blaisorblade]

What about an annotation that when define on trait/class/... means that all the implicits in it are prioritise by order of definition?

EDITED for precision. Order of definition? Most people agree that depending on definition order makes a language worse (less declarative), not better (see Prolog vs. Datalog). So :-1: on that from me.

[Blaisorblade]

A colleague suggested having relative weights — with implicits being able to say they have a higher-priority than some other implicits. That's a way to get a partial order. Moreover, if you only allow that for implicits declared together, you can actually encode it by converting to the hierarchy you write by hand nowadays (which would retain compatibility). You have to write more code (to name methods), but that's actually more declarative and closer to your intent (weights are a way to encode that).

Concretely:

@preferredTo("name2") implicit def name
implicit def name2

I still dislike the implementation complexity of the encoding so I would probably not do it, but I might be wrong.

So, one alternative is to generate the implicit hierarchies via code expansion. If this could be done in a macro it would be better.

On using implicit weights, I am not so convinced that the modularity problem is so relevant, because implicits typically have to involve "fresh" types. Good code can't declare "implicit foo: Int". The modularity problem arises when combining two independent extensions to the same library — but that seems (a) uncommon (we found no library actually needing that); (b) very hard anyway

In other words, that seems a research problem which seems not so interesting. So, we could let in the current @implicitWeight (or a version with Longs/Doubles).

[Blaisorblade]

Forgot to point out (I was writing that by email): you can either:

• have a @preferredTo annotation and encode it through desugaring to trait hierarchies. (Assuming somebody can figure out the details of the encoding scheme).
• have an @implicitWeight annotation which establishes a global order among implicits. Since the order is global, a correct desugaring can only be done when the whole program is available, and this breaks separate compilation.

You cannot have what was proposed on the mailing list, that is the current @implicitWeight on the surface and the trait-based desugaring, because you need to respect @implicitWeight's natural semantics — which is the global one Paul implemented, which work across implicits in unrelated classes.

Any project switching to @implicitWeight would change behavior, but for cases which they do not support. But the compiler can't take such assumptions.

What you can implement with the encoding is an order across implicits defined together. That would map to a different source syntax (yes, you could use @implicitWeight, but the actual semantics would not match the "obvious" semantics of implicitWeight).

[aloiscochard]

+1 for the @preferredTo approach, which solve the concern I had about readability and reasoning.

[lefou]

+1 for @preferredTo too. It resolves ambiguities where they occur and it improves reasoning. As far as I understand it, it would solve all my implicit ambiguities I had in the past without implying precedence to other code locations.

[Blaisorblade]

I've wondered about the annotation overhead, so I've looked at the two worst examples above. TupleFlattener encodes a linear order, so switching to @preferredTo would need one annotation per implicit (mentioning the previous one).

The Spire example by @non is similar, except for rig/rng, which have no priority across each other:

trait DistInstances {
  implicit def semiring[A](implicit ev: Semiring[A]): Semiring[Dist[A]] =
    new DistSemiring[A] { def alg = ev }

  @preferredTo('semiring) implicit def rig[A](implicit ev: Rig[A]): Rig[Dist[A]] =
    new DistRig[A] { def alg = ev }

  @preferredTo('semiring)
  implicit def rng[A](implicit ev: Rng[A]): Rng[Dist[A]] =
    new DistRng[A] { def alg = ev }

  @preferredTo('rng, 'rig)
  implicit def ring[A](implicit ev: Ring[A]): Ring[Dist[A]] =
    new DistRing[A] { def alg = ev }
//...
}

Since the annotation is transitive, the number of annotations is kept low enough in these cases :-)

[propensive]

I'm not so happy with this @preferredTo idea. First off, it introduces a completely new concept to Scala: referring to the name of a method by a string/symbol literal of its name, which may not be unique amongst the implicit candidates. It feels very hackish, bolted-on, and as such, very unScalalike.

Secondly, it seems like actually a reasonably common use case to want to be able to disambiguate between two implicits defined in separate projects, each of which doesn't know about the other. Am I missing something here? This seems like one of the most important use cases...

[mandubian]

On Sat, Sep 20, 2014 at 12:28 AM, Jon Pretty notifications@github.com wrote:

I'm not so happy with this @preferredTo idea. First off, it introduces a completely new concept to Scala: referring to the name of a method by a string literal of its name, which may not be unique amongst the implicit candidates. It feels very hackish, bolted-on, and as such, very unScalalike.

I tend to agree with you on the symbol reference concept which doesn't exist now in Scala... And I wonder also about what happens with respect to other implicits declared without the annotation? What are the priority then?

Secondly, it seems like actually a reasonably common use case to want to be able to disambiguate between two implicits defined in separate projects, each of which doesn't know about the other. Am I missing something here? This seems like one of the most important use cases...

— Reply to this email directly or view it on GitHub https://github.com/typelevel/scala/issues/28#issuecomment-56243992.

[propensive]

I think there's still a long way to go on finding a good solution to this.

A question worth asking is whether the original idea, the @implicitWeight annotation is a useful stopgap measure, and whether implementing it now would preclude implementing some better solution later on which does what we want.

Either way, my feeling is that we shouldn't jump to any "solution" too hastily on this. Let's keep discussing it...

[Blaisorblade]

A question worth asking is whether the original idea, the @implicitWeight annotation is a useful stopgap measure, and whether implementing it now would preclude implementing some better solution later on which does what we want.

To be sure: as I argued above, you can't implement Paul's @implicitWeight semantics by translating to traits locally. You'd get something different there, which would be surprising to authors because the weights only work in a single compilation unit. So my weight 5000 might be less than weight 5 in another library. I think this would be a bad idea. You can't avoid that by translating to traits, because you'd need a global translation.

I think Paul's patch is useful inside Typelevel Scala, and thus worth experimenting with, behind a flag. The point of having multiple flags is also to allow merging ideas that later turn out to be stupid.

Moreover, getting the trait translation right is not going to be trivial. You simply need to write a program transformation which, for all possible uses, does a reasonable translation or says "this is too complicated" and gives a useful explanation. This is certainly an argument for Paul's patch.

[Blaisorblade]

I'm not so happy with this @preferredTo idea. First off, it introduces a completely new concept to Scala: referring to the name of a method by a string/symbol literal of its name, which may not be unique amongst the implicit candidates.

Not unique? I've thought about overloading, but IIRC it doesn't work with implicits. Otherwise I'd have gone with the signature. Moreover, what you write with @preferredTo is what you encode with weights.

I agree that the concept is novel — the more Scalaish way would be to use the function directly there. I've never seen an annotation doing that, but it fits better.

And I wonder also about what happens with respect to other implicits declared without the annotation? What are the priority then?

Good question — it also affects the naming. The two coherent solutions are:

• specify which traits have lower-than-default priority (with @lowerPriorityThan or similar, like LowPriorityImplicits). Everything else gets the same, high priority (and uses other mechanisms for disambiguation, that is the type). With translation to traits, unannotated traits get to the most specific trait, thus get highest priority.
• dually, specify which traits have higher-than-default priority (with @preferredTo). Everything else gets the same, low priority (and uses other mechanisms for disambiguation, that is the type). With translation to traits, unannotated traits get to the least specific trait, thus get lowest priority.

[Blaisorblade]

Secondly, it seems like actually a reasonably common use case to want to be able to disambiguate between two implicits defined in separate projects, each of which doesn't know about the other. Am I missing something here? This seems like one of the most important use cases...

I'm undecided. Currently, you'd need to use glue code to re-export the implicits. And maybe that's the reason why we'll find no actual example around.

For an example with, say, typeclasses, you'd need two libraries providing the equivalent of "orphan instances". Say, two libraries providing Show[File].

In this case, I'm not sure things are any easier:

1. With Paul's patch, you'd need to coordinate on weights. That might work but does not scale so well — not really modular. Or you need glue code reexporting the implicits with new priorities (see above), as a last resort, if you can then put them in the right scope.
2. With @preferredTo, you need glue code as above.

So, Paul's proposal allows at least some sort of solution.

[aryairani]

Maybe this is the wrong place to ask, but why do we have different implicit priorities, again? And is there a better solution to the problem?

[propensive]

@refried In brief, for a particular scope, for a given type, there may be many implicits which can provide a value compatible with that type, i.e. picking any one would satisfy all the type constraints of the program. But the compiler needs to deterministically make a unique choice, so there are a several rules which tell the compiler to prefer one implicit over another in a certain context. These rules aren't arbitrary, but it's not always obvious to the casual user why they were specified the way they were. Sometimes they result in ambiguous implicits with the same priority, and these cases result in compilation errors.

It's usually possible for a library designer to put together a set of implicits which take advantage of the different rules to ensure they never conflict in any context. But one library designer doesn't know about all other libraries, so it's still quite possible for two or more libraries to introduce ambiguous implicits into the same scope.

Scala's solution to the problem is certainly not the One True Way. There may be other ideas which work a little bit better, but I would be surprised if someone came up with an alternative which was significantly simpler without at the same time compromising on flexibility or modularity.

[paulp]

I would be surprised if someone came up with an alternative which was significantly simpler without at the same time compromising on flexibility or modularity.

Please. First swing at a problem with a million knobs and it's already optimal? Maybe you mean nobody can implement simpler solutions because scala (in both language and implementation) is so difficult to modify without bolts popping all over the place.

[propensive]

That wasn't the first swing...

Anyway, were we to try, we'd hit problems with the language before we even started looking at the implementation...

[aryairani]

I see. It's always fun when two or more libraries provide === and I don't know how to specify which one I want, because it's not a matter of excluding a particular import unless I want to hide all the syntax, which I probably don't, and maybe it's not even imported but present as part of something I'm extending.

But even within a single library, there are some issues, right, and we get hierarchies of prioritized instances, like Functor instance < Apply instance < Applicative instance. Oh I guess it's because otherwise when we look for a Functor instance, we'd get a dozen things that qualify as Functors, and this cues the compiler to pick the most prioritized one it can invoke, instead of giving up?