How does the <:< operator work in Scala?

Question

In Scala there's a class <:< that witnesses a type constraint. From Predef.scala:

  sealed abstract class <:<[-From, +To] extends (From => To) with Serializable
  private[this] final val singleton_<:< = new <:<[Any,Any] { def apply(x: Any): Any = x }
  implicit def $conforms[A]: A <:< A = singleton_<:<.asInstanceOf[A <:< A]

An example of how it's used is in the toMap method of TraversableOnce:

def toMap[T, U](implicit ev: A <:< (T, U)): immutable.Map[T, U] =

What I don't understand is how this works. I understand that A <:< B is syntactically equivalent to the type <:<[A, B]. But I don't get how the compiler can find an implicit of that type if and only if A <: B. I assume that the asInstanceOf call in the definition of $conforms is making this possible somehow, but how? Also, is it significant that a singleton instance of an abstract class is used, instead of just using an object?

Answer 1

Suppose we've got the following simple type hierarchy:

trait Foo
trait Bar extends Foo

We can ask for proof that Bar extends Foo:

val ev = implicitly[Bar <:< Foo]

If we run this in a console with -Xprint:typer, we'll see the following:

private[this] val ev: <:<[Bar,Foo] =
  scala.this.Predef.implicitly[<:<[Bar,Foo]](scala.this.Predef.$conforms[Bar]);

So the compiler has picked $conforms[Bar] as the implicit value we've asked for. Of course this value has type Bar <:< Bar, but because <:< is covariant in its second type parameter, this is a subtype of Bar <:< Foo, so it fits the bill.

(There's some magic involved here in the fact that the Scala compiler knows how to find subtypes of the type it's looking for, but it's a fairly generic mechanism and isn't too surprising in its behavior.)

Now suppose we ask for proof that Bar extends String:

val ev = implicitly[Bar <:< String]

If you turn on -Xlog-implicits, you'll see this:

<console>:9: $conforms is not a valid implicit value for <:<[Bar,String] because:
hasMatchingSymbol reported error: type mismatch;
 found   : <:<[Bar,Bar]
 required: <:<[Bar,String]
       val ev = implicitly[Bar <:< String]
                          ^
<console>:9: error: Cannot prove that Bar <:< String.
       val ev = implicitly[Bar <:< String]
                          ^

The compiler tries the Bar <:< Bar again, but since Bar isn't a String, this isn't a subtype of Bar <:< String, so it's not what we need. But $conforms is the only place the compiler can get <:< instances (unless we've defined our own, which would be dangerous), so it quite properly refuses to compile this nonsense.

---

To address your second question: the <:<[-From, +To] class is necessary because we need the type parameters for this type class to be useful. The singleton Any <:< Any value could just as well be defined as an object—the decision to use a val and an anonymous class is arguably a little simpler, but it's an implementation detail that you shouldn't ever need to worry about.