Making == symmetric?

Discussion in 'Ruby' started by Nathan Weston, Oct 1, 2003.

  1. It has always bothered me that == is not symmetric in ruby:
    a == b is shorthand for a.==(b), while b == a is shorthand for
    b.==(a), and a and b might not agree on whether they are equal.

    I have an idea as to how to fix this, and was thinking of posting an
    RCR on rubygarden, but I thought I'd post here first and see if I've
    missed any major problems.

    First of all: yes, this issue does come up in real code.
    Here's a quick example I ran into today:

    require "delegate"

    class Foo
    end

    class D < SimpleDelegator
    def initialize(obj)
    super(obj)
    end
    end

    f = Foo.new
    d = D.new(f)

    d == f #evaluates to true
    f == d #evaluates to false


    I ran into a similar problem trying to implement perl6-style
    junctions: you end up with any(1,2,3) == 1 being true, but 1 ==
    any(1,2,3) being false.

    My proposed solution is this:
    Instead of a == b being shorthand for a.==(b), it should be shorthand
    for Kernel::compare(a, b).

    def compare(a,b)
    if a.can_compare_to?(b)
    return a.compare_to(b)
    elsif b.can_compare_to?(a)
    return b.compare_to(a)
    else
    return false
    end
    end

    This way, a class is only responsible for comparing itself to other
    classes it knows about. This allows a lot more flexibility, because
    you can define new classes that introduce their own semantics for
    equality w.r.t existing classes (i.e., you can make a new class that
    is equal to some strings, without having to change String to know
    about the new class).

    Compare this to the current situation, where an object is responsible
    for comparing itself to any kind of object. In this situation, the
    only sensible response for a class that you know nothing about is
    "false", which limits flexibility, and can lead to == being
    asymmetric.

    Of course, this solution isn't perfect -- if a and b both know about
    each other, but have diffening ideas of equality, then a == b and b ==
    a will still return different results. But that's a lot easier to
    avoid than the problems which arise under the current handling of ==.

    This solution might be extended to other operators that should be
    symmetric, as well (such as +), but == is the most widely used and I
    think the most important to fix.
     
    Nathan Weston, Oct 1, 2003
    #1
    1. Advertising

  2. Nathan Weston

    Ben Giddings Guest

    Nathan Weston wrote:
    > def compare(a,b)
    > if a.can_compare_to?(b)
    > return a.compare_to(b)
    > elsif b.can_compare_to?(a)
    > return b.compare_to(a)
    > else
    > return false
    > end
    > end


    How about

    def compare(a, b)
    retval = false
    if a.can_compare_to(b)
    retval = a.compare_to(b)
    end
    if retval and b.can_compare_to(a)
    retval = b.compare_to(a)
    end

    return retval
    end

    This way if both of them know how to compare themselves to the other one,
    the comparison returns true only if both agree they're equal.

    Aside from the code though, I'm not sure if I like the idea. While in
    principle I agree that equality tests should be symmetrical, I also think
    that it is more natural to have an equality operator which you can
    overload. I think you'd still need "can_compare_to?" to know if 'a' knows
    how to compare itself to an instance of 'b'...

    Maybe instead:

    def compare(a, b)
    retval = false
    if a.can_compare_to?(b)
    retval = a.==(b)
    end
    if retval and b.can_compare_to?(a)
    retval = b.==(a)
    end

    return retval
    end

    Interesting food for thought though.

    Ben
     
    Ben Giddings, Oct 1, 2003
    #2
    1. Advertising

  3. "Ben Giddings" <> schrieb im Newsbeitrag
    news:...
    > Nathan Weston wrote:
    > > def compare(a,b)
    > > if a.can_compare_to?(b)
    > > return a.compare_to(b)
    > > elsif b.can_compare_to?(a)
    > > return b.compare_to(a)
    > > else
    > > return false
    > > end
    > > end

    >
    > How about
    >
    > def compare(a, b)
    > retval = false
    > if a.can_compare_to(b)
    > retval = a.compare_to(b)
    > end
    > if retval and b.can_compare_to(a)
    > retval = b.compare_to(a)
    > end
    >
    > return retval
    > end
    >
    > This way if both of them know how to compare themselves to the other

    one,
    > the comparison returns true only if both agree they're equal.


    But that's inefficient to a degree that can cause problems for
    applications. You end up always doing two comparisons. Even making the
    compare() method more complex (i.e do only one comparison if the
    instances' classes match) doesn't really solve this issue since for the
    standard case you still get the overhead.

    > Aside from the code though, I'm not sure if I like the idea. While in
    > principle I agree that equality tests should be symmetrical, I also

    think
    > that it is more natural to have an equality operator which you can
    > overload. I think you'd still need "can_compare_to?" to know if 'a'

    knows
    > how to compare itself to an instance of 'b'...
    >
    > Maybe instead:
    >
    > def compare(a, b)
    > retval = false
    > if a.can_compare_to?(b)
    > retval = a.==(b)
    > end
    > if retval and b.can_compare_to?(a)
    > retval = b.==(a)
    > end
    >
    > return retval
    > end


    Doesn't solve the overhead problem.

    What one would really need is multiple dispatch:

    module Kernel
    def self.register_compare(classA, classB, &comp)
    ( @comparisons ||= {})[ [classA, classB] ] = comp
    @comparisons[ [classB, classA] ] = proc { |b,a| comp.call(a, b) }
    end

    def self.compare(a, b)
    c = @comparisons[ [a.class, b.class] ]
    c.nil? ? a == b : c.call( a, b )
    end
    end


    class Foo
    Kernel.register_compare( self, self ) do |a,b|
    puts "Foo == Foo"
    false
    end

    def ==(b)
    Kernel.compare( self, b )
    end
    end


    class Bar < Foo
    Kernel.register_compare( self, self ) do |a,b|
    puts "Bar == Bar"
    false
    end

    Kernel.register_compare( self, Foo ) do |a,b|
    puts "Bar == Foo"
    false
    end
    end

    f1 = Foo.new
    f2 = Foo.new

    f1 == f2

    b1 = Bar.new
    b2 = Bar.new

    b1 == b2

    b1 == f1
    f1 == b1


    But this has several disadvantages, too: You keep creating all those
    temporary arrays and you have the need for O(n**2) comparison operators.

    Regards

    robert
     
    Robert Klemme, Oct 1, 2003
    #3
  4. "Robert Klemme" <> wrote in message news:<ble00n$b7qp2$-berlin.de>...
    > "Ben Giddings" <> schrieb im Newsbeitrag
    > news:...
    > > Nathan Weston wrote:


    [snip]

    > >
    > > Maybe instead:
    > >
    > > def compare(a, b)
    > > retval = false
    > > if a.can_compare_to?(b)
    > > retval = a.==(b)
    > > end
    > > if retval and b.can_compare_to?(a)
    > > retval = b.==(a)
    > > end
    > >
    > > return retval
    > > end

    >
    > Doesn't solve the overhead problem.
    >
    > What one would really need is multiple dispatch:
    >
    > module Kernel
    > def self.register_compare(classA, classB, &comp)
    > ( @comparisons ||= {})[ [classA, classB] ] = comp
    > @comparisons[ [classB, classA] ] = proc { |b,a| comp.call(a, b) }
    > end
    >
    > def self.compare(a, b)
    > c = @comparisons[ [a.class, b.class] ]
    > c.nil? ? a == b : c.call( a, b )
    > end
    > end
    >
    >
    > class Foo
    > Kernel.register_compare( self, self ) do |a,b|
    > puts "Foo == Foo"
    > false
    > end
    >
    > def ==(b)
    > Kernel.compare( self, b )
    > end
    > end
    >
    >
    > class Bar < Foo
    > Kernel.register_compare( self, self ) do |a,b|
    > puts "Bar == Bar"
    > false
    > end
    >
    > Kernel.register_compare( self, Foo ) do |a,b|
    > puts "Bar == Foo"
    > false
    > end
    > end
    >
    > f1 = Foo.new
    > f2 = Foo.new
    >
    > f1 == f2
    >
    > b1 = Bar.new
    > b2 = Bar.new
    >
    > b1 == b2
    >
    > b1 == f1
    > f1 == b1
    >
    >
    > But this has several disadvantages, too: You keep creating all those
    > temporary arrays and you have the need for O(n**2) comparison operators.
    >
    > Regards
    >
    > robert


    That seems a bit too messy to me. Just overriding == is cleaner and
    more intuitive.
    How about:

    def compare(a, b)
    if a.can_compare_to?(b)
    return a.==(b)
    elsif b.can_compare_to?(a)
    return b.==(a)
    end
    return false
    end

    I think the problem Ben's proposal is trying to avoid is something
    like this:

    class Foo
    def can_compare_to?(obj)
    if obj.is_a?(Bar)
    return true
    else
    ...
    end

    #Foo thinks that it is not equal to any Bar object
    def ==(obj)
    if obj.is_a?(Bar)
    return false
    else
    ...
    end
    end

    class Bar
    def can_compare_to?(obj)
    if obj.is_a?(Foo)
    return true
    else
    ...
    end

    #Bar thinks that it is equal to any Foo object
    def ==(obj)
    if obj.is_a?(Foo)
    return true
    else
    ...
    end
    end


    Under Ben's solution:
    Foo.new == Bar.new #false
    Bar.new == Foo.new #false

    So, the writer of Foo is happy, because he always gets the answer he
    wanted. But the writer of Bar is unhappy, because he wanted true in
    both cases.

    Under my proposal
    Foo.new == Bar.new #false
    Bar.new == Foo.new #true

    The writers of Foo and Bar are both unhappy, because they get the
    wrong result in one case.

    However, I would argue that, under both Ben's proposal and my
    proposal, you get broken behavior -- it's just broken in different
    ways. Either way, to get non-broken behavior, you need the writers of
    Foo and Bar to come to some agreement about how their classes are
    compared (which I don't think is unreasonable). And my way only does
    one comparison, instead of 2.

    Also, I suggest this default implentation of can_compare_to?

    class Object
    def can_compare_to?(obj)
    return obj.kind_of?(self.class)
    end
    end

    This way, in the common case where objects of class A are only equal
    to other objects of class A, there is no need to override
    can_compare_to?

    The main problem I still see is the need to override can_compare_to?
    at all. If this change is implemented, I expect many people will
    override #== and be confused when this has no effect.

    Maybe there is a way for #== to return an "I don't know" result, which
    could remove the need for can_compare_to? at all. Newbies could still
    break things by writing == methods that return false as a default
    (instead of "I don't know"), but this would really only be a problem
    if they were writing class libraries for someone else's consumption
    (which hopefully they wouldn't be doing).

    Nathan
     
    Nathan Weston, Oct 1, 2003
    #4
  5. Ben Giddings <> wrote in message news:<>...
    >
    > Maybe instead:
    >
    > def compare(a, b)
    > retval = false
    > if a.can_compare_to?(b)
    > retval = a.==(b)
    > end
    > if retval and b.can_compare_to?(a)
    > retval = b.==(a)
    > end
    >
    > return retval
    > end
    >


    I agree that the use of == instead of compare_to is more intuitive if
    people want to override equality. In general, I'm not attached to the
    specific names I've thrown out in this example -- Kernel#compare could
    just as easily be Kernel#==, if that makes more sense.

    Nathan
     
    Nathan Weston, Oct 1, 2003
    #5
  6. Nathan Weston

    Sean O'Dell Guest

    Nathan Weston wrote:
    > It has always bothered me that == is not symmetric in ruby:
    > a == b is shorthand for a.==(b), while b == a is shorthand for
    > b.==(a), and a and b might not agree on whether they are equal.


    My own opinion on this is: == is like asking one object if it's equal to
    another. I know that particular operator is supposed to provide a
    balanced equality test, but I only thought of == that way early in my
    programming career; that notion has long since been replaced with the
    notion that one side is asking if the other side is equal, and switching
    things around will yield different results. Because of this, the way
    Ruby handles == always made perfect sense to me.

    But it would be nice to have a way to perform a perfectly symmetrical
    balanced test.

    Perhaps a solution would be to create a module that overrides == and
    adds ==? to some or all classes. The ==? operator can return true,
    false or nil. Nil would mean the method isn't really an authority. The
    overridden == method can try the ==? method for both objects. If one or
    both ==? methods return true or false, that's the answer. If both
    return different, non-nil answers, an exception can be thrown. If both
    return nil, then the super == method can be called to alert you that
    both objects consider themselves an authority, but they are not
    returning the same result.

    Example:

    class Object

    def ==?(comparator)
    return nil
    end

    def ==(comparate)
    left = ==?(comparate)
    right = comparate.==?(self)
    if (left == nil and right == nil) then
    return super
    elsif (left == right)
    return left and right ? true : false
    elseif (left == nil)
    return right
    elseif (right == nil)
    return left
    else
    raise "both comparates return unbalanced equality tests"
    end

    end

    class String

    def ==?(comparate)
    return self.to_s == comparate.to_s if (comparate.class == Number)
    return super
    end

    end

    class Number

    def ==?(comparate)
    return self.to_s == comparate if (comparate.class == String)
    return super
    end

    end


    Clearly this is something that ought to be written in C, not Ruby, for
    speed purposes, but the idea seems right to me. Everything can even be
    kept in one module, expressly for the purpose of include'ing when
    needed, so this sort of implementation wouldn't break existing code.

    Sean O'Dell
     
    Sean O'Dell, Oct 1, 2003
    #6
  7. W li¶cie z ¶ro, 01-10-2003, godz. 19:31, Sean O'Dell pisze:

    > My own opinion on this is: == is like asking one object if it's equal to
    > another. I know that particular operator is supposed to provide a
    > balanced equality test, but I only thought of == that way early in my
    > programming career; that notion has long since been replaced with the
    > notion that one side is asking if the other side is equal, and switching
    > things around will yield different results. Because of this, the way
    > Ruby handles == always made perfect sense to me.


    This is like saying "my programming model is unable to describe the
    reality accurately, so let's change the reality to make it fit the
    model".

    For me this is simply a shortcoming in the traditional single-dispatched
    OO way of thinking, that it can't make the meaning of == depend on the
    types of both arguments.

    I don't say that the language should enforce == to be symmetric. I say
    that the language should allow to define a symmetric == with the desired
    meaning.

    So I'm a fan of generic functions. Unfortunately they don't quite fit
    Ruby (or Ruby doesn't quite fit my programming model) - I don't know if
    emulating them in Ruby is worth the effort.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Oct 1, 2003
    #7
  8. Nathan Weston

    Sean O'Dell Guest

    Marcin 'Qrczak' Kowalczyk wrote:
    > W li¶cie z ¶ro, 01-10-2003, godz. 19:31, Sean O'Dell pisze:
    >
    >
    >>My own opinion on this is: == is like asking one object if it's equal to
    >>another. I know that particular operator is supposed to provide a
    >>balanced equality test, but I only thought of == that way early in my
    >>programming career; that notion has long since been replaced with the
    >>notion that one side is asking if the other side is equal, and switching
    >>things around will yield different results. Because of this, the way
    >>Ruby handles == always made perfect sense to me.

    >
    >
    > This is like saying "my programming model is unable to describe the
    > reality accurately, so let's change the reality to make it fit the
    > model".


    The notion of a symmetrical equality test is an abstract concept. In
    reality, whether it's Ruby or anything else, testing is NOT symmetrical.

    If you compare two objects in real life, you have to compare one to the
    other by first observing one, then the second object. You can decide to
    either observe in one pass (object A first, then object B) or can
    observe a second time (object B first, then object A) and decide if they
    are equal.

    You can make as many passes as you want, or you can just make one pass.

    If you say:

    if (a == b) then

    ... then you are accepting one pass. If you say:

    if (a == b and b == a) then

    ... then you are demanding a second pass and trying to get a better idea
    if they are equal or not.

    Although I want to know if A and B are equal, I accept that the equality
    test is one object comparing itself to another. This is acceptable to
    me, and if I want more, I can override the == method or perform more
    tests to get the result I want.

    > For me this is simply a shortcoming in the traditional single-dispatched
    > OO way of thinking, that it can't make the meaning of == depend on the
    > types of both arguments.
    >
    > I don't say that the language should enforce == to be symmetric. I say
    > that the language should allow to define a symmetric == with the desired
    > meaning.


    But it does. You can very easily override == just as I described in my
    example code. You can make == anything you want it to be, for any
    class, existing or not.

    > So I'm a fan of generic functions. Unfortunately they don't quite fit
    > Ruby (or Ruby doesn't quite fit my programming model) - I don't know if
    > emulating them in Ruby is worth the effort.


    I'm just glad Ruby *lets* us override and emulate ... to our heart's
    content, it lets us. =)

    Sean O'Dell
     
    Sean O'Dell, Oct 1, 2003
    #8
  9. W li¶cie z ¶ro, 01-10-2003, godz. 21:42, Sean O'Dell pisze:

    > The notion of a symmetrical equality test is an abstract concept. In
    > reality, whether it's Ruby or anything else, testing is NOT symmetrical.


    The method used to determine the outcome is not symmetrical internally,
    but the outcome is (or rather: should be).

    > If you say:
    >
    > if (a == b) then
    >
    > ... then you are accepting one pass. If you say:
    >
    > if (a == b and b == a) then
    >
    > ... then you are demanding a second pass and trying to get a better idea
    > if they are equal or not.


    My concept of == requires that they give the same result, i.e. if they
    differ then some definition of == must be insane (probably a programmer-
    -supplied interpretation of == for a particular type).

    I mean that if an algorithm relies on == being symmetrical but doesn't
    explicitly check both directions and fails because of this, then the
    fault is at the definition of ==, not in the algorithm which uses ==.

    It wouldn't know what to do with conflicting answers anyway, except to
    signal error. Why do you use "and" and not "or" for example?

    Well, another, equally valid requirement is x==x, which is usually not
    satisied by NaN. I say: it is indeed against the rules; sometimes it's
    useful to make an exception. You shouldn't rely much on equality of
    floats anyway.

    > > I don't say that the language should enforce == to be symmetric. I say
    > > that the language should allow to define a symmetric == with the desired
    > > meaning.

    >
    > But it does. You can very easily override == just as I described in my
    > example code. You can make == anything you want it to be, for any
    > class, existing or not.


    How to make a new numeric type (say, long integer objects from another
    language or library wrapped as Ruby objects) and make == between this
    type and other numeric types compute the equality of numbers being
    represented? You don't know all other numeric types.

    --
    __("< Marcin Kowalczyk
    \__/
    ^^ http://qrnik.knm.org.pl/~qrczak/
     
    Marcin 'Qrczak' Kowalczyk, Oct 1, 2003
    #9
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Gazelle
    Replies:
    0
    Views:
    2,880
    Gazelle
    Nov 12, 2003
  2. lookaround
    Replies:
    1
    Views:
    381
    Alexey Smirnov
    Mar 15, 2007
  3. Adam Olsen

    cmp and sorting non-symmetric types

    Adam Olsen, Nov 13, 2007, in forum: Python
    Replies:
    5
    Views:
    291
    Raymond Hettinger
    Nov 14, 2007
  4. Gustavo Rondina

    Storage of symmetric boolean matrix

    Gustavo Rondina, Jun 27, 2009, in forum: C Programming
    Replies:
    9
    Views:
    499
    Flash Gordon
    Jun 29, 2009
  5. Paddy
    Replies:
    9
    Views:
    306
    Paddy
    Aug 17, 2010
Loading...

Share This Page