NetNews Usenet Archive 1992 #31/NN_1992_31.iso/spool/comp/object/4637

Text File | 1992-12-22 | 4.9 KB | 104 lines

Newsgroups: comp.object
Path: sparky!uunet!spool.mu.edu!yale.edu!ira.uka.de!chx400!bernina!neptune!santas
From: [e-mail] (Philip)
Subject: Re: Equality
Message-ID: <[e-mail]>
Sender: [e-mail] (Mr News)
Nntp-Posting-Host: ru8.inf.ethz.ch
Organization: Dept. Informatik, Swiss Federal Institute of Technology (ETH), Zurich, CH
References: <[e-mail]> <[e-mail]> <[e-mail]>
Date: Tue, 22 Dec 1992 23:41:47 GMT
Lines: 91

In article <[e-mail]> [e-mail] (Dave Griffith) writes:
> [e-mail] (Peter Grogono) writes:
>>[e-mail] (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: [e-mail]                 Philip Santas
Mail: Dept. Informatik                   Inst. of Scientific Computation
      ETH-Zentrum              Swiss Federal Institute of Technology
      CH-8092 Zurich                       Zurich, Switzerland
      Switzerland
Phone: [phone]