NICE-ESG-Libs Digest Thu, 16 Feb 95 Volume 1 : Issue 187
Today's Topics:
NICE-ESG-Libs Digest V1 #186
NICE Eiffel Standards Group -- Library Committee Mailing List
To post to list:
NICE-ESG-Libs@atlanta.twr.com
To send mail to the Chairman of the committee:
NICE-ESG-Libs-chair@atlanta.twr.com
Administrative matters (sign up, unsubscribe, mail problems, etc):
NICE-ESG-Libs-request@atlanta.twr.com
Date: Thu, 16 Feb 95 19:55:59 EST
From: fhart@atlanta.twr.com (C. Frederick Hart)
Subject: NICE-ESG-Libs Digest V1 #186
To: nice-esg-libs
This is a response to Paul's posting concerning the tower proposals
for COMPARABLE, PART_COMPARABLE, and HASHABLE.
| TWR-LIB95-HASHABLE2 seeks to move "hash_code" into ANY. I have two
| worries about this:
|
| 1: I dislike adding yet more features to ANY.
I agree that _unnecessary_ cluttering of GENERAL is undesirable. The
question then is: Is adding `hash_code' to GENERAL adding unnecessary
clutter? We proposed moving hash_code to GENERAL because a number of
people have expressed a desire to be able to hash objects of arbitrary
class. The question thus becomes: Where else can `hash_code' be put if
universal hashability is desired?
| 2: Suppose I have an object containing simply a reference. How should
| the system go about computing a hash code? The obvious starting
| point is the current value of the reference, but in a system with a
| copying GC that value is apt to change. And of course it *will*
| change when objects are stored and retrieved. I realise that of
| course it is not for us to define the default hash algorithm, but
| we must be very careful to avoid features that constrain
| implementors without good reason.
There is no unnecessary constraint on implementations implied
here. The only constraint is the one mentioned in the original
posting:
For all objects a and b:
a.is_equal(b) implies a.hash_code = b.hash_code
This condition can be assured by all current implementations for
arbitrary objects.
1. A "deep" algorithm can be employed.
2. A shallow algorithm that ignores refernece attributes completely
3. A shallow algorithm that uses the type of the object attached to
reference attributes rather than the value of the pointer.
Remember, the default hash_code does not have to be the best
hash_code. It does not even have to be a decent hash code for all
objects. For most complex objects that are hashed, the user will
probably override the default hash_code any way. The default hash_code
is provided so that users can still hash objects that they either can
not or do no wish to modify. The current situation for such objects is
that there is _no_ hash code and they are not hashable. Is this better
than at least providing a default hash code?
Finally, the persistance problem for hash_code can be avoided by using
one of the 3 proposed default hash_codes listed above. Any of the
three eliminate the problems with persistance. However, it should be
the implementor's choice as to which default algorithm to use.
| The definition of PART_COMPARABLE lists itself as an ancestor. I
| assume that this is a misprint.
Tis a misprint. Sorry.
| COMPARABLE <=
| -------------
|
| I am not entirely clear as to the semantics of this operator. The
| postconditions seem to imply that it returns true iff
|
| Current < other or Current = other
The precise postconditions for <= in COMPARABLE are:
ensure then
other_not_less : Result = (not (other < Current));
reflexive : (Current = other) implies Result;
The first of the two postconditions is the defintion. It fully fixes
the nature of `<='. The second postcondition states a (possibly
non-obvious) consequence of the first postcondition and is present for
consistency checking , but does not truly add any extra semantic
information. Reference or shallow equality is not part of the
definition of `<=' (Other than saying that the BOOLEAN value of "Result"
and the BOOLEAN value of "(not (other < Current))" are shallow equal)
In PART_COMPARABLE `<=' _is_ deferred since it is possible that there be
no order relation between two objects. In COMPARABLE, only `<' is
deferred since defining `<' fixes the definition of all of the other
operators in a total order. e.g.:
a <= b ::= not a < b
a > b ::= b < a
a <= b ::= b <= a
a = b ::= not (a < b) and not (b < a)
| The author of LIB-95-TWR-COMPARABLE writes that "is_equal" is not
| required in the assertions of PART_COMPARABLE or COMPARABLE, since
| "ordering" equality can be expressed as "(a <= b) and not (a < b)". I
| agree, but I notice that there is no order-equality method in the
| proposed specification. This seems to be a curious gap. I think we
| need one, such as in PART_COMPARABLE
|
| order_equal (other: like Current) : BOOLEAN
| -- Are `Current' and `other' at the same place in the ordered
| -- sequence of all objects of this type?
| require
| other_not_void: other /= Void;
| ensure
| commutive: Result = other.order_equal (Current);
| not_different: Result implies not (Current < other) and
| not (other < Current);
| consistent: Result = (Current <= other and other <= Current);
I like this proposal. (Note that the routine three_way_comparison was
intended to function more or less as an `order_equal' in COMPARABLE
but there is no such routine in PART_COMPARABLE).
Also `order_equal' should not be deferred in PART_COMPARABLE. There a
re two deferred routines in PART_COMPARABLE: `<' and `<='. Deferring
these two routines leaves no room for deferring any others in
PART_COMPARABLE.
We could switch the deferred/effective status of `<=' and
`order_equal' in PART_COMPARABLE, but our resident mathematician on
the library committee (Michael Schweitzer) has noted that most
mathematical texts define the remaining partial order relations in
terms of < and <= rather than < and =, therefore the preference for
deferring `<' and <='.
| This routine would be inherited unchanged by COMPARABLE. Other
| descendants would of course be at liberty to define a more efficient
| implementation. Also COMPARABLE would need to have modified
| postconditions for three_way_comparable to tie it into order_equal.
Technically, `three_way_comparison' in COMPARABLE need only be defined
in terms of `<', since all other features in COMPARABLE are defined in
terms of `<', including `order_equal'. The current postconditions of
`three_way_comparison' are sufficient, but if someone feels that they
would be more clear with the use of `order_equal' than the current use
of `<' and `>', then please suggest some changes.
I have no opinion on infix operators for `order_equal'
-- Fred Hart (fhart@atlanta.twr.com)
Tower Technology Corporation http://www.cm.cf.ac.uk/Tower/
|
