Type parameters should be instantiated before doing an implicit search #739

smarter · 2015-07-24T22:03:20Z

This is a separate issue from #738 but I think that they will need to be fixed together to get something that makes sense.
Consider the following code:

class Foo

object Test {
  def foo[T](x: T)(implicit ev: T): T = ???

  def test: Unit = {
    implicit val evidence: Foo = new Foo
    foo(new Foo)
  }
}

It currently fails with:

try/constrimpl.scala:9: error: ambiguous implicits: both getter StringCanBuildFrom in object Predef$ and getter NothingClassTag in object DottyPredef$ match type (T? >: Foo) of parameter ev of method foo in object Test$
    foo(new Foo)
                ^
try/constrimpl.scala:10: error: ambiguous implicits: both getter StringCanBuildFrom in object Predef$ and getter NothingClassTag in object DottyPredef$ match type (T? >: Foo) of parameter ev of method foo in object Test$
  }
   ^
two errors found

When we do the implicit search, T is not instantiated yet, the only thing we know is that its lower bound is Foo as the error message says: ... match type (T? >: Foo) of parameter ev of method foo .... I don't know how scalac deals with this exactly but it seems like it simply instantiate the type parameter before doing the implicit search, we should consider doing the same thing.

Note that this is also needed to properly fix #553, if we don't instantiate CC to List, then CC is only lower-bounded by List, and lower bounds of abstract types are not part of the implicit scope, this means that the implicit List.canBuildFrom will not be in the scope.

The text was updated successfully, but these errors were encountered:

odersky · 2015-08-06T02:16:45Z

scalac does not generally instantiate parameters before an implicit search. If it did, the whole concept of CanBuildFrom would not work, to give an example. But parameter instantiation is different between the two systems, and it seems this example shows where dotty's way is problematic. Maybe instantiate when there are ambiguity errors otherwise?

retronym · 2015-08-06T02:33:04Z

FYI, here's how to get a bit of logging from scalac about type param inference.

% cat sandbox/test.scala
class Foo[A, B]

object Test {
  def foo[T, U](x: T)(implicit ev: Foo[T, U]): U = ???

  def test: Unit = {
    implicit val evidence1: Foo[Int, String] = ???
    implicit val evidence2: Foo[String, Int] = ???
    foo(1)
  }
}

% scalac -Dscalac.debug.tvar -Xprint:typer -Ytyper-debug sandbox/test.scala

|    |    |    |-- foo(1) : pt=Unit EXPRmode (site: method test in Test)
|    |    |    |    |-- foo BYVALmode-EXPRmode-FUNmode-POLYmode (silent: method test in Test)
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to [T, U](x: T)(implicit ev: Foo[T,U])U
|    |    |    |    |    \-> (x: T)(implicit ev: Foo[T,U])U
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: method test in Test)
|    |    |    |    |    \-> Int(1)
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (T: ?T, U: ?U)
[   setInst] Int                      ( In Test#foo[T,U], T=Int )
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] String                   ( In Test#foo[T,U], U=String )
|    |    |    |    |-- [T, U](x: T)(implicit ev: Foo[T,U])U : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |-- { Test.this.foo[Int, String](1)(evidence1); () } : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |    \-> Unit
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    |    \-> Unit
|    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    \-> Unit
|    |    |    \-> Unit
|    |    \-> [def test] => Unit
|    \-> [object Test] Test.type
[[syntax trees at end of                     typer]] // test.scala
package <empty> {
  class Foo[A, B] extends scala.AnyRef {
    def <init>(): Foo[A,B] = {
      Foo.super.<init>();
      ()
    }
  };
  object Test extends scala.AnyRef {
    def <init>(): Test.type = {
      Test.super.<init>();
      ()
    };
    def foo[T, U](x: T)(implicit ev: Foo[T,U]): U = scala.this.Predef.???;
    def test: Unit = {
      implicit val evidence1: Foo[Int,String] = scala.this.Predef.???;
      implicit val evidence2: Foo[String,Int] = scala.this.Predef.???;
      {
        Test.this.foo[Int, String](1)(evidence1);
        ()
      }
    }
  }
}

smarter · 2015-08-06T02:33:44Z

@odersky : Yes, that description is not exactly right: in Scala 2, type parameters are instantiated after the first parameter list in which they appear, for example:

class Foo
class Bar extends Foo

object Test {
  def one[T](x: T, y: T): T = x
  def two[T](x: T)(y: T): T = x
  def twob[T](x: T)(y: T): Nothing = ???
  def two2[T,S](x: T)(y: S): T = x

  def test = {
    one(new Bar, new Foo) // scala and dotty: T=Foo
    two(new Bar)(new Foo) // scala: T=Bar, type mismatch; dotty: T=Foo
    twob(new Bar)(new Foo) // scala: T=Bar, type mismatch; dotty: T=Any
    two2(new Bar)(new Foo) // scala: T=Bar, S=Foo; dotty: T=Bar, S=Any
  }
}

The behavior of scalac with implicits is just a special case of that: type parameters which appear in a parameter list before an implicit parameter list will be instantiated, others won't so CanBuildFrom works fine. The behavior of dotty is not really consistent.

retronym · 2015-08-06T02:43:48Z

I think it is more accurate to say that the compiler attempts to instantiate them all, but retracts ones that solve to Nothing.

retronym · 2015-08-06T02:48:01Z

One more note: -Ytyper-debug is currently a bit crippled, a lot of useful messages are filtered out during implicit search.

Applying this diff:

git diff -- '**/Implicits.scala'
diff --git a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
index 7ec9cd7..1b5783f 100644
--- a/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
+++ b/src/compiler/scala/tools/nsc/typechecker/Implicits.scala
@@ -325,7 +325,7 @@ trait Implicits {
   class ImplicitSearch(tree: Tree, pt: Type, isView: Boolean, context0: Context, pos0: Position = NoPosition) extends Typer(context0) with ImplicitsContextErrors {
     val searchId = implicitSearchId()
     private def typingLog(what: String, msg: => String) =
-      typingStack.printTyping(tree, f"[search #$searchId] $what $msg")
+      typingStack.printTyping(f"[search #$searchId] $what $msg")

     import infer._
     if (Statistics.canEnable) Statistics.incCounter(implicitSearchCount)

Shows the interaction between implicit search and inference more explicitly:

|    |    |    |-- foo(1) : pt=Unit EXPRmode (site: method test in Test)
|    |    |    |    |-- foo BYVALmode-EXPRmode-FUNmode-POLYmode (silent: method test in Test)
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to [T, U](x: T)(implicit ev: Foo[T,U])U
|    |    |    |    |    \-> (x: T)(implicit ev: Foo[T,U])U
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: method test in Test)
|    |    |    |    |    \-> Int(1)
[    create] ?T                       ( In Test#foo[T,U] )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (T: ?T, U: ?U)
[   setInst] Int                      ( In Test#foo[T,U], T=Int )
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    solving for (U: ?U)
[   setInst] Nothing                  ( In Test#foo[T,U], U=Nothing )
|    |    |    |    [search #1] start `[T, U](x: T)(implicit ev: Foo[T,U])U` inferring type U, searching for adaptation to pt=Foo[Int,U] (silent: method test in Test) implicits disabled
|    |    |    |    [search #1] considering evidence1
[    create] ?U                       ( In Test#foo[T,U] )
|    |    |    |    [search #1] solve tvars=?U, tvars.constr= >: String <: String
|    |    |    |    solving for (U: ?U)
[   setInst] String                   ( In Test#foo[T,U], U=String )
|    |    |    |    [search #1] success inferred value of type Foo[Int,=?String] is SearchResult(evidence1, TreeTypeSubstituter(List(type U),List(String)))
|    |    |    |    |-- [T, U](x: T)(implicit ev: Foo[T,U])U : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |-- { Test.this.foo[Int, String](1)(evidence1); () } : pt=Unit EXPRmode (silent: method test in Test)
|    |    |    |    |    |    \-> Unit
|    |    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    |    \-> Unit
|    |    |    |    [adapt] [T, U](x: T)(implicit ev: Foo[T,U])U adapted to { Test.this.foo[Int, String](1)(evidence1); () } based on pt Unit
|    |    |    |    \-> Unit

retronym · 2015-08-06T02:51:50Z

Here's an test case that shows the difference between the "try to instantiate but retract nothing" and "instantiate when referred to in a param list" description:

class Foo[A, B]
class Test {
  implicit val f: Foo[Int, String] = ???
  def t[A, B >: A](a: A)(implicit f: Foo[A, B]) = ???
  t(1)
}

This fails with could not find implicit of Foo[Int, Int].

|    |-- t(1) BYVALmode-EXPRmode (site: value <local Test> in Test)
|    |    |-- t BYVALmode-EXPRmode-FUNmode-POLYmode (silent: value <local Test> in Test)
|    |    |    [adapt] [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing adapted to [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing
|    |    |    \-> (a: A)(implicit f: Foo[A,B])Nothing
|    |    |-- 1 BYVALmode-EXPRmode-POLYmode (site: value <local Test> in Test)
|    |    |    \-> Int(1)
|    |    solving for (A: ?A, B: ?B)
|    |    [search #1] start `[A, B >: A](a: A)(implicit f: Foo[A,B])Nothing`, searching for adaptation to pt=Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
sandbox/instantiate.scala:5: error: could not find implicit value for parameter f: Foo[Int,Int]
  t(1)
   ^
|    |    |-- [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing BYVALmode-EXPRmode (site: value <local Test> in Test)
|    |    |    [search #2] start `()`, searching for adaptation to pt=Unit => Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
|    |    |    [search #3] start `()`, searching for adaptation to pt=(=> Unit) => Foo[Int,Int] (silent: value <local Test> in Test) implicits disabled
|    |    |    \-> <error>
|    |    [adapt] [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing adapted to [A, B >: A](a: A)(implicit f: Foo[A,B])Nothing
|    |    \-> <error>

smarter · 2015-08-06T02:56:25Z

I think it is more accurate to say that the compiler attempts to instantiate them all, but retracts ones that solve to Nothing.

@retronym Ah indeed, I didn't know that! I think that for dotty we want to avoid special-casing Nothing in type inference, so the rule "instantiate when referred to in a param list" would be a good way to do that. It would have some other nice intuitive properties, like the fact that adding an empty parameter list cannot change the result of inference, unlike what happens with scalac:

class Foo
class Bar extends Foo

object Test {
  def a[T >: Foo](x: T): T = x
  def b[T >: Foo]()(y: T): T = y

  def test = {
    a(new Bar) // scalac: T=Bar
    b()(new Bar) // scalac: T=Foo
  }
}

smarter · 2015-08-06T03:03:20Z

(FWIW, I have a hacky implementation of my proposed scheme at https://github.com/smarter/dotty/commits/fix/tp-instantiation-scheme but it uncovered some other issues in dotty I need to fix first before opening a PR for it, it also breaks inference for some scala2 library methods like zip)

odersky · 2015-08-06T03:14:03Z

On Wed, Aug 5, 2015 at 7:43 PM, Jason Zaugg [email protected]
wrote:

I think it is more accurate to say that the compiler attempts to
instantiate them all, but retracts ones that solve to Nothing.

Yes, that's the problem. dotty does not have the "fear of Nothing", but
it does not instantiate type parameters eagerly either. It's a delicate
question. Maybe instantiate type params only if ambiguity errors are
encountered?

Martin

—

Reply to this email directly or view it on GitHub
#739 (comment).

Martin Odersky
EPFL

odersky · 2015-08-06T03:15:48Z

On Wed, Aug 5, 2015 at 7:56 PM, Guillaume Martres [email protected]
wrote:

I think it is more accurate to say that the compiler attempts to
instantiate them all, but retracts ones that solve to Nothing.

@retronym https://github.com/retronym Ah indeed, I didn't know that! I
think that for dotty we want to avoid special-casing Nothing in type
inference, so the rule "instantiate when referred to in a param list" would
be a good way to do that.

But how do you define that precisely? Does the argument need a type which
contains the typevar? What if it only has another typevar that contains
this typevar as a bound?

Martin

It would have some other nice intuitive properties, like the fact that
adding an empty parameter list cannot change the result of inference,
unlike what happens with scalac:

class Fooclass Bar extends Foo
object Test {
def a[T >: Foo](x: T): T = x
def bT >: Foo(y: T): T = y

def test = {
a(new Bar) // scalac: T=Bar
b()(new Bar) // scalac: T=Foo
}
}

—
Reply to this email directly or view it on GitHub
#739 (comment).

Martin Odersky
EPFL

smarter · 2015-08-06T03:20:23Z

But how do you define that precisely? Does the argument need a type which
contains the typevar? What if it only has another typevar that contains
this typevar as a bound?

"A type which contains the typevar" looks like a good rule to me since it's easy to visually identify, this is what I implemented in my prototype: https://github.com/smarter/dotty/commits/fix/tp-instantiation-scheme

Your proposal could work too, but note that some methods like foldLeft work better if we try to infer type parameters eagerly: https://issues.scala-lang.org/browse/SI-9262?focusedCommentId=72280&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-72280 (I'm sure that whatever we choose, we'll end up breaking inference for some methods, but it'd be good to decide which patterns are useful / worth preserving).

odersky · 2015-08-09T19:30:00Z

@smarter We could say: "Before typing an implicit parameter list of a method m, instantiate all type parameters of m that occur in the type of some preceding value parameter of m." Is that what your prototype does?

foldLeft already works as intended I believe. The general principle in dotty is not to interpolate type vars except in a handful of situations. One such situation is when we need to infer the type of the parameter of a lambda. In that case we instantiate the expected type of the lambda by interpolating all its type variables.

smarter · 2015-08-09T21:12:02Z

We could say: "Before typing an implicit parameter list of a method m, instantiate all type parameters of m that occur in the type of some preceding value parameter of m." Is that what your prototype does?

No, I don't special case implicit parameter lists, here's an example of how my prototype works:

def foo[T, S](x: Thing[T])(y: OtherThing[S]) = ???
foo(arg1)(arg2)

Typer will first type foo which will not instantiate anything
Then we type foo(arg1). At this point we notice that T appears in the current formal parameter list ((x: Thing[T])), so we instantiate it, there are two cases:
- If T only appears contravariantly in the current parameter list, we maximize T, this solves type parameter inference behaves unexpectedly when a type parameter is used in a contravariant position #718
- Otherwise, we minimize T.
Then we type foo(arg1)(arg2). At this point we notice that S appears in the current formal parameter list ((y: OtherThing[S])), so we instantiate it, the details are the same as in 2.

foldLeft already works as intended I believe. The general principle in dotty is not to interpolate type vars except in a handful of situations. One such situation is when we need to infer the type of the parameter of a lambda. In that case we instantiate the expected type of the lambda by interpolating all its type variables.

Interesting, I did not know that. That covers the most common usecase for multiple parameter lists, but there are other cases where people rely on eager instantiation, for example: http://stackoverflow.com/questions/31177695/shapeless-hlist-type-checking/31192042#31192042 So we need to decide if it's worth breaking compatibility here.

odersky · 2015-08-09T22:07:20Z

@smarter

No, I don't special case implicit parameter lists, here's an example of how my prototype works:

But I think we should special case them. The philosophy of type inference in dotty and scalac is just different. In dotty, we leave type variables uninstantiated by default, and instantiate in a small number of well-specifed cases. In scalac it's the reverse, type variables are by default instantiated except in a number of circumstances where they are left uninstantiated. Scalac's scheme is more problematic. In particular, it relies crucially on not inferring Nothing and in doing so it confounds Nothing as "unconstrained" and Nothing as a valid instance type.

Mixing the two schemes will make things more complicated than necessary, IMO.

I implemented the scheme I outlined and which is close to your idea. A PR will come shortly.

by adding the following rule: Before typing an implicit parameter list of a method m, instantiate all type parameters of m that occur in the type of some preceding value parameter of m.

smarter mentioned this issue Aug 5, 2015

Typer#escapingRefs: don't let the types of lower bounds escape #749

Merged

smarter mentioned this issue Aug 9, 2015

NamedPartsAccumulator: also include bounds of uninstantiated type variables #750

Closed

odersky mentioned this issue Aug 9, 2015

Change handling of tvars in implicits #752

Closed

smarter mentioned this issue Aug 10, 2015

Type parameters are instantiated too early in some cases #738

Closed

odersky added the stat:fix available label Aug 10, 2015

odersky closed this as completed in 493fbbd Oct 7, 2015

smarter mentioned this issue Dec 26, 2016

Fix #1857: Interpolate type variables before implicit search #1859

Closed

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Type parameters should be instantiated before doing an implicit search #739

Type parameters should be instantiated before doing an implicit search #739

smarter commented Jul 24, 2015

odersky commented Aug 6, 2015

retronym commented Aug 6, 2015

smarter commented Aug 6, 2015

retronym commented Aug 6, 2015

retronym commented Aug 6, 2015

retronym commented Aug 6, 2015

smarter commented Aug 6, 2015

smarter commented Aug 6, 2015

odersky commented Aug 6, 2015

odersky commented Aug 6, 2015

smarter commented Aug 6, 2015

odersky commented Aug 9, 2015

smarter commented Aug 9, 2015

odersky commented Aug 9, 2015

Type parameters should be instantiated before doing an implicit search #739

Type parameters should be instantiated before doing an implicit search #739

Comments

smarter commented Jul 24, 2015

odersky commented Aug 6, 2015

retronym commented Aug 6, 2015

smarter commented Aug 6, 2015

retronym commented Aug 6, 2015

retronym commented Aug 6, 2015

retronym commented Aug 6, 2015

smarter commented Aug 6, 2015

smarter commented Aug 6, 2015

odersky commented Aug 6, 2015

odersky commented Aug 6, 2015

smarter commented Aug 6, 2015

odersky commented Aug 9, 2015

smarter commented Aug 9, 2015

odersky commented Aug 9, 2015