Implicits, type classes, and extension methods, part 4: understanding implicits

In previous posts, we covered the most popular implicit use cases. What is left to complete the picture is the mechanics of implicits itself.

Implicit resolution

To have a complete understanding of implicits, we should understand how the compiler decides what goes into the scope and which implicit should be used.

The high-level descriptions are the following:

an implicit is a mapping from type T to a value t: T,
in order to find that value, Scala finds all definitions in scope that might fit the definition, and then takes the most specific definition,
if it cannot point to a single definition that is the most specific, a resolution fails as the implicit is ambiguous,
if it has such a definition that builds the value incrementally from other implicits, and those implicits are ambiguous, the resolution fails with a diverging implicit expansion,
of course, if there is no implicit that can match the definition, then it is not found. This includes situations in which there is a definition for your type T, but it is missing one of the implicits required to build the value.

That begs two questions: what goes into the scope?, and what does it mean for a definition to be more specific?

Implicit scope

Scala will put into the implicit scope the following definitions:

implicit definitions defined in or passed into the current scope,
implicit definitions defined in superclasses that the current trait/class/object extends,
implicit definitions imported to the current scope,
- basically anything that you can access directly (without any prefix prefix.something)
implicit definitions defined in companion objects or types related to the type $T$ $T$ you are resolving for:
- if $T$ is compound type $T_1$ with … with $T_n$ then all implicits from all companions of $T_1$ , …, $T_n$ ,
- if $T$ is a parametrized type $S[T_1, ..., T_n]$ then implicits from all companions of $S$ , $T_1$ , … $T_n$ ,
- if $T$ is a singleton type t.type then all implicits available for t,
- if $T$ is a type projection $S$ # $U$ then all implicits available for $S$ and $T$ ,
- if $T$ is a type alias then all implicits for its expansion,
- if $T$ is an abstract type, all implicits for its upper bound,
if $T$ $T$ is an implicit conversion with arguments $T_1$ $T_{1}$ , …, $T_n$ $T_{n}$ to type $U$ $U$ then all implicits from companions $T_1$ $T_{1}$ , …, $T_n$ $T_{n}$ and $U$ $U$ ,
- implicits for parts of quantified (existential or universal) and annotated types (e.g. T forSome { types }) are in implicit scope of $T$ ,
and of course $T$ ’s own companion.

As we can see, the compiler has a lot of implicits to consider for even a remotely more complex type than a non-parametric type that extends nothing. As a rule of thumb, we can assume that if $U$ is somehow used in $T$ ’s definition, its companion object will be scanned.

Without these properties, type class derivation would be much more troublesome, but probably a lot faster.

Best definition

All right, we have a potentially large set of implicit definitions, and we have to decide on just one of them. How does the compiler make that decision? The same way it decides on overloading resolution - by choosing the most specific alternative:

for each two definitions $A$ $A$ , $B$ $B$ calculate the relative weight:
- if one is as specific as the other - weight is 1, otherwise 0
- if one is a class/object being derived from the other class/object - weight is 1, otherwise 0
- sum the values
if relative weight for $(A, B)$ is greater than $(B, A)$ , then $A$ is more specific than $B$ ,
if relative weight for $(A, B)$ is smaller than $(B, A)$ , then $B$ is more specific than $A$ .

Intuitively, for one definition to be as specific as the other, if you could replace one call with the other without issue with types (for more formal definition look at the specification).

For class $C$ to be derived from $D$ , $C$ must be a subtype of $D$ , or $C$ / $D$ must be companion objects of classes such that one extends the other (again, informal definition, take a look at the specification).

Considering that we use terms as specific as and more specific than, we are actually considering a subset of a partial order and then looking for the minimum of that subset (or maximum, depending on how we define it). It makes sense as type hierarchy itself would also be a partial order.

Troublesome cases

Most of the time, such definitions result in fairly understandable behavior. There are some exceptions, though.

What if you have two definitions that are different but could be used to produce the same type? If their ranking decides that one is not more specific than the other, you’ll get an error (ambiguous implicit or diverging implicit expansion).

class A

class B[T]

object A {
  implicit val ai: B[A] = new B[A] { override def toString = "A" }
}

object B {
  implicit val bi: B[A] = new B[A] { override def toString = "B" }
}

implicitly[B[A]] // error: ambiguous implicit values

One way of handling such a situation is to declare/import the implicit manually — if it was imported from the companion, put it directly into the scope; the relative weight ranking algorithm will declare the local implicit as more specific than the one from the companion.

import A._
implicitly[B[A]].toString // "A"

That would be an issue, though, if you are working on automatic type class derivation and you want both rules to appear in the same companion object, handling different cases.

class A
object A {
  implicit val a = new A { override def toString = "A" }
}

class B
object B {
  implicit val b = new B { override def toString = "B" }
}

class C
object C {
  implicit def a2c(implicit a: A) =
    new C { override def toString = a.toString }
  implicit def b2c(implicit b: B) =
    new C { override def toString = b.toString }
}

implicitly[C] // error: ambiguous implicit values

In such a case, we might influence the relative-weight algorithm by having them defined in different classes/traits:

class C
object C extends LowPriorityImplicits {
  implicit def a2c(implicit a: A) =
    new C { override def toString = a.toString }
}

trait LowPriorityImplicits { self: C.type =>
   implicit def b2c(implicit b: B) =
    new C { override def toString = b.toString }
}

implicitly[C].toString // "A"

As a matter of fact, this is quite a popular pattern. You can find LowPriorityImplicits in scala.Predef and in virtually all more complex shapeless-based projects (e.g. the majority of Typelevel projects).

In some cases, neither of these is applicable. Often, you have some sort of cyclic dependency between implicit definitions. As the Scala compiler has trouble with such definitions at the moment, shapeless provides the Lazy macro — it defers the resolution of some dependency and thus breaks the cyclic dependency.

In future versions of Scala, Lazy should no longer be needed, as it will be replaced with by-name implicits.

Debugging hints

The last topic about implicits is how to debug them. Let’s face it: it is not easy.

Well, there is a flag -Xlog-implicits which prints some internal messages… but it generates tons of logs, as we always use tons of implicits - even if we don’t know about them. An example is CanBuildFrom type class which is used to describe if the transformation we are doing currently is allowed (e.g. turning a collection of pairs into Map). So if you are (flat)mapping collection implicits are there.

An improvement over it might be the splain compiler plugin. Its author aims to make the compiler generate better error messages about implicits, which is why the plugin creates a pretty-printed implicit derivation tree.

If we are trying to debug, e.g., type class derivation, my first idea is to run the REPL. Then import things so that your scope is possibly close to the one you are trying to fix (you might need to comment something out in order to make the project compile and run the console). Then, you have two tools at your disposal:

implicitly[T] provided by scala.Predef,
shapeless[T] from the shapeless library - it works similarly to implicitly but provides more information.

sealed trait Natural

sealed trait Zero extends Natural
object Zero extends Zero

class Succesor[N <: Natural] extends Natural

trait Add[N <: Natural, M <: Natural] {
  type Result <: Natural
}

object Add {

  implicit def zeroCase[M <: Natural]:
    Add[Zero, M] { type Result = M } = null

  implicit def succCase[N <: Natural, M <: Natural(
    implicit add: Add[N, M]
  ):
    Add[Succesor[N], M] { type Result = Succesor[add.Result] } =
     null
}

implicitly[Add[Succesor[Zero], Zero]]
// Add[Succesor[Zero], Zero] = null

import shapeless._
shapeless.the[Add[Succesor[Zero], Zero]]
// Add[Succesor[Zero], Zero]{type Result = ammonite.$sess.cmd6.Succesor[ammonite.$sess.cmd6.Zero]} = null

Another tool you should have under your belt is scala.reflect.runtime.universe.reify:

show(reify(implicitly[Add[Succesor[Zero], Succesor[Zero]]]).tree) 
// String = "Predef.implicitly[cmd7.Add[cmd6.Succesor[cmd6.Zero], cmd6.Succesor[cmd6.Zero]]](cmd7.this.Add.succCase(cmd7.this.Add.zeroCase))"

These examples should give you the general idea how these utilities work.

If I wanted to debug shapeless-generated type class I would try to:

generate Generic.Aux (maybe using some utility function to avoid passing the other type parameter myself),
check if derivation of intermediate HList or Coproduct works,
check if you are able to convert the generic version back to the specific one.

If you are terrified, that you would have to write by hand a lot of intermediate implicits, remember: you are testing derivation and resolution in REPL, not writing a production code. Usage of null.asInstanceOf[X] and ??? is perfectly fine for populating the scope with mock data.

In some cases (not many, though), an IDE can help you. IntelliJ has an option for showing implicits. By putting the cursor in the place you are interested and selecting View > Implicit Parameters (or Ctrl + Shift + P on non-Mac computers) you will be able to show from where the supplied implicit came from. As far as I remember, it is far from perfect, but it’s better than nothing.

One last thing you can do is customize error messages using @implicitNotFound and (since 2.12) @implicitAmbiguous. If you know beforehand that your trait/class requires some import or local definition, or that the enclosing class extends some trait, you can leave that information here. This way, in the future, when you forget about the assumptions, the error message can get you back on track much faster than if you had to reverse-engineer your past thinking. The same applies to colliding implicits — if you know which imports might clash, you can leave yourself a reminder in the annotation.

Summary

Implicits are a really useful mechanism without which Scala would not be the language it is today. They make it possible to automate a lot of code generation (type class derivation) and - if used properly - they can help express assumptions about your code (type bounds, implicit evidence).

However, this mechanism comes with a cost: they are hard to debug, might require in-depth knowledge about how resolution works and generate a lot of work for the compiler. As such, they might become dangerous in inexperienced programmers’ hands.

In the end, each team/project needs to weigh the pros and cons themselves, based on their own values, preferences, and limitations to answer questions like how much work they want to move to the compiler, and how much extra compile time is bearable.

If someone was looking for a compiled version of posts 1-4, it can be found here.

kubuszok.com