An exploration of implicit conflict resolution

[nuttycom]

After revisiting the "contrainvariance" thread today and some discussion with Daniel Spiewak, I decided to play around a bit with implicit resolution, and found some behavior that surprised me a little. It probably won't surprise a lot of people, but it did me even after all this time. A REPL session follows:

scala> class A

defined class A

scala> class B extends A

defined class B

scala> class C extends A

defined class C

scala> :paste

// Entering paste mode (ctrl-D to finish)

class Foo[+A]

implicit val fooa = new Foo[A]

implicitly[Foo[A]]

// Exiting paste mode, now interpreting.

defined class Foo

fooa: Foo[A] = Foo@72a5ce92

res0: Foo[A] = Foo@72a5ce92

... okay, this is exactly what I expect. So far, so good.

scala> :paste

// Entering paste mode (ctrl-D to finish)

implicit val fooa = new Foo[A]

implicit val foob = new Foo[B]

implicitly[Foo[A]]

// Exiting paste mode, now interpreting.

fooa: Foo[A] = Foo@670064a4

foob: Foo[B] = Foo@4acf7fd0

res1: Foo[A] = Foo@4acf7fd0

... Interesting. I asked for a Foo[A], and it gave me a Foo[B] because that's the most specific, or narrowest-typed thing that the compiler could find that satisfied the signature. I had kind of expected this to be ambiguous though. After all, I asked for a Foo[A] and there are two valid implicits satisfying that signature.

scala> :paste

// Entering paste mode (ctrl-D to finish)

implicit val fooa = new Foo[A]

implicit val foob = new Foo[B]

implicit val fooc = new Foo[C]

implicitly[Foo[A]]

// Exiting paste mode, now interpreting.

<console>:21: error: ambiguous implicit values:

 both value fooc in object $iw of type => Foo[C]

 and value foob in object $iw of type => Foo[B]

 match expected type Foo[A]

              implicitly[Foo[A]]

                        ^

... If this is ambiguous, as expected, why was the former not so? In both cases, you have more than one implicit in scope that can satisfy the signature, but here because there's more than one "most specific"-typed implicit available, it complains of ambiguity. Further exploration shows that contravariance is treated in exactly the same fashion; the compiler does not complain of ambiguity so long as the hierarchy of implicits in scope is a tree with only one branch.

scala> trait X

defined trait X

scala> trait Y

defined trait Y

scala> trait Z extends X with Y

defined trait Z

scala> :paste

// Entering paste mode (ctrl-D to finish)

class Bar[-A]

implicit val barz = new Bar[Z]

implicitly[Bar[Z]]

// Exiting paste mode, now interpreting.

defined class Bar

barz: Bar[Z] = Bar@65f102c1

res3: Bar[Z] = Bar@65f102c1

scala> :paste

// Entering paste mode (ctrl-D to finish)

implicit val barx = new Bar[X]

implicit val barz = new Bar[Z]

implicitly[Bar[Z]]

// Exiting paste mode, now interpreting.

barx: Bar[X] = Bar@73d742a1

barz: Bar[Z] = Bar@39579371

res4: Bar[Z] = Bar@73d742a1

scala> :paste

// Entering paste mode (ctrl-D to finish)

implicit val barx = new Bar[X]

implicit val bary = new Bar[Y]

implicit val barz = new Bar[Z]

implicitly[Bar[Z]]

// Exiting paste mode, now interpreting.

<console>:27: error: ambiguous implicit values:

 both value barx in object $iw of type => Bar[X]

 and value bary in object $iw of type => Bar[Y]

 match expected type Bar[Z]

              implicitly[Bar[Z]]

 

... Well, at least this is consistent with what we've seen before in the case of covariance. But it puzzles me that implicit search doesn't consider the 2-valid-implicits-in scope cases to be ambiguous, while the 3-in-scope cases are so. After all, naively it seems that there would be a rational choice in each ambiguous case; that being the fooa and barz implicits, which don't even appear to be considered in the search if there is any implicit for a subtype available. And, this seems to me to be the issue with contravariant typeclasses like Ordering; it's not that the compiler *couldn't* find the correct implicit if it were the only one in scope, it's that it will actively seek out the "wrong" one (wrong from the perspective of the user, at least.) So, could a solution be to make the rules surrounding ambiguity stronger, so that the 2-valid-implicits cases are also rejected as ambiguous?

Thanks,

Kris

[Daniel Spiewak]

I think the main concern I would have with treating "multiple valid implicits along a linear subsumption path" as ambiguous is the question of whether this disrupts anything we're doing with CanBuildFrom.  I think everything happening with CanBuildFrom is otherwise disambiguated by container or scope, but I'm not sure off the top of my head.

It does seem extremely odd to me that the cases Kris listed are not errors.

Daniel

[nuttycom]

As an addendum, in response to a suggestion from Paul, this behavior also reproduces outside of the REPL:

Nope, this reproduces just fine:

[nuttycom@yggdrasil scala]$ cat TestImplicits.scala 

class A

class B extends A

class C extends A

class Foo[+A]

object FooImplicits1 {

  implicit val fooa = new Foo[A]

  def foo = implicitly[Foo[A]]

}

object FooImplicits2 {

  implicit val fooa = new Foo[A]

  implicit val foob = new Foo[B]

  def foo = implicitly[Foo[A]]

}

/*

object FooImplicits3 {

  implicit val fooa = new Foo[A]

  implicit val foob = new Foo[B]

  implicit val fooc = new Foo[C]

  def foo = implicitly[Foo[A]]

}

*/

trait X

trait Y

trait Z extends X with Y

class Bar[-A]

object BarImplicits1 {

  implicit val barz = new Bar[Z]

  def bar = implicitly[Bar[Z]]

}

object BarImplicits2 {

  implicit val barx = new Bar[X]

  implicit val barz = new Bar[Z]

  def bar = implicitly[Bar[Z]]

}

/*

object BarImplicits3 {

  implicit val barx = new Bar[X]

  implicit val bary = new Bar[Y]

  implicit val barz = new Bar[Z]

  def bar = implicitly[Bar[Z]]

}

*/

object Test extends App {

  println("fooa: " + FooImplicits1.fooa)

  println("foo:  " + FooImplicits1.foo)

  println("")

  println("fooa: " + FooImplicits2.fooa)

  println("foob: " + FooImplicits2.foob)

  println("foo:  " + FooImplicits1.foo)

  println("")

  println("barz: " + BarImplicits1.barz)

  println("bar:  " + BarImplicits1.bar)

  println("")

  println("barx: " + BarImplicits2.barx)

  println("barz: " + BarImplicits2.barz)

  println("bar:  " + BarImplicits2.bar)

}

[nuttycom@yggdrasil scala]$ scalac TestImplicits.scala 

[nuttycom@yggdrasil scala]$ scala Test

fooa: Foo@144aa0ce

foo:  Foo@144aa0ce

fooa: Foo@311671b2

foob: Foo@3882764b

foo:  Foo@144aa0ce

barz: Bar@6860991f

bar:  Bar@6860991f

barx: Bar@2345f0e3

barz: Bar@44c9d92c

bar:  Bar@2345f0e3

Did I make any mistakes?

Kris

On Wednesday, September 5, 2012 10:50:08 PM UTC-6, nuttycom wrote:

[nuttycom]

Oops, yes: But a trivial one, and it still reproduces:

Correction to TestImplicits.scala:

object Test extends App {

  println("fooa: " + FooImplicits1.fooa)

  println("foo:  " + FooImplicits1.foo)

  println("")

  println("fooa: " + FooImplicits2.fooa)

  println("foob: " + FooImplicits2.foob)

  println("foo:  " + FooImplicits2.foo)

  println("")

  println("barz: " + BarImplicits1.barz)

  println("bar:  " + BarImplicits1.bar)

  println("")

  println("barx: " + BarImplicits2.barx)

  println("barz: " + BarImplicits2.barz)

  println("bar:  " + BarImplicits2.bar)

}

nuttycom@yggdrasil scala]$ scalac TestImplicits.scala 

[nuttycom@yggdrasil scala]$ scala Test

fooa: Foo@144aa0ce

foo:  Foo@144aa0ce

fooa: Foo@311671b2

foob: Foo@3882764b

foo:  Foo@3882764b

barz: Bar@6860991f

bar:  Bar@6860991f

barx: Bar@2345f0e3

barz: Bar@44c9d92c

bar:  Bar@2345f0e3

[Jason Zaugg]

foob and fooc each individually beat fooa (based on
Infer#isStrictlyMoreSpecific). But when these two are left in the
running, they can't be split, and the ambiguity is reported.

-jason

[nuttycom]

On Thursday, September 6, 2012 1:55:55 PM UTC-6, Jason Zaugg wrote:

> ... If this is ambiguous, as expected, why was the former not so? In both
> cases, you have more than one implicit in scope that can satisfy the
> signature, but here because there's more than one "most specific"-typed
> implicit available, it complains of ambiguity. Further exploration shows
> that contravariance is treated in exactly the same fashion; the compiler
> does not complain of ambiguity so long as the hierarchy of implicits in
> scope is a tree with only one branch.

foob and fooc each individually beat fooa (based on
Infer#isStrictlyMoreSpecific). But when these two are left in the
running, they can't be split, and the ambiguity is reported.

-jason

Well, I can see what's happening, but the question is really why this behavior is desirable. 

[nuttycom]

(that is, desirable as opposed to being given an ambiguous implicits error in the 2-implicit cases)