NICE-ESG-Libs Digest Thu, 16 Feb 95 Volume 1 : Issue 186
Today's Topics:
LIB95-TWR-HASHABLE and HASHABLE2
LIB95-TWR-PART_COMPARABLE
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: 16 Feb 1995 10:30:15-GMT
From: paj
Subject: LIB95-TWR-HASHABLE and HASHABLE2
To: NICE-ESG-Libs@atlanta.twr.com
TWR-LIB95-HASHABLE removes the "is_hashable" feature and precondition
from HASHABLE.
This precondition was orignally introduced because hash tables usually
use a default value in the key array to flag an empty cell. This
works for reference types because the default value is Void, and Void
is not hashable. Now we can hash on integers and reals, default
values no longer have this property.
I support the motion. If a hash table cannot handle default values as
keys, let it say so in its preconditions e.g
has (k: KEY): BOOLEAN
-- Is `k' in this table?
require
not_void: k /= Void;
not_default: k /= k.default;
A hash table that can handle default value keys (e.g by using a
parallel array of BOOLEAN to flag empty cells) does not then need
special case code to evaluate the hashes for default key value.
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.
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.
Paul.
--
Paul Johnson | GEC-Marconi Ltd is not responsible for my opinions. |
+44 245 473331 ext 3245 +-----------+-----------------------------------------+
Work: | You are lost in a twisty maze of little
Home: | standards, all different.
Date: 16 Feb 1995 10:09:04-GMT
From: paj
Subject: LIB95-TWR-PART_COMPARABLE
To: NICE-ESG-Libs@atlanta.twr.com
Misprint
--------
The definition of PART_COMPARABLE lists itself as an ancestor. I
assume that this is a misprint.
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
This introduces reference equality (or shallow equality for expanded
types) into COMPARABLE, which I thought we were trying to avoid (c.f
the golfing example). Therefore I think that either this routine should be
left undefined in COMPARABLE, or it should be defined in both
PART_COMPARABLE and COMPARABLE in terms of an order equality test (see
below).
Ordering Equality Test
----------------------
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);
The second two postconditions together express the
"(a <= b) and not (a < b)" condition in both directions.
The last term in postconditions could be adapted into the default
implementation, or (perhaps better) we will leave both "<" and
"order_equal" deferred and define "<=" in those terms in both
PART_COMPARABLE and COMPARABLE. I don't see how we can get away
without two deferred routines unless we initially implement
"order_equal" in terms of "is_equal" and let the descendants redefine
it if appropriate. I would be against this: descendants of COMPARABLE
should need to explicitly state their semantics. Opinions anyone?
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.
The name might be changed. I picked "order_equal" as simply
descriptive, but perhaps we should have an infix operator instead (I
would suggest "&="). This has the advantage of fitting in with the
other comparison operators, but the disadvantage that the binary
arithmetic operators have higher precedance than the comparison
operators but lower than the free operators. Hence we would see
a * b < c + d
parsed as
(a * b) < (c + d)
but
a * b &= c + d
parsed as
a * (b &= c) + d
which is not the Right Thing. I don't know what the best solution
might be. Does anyone have any other comments?
If I get two messages supporting this addition in principle then I
will submit a revised version to the chair as a formal motion.
--
Paul Johnson | GEC-Marconi Ltd is not responsible for my opinions. |
+44 245 473331 ext 3245 +-----------+-----------------------------------------+
Work: | You are lost in a twisty maze of little
Home: | standards, all different.
|
