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

@adriaanm said (edited on Jan 24, 2012 4:04:41 PM UTC):
with Paul's recent experiments of priming type vars with the parameter's bounds, maybe a tweak to how we compute the "direction" in which we solve type vars based on the variance positions in which they occur could suffice for inferring Bar instead of Nothing in code like:

def foo[T <: Bar]: T = ...
foo // Nothing inferred, could infer Bar

@Blaisorblade said (edited on Jan 26, 2012 4:44:04 PM UTC):
Hi,
I don't understand whether fixing that example would also fix the code I reported.
Maybe I'm being dense here, but my code is more similar to:

def foo[A, B <: Traversable[A]](base: B) = null
foo(List(1))

which gives:

<console>:9: error: inferred type arguments [Nothing,List[Int]] do not conform to method foo's type parameter bounds [A,B <: Traversable[A]]
              foo(List(1))
              ^

there, the problem is in deducing A which is on the right of a subtype constraint. Of course, I'm not sure it makes a difference, that's why I'm asking.

Additionally, Scala's specification request that a constraint system be used for local type inference (Sec. 6.26.4), but according to the specification, both this example with foo and the example you posted should be valid - i.e. it seems that an appropriate substitution exists and that a constraint system should be able to find it. Is that strategy actually implemented?

@adriaanm said:
You're right. That's a separate problem. Type vars that depend on other type vars are not supported well. I'm not sure that can be fixed ( without major changes to the algorithm)

@Blaisorblade said:
I see... but am I also right in my suspicion that the implementation doesn't match the spec?
Anyway, I did propose a workaround for the example I suggested, even if I guess it is a hack and it probably has limitations.

@adriaanm said:
Type inference is not spec'ed, essentially. It's also not that easy to improve it without breaking existing code. We are certainly interested in improving it overall, but I hesitate to add an ad-hoc hack for this case. It needs to be an all-encompassing improvement, with assurances about the effect on existing code, understandability,... That's not going to happen right away. It's just too hard, sorry.

• Posted from Bugbox for iPhone

@Blaisorblade said:
That's fine; understandability is an especially big problem currently. For me, the amount of problems with type inference + implicits which I can neither report (for lack of time) nor fully understand (so as to avoid them) is very high (I am currently working on something similar to Delite).
Anyway, it's important to know that you're interested in improving that.
Thanks!

@Blaisorblade said:
I've just realized a new side of this issue, which might or might not be solved by your new virtualized pattern-matcher. Type bounds are also ignored by "GADT-like type inference", but the above workaround helps there too. Can you add this to your testcases, if that's relevant for the changes you're doing?

To wit, here's an example REPL session, with the above definitions in scope:

scala> (_: Any) match {
     | case View1(base) => base.map(identity)
     | }
<console>:12: error: value map is not a member of Any
              case View1(base) => base.map(identity)
scala>  (_: Any) match {
     | case ViewNoTypeAnnotWorkingInference(base) => base.map(identity)
     | }
<console>:12: error: Cannot construct a collection of type That with elements of type Any based on a collection of type Any.
              case ViewNoTypeAnnotWorkingInference(base) => base.map(identity)
//Slightly better, but implicit search got confused. However, base has type TraversableLike, maybe that's the problem...
scala> case class ViewNoTypeAnnotWorkingInference[T, Repr <:  TraversableLike[T, Repr] with Traversable[T]](base: Repr with TraversableLike[T, Repr] with Traversable[T]) {
     | def copy(base: Repr) = ViewNoTypeAnnotWorkingInference(base)
     | }
defined class ViewNoTypeAnnotWorkingInference

scala> (_: Any) match {
     | case ViewNoTypeAnnotWorkingInference(base) => base.map(identity)
     | }
res4: Any => Traversable[Any] = <function1>

Now I'm going to clutter my case classes definitions with this trick and unclutter my pattern matching code :-)

@paulp said:
Maybe I'm missing something, but it looks like there's a simpler route available which accomplishes the same thing.

scala> case class CC[Repr <: Traversable[_]](base: Repr) { def copy(base: Repr) = CC(base) }
defined class CC

scala> CC(List(1,2,3))
res0: CC[List[Int]] = CC(List(1, 2, 3))

scala> res0.copy(Set(1,2,3))
<console>:11: error: type mismatch;
 found   : scala.collection.immutable.Set[Int]
 required: List[Int]
              res0.copy(Set(1,2,3))
                           ^

scala> CC(Map(1 -> 2))
res2: CC[scala.collection.immutable.Map[Int,Int]] = CC(Map(1 -> 2))

scala> res2.copy _
res3: scala.collection.immutable.Map[Int,Int] => CC[scala.collection.immutable.Map[Int,Int]] = <function1>

@Blaisorblade said (edited on Jul 4, 2012 1:45:47 PM UTC):
I guess I should be more clear about what I'm trying to accomplish - it seems that I reduced the code too much. Paul, your idea works in this example, but in the full code T must be bound in the body, so your workaround is not general enough. Thanks anyway!

Why do I need T? I'm unable to explain that without a slightly more complex example from my research project, which I present in the rest of this comment. Sorry for the length, I already spent some time trying to simplify the code. Feel free to skip the rest.

[Some of you, say Adrian Moors, will recognize below some similarities with Lightweight Modular Staging, Delite, Scala Integrated Query and all that stuff; I have a paper draft which discusses the differences, should you care.]

In my project, among tons of other things I manipulate ASTs representing programs on collection. The above code derives from the AST node representing Traversable.view.
Let's try to represent an AST node for a map operation; it should also contain ASTs for its subnodes, so that clients can examine the whole expressions. An AST for an expression of type T has type Exp[T] in this setup. To keep it simple, I'll first show such a node on lists, where binding T is already required. Also, let's make things more interesting: these nodes should be well-typed, and I want to write an interpreter for them; moreover I want to use the Scala typesystem to also prove that this interpreter is type-correct.

trait Exp[+T] {
  def interpret(): T
}
case class ListMapNode[T, U](coll: Exp[List[T]], mapping: Exp[T => U]) extends Exp[List[U]] {
  def interpret(): List[U] = coll.interpret() map mapping.interpret()
}

Note that mapping can be applied to the collection only because T appears in both. Otherwise, I'd need to use casts which might fail at runtime.

Writing the code above is not a problem since it is restricted to lists, but that restriction is stupid: I want to manipulate programs using any collection, I want a single node to represent map on all of them, and I want the result to be as precise. The type of this node will therefore be at least as complex as the type of map; here's the minimal version:

case class MapNode[T, Repr <: TraversableLike[T, Repr],
                   U, That](base: Exp[Repr], f: Exp[T => U])
                          (implicit val c: CanBuildFrom[Repr, U, That]) extends Exp[That] {
  def interpret() = base.interpret() map f.interpret()
  def copy(base: Exp[Repr], f: Exp[T => U]) = MapNode[T, Repr, U, That](base, f)
}

[The copy method is needed for transformations.]
This example requires both T and Repr in its body, even to typecheck interpret(). If I use wildcards instead of T, I get this code, which is rightfully rejected by the REPL - the two wildcards might refer to different types, so they aren't compatible.

case class MapNode[Repr <: TraversableLike[_, Repr],
                   U, That](base: Exp[Repr], f: Exp[_ => U])
                          (implicit val c: CanBuildFrom[Repr, U, That]) extends Exp[That] {
  def interpret() = base.interpret() map f.interpret()
}

<console>:25: error: type mismatch;
 found   : _$2 => U where type _$2
 required: Any => ?
         def interpret() = base.interpret() map f.interpret()
                                                           ^

If I now try to write type-safe transformations on these ASTs, this bug gets even more annoying, but I won't go into the details. I'll just say that it's because of those details that my code is even crazier.
If you want to see what I try to write as client code, take a look at this attempt to write a type-safe transformation; in the end I managed, but only with a lot of manual type annotations.

@paulp said:
Funny, I've been working on this pretty much exactly in my attempt to rewrite views. I have spent a lot of time on this sort of thing, and I am hip to the obstacles you have enjoyed. Funny how we both came to the conclusion we'd be better off with a constraint solver in there... enough trials and enough errors will do that.

I recently managed to hack my way to seeing Coll inferred correctly here:

def f[A, CC[X] <: Traversable[X], Coll <: CC[A]](xs: Coll) = xs

I have to get back to that code, it's in a tributary somewhere.

@Blaisorblade said:
Since you worked on similar code, here's a question: have you tried doing map fusion - that is, rewrite "coll map f map g" to "coll map (f andThen g)"? That's the example I linked to at the end, and making that typecheck is surprisingly hard. And that's the simplest optimization I have, so I've given up on typechecking for now.

Your solution looks interesting - I thought for a second that it would work on vanilla Scala, but it doesn't (not on 2.9.2, nor on the latest 2.10 snapshot I have, from mid-June):

scala> def f[A, CC[X] <: Traversable[X], Coll <: CC[A]](xs: Coll) = xs
f: [A, CC[X] <: Traversable[X], Coll <: CC[A]](xs: Coll)Coll

scala> f(List(1))
<console>:9: error: inferred kinds of the type arguments (Nothing,List[Int],List[Int]) do not conform to the expected kinds of the type parameters (type A,type CC,type Coll).
List[Int]'s type parameters do not match type CC's expected parameters: class List has one type parameter, but type CC has one
              f(List(1))
              ^

If you have a Scalac compiler supporting such crazy code, I'd be delighted to try it out :-). The error message above also seems related to #5075/#2712.
Still, I'll probably need to have TraversableLike in the bound. Why? Code like this is (subtly?) wrong:

def f[A, CC[X] <: Traversable[X], Coll <: CC[A], That](xs: Coll)(implicit cbf: CanBuildFrom[Coll, A, That]): That = xs map (x => x)

Unless you have TraversableLike in your bound (Coll <: TraversableLike[A, Coll]), the result type will be in fact Traversable[A] - the typechecker is right about that. Writing CC[X] also doesn't fit so nicely with non-unary constructors, say Map[K, V]: CC would be Iterable there (if Scalac manages to find the solution), and Coll != CC[A] is rather annoying.

@paulp said:
No, by "hack my way to" I meant "I fairly extensively modified the compiler until it correctly inferred the types of this method declaration." And by "it's in a tributary somewhere" I meant "it's in a git branch on one of my machines and at the moment I don't know more than that."

Seems unlikely to progress in Scalac (Adriaan already said as much), the sample is currently illegal in Dotty because of the overriding/shadowing of copy methods.

I think closing issues like this is premature. I think we can make progress on inference bugs in Scala 2.

@milessabin Paolo wrote, "the sample is currently illegal in Dotty because of the overriding/shadowing of copy methods" — can you address that? what is the path forward here that you see?

That comment of mine was honestly lazy, the other examples in this ticket don’t depend on copy;
#5298 (comment) and the next comment are more interesting, and now I wonder if scala/scala3#4059 is related to the same question.

More specifically: according to Martin's explanation of interpolation, Dotty's inference will (at some "strictness point") loop over uninstantiated variables and instantiate them to some bound, usually trying to infer the most specific type for a method (though solutions must be heuristic here, as long as type inference stays local rather than global). So IIUC for foo you'll still get Nothing, but for bar you'll get Bar, because T appears in opposite variances:

def foo[T <: Bar]: T = ...
foo // Nothing inferred, could infer Bar
def bar[T <: Bar](x: T): Any = ...
bar _ //infers T = Bar to minimize the return type

On my other example:

def foo[A, B <: Traversable[A]](base: B) = null

You're right. That's a separate problem. Type vars that depend on other type vars are not supported well. I'm not sure that can be fixed (without major changes to the algorithm)

I think that comment stands, and Dotty uses indeed a different algorithm — I think its subtype constraint solver can handle this well.

==

@milessabin I had forgot, but the real argument for closing was Adriaan's:

Type inference is not spec'ed, essentially. It's also not that easy to improve it without breaking existing code. We are certainly interested in improving it overall, but I hesitate to add an ad-hoc hack for this case. It needs to be an all-encompassing improvement, with assurances about the effect on existing code, understandability,... That's not going to happen right away. It's just too hard, sorry.

Here, scala/scala3#4059 exemplifies the kind of breakage you risk. We don't search for a solution over the whole search space, so inference is incomplete (and changing that still seems unfeasible, though who knows what Martin comes up with tomorrow), and sometimes (like here) it does arbitrary choices, which might trigger errors. If those choices don't match Scalac's (and they can't easily since the algorithms are so different), some existing code will stop working (while some code that currently fails might start working — but that won't affect existing and used code).

I'm not persuaded by councils of despair. I think that, as you've observed elsewhere, the main obstacle to fixing some of these issues is deciding to fix them ... I think that applies here to. Some work here is probably relevant to this ticket too: scala/scala#6127.