scalac does not infer super types when implicit for super type exists.

[Jonathan Chayat]

Hi all,

I'm reposting this after posting on scala-internals where it did not get much traction.

It seems that currently when inferring a type T which requires some implicit evidence R[T], 

scalac will start by inferring the most specific T possible, and upon failing to find evidence for that type

it will give up, even if evidence is present for a super type. 

Here's an example from SO (tinyurl.com/hmap-so-question):  

trait R[T]

case class A(i: Int)

object A {

  implicit object RA extends R[A]

}

class B(i: Int) extends A(i)

def foo[T](x : T)(implicit ev: R[T]) = 0

println(foo(new B(1))) // infers T as B and fails to find implicit R[B]

println(foo(new B(1) : A)) // Works, but undesirable

Another Example  (using spire):

import spire.algebra.AdditiveSemigroup
import spire.implicits._
 
sealed abstract class A(val j: Int)
 
object A {
 
    implicit val ev: AdditiveSemigroup[A] = new AdditiveSemigroup[A] {
      override def plus(x: A, y: A): A = (x, y) match {
        case (B(l), B(r)) => B(l + r)
        case _ => C(x.j + y.j)
      }
    }
 
}
 
case class B(i: Int) extends A(i)
 
case class C(i: Int) extends A(i)
 
B(1) + B(2) // Does not work because no evidence of AdditiveSemigroup[B]
 
(B(1) : A) + (B(2) : A) // Works - each B is also an A

IMO, this seriously undermines usage of subtyping to encode co-products, which is very idiomatic in scala.

I would like to propose the following change to type inference/implicit resolution: 

When trying to infer a type T which appears in some implicit parameter, the compiler should successivelt try inferring supertypes of the type it starts from only failing if it reaches Any without finding suitable implicits.

In my opinion, this should not violate any type system rules, given that all type rules must still be satisfied. I could always add type annotations which make things work - so there is no correctness problem here.  

I understand that this is not a formal enough definition, but my goal here is to start a discussion of this issue.

WDYT?

[Stephen Compall]

On Sun, 2015-03-15 at 15:01 -0700, Jonathan Chayat wrote:

def foo[T](x : T)(implicit ev: R[T]) = 0

println(foo(new B(1))) // infers T as B and fails to find implicit R[B]

println(foo(new B(1) : A)) // Works, but undesirable

IMO, this seriously undermines usage of subtyping to encode co-products, which is very idiomatic in scala.

It undermines it, but not seriously. In most cases in non-test code, you don't statically know which data constructor of the ADT you have in hand anyway.

I would like to propose the following change to type inference/implicit resolution: 

When trying to infer a type T which appears in some implicit parameter, the compiler should successivelt try inferring supertypes of the type it starts from only failing if it reaches Any without finding suitable implicits.

In my opinion, this should not violate any type system rules, given that all type rules must still be satisfied. I could always add type annotations which make things work - so there is no correctness problem here.  

I understand that this is not a formal enough definition, but my goal here is to start a discussion of this issue.

Any solution to the problem you describe must satisfactorily address the various concerns raised in this very argumentative thread about this issue. Specifically regarding your proposal, you must also deal with the fact that there may be no unambiguous or finite linearization of supertypes of a given type to try.

-- Stephen Compall "^aCollection allSatisfy: [:each|aCondition]": less is better

[Jonathan Chayat]

Hi Stephen,

Thanks for your reply.

On Saturday, 21 March 2015 06:09:20 UTC+2, Stephen Compall wrote:

It undermines it, but not seriously. In most cases in non-test code, you don't statically know which data constructor of the ADT you have in hand anyway.

I disagree here. The following situations are common:

1. Creating object literals (as demonstrated) is not specific to test code (although it's more prevalent there). Besides, test code is just as important to me as non-test code (around 50% of my code is test code).
2. It seems you assume that working with ADTs always means you only know you have something whose type is the base of the hierarchy (perhaps because the hierarchy is shallow). But some hierarchies are deep, and methods might return a more specific type than the root. Think about the spire example, It is perfectly valid to have a method returning a B
   
   def foo(i): B = B(i)
   
   def bar(a: A): Unit = println(a.i)
   
   bar(foo(1)) //Compiles
   
   foo(1) + foo(2) //Does not compile
   
   Of course I could define foo this way:
   
   def foo(i): A = B(i)
   
   but then I have information loss. 

Any solution to the problem you describe must satisfactorily address the various concerns raised in this very argumentative thread about this issue. 

I've been looking at that thread  - I'm not sure this is exactly the same problem. The thread deals specifically with contravariant typeclasses - my case is the one of an invariant typeclass. while playing with my own example and the one in https://issues.scala-lang.org/browse/SI-2509 I've found that scalac is very (too) sensitive to a lot of detail, such as whether I write

implicit object RA extends R[A]

or  

object RA extends R[A]

implicit val ra = A

or

object RA extends R[A]

implicit val ra: R[A] = A

Now couple this with the placement of the implicit definition (both evidences in the same scope vs in each companion object) and with an invariant vs. contravariant typeclass and you get every possible outcome (A inferred, B inferred, implicit not found, ambigious implicits).

My point being - although that issue also deals with implicit search, I'm not convinced this is actually the same issue.

Specifically regarding your proposal, you must also deal with the fact that there may be no unambiguous or finite linearization of supertypes of a given type to try.

Well implicit search has a notion of a finite linearization of supertypes - why not use it for this case as well? 

Jon