Search code examples
scalaimplicits

How does the Scala compiler synthesize implicit evidence with `<:<`?

Given this (admittedly contrived) code fragment in Scala:

object Main extends App {

  class X { def foo = 1 }

  def f[A](value: A)(implicit ev: A <:< X) = { value.foo }

  println(f(new X()))

}

What does the Scala compiler do to make this pass? I have looked at some code in Predef but I don't understand the implementation. Please give a detailed step by step explanation.

Solution

  • Callsite

    Let's look at what the type inferencer does when you write:

    f(new X())

    It first has to figure out, what the template parameter A of f is. Type inference in Scala goes left to right in argument lists, so trivially (given new X is of type X), we get

    f[X](new X)

    Now the compiler needs to find an implicit value of type X <:< X (remember, A got resolved to X).

    To find implicit values, the compiler looks in various places, amongst others your current scope (in which Predef._ is imported).

    The compiler then finds Predef.$conforms:

    implicit def $conforms[A]: A <:< A = // some implementation

    So this can be used to produce a X <:< X, by invoking it with X as parameter:

    f[X](new X)(Predef.$conforms[X])

    The actual implementation of $conforms does not matter as far as the type checker is concerned.

    Method Implementation

    Now lets look at the implementation:

     def f[A](value: A)(implicit ev: A <:< X) = { value.foo }

    Value is of type A (so something unknown). You want to call foo on value. Since foo is not defined on A, the compiler is looking for an implicit function (or method) that converts A into something that has a foo.

    There is such a thing in scope: ev (A <:< B extends A => B).

    Therefore, the compiler inserts an implicit conversion using ev:

    ev(value).foo

    Small Note About Variance

    As you might have noticed, <:< is variant in its parameters: <:<[-From, +To]. This can be used to generate actual subtyping evidences. Consider:

    class A
class B extends A

val ev1: A <:< A = conforms
val ev2: B <:< A = ev1 // makes sense, works because of variance

// Also
val ev3: B <:< B = conforms
val ev4: B <:< A = ev3 // makes sense, works because of variance

    This is notably the reason, why there is no need for a conforms method with two type parameters. Further, note that this behavior is specifically not wanted for =:= (since this is type equivalence), so it is invariant.