Re: Comparing DS_HASH_TABLE objects

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

-- 
Paul Cohen
www.seibostudios.se
mobile: +46 730 787 035
e-mail: paul.cohen-qf2BM/[email protected]


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

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/