Inferring List[Any]

[Blaisorblade]

While talking about a List(1, "X", 2.0) which was inferred to be List[Any] but was a bug, @paulp wrote in #1:

@Blaisorblade If you have to tell the compiler so the compiler can tell you, I suggest cutting out the middleman.

I see why here (and probably elsewhere) inferring List[Any] is inconvenient.

We should certainly consider a warning for this, and even @paulp's idea of not inferring Any: this is what this issue should be about.

[Blaisorblade]

I'm uncomfortable with the original suggestion of never inferring Any, because it's irregular, and most Scala irregularities are agreed to be bugs. I'd need to try out a compiler like that before agreeing the idea is good.

What should be the result type of this list? Is it intended to be List[X], or is there a bug?

sealed trait X
case class A(a: Int) extends X
case object B extends X
case object C extends X

List(A(1), B, C)

Similar examples can be repeated at various levels of the hierarchy. You can try to guess what the programmer meant by letting the list members "vote" (so that in List(A(1), A(2), .... A(n), B), B is rejected because the list should be List[A], not List[X]), but that seems a hack.

So in general, you will need some annotations at some point.

This problem arises also because ADTs are encoded by reusing subtyping. So a cleaner design to avoid this problem is to avoid this conflation altogether: ML-like languages have subtyping, but limit it to the module system. I imagine Robert Harper would point this out. I remember also @pchiusano disliked subtyping — is this an argument against subtyping that you like as well, @pchiusano?

I think this difficulty is related with this quote from PFPL:

Subtyping is perhaps the most widely misunderstood concept in programming languages. Subtyping is principally a convenience, akin to type inference, that makes some programs simpler to write. But the subsumption rule cuts both ways. Inasmuch as it allows the implicit passage from τ′ to τ whenever τ′ is a subtype of τ, it also weakens the meaning of a type assertion e : τ to mean that e has some type contained in the type τ. This precludes expressing the requirement that e has exactly the type τ, or that two expressions jointly have the same type. And it is precisely this weakness that creates so many of the difficulties with subtyping.

I agree subtyping is annoying here; but limiting subtyping does have its downsides (and it wouldn't be Scala). So maybe we have to take a non-clean solution for convenience here. But I can't help hoping for some cooler idea here.

Still, a warning for inferred Anys would IMHO be appropriate. It might have to be optional for the sake of -Xfatal-warnings, but support for that is coming.

[paulp]

You're late to this party:

% scala -Ywarn-infer-any
Welcome to Scala version 2.11.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_20).
Type in expressions to have them evaluated.
Type :help for more information.

scala> List(1, "a")
<console>:8: warning: a type was inferred to be `Any`; this may indicate a programming error.
              List(1, "a")
                   ^
res0: List[Any] = List(1, a)

[jdegoes]

I'd love data Foo(...) being shorthand for something like @NonInferrable final case class Foo(...), think it would generally solve the ADT encoding issue without abandoning subtyping, per se.

Also as has been pointed out, not inferring Any doesn't solve any real problems, as Serializable or some other common supertype will be inferred. Don't add more irregularities!

[paulp]

Any is just the most visible, yes, but the list doesn't go on forever. What good is it to infer Serializable? After Serializable and Product, which we can view as artifacts of the implementation, what type is going to be the lub with any frequency?

[paulp]

Or maybe you're in the club of AnyVal lovers. Not sure that's a real club.

scala> List(1, true)
<console>:8: warning: a type was inferred to be `AnyVal`; this may indicate a programming error.
              List(1, true)
                   ^
res0: List[AnyVal] = List(1, true)

[jdegoes]

Well, if you don't infer Serializable and Product, you've eliminated some bad cases but more will occur in user-defined type hierarchies (although at least users have control over this to some degree)

To solve it in a user-defined manner, you might need something like "top limit" and "bottom limit" annotations that prevent type inference from inferring a less specific type than something annotated with "top limit", or a more specific type than something annotated with "bottom limit".

[Blaisorblade]

@NonInferrable

@jdegoes, I love that! We can add syntactic sugar on top, but adding that annotation sounds like a great improvement.

You still need to guess where to put it, and some occurrences are in the standard library, but hey, a library is of course entitled to have ad-hoc code — that's much better than the compiler. And users could add that flag.

Personally, I'm happy with @NonInferrable on all the examples Paul mentioned (Any, AnyVal, Serializable, Product). Per #14, this flag would have to be honored under some -Zhonor-NonInferrable.

To solve it in a user-defined manner, you might need something like "top limit" and "bottom limit" annotations that prevent type inference from inferring a less specific type than something annotated with "top limit", or a more specific type than something annotated with "bottom limit".

I'm not sure yet that's an improvement. Some examples where you need these more complex annotations?

[puffnfresh]

We should be able to add just an annotation without requiring a flag.

And yes, I really want a NonInferrable annotation.

[jdegoes]

I'm not sure yet that's an improvement. Some examples where you need these more complex annotations?

Bottom limit is equivalent in power to @NonInferrable, but you might use a "top limit" annotation on the trait that unifies the non-inferrable case class children. This would prevent Scala from inferring any supertype of the specified trait.

e.g.

sealed trait Node

@InferrableTop
sealed trait Decl extends Node

@NonInferrable
final case class FnDecl(...) extends Node

@InferrableTop
sealed trait Expr extends Node

@NonInferrable
final case class Mul(...) extends Expr

Thus, things like, List(Mul(...), FnDecl(...)) would be an error, while List(Mul(...)) would be inferred to List[Expr].

[Blaisorblade]

@jdegoes: Sounds interesting, but let's move to #17 :-).

[stanch]

I know it’s probably not merge-compatible or fully existing, but what happened to this @paulp? https://groups.google.com/d/topic/scala-language/J8LpYDmrOCg/discussion

val x = List(1, "X", 2.0)
x: List[Int|String|Double] = List(1, X, 2.0)

[paulp]

No idea. I burned hundreds of branches. My comments in that thread are pretty good I think, and they will have to serve as my legacy.