Re: Comparing DS_HASH_TABLE objects

Hello Paul,

I think the basic question is "What does equality mean?".

Considering expanded type objects like INTEGERs or REALs, everything is
clear. a = b means "Does a and b represent the same number?".

When coming to STRINGs the first strangeness occurs.

  check
     "Hello" /= "Hello"
  end

The 2 string "Hello" and "Hello" are not considered equal because they
are not the same object. In ECMA Eiffel the equality operator "~" has
been introduced to test for object and not reference equality. So using
that we get

  check
    "Hello" ~ "Hello"
  end

But the you can push it one level further and use containers and you get

  check
    <<"a","b">  /= <<"a","b">>
    <<"a","b">  /~ <<"a","b">>
  end

You can remedy the situation, if you set `object_comparison' in ARRAYs.

In my opinion the notion of equality in Eiffel is not very consistent.
Eiffel has expanded type objects and reference type objects. For feature
calls there is not difference. You write

  exp.some_feature
  ref.some_feature

So regardless whether an entity is reference or expanded, feature calls
are done in the same manner. If it comes to equality testing, we have to
use different operators to test for equality (surely you can write 200 ~
200 instead of 200 = 200, but it reads ugly).

The we have the difference between deep equality and normal equality. In
generic classes like hash tables or even simple arrays it is difficult
to take all the differences into account.

So for me, the problem is not in Eric's implementation of the hash
tables, the problem is in the concept of equality in Eiffel.

Regards
Helmut



Paul Cohen wrote:
> On Mon, Jun 1, 2009 at 9:42 AM, Eric Bezault <ericb-D6Qt/9opevxWk0Htik3J/[email protected]> wrote:
>> Paul Cohen wrote:
>>> The 'key_equality_tester' and 'equality_tester' are properties of the
>>> hash table, not of the keys or the items in the hash_table.
>> I don't agree with that. Objects can be compared in many different
>> ways, regardless whether they are used in hash tables or not.
>> `is_equal' is just one way to compare them, but that does not
>> mean that the other ways to compare them are not properties of
>> these objects.
> 
> Ok. I agree with what you're saying. However, I still maintain that
> `key_equality_tester' and `equality_tester' are properties of
> DS_HASH_TABLE. There are no contracts in ANY or HASHABLE that refer to
> `key_equality_tester' and `equality_tester' in DS_HASH_TABLE simply
> because they are not properties of ANY.
> 
> On a more important and fundamental level you are absolutely right. I
> think the problem is that we (as Eiffel-programmers) are trying to
> model mathematical *relations* as operations that are features of the
> types instead of defining the relations outside the types. Your
> `equality_tester' approach/solution adresses exactly that problem. In
> your approach the equivalence relation is moved and defined outside of
> the class/type the relation works on.
> 
> Maybe an `equality_tester' mechanism should be introduced in ANY, or
> maybe some new general Eiffel mechanism for defining relations between
> types outside of the types themselves (yet still let us use the
> current operator style syntax). I wonder how many catcall problems
> could be removed by that. ADT:s and mathematical relations on
> (mathemathical) objects simply don't work together very well.
> 
>> In Gobo, by design, I try to avoid using `is_equal' as much as
>> possible. First, it is cat-call error-prone. Second, as already said
>> above, there are many ways to compare objects, and `is_equal'
>> is not necessarily the best one. That's why I introduced the
>> notion of equality tester in Gobo.
> 
> Ok. I'm with you on that.
> 
>>> The current solution would mean that two hash tables, that have the
>>> same `key_equality_tester' and `equality_tester', the same keys but
>>> where the items do not reference the same objects yet the items are
>>> equal in an 'is_equal' sense, are not equal!? That feels strange to
>>> me.
>> It does not feel strange for someone who wants to know whether
>> the hash table contains the same item objects and not duplicates.
>> By default, when not redefined, objects are considered `is_equal'
>> if their attributes (i.e. their content) are the same objects.
>> That's what is done here for hash tables: do they have the same
>> content (i.e. the same item objects)? So it does not feel stranger
>> than this:
>>
>> c1, c2: CELL [STRING]
>> value: STRING
>> b: BOOLEAN
>> ...
>> create c1
>> value := "Eiffel"
>> c1.put (value)
>> create c2
>> value := "Eiffel"
>> c2.put (value)
>> b := c1.is_equal (c2) -- b is False
> 
> Well, we have:
> 
>     c1, c2: CELL [INTEGER]
>     value: INTEGER
>     b: BOOLEAN
>         ...
>     value := 42
>     c1.put (value)
>     create c2
>     value := 42
>     c2.put (value)
>     b := c1.is_equal (c2) -- b is True
> 
> Yes, I know why this works. It's just that to my mind CELL.is_equal
> should return "whether two cells are considered equal", which they in
> my opinion are if the contents of the two cells `is_equal'.
> 
> Currently, "=" means existential (identity/reference) equivalence or
> "same object" and `is_equal' usually means "value" equivalence. I am
> aware that CELL.is_equal means that the two cells contain objects that
> are existential (identity) equivalence or "same object", but I'm
> interested in a feature for finding out if two CELL:s contain objects
> that are "value equivalent". For expanded classes like INTEGERs, "="
> existential (identity) equivalence and value equivalence are the same.
> 
> So I end up with  your conclusion; dont use/rely on is_equal (or
> interpret it always as meaning have "same"/"identical" contents). I
> should simply define my own equivalence relation just like an
> `equality_tester'.
> 
>>>> It uses '=' to compare items because `is_equal' is used
>>>> in the postcondition of `copy/twin', and their implementation
>>>> in hash table does not clone the items.
>>> I don't understand the problem. Using `is_equal' to compare items
>>> would not break the postcondition in `copy'
>> It would not break the postcondition, but it would not be
>> as precise as it could. We can say more than just that the
>> items are equal. They are the same.
> 
> Ok.
> 
>>> So, to summarize:
>>>
>>> 1. I don't understand conceptually why t1.is_equal (t2) = False in
>>> the example given above. And I see that HASH_TABLE works the same.
>> Let's consider strings. We can consider that two strings are equal
>> if they are case-sensitive equal (this is typically what `is_equal'
>> implements) or if they are case-insensitive equal. When writing
>> an Eiffel compiler, the strings representing Eiffel identifiers
>> should be considered equal if they are case-insensitive equal.
>> So, "foo" and "Foo" will be considered equal using this criterion
>> even though `is_equal' will return false.
> 
> Ok. Then for a challenge, what about if we had:
> 
>     s1, s2: STRING
>     b: BOOLEAN
>         ...
>     s1 := "Eiffel"
>     s2 := "Eiffel"
>     b := s1.is_equal (s2) -- b is False
> 
> since s1 and s2 don't contain the same character objects? Yes I know b is True!
> 
> I know strings are tricky since they exist in a hazy limbo between
> value and reference objects! We still end up with the problem of
> defining the equivalence relation. And that will always be context
> dependent.
> 
>>> 2. I'd like an `is_equivalent' or `has_the_same_keys_and_items'
>>> feature in DS_HASH_TABLE that ignores `key_equality_tester' and
>>> `equality_tester'!
>> The fact that the classes in Gobo try to avoid using `is_equal'
>> is a design decision. I stopped using `is_equal' to compare objects.
>> In my opinion this is a caveat of Eiffel to do so.
> 
> I agree. As I've said, I think you are spot on in saying "there are
> many ways to compare objects, and `is_equal' is not necessarily the
> best one. That's why I introduced the notion of equality tester in
> Gobo."
> 
> I understand your rationale now for how DS_HASH_TABLE.is_equal works,
> even though I still don't think the current implementation agrees with
> my notion of what equal hash tables are - so be it. I will of course
> implement my feature for comparing hash tables outside of
> DS_HASH_TABLE.
> 
> So I'm satisfied with your answer. Yet unsatisfied with the problem of
> defining equivalence relations in Eiffel! Thanks, Eric, for taking
> time and for an enlightening discussion.
> 
> /Paul
> 


------------------------------------

To Post a message, send it to:   [email protected]
To Unsubscribe, send a blank message to: [email protected]! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/gobo-eiffel/

<*> Your email settings:
    Individual Email | Traditional

<*> To change settings online go to:
    http://groups.yahoo.com/group/gobo-eiffel/join
    (Yahoo! ID required)

<*> To change settings via email:
    mailto:[email protected] 
    mailto:[email protected]

<*> To unsubscribe from this group, send an email to:
    [email protected]

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/