How does overload resolution interact with implicit conversions?

Question
#1

While developing a tiny DSL, I ran into a situation where the interaction of overload resolution and implicit conversions is limited. For example:

case class A(i: Int)
implicit def toA(i: Int) = A(i)
def f(a: A) = ???
def f(a: Seq[A]) = ???

All the following calls compile:

f(A(0))
f(Seq(A(0)))
f(0)
f(Seq[A](0))

This one, however, does not compile:

f(Seq(0))

It causes the following error message:

overloaded method f with alternatives:
  (a: Seq[A])Nothing <and>
  (a: A)Nothing
 cannot be applied to (Seq[Int])
    f(Seq(0))

I failed to find information on the role of implicit conversions in overload resolution. Is there a way to make the compiler try harder?

#2

Try with a varargs instead: Scastie - An interactive playground for Scala.

#3

@BalmungSan, I used Seq only for the purpose of presentation. In the DSL, I use a different type.

#4

As the Seq in the example seems to be misleading, I reworked the example.

This piece of code compiles:

case class A(i: Int)
case class B(a: A)
implicit def toA(i: Int) = A(i)
def f(a: A) = ???
def f(b: B) = ???
f(A(0))
f(0)
f(B(A(0)))
f(B(0))

Problems start when adding a type parameter to B:

case class A(i: Int)
case class B[T](t: T)
implicit def toA(i: Int) = A(i)
def f(a: A) = ???
def f(b: B[A]) = ???
f(A(0))
f(B(A(0)))
f(0)
f(B[A](0))
f(B(0))

This yields:

overloaded method f with alternatives:
  (b: B[A])Nothing <and>
  (a: A)Nothing
 cannot be applied to (B[Int])
    f(B(0))

The problem can be avoided by removing the first definition of f:

case class A(i: Int)
case class B[T](t: T)
implicit def toA(i: Int) = A(i)
def f(b: B[A]) = ???
f(B(A(0)))
f(B[A](0))
f(B(0))

Concluding, only when f is not overloaded, the compiler is able to transform f(B(0)) into f(B(A(0))). That’s why I asked about the interaction of overload resolution with implicit conversions.

#5

Let’s start with what B(0) means. Given the definition

case class B[T](t: T)

Then B(0) is sugar for B.apply(0). The auto-generated definition of apply is

object B {
  def apply[T](t: T): B[T] = new B[T](t)
}

However the expression B.apply(0) doesn’t specify what T is so it must be inferred. This can happen in two main ways: from the “inside-out” where T is deduced from the argument’s type, and from the “outside-in” where T is mandated by the expression in which it’s involved.

In isolation, the expression B(0) has type B[Int], because T is deduced solely from the argument. In the expression f(B(0)), however, the declared type of the parameter to f influences the deduction for T. Inference within an expression is not specified anywhere I know, but it practice it roughly proceeds left-to-right and outside-in before inside-out, which means the types mandated by the type of f's parameters are applied before the type deduced from the argument.

In the non-overloaded case you have

def f(b: B[A]) = ???

and therefore within the expression f(B(0)), the type of B(0) must be B[A], meaning B.apply[T](0): B[A], allowing the deduction that T = A, yielding the final expression B.apply[A](0)

From the implicit conversions docs:

An implicit conversion from type S to type T is defined by an implicit value which has function type S => T, or by an implicit method convertible to a value of that type.
Implicit conversions are applied in two situations:

  • If an expression e is of type S, and S does not conform to the expression’s expected type T.
  • In a selection e.m with e of type S, if the selector m does not denote a member of S.

The key is "S does not conform to the expression’s expected type T". This implies the expected type T must be known and unambiguous in order for an implicit conversion to happen.

Given B.apply[A](0), the type of 0 is Int and the expected type is A. These do not conform so an implicit search is executed, and the implicit conversion toA is found and invoked as B.apply[A](toA(0)).

In the overloaded case you have

def f(a: A) = ???
def f(b: B[A]) = ???

When resolving f(B(0)), what should the type of B(0) be? By itself it’s B[Int], but needs to be either A or B[A], yet it does not conform to either, there is no direct conversion for B[Int] to either A or B[A], and not enough other information available to choose whether A or B[A] should be used to direct inference. Therefore the expected type is not definitely known and no implicit conversion may be applied. Finally without enough type information to resolve the overloads and induce a conversion, you receive an ambiguity error.

Note the “no direct conversion” bit. If you define something like

implicit def bintToA(bi: B[Int]) = A(bi.t)

Then the compiler can figure out that B(0) with type B[Int] may be converted to A and it will resolve the first overload. You can similarly define a conversion to B[A] and resolve the other overload. And naturally supplying both would again result in an ambiguity error.

In principle the compiler could try to resolve the ambiguity by going down all potential inference paths to see if only one resolves, e.g. try both B(0): A and B(0): B[A] to find that the former cannot succeed in isolation but the latter can. However the compiler clearly does not do this right now, and arguably never should for reasons of performance and predictability as the number of overloads and types and possible conversions increases at each inference step. Better to have the ambiguity error sooner and require the code to be a bit more explicit about its intent, I think.

1 Like
#6

@jgulotta, thanks a lot for your detailed and well-written explanation!