Where does Scala look for implicits?

50,194

Solution 1

Types of Implicits

Implicits in Scala refers to either a value that can be passed "automatically", so to speak, or a conversion from one type to another that is made automatically.

Implicit Conversion

Speaking very briefly about the latter type, if one calls a method m on an object o of a class C, and that class does not support method m, then Scala will look for an implicit conversion from C to something that does support m. A simple example would be the method map on String:

"abc".map(_.toInt)

String does not support the method map, but StringOps does, and there's an implicit conversion from String to StringOps available (see implicit def augmentString on Predef).

Implicit Parameters

The other kind of implicit is the implicit parameter. These are passed to method calls like any other parameter, but the compiler tries to fill them in automatically. If it can't, it will complain. One can pass these parameters explicitly, which is how one uses breakOut, for example (see question about breakOut, on a day you are feeling up for a challenge).

In this case, one has to declare the need for an implicit, such as the foo method declaration:

def foo[T](t: T)(implicit integral: Integral[T]) {println(integral)}

View Bounds

There's one situation where an implicit is both an implicit conversion and an implicit parameter. For example:

def getIndex[T, CC](seq: CC, value: T)(implicit conv: CC => Seq[T]) = seq.indexOf(value)

getIndex("abc", 'a')

The method getIndex can receive any object, as long as there is an implicit conversion available from its class to Seq[T]. Because of that, I can pass a String to getIndex, and it will work.

Behind the scenes, the compiler changes seq.IndexOf(value) to conv(seq).indexOf(value).

This is so useful that there is syntactic sugar to write them. Using this syntactic sugar, getIndex can be defined like this:

def getIndex[T, CC <% Seq[T]](seq: CC, value: T) = seq.indexOf(value)

This syntactic sugar is described as a view bound, akin to an upper bound (CC <: Seq[Int]) or a lower bound (T >: Null).

Context Bounds

Another common pattern in implicit parameters is the type class pattern. This pattern enables the provision of common interfaces to classes which did not declare them. It can both serve as a bridge pattern -- gaining separation of concerns -- and as an adapter pattern.

The Integral class you mentioned is a classic example of type class pattern. Another example on Scala's standard library is Ordering. There's a library that makes heavy use of this pattern, called Scalaz.

This is an example of its use:

def sum[T](list: List[T])(implicit integral: Integral[T]): T = {
    import integral._   // get the implicits in question into scope
    list.foldLeft(integral.zero)(_ + _)
}

There is also syntactic sugar for it, called a context bound, which is made less useful by the need to refer to the implicit. A straight conversion of that method looks like this:

def sum[T : Integral](list: List[T]): T = {
    val integral = implicitly[Integral[T]]
    import integral._   // get the implicits in question into scope
    list.foldLeft(integral.zero)(_ + _)
}

Context bounds are more useful when you just need to pass them to other methods that use them. For example, the method sorted on Seq needs an implicit Ordering. To create a method reverseSort, one could write:

def reverseSort[T : Ordering](seq: Seq[T]) = seq.sorted.reverse

Because Ordering[T] was implicitly passed to reverseSort, it can then pass it implicitly to sorted.

Where do Implicits come from?

When the compiler sees the need for an implicit, either because you are calling a method which does not exist on the object's class, or because you are calling a method that requires an implicit parameter, it will search for an implicit that will fit the need.

This search obey certain rules that define which implicits are visible and which are not. The following table showing where the compiler will search for implicits was taken from an excellent presentation (timestamp 20:20) about implicits by Josh Suereth, which I heartily recommend to anyone wanting to improve their Scala knowledge. It has been complemented since then with feedback and updates.

The implicits available under number 1 below has precedence over the ones under number 2. Other than that, if there are several eligible arguments which match the implicit parameter’s type, a most specific one will be chosen using the rules of static overloading resolution (see Scala Specification §6.26.3). More detailed information can be found in a question I link to at the end of this answer.

  1. First look in current scope
    • Implicits defined in current scope
    • Explicit imports
    • wildcard imports
    • Same scope in other files
  2. Now look at associated types in
    • Companion objects of a type
    • Implicit scope of an argument's type (2.9.1)
    • Implicit scope of type arguments (2.8.0)
    • Outer objects for nested types
    • Other dimensions

Let's give some examples for them:

Implicits Defined in Current Scope

implicit val n: Int = 5
def add(x: Int)(implicit y: Int) = x + y
add(5) // takes n from the current scope

Explicit Imports

import scala.collection.JavaConversions.mapAsScalaMap
def env = System.getenv() // Java map
val term = env("TERM")    // implicit conversion from Java Map to Scala Map

Wildcard Imports

def sum[T : Integral](list: List[T]): T = {
    val integral = implicitly[Integral[T]]
    import integral._   // get the implicits in question into scope
    list.foldLeft(integral.zero)(_ + _)
}

Same Scope in Other Files

Edit: It seems this does not have a different precedence. If you have some example that demonstrates a precedence distinction, please make a comment. Otherwise, don't rely on this one.

This is like the first example, but assuming the implicit definition is in a different file than its usage. See also how package objects might be used in to bring in implicits.

Companion Objects of a Type

There are two object companions of note here. First, the object companion of the "source" type is looked into. For instance, inside the object Option there is an implicit conversion to Iterable, so one can call Iterable methods on Option, or pass Option to something expecting an Iterable. For example:

for {
    x <- List(1, 2, 3)
    y <- Some('x')
} yield (x, y)

That expression is translated by the compiler to

List(1, 2, 3).flatMap(x => Some('x').map(y => (x, y)))

However, List.flatMap expects a TraversableOnce, which Option is not. The compiler then looks inside Option's object companion and finds the conversion to Iterable, which is a TraversableOnce, making this expression correct.

Second, the companion object of the expected type:

List(1, 2, 3).sorted

The method sorted takes an implicit Ordering. In this case, it looks inside the object Ordering, companion to the class Ordering, and finds an implicit Ordering[Int] there.

Note that companion objects of super classes are also looked into. For example:

class A(val n: Int)
object A { 
    implicit def str(a: A) = "A: %d" format a.n
}
class B(val x: Int, y: Int) extends A(y)
val b = new B(5, 2)
val s: String = b  // s == "A: 2"

This is how Scala found the implicit Numeric[Int] and Numeric[Long] in your question, by the way, as they are found inside Numeric, not Integral.

Implicit Scope of an Argument's Type

If you have a method with an argument type A, then the implicit scope of type A will also be considered. By "implicit scope" I mean that all these rules will be applied recursively -- for example, the companion object of A will be searched for implicits, as per the rule above.

Note that this does not mean the implicit scope of A will be searched for conversions of that parameter, but of the whole expression. For example:

class A(val n: Int) {
  def +(other: A) = new A(n + other.n)
}
object A {
  implicit def fromInt(n: Int) = new A(n)
}

// This becomes possible:
1 + new A(1)
// because it is converted into this:
A.fromInt(1) + new A(1)

This is available since Scala 2.9.1.

Implicit Scope of Type Arguments

This is required to make the type class pattern really work. Consider Ordering, for instance: It comes with some implicits in its companion object, but you can't add stuff to it. So how can you make an Ordering for your own class that is automatically found?

Let's start with the implementation:

class A(val n: Int)
object A {
    implicit val ord = new Ordering[A] {
        def compare(x: A, y: A) = implicitly[Ordering[Int]].compare(x.n, y.n)
    }
}

So, consider what happens when you call

List(new A(5), new A(2)).sorted

As we saw, the method sorted expects an Ordering[A] (actually, it expects an Ordering[B], where B >: A). There isn't any such thing inside Ordering, and there is no "source" type on which to look. Obviously, it is finding it inside A, which is a type argument of Ordering.

This is also how various collection methods expecting CanBuildFrom work: the implicits are found inside companion objects to the type parameters of CanBuildFrom.

Note: Ordering is defined as trait Ordering[T], where T is a type parameter. Previously, I said that Scala looked inside type parameters, which doesn't make much sense. The implicit looked for above is Ordering[A], where A is an actual type, not type parameter: it is a type argument to Ordering. See section 7.2 of the Scala specification.

This is available since Scala 2.8.0.

Outer Objects for Nested Types

I haven't actually seen examples of this. I'd be grateful if someone could share one. The principle is simple:

class A(val n: Int) {
  class B(val m: Int) { require(m < n) }
}
object A {
  implicit def bToString(b: A#B) = "B: %d" format b.m
}
val a = new A(5)
val b = new a.B(3)
val s: String = b  // s == "B: 3"

Other Dimensions

I'm pretty sure this was a joke, but this answer might not be up-to-date. So don't take this question as being the final arbiter of what is happening, and if you do noticed it has gotten out-of-date, please inform me so that I can fix it.

EDIT

Related questions of interest:

Solution 2

I wanted to find out the precedence of the implicit parameter resolution, not just where it looks for, so I wrote a blog post revisiting implicits without import tax (and implicit parameter precedence again after some feedback).

Here's the list:

  • 1) implicits visible to current invocation scope via local declaration, imports, outer scope, inheritance, package object that are accessible without prefix.
  • 2) implicit scope, which contains all sort of companion objects and package object that bear some relation to the implicit's type which we search for (i.e. package object of the type, companion object of the type itself, of its type constructor if any, of its parameters if any, and also of its supertype and supertraits).

If at either stage we find more than one implicit, static overloading rule is used to resolve it.

Share:
50,194
Daniel C. Sobral
Author by

Daniel C. Sobral

I have been programming for more than 20 years now, starting with 8 bits computers, assembler and BASIC. My passion for languages meant that, by the time I entered college, I had already programmed for fun or profit in more than 20 languages, including odd ones like Forth, MUMPS and APL, as well as theoretically important ones like Lisp and Prolog. Some of my code ended up in FreeBSD, of which I was a committer for some years, while I got my masters degree in the field of distributed algorithms. I also contributed to Scala, with small amounts of code, some reasonable amount of documentation, and a couple of years of a lot of attention to the Scala questions on Stack Overflow.

Updated on July 08, 2022

Comments

  • Daniel C. Sobral
    Daniel C. Sobral almost 2 years

    An implicit question to newcomers to Scala seems to be: where does the compiler look for implicits? I mean implicit because the question never seems to get fully formed, as if there weren't words for it. :-) For example, where do the values for integral below come from?

    scala> import scala.math._
    import scala.math._
    
    scala> def foo[T](t: T)(implicit integral: Integral[T]) {println(integral)}
    foo: [T](t: T)(implicit integral: scala.math.Integral[T])Unit
    
    scala> foo(0)
    scala.math.Numeric$IntIsIntegral$@3dbea611
    
    scala> foo(0L)
    scala.math.Numeric$LongIsIntegral$@48c610af
    

    Another question that does follow up to those who decide to learn the answer to the first question is how does the compiler choose which implicit to use, in certain situations of apparent ambiguity (but that compile anyway)?

    For instance, scala.Predef defines two conversions from String: one to WrappedString and another to StringOps. Both classes, however, share a lot of methods, so why doesn't Scala complain about ambiguity when, say, calling map?

    Note: this question was inspired by this other question, in the hopes of stating the problem in a more general manner. The example was copied from there, because it is referred to in the answer.

  • pedrofurla
    pedrofurla about 13 years
    It's time for you to start using your answers in a book, by now it's only a matter of put it all together.
  • Daniel C. Sobral
    Daniel C. Sobral about 13 years
    @pedrofurla I have been considered writing a book in portuguese. If someone can find me a contact with a technical publisher...
  • pedrofurla
    pedrofurla about 13 years
    @Daniel, I know. And I also volunteered to review it :)
  • retronym
    retronym about 13 years
    The package objects of the companions of the parts of the type are also searched. lampsvn.epfl.ch/trac/scala/ticket/4427
  • Daniel C. Sobral
    Daniel C. Sobral about 13 years
    @retronym IMHO, things defined in the package object are "current scope" for other stuff in the package, so they'd be handled either as current scope in the same file or as same scope, different file, as the case may be.
  • retronym
    retronym about 13 years
    In this case, it's part of the implicit scope. The call site need not be within that package. That was surprising to me.
  • Kipton Barros
    Kipton Barros almost 13 years
    Nice list of sources for implicits. How is ambiguity resolved? You listed 8 sources (1.1, 1.2, ... 2.4). Are implicits shadowed in this order, with 1.1 taking highest priority?
  • Daniel C. Sobral
    Daniel C. Sobral almost 13 years
    @Kipton 7, actually. They 8th is a joke. Yes, these source are ordered by priority. Within a category, there's ambiguity, except in the case of inheritance. An inherited implicit has lower precedence than one not inherited.
  • retronym
    retronym over 12 years
    One more place to look: stackoverflow.com/questions/7647835/…
  • Daniel C. Sobral
    Daniel C. Sobral over 12 years
    @retronym Thank you, I missed that one! Updated.
  • Daniel C. Sobral
    Daniel C. Sobral over 12 years
    This could be improved if you wrote some code just defining packages, objects, traits and classes, and using their letters when you refer to the scope. No need to put any method declaration at all -- just names and who extends whom, and in which scope.
  • Eugene Yokota
    Eugene Yokota over 12 years
    The current scope also includes implicit parameters of the current method, outer blocks, inherited implicits, and implicits made available by package object. The only precedence among the current scope is locally defined one vs the rest in 2.9.1, but it's a bug. After 2.10, all of them within current scope have the same precedence. The same goes for implicit scope. When there are more than one candidate, static overloading rule is used, which means the implicits defined in an object wins over implicits defined in its supertrait etc.
  • Daniel C. Sobral
    Daniel C. Sobral over 12 years
    @EugeneYokota I'd rather "outsource" the whole issue of implicit resolution precedence. Would you mind asking/answering that question? You have tons of material already from your blog. :-) Also, it would be a nice additions to the FAQ at the doc site.
  • Eugene Yokota
    Eugene Yokota over 12 years
    Yea, so stackoverflow.com/questions/8623055 covers that specifically, but I noticed you wrote "The following list is intended to be presented in precedence order ... please report." Basically, the inner lists should be unordered since they all have equal weight (at least in 2.10).
  • lcn
    lcn about 10 years
    @DanielC.Sobral, I found the "Second, the companion object of the expected type" saying very misleading. Both Joshua Suereth (on page 102 of Scala in Depth) and Martin Odersky (eed3si9n.com/…) say the search happens only for the source type. In the example you gave, List(1, 2, 3).sorted, the search of an Ordering[T] has nothing to do with expected type. The Ordering[T] here is just a comparator, which is a function.
  • Daniel C. Sobral
    Daniel C. Sobral about 10 years
    @lcn Your last sentence is irrelevant -- comparator and function have nothing to do with it. It needs an implicit of type Ordering[T]. Where should it look for it, and why? There's no method being called on an object of the type Ordering[T], so source type does not apply. Explain from there.
  • lcn
    lcn about 10 years
    @DanielC.Sobral, Yes, I shall have limited my previous comment to implicit conversions when talking about the search. Yet as for implicit parameters, which your List.ordered example falls into, there is neither a source type nor an expected type. Though the " implicit object Int extends IntOrdering" is defined in the "Ordering" object, the search for such an implicit is not initiated by an expected type, even though Ordering serves here as the expected type of Int. So using it as an example for illustrating search in "the companion object of the expected type" is still inappropriate.
  • Daniel C. Sobral
    Daniel C. Sobral about 10 years
    @lcn If you cannot provide an explanation of how IntOrdering inside object Ordering is found, then you must assume you are wrong. Not me, you must assume so. As it happens, the sources you cite contradict you. Odersky said we look in the "implicit scope", which contains all sort of companion objects that bear some relation to the type which we search for -- "type which we search for" is the expected type. Josh says on 5.1.3 "implicit scope of the type it's looking for" -- again, expected type. Or consider this commit's second paragraph.
  • lcn
    lcn about 10 years
    @DanielC.Sobral, I guess our disagreement is about the concept "expected type". To locate the implicit definition of an implicit parameter, the compiler does have to find in the companion object of that parameter's type, which does be an expected type. But this situation has to be distinguished from the case for implicit conversion, "implicit def int2bigInt(i: Int): BigInt", which is defined in the BigInt companian object instead of in Int object, the source type. This in my opinion is the real case for implicit search in an expected type.
  • Daniel C. Sobral
    Daniel C. Sobral about 10 years
    @lcn There's no need to distinguish between these cases, because they are the same wrt to where the implicit is found.
  • Paul Draper
    Paul Draper over 9 years
    Your 1 + new A(1) example does not work. (2.11.4): "overloaded method value + with alternatives...cannot be applied to (A)"
  • Daniel C. Sobral
    Daniel C. Sobral over 9 years
    @PaulDraper I just tested on 2.11.4, and it worked. It also certainly worked back on whatever version I original used at the time I wrote this. What version are you using, and are you sure you don't have other implicits defined? These examples are not supposed to be used together, for one thing.
  • ievgen.garkusha
    ievgen.garkusha over 7 years
    another simple example for "outer objects for nested types": objectOuter{ trait Nested implicit val i: Nested = new Nested{} } implicitly[Outer.Nested]
  • metasim
    metasim about 7 years
    Unfortunately, the link to @jsuereth 's presentation is now blocked.
  • dade
    dade about 7 years
    The 1 + new A(1) seems to work for the wrong reason. I changed + to +++ and expected it to work: ` class A(val n: Int) { def +++(other: A) = new A(n + other.n) } object A { implicit def fromInt(n: Int) = new A(n) } ` but got this: ` // This becomes possible: 1.+++(new A(1)) // compile error A.fromInt(1) +++ new A(1) // this works `
  • steinybot
    steinybot over 6 years
    "Same Scope in Other Files" is a little unclear. I expected package objects from parent packages of the current scope to be searched but they are not. It is actually the package objects for the type that is searched. @retronym hints at this. x.implicitFoo will only search the scope of x and not the scope of where it is used. (see gist for an example)[gist.github.com/steinybot/121d24730edda4d815918c08b‌​7d64a46]
  • Julian A.
    Julian A. over 4 years
    @DanielC.Sobral Can you explain more what you mean by “ this does not mean the implicit scope of A will be searched for conversions of that parameter, but of the whole expression”? What is the “whole expression”? Thanks.
  • Daniel C. Sobral
    Daniel C. Sobral over 4 years
    @JulianA. See the example that follows: 1 + new A(1). Here, the + method on the A class takes and A, so there's no implicit conversion happening for the parameter itself, but because the parameter is of type A, then the implicit scope for A is applied to other elements of the expression, once the initial look up fails, which is why the object on which the + method is called gets an implicit conversion.
  • soMuchToLearnAndShare
    soMuchToLearnAndShare over 3 years
    Where does implicit class fit into the types you mentioned here? The scala doc did not say much, only says “make” the primary constructor available for type conversion , but didn’t give examples . docs.scala-lang.org/overviews/core/implicit-classes.html
  • Daniel C. Sobral
    Daniel C. Sobral over 3 years
    @soMuchToLearn It doesn't. They didn't exist at the time, and since they are being replaced on Scala 3 I'm not sure it's worth adding them to the answer, though I would not object if someone else edited the answer to add them.
  • mert inan
    mert inan over 2 years
    I had to vote this up