Hopefully the last time I am to ring the big unsoundness bell

[Paul Phillips]

The thrill is completely gone, don't worry. I found this the usual way: fix a bug only to discover that a) the bug was creating unsoundness and b) the standard library depends on the unsoundness.

The library compilation failure, after fixing the bug:

% ./build/quick/bin/scalac src/actors/scala/actors/remote/Proxy.scala 

src/actors/scala/actors/remote/Proxy.scala:163: error: type mismatch;

 found   : scala.actors.Channel[a]

 required: scala.actors.OutputChannel[Any]

          sessionMap.get(ch) match {

                         ^

one error found

The soundness failure thus revealed:

trait Covariant[+A]

trait Contra[-A] { def accept(p: A): Unit }

trait Invariant[A] extends Covariant[A] with Contra[A]

case class Unravel[A](m: Contra[A], msg: A)

object Test extends Covariant[Any] {

  def g(m: Contra[Any]): Unit = m accept 5

  def f(x: Any): Unit = x match {

    case Unravel(m, msg) => g(m)

    case _               =>

  }

  def main(args: Array[String]): Unit {

    f(Unravel[String](new Contra[String] { def accept(x: String) = x.length }, ""))

  }

}

// java.lang.ClassCastException: java.lang.Integer cannot be cast to java.lang.String

//   at Test$$anon$1.accept(a.scala:18)

//   at Test$.g(a.scala:13)

//   at Test$.f(a.scala:15)

//   at Test$.main(a.scala:18)

//   at Test.main(a.scala)

[Adriaan Moors]

Were you improving my original fix for https://issues.scala-lang.org/browse/SI-6680, by any chance?

[Adriaan Moors]

(Sorry, by "original fix" I meant "attempted fix")

[Paul Phillips]

On Mon, Sep 30, 2013 at 12:04 PM, Adriaan Moors <adriaa...@typesafe.com> wrote:

Were you improving my original fix for https://issues.scala-lang.org/browse/SI-6680, by any chance?

Not on purpose: I was chasing down this.

       // TODO: fix the illegal type bound in pos/t602 -- type inference messes up before we get here:

       /*override def equals(x$1: Any): Boolean = ...

              val o5: Option[com.mosol.sl.Span[Any]] =  // Span[Any] --> Any is not a legal type argument for Span!

       */

      

[Paul Phillips]

Here it is in pull request form: https://github.com/scala/scala/pull/3005

[Paul Phillips]

Looks like it picks off SI-6680 as well.

[Paul Phillips]

On Mon, Sep 30, 2013 at 12:18 PM, Paul Phillips <pa...@improving.org> wrote:

Looks like it picks off SI-6680 as well.

Actually just a subset of the examples in that ticket.

[martin odersky]

On Mon, Sep 30, 2013 at 8:49 PM, Paul Phillips <pa...@improving.org> wrote:

The thrill is completely gone, don't worry. I found this the usual way: fix a bug only to discover that a) the bug was creating unsoundness and b) the standard library depends on the unsoundness.

I believe that's the problem discovered by Paolo Giarruso, presented in his talk at the last Scala workshop:

  "Open GADTs and Declaration-site Variance: A Problem Statement"

I also believe the right fix is to change pattern matching to infer GADT-style typed only for non-variant parameters. 

Cheers

 - Martin

 

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

--

Martin Odersky
Prof., EPFL and Chairman, Typesafe
PSED, 1015 Lausanne, Switzerland
Tel. EPFL: +41 21 693 6863
Tel. Typesafe: +41 21 691 4967

[Paul Phillips]

55 errors in the standard library. Maybe all legit. Here's an example, reduced version of TailCalls. 

object TailCalls {

  case class Call[A](rest: () => TailRec[A]) extends TailRec[A]

  case class Done[A](value: A) extends TailRec[A]

  case class Cont[A, B](a: TailRec[A], f: A => TailRec[B]) extends TailRec[B]

  abstract class TailRec[+A] {

    final def flatMap[B](f: A => TailRec[B]): TailRec[B] = this match {

      case Done(a)    => Call(() => f(a))

      case c@Call(_)  => Cont(c, f)

      case Cont(s, g) => Cont(s, (x:Any) => g(x).flatMap(f)) // !!! (x: Any) => g(x) ?

    }

  }

}

[Paul Phillips]

On Mon, Sep 30, 2013 at 1:24 PM, martin odersky <martin....@epfl.ch> wrote:

I also believe the right fix is to change pattern matching to infer GADT-style typed only for non-variant parameters. 

...and invariant in every base type? If you can view a Sub[A] as a Super[+A] then it all comes back.

[martin odersky]

Yes, probably.

Can you give an example how not doing so would break things?

Thanks

 - Martin 

--  

You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Mon, Sep 30, 2013 at 1:45 PM, Paul Phillips <pa...@improving.org> wrote:

      case Cont(s, g) => Cont(s, (x:Any) => g(x).flatMap(f)) // !!! (x: Any) => g(x) ?

By the way, that line can be written with less unsoundness

  case c: Cont[a1, b1] => Cont(c.a, (x: a1) => c f x flatMap f)

It seems we still don't have this:

  case Cont[a1, b1](c, g) => ...

It makes it past the parser, but then dies in confusion.

[Paul Phillips]

On Mon, Sep 30, 2013 at 1:53 PM, martin odersky <martin....@epfl.ch> wrote:

Can you give an example how not doing so would break things?

trait Super[+A]

case class Sub[B](f: B => B) extends Super[B]

object Test extends App {

  val s1 = Sub((x: Int) => x)

  (s1: Super[Any]) match { case Sub(f) => f("abc") }

}

// java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer

//   at scala.runtime.BoxesRunTime.unboxToInt(BoxesRunTime.java:105)

//   at Test$$anonfun$1.apply(a.scala:5)

//   at Test$.delayedEndpoint$Test$1(a.scala:7)

[Lex Spoon]

On Mon, Sep 30, 2013 at 4:59 PM, Paul Phillips <pa...@improving.org> wrote:
>
> On Mon, Sep 30, 2013 at 1:53 PM, martin odersky <martin....@epfl.ch>
> wrote:
>>
>> Can you give an example how not doing so would break things?
>
>
> trait Super[+A]
> case class Sub[B](f: B => B) extends Super[B]

It was a lot of negatives, but I think he meant the other way around.
Would it be overly restrictive to bar all GADT-narrowing for
non-invariant type parameters, including ones from superclasses.

Lex

[martin odersky]

Yes, good point. Let's make it a test case, along with the original example. Unfortunately, as all unsoundness problems this one seems to be already exploited extensively. So we have work to do to fix the usages as well.

 - Martin

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[martin odersky]

No, I meant it the other, other way around ;-) If we need to bar GADT-narrowing for non-invariant type parameters, including ones from superclasses, then that's what we have to do. I just wanted a concrete unsoundness example, which Paul supplied.

 - Martin

 

Lex

--
You received this message because you are subscribed to the Google Groups "scala-language" group.
To unsubscribe from this group and stop receiving emails from it, send an email to scala-languag...@googlegroups.com.
For more options, visit https://groups.google.com/groups/opt_out.

[Paul Phillips]

On Mon, Sep 30, 2013 at 1:24 PM, martin odersky <martin....@epfl.ch> wrote:

I believe that's the problem discovered by Paolo Giarruso, presented in his talk at the last Scala workshop:

  "Open GADTs and Declaration-site Variance: A Problem Statement"

I also believe the right fix is to change pattern matching to infer GADT-style typed only for non-variant parameters. 

Now having read that, I can say it's not the same thing. The problem he's getting at is severe and fundamental - it is the one covered in SI-6680. The problem I discovered is an implementation bug which can be fixed without affecting SI-6680 one way or the other. Here's a summary which involves no variance nor even subtyping.

case class Sub[B <: Ordered[B]](x: B)

object Test {

  def g[A](x: Ordered[A]) = ()

  def f(x: Any) = x match { case Sub(x) => g(x) }

}

This doesn't compile, because the wrong type is inferred for x in the pattern match.

a.scala:4: error: No implicit Ordering defined for Any.

  def f(x: Any) = x match { case Sub(x) => g(x) }

                                             ^

one error found

The type parameter bound is lost because the pattern's type is inferred with expected type Any, which swallows kind errors and causes the type arguments to be inferred without restriction. If the pattern is typed with expected type Sub[B], the program compiles as expected.

[Jan Vanek]

On 30.09.2013 22:24, martin odersky wrote:

On Mon, Sep 30, 2013 at 8:49 PM, Paul Phillips <pa...@improving.org> wrote:

The thrill is completely gone, don't worry. I found this the usual way: fix a bug only to discover that a) the bug was creating unsoundness and b) the standard library depends on the unsoundness.

I believe that's the problem discovered by Paolo Giarruso, presented in his talk at the last Scala workshop:

  "Open GADTs and Declaration-site Variance: A Problem Statement"

trait Exp[+T]
case class Const[T](t: T) extends Exp[T]
class UnsoundConst(t: String) extends Const[Any](t) with Exp[Boolean]

Would DOT allow this? I don't quite know how but I hoped that both the Exp[Any] from Const[Any] and the Exp[Boolean] would contribute, resulting in Any & Boolean = Boolean required for the t given to Const, even when only Const[Any] is written.

With regards,
Jan

[Paul Phillips]

On Tue, Oct 1, 2013 at 2:48 PM, Jan Vanek <j3v...@gmail.com> wrote:

trait Exp[+T]
case class Const[T](t: T) extends Exp[T]
class UnsoundConst(t: String) extends Const[Any](t) with Exp[Boolean]

Would DOT allow this? I don't quite know how but I hoped that both the Exp[Any] from Const[Any] and the Exp[Boolean] would contribute, resulting in Any & Boolean = Boolean required for the t given to Const, even when only Const[Any] is written.

We can already see it not being allowed if you take the other code path.

package p1 {

  trait Expr { type T <: Any }

  trait ExprBool extends Expr { type T <: Boolean }

  class Cell extends Expr { type T = Int }

  class UnsoundCell extends Cell with ExprBool

}

// ./a.scala:6: error: overriding type T in trait ExprBool with bounds <: Boolean;

//  type T in class Cell, which equals Int has incompatible type

//   class UnsoundCell extends Cell with ExprBool

//         ^

// one error found

[Paul Phillips]

Obviously the default should go the other way, but here's the best I'm going to do given the requirement to let existing code compile.

% cat test/files/neg/gadts2.scala

trait Super[+A]

case class Sub[B](f: B => B) extends Super[B]

object Test extends App {

  val s1 = Sub((x: Int) => x)

  (s1: Super[Any]) match { case Sub(f) => f("abc") }

}

% qscalac test/files/neg/gadts2.scala

% qscalac test/files/neg/gadts2.scala -Xstrict-inference

test/files/neg/gadts2.scala:7: error: type mismatch;

 found   : String("abc")

 required: B

  (s1: Super[Any]) match { case Sub(f) => f("abc") }

                                            ^

one error found