Equality and case objects

On Feb 27, 2009, at 1:36 AM, David MacIver wrote:
> Alas, pattern matching on case objects (*not* case classes) invokes
> their equals method. So when the equals method is defined in terms
> of something which is defined in terms of pattern matching... yep.
> Badness happens.
>
> I propose the following alteration to the spec: Case objects (not
> objects in general) will always override equality to mean objects
> equality, unless a parent defined equality as a final method or the
> user explicitly provides an equals method in the object definition

I like the idea, but why the first exception? It seems just as well
to simplify the spec some and say that the inherited equals method is
ignored for case classes and case objects. In fact, I thought that
was already the spec.

For the example you give, you could actually even leave out the equals
methods all together, and everything would work.

Lex

On Thu, Feb 26, 2009 at 10:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 27, 2009, at 1:36 AM, David MacIver wrote:

Alas, pattern matching on case objects (*not* case classes) invokes their equals method. So when the equals method is defined in terms of something which is defined in terms of pattern matching... yep. Badness happens.

I propose the following alteration to the spec: Case objects (not objects in general) will always override equality to mean objects equality, unless a parent defined equality as a final method or the user explicitly provides an equals method in the object definition

I like the idea, but  why the first exception?

Sorry, which exception?
 

It seems just as well to simplify the spec some and say that the inherited equals method is ignored for case classes and case objects.  In fact, I thought that was already the spec.

It's not. Actually it's the opposite: If there is an inherited equals method case classes and case objects won't generate equals methods (except in the essentially unspecced bizarre corner case of brokenness that is case class inheritance. But let's not go there for now). Also you can't ignore them because they might be final.

Hm.

Actually, if you mean "ignore" in the sense that the pattern matching doesn't use them, that might work. But I quite like that case object pattern matching is currently just an instance of stable identifier pattern matching. It seems more aesthetically pleasing to have case objects behave like normal pattern matches on objects and specify their default equality behaviour to be more useful than to special case pattern matching for them. But I could be persuaded.
 

For the example you give, you could actually even leave out the equals methods all together, and everything would work.

Yes, absolutely. But it's a condensation of an example where this wasn't the case. (I had multiple alternatives which you could get an empty list, but this wasn't necessary to demonstrate the problem).

Hmm.

Actually, having talked that through, I see now that my proposed solution wouldn't fix the problem because the case objects would override equals and thus break that case. On second thoughts, I think you might be right: Case object pattern matching probably shouldn't use equality.

Clearly this needs further thought.

On Feb 27, 2009, at 10:08 AM, David MacIver wrote:

On Thu, Feb 26, 2009 at 10:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 27, 2009, at 1:36 AM, David MacIver wrote:

Alas, pattern matching on case objects (*not* case classes) invokes their equals method. So when the equals method is defined in terms of something which is defined in terms of pattern matching... yep. Badness happens.

I propose the following alteration to the spec: Case objects (not objects in general) will always override equality to mean objects equality, unless a parent defined equality as a final method or the user explicitly provides an equals method in the object definition

I like the idea, but  why the first exception?

Sorry, which exception?

I meant this one: "unless a parent defined equality as a final method".

It seems just as well to simplify the spec some and say that the inherited equals method is ignored for case classes and case objects.  In fact, I thought that was already the spec.

It's not. Actually it's the opposite: If there is an inherited equals method case classes and case objects won't generate equals methods (except in the essentially unspecced bizarre corner case of brokenness that is case class inheritance. But let's not go there for now). Also you can't ignore them because they might be final.

You're right, and the exception is already in the spec.  Here's the spec (section 5.3):
Every case class implicitly overrides some method definitions of class scala.AnyRef (§12.1) unless a definition of the same method is already given in the case class itself or a concrete definition of the same method is given in some base class of the case class different from AnyRef.

I guess the idea is that you can define an equals method for a hierarchy of case classes, as in the example you gave.  I'm iffy, because case classes are supposed to be regular, not swiss army knives.  However, it looks perfectly workable, so I don't think it would be worth the problems that a spec change would cause.

Actually, having talked that through, I see now that my proposed solution wouldn't fix the problem because the case objects would override equals and thus break that case. On second thoughts, I think you might be right: Case object pattern matching probably shouldn't use equality.

There has been a lot of discussion about it.  The current arrangement, if I understand, is to consistently use == but for the compiler to notice if == is the same as eq.  In that common case, the pattern can also be used as a stable identifier.  The problem with using eq in some cases is it's hard to define which ones.  All objects?  That doesn't work well.  All case objects?  That would not be emulatable by non-case objects. What subset, then?  At the least, it will be a complicated rule.  To contrast, using == consistently is at least simple to explain and understand.
Given all this, you're certainly right that there's a trap: since pattern matching uses equals, implementations of equals had better be careful with pattern matching.  I don't see what to do about it, though.  Notice infinite regressions as a compiler warning?
-Lex

On Fri, Feb 27, 2009 at 12:39 AM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 27, 2009, at 10:08 AM, David MacIver wrote:

On Thu, Feb 26, 2009 at 10:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 27, 2009, at 1:36 AM, David MacIver wrote:

Alas, pattern matching on case objects (*not* case classes) invokes their equals method. So when the equals method is defined in terms of something which is defined in terms of pattern matching... yep. Badness happens.

I propose the following alteration to the spec: Case objects (not objects in general) will always override equality to mean objects equality, unless a parent defined equality as a final method or the user explicitly provides an equals method in the object definition

I like the idea, but  why the first exception?

Sorry, which exception?

I meant this one: "unless a parent defined equality as a final method".

Oh, right. Well, that's unfortunately essential. If the parent has a final equals method you can't override it.
 

It seems just as well to simplify the spec some and say that the inherited equals method is ignored for case classes and case objects.  In fact, I thought that was already the spec.

It's not. Actually it's the opposite: If there is an inherited equals method case classes and case objects won't generate equals methods (except in the essentially unspecced bizarre corner case of brokenness that is case class inheritance. But let's not go there for now). Also you can't ignore them because they might be final.

I guess the idea is that you can define an equals method for a hierarchy of case classes, as in the example you gave.  I'm iffy, because case classes are supposed to be regular, not swiss army knives.  However, it looks perfectly workable, so I don't think it would be worth the problems that a spec change would cause.

I'm not sure being able to define equality in a natural way on your custom datatype without it breaking really counts as a swiss army knife. :-)

I do however agree with the sentiment that case classes shouldn't be a swiss army knife. In particular I'd rather like to see a lot of their functionality factored out and case classes be left as only significant for pattern matching. But that's an argument for another day.

Actually, having talked that through, I see now that my proposed solution wouldn't fix the problem because the case objects would override equals and thus break that case. On second thoughts, I think you might be right: Case object pattern matching probably shouldn't use equality.

There has been a lot of discussion about it.  The current arrangement, if I understand, is to consistently use == but for the compiler to notice if == is the same as eq.  In that common case, the pattern can also be used as a stable identifier.  The problem with using eq in some cases is it's hard to define which ones.  All objects?  That doesn't work well.  All case objects?  That would not be emulatable by non-case objects. What subset, then?  At the least, it will be a complicated rule.  To contrast, using == consistently is at least simple to explain and understand.

I'm not sure I see why this has to be complicated. It seems straightforward enough, for example, to say that case object pattern matching translates to a pattern match on type type of the object.

e.g. given case object Foo;

case Foo =>

becomes
 
case (_ : Foo.type) =>

And have all other objects match as stable identifiers.

This does mean that case objects are not simply stable identifier patterns, which is a little sad, but seems to me to be the best option. It breaks less stuff, means the compiler can assume stronger guarantees about matching of case classes (for whatever that's worth) and means that case object matching is consistent with case class matching. It's also easy to do something equivalent on non case class objects, either by defining your own equals method or by doing the match on the type explicitly.

Oh. Hang on a minute. I've got an idea.

Stable identifier patterns are in need of respeccing anyway because of the type soundness hole paul and I discovered a little while back. In particular where

case x@Foo =>

currently translates to

case x if Foo == x if =>

If needs to translate to

case (x : Foo.type) if Foo == x =>

If we modify this slightly to:

case (x : Foo.type) if (Foo eq x) || (Foo == x) =>

then the problem is consistently solved. An object will not invoke its equals method when pattern matched against itself, but equality based pattern matching will continue to work (except for the corner case where you have an incorrect implementation of equality where an object is not equal to itself. But that's so broken that there's no way it should be catered for). However, most points where you would unintentionally enter an infinite recursion through equality are now guaranteed to shortcut.

In particular if you modify my motivating example to shortcut on eq then the problem goes away.

On Thu, Feb 26, 2009 at 3:36 PM, David MacIver wrote:
> Observe the following code:
>
> abstract class MyList{
>   def toList : List[Int] = this match {
>     case Nope => Nil
>     case Cons(x, y) => x :: y.toList
>   }
>
>   override def equals(that : Any) = that match {
>     case (that : MyList) => this.toList == that.toList;
>     case _ => false;
>   }
> }
>
> case class Cons(x : Int, y : MyList) extends MyList;
> case object Nope extends MyList;
>
> object Test{
>   def main(args : Array[String]){
>     println(Nope.toList)
>   }
> }
>
>
> Care to take a guess what happens?
>
> Alas:java.lang.StackOverflowError
>     at MyList.equals(mylist.scala:7)
>     at MyList.toList(mylist.scala:2)
> ...
>
> Alas, pattern matching on case objects (*not* case classes) invokes their
> equals method. So when the equals method is defined in terms of something
> which is defined in terms of pattern matching... yep. Badness happens.
>
> I propose the following alteration to the spec: Case objects (not objects in
> general) will always override equality to mean objects equality, unless a
> parent defined equality as a final method or the user explicitly provides an
> equals method in the object definition
>
I think this violates one motivation for the current design: It should
be easy to have user-defined equality methods also for case classes.
That's why there is the rule in the spec that concrete equals methods
are not overridden by case classes (unless the overridden method comes
from Object, of course).
The new rule would violate this rule for case object. Making an
exception to the exception if the equality method is final only
complicates matters further, I fear.

I believe it would be much more regular to change the pattern matching
for case objects. In a

case X =>

where X is a case object, translate this to an instanceOf test of X's
implementing class. That brings pattern matching of case objects and
case classes into line, and it also avoids special casing equality.

Cheers

On Fri, Feb 27, 2009 at 11:05 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:

On Thu, Feb 26, 2009 at 3:36 PM, David MacIver <david [dot] maciver [at] gmail [dot] com> wrote:
> Observe the following code:
>
> abstract class MyList{
>   def toList : List[Int] = this match {
>     case Nope => Nil
>     case Cons(x, y) => x :: y.toList
>   }
>
>   override def equals(that : Any) = that match {
>     case (that : MyList) => this.toList == that.toList;
>     case _ => false;
>   }
> }
>
> case class Cons(x : Int, y : MyList) extends MyList;
> case object Nope extends MyList;
>
> object Test{
>   def main(args : Array[String]){
>     println(Nope.toList)
>   }
> }
>
>
> Care to take a guess what happens?
>
> Alas:java.lang.StackOverflowError
>     at MyList.equals(mylist.scala:7)
>     at MyList.toList(mylist.scala:2)
> ...
>
> Alas, pattern matching on case objects (*not* case classes) invokes their
> equals method. So when the equals method is defined in terms of something
> which is defined in terms of pattern matching... yep. Badness happens.
>
> I propose the following alteration to the spec: Case objects (not objects in
> general) will always override equality to mean objects equality, unless a
> parent defined equality as a final method or the user explicitly provides an
> equals method in the object definition
>
I think this violates one motivation for the current design: It should
be easy to have user-defined equality methods also for case classes.

Yes. I've come to the same conclusion.

Unfortunately the current design also makes it difficult to have user-defined equality methods for case classes because you can't use pattern matching to define it. :-)
 

That's why there is the rule in the spec that concrete equals methods
are not overridden by case classes (unless the overridden method comes
from Object, of course).
The new rule would violate this rule for case object. Making an
exception to the exception if the equality method is final only
complicates matters further, I fear.

Agreed.
 

I believe it would be much more regular to change the pattern matching
for case objects. In a

 case X =>

where X is a case object, translate this to an instanceOf test of X's
implementing class. That brings pattern matching of case objects and
case classes into line, and it also avoids special casing equality.

See my proposal for the change to stable identifier matching in my last email. That nicely covers this as a special case - the changes we already have to make to stable identifier matching mean that only X can match case X anyway. Therefore all that needs to be changed to make this consistent is to guarantee that X does match case X (which should always be true in my opinion, regardless of what daft game of silly buggers the programmer is playing with equality. It violates the contract for equals to not have this be true) without invoking the equality method.

Hi David,

I had not seen your last mail yet when I answered your first one.
It seems we agree on most points, except for one detail.
If Foo is a case object, I was proposing to translate

case Foo =>

to

case x: (object Foo) =>

where (object Foo) is the underlying class of Foo (we'll probably let
you write this in source sometimes soon, but not now). You also added
an equality test, which I don't think is necessary.

There's one other related issue for inner objects and classes (ticket
1698), which might be relevant. Generally, if we write

case x: SomeClass

should we match this as

case x: this.SomeClass

i.e. test that the prefix is this, or should we just accept any
prefix. Currently, it's the former, and this led to the interesting
bug that fsc always reloaded the complete environment on every run. I
proposed to change the behavior so that any prefix would match. This
would also make pattern matching behave the same as isInstanceOf.

The change that would be required for the spec is in the section on
type designators. It currently reads:

Specifically, the unqualified type name $t$ where $t$ is bound in some
class, object, or package $C$ is taken as a shorthand for C.this.type
# t.

I propose to change this as follows:

Specifically, the unqualified type name $t$ where $t$ is bound in some
class, object, or package $C$ is taken as a shorthand for C.this.type
# t, except if the type $t$ occurs as a part
of a typed pattern (\sref{sec:typed-patterns}) and C is an inner
class. In the latter case, $t$ is taken as a shorthand for just C # t.

Together with my proposed change to case object matching, this means
that matching on an inner case class or a case object would not test
implicit this prefixes. In your proposal the implicit this would still
be checked for equality if we match on a case object. Here's an
example:

class Outer {
case class C()
case object O
val V = O

x match {
case C() => // this not tested
case O => // this not tested
case V => // this is tested
}
}

So the match expression would be translated to:

x match {
case (_: C) => ...
case (_: object O) => ...
case y if (y == this.V) => ...
}

What's your opinion on this?

Cheers

On Fri, Feb 27, 2009 at 11:59 AM, martin odersky <martin [dot] odersky [at] epfl [dot] ch> wrote:

Hi David,

I had not seen your last mail yet when I answered your first one.
It seems we agree on most points, except for one detail.
If Foo is a case object, I was proposing to translate

  case Foo =>

to

 case x: (object Foo) =>

where (object Foo) is the underlying class of Foo (we'll probably let
you write this in source sometimes soon, but not now). You also added
an equality test, which I don't think is necessary.

It's not neccessary in this particular case, but it has the nice property of working for all stable identifier patterns. Internally the compiler could implement it as simply matching on the type when what you have is a top level object (as we guarantee that the only thing that can match it is the object), but the spec doesn't need to mention that special case.
 

There's one other related issue for inner objects and classes (ticket
1698), which might be relevant. Generally, if we write

 case x: SomeClass

should we match this as

 case x: this.SomeClass

i.e. test that the prefix is this, or should we just accept any
prefix. Currently, it's the former, and this led to the interesting
bug that fsc always reloaded the complete environment on every run. I
proposed to change the behavior so that any prefix would match. This
would also make pattern matching behave the same as isInstanceOf.

I agree that pattern matching should have the same behaviour as isInstanceOf (The spec does too! Any case where pattern matching and isInstanceOf disagree is a compiler bug). But that really should emit a warning then, in much the same way that type erasure does: The pattern can match things which claim to be of the correct static type but aren't, and this won't fail with a CCE except at some unknown point later.
 

The change that would be required for the spec is in the section on
type designators. It currently reads:

Specifically, the unqualified type name $t$ where $t$ is bound in some
class, object, or package $C$ is taken as a shorthand for C.this.type
# t.

I propose to change this as follows:

Specifically, the unqualified type name $t$ where $t$ is bound in some
class, object, or package $C$ is taken as a shorthand for C.this.type
# t, except if the type $t$ occurs as a part
of a typed pattern (\sref{sec:typed-patterns}) and C is an inner
class. In the latter case, $t$ is taken as a shorthand for just C # t.

Together with my proposed change to case object matching, this means
that matching on an inner case class or a case object would not test
implicit this prefixes. In your proposal the implicit this would still
be checked for equality if we match on a case object.

Personally, I think that's a feature, in that it means that it behaves like matching on any other stable identifier. The idea that I could have

class Foo{
   case object Bar;

   def stuff(x : Any) = x match { case Bar => true; case _ => false }
}

...and have stuff match things which weren't actually equal to Bar fills me with mild horror.

Here's an
example:

class Outer {
 case class C()
 case object O
 val V = O

 x match {
   case C() => // this not tested
   case O  => // this not tested
   case V => // this is tested
 }
}

So the match expression would be translated to:

 x match {
    case (_: C) => ...
    case (_: object O) => ...
    case y if (y == this.V) => ...
 }

What's your opinion on this?

I agree that the errors caused by this case are somewhat problematic, but I'm not sure they occur commonly enough for it to be worth the spec complication, particularly if (as suggested above) matching on inner objects of a class becomes a warning. I'm also a little concerned that it's not caught statically. If x is known to come from a different instance of Outer, why is this not being rejected as the types of the matches not being subtypes of the matched object? Between that and warning on matching inner case classes I think that would catch most of the use cases adequately.

Additionally, the difference in behaviour between V and O bothers me somewhat. Particularly given that it means that

case Foo =>

has significantly different meanings depending on what Foo is.

On Feb 28, 2009, at 12:23 AM, David MacIver wrote:
> So the match expression would be translated to:
>
> x match {
> case (_: C) => ...
> case (_: object O) => ...
> case y if (y == this.V) => ...
> }
>
> What's your opinion on this?
>
> I agree that the errors caused by this case are somewhat
> problematic, but I'm not sure they occur commonly enough for it to
> be worth the spec complication, particularly if (as suggested above)
> matching on inner objects of a class becomes a warning. I'm also a
> little concerned that it's not caught statically. If x is known to
> come from a different instance of Outer, why is this not being
> rejected as the types of the matches not being subtypes of the
> matched object? Between that and warning on matching inner case
> classes I think that would catch most of the use cases adequately.

This is my initial reaction, too, but more broadly. How important is
it to support custom equality methods for case class hierarchies? If
people have to use eq for case objects, then it makes those equals
methods ugly, but it might simplify some more wide-reaching parts of
Scala semantics.

Specifically, it's a pity if a case object pattern matches differently
than a val that attempts to have the same meaning as the case object.
Someone might naturally refactor their code to change this:

case object Foo extends Bar

into this:

class GeneralFoo extends Bar
val Foo = new Bar

Unfortunately, if the pattern matcher does different things, this will
no longer be a safe refactoring.

Lex

On Fri, Feb 27, 2009 at 11:11 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 28, 2009, at 12:23 AM, David MacIver wrote:

So the match expression would be translated to:

 x match {
   case (_: C) => ...
   case (_: object O) => ...
   case y if (y == this.V) => ...
 }

What's your opinion on this?

I agree that the errors caused by this case are somewhat problematic, but I'm not sure they occur commonly enough for it to be worth the spec complication, particularly if (as suggested above) matching on inner objects of a class becomes a warning. I'm also a little concerned that it's not caught statically. If x is known to come from a different instance of Outer, why is this not being rejected as the types of the matches not being subtypes of the matched object? Between that and warning on matching inner case classes I think that would catch most of the use cases adequately.

This is my initial reaction, too, but more broadly.  How important is it to support custom equality methods for case class hierarchies?  

I think it's pretty important. Case classes are basically used for creating custom interesting data structures, and it can be unnecessarily difficult to ensure that the user desired value of equality always matches that of the case class.
 

If people have to use eq for case objects, then it makes those equals methods ugly, but it might simplify some more wide-reaching parts of Scala semantics.

Specifically, it's a pity if a case object pattern matches differently than a val that attempts to have the same meaning as the case object.  Someone might naturally refactor their code to change this:

case object Foo extends Bar

into this:

class GeneralFoo extends Bar
val Foo = new Bar

Unfortunately, if the pattern matcher does different things, this will no longer be a safe refactoring.

Well, that's why I proposed a version in which case object matching is equivalent to stable identifier matching. :-) 

On Fri, Feb 27, 2009 at 11:15 PM, David MacIver <david [dot] maciver [at] gmail [dot] com> wrote:

On Fri, Feb 27, 2009 at 11:11 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Feb 28, 2009, at 12:23 AM, David MacIver wrote:

So the match expression would be translated to:

 x match {
   case (_: C) => ...
   case (_: object O) => ...
   case y if (y == this.V) => ...
 }

What's your opinion on this?

I agree that the errors caused by this case are somewhat problematic, but I'm not sure they occur commonly enough for it to be worth the spec complication, particularly if (as suggested above) matching on inner objects of a class becomes a warning. I'm also a little concerned that it's not caught statically. If x is known to come from a different instance of Outer, why is this not being rejected as the types of the matches not being subtypes of the matched object? Between that and warning on matching inner case classes I think that would catch most of the use cases adequately.

This is my initial reaction, too, but more broadly.  How important is it to support custom equality methods for case class hierarchies?  

I think it's pretty important. Case classes are basically used for creating custom interesting data structures, and it can be unnecessarily difficult to ensure that the user desired value of equality always matches that of the case class.

Sorry. "often" rather than "basically". There are of course other usages.

On Sat, Feb 28, 2009 at 12:15 AM, David MacIver wrote:
> On Fri, Feb 27, 2009 at 11:11 PM, Lex Spoon wrote:
>>
>> On Feb 28, 2009, at 12:23 AM, David MacIver wrote:
>>>
>>> So the match expression would be translated to:
>>>
>>>  x match {
>>>    case (_: C) => ...
>>>    case (_: object O) => ...
>>>    case y if (y == this.V) => ...
>>>  }
>>>
>>> What's your opinion on this?
>>>
>>> I agree that the errors caused by this case are somewhat problematic, but
>>> I'm not sure they occur commonly enough for it to be worth the spec
>>> complication, particularly if (as suggested above) matching on inner objects
>>> of a class becomes a warning. I'm also a little concerned that it's not
>>> caught statically. If x is known to come from a different instance of Outer,
>>> why is this not being rejected as the types of the matches not being
>>> subtypes of the matched object? Between that and warning on matching inner
>>> case classes I think that would catch most of the use cases adequately.
>>
>> This is my initial reaction, too, but more broadly.  How important is it
>> to support custom equality methods for case class hierarchies?
>
> I think it's pretty important. Case classes are basically used for creating
> custom interesting data structures, and it can be unnecessarily difficult to
> ensure that the user desired value of equality always matches that of the
> case class.
>
>>
>> If people have to use eq for case objects, then it makes those equals
>> methods ugly, but it might simplify some more wide-reaching parts of Scala
>> semantics.
>>
>> Specifically, it's a pity if a case object pattern matches differently
>> than a val that attempts to have the same meaning as the case object.
>>  Someone might naturally refactor their code to change this:
>>
>> case object Foo extends Bar
>>
>> into this:
>>
>> class GeneralFoo extends Bar
>> val Foo = new Bar
>>
>> Unfortunately, if the pattern matcher does different things, this will no
>> longer be a safe refactoring.
>
> Well, that's why I proposed a version in which case object matching is
> equivalent to stable identifier matching. :-)
>
I just checked that in

class Outer {
case class Inner()
val i = new Inner()
def isI(x: Any) = x match {
case Inner() => true
case _ => false
}
}

The pattern match in isI will check the this-prefix. I.e. a.isI(b.i) is false.
Somehow I was under the impression before that this was not the case.
I think this tips the balance rather heavily in favor of David's
proposal. I.e.

case Inner() => checks this prefx
case x: Inner => checks this prefix
asInstanceOf[Inner] does not check this prefix but should.

Previously I thought that the middle x: Inner was the odd man out, but
it turns out it is really asInstanceOf which is different from the
others. So I think we should fix asInstanceOf. This means some
refactoring from the pattern matchewr to erasure where asInstanceOf is
handled. Right now, in the pattern matcher we complement the
asInstanceOf with an equality check of the prefix. This will be no
longer necessary once it's done by the asInstanceOf itself.

Cheers

On Sun, Mar 1, 2009 at 9:43 AM, martin odersky wrote:
> On Sat, Feb 28, 2009 at 12:15 AM, David MacIver wrote:
>> On Fri, Feb 27, 2009 at 11:11 PM, Lex Spoon wrote:
>>>
>>> On Feb 28, 2009, at 12:23 AM, David MacIver wrote:
>>>>
>>>> So the match expression would be translated to:
>>>>
>>>>  x match {
>>>>    case (_: C) => ...
>>>>    case (_: object O) => ...
>>>>    case y if (y == this.V) => ...
>>>>  }
>>>>
>>>> What's your opinion on this?
>>>>
>>>> I agree that the errors caused by this case are somewhat problematic, but
>>>> I'm not sure they occur commonly enough for it to be worth the spec
>>>> complication, particularly if (as suggested above) matching on inner objects
>>>> of a class becomes a warning. I'm also a little concerned that it's not
>>>> caught statically. If x is known to come from a different instance of Outer,
>>>> why is this not being rejected as the types of the matches not being
>>>> subtypes of the matched object? Between that and warning on matching inner
>>>> case classes I think that would catch most of the use cases adequately.
>>>
>>> This is my initial reaction, too, but more broadly.  How important is it
>>> to support custom equality methods for case class hierarchies?
>>
>> I think it's pretty important. Case classes are basically used for creating
>> custom interesting data structures, and it can be unnecessarily difficult to
>> ensure that the user desired value of equality always matches that of the
>> case class.
>>
>>>
>>> If people have to use eq for case objects, then it makes those equals
>>> methods ugly, but it might simplify some more wide-reaching parts of Scala
>>> semantics.
>>>
>>> Specifically, it's a pity if a case object pattern matches differently
>>> than a val that attempts to have the same meaning as the case object.
>>>  Someone might naturally refactor their code to change this:
>>>
>>> case object Foo extends Bar
>>>
>>> into this:
>>>
>>> class GeneralFoo extends Bar
>>> val Foo = new Bar
>>>
>>> Unfortunately, if the pattern matcher does different things, this will no
>>> longer be a safe refactoring.
>>
>> Well, that's why I proposed a version in which case object matching is
>> equivalent to stable identifier matching. :-)
>>
> I just checked that in
>
> class Outer {
>  case class Inner()
>  val i = new Inner()
>  def isI(x: Any) = x match {
>    case Inner() => true
>    case _ => false
>  }
> }
>
> The pattern match in isI will check the this-prefix. I.e. a.isI(b.i) is false.
> Somehow I was under the impression before that this was not the case.
> I think this tips the balance rather heavily in favor of David's
> proposal. I.e.
>
>  case Inner() =>  checks this prefx
>  case x: Inner => checks this prefix
>  asInstanceOf[Inner] does not check this prefix but should.
>
> Previously I thought that the middle x: Inner was the odd man out, but
> it turns out it is really asInstanceOf which is different from the
> others.  So I think we should fix asInstanceOf. This means some
> refactoring from the pattern matchewr to erasure where asInstanceOf is
> handled. Right now, in the pattern matcher we complement the
> asInstanceOf with an equality check of the prefix. This will be no
> longer necessary once it's done by the asInstanceOf itself.

That seems reasonable.

Now is as good a time as any to mention that, as you've probably
noticed, I'm not having much luck with the pattern matcher at the
moment. :-) Between work and other time sinks I'm only able to put
about a day's work here and there into it right now, and that's not
enough for me to really break the back of most of the remaining
problems with it, let alone start to make substantial changes to its
logic. My plan is that at some point in the not too distant future
I'll take a week off work to devote some solid time to it, and
hopefully I'll be able to make enough progress in the course of that
to get things back on track. Making changes to the way most of this
works will probably have to wait until then.

Hi David,

That's fine. Thanks for doing this in the first place! I completely
understand that there are constraints how much time you can put into
this when.

Cheers

Thanks. :-)

Back on the previous subject, what should this code do?

object Test {

def foo(x : Any) : Any = {
case class Foo();
println(x match {
case Foo() => true
case _ => false;
})
new Foo;
}

def main(args : Array[String]){
foo(foo(new AnyRef))
}
}

The two Foos come from different invocations of the method (which are
morally equivalent to different instances of an enclosing class in my
opinion), but they still match as eachother. This seems wrong, but I'm
not sure what to suggest as an alternative.

On Sun, Mar 1, 2009 at 1:15 PM, martin odersky wrote:
> Hi David,
>
> That's fine. Thanks for doing this in the first place! I completely
> understand that there are constraints how much time you can put into
> this when.
>
> Cheers
>
>  -- Martin
>
>
> On Sun, Mar 1, 2009 at 2:10 PM, David MacIver wrote:
>> On Sun, Mar 1, 2009 at 9:43 AM, martin odersky wrote:
>>> On Sat, Feb 28, 2009 at 12:15 AM, David MacIver wrote:
>>>> On Fri, Feb 27, 2009 at 11:11 PM, Lex Spoon wrote:
>>>>>
>>>>> On Feb 28, 2009, at 12:23 AM, David MacIver wrote:
>>>>>>
>>>>>> So the match expression would be translated to:
>>>>>>
>>>>>>  x match {
>>>>>>    case (_: C) => ...
>>>>>>    case (_: object O) => ...
>>>>>>    case y if (y == this.V) => ...
>>>>>>  }
>>>>>>
>>>>>> What's your opinion on this?
>>>>>>
>>>>>> I agree that the errors caused by this case are somewhat problematic, but
>>>>>> I'm not sure they occur commonly enough for it to be worth the spec
>>>>>> complication, particularly if (as suggested above) matching on inner objects
>>>>>> of a class becomes a warning. I'm also a little concerned that it's not
>>>>>> caught statically. If x is known to come from a different instance of Outer,
>>>>>> why is this not being rejected as the types of the matches not being
>>>>>> subtypes of the matched object? Between that and warning on matching inner
>>>>>> case classes I think that would catch most of the use cases adequately.
>>>>>
>>>>> This is my initial reaction, too, but more broadly.  How important is it
>>>>> to support custom equality methods for case class hierarchies?
>>>>
>>>> I think it's pretty important. Case classes are basically used for creating
>>>> custom interesting data structures, and it can be unnecessarily difficult to
>>>> ensure that the user desired value of equality always matches that of the
>>>> case class.
>>>>
>>>>>
>>>>> If people have to use eq for case objects, then it makes those equals
>>>>> methods ugly, but it might simplify some more wide-reaching parts of Scala
>>>>> semantics.
>>>>>
>>>>> Specifically, it's a pity if a case object pattern matches differently
>>>>> than a val that attempts to have the same meaning as the case object.
>>>>>  Someone might naturally refactor their code to change this:
>>>>>
>>>>> case object Foo extends Bar
>>>>>
>>>>> into this:
>>>>>
>>>>> class GeneralFoo extends Bar
>>>>> val Foo = new Bar
>>>>>
>>>>> Unfortunately, if the pattern matcher does different things, this will no
>>>>> longer be a safe refactoring.
>>>>
>>>> Well, that's why I proposed a version in which case object matching is
>>>> equivalent to stable identifier matching. :-)
>>>>
>>> I just checked that in
>>>
>>> class Outer {
>>>  case class Inner()
>>>  val i = new Inner()
>>>  def isI(x: Any) = x match {
>>>    case Inner() => true
>>>    case _ => false
>>>  }
>>> }
>>>
>>> The pattern match in isI will check the this-prefix. I.e. a.isI(b.i) is false.
>>> Somehow I was under the impression before that this was not the case.
>>> I think this tips the balance rather heavily in favor of David's
>>> proposal. I.e.
>>>
>>>  case Inner() =>  checks this prefx
>>>  case x: Inner => checks this prefix
>>>  asInstanceOf[Inner] does not check this prefix but should.
>>>
>>> Previously I thought that the middle x: Inner was the odd man out, but
>>> it turns out it is really asInstanceOf which is different from the
>>> others.  So I think we should fix asInstanceOf. This means some
>>> refactoring from the pattern matchewr to erasure where asInstanceOf is
>>> handled. Right now, in the pattern matcher we complement the
>>> asInstanceOf with an equality check of the prefix. This will be no
>>> longer necessary once it's done by the asInstanceOf itself.
>>
>> That seems reasonable.
>>
>> Now is as good a time as any to mention that, as you've probably
>> noticed, I'm not having much luck with the pattern matcher at the
>> moment. :-) Between work and other time sinks I'm only able to put
>> about a day's work here and there into it right now, and that's not
>> enough for me to really break the back of most of the remaining
>> problems with it, let alone start to make substantial changes to its
>> logic. My plan is that at some point in the not too distant future
>> I'll take a week off work to devote some solid time to it, and
>> hopefully I'll be able to make enough progress in the course of that
>> to get things back on track. Making changes to the way most of this
>> works will probably have to wait until then.
>>
>>
>

On Sun, Mar 1, 2009 at 3:48 PM, David MacIver wrote:
> Thanks. :-)
>
> Back on the previous subject, what should this code do?
>
> object Test {
>
>  def foo(x : Any) : Any = {
>    case class Foo();
>    println(x match {
>      case Foo() => true
>      case _ => false;
>    })
>    new Foo;
>  }
>
>  def main(args : Array[String]){
>    foo(foo(new AnyRef))
>  }
> }
>
> The two Foos come from different invocations of the method (which are
> morally equivalent to different instances of an enclosing class in my
> opinion), but they still match as eachother. This seems wrong, but I'm
> not sure what to suggest as an alternative.

Paul has pointed out a good solution: Simply create a "local scope"
object for the call and treat all classes defined within the scope to
be inner classes of that object.

On Feb 27, 2009, at 6:59 AM, martin odersky wrote:
> Specifically, the unqualified type name $t$ where $t$ is bound in some
> class, object, or package $C$ is taken as a shorthand for C.this.type
> # t, except if the type $t$ occurs as a part
> of a typed pattern (\sref{sec:typed-patterns}) and C is an inner
> class. In the latter case, $t$ is taken as a shorthand for just C # t.

Of course, that would be a second irregularity in the language that is
added for this feature.

I'm also not sure the current proposal suffices for the goal. Here's
a new thorny case: suppose someone defines two case objects, Zero and
NegativeZero, and defines them to be == but not eq. Some poor user
then walks into this trap:

NegativeZero match {
case Zero => "not reached"
case _ => "safe to divide... except not really"
}

I'm also worried that there might be other instances than case objects
where the definition of equals might accidentally get into an infinite
loop. I can't come up with one off-hand, however.

The overall goal seems to be to have a low-level pattern match used to
define the meaning of a high-level pattern match. That is, a
programmer wants to define how pattern matching should work on the
case class they are defining, and they want to use pattern matching to
do it. Is there perhaps a way to come up with a syntax that means
don't even try to use == ? That way might be more explicit and
require fewer special cases. As well, it might lead to a better
general reason to think the feature is working as desired.

-Lex

On Tue, Mar 3, 2009 at 4:38 PM, Lex Spoon wrote:
> On Feb 27, 2009, at 6:59 AM, martin odersky wrote:
>>
>> Specifically, the unqualified type name $t$ where $t$ is bound in some
>> class, object, or package $C$ is taken as a shorthand for C.this.type
>> # t, except if the type $t$ occurs as a part
>> of a typed pattern (\sref{sec:typed-patterns}) and C is an inner
>> class. In the latter case, $t$ is taken as a shorthand for just C # t.
>
> Of course, that would be a second irregularity in the language that is added
> for this feature.

I think the feature is already retracted. We'll stick to the current
meaning of pattern matching and adapt asInstanceOf.

>
> I'm also not sure the current proposal suffices for the goal.  Here's a new
> thorny case:  suppose someone defines two case objects, Zero and
> NegativeZero, and defines them to be == but not eq.  Some poor user then
> walks into this trap:
>
>  NegativeZero match {
>    case Zero => "not reached"
>    case _ => "safe to divide... except not really"
>  }
>
> I'm also worried that there might be other instances than case objects where
> the definition of equals might accidentally get into an infinite loop.  I
> can't come up with one off-hand, however.
>
> The overall goal seems to be to have a low-level pattern match used to
> define the meaning of a high-level pattern match.  That is, a programmer
> wants to define how pattern matching should work on the case class they are
> defining, and they want to use pattern matching to do it.  Is there perhaps
> a way to come up with a syntax that means don't even try to use ==  ?  That
> way might be more explicit and require fewer special cases.  As well, it
> might lead to  a better general reason to think the feature is working as
> desired.
>
The problem is you always need equality for prefix paths for inner
classes. So the problem will
not go away completely.

Cheers

I'm a little confused as to the current state of proposals and who is
agreeing with which parts. Let's see if I have this right. As I
understand it there are two orthogonal questions and suggestions under
consideration:

Q) What happens when pattern matching on inner classes?
A)

Current suggestion is that we adapt isInstanceOf so that it checks prefixes.

i.e. given

class Foo{
class Bar;

def stuff(that : Any) = that.isInstanceOf[Bar];
}

val x = new Foo;
val y = new Foo;

x.stuff(new y.Bar) == false;
x.stuff(new x.Bar) == true;

Pattern matching would inherit this behaviour automatically.

Q) What happens to pattern matching on case objects when a custom
equality method is defined?
A)

Stable identifier pattern matching will be redefined so that

case x@X =>

is translated to mean

case (x : X.type) if (X eq x || X == x) =>

Matching on an object (case or not) will be treated exactly like any
other stable identifier

This means that when you have a top level object and pattern match on
it, the user defined equality will never in fact be invoked: Things
will not hit the guard unless they are eq X, so never get the X == x
test. However for things like val X : MySuperType = new MyCaseClass();
the test will be an equality test as you would expect.

Does this accurately capture the latest state of proposals? Lex, could
you clarify which of these you're objecting to? Martin, were you ok
with the second one in the end?

On Tue, Mar 3, 2009 at 5:08 PM, David MacIver wrote:
> I'm a little confused as to the current state of proposals and who is
> agreeing with which parts. Let's see if I have this right.  As I
> understand it there are two orthogonal questions and suggestions under
> consideration:
>
> Q) What happens when pattern matching on inner classes?
> A)
>
> Current suggestion is that we adapt isInstanceOf so that it checks prefixes.
>
> i.e. given
>
> class Foo{
>   class Bar;
>
>   def stuff(that : Any) = that.isInstanceOf[Bar];
> }
>
> val x = new Foo;
> val y = new Foo;
>
> x.stuff(new y.Bar) == false;
> x.stuff(new x.Bar) == true;
>
> Pattern matching would inherit this behaviour automatically.
>
Yes, OK.

> Q) What happens to pattern matching on case objects when a custom
> equality method is defined?
> A)
>
> Stable identifier pattern matching will be redefined so that
>
> case x@X =>
>
> is translated to mean
>
> case (x : X.type) if (X eq x || X == x) =>
>
I am not at all sure about this one. You said you and Paul discovered
a type soundness hole with the previosu scheme. Can you remind me what
this was?

Thanks

On Tue, Mar 3, 2009 at 6:03 PM, martin odersky wrote:
>> Q) What happens to pattern matching on case objects when a custom
>> equality method is defined?
>> A)
>>
>> Stable identifier pattern matching will be redefined so that
>>
>> case x@X =>
>>
>> is translated to mean
>>
>> case (x : X.type) if (X eq x || X == x) =>

Oops. I actually didn't mean X.type here. Sorry! I meant the type of X
rather than the singleton type of X. Is there a good notation for
that?

> I am not at all sure about this one. You said you and Paul discovered
> a type soundness hole with the previosu scheme. Can you remind me what
> this was?

The problem is that the pattern matcher assumes that when we have

case x@X => ...

then x has the same type as X.

But in actual fact the most specific type you can infer for x is Any
(because equality is essentially arbitrary). This means that this
pattern will result in a CCE when X == returns true for anything that
has a more general type.

In this use case it doesn't really matter that much in most cases, but
it matters often enough that it would be a nuisance to not be able to
assume any more specific type for x. Particularly annoying is the case
where you have:

case x@(SomeConstant | SomeOtherConstant) =>

At this point it becomes really annoying.

So we want to keep the assumption that x has the same type of X, so we
enforce it at the pattern level.

What we decided on when we discussed this a while back was that we
would change this so that the type assumption was enforced. i.e. we
would add an additional type check to the constant pattern match so
that only things with the same type as X would match it as a pattern.

So where

case x@X =>

currently simply becomes

case temp if X == temp => val x = temp.asInstanceOf[type of X]

it would instead become

case x : (type of X) if X == x =>

In particular this has the consequence that if X is a top level object
then only X can match itself as a pattern.

What I've proposed in this thread is simply adding an additional
clause to the guard which lets us shortcut the equality check when the
matched value is eq to the constant. So it becomes:

case x : (type of X) if (X eq x) || (X == x) =>

This guarantees that all top level objects do match themselves as a
pattern without having to perform a user defined equality check, while
leaving all sensible equality implementations unchanged.

On Tue, Mar 3, 2009 at 7:38 PM, David MacIver wrote:
> On Tue, Mar 3, 2009 at 6:03 PM, martin odersky wrote:
>>> Q) What happens to pattern matching on case objects when a custom
>>> equality method is defined?
>>> A)
>>>
>>> Stable identifier pattern matching will be redefined so that
>>>
>>> case x@X =>
>>>
>>> is translated to mean
>>>
>>> case (x : X.type) if (X eq x || X == x) =>
>
> Oops. I actually didn't mean X.type here. Sorry! I meant the type of X
> rather than the singleton type of X. Is there a good notation for
> that?
>
Not in scala syntax. Let's write this typeof(x) to be clear. But I
understood what you meant anyway.

>> I am not at all sure about this one. You said you and Paul discovered
>> a type soundness hole with the previosu scheme. Can you remind me what
>> this was?
>
> The problem is that the pattern matcher assumes that when we have
>
> case x@X => ...
>
> then x has the same type as X.
>
I just verified this. This is certainly a huge problem. We have two
ways of fixing this though, either by changing the typing rule or by
changing the
matching behavior. In my opinion it could be reasonable to assume for
x only the expected type of the pattern. It's worth an experiment to
see whether this would break any code.

Cheers

I'm losing track as well. FWIW:

On Mar 3, 2009, at 11:08 AM, David MacIver wrote:
> Q) What happens when pattern matching on inner classes?
> A)
>
> Current suggestion is that we adapt isInstanceOf so that it checks
> prefixes.

I like that. I thought that was already how it worked, because I
remember this issue being discussed years ago. I don't remember how
those discussions came out, though.

> def stuff(that : Any) = that.isInstanceOf[Bar];
>
> val x = new Foo;
> val y = new Foo;
>
> x.stuff(new y.Bar) == false;
> x.stuff(new x.Bar) == true;

Yeah, cool.

> Q) What happens to pattern matching on case objects when a custom
> equality method is defined?
> A)
>
> Stable identifier pattern matching will be redefined so that
>
> case x@X =>
>
> is translated to mean
>
> case (x : X.type) if (X eq x || X == x) =>
>
> Matching on an object (case or not) will be treated exactly like any
> other stable identifier

I objected to having case objects be treated differently than vals.
This more general rule about any stable path looks much better.

However, what about the example I gave where two case objects are ==
but not eq ? I gave the example of Zero and NegativeZero. If "case
Zero" turns into an eq test, then that means users can't use "case
Zero" to match NegativeZero.

-Lex

On Tue, Mar 3, 2009 at 7:18 PM, martin odersky wrote:
>> Oops. I actually didn't mean X.type here. Sorry! I meant the type of X
>> rather than the singleton type of X. Is there a good notation for
>> that?
>>
> Not in scala syntax. Let's write this typeof(x) to be clear. But I
> understood what you meant anyway.

Ok.

>>> I am not at all sure about this one. You said you and Paul discovered
>>> a type soundness hole with the previosu scheme. Can you remind me what
>>> this was?
>>
>> The problem is that the pattern matcher assumes that when we have
>>
>> case x@X => ...
>>
>> then x has the same type as X.
>>
> I just verified this. This is certainly a huge problem. We have two
> ways of fixing this though, either by changing the typing rule or by
> changing the
> matching behavior. In my opinion it could be reasonable to assume for
> x only the expected type of the pattern. It's worth an experiment to
> see whether this would break any code.

When we discussed this last time the conclusion was that adding the
additional check was nicer because it means that the runtime type of a
pattern is always a subtype of its static type. Having a constant
match something which is not of its type has always struck me as very
weird behaviour.

I also don't think having case x@X => having x as Any is a valid option:

- It would mean that for consistency we really have to have case x@(X
| Y) => match x as any.
- Further, we really need stable identifier patterns to be consistent
with matching literals (as frequently stable identifier patterns will
get turned into matching literals when they have the right type).
- This means that things like case x@('0' | '1' | '2' | '3') => will
max x as Any
- This means that things like creating lexers is much more annoying
(although I notice that the Scala one doesn't actually use variable
binding like this).

It seems like it's just going to introduce a lot of pain.

On Tue, Mar 3, 2009 at 8:12 PM, Lex Spoon wrote:
> I'm losing track as well.  FWIW:
>
>
> On Mar 3, 2009, at 11:08 AM, David MacIver wrote:
>>
>> Q) What happens when pattern matching on inner classes?
>> A)
>>
>> Current suggestion is that we adapt isInstanceOf so that it checks
>> prefixes.
>
> I like that. I thought that was already how it worked, because I remember
> this issue being discussed years ago.  I don't remember how those
> discussions came out, though.

It's currently how it works in pattern matching but not how it works
in isInstanceOf. I think. I'd need to double check to be sure.

>> Q) What happens to pattern matching on case objects when a custom
>> equality method is defined?
>> A)
>>
>> Stable identifier pattern matching will be redefined so that
>>
>> case x@X =>
>>
>> is translated to mean
>>
>> case (x : X.type) if (X eq x || X == x) =>
>>
>> Matching on an object (case or not) will be treated exactly like any
>> other stable identifier
>
> I objected to having case objects be treated differently than vals.  This
> more general rule about any stable path looks much better.
>
> However, what about the example I gave where two case objects are == but not
> eq ?  I gave the example of Zero and NegativeZero. If "case Zero" turns into
> an eq test, then that means users can't use "case Zero" to match
> NegativeZero.

I think that's a feature. It's already the case that if you assume
that pattern matching follows your user defined equality rules you're
going to get bitten.

Suppose I have:

abstract class Num{
def toInt : Int;

def equals(x : Any) = that match {
case (x : Num) => this.toInt == that.toInt;
case _ => false;
}
}

case class Positive(x : Int) extends Num{
def toInt = x;
}
case class Negative(x : Int) extends Num{
def toInt = -x;
}

Then if I assume that equality implies they match as eachother I'll be
surprised when

Positive(0) match {
case Negative(0) => true;
case _ => false;
}

return false.

This way matching of case objects is precisely as decoupled from
equality as matching of case classes.

On Tue, Mar 3, 2009 at 5:08 PM, David MacIver wrote:
> I'm a little confused as to the current state of proposals and who is
> agreeing with which parts. Let's see if I have this right.  As I
> understand it there are two orthogonal questions and suggestions under
> consideration:
>
> Q) What happens when pattern matching on inner classes?
> A)
>
> Current suggestion is that we adapt isInstanceOf so that it checks prefixes.
>
> i.e. given
>
> class Foo{
>   class Bar;
>
>   def stuff(that : Any) = that.isInstanceOf[Bar];
> }
>
> val x = new Foo;
> val y = new Foo;
>
> x.stuff(new y.Bar) == false;
> x.stuff(new x.Bar) == true;
>
> Pattern matching would inherit this behaviour automatically.
>
> Q) What happens to pattern matching on case objects when a custom
> equality method is defined?
> A)
>
> Stable identifier pattern matching will be redefined so that
>
> case x@X =>
>
> is translated to mean
>
> case (x : X.type) if (X eq x || X == x) =>
>
What I don't like about this is that a simple test like

case Nil =>

is going to be greatly complicated, and hence made slower by this
rule. But performance of such tests matters! What can we do about
this?

Another problematic thing is that eq works only for AnyRef, so
we need a special case for value types...

Cheers

On Tue, Mar 3, 2009 at 9:02 PM, martin odersky wrote:
> On Tue, Mar 3, 2009 at 5:08 PM, David MacIver wrote:
>> I'm a little confused as to the current state of proposals and who is
>> agreeing with which parts. Let's see if I have this right.  As I
>> understand it there are two orthogonal questions and suggestions under
>> consideration:
>>
>> Q) What happens when pattern matching on inner classes?
>> A)
>>
>> Current suggestion is that we adapt isInstanceOf so that it checks prefixes.
>>
>> i.e. given
>>
>> class Foo{
>>   class Bar;
>>
>>   def stuff(that : Any) = that.isInstanceOf[Bar];
>> }
>>
>> val x = new Foo;
>> val y = new Foo;
>>
>> x.stuff(new y.Bar) == false;
>> x.stuff(new x.Bar) == true;
>>
>> Pattern matching would inherit this behaviour automatically.
>>
>> Q) What happens to pattern matching on case objects when a custom
>> equality method is defined?
>> A)
>>
>> Stable identifier pattern matching will be redefined so that
>>
>> case x@X =>
>>
>> is translated to mean
>>
>> case (x : X.type) if (X eq x || X == x) =>
>>
> What I don't like about this is that a simple test like
>
> case Nil =>
>
> is going to be greatly complicated, and hence made slower by this
> rule. But performance of such tests matters! What can we do about
> this?

No, that doesn't matter, because the implementation is not bound to
follow the specification verbatim as long as it implements equivalent
semantics. In particular for top level objects it's equivalent to just
test for eq, so we're free to do that instead of performing the
specified rewrite (so is in fact potentially faster as we're not
forced to check for ==).

> Another problematic thing is that eq works only for AnyRef, so
> we need a special case for value types...

Oh, that's true. It's not hugely problematic to add that special case though.

On Tue, Mar 3, 2009 at 10:07 PM, David MacIver wrote:
> On Tue, Mar 3, 2009 at 9:02 PM, martin odersky wrote:
>> On Tue, Mar 3, 2009 at 5:08 PM, David MacIver wrote:
>>> I'm a little confused as to the current state of proposals and who is
>>> agreeing with which parts. Let's see if I have this right.  As I
>>> understand it there are two orthogonal questions and suggestions under
>>> consideration:
>>>
>>> Q) What happens when pattern matching on inner classes?
>>> A)
>>>
>>> Current suggestion is that we adapt isInstanceOf so that it checks prefixes.
>>>
>>> i.e. given
>>>
>>> class Foo{
>>>   class Bar;
>>>
>>>   def stuff(that : Any) = that.isInstanceOf[Bar];
>>> }
>>>
>>> val x = new Foo;
>>> val y = new Foo;
>>>
>>> x.stuff(new y.Bar) == false;
>>> x.stuff(new x.Bar) == true;
>>>
>>> Pattern matching would inherit this behaviour automatically.
>>>
>>> Q) What happens to pattern matching on case objects when a custom
>>> equality method is defined?
>>> A)
>>>
>>> Stable identifier pattern matching will be redefined so that
>>>
>>> case x@X =>
>>>
>>> is translated to mean
>>>
>>> case (x : X.type) if (X eq x || X == x) =>
>>>
>> What I don't like about this is that a simple test like
>>
>> case Nil =>
>>
>> is going to be greatly complicated, and hence made slower by this
>> rule. But performance of such tests matters! What can we do about
>> this?
>
> No, that doesn't matter, because the implementation is not bound to
> follow the specification verbatim as long as it implements equivalent
> semantics. In particular for top level objects it's equivalent to just
> test for eq, so we're free to do that instead of performing the
> specified rewrite (so is in fact potentially faster as we're not
> forced to check for ==).
>
You mean for objects that do not override equality right? But that
should be the most common case.

Cheers

On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
> You mean for objects that do not override equality right? But that
> should be the most common case.

No, that's what the eq shortcut is for: It guarantees that for a top
level object X, matching against X will never result in the equality
method being invoked (we already get that it's never invoked for x neq
X from the type test. The eq shortcut guarantees that it will never be
invoked in the remaining case).

On Tue, Mar 3, 2009 at 10:52 PM, David MacIver wrote:
> On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
>> You mean for objects that do not override equality right? But that
>> should be the most common case.
>
> No, that's what the eq shortcut is for: It guarantees that for a top
> level object X, matching against X will never result in the equality
> method being invoked (we already get that it's never invoked for x neq
> X from the type test. The eq shortcut guarantees that it will never be
> invoked in the remaining case).
>
Wait, but I don't want to do the type test! The eq method should
be good enough, unless equals is overridden.

Cheers

On Tue, Mar 3, 2009 at 10:03 PM, martin odersky wrote:
> On Tue, Mar 3, 2009 at 10:52 PM, David MacIver wrote:
>> On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
>>> You mean for objects that do not override equality right? But that
>>> should be the most common case.
>>
>> No, that's what the eq shortcut is for: It guarantees that for a top
>> level object X, matching against X will never result in the equality
>> method being invoked (we already get that it's never invoked for x neq
>> X from the type test. The eq shortcut guarantees that it will never be
>> invoked in the remaining case).
>>
> Wait, but I don't want to do the type test! The eq method should
> be good enough, unless equals is overridden.

Right. But the eq test implies the type test: if X eq x then certainly
x.isInstanceOf[typeof(X)]. Similarly, if x.isInstanceOf[typeof(X)]
then (because X is a singleton and so there's only one instance of
typeof(X)) we have X eq x. So the whole lot can simply be replaced by
X eq x.

On Tue, Mar 3, 2009 at 11:06 PM, David MacIver wrote:
> On Tue, Mar 3, 2009 at 10:03 PM, martin odersky wrote:
>> On Tue, Mar 3, 2009 at 10:52 PM, David MacIver wrote:
>>> On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
>>>> You mean for objects that do not override equality right? But that
>>>> should be the most common case.
>>>
>>> No, that's what the eq shortcut is for: It guarantees that for a top
>>> level object X, matching against X will never result in the equality
>>> method being invoked (we already get that it's never invoked for x neq
>>> X from the type test. The eq shortcut guarantees that it will never be
>>> invoked in the remaining case).
>>>
>> Wait, but I don't want to do the type test! The eq method should
>> be good enough, unless equals is overridden.
>
> Right. But the eq test implies the type test: if X eq x then certainly
> x.isInstanceOf[typeof(X)]. Similarly, if x.isInstanceOf[typeof(X)]
> then (because X is a singleton and so there's only one instance of
> typeof(X)) we have X eq x. So the whole lot can simply be replaced by
> X eq x.
>
Oh yes, of course. So why is this different from nested objects?
If we have

class C { object O }

then x.C eq y.C implies their type is the same (obviously).
Furthermore, if their types are the same, then their prefixes
must be the same, so they are eq. Or am I missing omething?

So that means if we match for a stable identifier X

- if X is an object, use eq
- if X is of a value type, use natural equality
- otherwise use the scheme you have described.

Correct?

On Tue, Mar 3, 2009 at 10:31 PM, martin odersky wrote:
> On Tue, Mar 3, 2009 at 11:06 PM, David MacIver wrote:
>> On Tue, Mar 3, 2009 at 10:03 PM, martin odersky wrote:
>>> On Tue, Mar 3, 2009 at 10:52 PM, David MacIver wrote:
>>>> On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
>>>>> You mean for objects that do not override equality right? But that
>>>>> should be the most common case.
>>>>
>>>> No, that's what the eq shortcut is for: It guarantees that for a top
>>>> level object X, matching against X will never result in the equality
>>>> method being invoked (we already get that it's never invoked for x neq
>>>> X from the type test. The eq shortcut guarantees that it will never be
>>>> invoked in the remaining case).
>>>>
>>> Wait, but I don't want to do the type test! The eq method should
>>> be good enough, unless equals is overridden.
>>
>> Right. But the eq test implies the type test: if X eq x then certainly
>> x.isInstanceOf[typeof(X)]. Similarly, if x.isInstanceOf[typeof(X)]
>> then (because X is a singleton and so there's only one instance of
>> typeof(X)) we have X eq x. So the whole lot can simply be replaced by
>> X eq x.
>>
> Oh yes, of course. So why is this different from nested objects?
> If we have
>
>  class C { object O }
>
>  then x.C eq y.C implies their type is the same (obviously).
>  Furthermore, if their types are the same, then their prefixes
>  must be the same, so they are eq. Or am I missing omething?

No, good point, it's not any different when you take into account the
fact that we check paths. Sorry.

> So that means if we match for a stable identifier X
>
>  - if X is an object, use eq
>  - if X is of a value type, use natural equality

There's a slight ambiguity about what the correct behaviour is here.
Do we add a type test or not? In particular, what is the result of the
following?

1L match {
case 1 => true;
case _ => false;
}

As 1L == 1, but !1L.isInstanceOf[Int] (confusingly,
1L.asInstanceOf[Int] succeeds. I thought I'd opened a ticket about
this inconsistency, but can't find it).

An additional thing worth considering is that if we don't insert these
type tests it makes it a lot harder to emit switches.

>  - otherwise use the scheme you have described.

Yep. (though at the specification level we may not want to reveal that
these behaviours differ, as they can all be regarded as equivalent).

On Tue, Mar 3, 2009 at 11:41 PM, David MacIver wrote:
> On Tue, Mar 3, 2009 at 10:31 PM, martin odersky wrote:
>> On Tue, Mar 3, 2009 at 11:06 PM, David MacIver wrote:
>>> On Tue, Mar 3, 2009 at 10:03 PM, martin odersky wrote:
>>>> On Tue, Mar 3, 2009 at 10:52 PM, David MacIver wrote:
>>>>> On Tue, Mar 3, 2009 at 9:45 PM, martin odersky wrote:
>>>>>> You mean for objects that do not override equality right? But that
>>>>>> should be the most common case.
>>>>>
>>>>> No, that's what the eq shortcut is for: It guarantees that for a top
>>>>> level object X, matching against X will never result in the equality
>>>>> method being invoked (we already get that it's never invoked for x neq
>>>>> X from the type test. The eq shortcut guarantees that it will never be
>>>>> invoked in the remaining case).
>>>>>
>>>> Wait, but I don't want to do the type test! The eq method should
>>>> be good enough, unless equals is overridden.
>>>
>>> Right. But the eq test implies the type test: if X eq x then certainly
>>> x.isInstanceOf[typeof(X)]. Similarly, if x.isInstanceOf[typeof(X)]
>>> then (because X is a singleton and so there's only one instance of
>>> typeof(X)) we have X eq x. So the whole lot can simply be replaced by
>>> X eq x.
>>>
>> Oh yes, of course. So why is this different from nested objects?
>> If we have
>>
>>  class C { object O }
>>
>>  then x.C eq y.C implies their type is the same (obviously).
>>  Furthermore, if their types are the same, then their prefixes
>>  must be the same, so they are eq. Or am I missing omething?
>
> No, good point, it's not any different when you take into account the
> fact that we check paths. Sorry.
>
>> So that means if we match for a stable identifier X
>>
>>  - if X is an object, use eq
>>  - if X is of a value type, use natural equality
>
> There's a slight ambiguity about what the correct behaviour is here.
> Do we add a type test or not? In particular, what is the result of the
> following?
>
> 1L match {
>  case 1 => true;
>  case _ => false;
> }
>
> As 1L == 1, but !1L.isInstanceOf[Int] (confusingly,
> 1L.asInstanceOf[Int] succeeds. I thought I'd opened a ticket about
> this inconsistency, but can't find it).
>
> An additional thing worth considering is that if we don't insert these
> type tests it makes it a lot harder to emit switches.
>
I think you are right. Let's keep the type test in this case. I assume
that the type test can be factored out if we have a large number of
cases all with the same type?

Cheers

On Tue, Mar 3, 2009 at 11:01 PM, martin odersky wrote:
>> As 1L == 1, but !1L.isInstanceOf[Int] (confusingly,
>> 1L.asInstanceOf[Int] succeeds. I thought I'd opened a ticket about
>> this inconsistency, but can't find it).
>>
>> An additional thing worth considering is that if we don't insert these
>> type tests it makes it a lot harder to emit switches.
>>
> I think you are right. Let's keep the type test in this case. I assume
> that the type test can be factored out if we have a large number of
> cases all with the same type?

No reason it couldn't be if it proves necessary, but I'd assume this
was somewhere hotspot would be good at removing repeat tests.
Certainly in the cases where we emit switches the type test would only
be applied once.

In general there are probably a lot of missed opportunities for
optimisation in the pattern matcher. My expectation is that I'll try
to address most of them once I've got the specification details and
the worst of the bugs dealt with.

On Mar 3, 2009, at 3:23 PM, David MacIver wrote:
> Then if I assume that equality implies they match as eachother I'll be
> surprised when
>
> Positive(0) match {
> case Negative(0) => true;
> case _ => false;
> }
>
> return false.

This is basically my point. Case classes are supposed to support
pattern matching. However, if they have non-standard equals methods,
then pattern matching ceases to work intuitively. To contrast, going
the full mile and implementing unapply methods would restore such a
library to having consistent equals() and pattern matching.

-Lex

On Wed, Mar 11, 2009 at 2:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 3, 2009, at 3:23 PM, David MacIver wrote:

Then if I assume that equality implies they match as eachother I'll be
surprised when

Positive(0) match {
 case Negative(0) => true;
 case _ => false;
}

return false.

This is basically my point.  Case classes are supposed to support pattern matching.  However, if they have non-standard equals methods, then pattern matching ceases to work intuitively.  

I don't understand why. The assumption that equality and pattern matching on case classes are at all related seems highly unintuitive to me. In particular it's totally unnecessary for the implementation and strongly limits the utility of case classes for implementing custom data structures, so why is it desirable?
 

To contrast, going the full mile and implementing unapply methods would restore such a library to having consistent equals() and pattern matching.

Sorry, I'm not sure what you mean?

On Mar 11, 2009, at 1:59 PM, David MacIver wrote:

On Wed, Mar 11, 2009 at 2:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 3, 2009, at 3:23 PM, David MacIver wrote:

Then if I assume that equality implies they match as eachother I'll be
surprised when

Positive(0) match {
 case Negative(0) => true;
 case _ => false;
}

return false.

This is basically my point.  Case classes are supposed to support pattern matching.  However, if they have non-standard equals methods, then pattern matching ceases to work intuitively.  

I don't understand why. The assumption that equality and pattern matching on case classes are at all related seems highly unintuitive to me. In particular it's totally unnecessary for the implementation and strongly limits the utility of case classes for implementing custom data structures, so why is it desirable?

This is actually one of the basic design principles of the pattern matchers, so I'm surprised you're not familiar with it. In code, one of the firmest principles of its design is that the following assertion should succeed as often as humanly possible:
x match {  case some_pattern =>  assert (x == some_pattern)}
I've been in a number of design meetings where we worked to keep this true.  The following assertion is slightly different, but would also be great to hold true whenever possible:
if (x == some_pattern)  assert({ case some_pattern => ()}.isDefinedAt(x))

Don't you agree about these?  In general, it's a better programming language if programmers don't have to run the compiler in their head to figure out what's going on.  Giving up the above equivalences is a real harm to people's ability to reason about Scala code.

To contrast, going the full mile and implementing unapply methods would restore such a library to having consistent equals() and pattern matching.

Sorry, I'm not sure what you mean?

If the implementor of Positive, Negative, and Zero used manual apply and unapply methods rather than the default case-class implementation, then pattern matching and equals() could remain consistent.  Therefore, I don't see why a *good* implementor would want to override equals() and then stop there.  Yet, that's exactly the use case that's been proposed for using case classes but overriding equals().

Lex

Array matching already breaks these rules.

scala> Array(1, 2) match { case Array(x, y) => Array(x, y) == Array(1, 2) }
res0: Boolean = false

The rules are good, but in the absence of a useful equals method,
pattern matching should not be hampered.

2009/3/26 Lex Spoon :
> On Mar 11, 2009, at 1:59 PM, David MacIver wrote:
>
> On Wed, Mar 11, 2009 at 2:39 PM, Lex Spoon wrote:
>>
>> On Mar 3, 2009, at 3:23 PM, David MacIver wrote:
>>>
>>> Then if I assume that equality implies they match as eachother I'll be
>>> surprised when
>>>
>>> Positive(0) match {
>>>  case Negative(0) => true;
>>>  case _ => false;
>>> }
>>>
>>> return false.
>>
>> This is basically my point.  Case classes are supposed to support pattern
>> matching.  However, if they have non-standard equals methods, then pattern
>> matching ceases to work intuitively.
>
> I don't understand why. The assumption that equality and pattern matching on
> case classes are at all related seems highly unintuitive to me. In
> particular it's totally unnecessary for the implementation and strongly
> limits the utility of case classes for implementing custom data structures,
> so why is it desirable?
>
> This is actually one of the basic design principles of the pattern matchers,
> so I'm surprised you're not familiar with it. In code, one of the firmest
> principles of its design is that the following assertion should succeed as
> often as humanly possible:
> x match {
>   case some_pattern =>  assert (x == some_pattern)
> }
> I've been in a number of design meetings where we worked to keep this true.
>  The following assertion is slightly different, but would also be great to
> hold true whenever possible:
> if (x == some_pattern)
>   assert({ case some_pattern => ()}.isDefinedAt(x))
>
> Don't you agree about these?  In general, it's a better programming language
> if programmers don't have to run the compiler in their head to figure out
> what's going on.  Giving up the above equivalences is a real harm to
> people's ability to reason about Scala code.
>
>
>> To contrast, going the full mile and implementing unapply methods would
>> restore such a library to having consistent equals() and pattern matching.
>
> Sorry, I'm not sure what you mean?
>
>
> If the implementor of Positive, Negative, and Zero used manual apply and
> unapply methods rather than the default case-class implementation, then
> pattern matching and equals() could remain consistent.  Therefore, I don't
> see why a *good* implementor would want to override equals() and then stop
> there.  Yet, that's exactly the use case that's been proposed for using case
> classes but overriding equals().
>
> Lex
>

A lot of this discussion has skimmed over the top of my head, so I could be wrong, but...

How can:
x match {  case some_pattern =>  assert (x == some_pattern)}

hold true in cases where some_pattern contains wildcards?


On Thu, Mar 26, 2009 at 12:22 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 11, 2009, at 1:59 PM, David MacIver wrote:

On Wed, Mar 11, 2009 at 2:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 3, 2009, at 3:23 PM, David MacIver wrote:

Then if I assume that equality implies they match as eachother I'll be
surprised when

Positive(0) match {
 case Negative(0) => true;
 case _ => false;
}

return false.

This is basically my point.  Case classes are supposed to support pattern matching.  However, if they have non-standard equals methods, then pattern matching ceases to work intuitively.  

I don't understand why. The assumption that equality and pattern matching on case classes are at all related seems highly unintuitive to me. In particular it's totally unnecessary for the implementation and strongly limits the utility of case classes for implementing custom data structures, so why is it desirable?

This is actually one of the basic design principles of the pattern matchers, so I'm surprised you're not familiar with it. In code, one of the firmest principles of its design is that the following assertion should succeed as often as humanly possible:
x match {  case some_pattern =>  assert (x == some_pattern)}
I've been in a number of design meetings where we worked to keep this true.  The following assertion is slightly different, but would also be great to hold true whenever possible:
if (x == some_pattern)  assert({ case some_pattern => ()}.isDefinedAt(x))

Don't you agree about these?  In general, it's a better programming language if programmers don't have to run the compiler in their head to figure out what's going on.  Giving up the above equivalences is a real harm to people's ability to reason about Scala code.

To contrast, going the full mile and implementing unapply methods would restore such a library to having consistent equals() and pattern matching.

Sorry, I'm not sure what you mean?

If the implementor of Positive, Negative, and Zero used manual apply and unapply methods rather than the default case-class implementation, then pattern matching and equals() could remain consistent.  Therefore, I don't see why a *good* implementor would want to override equals() and then stop there.  Yet, that's exactly the use case that's been proposed for using case classes but overriding equals().

Lex

--
http://erikengbrecht.blogspot.com/

Never mind...I forgot how wildcards actually work in pattern matching because I never use them that way.

On Thu, Mar 26, 2009 at 12:58 PM, Erik Engbrecht <erik [dot] engbrecht [at] gmail [dot] com> wrote:

A lot of this discussion has skimmed over the top of my head, so I could be wrong, but...

How can:
x match {  case some_pattern =>  assert (x == some_pattern)}

hold true in cases where some_pattern contains wildcards?


On Thu, Mar 26, 2009 at 12:22 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 11, 2009, at 1:59 PM, David MacIver wrote:

On Wed, Mar 11, 2009 at 2:39 PM, Lex Spoon <lex [at] lexspoon [dot] org> wrote:

On Mar 3, 2009, at 3:23 PM, David MacIver wrote:

Then if I assume that equality implies they match as eachother I'll be
surprised when

Positive(0) match {
 case Negative(0) => true;
 case _ => false;
}

return false.

This is basically my point.  Case classes are supposed to support pattern matching.  However, if they have non-standard equals methods, then pattern matching ceases to work intuitively.  

I don't understand why. The assumption that equality and pattern matching on case classes are at all related seems highly unintuitive to me. In particular it's totally unnecessary for the implementation and strongly limits the utility of case classes for implementing custom data structures, so why is it desirable?

This is actually one of the basic design principles of the pattern matchers, so I'm surprised you're not familiar with it. In code, one of the firmest principles of its design is that the following assertion should succeed as often as humanly possible:
x match {  case some_pattern =>  assert (x == some_pattern)}
I've been in a number of design meetings where we worked to keep this true.  The following assertion is slightly different, but would also be great to hold true whenever possible:
if (x == some_pattern)  assert({ case some_pattern => ()}.isDefinedAt(x))

Don't you agree about these?  In general, it's a better programming language if programmers don't have to run the compiler in their head to figure out what's going on.  Giving up the above equivalences is a real harm to people's ability to reason about Scala code.

To contrast, going the full mile and implementing unapply methods would restore such a library to having consistent equals() and pattern matching.

Sorry, I'm not sure what you mean?

If the implementor of Positive, Negative, and Zero used manual apply and unapply methods rather than the default case-class implementation, then pattern matching and equals() could remain consistent.  Therefore, I don't see why a *good* implementor would want to override equals() and then stop there.  Yet, that's exactly the use case that's been proposed for using case classes but overriding equals().

Lex

--
http://erikengbrecht.blogspot.com/

--
http://erikengbrecht.blogspot.com/

2009/3/26 Lex Spoon :
> I don't understand why. The assumption that equality and pattern matching on
> case classes are at all related seems highly unintuitive to me. In
> particular it's totally unnecessary for the implementation and strongly
> limits the utility of case classes for implementing custom data structures,
> so why is it desirable?
>
> This is actually one of the basic design principles of the pattern matchers,
> so I'm surprised you're not familiar with it. In code, one of the firmest
> principles of its design is that the following assertion should succeed as
> often as humanly possible:
> x match {
>   case some_pattern =>  assert (x == some_pattern)
> }
> I've been in a number of design meetings where we worked to keep this true.
>  The following assertion is slightly different, but would also be great to
> hold true whenever possible:
> if (x == some_pattern)
>   assert({ case some_pattern => ()}.isDefinedAt(x))
>
> Don't you agree about these?

Actually, I don't.

I don't for various reasons. Ignoring language agnostic philosophical
and practical objections, the biggest remaining issue is that these
conditions are logically impossible to satisfy in Scala. You hit all
the problems that equality + subtyping usually has, plus additional
problematic interactions with case class inheritance, and then some
more about the basically untyped nature of equality in Scala.

Here are some examples:

case class Foo(x : Int)
case class Bar(y : Int) extends Foo(0);

Bar(x) match { case Foo(0) => true; case _ => false }

should return true.

Adhering to the principle that matching should imply equality results
in Bar(x) == Foo(0). But therefore Bar(x) == Bar(y) for all x, y.
Therefore according to the principle that equality should imply
something matches as another, Bar(10) should match as Bar(5).

Therefore there is no correct way for these principles to interact
with case class inheritance.

But case class inheritance is known to be dodgy, so it's not
surprising that there are dark corners here. Alas, the problem is not
restricted to case class inheritance. Let's take some more examples:

case class Foo(x : Int);
object Bar extends Foo(0);

Bar match {
case Foo(0) => ...
}

should obviously succeed.

But should

Foo(0) match {
case Bar => ...
}

succeed?

And if so, what type should x have in

Foo(0) match {
case x@Bar => ...
}

Attempting to adhere to the principle that if x == somepattern then x
match { case somepattern => } succeeds loses what I feel is the much
more important principle that if x matches somepattern then typeof(x)
<: typeof(somepattern).

Lest you doubt that this principle is important, consider the following case:

something match {
case x@("foo" | "bar") => x.length
}

I think it is reasonable to expect this to compile, yes?

Further I think it is reasonable to expect it to be equivalent to the following:

val Foo = "foo"
val Bar = "bar"

something match {
case x@(Foo | Bar) => x.length
}

Which of course translates to

something match {
case x@Foo => x.length
case x@Bar => x.length
}

So it's vital that we can assume that matching a constant assumes
we've got something of the same type as the constant (note: Currently
the pattern matcher does assume that. It's just that it doesn't
enforce that to actually hold in the match, so is unsound)

So, given that we have imposed this constraint, it is no longer the
case that equality is enough to determine pattern matching.

> In general, it's a better programming language
> if programmers don't have to run the compiler in their head to figure out
> what's going on.  Giving up the above equivalences is a real harm to
> people's ability to reason about Scala code.

I don't agree. The rules I have described for pattern matching are
simple and consistent and have far fewer gotchas than the existing
behaviour.

>> To contrast, going the full mile and implementing unapply methods would
>> restore such a library to having consistent equals() and pattern matching.
>
> Sorry, I'm not sure what you mean?
>
>
> If the implementor of Positive, Negative, and Zero used manual apply and
> unapply methods rather than the default case-class implementation, then
> pattern matching and equals() could remain consistent.  Therefore, I don't
> see why a *good* implementor would want to override equals() and then stop
> there.  Yet, that's exactly the use case that's been proposed for using case
> classes but overriding equals().

Well, why should they? You're asking them to give up performance and
convenience of implementation for something that not everyone agrees
is important in general and which certainly isn't important in
specific cases.

Let's take a concrete example: IntMap. It uses pattern matching
internally, but this isn't exposed outside its implementation. However
it inherits the Map definition of equality because two immutable maps
should be equal if they have the same key/value mappings. What would
you like it to do instead?

An additional concern, which I admit shouldn't factor into long term
planning, is that the extractor implementation is severely broken and
I don't trust it as far as I can throw it. (Yes, I know it's my job to
fix this. I so far haven't been able to).

2009/3/26 David MacIver :
> Let's take a concrete example: IntMap. It uses pattern matching
> internally, but this isn't exposed outside its implementation. However
> it inherits the Map definition of equality because two immutable maps
> should be equal if they have the same key/value mappings. What would
> you like it to do instead?

As a side note (and I don't particularly intend this to be an argument
for or against this position so much as an interesting data point) I
have noticed that I had major brainfail in working around the
behaviour of equality and matching on IntMap, in that I ended up
doing:

private[immutable] case object Nil extends IntMap[Nothing]{
override def equals(that : Any) = this eq that.asInstanceOf[AnyRef]
};

This is in retrospect obviously contrary to the intended behaviour of
equality, and results in the following issue:

scala> import scala.collection.immutable._
import scala.collection.immutable._

scala> IntMap.empty
res0: scala.collection.immutable.IntMap[Nothing] = IntMap()

scala> HashMap.empty
res1: scala.collection.immutable.HashMap[Nothing,Nothing] = Map()

scala> res1 == res0
res2: Boolean = true

scala> res0 == res1
res3: Boolean = false

scala> IntMap(1 -> 2)
res4: scala.collection.immutable.IntMap[Int] = IntMap(1 -> 2)

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

scala> res4 == res5
res6: Boolean = true

i.e. IntMap.equals does not behave correctly for empty IntMaps.

I'll file a bug (and will fix it later, but not while I'm at work).

On Mar 26, 2009, at 12:58 PM, Erik Engbrecht wrote:
> A lot of this discussion has skimmed over the top of my head, so I
> could be wrong, but...
>
> How can:
> x match {
> case some_pattern => assert (x == some_pattern)
> }
>
> hold true in cases where some_pattern contains wildcards?

There are patterns that aren't valid expressions, but what I described
is a general rule that you'd like to follow in order for patterns to
mean what they intuitively appear to mean.

For wildcards, the rule can easily be patched up to say that a
wildcard pattern is equivalent to a pattern with a fresh variable in
place of the wildcard. That is, List(_,_) would actually be treated
as List(t1, t2). In that case, the above rule holds fine:

x match {
case List(t1,t2) => List(t1,t2) == x // true
}

Lex

On Mar 26, 2009, at 12:58 PM, Ricky Clarkson wrote:
> Array matching already breaks these rules.
>
> scala> Array(1, 2) match { case Array(x, y) => Array(x, y) ==
> Array(1, 2) }
> res0: Boolean = false
>
> The rules are good, but in the absence of a useful equals method,
> pattern matching should not be hampered.

True, but that's an argument that there are funny corner cases with
arrays. To that I would completely agree, but nobody is going to be
convinced either way by arguments about odd array corner cases. It's
much more important that plain old case classes work well.

Lex

Hey, David,

I'm not sure how to answer briefly, because you write and write and
write. :) I might suggest two things as focus points. First, do you
think Scala pattern matching will be possible to understand without
mentally desugaring the pattern matches? If we leave out custom
equals methods, then there are some helpful properties such as the
equals properties I showed. You dismissed those on unspecified
philosophical grounds, and the only counter-proposal you offer is one
that, as I explain below, does not hold. Doesn't this mean Scala
pattern matching is left in such a way that programmers must play
compiler to understand what a pattern means?

Second, what do you think of this example:

x match {
case Foo(0) => // case 1
case _ => // case 2
}

Personally, if case 1 can be skipped even for objects that are ==
Foo(0), I really think pattern matching has become less intuitive.
This is just the kind of puzzler that a carefully designed language
could avoid, if we try. It's too bad arrays work that way, but do we
have to add case classes to the list?

On details:

> Here are some examples:
>
> case class Foo(x : Int)
> case class Bar(y : Int) extends Foo(0);
>
> Bar(x) match { case Foo(0) => true; case _ => false }
>
> should return true.
>
> Adhering to the principle that matching should imply equality results
> in Bar(x) == Foo(0). But therefore Bar(x) == Bar(y) for all x, y.
> Therefore according to the principle that equality should imply
> something matches as another, Bar(10) should match as Bar(5).

Like you say, I agree that case class inheritance appears to imply
some various oddities. I would hope that oddities of inheriting case
classes would not cause us to weaken what you get from normal case
classes.

On the particular examples, I agree with you. I have followed similar
reasoning in the past to decide that case class inheritance is
problematic. You have to choose one of three poisons:

Matching against Foo(0) can give you something not == to Foo(0).
Equality is not transitive.
Bar(5) == Bar(10), even though they aren't intuitively "equal".

You are leaping to choose the first of these. So be it, if it only
applies to case class inheritance. I simply don't see it as a reason
to weaken what programmer can assume about patterns for more typical
case classes.

> Attempting to adhere to the principle that if x == somepattern then x
> match { case somepattern => } succeeds loses what I feel is the much
> more important principle that if x matches somepattern then typeof(x)
> <: typeof(somepattern).

Some such typing rule would be good, but it doesn't hold, and it
doesn't look likely to hold. Here's an example violation:

val A: Zero.type = Zero
val B: Positive = new Positive(0)

In this case, A==B, so the following pattern matches succeed.
However, in both cases the type of x cannot soundly be the type of the
pattern.

A match { case x@B => x }
B match { case x@A => x }

I don't see any problem, though. It looks simply like something for
the compiler to be careful about. Also, note that for many special
cases, the compiler can still tighten the type of the pattern variable.

>
> Lest you doubt that this principle is important, consider the
> following case:
>
[...]
>
> Which of course translates to
>
> something match {
> case x@Foo => x.length
> case x@Bar => x.length
> }
>
> So it's vital that we can assume that matching a constant assumes
> we've got something of the same type as the constant (note: Currently
> the pattern matcher does assume that. It's just that it doesn't
> enforce that to actually hold in the match, so is unsound)

This would be an example of an important special case. A pattern
match on Strings, or any literal, would be on a type the compiler can
be told to understand will only match same-typed things.

>> In general, it's a better programming language
>> if programmers don't have to run the compiler in their head to
>> figure out
>> what's going on. Giving up the above equivalences is a real harm to
>> people's ability to reason about Scala code.
>
> I don't agree. The rules I have described for pattern matching are
> simple and consistent and have far fewer gotchas than the existing
> behaviour.

You have only given one rule, the typing one, and it doesn't hold. As
for gotchas, it doesn't make sense that adding a new feature, case
classes with equals methods, could remove a gotcha for people who
don't use them.

>
>
>>> To contrast, going the full mile and implementing unapply methods
>>> would
>>> restore such a library to having consistent equals() and pattern
>>> matching.
>>
>> Sorry, I'm not sure what you mean?
>>
>>
>> If the implementor of Positive, Negative, and Zero used manual
>> apply and
>> unapply methods rather than the default case-class implementation,
>> then
>> pattern matching and equals() could remain consistent. Therefore,
>> I don't
>> see why a *good* implementor would want to override equals() and
>> then stop
>> there. Yet, that's exactly the use case that's been proposed for
>> using case
>> classes but overriding equals().
>
> Well, why should they? You're asking them to give up performance and
> convenience of implementation for something that not everyone agrees
> is important in general and which certainly isn't important in
> specific cases.

It doesn't feel like an honest debate if I have to spell out something
like this. To take a shot at it, it's like the example I gave above.
It looks better if users of the library can write code like this:

x match {
case Zero => // handle zero case
case _ => // handled non-zero case
}

Wouldn't it be preferable for this to work than for this to not work?

> Let's take a concrete example: IntMap. It uses pattern matching
> internally, but this isn't exposed outside its implementation. However
> it inherits the Map definition of equality because two immutable maps
> should be equal if they have the same key/value mappings. What would
> you like it to do instead?

I have looked at this example now, the IntMap Nil case actually fails
that test: it is not equal to anything but itself. Nonetheless, we
could imagine fixing this up so that, as you describe, all IntMaps are
equals() to other kind of maps that have the same mappings in them.

As you can guess, I don't think this is a happy situation. Pattern
matching on IntMaps will behave funny from a user's perspective. To
correct this, I concede that the library developer would have to add
an extra wrapper object to get the desired equals() method.

I'm not sure how big of a deal the extra wrapper object is. It needs
to be weighed against other issues.

Are there any other examples you can provide? I'm not seeing a strong
win for custom equals methods, and I really would like if pattern
matching was as intuitive as possible w.r.t. equals().

> An additional concern, which I admit shouldn't factor into long term
> planning, is that the extractor implementation is severely broken and
> I don't trust it as far as I can throw it.

How unfortunate.

Overall, I see that it might be nice to provide some kind of "high-
level equals" that would be different from the equals you get from
case classes. The objections I raise wouldn't rule this out
entirely. Is there perhaps a way Scala could have "high-level"
equality and "low-level" equality? One level for users of a data
structure, and one for the implementor of that data structure? When
you implement IntMap, an empty IntMap really isn't the same as an
empty hash map. When you use an IntMap via the Map interface,
however, you'd prefer to think of them as the same.

Lex

Hi David,

On Fri, Mar 27, 2009 at 1:28 AM, David MacIver wrote:
>
> I don't for various reasons. Ignoring language agnostic philosophical
> and practical objections, the biggest remaining issue is that these
> conditions are logically impossible to satisfy in Scala. You hit all
> the problems that equality + subtyping usually has, plus additional
> problematic interactions with case class inheritance, and then some
> more about the basically untyped nature of equality in Scala.
>
> Here are some examples:
>
> case class Foo(x : Int)
> case class Bar(y : Int) extends Foo(0);
>
> Bar(x) match { case Foo(0) => true; case _ => false }
>
> should return true.
>
> Adhering to the principle that matching should imply equality results
> in Bar(x) == Foo(0). But therefore Bar(x) == Bar(y) for all x, y.
> Therefore according to the principle that equality should imply
> something matches as another, Bar(10) should match as Bar(5).
>
> Therefore there is no correct way for these principles to interact
> with case class inheritance.
>
I apologize in advance because I haven't had time to really study this
discussion, but these comments here reminded me of a concern I'd had
that I never expressed and there's an off chance it would help here.
In the PinS book, we published in the equality chapter an approach to
dealing with equals and inheritance that works, and it was the first
time I'd actually seen a real solution to this problem in all my years
of Java. Martin figured it out of course. But then it seemed
inconsistent to me that the equals and hashCode generated in case
classes did not match the "recommended" way for people to write these
methods by hand that we published in the book. So the question I had
is, would it make sense to do that? Would using that approach address
the problems that you're complaining about here?

If you don't have the book let me know and I can post here what it is,
but if you have the book look for canEqual in the Equality chapter.

Thanks.

Bill

On Thu, 2009-04-02 at 22:22 +0800, Bill Venners wrote:
> I apologize in advance because I haven't had time to really study this
> discussion, but these comments here reminded me of a concern I'd had
> that I never expressed and there's an off chance it would help here.
> In the PinS book, we published in the equality chapter an approach to
> dealing with equals and inheritance that works, and it was the first
> time I'd actually seen a real solution to this problem in all my years
> of Java. Martin figured it out of course. But then it seemed
> inconsistent to me that the equals and hashCode generated in case
> classes did not match the "recommended" way for people to write these
> methods by hand that we published in the book. So the question I had
> is, would it make sense to do that? Would using that approach address
> the problems that you're complaining about here?

Someone asked about that a few months ago and, if I recall correctly,
Martin said at the time that he planned to do it for 2.8.0 (and had not
done it before because it could cause breakage).

Best,
Ismael

I lack the time right now to make a meaningful contribution to this
discussion, but I think its resolution is extremely important so I hope
it will continue until everyone is within a tolerable delta of
satisfied, although I admit that to me it seems unnecessarily tense.

I have one question:

On Thu, Apr 02, 2009 at 10:10:04AM -0400, Lex Spoon wrote:
> Like you say, I agree that case class inheritance appears to imply
> some various oddities.

Is it too late to deprecate case class inheritance? Maybe it wouldn't
seem like such a bugbear if the pattern matcher were otherwise solid,
but as things stand it isn't and case class inheritance complicates the
spec, the implementation, and the number of unavoidable mismatches
between intuition and reality.

On Thu, Apr 02, 2009 at 10:22:37PM +0800, Bill Venners wrote:
> In the PinS book, we published in the equality chapter an approach to
> dealing with equals and inheritance that works, and it was the first
> time I'd actually seen a real solution to this problem in all my years
> of Java. Martin figured it out of course. But then it seemed
> inconsistent to me that the equals and hashCode generated in case
> classes did not match the "recommended" way for people to write these
> methods by hand that we published in the book.

And at present they don't meet the equals contract:

https://lampsvn.epfl.ch/trac/scala/ticket/1332

On Thu, Apr 2, 2009 at 4:52 PM, Paul Phillips wrote:
> I lack the time right now to make a meaningful contribution to this
> discussion, but I think its resolution is extremely important so I hope
> it will continue until everyone is within a tolerable delta of
> satisfied, although I admit that to me it seems unnecessarily tense.
>
> I have one question:
>
> On Thu, Apr 02, 2009 at 10:10:04AM -0400, Lex Spoon wrote:
>> Like you say, I agree that case class inheritance appears to imply
>> some various oddities.
>
> Is it too late to deprecate case class inheritance? Maybe it wouldn't
> seem like such a bugbear if the pattern matcher were otherwise solid,
> but as things stand it isn't and case class inheritance complicates the
> spec, the implementation, and the number of unavoidable mismatches
> between intuition and reality.

I think it might not be too late. Case class inheritance was added
rather late, and as an afterthought, without having really thought the
issues through. So we might not break too much code deprecating them.
(I also noted a rather
unfortunate misunderstanding where newbies start with an abstract case
class extended by other case classes; they did not intend to match on
the abstract class; they were just unsure where to put the case, so
they put it everywhere).

I am not yet saying we should deprecate them, just that it's worth
discussing the issue.

Cheers