String equality brain benders

Hi Jorge, Paul:

These are good observations! Transitivity loss is worrying, but
breaking the equals/hashcode contract is really bad. I think we need
to disentangle RichString from other sequences. That is, Richstring's
are only equal to strings, never to other kinds of sequences. That
requires just some care in Sequence.equals. We might envision a
similar disentanglement for arrays.

Cheers

Sorry to be a bit naive on this, but why should we ever see instances
of RichString? If none of RichString's methods returned RichString,
how would the user come across a RichString?

2009/6/10 martin odersky :
> Hi Jorge, Paul:
>
> These are good observations! Transitivity loss is worrying, but
> breaking the equals/hashcode contract is really bad. I think we need
> to disentangle RichString from other sequences. That is, Richstring's
> are only equal to strings, never to other kinds of sequences. That
> requires just some care in Sequence.equals. We might envision a
> similar disentanglement for arrays.
>
> Cheers
>
>  -- Martin
>
>
>
> On Mon, Jun 8, 2009 at 11:19 PM, Paul Phillips wrote:
>> Let us limit our ambition to this one specific case: RichString.
>>
>> I implemented String/RichString equality in such a way as to cause zero
>> performance degradation and catch all the cases we might want where a
>> String is inadvertantly being compared to a RichString.  Which is kind
>> of cool I suppose, but this process has revealed yet further issues
>> which seem irresolvable.
>>
>> Jorge Ortiz points out that in fixing symmetry, we have broken
>> transitivity, and indeed:
>>
>> // a == b (this is what doesn't return true without my patch)
>> scala> "abc" == stringWrapper("abc")
>> res0: Boolean = true
>>
>> // b == c (this does)
>> scala> stringWrapper("abc") == List('a', 'b', 'c')
>> res1: Boolean = true
>>
>> // a != c (doubtful we would even want this to work!)
>> // also of course c != a
>> scala> "abc" == List('a', 'b', 'c')
>> res2: Boolean = false
>>
>> Short of something ridiculous like having Sequences notice when they're
>> being compared to Strings and trying again with a RichString, I don't
>> see that one getting better.
>>
>> And:
>>
>> A related and most likely unfixable issue is that we are again breaking
>> the equals hashCode contract.
>>
>> scala> val x = stringWrapper("abc")
>> x: scala.runtime.RichString = abc
>>
>> // unavoidably different hashCodes for these next two
>> scala> "abc".toList.hashCode
>> res0: Int = 1840836383
>>
>> scala> "abc".hashCode
>> res1: Int = 96354
>>
>> // ...but RichString thinks it's equal to both of them.
>> scala> x == "abc".toList
>> res2: Boolean = true
>>
>> scala> x == "abc"
>> res3: Boolean = true
>>
>> --
>> Paul Phillips      | Giving every man a vote has no more made men wise
>> In Theory          | and free than Christianity has made them good.
>> Empiricist         |     -- H. L. Mencken
>> i'll ship a pulp   |----------* http://www.improving.org/paulp/ *----------
>>
>>
>

Ah, but RichString's methods do return RichString, and they must because RichString inherits from Sequence (and so RichString's method's must obey Sequence's contract).

Perhaps we should suffer some code duplication and have RichString be Sequence-like but not actually inherit from Sequence?

--j

On Wed, Jun 10, 2009 at 2:53 AM, Ricky Clarkson <ricky.clarkson@gmail.com> wrote:

Sorry to be a bit naive on this, but why should we ever see instances
of RichString?  If none of RichString's methods returned RichString,
how would the user come across a RichString?

2009/6/10 martin odersky <martin.odersky@epfl.ch>:
> Hi Jorge, Paul:
>
> These are good observations! Transitivity loss is worrying, but
> breaking the equals/hashcode contract is really bad. I think we need
> to disentangle RichString from other sequences. That is, Richstring's
> are only equal to strings, never to other kinds of sequences. That
> requires just some care in Sequence.equals. We might envision a
> similar disentanglement for arrays.
>
> Cheers
>
>  -- Martin
>
>
>
> On Mon, Jun 8, 2009 at 11:19 PM, Paul Phillips<paulp@improving.org> wrote:
>> Let us limit our ambition to this one specific case: RichString.
>>
>> I implemented String/RichString equality in such a way as to cause zero
>> performance degradation and catch all the cases we might want where a
>> String is inadvertantly being compared to a RichString.  Which is kind
>> of cool I suppose, but this process has revealed yet further issues
>> which seem irresolvable.
>>
>> Jorge Ortiz points out that in fixing symmetry, we have broken
>> transitivity, and indeed:
>>
>> // a == b (this is what doesn't return true without my patch)
>> scala> "abc" == stringWrapper("abc")
>> res0: Boolean = true
>>
>> // b == c (this does)
>> scala> stringWrapper("abc") == List('a', 'b', 'c')
>> res1: Boolean = true
>>
>> // a != c (doubtful we would even want this to work!)
>> // also of course c != a
>> scala> "abc" == List('a', 'b', 'c')
>> res2: Boolean = false
>>
>> Short of something ridiculous like having Sequences notice when they're
>> being compared to Strings and trying again with a RichString, I don't
>> see that one getting better.
>>
>> And:
>>
>> A related and most likely unfixable issue is that we are again breaking
>> the equals hashCode contract.
>>
>> scala> val x = stringWrapper("abc")
>> x: scala.runtime.RichString = abc
>>
>> // unavoidably different hashCodes for these next two
>> scala> "abc".toList.hashCode
>> res0: Int = 1840836383
>>
>> scala> "abc".hashCode
>> res1: Int = 96354
>>
>> // ...but RichString thinks it's equal to both of them.
>> scala> x == "abc".toList
>> res2: Boolean = true
>>
>> scala> x == "abc"
>> res3: Boolean = true
>>
>> --
>> Paul Phillips      | Giving every man a vote has no more made men wise
>> In Theory          | and free than Christianity has made them good.
>> Empiricist         |     -- H. L. Mencken
>> i'll ship a pulp   |----------* http://www.improving.org/paulp/ *----------
>>
>>
>

To spell things out: then RichString's methods can all return String and (String == RichString) equality is much less problematic.

--j

On Wed, Jun 10, 2009 at 9:07 AM, Jorge Ortiz <jorge.ortiz@gmail.com> wrote:

Ah, but RichString's methods do return RichString, and they must because RichString inherits from Sequence (and so RichString's method's must obey Sequence's contract).

Perhaps we should suffer some code duplication and have RichString be Sequence-like but not actually inherit from Sequence?

--j

On Wed, Jun 10, 2009 at 2:53 AM, Ricky Clarkson <ricky.clarkson@gmail.com> wrote:

Sorry to be a bit naive on this, but why should we ever see instances
of RichString?  If none of RichString's methods returned RichString,
how would the user come across a RichString?

2009/6/10 martin odersky <martin.odersky@epfl.ch>:
> Hi Jorge, Paul:
>
> These are good observations! Transitivity loss is worrying, but
> breaking the equals/hashcode contract is really bad. I think we need
> to disentangle RichString from other sequences. That is, Richstring's
> are only equal to strings, never to other kinds of sequences. That
> requires just some care in Sequence.equals. We might envision a
> similar disentanglement for arrays.
>
> Cheers
>
>  -- Martin
>
>
>
> On Mon, Jun 8, 2009 at 11:19 PM, Paul Phillips<paulp@improving.org> wrote:
>> Let us limit our ambition to this one specific case: RichString.
>>
>> I implemented String/RichString equality in such a way as to cause zero
>> performance degradation and catch all the cases we might want where a
>> String is inadvertantly being compared to a RichString.  Which is kind
>> of cool I suppose, but this process has revealed yet further issues
>> which seem irresolvable.
>>
>> Jorge Ortiz points out that in fixing symmetry, we have broken
>> transitivity, and indeed:
>>
>> // a == b (this is what doesn't return true without my patch)
>> scala> "abc" == stringWrapper("abc")
>> res0: Boolean = true
>>
>> // b == c (this does)
>> scala> stringWrapper("abc") == List('a', 'b', 'c')
>> res1: Boolean = true
>>
>> // a != c (doubtful we would even want this to work!)
>> // also of course c != a
>> scala> "abc" == List('a', 'b', 'c')
>> res2: Boolean = false
>>
>> Short of something ridiculous like having Sequences notice when they're
>> being compared to Strings and trying again with a RichString, I don't
>> see that one getting better.
>>
>> And:
>>
>> A related and most likely unfixable issue is that we are again breaking
>> the equals hashCode contract.
>>
>> scala> val x = stringWrapper("abc")
>> x: scala.runtime.RichString = abc
>>
>> // unavoidably different hashCodes for these next two
>> scala> "abc".toList.hashCode
>> res0: Int = 1840836383
>>
>> scala> "abc".hashCode
>> res1: Int = 96354
>>
>> // ...but RichString thinks it's equal to both of them.
>> scala> x == "abc".toList
>> res2: Boolean = true
>>
>> scala> x == "abc"
>> res3: Boolean = true
>>
>> --
>> Paul Phillips      | Giving every man a vote has no more made men wise
>> In Theory          | and free than Christianity has made them good.
>> Empiricist         |     -- H. L. Mencken
>> i'll ship a pulp   |----------* http://www.improving.org/paulp/ *----------
>>
>>
>

Why does RichString need to inherit from Sequence?

2009/6/10 Jorge Ortiz :
> Ah, but RichString's methods do return RichString, and they must because
> RichString inherits from Sequence (and so RichString's method's must obey
> Sequence's contract).
>
> Perhaps we should suffer some code duplication and have RichString be
> Sequence-like but not actually inherit from Sequence?
>
> --j
>
> On Wed, Jun 10, 2009 at 2:53 AM, Ricky Clarkson
> wrote:
>>
>> Sorry to be a bit naive on this, but why should we ever see instances
>> of RichString?  If none of RichString's methods returned RichString,
>> how would the user come across a RichString?
>>
>> 2009/6/10 martin odersky :
>> > Hi Jorge, Paul:
>> >
>> > These are good observations! Transitivity loss is worrying, but
>> > breaking the equals/hashcode contract is really bad. I think we need
>> > to disentangle RichString from other sequences. That is, Richstring's
>> > are only equal to strings, never to other kinds of sequences. That
>> > requires just some care in Sequence.equals. We might envision a
>> > similar disentanglement for arrays.
>> >
>> > Cheers
>> >
>> >  -- Martin
>> >
>> >
>> >
>> > On Mon, Jun 8, 2009 at 11:19 PM, Paul Phillips
>> > wrote:
>> >> Let us limit our ambition to this one specific case: RichString.
>> >>
>> >> I implemented String/RichString equality in such a way as to cause zero
>> >> performance degradation and catch all the cases we might want where a
>> >> String is inadvertantly being compared to a RichString.  Which is kind
>> >> of cool I suppose, but this process has revealed yet further issues
>> >> which seem irresolvable.
>> >>
>> >> Jorge Ortiz points out that in fixing symmetry, we have broken
>> >> transitivity, and indeed:
>> >>
>> >> // a == b (this is what doesn't return true without my patch)
>> >> scala> "abc" == stringWrapper("abc")
>> >> res0: Boolean = true
>> >>
>> >> // b == c (this does)
>> >> scala> stringWrapper("abc") == List('a', 'b', 'c')
>> >> res1: Boolean = true
>> >>
>> >> // a != c (doubtful we would even want this to work!)
>> >> // also of course c != a
>> >> scala> "abc" == List('a', 'b', 'c')
>> >> res2: Boolean = false
>> >>
>> >> Short of something ridiculous like having Sequences notice when they're
>> >> being compared to Strings and trying again with a RichString, I don't
>> >> see that one getting better.
>> >>
>> >> And:
>> >>
>> >> A related and most likely unfixable issue is that we are again breaking
>> >> the equals hashCode contract.
>> >>
>> >> scala> val x = stringWrapper("abc")
>> >> x: scala.runtime.RichString = abc
>> >>
>> >> // unavoidably different hashCodes for these next two
>> >> scala> "abc".toList.hashCode
>> >> res0: Int = 1840836383
>> >>
>> >> scala> "abc".hashCode
>> >> res1: Int = 96354
>> >>
>> >> // ...but RichString thinks it's equal to both of them.
>> >> scala> x == "abc".toList
>> >> res2: Boolean = true
>> >>
>> >> scala> x == "abc"
>> >> res3: Boolean = true
>> >>
>> >> --
>> >> Paul Phillips      | Giving every man a vote has no more made men wise
>> >> In Theory          | and free than Christianity has made them good.
>> >> Empiricist         |     -- H. L. Mencken
>> >> i'll ship a pulp   |----------* http://www.improving.org/paulp/
>> >> *----------
>> >>
>> >>
>> >
>
>

On Wed, 2009-06-10 at 17:21 +0100, Ricky Clarkson wrote:
> Why does RichString need to inherit from Sequence?

The idea is that a String is a Seq[Char] too, but this causes a lot of
issues given the constraints of the design (i.e. Java's String is a
final class) as has been said elsewhere.

Best,
Ismael

I think "need" is a strong word. Why would it be desirable for RichString to inherit from Sequence? To avoid code duplication and increase abstraction. Also gets us String methods for free whenever a method is added to Sequence.

Given the headaches involved, it might be easier to just do without Sequence.

--j

On Wed, Jun 10, 2009 at 9:21 AM, Ricky Clarkson <ricky.clarkson@gmail.com> wrote:

Why does RichString need to inherit from Sequence?

2009/6/10 Jorge Ortiz <jorge.ortiz@gmail.com>:
> Ah, but RichString's methods do return RichString, and they must because
> RichString inherits from Sequence (and so RichString's method's must obey
> Sequence's contract).
>
> Perhaps we should suffer some code duplication and have RichString be
> Sequence-like but not actually inherit from Sequence?
>
> --j
>
> On Wed, Jun 10, 2009 at 2:53 AM, Ricky Clarkson <ricky.clarkson@gmail.com>
> wrote:
>>
>> Sorry to be a bit naive on this, but why should we ever see instances
>> of RichString?  If none of RichString's methods returned RichString,
>> how would the user come across a RichString?
>>
>> 2009/6/10 martin odersky <martin.odersky@epfl.ch>:
>> > Hi Jorge, Paul:
>> >
>> > These are good observations! Transitivity loss is worrying, but
>> > breaking the equals/hashcode contract is really bad. I think we need
>> > to disentangle RichString from other sequences. That is, Richstring's
>> > are only equal to strings, never to other kinds of sequences. That
>> > requires just some care in Sequence.equals. We might envision a
>> > similar disentanglement for arrays.
>> >
>> > Cheers
>> >
>> >  -- Martin
>> >
>> >
>> >
>> > On Mon, Jun 8, 2009 at 11:19 PM, Paul Phillips<paulp@improving.org>
>> > wrote:
>> >> Let us limit our ambition to this one specific case: RichString.
>> >>
>> >> I implemented String/RichString equality in such a way as to cause zero
>> >> performance degradation and catch all the cases we might want where a
>> >> String is inadvertantly being compared to a RichString.  Which is kind
>> >> of cool I suppose, but this process has revealed yet further issues
>> >> which seem irresolvable.
>> >>
>> >> Jorge Ortiz points out that in fixing symmetry, we have broken
>> >> transitivity, and indeed:
>> >>
>> >> // a == b (this is what doesn't return true without my patch)
>> >> scala> "abc" == stringWrapper("abc")
>> >> res0: Boolean = true
>> >>
>> >> // b == c (this does)
>> >> scala> stringWrapper("abc") == List('a', 'b', 'c')
>> >> res1: Boolean = true
>> >>
>> >> // a != c (doubtful we would even want this to work!)
>> >> // also of course c != a
>> >> scala> "abc" == List('a', 'b', 'c')
>> >> res2: Boolean = false
>> >>
>> >> Short of something ridiculous like having Sequences notice when they're
>> >> being compared to Strings and trying again with a RichString, I don't
>> >> see that one getting better.
>> >>
>> >> And:
>> >>
>> >> A related and most likely unfixable issue is that we are again breaking
>> >> the equals hashCode contract.
>> >>
>> >> scala> val x = stringWrapper("abc")
>> >> x: scala.runtime.RichString = abc
>> >>
>> >> // unavoidably different hashCodes for these next two
>> >> scala> "abc".toList.hashCode
>> >> res0: Int = 1840836383
>> >>
>> >> scala> "abc".hashCode
>> >> res1: Int = 96354
>> >>
>> >> // ...but RichString thinks it's equal to both of them.
>> >> scala> x == "abc".toList
>> >> res2: Boolean = true
>> >>
>> >> scala> x == "abc"
>> >> res3: Boolean = true
>> >>
>> >> --
>> >> Paul Phillips      | Giving every man a vote has no more made men wise
>> >> In Theory          | and free than Christianity has made them good.
>> >> Empiricist         |     -- H. L. Mencken
>> >> i'll ship a pulp   |----------* http://www.improving.org/paulp/
>> >> *----------
>> >>
>> >>
>> >
>
>

On Wed, Jun 10, 2009 at 05:21:08PM +0100, Ricky Clarkson said
> Why does RichString need to inherit from Sequence?

The more I hear about how tricky this has been (is), the more I think
that it's a losing battle to make RichString <: Seq[Char]. I think it'd
work out much better to have RichString with a toSeq method to create a
Seq[Char] view of the string. It should also include the really usefull
stuff that RichString provides now (like reverse, take, drop, etc.) but
returning String instead of RichString. These of course could forward
directly to toSeq. and unwrap/convert back to a regular
String. If we're lucky, escape analysis could do stack allocation or
scalar replacement optimization for those too.

Ismael Juma wrote:
> On Wed, 2009-06-10 at 17:21 +0100, Ricky Clarkson wrote:
>> Why does RichString need to inherit from Sequence?
>
> The idea is that a String is a Seq[Char] too, but this causes a lot of
> issues given the constraints of the design (i.e. Java's String is a
> final class) as has been said elsewhere.

Will any of these issues go away when we get interface injection that John Rose
is working on? So we won't need a RichString class any more?

Blair

On Wed, 2009-06-10 at 12:40 -0700, Blair Zajac wrote:
> Will any of these issues go away when we get interface injection that John Rose
> is working on? So we won't need a RichString class any more?

It would provide a much saner model for this kind of thing, yes.
However, it's unclear when Scala will depend on a JDK7 feature. After
all, it will only move to JDK5 in 2.8.0.

Ismael

On Wed, Jun 10, 2009 at 9:52 PM, Ismael Juma wrote:
> On Wed, 2009-06-10 at 12:40 -0700, Blair Zajac wrote:
>> Will any of these issues go away when we get interface injection that John Rose
>> is working on?  So we won't need a RichString class any more?
>
> It would provide a much saner model for this kind of thing, yes.
> However, it's unclear when Scala will depend on a JDK7 feature. After
> all, it will only move to JDK5 in 2.8.0.
>
And, last I heard, interface injection will not make it into JDK 7 :-(

On Wed, Jun 10, 2009 at 9:28 PM, Geoff Reedy wrote:
> On Wed, Jun 10, 2009 at 05:21:08PM +0100, Ricky Clarkson said
>> Why does RichString need to inherit from Sequence?
>
> The more I hear about how tricky this has been (is), the more I think
> that it's a losing battle to make RichString <: Seq[Char]. I think it'd
> work out much better to have RichString with a toSeq method to create a
> Seq[Char] view of the string. It should also include the really usefull
> stuff that RichString provides now (like reverse, take, drop, etc.) but
> returning String instead of RichString. These of course could forward
> directly to toSeq. and unwrap/convert back to a regular
> String. If we're lucky, escape analysis could do stack allocation or
> scalar replacement optimization for those too.
>
Well, somebody would have to implement the 70+ methods on Sequences
for Richstring.
And keep them current ever after. Also, I believe independently of
merits or not, disabling the RichStrig <: Sequence relationship would
break quite a bit of code. We can make RichString different from other
sequences for the purposes of equals comparison; I do not see a big
complication in that.

Cheers

On Wed, 2009-06-10 at 21:55 +0200, martin odersky wrote:
> And, last I heard, interface injection will not make it into JDK 7 :-(

That's a real shame.

Ismael

On Wed, Jun 10, 2009 at 09:58:58PM +0200, martin odersky wrote:
> And keep them current ever after. Also, I believe independently of
> merits or not, disabling the RichStrig <: Sequence relationship would
> break quite a bit of code. We can make RichString different from other
> sequences for the purposes of equals comparison; I do not see a big
> complication in that.

Hmmm, that would certainly be a lot more doable. So:

Strings are only equal to Strings and (throuh hackery) RichStrings

RichStrings are only equal to RichStrings and Strings

Sequences are equal to Sequences, so... before anything else, they
look for the marker interface FauxSequence and return false if seen?

Incidentally, more equal objects with unequal hashCodes. This could
sort of be fixed by having range use the hashCode of itself.toList, and
maybe use a lazy val so as not to get too punished. Still, it takes
(0 until Math.MAX_INT).hashCode from a cheap operation to a killer.

scala> (0 until 10) == List.range(0, 10)
res0: Boolean = true

scala> (0 until 10).hashCode
res1: Int = 11625210

scala> List.range(0, 10).hashCode
res2: Int = 426645534

2009/6/10 Paul Phillips :
> On Wed, Jun 10, 2009 at 09:58:58PM +0200, martin odersky wrote:
>> And keep them current ever after. Also, I believe independently of
>> merits or not, disabling the RichStrig <: Sequence relationship would
>> break quite a bit of code. We can make RichString different from other
>> sequences for the purposes of equals comparison; I do not see a big
>> complication in that.
>
> Hmmm, that would certainly be a lot more doable. So:
>
>  Strings are only equal to Strings and (throuh hackery) RichStrings
>
>  RichStrings are only equal to RichStrings and Strings
>
>  Sequences are equal to Sequences, so... before anything else, they
>  look for the marker interface FauxSequence and return false if seen?

This seems an appropriate use for the canEquals method as described in
http://www.artima.com/lejava/articles/equality.html or PiS.

> Incidentally, more equal objects with unequal hashCodes.  This could
> sort of be fixed by having range use the hashCode of itself.toList, and
> maybe use a lazy val so as not to get too punished.  Still, it takes
> (0 until Math.MAX_INT).hashCode from a cheap operation to a killer.

Hm. So it might be hard to get this to work well with the generic
implementation, but hotspot actually does a rather good job of
optimising the integer ops here. e.g.

scala> def hashTo(max : Int) = { var h = 0; var i = 0; while (i < max)
{ h *= 31; h += i; i += 1; }; h }
hashTo: (Int)Int

scala> h(10)
:5: error: not found: value h
h(10)
^

scala> hashTo(Int.MaxValue)
res3: Int = -34636833

completed in not that long (a couple of seconds).It's not great, but
it's a lot better than you'll manage with most collections that size.

On Wed, Jun 10, 2009 at 11:11 PM, David MacIver wrote:
> 2009/6/10 Paul Phillips :
>> On Wed, Jun 10, 2009 at 09:58:58PM +0200, martin odersky wrote:
>>> And keep them current ever after. Also, I believe independently of
>>> merits or not, disabling the RichStrig <: Sequence relationship would
>>> break quite a bit of code. We can make RichString different from other
>>> sequences for the purposes of equals comparison; I do not see a big
>>> complication in that.
>>
>> Hmmm, that would certainly be a lot more doable. So:
>>
>>  Strings are only equal to Strings and (throuh hackery) RichStrings
>>
>>  RichStrings are only equal to RichStrings and Strings
>>
>>  Sequences are equal to Sequences, so... before anything else, they
>>  look for the marker interface FauxSequence and return false if seen?
>
> This seems an appropriate use for the canEquals method as described in
> http://www.artima.com/lejava/articles/equality.html or PiS.
>
Or in chapter 28 of Programming in Scala. I agree.

Cheers