From: knight@mrco.carleton.ca (Alan Knight)
Subject: Re: Equality
Reply-To: knight@mrco.carleton.ca (Alan Knight)
Organization: Carleton University
Date: Thu, 24 Dec 1992 21:20:43 GMT

In <1992Dec21.184405.2215@midway.uchicago.edu> dave@alex.uchicago.edu (Dave Griffith) writes:

>So just what exactly do you all mean when you say "equality".  If it's just 
>another binary predicate, why bother to call it equality?  If not, what 
>semantic properties should it have?  The recent object/value discussion brought
>up some examples which cause me to question my preconceived notions.  I will
>below attempt to list those notions, in hope the group will provide useful 
>comments.   Throughout the following, "object" is used as in current OO 
>languages, to represent both "objects" and "values".  

>1) Equality should be reflexive.  
>	I thought this was obvious, but IEEE754 may provide a counterexample.

>2) Equality should be symettric.
>3) Equality should be transitive.

I already mentioned interval arithmetic, for which this does not hold.
You said that there didn't appear to be a good equality operation for
interval arithmetic, which is quite possibly true, but doesn't mean
that I don't want to use it. If so, your system would need to allow
things for which there is no equality operation.

>4) Substitution of equals for equals should give equals.
>5) If two objects are equal at one point in program execution, they should be
>     equal at all points. 

If you have this condition, then you have to use identity or else have
immutable values. I don't see why it should have to hold. 

>6) Assignment should respect equality.   (Assuming no side-effects, after 
>   executing x:=a; it should be true that x=a.

This also fails for IEEE floating point arithmetic. 

>7) If your parameter passing model is based on assignment, 6) should hold 
>   mutatis mutandi.
This too. 

>8) If two objects are equal, they should be behaviourally indistinguishable. 
>   The converse need not hold, but often will.

For graphs, one might wish to consider isomorphic graphs equal.

>9) Two sets A,B are equal iff  for_all(x:A)there_exists(y:B) such y=x, and
>   vice versa.

Apparently sets are not objects, since one has an equality operation
for them which is not the same as that for other objects (identity).
If I make my own implementation of sets, or some other type of
collection, which equality do I use.

>Given mutable objects, identity was the only practical definition I found
>which would  support all of the above.  However, identity is not a practical 
>equality definition for all objects we wish to program with (vis, integers). 
>In these cases, if immutability holds, users may be able to define equality
>in ways which satisfy the above, and there are good reasons to let them try. 

Removing condition 5 would make it rather easier.  

One might also have functions as objects, which might satisfy all of
those conditions but not be identical.

>This is comp.object, so presumably when people talk equality here, they don't 
>mean bitwise or address equality, although these may be used as implementation 
>techniques.   The following questions also arise do to object orientation: 
>May two objects of different classes be equal?  May two objects be equal even 
>if they don't respond to the same protocol?  If they respond to the same 
>protocol but have no common superclass which defines that protocol 
>(i.e. protocol similarity is incidental)?  

How about 1.0 = 1
          1/1 = 1
          1+0i = 1

These are certainly of different classes, and they might have a
different protocol (depending if operations like mantissa or imaginary
part are implemented for integers).

>If programmers view equality as just another binary predicate, perhaps I 
>should come up with a different name for the operation I need.  Any 
>suggestions?

How about identity? 

I think that you are trying to take a very strong definition of
equality that can work for some mathematical abstractions and apply it
to everything.  I don't think this definition of equality is universal
in mathematics either. One often refers to two sides of a triangle
being equal, meaning that their lengths are equal. I, and others, have
already mentioned graphs.

-- 
 Alan Knight  knight@mrco.carleton.ca  +1 613 788 2600x1027 
 Dept. of Mechanical and Aerospace Engineering              
 Carleton University, Ottawa, Ontario, Canada, K1S 5B6      

Newsgroups: comp.object