From: santas@inf.ethz.ch (Philip)
Subject: Re: Equality
Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
Date: Tue, 22 Dec 1992 23:41:47 GMT

In article <1992Dec22.183803.16421@midway.uchicago.edu> dave@alex.uchicago.edu (Dave Griffith) writes:
> grogono@cs.concordia.ca (Peter Grogono) writes:
>>dave@alex.uchicago.edu (Dave Griffith) writes:
>>> .......
>>>8) If two objects are equal, they should be behaviourally indistinguishable.
>>>   The converse need not hold, but often will.
>>>9) Two sets A,B are equal iff  for_all(x:A)there_exists(y:B) such y=x, and
>>>   vice versa.
>>>
>>>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).
>>
>>I do not see how "identity" supports #9. In principle, A=B, where A and
>>B are sets, should mean that A and B have the same members, even if the
>>representations of A and B are distinct in memory and may be different
>>data structures. I do not see how an equality test of this kind can be
>>built-in to a language, and this was my reason for saying that equality
>>must be user-defined in general.
>
>For all of the above to hold for set objects, they must be
>immutable anyway (#5 and #8, as well as the basic mathematical idea of set),
>and I've never expressed any disagreement with user-defined equality for
>immutable objects.  If you want to test mutable "sets" to see whether they
>have the same members, but I'm not sure with calling such a test equality,
>unless equality is just another binary predicate.

Although "mutable sets" is an oxymoron, and although types are _not_
sets, equality is not the same as identity, and should not be like
that, if you want to deal with non-trivial applications.

Peter makes a good point concerning the separation of behaviour from
representation: if you really want to separate them, you have to 
separate equality from identity.

In other words, we come pretty close to the concepts of _isomorphism_
and _canonicality_: the former refers to types or sets, the latter to
their elements or instances respectively.

If you wish to combine _equality_ with _identity_, then a combination
of the two above helps a lot: if _any_ time we construct an object
which happens to be _isomorphic_ to one previously stored, the 
constructor function simply returns the same location in memory as 
the first. This approach introduces _canonicality_ in a programming
environment: two equal expressions are represented by pointers to one
_canonical_ data structure. 

Since nothing is so simple in this world, in order to be consistent
with our models, we need _algorithms_ to _convert_ an expression/value
to a canonical form (say goodbye to "mutability"): the deriving 
representation must be _canonical_ with respect to a _class_ of functions, 
ie. two _mathematically_ equivalent_ forms in that class, are 
algorithmically mapped to identical _unique_ forms. Example:

x, y : Integer
x-x == y-y == 0

The canonical form above is the 0:Integer, ie. we came to  a canonical
form in respect to _implementation_ (remember that we started from
_behaviour_)

These things are definitely not new, and they have been used since _years_
with _much_ success in computer algebra systems like Maple and in
general purpose languages like Lisp: Signature Hashing is by no means
a new term in the CS community.

If one still wishes to program with side-effects,  then you have
to be more careful with the _destructive_ operations. In general
there is no reason to impose a paradigm which forces the user
to use side-effects in the 90% of the situations in which he does
not need them: given a good algorighm for generating canonical forms
for each class, there is _no_ need at all to care about efficiency
of "mutability", which is much _less_ than the 10% of the _whole_ work.

Equality is not something which you can sacrifice for _forcing_
the user to write ugly and _inneficient_ programs full with side-effects 
and unexpected behaviour. For sure you _need_ mutable objects, _but_ they 
are a _very_ small minority in a _decent_ program.

Philip Santas

  "In an evolving universe those who stand still are really moving backwards"
--------------------------------------------------------------------------------
email: santas@inf.ethz.ch				 Philip Santas
Mail: Dept. Informatik			       Inst. of Scientific Computation
      ETH-Zentrum			  Swiss Federal Institute of Technology
      CH-8092 Zurich				       Zurich, Switzerland
      Switzerland
Phone: +41-1-2547478