[BUG] Dictionary equality test

Richard A. O'Keefe ok at cs.otago.ac.nz
Tue Jun 18 05:20:54 UTC 2002


One last time:
	Now, if you stretch out that context to the mathematical extremes you did, yes,
	there may be a small traces of potential ambiguity.
	
Comparing dictionaries is hardly "mathematical extremes".

Let me remind readers that I am *NOT* proposing adding a new operation
to Squeak.  I am simply proposing that an *EXISTING* operation which is
badly broken should be given an interpretation which is
 - consistent with the use of = on Array,
 - consistent with other programming languages,
 - consistent with the standard idea of what mathematical value,
   a dictionary represents,
 - not easily obtainable any other way, and
 - actually useful.

	Honestly, if I had to guess a single meaning of Set>>=, I would
	have guessed what it currently does.

Fine.  We agree.  The definition of Set>>= is consistent with the
meaning of equality for sets in general, with other languages, and
with equality of collections in Smalltalk generally.

	I probably wouldn't, however, for Dictionary, Bag and
	OrderedCollection.  What does the Set theory book say about those?

That's because the definition for Dictionary is BROKEN.
(I have posted a correction).
And the definition for Bag is BROKEN.
(I have posted a correction; it's in the same change set.)

The definition for OrderedCollection is inherited from SequenceableCollection:
    = otherCollection
	self == otherCollection ifTrue: [^true].
	self species == otherCollection species ifFalse: [^false].
	^self hasEqualElements: otherCollection

    hasEqualElements: otherCollection
	|size|
	(otherCollection isKindOf: SequenceableCollection)
	    ifFalse: [^false].
        (size := self size) = otherCollection size
	    ifFalse: [^false].
	1 to: size do: [:index |
	    (self at: index) = (otherCollection at: index)
		ifFalse: [^false]].
	^true

Apart from the usual Squeak insistence that the two be roughly the
same kind of collection, this is indeed precisely the standard
mathematical definition:

    Two OrderedCollections are equal if and only if
	- they have the same domain (here: size)
	- they are pointwise equal (here: at:)

Mutatis mutandis, this is precisely the same as the semantics of
= for Arrays and it is precisely the semantics I want for equality
of Dictionaries.

	> on pp 108-109 of Common Lisp, the Language, 2nd edition:
	> Two hash tables are considered the same ... if and only if
	> they satisfy a four-part test:
	
	Wow, all that meaning in one little = message!

It is no more complicated than the existing OrderedCollection>>=,
to which it is indeed isomorphic.  And it pales into insignificance
when you look into what happens with #+.

	Hey, I can't disagree with the mathematical definitions you've
	referenced, a less ambiguous message name is more productive.
	
BUT THERE IS NOTHING IN THE SLIGHTEST AMBIGUOUS ABOUT THE MESSAGE NAME.

There is only *one* mathematical definition of equality for finite mappings
on offer.  I want to have the same kind of equality available for Dictionaries
and Bags that we have for Arrays and OrderedCollections.  And I want to use
the intention-revealing method name #= for this equality operation.

The only serious rival to this interpretation of #= that is on the table
is #==, but we already HAVE #==.

	It is not my intent to stifle any improvements to the Collection
	classes.  I am all for mathematical rigor as much as possible!

Mathematical rigor has nothing to do with the case.
We have a BROKEN operation.
I want it to do something useful.
There is only one common-sensical thing it could mean:
two finite mappings are equal iff they have the same keys in their
domain and the values for corresponding keys are equal.
The ONE semantics should apply uniformly to Arrays, OrderedCollections,
Bags, and Dictionaries.

Why is this hard to understand?



More information about the Squeak-dev mailing list