This page is no longer maintained — Please continue to the home page at www.scala-lang.org

Equality and case objects

53 replies
David Pollak
Joined: 2008-12-16,
User offline. Last seen 42 years 45 weeks ago.
Re: Equality and case objects

I've never seen or found a use for case class hierchies.  I'd be all for deprecating them.

On Apr 2, 2009 9:43 AM, "martin odersky" <martin [dot] odersky [at] epfl [dot] ch> wrote:

On Thu, Apr 2, 2009 at 4:52 PM, Paul Phillips <paulp [at] improving [dot] org> wrote: > I lack the time right n...

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

DRMacIver
Joined: 2008-09-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Equality and case objects

2009/4/2 Lex Spoon :
> Hey, David,
>
> I'm not sure how to answer briefly, because you write and write and write.
>  :)

Sorry if it's a bit overwhelming. The problem is I've spent a *lot* of
time thinking about these problems (I've spent far more time finding
problems with the pattern matcher than I have fixing them
unfortunately), and they're endlessly subtle, so I really don't want
this underemphasised.

> 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?

Yes, absolutely.

> 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

I'll happily get into those if you want me to. I de-emphasised them
because there are more than enough technical and practical problems to
fret about.

> counter-proposal you offer is one that, as I explain below, does not hold.

Well, neither property holds. The question is which one can be made to
hold the most consistently and which is the more important.

>  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?

It should be noted that the fact that arrays work that way is nothing
more than a symptom of the general fact that extractors work that way:
There's nothing to tie apply and unapply together, and no guarantees
of what equality methods are present.

> 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.

I agree that it breaking for case classes is not a compelling reason
for violating this principle in general: I would certainly agree that
it's a valuable property for users to implement. But it should be
noted that case class inheritance works very straightforwardly if
you're not worried about interaction with equality.

>> 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 }

Well, yes. Example violations are easy to construct. That's what
sparked some of the issues that act as backstory to this conversation
off: I want to tighten up pattern matching so that those violations
don't match (Martin tentatively agreed with this, though I expect that
it will be up for further discussion once I have an implementation).
In particular, Positive(0) *shouldn't* match case Zero =>.

> 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.

The phrase "many special cases" worries me a lot. :-)

In particular:

>> 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.

I would desperately like to avoid doing this.

If the compiler has to have special knowledge of pattern matching on
user types in order to determine the type correctness of certain
patterns then we've created a situation in which the pattern matcher
for the standard library has more expressive power than user code.
This seems very very desireable to avoid.

Granted that the literal patterns are already a special case. But the
constant patterns are equally important. In particular having a user
define something like

val Foo : Thing = stuff;
val Bar : Thing = otherstuff;

x match { case y@(Foo | Bar) => }

and have y be an Any seems like we're doing the user a terrible disservice.

>>> 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.

It only fails to hold in a subset of cases, which we've tentatively
concluded the spec should be updated to change so that it does hold.
Between the typing rule and the rule that

somepattern match {
case somepattern => ;
}

succeeds this covers most of the cases.

> 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.

It's not a new feature. Case classes have always (or at least for as
long as I've used the language) been allowed user definable equals
methods. All I've proposed is to make matching on case objects not
break when you use this fact.

>> 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.

this may be an instance of different debating styles. I find it's very
useful for both sides to spell things out in detail where there is a
disagreement, as often disagreements are too high level to find the
exact point at which one differs.

> 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?

No, I really don't see that it would be. My inclination would be that
if you really wanted something like this to work then it's a perfect
instance

case object ConstantZero extends Num;
case class Positive(n : Int) extends Num;
case class Negative(n : Int) extends Num;

object Zero{
def unapply(x : Num) = x match { case ConstantZero | Positive(0) |
Negative(0) => true; case _ => false }
}

(Of course this brings us back to the problem of working extractors,
but oh well...)

>> 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.

Not really: The user doesn't pattern match on IntMaps. The fact that
it is implemented in terms of pattern matching is entirely hidden from
them.

> 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.

I think it's a big deal. There are a lot of cases where having to
construct additional wrappers turns operations that should be cheap
into expensive ones.

For example:

> Are there any other examples you can provide?

https://lampsvn.epfl.ch/trac/scala/ticket/761 is unfixable without
custom equality methods or a wrapper object. If you use a wrapper
object then List.tail needs to allocate a new wrapper, which seems
exceedingly non-ideal. Further we want to continue to be able to
pattern match on List, so we need to provide extractors for that case,
which means more performance issues...

> 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().

If I haven't already (I can't remember), I should emphasise that I am
in favour of people implementing equality in such a way that wherever
possible x == somepattern and typeof(x) <: typeof(somepattern) if and
only if x match { case somepattern => } succeeds. I just don't think
this should be enforced (or required for correctness of pattern
matching), and I don't think that the equality behaviour for the case
where x is not an instance of typeof(somepattern) should be forced by
the desire to use pattern matching.

>> 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.

Absolutely. They're a lovely feature. If only they also worked. :-)

> 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.

I think this is an instance of FP/OO clash. It's also an instance of
the incoherence of the desired behaviour for equality (this is
something inherited from Java) - it's really not clear what equality
should mean, but whatever that is it certainly doesn't seem to be used
in a way that suggests that it's synonymous with "is the same as".

I think something like this may be at the heart of the disagreement:
You (and I'm not intending to attribute this solely to you) want
equality for case classes to mean that. The problem is that I want
case classes to be useable for implementing generic data structures,
which in turn really need to have their own equality methods in order
to be consistent with the desired behaviour for collections overall.

If there is some way to get a low level "is the same as" equality
available in Scala that would be interesting. But I'm not sure I can
see how it would work.

DRMacIver
Joined: 2008-09-02,
User offline. Last seen 42 years 45 weeks ago.
Re: Equality and case objects

Ok. Having sent that email... let's recap, as to be honest I'm no
longer clear on what we're arguing about.

Here are things as I see them:

- I have previously proposed a change to stable identifier matching to
add a type test. This has tentatively been agreed to, pending
investigation.
- It is currently entirely possible to have user defined equality
methods on case classes.
- However there are some gotchas when one defines equality in terms of
pattern matching. Therefore I have proposed additionally adding a
shortcut so that when doing stable identifier matching on an AnyRef it
is allowed to shortcut for reference equal objects without calling
equals.

Lex:

As I understand it, you are not specifically objecting to either of my
proposed modifications, but are instead in favour of deprecating the
ability to have user defined equality for case classes. Is this
correct?

Copyright © 2012 École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Switzerland