Why Scala Infer the Bottom Type when the type parameter is not specified?

Viewed 330

I wonder if anyone could explain the inferencing rule in this particular case below, and most importantly it's rational/implication ?

case class E[A, B](a: A) // class E
E(2) // E[Int,Nothing] = E(2)

Note that I could have wrote E[Int](2). What matter to me is why is the second parameter type inferred to be Nothing (i.e. Bottom type) instead of let say Any for instance ? Why is that and What's the rational/Implication ?

Just to give some context, this is related to the definition of Either and how it works for Left and Right. Both are defined according to the pattern

final case class X[+A, +B](value: A) extends Either[A, B]

Where you instantiate it let say as Right[Int](2) and the type inferred is Right[Nothing, Int] and by extension Either[Nothing, Int]

EDIT1

There is consistency here, but i still can figure out the rational. Below is the same definition with a contra-variant paramete:

case class E[A, -B](a: A)// class E
E(2) // E[Int, Any] = E(2)

Hence we do have the same thing the other way around when it is contra-variant, and that make the all behavior or inference rule, coherent. However the rational for this i am not sure ....

Why not the opposite rule i.e. infer Any when Co-Variant/Invariant and Nothing when Contra-Variant ?

EDIT2

In the light of @slouc Answer, which make good sense, i'm left with still understanding what and why the compiler is doing what it is doing. The example below illustrate my confusion

val myleft = Left("Error") // Left[String,Nothing] = Left(Error)
myleft map { (e:Int) => e * 4} // Either[String,Int] = Left(Error)

  1. First the compiler fix the type to something that "for sure work" to reuse the conclusion of @slouc (albeit make more sense in the context of a Function) Left[String,Nothing]
  2. Next the compile infer myleft to be of type Either[String,Int]

given map definition def map[B](f: A => B): Either[E, B], (e:Int) => e * 4 can only be supplied if myleft is actually Left[String,Int] or Either[String,Int]

So in other words, my question is, what is the point of fixing the type to Nothing if it is to change it later.

Indeed the following does not compile

val aleft: Left[String, Nothing] = Left[String, Int]("Error")

type mismatch;
found   : scala.util.Left[String,Int]
required: Left[String,Nothing]
val aleft: Left[String, Nothing] = Left[String, Int]("Error")

So why would I infer to a type, that normally would block me to do anything else over variable of that type (but for sure works in term of inference), to ultimately change that type, so i can do something with a variable of that inferred type.

EDIT3

Edit2 is a bit misunderstanding and everything is clarified in @slouc answer and comments.

2 Answers
  • Covariance:
    Given type F[+A] and relation A <: B, then the following holds: F[A] <: F[B]

  • Contravariance:
    Given type F[-A] and relation A <: B, then the following holds: F[A] >: F[B]

If the compiler cannot infer the exact type, it will resolve the lowest possible type in case of covariance and highest possible type in case of contravariance.

Why?

This is a very important rule when it comes to variance in subtyping. It can be shown on the example of the following data type from Scala:

trait Function1[Input-, Output+]

Generally speaking, when a type is placed in the function/method parameters, it means it's in the so-called "contravariant position". If it's used in function/method return values, it's in the so-called "covariant position". If it's in both, then it's invariant.

Now, given the rules from the beginning of this post, we conclude that, given:

trait Food
trait Fruit extends Food
trait Apple extends Fruit

def foo(someFunction: Fruit => Fruit) = ???

we can supply

val f: Food => Apple = ???
foo(f)

Function f is a valid substitute for someFunction because:

  • Food is a supertype of Fruit (contravariance of input)
  • Apple is a subtype of Fruit (covariance of output)

We can explain this in natural language like this:

"Method foo needs a function that can take a Fruit and produce a Fruit. This means foo will have some Fruit and will need a function it can feed it to, and expect some Fruit back. If it gets a function Food => Apple, everything is fine - it can still feed it Fruit (because the function takes any food), and it can receive Fruit (apples are fruit, so the contract is respected).

Coming back to your initial dilemma, hopefully this explains why, without any extra information, compiler will resort to lowest possible type for covariant types and highest possible type for contravariant ones. If we want to supply a function to foo, there's one that we know surely works: Any => Nothing.

Variance in general.

Variance in Scala documentation.

Article about variance in Scala (full disclosure: I wrote it).

EDIT:

I think I know what's confusing you.

When you instantiate a Left[String, Nothing], you're allowed to later map it with a function Int => Whatever, or String => Whatever, or Any => Whatever. This is precisly because of the contravariance of function input explained earlier. That's why your map works.

"what is the point of fixing the type to Nothing if it is to change it later?"

I think it's a bit hard to wrap your head around compiler fixing the unknown type to Nothing in case of contravariance. When it fixes the unknown type to Any in case of covariance, it feels more natural (it can be "Anything"). Because of the duality of covariance and contravariance explained earlier, same reasoning applies for contravariant Nothing and covariant Any.

This is a quote from Unification of Compile-Time and Runtime Metaprogramming in Scala by Eugene Burmako

https://infoscience.epfl.ch/record/226166 (p. 95-96)

During type inference, the typechecker collects constraints on missing type arguments from bounds of type parameters, from types of term arguments, and even from results of implicit search (type inference works together with implicit search because Scala supports an analogue of functional dependencies). One can view these constraints as a system of inequalities where unknown type arguments are represented as type variables and order is imposed by the subtyping relation.

After collecting constraints, the typechecker starts a step-by-step process that, on each step, tries to apply a certain transformation to inequalities, creating an equivalent, yet supposedly simpler system of inequalities. The goal of type inference is to transform the original inequalities to equalities that represent a unique solution of the original system.

Most of the time, type inference succeeds. In that case, missing type arguments are inferred to the types represented by the solution.

However, sometimes type inference fails. For example, when a type parameter T is phantom, i.e. unused in the term parameters of the method, its only entry in the system of inequalities will be L <: T <: U, where L and U are its lower and upper bound respectively. If L != U, this inequality does not have a unique solution, and that means a failure of type inference.

When type inference fails, i.e. when it is unable to take any more transformation steps and its working state still contains some inequalities, the typechecker breaks the stalemate. It takes all yet uninferred type arguments, i.e. those whose variables are still represented by inequalities, and forcibly minimizes them, i.e. equates them to their lower bounds. This produces a result where some type arguments are inferred precisely, and some are replaced with seemingly arbitrary types. For instance, unconstrained type parameters are inferred to Nothing, which is a common source of confusion for Scala beginners.

You can learn more about type inference in Scala:

Hubert Plociniczak Decrypting Local Type Inference https://infoscience.epfl.ch/record/214757

Guillaume Martres Scala 3, Type Inference and You! https://www.youtube.com/watch?v=lMvOykNQ4zs

Guillaume Martres Dotty and types: the story so far https://www.youtube.com/watch?v=YIQjfCKDR5A

Slides http://guillaume.martres.me/talks/

Aleksander Boruch-Gruszecki GADTs in Dotty https://www.youtube.com/watch?v=VV9lPg3fNl8

Related