Sunday, December 03, 2017

Implicit Scope and Implicit Resolution in Scala

Having a good understanding of implicits is necessary to fully appreciating how the type-class pattern is encoded in Scala.

This is because implicit is one of the core language features of Scala that makes it possible to encode the type-class pattern.

This post would, therefore, explore implicit in Scala with a focus on implicit resolution. It is the second post in the Type class knowledge pack series.


Understanding Implicits

There were two broad things that left me confounded with Implicits in Scala when I first encountered them.

First, was understanding exactly what they are and the best way to think about them. The second confounding thing was how implicits are resolved.

How the scala compiler gets hold of an implicit value when needed. It seemed as if some black magic happens and viola, an Implicit value is retrieved by the compiler.

The whole process seemed shrouded in mystery and made it difficult to be able to think properly about what is going on when implicits are involved.

Especially since it appeared that the location where an implicit is defined will affect how it is resolved. Sometimes implicits are defined within a class, sometimes within a companion objects, sometimes within a trait. But it was not exactly clear how these locations affect resolution.

In Understanding Implicits In Scala, I addressed the first aspect of my confusion by capturing in that blog post my understanding of how implicits work in general, what they do and how to reason about them.

This post will focus on the second confusing point: How implicits are resolved and used. It will capture my understanding thus far about how to reason about the process of implicit resolution.

It is quite true that the rules that govern implicit resolution are quite involved, and the process I describe in this post can be seen as a simplified model of what actually goes on. but for all practical purposes, this simplification has proven to be elucidating for me when reasoning about Implicits. If you are interested in exploring a more elaborate take on the topic of Implicit resolution, I recommend revisiting implicits without import tax.

I will thus go ahead to explain the simplified mental model that has enabled me to understand implicit resolution just a little bit more.

Seeing Implicit resolution as Function Calls and Understanding The Implicit Scope.

Two key things helped in getting a better understanding of how implicits are resolved. First one was to view the implicit resolution process as a Function call. The second was to understand the relationship between the type signature of the imagined function call and the implicit scopes and resolution.

Let us look at the first one, which is modeling the implicits as function calls

Implicit as a function call

We can roughly summarize the job implicit do as one of converting one type to another whenever a subset of compiler error is encountered, with the intention that the compilation error is prevented with the type conversion.

One can thus view this type conversion as an application of a function that can take a GivenType to produce a RequiredType that would prevent the compilation error.

And the kind of function that gets applied depends on the type conversion that needs to take place. As mentioned in Understanding Implicits In Scala there are a couple of type conversions that take place when implicits kick in.

From that post we see that broadly speaking, this process of converting from one type to another takes place when two categories of compilation errors are about to occur:

  1. Compilation errors due to missing function parameters
  2. Compilation errors due to Type mismatch
The implicit that kicks in, in the case of missing function parameters is often referred to as implicit parameter while the one due to type mismatch is called implicit conversation.

Let us explore these two implicit type/scenario further using the function call metaphor.

The Compilation errors that occur due to missing function parameters is a case where a function is defined to be called with certain arguments but is called without providing the required argument.

def whatIsTheAnswer(implicit ans:Int): Unit = {
  println(
  if (ans == 42) 
    s"Yes. 42 is the answer to Life, Universe, and Everything"
  else
    s"Nope. $ans is not the answer"
  )
}

// calling the method
whatIsTheAnswer //missing argument

This would lead to an error:

Error:(33, 2) missing arguments for method whatIsTheAnswer in class A$A122;
follow this method with `_' if you want to treat it as a partially applied function
whatIsTheAnswer
^

The second class of compilation errors, that is, Compilation errors due to Type mismatch can be further divided into 2 kinds:

The first kind is when the compiler expects a particular type, but another was given.

case class CustomInt(value:Int)
val answerToLifeUniverseAndEverything:Int = CustomInt(42)

The variable answerToLifeUniverseAndEverything is defined as an Int, but a value of CustomInt is given. This would lead to a compilation error:

Error:(102, 189) type mismatch;
 found   : A$A21.this.CustomInt
 required: Int
def get$$instance$$answerToLifeUniverseAndEverything = answerToLifeUniverseAndEverything;/* ###worksheet### generated $$end$$ */ lazy val answerToLifeUniverseAndEverything:Int = CustomInt(42)


The second type is when a method is called on a type, but the method is not defined on that type.

class AnswerToAll {
  def answer = {
    "The answer to Life, Universe, and Everything is 42"
  }
}

// calling getAnswer which is not a defined method
print((new AnswerToAll).getAnswer) 

causes a compilation error:

Error:(33, 26) value getAnswer is not a member of A$A85.this.AnswerToAll
print((new AnswerToAll).getAnswer)
^

Signature of Function call

So we have reiterated the various compiler error/scenarios where an implicit resolution can kick in.

As suggested, if we look at the process of implicit as a function call where a GivenType is converted to a RequiredType, then the specific type signature of such a function can then be further explored as it depends on the kind of type error that needs to be prevented.

What would the function signatures for these various scenarios look like?

Note, this whole function call model is just a metaphor, and I do not think the function signature mentioned below actually exist in this format in the bowers of Scala compiler.

So let’s go ahead and imagine how the function signature would look like:

Missing parameters scenario
With the missing parameters scenario, the implicit resolution that takes place can be seen as a search for a function that takes nothing but can produce the RequiredType.

Thus a function of type:

ImplicitValue: Unit => RequiredType.

Mismatch Type scenario
With the Type mismatch scenario, the implicit resolution that takes place depends on the kind of Type mismatch.

In the case where a particular type was required, but another was given, the function that is applied to prevent this compilation error can be seen as one that takes the GivenType and returns the RequiredType.

Thus a function of type:

ImplicitValue: GivenType => RequiredType.

And in the case where a method not defined on a type is called, the function that is applied to prevent the compilation error can be seen as one that takes the GivenType on which the method is called and can produce any kind of type, no matter what, as long as the produced type has the missing method defined on it.

Thus a function of type:

ImplicitValue: GivenType => ??? 

Note that ??? is not a scala syntax. It is just a placeholder which means we do not know the exact type, but ??? is acceptable as long as ??? has the missing method defined.

In this scenario, we cannot say exactly what the expected type should be, except for the fact that is must be a type with the needed method defined on it.

Let see some code to demonstrate the function signature metaphor further:

The following code:
def whatIsTheAnswer(implicit ans:Int): Unit = {
  println(
  if (ans == 42) 
    s"Yes. 42 is the answer to Life, Universe, and Everything"
  else
    s"Nope. $ans is not the answer"
  )
}

// calling the method
whatIsTheAnswer

Would require the following function call to resolve:

ImplicitValue: Function1[Unit, Int]

Which is more or less the type signature of the implicit value that needs to be in scope in this scenario...that is implicit val answer = 42 a value that from nothing, materializes a value of type Int.

Let us move on to the case where the wrong type is assigned to a variable. For example the following code:

case class CustomInt(value:Int)
val answerToLifeUniverseAndEverything:Int = CustomInt(42)

The variable above is defined as an Int, but a CustomInt value was given. This would lead to a compilation error:

Error:(102, 189) type mismatch;
 found   : A$A21.this.CustomInt
 required: Int
def get$$instance$$answerToLifeUniverseAndEverything = answerToLifeUniverseAndEverything;/* ###worksheet### generated $$end$$ */ lazy val answerToLifeUniverseAndEverything:Int = CustomInt(42)

which would require an implicit application of the following function call to resolve:

implicitValue: Function1[CustomInt, Int]

Which is more or less the type signature of the implicit value that needs to be in scope in this scenario...that is:

implicit def toInt(given:CustomInt): Int = {
  given.value
}

Or defined as a function to make the type signature more obvious

implicit val toInt:Function1[CustomInt, Int] = (given:CustomInt) => given.value

thus a function that from CustomInt, materializes a value of type Int.

And lastly, the compilation error scenario, due to the following class:

class AnswerToAll {
  def answer = {
    "The answer to Life, Universe and Everything is 42"
  }
}

having a method which is not defined on it called:

print((new AnswerToAll).getAnswer)

causes a compilation error:

Error:(33, 26) value getAnswer is not a member of A$A85.this.AnswerToAll
print((new AnswerToAll).getAnswer)

which would require an implicit application of the following function call to resolve:

Function1[GivenType, ???]

Which is more or less the function signature of the implicit needed to be in scope:

implicit class WithGetAnswer(convertFrom: AnswerToAll) {
  def getAnswer = convertFrom.answer
}

Which can be seen as accepting AnswerToAll and materializes a class which has a getAnswer method, which is what WithGetAnswer is.

So if we can view the mechanism of implicit as the application of function calls as thus illustrated, the next question is, how and where does the Scala compiler search and find these needed functions?

This brings to the second key point, which is implicit Scope and implicit resolution.

Implicit Scope and Implicit Resolution

There is nothing mystifying about the implicit scope as long as you understand that it is more or less the same in nature, as the normal scope encountered in everyday programming. The only difference is the rule that governs where the there implicit scope is. It is different from the normal variable scoping rules any programmer already knows

For example, taking a look at this code snippet:

// brings Duration,ChronoUnit into scope
import java.time.Duration
import java.time.temporal.ChronoUnit

object Test extends App {

  private val intValue = 10
  def printDuration: Unit = {
    // intValue is accessible because it is in scope since its member variable
    // Duration is accessible because it is in scope via import
    // ChronoUnit is accessible because it is in scope via import
    println(Duration.of(intValue, ChronoUnit.DAYS))
  }

  printDuration
}

It can then be seen that the "normal scope" is nothing but the region of the code base, that is looked into, in other to find the definition of an identifier that is encountered in another part of the codebase. This involves looking into the local block of code, the outer encompassing block of codes, member variables, super classes, imports etc.

This is also basically what the implicit scope is also: the region of the code base, that is looked into, in other to find an implicit value when one is needed in another part of the codebase.

Just like you have specific areas and rules that define where the normal scope is, you also have specific areas and rules that define the implicit scope.

For implicits, the places where the compiler looks can be divided into 2. The first is the Current scope. The second place is in the associated types of the Types involved in the implicit conversion.

The current scope is clear enough. This is more or less exactly the same scope that is used for normal resolution of identifiers, variables etc. The associated types scope is unfamiliar and this is the one where the function call metaphor helped me in understanding the implicit resolution.

The second layer is in the associated types of the Types involved in the implicit conversion.

This statement might initially appear complicated, but it ends up being simple, especially when taken with the metaphor of considering the implicit mechanism as a function call. I will expand further on this later on, but let us first look at the first layer of the implicit resolution: The current scope:

The Current Scope:

When an implicit value is required, the Scala compiler would first look into the current scope to find the required implicit value that can act as a function for the type conversion required. The current scope used as implicit scope include:

  1. Local scope
  2. Current Scope defined by Imports (Explicit Imports and Wildcard Imports)

All the implicits used so far as examples in this post has been defined in the current scope.

Associated Type:
If no candidate is found in any of the places included in the current scope, then the Scala compiler looks into the associated types.

What exactly is the associated type?

Remember previously we said the implicit mechanism can be seen as an application of a function that produces the type conversation needed to prevent a compilation error? And we were able to identify 3 different function signature of such a function? That is:

Function0[RequiredType]
Function1[GivenType, RequireType]
Function1[GivenType, ???]

The associated types are then the companion objects and type parameters of the types you see in these function signature.

So for example, if the implicit resolution looks like the application of Function0[RequiredType] then the compiler would first look into the current scope for the needed implicit value. If nothing is found then the compiler would look into the companion objects of the RequiredType . If nothing is found there and RequiredType is a type constructor, ie RequiredType[T] then the implicit scopes of T would be searched in other to retrieve the implicit value required.

In the case of [GivenType, RequireType]the places that would be looked into include the companion objects of  GivenType and RequireType. if they are type constructors ie GivenType[A] and RequireType[B], then the implicit scope of their type arguments A and B would be looked into.

For Function1[GivenType, ???] the same rule applies, but the search would only involve GivenType. Thus, if no needed implicit is found in current scope, first look into the companion object for GivenType, if GivenType is a type constructor, then look into the implicit scope of its type parameter.

Note that in the case where the GivenType/RequiredType extends a class or traits, then the implicit search would include these super class/traits and also their own companion objects.

This knowledge of associated types and the role they play as the implicit scope was a very crucial one in deepening my understanding of what goes on with implicits in Scala.

Now it’s pretty straightforward less confusing. Implicits don't just appear magically, they are either picked from the current scope, or within the associated types (companion objects and type parameters) of the types involved in the implicit conversion (including thier super types).

The Implicitly Function

The last thing I would touch regarding implicit is the Implicitly function defined in the standard library. Reason being that, it is often used when encoding the Type-class pattern in Scala, thus it would be handy to be conversant with what it is, and what it does.


From the git comment, the implicitly function can be seen as a function
"for summoning implicit values from the nether world"

In less dramatic words, we can view implicitly as a function that can be used to retrieve an implicit value from the possible implicit scopes.

for example:

val person: Person = Implicitly[Person]

looks for an implicit value of type Person from within the current scope or the associated types of the Person type. ie the companion object or type parameter (if any) of Person would be looked into.

another example of Implicitly usage:

val cyborgCreator: CyborgCreator = Implicitly[Person => Cyborg] 


would look for an implicit value that can convert from Person to Cyborg in the current scope and also in the associated scope of Person and Cyborg.

Additional Resources

Implicits and implicits resolution could be one of the less explicit and straightforward features in Scala, but yet, it is one of the features that make Scala, Scala. Hence it is inevitable to develop a working mental model of how they work.

Find listed below links to some of the resources that have helped me move from utter confusion to being able to follow along in reading code that makes use of implicits:

Conclusion

Having explored implicits in a little more detail, let us now take a look at another language feature in Scala that comes into play when encoding the Type class pattern, that is Type annotations



No comments: