Order of implicit arguments matters, so turning an implicit parameter into a context bound breaks implicit resolution #7054

scabug · 2013-01-31T23:00:39Z

Below I show two lines of code which should be equivalent but aren't - implicit resolution has issues on the first. The workaround was simply to desugar the context bound That: Man into an implicit parameter - hence I would say that this is a bug. -Xprint:typer suggest that this bug will stay open for long, as explained below.

Non-working version:

def map[B:Man, That:Man](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That]): Exp[That]

Working version:

def map[B:Man, That](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That], m: Man[That]): Exp[That]

Note that the two lines desugar into different things: the order of implicit parameters is different.
The first desugars to:

def map[B >: Nothing <: Any, That >: Nothing <: Any](f: BugMan.Exp[A] => BugMan.Exp[B])(implicit evidence$6: BugMan.Man[B], evidence$7: BugMan.Man[That], foo: BugMan.CanBuild1[B,That]): BugMan.Exp[That] = scala.sys.`package`.error("TraversableOps1.map")
//Call site:
new BugMan.TraversableOps1[Int]()(BugMan.this.man[Int]).map[Int, List[Int]](((x: BugMan.Exp[Int]) => x))(BugMan.this.man[Int], BugMan.this.man[Nothing], BugMan.this.canBuildList1[Int](BugMan.this.man[Int]));

Note that That is deduced from the last parameter and used before.
The second example desugars to:

def map[B >: Nothing <: Any, That >: Nothing <: Any](f: BugMan.Exp[A] => BugMan.Exp[B])(implicit evidence$9: BugMan.Man[B], foo: BugMan.CanBuild1[B,That], m: BugMan.Man[That]): BugMan.Exp[That] = scala.sys.`package`.error("TraversableOps1.map")
//Call site:
new BugMan.TraversableOps2[Int]()(BugMan.this.man[Int]).map[Int, List[Int]](((x: BugMan.Exp[Int]) => x))(BugMan.this.man[Int], BugMan.this.canBuildList1[Int](BugMan.this.man[Int]), BugMan.this.man[List[Int]])

Complete example and error message below.

The error message mentions Nothing, as if type inference hadn't fully happened. In fact, this code would require the different implicits to be in different parameter lists - or failing that, scalac should do type inference across a single parameter list, the kind of thing which it consciously refuses to do for e.g. non-curried fold methods. Given that the second thing is not going to happen soon, I'd mention again my proposal for multiple implicit parameter lists:

http://blaisorbladeprog.blogspot.de/2013/01/flexible-implicits-from-agda-for-scala.html

Note that if instead of a generic Man I use Manifest (as I was doing before reducing the example), the error message is completely different - it claims another implicit is missing, of type CanBuild1[Int,That] - as if That hadn't yet been deduced.

object BugMan {
  class Man[T]
  implicit def man[T] = new Man[T]

  class Exp[A:Man]
  class CanBuild1[B:Man, That:Man]
  implicit def canBuildList1[A:Man] = new CanBuild1[A, List[A]]
  //Fails:
//  /*
  class TraversableOps1[A:Man] {
    def map[B:Man, That:Man](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That]): Exp[That] = sys error "TraversableOps1.map"
  }
  for { x <- new TraversableOps1[Int] } yield x
//  */
  class TraversableOps2[A:Man] {
    def map[B:Man, That](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That], m: Man[That]): Exp[That] = sys error "TraversableOps1.map"
  }
  for { x <- new TraversableOps2[Int] } yield x
}

object BugManifest {
  class Exp[A:Manifest]
  class CanBuild1[B:Manifest, That:Manifest]
  implicit def canBuildList1[A:Manifest] = new CanBuild1[A, List[A]]
  //Fails:
//  /*
  class TraversableOps1[A:Manifest] {
    def map[B:Manifest, That:Manifest](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That]): Exp[That] = sys error "TraversableOps1.map"
  }
  for { x <- new TraversableOps1[Int] } yield x
//  */
  class TraversableOps2[A:Manifest] {
    def map[B:Manifest, That](f: Exp[A] => Exp[B])(implicit foo: CanBuild1[B, That], m: Manifest[That]): Exp[That] = sys error "TraversableOps1.map"
  }
  for { x <- new TraversableOps2[Int] } yield x
}

Scalac's lament:

bugReport.scala:14: error: type mismatch;
 found   : BugMan.Man[Nothing]
 required: BugMan.Man[List[Int]]
Note: Nothing <: List[Int], but class Man is invariant in type T.
You may wish to define T as +T instead. (SLS 4.5)
  for { x <- new TraversableOps1[Int] } yield x
          ^
bugReport.scala:31: error: could not find implicit value for parameter foo: BugManifest.CanBuild1[Int,That]
  for { x <- new TraversableOps1[Int] } yield x
          ^
two errors found

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

scabug · 2013-01-31T23:00:39Z

Imported From: https://issues.scala-lang.org/browse/SI-7054?orig=1
Reporter: @Blaisorblade
Affected Versions: 2.10.0

scabug · 2014-05-01T09:00:32Z

Barnabás Králik (kralikba) said:
Dear Devs,

What are Your comments on this? Does it have concrete causes that the context bounds are desugared into implicits that are at the beginning of the implicit parameter list? If not, this small change would make code clearer.

scabug · 2014-05-01T13:19:58Z

@Blaisorblade said:
IIUC, with the change you propose, Scalac would desugar context bounds into implicits at the end of the list.

This change might cause regressions when the opposite order is better, so it's not obvious it is an improvement. But I know no concrete instance, so there might be some non-obvious reason this regression is impossible.

In fact, context bounds are always desugared to implicit params with a single type parameter (TypeConstructor[T], rather than TypeConstructor[T, U]), so I can't exclude that they are easier to infer and they can be moved at the end. But I see no good argument there.

Failing that, I don't see how this can be easily improved.

scabug · 2014-05-01T13:21:05Z

@Blaisorblade said:
I fixed the title with a better description — "desugaring bug" made little sense even to me.

scabug · 2014-05-01T18:30:04Z

Barnabás Králik (kralikba) said (edited on May 1, 2014 6:30:26 PM UTC):
bq. so I can't exclude that they are easier to infer and they can be moved at the end.

The problem - as I see it - is not the inference of itself the implicit, but the inference of the type parameter of a context bound. As far as I have understood, the context bound places a restriction on the type parameter - whereas implicit parameters might help in actually inferring a type parameter. Suppose the following:

class A[X,Y]
class B; class C
implicit val a = new A[B,C]
def f[U,V : Manifest](u : U)(implicit ax : A[U,V]) = ...

The intention of the programmer would be:

get me a V for which an implicit A[U,V] exists. Do not let V be such that Manifest\[V] does not have an implicit associated

However, the signature of f tells the type inference engine that:
there are two type parameters, U and V. U is the type of u. Please fetch some kind of V for which an implicit Manifest exists. Now, please fetch me an A\[U,V].

The algorithm here chooses Nothing as the smallest type for which a Manifest exists; but A[U,Nothing] does not exist for any U as an implicit. Thus, f(new B) will fail with "implicit not found" in spite of V =:= C being a perfectly sensible choice.

One would need to write:

def f[U,V](u : U)(implicit ax : A[U,V], m  : Manifest[V]) = ...

to let both implicits be correctly guessed.

I would argue that something called a "bound" should not make the type inference engine make any guess about the type and then keep to it. Imagine if an upper type bound would make type inference assume that if the type parameter is not explicitly specified, then it must be itself the upper bound.

scabug · 2014-05-02T05:54:33Z

@retronym said:
It is extrememly hard to change the desugaring of context bounds now, as it is likely to break inference in some programs.

scabug · 2014-05-02T09:40:39Z

@Blaisorblade said (edited on May 2, 2014 9:44:41 AM UTC):

As far as I have understood, the context bound places a restriction on the type parameter - whereas implicit parameters might help in actually inferring a type parameter.

The problem is that they help "too much" — indeed, also implicit parameters should simply be constraints.
I agree that implicit/type inference violates some intuitive expectations; the problem is that making it more predictable is (AFAIK) a hard research problem. Moreover, it would probably change behavior in some cases, so it would be hard to push this in for Scala 2. I'm hoping that Dotty might help here.
(But I'm just a contributor).

scabug · 2014-05-02T10:31:40Z

Barnabás Králik (kralikba) said:
I absolutely agree with this; currently we are discussing half-solutions to a sub-question of a quite hard problem.

bq. the problem is that making it more predictable
What do you mean by inference not being predictable?

bq. (AFAIK) a hard research problem
Do you have any specific ongoing research in mind?

bq. Moreover, it would probably change behavior in some cases, so it would be hard to push this in for Scala 2.

What comes to my mind are cases where implicits are explicitly passed; the order of parameters matters here a lot and mixing them up might sometimes cause bugs only detected at run time.

Maybe a less intrusive patch that should not break existing code and not result in the complete rewrite of the inference algorithms could be proposed along the lines of the following:

Annotate context bound-generated evidences with @weakEvidence
Iff the language feature weakEvidences is enabled, let the inference algorithm consider the un-annotated parameters first.
If the language feature is turned off and implicit resolution ultimately fails but turning it on would work, a compiler hint could be given.

scabug · 2014-05-02T10:58:18Z

@retronym said:
I'd say if you want full control over the order of implicit parameters, you would need to write them explicitly. The desugaring happens in the parser, before we are able to typecheck annoations to or feature imports.

scabug · 2014-05-02T12:07:47Z

@Blaisorblade said (edited on May 2, 2014 12:19:08 PM UTC):
@barnaBás Králik, I'm not sure I can add something on your proposal. (I hadn't seen Jason Zaugg's latest answer).

What do you mean by inference not being predictable?

Take an arbitrary Scala program requiring type/implicit inference to fill in some blanks. Can you predict whether Scalac will manage to do such inference? I know nobody who can. There are many other questions whose answer should be predictable and isn't.

For instance, Dunﬁeld and Krishnaswami write, in a type inference paper for a different language (without subtyping):
"We want to relieve programmers from having to write redundant type annotations, and even more importantly, enable programmers to easily predict where type annotations are needed." (Sec. 2.3, Robustness of Typing; the paper lives at http://arxiv.org/pdf/1306.6032.pdf, http://dl.acm.org/citation.cfm?id=2500582). Some theorems in that section state that some simple refactorings keep type inference working. (However, those theorems are hard to prove).

For instance, imagine the statement "if you change the order of implicit parameters in a function declaration, it will still be possible to infer implicit parameters for every call site where it was possible before". If this were a theorem for Scala type inference, this bug would not show up. That's why I titled the bug "Order of implicit arguments matters".

However, that paper contains a 70-page appendix of proofs, and the Scala type system is bigger and more complex, so it's not easy to extend their work to Scala — it would be another research effort. So, I don't have "specific ongoing research in mind", but maybe this research is happening as part of the Dotty project. But I would expect quite some improvements to be possible.

scabug · 2014-05-02T12:26:54Z

@Blaisorblade said:
Jason, note that the annotation would be produced by the desugaring, not consumed by it, so your objection does not apply. The strategical question is whether you want to provide knobs for implicit/type inference, via annotations to be used by the desugaring (and arguably also by users). I suspect this is not worth it.

Jason, does it make sense to close this as Won't Fix for Scala 2, since nobody plans to rewrite Scalac inference algorithm?

scabug · 2014-05-02T13:20:12Z

@retronym said:
Oh I misread that proposal, I though the annotation was to be attached by the user to the context bound.

Given that context bounds are a convenience feature only, and writing the implicit arguments offers a workaround when full control is needed, I do think this is a wont-fix.

scabug closed this as completed May 2, 2014

scabug added won't fix infer implicit implicits labels Apr 7, 2017

scabug assigned retronym Apr 7, 2017

adriaanm added implicit and removed implicit implicits labels Apr 7, 2017

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Order of implicit arguments matters, so turning an implicit parameter into a context bound breaks implicit resolution #7054

Order of implicit arguments matters, so turning an implicit parameter into a context bound breaks implicit resolution #7054

scabug commented Jan 31, 2013 •

edited by retronym

scabug commented Jan 31, 2013

scabug commented May 1, 2014

scabug commented May 1, 2014

scabug commented May 1, 2014

scabug commented May 1, 2014 •

edited by retronym

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

Order of implicit arguments matters, so turning an implicit parameter into a context bound breaks implicit resolution #7054

Order of implicit arguments matters, so turning an implicit parameter into a context bound breaks implicit resolution #7054

Comments

scabug commented Jan 31, 2013 • edited by retronym

scabug commented Jan 31, 2013

scabug commented May 1, 2014

scabug commented May 1, 2014

scabug commented May 1, 2014

scabug commented May 1, 2014 • edited by retronym

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented May 2, 2014

scabug commented Jan 31, 2013 •

edited by retronym

scabug commented May 1, 2014 •

edited by retronym