Scala implicit search of covariant type class replaces the type argument with Nothing. Why?

Question

Let's use a real world example. A string parser type class whose implicit instances are created by a function that delegates the creation to a factory.

import scala.reflect.runtime.universe.TypeTag

object Test {

    trait Parser[+T] { def parse(input: String): T }

    implicit def summonParserOf[T](implicit factory: ParserFactory[T]): Parser[T] = factory.build

    trait ParserFactory[T] { def build: Parser[T] }

    implicit def summonFactoryOfParsersOf[T](implicit t: TypeTag[T]): ParserFactory[T] =
        new ParserFactory[T] {
            def build: Parser[T] = new Parser[T] {
                def parse(input: String) = {
                    println("T = " + t.tpe) // this outputs "T = Int" if Parser is non variant, and "T = Nothing" if Parser is covariant on T. Why?
                    null.asInstanceOf[T]
                }
            }
        }

    def main(args: Array[String]): Unit = {
        val parserOfInt = implicitly[Parser[Int]]
        parserOfInt.parse("")
    }
}

The type parameter T received by the factory is Int when Parser is non-variant, and Nothing when it is covariant. Why?

Edit 1: The factory is not necessary. The replacement occurs before. So the test can be reduced to:

package jsfacile.test

import scala.reflect.runtime.universe.TypeTag

object Probando {

    trait Parser[+T] { def parse(input: String): T }

    implicit def summonParserOf[T](implicit t: TypeTag[T]): Parser[T] = new Parser[T] {
        def parse(input: String): T = {
            println("summon parser: T = " + t.tpe) // this outputs "T = Int" if Parser is non variant, and "T = Nothing" if Parser is covariant on T. Why?
                null.asInstanceOf[T]
            null.asInstanceOf[T]
        }
    }

    def main(args: Array[String]): Unit = {
        val parserOfInt = implicitly[Parser[Int]]
        parserOfInt.parse("")
    }
}

Parser[Nothing] is assignable to Parser[Int], but which is the purpose of choosing the lower bound instead of the upper one?

Edit 2: The answer given by @Dmytro Mitin and the useful comments below, translated to my own words and limited scope of thinking, for future reference to myself.

What stopped me to understand was the wrong idea that, when the implicit value provider is a def with parametrized result type, there is no set of living values from which the compiler has to pick one of. In that case, I thought, it just skips that step (the one that chooses the value with the most specific declared type). And given the summoner function grants the compiler the power to build a value of any type, why not to fill the implicit parameter with a value that makes him happy. If the implicit parameter demands something assignable to a type T then give it a value of type T. Giving it Nothing, which is assignable to everything, wouldn't be nice nor useful.

The problem with that idea arises when there is more than one summoner providing values assignable to the implicit parameter type. In that case, the only consistent way to decide which summoner to chose is to deduce the set of types of the values they produce, pick a type from said set based on an established criteria (the most specific, for instance), and choose the summoner that produces it.

Why not? A **Parser[Nothing]** is a valid **Parser[Int]** due covariance. If you do not like that, make it invariant _(that is why most typeclasses are invariant, because variance can make implicit resolution really tricky)_. - In any case, it is really interesting it picks **Nothing**, hopefully, someone will have a clue. — Luis Miguel Mejía Suárez, Nov 06 '20 at 21:03
_"but which is the purpose of choosing the lower bound instead of the upper one?"_ Because the specs say that implicit resolution will pick the "most specific value", here `specific` is in subtyping terms, meaning the lowest possible subtype. [this](https://github.com/BalmungSan/scala-functional-programming-tutorial/blob/master/scala-intro/src/main/scala/co/edu/eafit/dis/progfun/scala/intro/ImplicitsNotes.scala) may give some light on the problem. — Luis Miguel Mejía Suárez, Nov 06 '20 at 22:01
It doesn't matter what it infers, because the only "meaningful" way to implement `summonParserOf` is to throw an error. That must be non-implementable, because otherwise, one would trivially obtain every kind of `val u: Unobtanium = summonParserOf[Unobtanium].parse("")`, ranging from the merely too-good-to-be-true `summonParserOf[SatoshiNakomotosPrivateKey].parse("")` to the completely unthinkable `summonParserOf[HaltingProblemSolver].parse("")`. With covariant type, the compiler at least tries to prevent any further damage by choosing the `Nothing`-type - at least it has no instances. — Andrey Tyukin, Nov 06 '20 at 22:17
https://stackoverflow.com/questions/62747743/in-scala-2-13-how-to-use-implicitlyvalue-singleton-type — Dmytro Mitin, Nov 06 '20 at 22:42
@AndreyTyukin Then why does the compiler allow to define such a function? — Readren, Nov 07 '20 at 01:10
@Readren Do you want `def makeAValueOfAnyType[A]: A = ???` not to compile either? — Dmytro Mitin, Nov 07 '20 at 01:28
@Readren Because there are always programs that do not have any runtime type errors, but for which you cannot prove it within the type system. Or maybe you could prove it, with some effort, but it would be too cumbersome to do so. That's why all practical systems have the type casting (`asInstanceOf` etc): so that the programmer can simply tell the type system to trust him/her unconditionally, and to assume that a certain expression has a certain type. In your particular example, you are telling the type system to trust you that `null` will always be a valid instance of any given type... — Andrey Tyukin, Nov 07 '20 at 01:29
...which is a dangerous assumption. As soon as you would try to clean up the `null`s and `asInstanceOf` "emergency overrides", you would soon notice that this method is not actually implementable, some other inputs or assumptions are missing. — Andrey Tyukin, Nov 07 '20 at 01:31
@AndreyTyukin I guess OP's question can be reformulated for `trait MyTypeclass[T /*+T*/] { def printTypeT(): Unit }` `implicit def summonMyTypeclass[T](implicit t: TypeTag[T]): MyTypeclass[T] = () => { println("T = " + t.tpe) }` `val tc = implicitly[MyTypeclass[Int]]` `tc.printTypeT()` Then your argument about absence of meaningful implementation is no longer relevant. Right? — Dmytro Mitin, Nov 07 '20 at 01:53
@LuisMiguelMejíaSuárez The question is, which are the values in scope when the only summoner is a `def`? If I am right the value generated by an implicit `def` is produced on demand. And what is demanded here is something that is assignable to `Parser[Int]`. Given the implicit values provided are not vals but a `def` the compiler is not limited to choose a value from a finite set. It can create a `Parser[T]` of any `T` because the summoner is parametrized on T. It has the power to choose. And what would a gentle guy give to the demander. A `Parser[Int]` or a `Parser[Nothing]`? — Readren, Nov 07 '20 at 02:03
@Readren By the way, sometimes compiler doesn't like to infer `Nothing` https://stackoverflow.com/questions/61951621/failed-implicit-resolution-for-nothing-with https://stackoverflow.com/questions/63642765/scalas-nothing-vs-partial-unification — Dmytro Mitin, Nov 07 '20 at 02:04
@DmytroMitin Right. Additionally, since the `MyTypeclass` no longer has any obligations to either generate or consume `T`s, one can also see that for `-T`, it picks `Int` (not `Any`), which seems weirdly asymmetric. But my point is not about the specific types, more about this whole example looking like an artificial XY problem. I have the impression that as soon as one introduces more realistic constraints and removes all the weird hypothetical `null.asInstanceOf`s, the types should fall into place all by themselves. — Andrey Tyukin, Nov 07 '20 at 02:21
@AndreyTyukin I still don't understand why the only meaningful implementation of `summonParserOf` is to throw an error. The summoner intention is to provide an implicit value when one is demanded. Here thee demand is something assignable to `Parser[Int]`. And the result type of the summoner function is compatible with that. The only problem is that there is degree of freedom on what `T` to choose. — Readren, Nov 07 '20 at 02:22
@AndreyTyukin This makes sense. For covariant type class when you look for `TC[Int]` all `TC[A]` (`A <: Int`) are eligible, so the most specific is selected, namely `TC[Nothing]`. For contravariant type class when you look for `TC[Int]` all `TC[A]` (`A >: Int`) are eligible, so the most specific is selected, namely `TC[Int]`. The asymmetricity is because of Liskov principle. Liskov is asymmetric. — Dmytro Mitin, Nov 07 '20 at 02:29
@AndreyTyukin If you want symmetricity then you need something like `implicitExactTypeOf` (from my [answer](https://stackoverflow.com/a/62748275/5249621)) rather than standard `implicitly`. — Dmytro Mitin, Nov 07 '20 at 02:33
@Readren Because given your definitions, I can first define `def impossibleFactory[A: TypeTag]: A = summonParserOf(summonFactoryOfParsersOf[A]).parse("")`, and then define `val u: Nothing = impossibleFactory[Nothing]`, which compiles, but results in some weird value `u` which can't even be printed without crashing everything. — Andrey Tyukin, Nov 07 '20 at 02:34

score 2 · Accepted Answer · answered Nov 07 '20 at 02:21

Scala spec says

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

https://scala-lang.org/files/archive/spec/2.11/07-implicits.html#implicit-parameters

Since you defined instances like

implicit def summonParserOf[T](implicit t: TypeTag[T]): Parser[T] = ...

for covariant

trait Parser[+T] { ... }

when you look for implicitly[Parser[T]], all summonParserOf[S] (S <: T) are eligible candidates, so the compiler selects the most specific one.

I understand now. First the compiler imagines all the posible results types of the summoner, then chooses the most specific, and lastly calls the summoner with the chosen type. — Readren, Nov 07 '20 at 02:55

Scala implicit search of covariant type class replaces the type argument with Nothing. Why?

1 Answers1