Should there be protections against inferring non-covariant types?

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Should there be protections against inferring non-covariant types?

Owen
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Should there be protections against inferring non-covariant types?

Martin Odersky


On Fri, Sep 5, 2014 at 11:41 PM, Owen <[hidden email]> wrote:
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

Hubert Plocinicak has some interesting work, where he traces type errors back to the original cause, such as a too specific type inferred in a non-covariant context. I believe this has the potential to be used for better type error messages.

 - Martin


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



--
Martin Odersky
EPFL

--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Should there be protections against inferring non-covariant types?

Owen
That's interesting. I searched a bit for Hubert Plocinicak's work but haven't found it.

In this case, it looks like it would be enough to say "Scala will not use a method argument to infer a method parameter type that is later in the same method signature used in a non-covariant way". So for example in a definition of fold like

class List[+A] {
    def fold[B](b0: B)(f: (B, A) => B): B = ???
}

Both b0: B and f: (B, A) => B use B in a non-covariant way. Since f: (B, A) => B comes after b0: B, b0: B is not allowed to cause B to be inferred.

Likewise a definition like

class Set[T]
 
object Set {
  def apply[T](xs: T*): Set[T] = ???
}

the return type of apply uses T in a non-covariant way; so, xs is not allowed to cause T to be inferred.

Best,
Owen


On Fri, Sep 5, 2014 at 9:13 PM, martin odersky <[hidden email]> wrote:


On Fri, Sep 5, 2014 at 11:41 PM, Owen <[hidden email]> wrote:
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

Hubert Plocinicak has some interesting work, where he traces type errors back to the original cause, such as a too specific type inferred in a non-covariant context. I believe this has the potential to be used for better type error messages.

 - Martin


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



--
Martin Odersky
EPFL


--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Should there be protections against inferring non-covariant types?

Heather Miller
Here's an (old) draft of one of Hubert's papers on this topic: http://infoscience.epfl.ch/record/197948
It's got some informative examples in it. HTH


On Fri, Sep 5, 2014 at 7:05 PM, Owen <[hidden email]> wrote:
That's interesting. I searched a bit for Hubert Plocinicak's work but haven't found it.

In this case, it looks like it would be enough to say "Scala will not use a method argument to infer a method parameter type that is later in the same method signature used in a non-covariant way". So for example in a definition of fold like

class List[+A] {
    def fold[B](b0: B)(f: (B, A) => B): B = ???
}

Both b0: B and f: (B, A) => B use B in a non-covariant way. Since f: (B, A) => B comes after b0: B, b0: B is not allowed to cause B to be inferred.

Likewise a definition like

class Set[T]
 
object Set {
  def apply[T](xs: T*): Set[T] = ???
}

the return type of apply uses T in a non-covariant way; so, xs is not allowed to cause T to be inferred.

Best,
Owen


On Fri, Sep 5, 2014 at 9:13 PM, martin odersky <[hidden email]> wrote:


On Fri, Sep 5, 2014 at 11:41 PM, Owen <[hidden email]> wrote:
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

Hubert Plocinicak has some interesting work, where he traces type errors back to the original cause, such as a too specific type inferred in a non-covariant context. I believe this has the potential to be used for better type error messages.

 - Martin


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



--
Martin Odersky
EPFL


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



--
Heather Miller
Doctoral Assistant
EPFL, IC, LAMP

--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Should there be protections against inferring non-covariant types?

Martin Odersky
In reply to this post by Owen



On Sat, Sep 6, 2014 at 4:05 AM, Owen <[hidden email]> wrote:
That's interesting. I searched a bit for Hubert Plocinicak's work but haven't found it.

In this case, it looks like it would be enough to say "Scala will not use a method argument to infer a method parameter type that is later in the same method signature used in a non-covariant way". So for example in a definition of fold like

class List[+A] {
    def fold[B](b0: B)(f: (B, A) => B): B = ???
}

Both b0: B and f: (B, A) => B use B in a non-covariant way. Since f: (B, A) => B comes after b0: B, b0: B is not allowed to cause B to be inferred.

Likewise a definition like

class Set[T]
 
object Set {
  def apply[T](xs: T*): Set[T] = ???
}

the return type of apply uses T in a non-covariant way; so, xs is not allowed to cause T to be inferred.

I think that would be too constraining. People want to write

  Set(1, 2, 3)
  Array("a", "b")

 - Martin


Best,
Owen


On Fri, Sep 5, 2014 at 9:13 PM, martin odersky <[hidden email]> wrote:


On Fri, Sep 5, 2014 at 11:41 PM, Owen <[hidden email]> wrote:
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

Hubert Plocinicak has some interesting work, where he traces type errors back to the original cause, such as a too specific type inferred in a non-covariant context. I believe this has the potential to be used for better type error messages.

 - Martin


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



--
Martin Odersky
EPFL


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



--
Martin Odersky
EPFL

--
You received this message because you are subscribed to the Google Groups "scala-debate" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [hidden email].
For more options, visit https://groups.google.com/d/optout.
Reply | Threaded
Open this post in threaded view
|

Re: Should there be protections against inferring non-covariant types?

Owen
Hello all,

First, that is a wonderful paper. It would completely revolutionize the experience of programming Scala. Are there any plains to add those features to the main scala compiler?

But, back to the question of inferring contravariant types from positive values...

Yes, I suppose people do want to write `Array(1, 2, 3)` and `Set(1, 2, 3)` -- but should they? If a positive value produces the correct contravariant type, isn't it just a coincidence?

As for these two use cases... in pure Scala code `Array(1, 2, 3)` would more commonly be `Vector(1, 2, 3)`. What `Array(1, 2, 3)` is really good for is passing arrays to Java methods, since Java doesn't have covariant types. But in this case, if you have a method declared

    class JavaClass {
        def javaMethod(things: Array[Int])
    }

you can safely write `javaMethod(Array(1, 2, 3))` because the parameter type indicates the Array type argument.

`Set(1, 2, 3)` is trickier. Scala sets rely on the fact that `AnyRef` defines `equals()` and `hashCode()`. So, Scala sets could be covariant without creating unsound code:

    trait AnyRefSet[+T <: AnyRef] {
        def toSeq: Seq[T]
        def contains(x: AnyRef): Boolean
    }

In doing so, you give up the "oops, you're looking for something in the set that couldn't possibly be there -- bit of a waste of time, no?" check:

    val s = Set(1, 2, 3)
    s.contains("Hello") // Type error; this set couldn't possibly have strings in it.

But I wouldn't worry too much about that -- first, because again it's really just a coincidence:

    val s = Set(1, 2, Some(3))
    s.contains("Hello") // All OK.

and second because checking for futile elements doesn't lead to unsound code.

Traditional abstract sets are more recalcitrant because without the properties of `AnyRef` they are inherently invariant:

    trait Set[T] {
        def toSeq: Seq[T]
        def contains(x: t) : Boolean
    }

So, should their inherent invariance justify `Set(1, 2, 3)`? I do not think so. `Set(a, b, c)` relies on two properties of `a`, `b` and `c` -- their role as positive values, and their role as matchers:

    trait Thing[T] {
        val it: T
        def is(t: T): Boolean
    }

    case class Set[T](things: Seq[Thing[T]]) {
        def toSeq = things map (_.it)
        def contains(t: T) = things exists (_ is t)
    }

And you can see that it is neither sound to narrow a `Thing` to produce an invalid `it` nor to broaden it to leave `is` with a mistyped argument.

Besides, even in the case of a single element it can be unclear how to draw the bound:

    sealed trait Choice1
    sealed trait Choice2 extends Choice1
    case object TheChoice extends Choice2 with Thing[???]

More generally, I would say that `var x = 1` strays from being just type inference to being something more like type estimation, because it produces a solution for the type variable that isn't actually mandated by the code -- just hinted at by it. Now, that's not necessarily a bad thing. After all, programming languages are human-facing things, so raw logic doesn't have to be the only tool that guides the compiler. But I think if you're going to stray away from the security and trust of type inference, you should be careful that you do it in a way that's really solid, so that the language still provides a secure foundation to build on. Inferring contravariant types from positive values is clever in some cases, but I wouldn't call it solid, and that's why it ends up leaving people confused.

Best,
Owen

On Fri, Sep 5, 2014 at 10:26 PM, martin odersky <[hidden email]> wrote:



On Sat, Sep 6, 2014 at 4:05 AM, Owen <[hidden email]> wrote:
That's interesting. I searched a bit for Hubert Plocinicak's work but haven't found it.

In this case, it looks like it would be enough to say "Scala will not use a method argument to infer a method parameter type that is later in the same method signature used in a non-covariant way". So for example in a definition of fold like

class List[+A] {
    def fold[B](b0: B)(f: (B, A) => B): B = ???
}

Both b0: B and f: (B, A) => B use B in a non-covariant way. Since f: (B, A) => B comes after b0: B, b0: B is not allowed to cause B to be inferred.

Likewise a definition like

class Set[T]
 
object Set {
  def apply[T](xs: T*): Set[T] = ???
}

the return type of apply uses T in a non-covariant way; so, xs is not allowed to cause T to be inferred.

I think that would be too constraining. People want to write

  Set(1, 2, 3)
  Array("a", "b")

 - Martin


Best,
Owen


On Fri, Sep 5, 2014 at 9:13 PM, martin odersky <[hidden email]> wrote:


On Fri, Sep 5, 2014 at 11:41 PM, Owen <[hidden email]> wrote:
Everyone knows that inferring non-covariant types can be unreliable. It seems that this can trip up new-comers who don't realize that an explicit type might be needed to solve their problem:

Stack Overflow: Scala Map with Either


Other common examples are:

var x = 0
x += 0.5


List(1, 2, 3).foldLeft(None) { (a, b) => Some(b) }

Perhaps the compiler could warn or error in these situations?

Hubert Plocinicak has some interesting work, where he traces type errors back to the original cause, such as a too specific type inferred in a non-covariant context. I believe this has the potential to be used for better type error messages.

 - Martin


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



--
Martin Odersky
EPFL


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



--
Martin Odersky
EPFL


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