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

[Jonathan Chayat]

Hi all

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?

[Jesper Nordenberg]

Two solutions:

Make the trait contravariant:

trait R[-T]

or the implicit more general:

implicit def RA[T <: A] = new R[T] {}

/Jesper Nordenberg

[Jonathan Chayat]

Making the evidence contravariant can create a lot of issues in practice and is not always possible. 

Example when this is problematic:

in https://github.com/SupersonicAds/marbles/blob/master/src/main/scala/marbles/HMap.scala#L45

if we have M[-K, -V] then V gets inferred as Nothing.

Example when this is not possible: the spire example above. I didn't write AdditiveSemigroup, so I cant change it's variance. In fact, making it contravariant is not correct... 

The second solution also does not hold for the spire example (defining a semigroup over a set does not mean it's a semigroup over subsets).

Jon

[Adriaan Moors]

FWIW, the code below works -- not sure it addresses your use case

  - RA must be in the implicit scope at calls to foo -- here's one way to ensure that

  - you must encode the variance at use-site using the lower-bounded existential

I don't like special casing type inference for implicit search involving a sealed hierarchy and I'll try to write down why soon.

trait R[T]

object R { 

  implicit object RA extends R[A] // must be in implicit scope when searching implicit of type that has R as its part

}

case class A(i: Int)

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

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

println(foo(new B(1)))

 

--
You received this message because you are subscribed to the Google Groups "scala-internals" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-interna...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jonathan Chayat]

Hi,

So, AFAIK, using implicit ev: R[_ >: T] will not do an implicit search in the T's and T's parents' companion objects (which might be worth a separate discussion)

and this means we need to import the evidence at each use site of foo. 

Having the evidence under the R companion is definitely not always an option (such as when R is defined by an external library)

To me, this is a non-solution, as it creates overhead which is equivalent to or greater than adding type annotations.

Also, I didn't understand the remark about sealed hierarchy. I'm proposing this as a modification for all types, not only sealed ones. 

[Jonathan Chayat]

Hi,

Regarding proposed solution:

1. AFAIK, scalac will not look for implicits in T's parents' companion objects when 
   encountering  implicit ev: R[_ >: T] (perhaps a topic for another discussion).
   Having to manually import the implicit evidence at each call site nullifies the benefits
   of implicit search and requires a lot of boilerplate. Thus I don't consider this a viable solution.
2. In many cases the definition of said foo or typeclass is in a third party library (e.g. spire)
   so it is not up to the developer to change the method's signature or said companion object.
3. I'm not sure about the special casing argument, as I'm not proposing a special case
   for sealed hierarchies, but rather a universal change which works for all types.

Jon

On Tuesday, 3 March 2015 03:41:32 UTC+2, Adriaan Moors wrote:

[Jonathan Chayat]

Is scala-language a better place for this discussion?

[Adriaan Moors]

Sorry, mostly just having trouble keeping up with email volume. It's an interesting discussion, but I don't have the bandwidth right now to discuss changes to type inference, that we can't really make in the 2.x series because of source compatibility concerns.

On Sat, Mar 14, 2015 at 4:23 AM, Jonathan Chayat <jch...@gmail.com> wrote:

Is scala-language a better place for this discussion?

[Jonathan Chayat]

Do you think maybe this can be developed and activated with a compiler flag (thus not breaking compatibility)?

--
You received this message because you are subscribed to a topic in the Google Groups "scala-internals" group.
To unsubscribe from this topic, visit https://groups.google.com/d/topic/scala-internals/1RHeSINAcDM/unsubscribe.
To unsubscribe from this group and all its topics, send an email to scala-interna...@googlegroups.com.

[Adriaan Moors]

That's certainly feasible, but our team can't take on anything that doesn't directly further the 2.12 roadmap. Lots of good stuff in there already, I'd say, though :-)