Contravariant Ordering[T], java.util.Comparator, and uncheckedVariance

Silly me. I was using the annotation wrong. For future reference:

  trait Ordering[-T] extends java.util.Comparator[T @uncheckedVariance] ...

--j

On Tue, Oct 20, 2009 at 10:54 AM, Jorge Ortiz <jorge [dot] ortiz [at] gmail [dot] com> wrote:

I'm working on a patch to make Ordering[T] contravariant. So far so good, except we'd have to give up inheritance from java.util.Comparator. Ideally @uncheckedVariance would let me do something like:

  trait Ordering[-T] extends java.util.Comparator[@uncheckedVariance T] ...

Right now it says:

  [scalacfork] /Users/jortiz/Code/scala/trunk/src/library/scala/Ordering.scala:46: error: identifier expected but '@' found.

--j

On Wed, Oct 7, 2009 at 11:51 AM, Jorge Ortiz <jorge [dot] ortiz [at] gmail [dot] com> wrote:

Hmm... this works:

  trait Ordering[-T] {
    def compare(x: T, y: T): Int
    def max[S <: T](x: S, y: S): S = if (compare(x, y) <= 0) x else y
  }

--j

On Wed, Oct 7, 2009 at 11:13 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Wed, Oct 07, 2009 at 11:01:39AM -0700, Randall R Schulz wrote:
> I believe this is one of those things that changing fundamentally in
> 2.8, by the way.

Yeah, Ordering isn't contravariant either.  I realized when I attempted
to make it so a while ago that methods like this:

 def max(x: T, y: T): T = if (gteq(x, y)) x else y

put the kibosh on anything but invariance.

This could change, things could be restructured, invariant and
co/contravariant bits could be separated out, but I doubt it's super
high on anyone's list.

--
Paul Phillips      | Appreciation is a wonderful thing; it makes what is
Future Perfect     | excellent in others belong to us as well.
Empiricist         |     -- Voltaire
slap pi uphill!    |----------* http://www.improving.org/paulp/ *----------

Jorge Ortiz schrieb:

> I'm working on a patch to make Ordering[T] contravariant. So far so
> good, except we'd have to give up inheritance from
> java.util.Comparator.

I notice that you guys diligently patch and enhance the existing library
classes and traits. Many things still seem open for discussions here,
things like `for' loops, filtering, sorting, comparing Floats and
Doubles---virtually everything. It's of course nice if things are alive
and ever-evolving, but for me as a newbie all of this is very confusing,
if not frightening: Will the code I wrote yesterday still work with 2.8
final? And will there be good documents on what has actually changed in 2.8?

If a trait suddenly no longer inherits `j.u.Comparator', then that's a
major revamp, isn't it? Are things like these simply changed by
individuals without further team discussions?

Frankly said, this scares me.

Cheers
---Phil

If I translated Jorge's incantations right, what he just said is that Comparator will be just fine.

On Tue, Oct 20, 2009 at 8:30 PM, Philip Köster <philip [dot] koester [at] web [dot] de> wrote:

Jorge Ortiz schrieb:

   I'm working on a patch to make Ordering[T] contravariant. So far so
   good, except we'd have to give up inheritance from
   java.util.Comparator.

I notice that you guys diligently patch and enhance the existing library classes and traits. Many things still seem open for discussions here, things like `for' loops, filtering, sorting, comparing Floats and Doubles---virtually everything. It's of course nice if things are alive and ever-evolving, but for me as a newbie all of this is very confusing, if not frightening: Will the code I wrote yesterday still work with 2.8 final? And will there be good documents on what has actually changed in 2.8?

If a trait suddenly no longer inherits `j.u.Comparator', then that's a major revamp, isn't it? Are things like these simply changed by individuals without further team discussions?

Frankly said, this scares me.

Cheers
---Phil

--
Viktor Klang

Blog: klangism.blogspot.com
Twttr: viktorklang
Wave: viktor [dot] klang [at] googlewave [dot] com
Code: github.com/viktorklang

AKKA Committer - akkasource.org
Lift Committer - liftweb.com
Atmosphere Committer - atmosphere.dev.java.net
SoftPub founder: http://groups.google.com/group/softpub

Scala 2.8 is widely seen as Scala's last chance to fix things that are horribly, horribly broken before APIs freeze in a much greater effort at backwards compatibility. So that means, yes, there will be breaking changes from 2.7.x to 2.8. However, they will be fairly well documented and well-discussed. Judging by the traffic on the various Scala lists, most changes elicit some fairly serious debate about the pros and cons. After 2.8, breaking changes should be rare to nonexistent.

My proposed (keyword: proposed; I'm just playing around with the APIs and have no more say than you do as to what goes into the final Scala version) change to Ordering was to make it contravariant. This means, for example, that an Ordering on Animals can also be used as an Ordering on Cats. Pretty intuitive, and should involve no breaking changes. The snag I ran into is that java.util.Comparator is not contravariant (Java has no such notion), so a contravariant Ordering wouldn't be able to inherit from it. Thankfully, There's An Annotation For That (the Apple ads just script themselves). So I can assure the compiler that inheriting from Comparator is indeed safe (even though Java has no such notion, Comparator is indeed contravariant). Now that I've figured out how to use the annotation, my proposed (keyword: proposed) changes won't break backwards compatibility at all.

--j

On Tue, Oct 20, 2009 at 11:30 AM, Philip Köster <philip [dot] koester [at] web [dot] de> wrote:

Jorge Ortiz schrieb:

   I'm working on a patch to make Ordering[T] contravariant. So far so
   good, except we'd have to give up inheritance from
   java.util.Comparator.

I notice that you guys diligently patch and enhance the existing library classes and traits. Many things still seem open for discussions here, things like `for' loops, filtering, sorting, comparing Floats and Doubles---virtually everything. It's of course nice if things are alive and ever-evolving, but for me as a newbie all of this is very confusing, if not frightening: Will the code I wrote yesterday still work with 2.8 final? And will there be good documents on what has actually changed in 2.8?

If a trait suddenly no longer inherits `j.u.Comparator', then that's a major revamp, isn't it? Are things like these simply changed by individuals without further team discussions?

Frankly said, this scares me.

Cheers
---Phil

It's not all that bad as it seems, and there _is_ communication going on, as well as concern for source compatibility.
If you target 2.7, and avoid anything deprecated there, you should be mostly fine with 2.8. Likely, your code will emit deprecation warnings on Scala 2.8, and more complex code may need to be changed, but most of the day to day stuff should be fine. Library and frameworks are the more impacted here.   If you target any 2.8 nightly, then you are definitely in for a rollercoaster. Scala 2.8 is a moving target, and some things in it WILL change, and without notice if they happen not to exist on Scala 2.7.   It's important to note, though, that many of the things being changed are _broken_. Arrays and numeric equality are two such examples. They may seem to work, and, mostly, they do. But they have ragged edges which are completely broken.   Finally, as for good documents about what has changed (as opposed to simply what the major new features are), I honestly doubt it, unfortunately. It would be at least useful if, when porting the major frameworks and libraries (Lift, ScalaTest, ScalaCheck, Specs, Scalaz, SBT, ScalaQuery, to name a few), the pitfalls where marked and submitted, so that they can be compiled into a document to be made available at release.
On Tue, Oct 20, 2009 at 4:30 PM, Philip Köster <philip [dot] koester [at] web [dot] de> wrote:

Jorge Ortiz schrieb:

   I'm working on a patch to make Ordering[T] contravariant. So far so
   good, except we'd have to give up inheritance from
   java.util.Comparator.

I notice that you guys diligently patch and enhance the existing library classes and traits. Many things still seem open for discussions here, things like `for' loops, filtering, sorting, comparing Floats and Doubles---virtually everything. It's of course nice if things are alive and ever-evolving, but for me as a newbie all of this is very confusing, if not frightening: Will the code I wrote yesterday still work with 2.8 final? And will there be good documents on what has actually changed in 2.8?

If a trait suddenly no longer inherits `j.u.Comparator', then that's a major revamp, isn't it? Are things like these simply changed by individuals without further team discussions?

Frankly said, this scares me.

Cheers
---Phil

--
Daniel C. Sobral

Something I learned in academia: there are three kinds of academic reviews: review by name, review by reference and review by value.

Dear Jorge,

I didn't mean to complain but am slowly losing overview. But if things
need changing, then please change them. I followed this ``Range-yield"
discussion vigilantly and agree: If `Range' needs a new implementation
here, considering most Scala users will use `Int.to' and `Int.until' as
a replacement for the Java-like `for (int i = 0; i < n; ++i)' idiom,
then now is the time to do it---*before* 2.8 final.

---Ph.

Finally, as for good documents about what has changed (as opposed to simply what the major new features are), I honestly doubt it, unfortunately. It would be at least useful if, when porting the major frameworks and libraries (Lift, ScalaTest, ScalaCheck, Specs, Scalaz, SBT, ScalaQuery, to name a few), the pitfalls where marked and submitted, so that they can be compiled into a document to be made available at release.

That would not be very good. Maybe someone wants to volunteer to watch and document all tickets that get closed for 2.8?

Besides which, he said he's working on a patch. That means that it still has to be accepted (hopefully it will be).In any case nothing is stopping you from using 2.7.x.Scala's "version brittleness" may sound scary and it may sound like a disadvantage compared to Java--what would happen if Java would not be backward compatible between say 1.5 and 1.6? If your web host upgrades to 1.6 your webapps may not work. But the truth is it's very different. From a runtime perspective, Scala is just another library in the classpath. All it takes is to ensure that the correct scala jars are in your classpath, and all scala products that use each other are compiled with the same version of Scala. True, it's a bit of work, but it's not like what would be if the JVM or PHP or MySQL etc. would not be backward compatible. You are in control of all the components you deploy.

On Tue, Oct 20, 2009 at 2:53 PM, Viktor Klang <viktor [dot] klang [at] gmail [dot] com> wrote:

If I translated Jorge's incantations right, what he just said is that Comparator will be just fine.

On Tue, Oct 20, 2009 at 8:30 PM, Philip Köster <philip [dot] koester [at] web [dot] de> wrote:

Jorge Ortiz schrieb:

   I'm working on a patch to make Ordering[T] contravariant. So far so
   good, except we'd have to give up inheritance from
   java.util.Comparator.

I notice that you guys diligently patch and enhance the existing library classes and traits. Many things still seem open for discussions here, things like `for' loops, filtering, sorting, comparing Floats and Doubles---virtually everything. It's of course nice if things are alive and ever-evolving, but for me as a newbie all of this is very confusing, if not frightening: Will the code I wrote yesterday still work with 2.8 final? And will there be good documents on what has actually changed in 2.8?

If a trait suddenly no longer inherits `j.u.Comparator', then that's a major revamp, isn't it? Are things like these simply changed by individuals without further team discussions?

Frankly said, this scares me.

Cheers
---Phil

--
Viktor Klang

Blog: klangism.blogspot.com
Twttr: viktorklang
Wave: viktor [dot] klang [at] googlewave [dot] com
Code: github.com/viktorklang

AKKA Committer - akkasource.org
Lift Committer - liftweb.com
Atmosphere Committer - atmosphere.dev.java.net
SoftPub founder: http://groups.google.com/group/softpub

> If you target any 2.8 nightly, then you are definitely in for a
> rollercoaster. Scala 2.8 is a moving target, and some things in it WILL
> change, and without notice if they happen not to exist on Scala 2.7.

It all started with the problem I was unable to install Miles's 2.7 plug
into my Eclipse because of JDT-weaving incompatibilities. (I know what a
weaver is, but I still don't know what JDT weaving is good for.) I only
wanted the banana amd had to take the whole gorilla. Now I have complete
version madness: My Scala-console binaries are of version 2.7.6 final,
the Maven plug forces me to use Scala-library version
2.8.0.r18462-b20090811081019, whatever that is, and Miles comes with yet
another library and compiler every night. :) It's easy to get crazy this
way! :) What is noteworthy is that the class files generated by Maven
and by Eclipse aren't compatible with each other because the collection
framework was heavily reorganized.

Well, this way I can at least support Miles with bug reports on his
latest builds, I think that is worth the effort.

But I'm anxiously awaiting 2.8 final to put an end to this three-fold
version chaos.

---Ph.

> Besides which, he said he's working on a patch. That means that it still
> has to be accepted (hopefully it will be).
> In any case nothing is stopping you from using 2.7.x.

I guess now it's too late for me to step back to 2.7.x. But I wasn't
able to get Maven, Spring 3 and AspectJ load-time weaving to run with
Scala in Eclipse with the older Scala-plug versions. I really tried but
didn't find a way.

---Ph.

I just tried to make Ordering contravariant but backed out again. One
reason was max, the other was that because of some quirk in type
inference the conversion `ordered' requires additional type info,
which breaks existing programs. Type inference might at some point be
improved to deal with it, but that's neither imminent nor certain. So
for the moment we'll leave Ordering invariant.

Cheers

Max is easily fixed:

  def max[S <: T](x: S, y: S): S

What conversion are you referring to? The one I'm running into problems with is mkOrderingOps, but it's new in 2.8 so I think an acceptable approach might still be found.

--j

On Wed, Oct 21, 2009 at 10:24 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:

I just tried to make Ordering contravariant but backed out again. One
reason was max, the other was that because of some quirk in type
inference the conversion `ordered' requires additional type info,
which breaks existing programs. Type inference might at some point be
improved to deal with it, but that's neither imminent nor certain. So
for the moment we'll leave Ordering invariant.

Cheers

On Wed, Oct 21, 2009 at 11:49:14AM -0700, Jorge Ortiz wrote:
> What conversion are you referring to? The one I'm running into
> problems with is mkOrderingOps, but it's new in 2.8 so I think an
> acceptable approach might still be found.

I would suppose this:

trait LowPriorityOrderingImplicits {
implicit def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
def compare(x: A, y: A) = x.compare(y)
}
}

For sure I always find interesting surprises when I try to make a change
such as this one. Another option we could consider is separating out
the contravariant core from any invariance-inducing elements (if in fact
there are any which can't be worked around) but one senses that approach
brings with it an intrinsic helping of fail.

This implicit is also new in 2.8. It's not a reason to give up on a contravariant Ordering.

--j

On Wed, Oct 21, 2009 at 12:07 PM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Wed, Oct 21, 2009 at 11:49:14AM -0700, Jorge Ortiz wrote:
> What conversion are you referring to? The one I'm running into
> problems with is mkOrderingOps, but it's new in 2.8 so I think an
> acceptable approach might still be found.

I would suppose this:

trait LowPriorityOrderingImplicits {
 implicit def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
   def compare(x: A, y: A) = x.compare(y)
 }
}

For sure I always find interesting surprises when I try to make a change
such as this one.  Another option we could consider is separating out
the contravariant core from any invariance-inducing elements (if in fact
there are any which can't be worked around) but one senses that approach
brings with it an intrinsic helping of fail.

--
Paul Phillips      | We must respect the other fellow's religion, but only
Apatheist          | in the sense and to the extent that we respect his
Empiricist         | theory that his wife is beautiful and his children smart.
pal, i pill push   |     -- H. L. Mencken

As a relative newcomer to this discussion, I am a bit befuddled.
Ordering is naturally contravariant, and, as I know from Java, it
causes a lot of pain if it is not allowed to be. Check out this blog:
http://in.relation.to/Bloggers/JavaGenericsWTF. (This is not a small
or uninportant API--without wanting to upset anyone here, I'll
confidently predict that more people will use JPA than all of Scala in
the near future.) At least he had a solution, thanks to "Y extends
Comparable<? super Y>" in Java. I have no idea how I would express
this in Scala without contravariant orderings. If indeed 2.8 is the
last best chance to fix fundamental API design issues, now is the time
to get busy to fix something as basic as this.

Cheers,

Cay

On Wed, Oct 21, 2009 at 10:24 AM, martin odersky wrote:
> I just tried to make Ordering contravariant but backed out again. One
> reason was max, the other was that because of some quirk in type
> inference the conversion `ordered' requires additional type info,
> which breaks existing programs. Type inference might at some point be
> improved to deal with it, but that's neither imminent nor certain. So
> for the moment we'll leave Ordering invariant.
>
> Cheers
>
>  -- Martin

On Tue, Oct 20, 2009 at 12:31:19PM -0700, Jorge Ortiz wrote:
> This means, for example, that an Ordering on Animals can also be used
> as an Ordering on Cats.

Let's see if that's REALLY true. I have this much working:

object Contravaricat
{
class Animal
case object Hipposhark extends Animal
case object Crocodolphin extends Animal

class Cat extends Animal
case object Snowball extends Cat
case object Wally extends Cat
case object Beelzebub extends Cat
case object FuzzyMcCatskin extends Cat

val cats = List(Snowball, Wally, Beelzebub, FuzzyMcCatskin)

implicit val ord: Ordering[Animal] = new Ordering[Animal] {
def compare(x: Animal, y: Animal) = x.toString() compare y.toString()
}

def main(args: Array[String]): Unit = {
println(cats max)
val set = new collection.immutable.TreeSet[Cat] ++ cats
println(set)

import ord._

println(max(Beelzebub, FuzzyMcCatskin))
println(min(Beelzebub, FuzzyMcCatskin))
println(Wally < Snowball)
println(Hipposhark >= Crocodolphin)
}
}

Output is:

Wally
TreeSet(Beelzebub, FuzzyMcCatskin, Snowball, Wally)
FuzzyMcCatskin
Beelzebub
false
true

I also ran into what martin did with ordered. Before contravariance,
this line worked:

implicit val SettingOrdering : Ordering[Setting] = Ordering.ordered;

After, it infers Ordering[Any] and fails despite the explicit
annotation. I guess the compiler is trying to help out in the same way
as it does by inferring the most specific type in covariant types. (Why
would you want an Ordering[Foo] when an Ordering[Any] is ALL THAT and
MORE!) But that quirk kill the deal, as it works if you just say
Ordering.ordered[Setting].

Here is a recent ticket bringing up the same (?) issue:

http://lampsvn.epfl.ch/trac/scala/ticket/2509
"Contravariance mucks with implicit resolution"

But reporter claims "the most-specific implicit is not being selected"
and I'm not sure that's true. X is contravariant, so if B extends A,
X[A] is a subtype of X[B] and thus X[A] is more specific. Or so I am
thinking this second, it's a little late for me to comprehend that
section of the spec and maybe some cats will come to me in a dream and
meow otherwise.

Setting? Where did that come from?

--j

On Sun, Oct 25, 2009 at 12:21 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Tue, Oct 20, 2009 at 12:31:19PM -0700, Jorge Ortiz wrote:
> This means, for example, that an Ordering on Animals can also be used
> as an Ordering on Cats.

Let's see if that's REALLY true.  I have this much working:

object Contravaricat
{
 class Animal
 case object Hipposhark extends Animal
 case object Crocodolphin extends Animal

 class Cat extends Animal
 case object Snowball extends Cat
 case object Wally extends Cat
 case object Beelzebub extends Cat
 case object FuzzyMcCatskin extends Cat

 val cats = List(Snowball, Wally, Beelzebub, FuzzyMcCatskin)

 implicit val ord: Ordering[Animal] = new Ordering[Animal] {
   def compare(x: Animal, y: Animal) = x.toString() compare y.toString()
 }

 def main(args: Array[String]): Unit = {
   println(cats max)
   val set = new collection.immutable.TreeSet[Cat] ++ cats
   println(set)

   import ord._

   println(max(Beelzebub, FuzzyMcCatskin))
   println(min(Beelzebub, FuzzyMcCatskin))
   println(Wally < Snowball)
   println(Hipposhark >= Crocodolphin)
 }
}

Output is:

Wally
TreeSet(Beelzebub, FuzzyMcCatskin, Snowball, Wally)
FuzzyMcCatskin
Beelzebub
false
true

I also ran into what martin did with ordered.  Before contravariance,
this line worked:

 implicit val SettingOrdering : Ordering[Setting] = Ordering.ordered;

After, it infers Ordering[Any] and fails despite the explicit
annotation.  I guess the compiler is trying to help out in the same way
as it does by inferring the most specific type in covariant types.  (Why
would you want an Ordering[Foo] when an Ordering[Any] is ALL THAT and
MORE!) But that quirk kill the deal, as it works if you just say
Ordering.ordered[Setting].

Here is a recent ticket bringing up the same (?) issue:

 http://lampsvn.epfl.ch/trac/scala/ticket/2509
 "Contravariance mucks with implicit resolution"

But reporter claims "the most-specific implicit is not being selected"
and I'm not sure that's true.  X is contravariant, so if B extends A,
X[A] is a subtype of X[B] and thus X[A] is more specific.  Or so I am
thinking this second, it's a little late for me to comprehend that
section of the spec and maybe some cats will come to me in a dream and
meow otherwise.

--
Paul Phillips      | Every normal man must be tempted at times
Everyman           | to spit on his hands, hoist the black flag,
Empiricist         | and begin to slit throats.
i pull his palp!   |     -- H. L. Mencken

On Sun, Oct 25, 2009 at 09:49:08AM -0700, Jorge Ortiz wrote:
> Setting? Where did that come from?

Let me grep trunk for that for you!

http://lampsvn.epfl.ch/svn-repos/scala/scala/trunk/src/compiler/scala/to...

Ahh, src/compiler. I try to avoid that and stick to src/library :). Grep is slow enough as it is with just src/library :P

--j

On Sun, Oct 25, 2009 at 9:57 AM, Paul Phillips <paulp [at] improving [dot] org> wrote:

On Sun, Oct 25, 2009 at 09:49:08AM -0700, Jorge Ortiz wrote:
> Setting? Where did that come from?

Let me grep trunk for that for you!

 http://lampsvn.epfl.ch/svn-repos/scala/scala/trunk/src/compiler/scala/tools/nsc/Settings.scala

--
Paul Phillips      | Every election is a sort of advance auction sale
Apatheist          | of stolen goods.
Empiricist         |     -- H. L. Mencken
i'll ship a pulp   |----------* http://www.improving.org/paulp/ *----------

On Sun, Oct 25, 2009 at 6:57 PM, Paul Phillips wrote:
> On Sun, Oct 25, 2009 at 09:49:08AM -0700, Jorge Ortiz wrote:
>> Setting? Where did that come from?
>
> Let me grep trunk for that for you!
>
>  http://lampsvn.epfl.ch/svn-repos/scala/scala/trunk/src/compiler/scala/tools/nsc/Settings.scala
>
That's indeed where it turned up first. And then also in one of the
tests. The problem is unfortunately a bit nasty, and it dows not have
a quick fix. In the situation at hand, type inference tries to find
the largest possible solution for the contravariant type parameter.
Unfortunately, this type parameter also has an F-bound (i..e it occurs
in its own upper bound). This means we have to maximize T under the
constraint

T <: Ordering[T]

But that's not in the class of constraints that Scala's type inference
knows how to solve. Scala's type ingerence only admits subtyping
constraints where all the variables are on one side (the reason is
that the more general class of constraints does not always have most
general solutions.) So what happens is that a solution for T is
searched and the F-bound is tested after the fact. In our case there
are no other upper constraints for T, so we get Any, which of course
fails to be under the bound.

It would probably be better to suspend solving these constraints in
these cases. But I believe that's best done in the future as part of
an effort to put Scala type inference on a different basis. As it is I
would be very reluctant to apply quick fixes to type inference, now.
It's too subtle for that.

Cheers

On Sun, Oct 25, 2009 at 07:43:02PM +0200, martin odersky wrote:
> It would probably be better to suspend solving these constraints in
> these cases. But I believe that's best done in the future as part of
> an effort to put Scala type inference on a different basis. As it is I
> would be very reluctant to apply quick fixes to type inference, now.
> It's too subtle for that.

Full agreement there. I'm still holding out hope there's a way to make
Ordering contravariant now in exchange for some modest inconvenience in
atypical cases, but the test case which fails is the one I added for
#2260 and I'd sure hate to unfix that so soon after stumbling upon what
#seems a nice solution.

The fix for #2260 made this work again:

val tree = TreeMap.empty[Text, String]

Making Ordering contravariant undoes that work, necessitating this as
before:

val tree = TreeMap.empty[Text, String](Ordering.ordered[Text])

I don't know what the relative importances are, but my spidey sense
tells me we should strain our necks looking for a way to make Ordering
contravariant now as opposed to kicking it down the road.