NICE-ESG-Libs Digest Fri, 10 Feb 95 Volume 1 : Issue 181
Today's Topics:
LIB95-TWR-COMPARABLE
LIB95-TWR-HASHABLE
LIB95-TWR-HASHABLE2 (2 msgs)
LIB95-TWR-PART_COMPARABLE
Tower proposals, PART_COMPARABLE, COMPARABLE and HASHABLE
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: Fri, 10 Feb 1995 13:36:06 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: LIB95-TWR-COMPARABLE
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
LIB95-TWR-COMPARABLE
--------------------
SUMMARY:
--------
There are several differences between the proposed COMPARABLE below
and the current one in PELKS.
1. This COMPARABLE inherits from PART_COMPARABLE described in a
separate proposal
2. There is no redefinition of `is_equal' nor is there any use of
`is_equal' in postconditions.
3. The return values of `three_way_comparison' are relaxed to allow
for more efficent implementation.
4. Several postconditions are stronger
5. The invariant is replaced with a postcondition on `<'
RATIONALE:
----------
1. The inheritance from PART_COMPARABLE is natural, both from an
implementation and theoretical perspective and the relationship
between the two classes is more completely discussed in the
proposal for PART_COMPARABLE.
2. The lack of `is_equal' in this proposal reflects the fact that
there are several useful levels on which to compare objects for
equality. Eiffel already has the concept of reference equality `=',
and two types of value equality `is_equal' and
`deep_equal'. Another possible kind of equality is
"order_equality". This notion of equality is not necessarily the
same as any of the aforementioned forms of equality. In particular,
it is often useful to separate the notion of "order equality" from
shallow equality (`is_equal'). PELKS does not allow this separation
since it insists that the comparison operators are intimately tied
to the notion of `is_equal'.
As an example of the utility of providing a separate notion of
order equality, consider a golf tournament. In the final standings,
any of a number of separate golfers may posess the same score. If
we were to write a program to analyze the standings, we might
define a class GOLFER and have it inherit from COMPARABLE and
redefine the ordering relations to compare the final scores of
golfers. This is where a problem arises. Given the PELKS use of
`is_equal' in COMPARABLE, `is_equal' must be redefined to state
that two GOLFERs are `is_equal' if their scores are the same. This
means that `is_equal' can no longer be used to see if two objects
represent the same GOLFER. We can only tell if two GOLFERs have the
same score. In other words, the standard use of `is_equal' is
usurped by its new use in GOLFER (via COMPARABLE).
It is actually quite simple to consistently and completely define
the concept of a total ordering (COMPARABLE) without ever bringing
in an independent definition of equality. This proposal does this
and many abstract math texts do the same. In other words, equality
for the ordering is completely defined in terms of `<' and `<='. So
two items `a' and `b' are "equal" in the sense of the ordering if:
(a <= b) and (not a < b)
It is unneccesary and superfluous to tie the concept of `is_equal'
to the concept of equality defined by the ordering.
3. The return values for three_way_comparison should be either
positive, negative, or 0 rather than 1, -1, or 0. This is because
for many numeric arguments, a.three_way_comparison(b) could be
implemented as
Result := (a-b)
rather than the less efficient
if a > b then
Result := 1
else if a < b then
Result := -1
else
Result := 1
There is no loss of information or correctness with the proposed
change.
4. Several postconditions are strenghtened in this proposal. For
example, the single postcondition on PELKS `<' is
assymetric: Result implies not (other < Current)
this can be strengthened, given the nature of a total ordering, to be
other_not_less_or_equal : Result = (not (other <= Current));
The postcondition in `<=' relies on `is_equal' which is not
desirable for reasons described above, so the postconditions on
`<=' have been modified to eliminate this use of `is_equal'.
The postconditions for `>' and `>=' in this proposal can be found
in PART_COMPARABLE. These two relations are completely defined in
terms of `<' and `<='. Their postconditions are identical to the
ones found in COMPARABLE in PELKS.
The equal_zero postcondition of `three_way_comparison' eliminates
the use of `is_equal' and defines equality in terms of other
relational operators as described in point 2 above..
5. The invariant is removed and used as a postcondition (in an altered
form) on the routine `<'.
SHORT:
------
-------------------------------------------------------------------------------
-- Elements that may be compared for a total order relation. Descendants need
-- only define the behavior of `infix "<"'.
--
-- Inheritance:
-- PART_COMPARABLE
-- redefine
-- infix "<",
-- infix "<="
-- end;
deferred class interface COMPARABLE
ancestors
COMPARABLE
PART_COMPARABLE
feature summary
infix "<" (other : like Current) : BOOLEAN
infix "<=" (other : like Current) : BOOLEAN
infix ">" (other : like Current) : BOOLEAN
infix ">=" (other : like Current) : BOOLEAN
max (other : like Current) : like Current
min (other : like Current) : like Current
three_way_comparison (other : like Current) : INTEGER
inherited features
-- From PART_COMPARABLE:
infix ">", infix ">="
feature specification
-- Features from PART_COMPARABLE
infix "<" (other : like Current) : BOOLEAN
-- Is `Current' strictly less than `other'?
-- This features determines the total ordering.
--
-- Redefined from PART_COMPARABLE to strengthen the
-- postcondition.
require else
other_not_void : other /= void;
deferred
ensure then
other_not_less_or_equal : Result = (not (other <= Current));
irreflexive : (Current = other) implies (not Result);
infix "<=" (other : like Current) : BOOLEAN
-- Is `Current' less than or equal to `other'?
--
-- Effects the deferred feature from PART_COMPARABLE.
require else
other_not_void : other /= void;
ensure then
other_not_less : Result = (not (other < Current));
reflexive : (Current = other) implies Result;
feature specification
-- Other useful features for comparable objects.
three_way_comparison (other : like Current) : INTEGER
-- The relative position of `Current' to `other':
-- `< 0' if `Current < other';
-- `0' if `Current = other';
-- `> 0' if `Current > other'.
require
other_not_void : other /= void;
ensure
equal_zero : (Result = 0) = (not ((Current < other) or (Current > other)));
smaller_negative : (Result < 0) = (Current < other);
greater_positive : (Result > 0) = (Current > other);
min (other : like Current) : like Current
-- The smaller of `Current' and `other';
-- `Current' if thay are comparably equal.
require
other_not_void : other /= void;
ensure
not_void : Result /= void;
current_if_not_greater : (Current <= other) implies (Result = Current);
other_if_greater : (Current > other) implies (Result = other);
max (other : like Current) : like Current
-- The larger of `Current' and `other';
-- `other' if thay are comparably equal.
require
other_not_void : other /= void;
ensure
not_void : Result /= void;
current_if_not_smaller : (Current >= other) implies (Result = Current);
other_if_smaller : (Current < other) implies (Result = other);
end interface -- class COMPARABLE
Date: Fri, 10 Feb 1995 13:24:09 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: LIB95-TWR-HASHABLE
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
LIB95-TWR-HASHABLE
------------------
RATIONALE:
----------
This proposal removes the feature `is_hashable' from HASHABLE and
therefore the restriction that default values cannot be hashed. This
restriction is arbitrary from the user's viewpoint and is an artifact
of an implementation that can easily be altered. Numerous comments
have been expressed both publicly on comp.lang.eiffel and privately
expressing the desire to remove this restriction.
SHORT:
------
-------------------------------------------------------------------------------
-- Hashable elements
--
-- Inheritance:
-- -- none
deferred class interface HASHABLE
ancestors
HASHABLE
feature summary
hash_code : INTEGER
feature specification
hash_code : INTEGER
-- Hash_code value
deferred
ensure
non_negative : Result >= 0;
end interface -- class HASHABLE
Date: Fri, 10 Feb 1995 13:25:47 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: LIB95-TWR-HASHABLE2
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
LIB95-TWR-COMPARABLE
--------------------
SUMMARY:
--------
There are several differences between the proposed COMPARABLE below
and the current one in PELKS.
1. This COMPARABLE inherits from PART_COMPARABLE described in a
separate proposal
2. There is no redefinition of `is_equal' nor is there any use of
`is_equal' in postconditions.
3. The return values of `three_way_comparison' are relaxed to allow
for more efficent implementation.
4. Several postconditions are stronger
5. The invariant is replaced with a postcondition on `<'
RATIONALE:
----------
1. The inheritance from PART_COMPARABLE is natural, both from an
implementation and theoretical perspective and the relationship
between the two classes is more completely discussed in the
proposal for PART_COMPARABLE.
2. The lack of `is_equal' in this proposal reflects the fact that
there are several useful levels on which to compare objects for
equality. Eiffel already has the concept of reference equality `=',
and two types of value equality `is_equal' and
`deep_equal'. Another possible kind of equality is
"order_equality". This notion of equality is not necessarily the
same as any of the aforementioned forms of equality. In particular,
it is often useful to separate the notion of "order equality" from
shallow equality (`is_equal'). PELKS does not allow this separation
since it insists that the comparison operators are intimately tied
to the notion of `is_equal'.
As an example of the utility of providing a separate notion of
order equality, consider a golf tournament. In the final standings,
any of a number of separate golfers may posess the same score. If
we were to write a program to analyze the standings, we might
define a class GOLFER and have it inherit from COMPARABLE and
redefine the ordering relations to compare the final scores of
golfers. This is where a problem arises. Given the PELKS use of
`is_equal' in COMPARABLE, `is_equal' must be redefined to state
that two GOLFERs are `is_equal' if their scores are the same. This
means that `is_equal' can no longer be used to see if two objects
represent the same GOLFER. We can only tell if two GOLFERs have the
same score. In other words, the standard use of `is_equal' is
usurped by its new use in GOLFER (via COMPARABLE).
It is actually quite simple to consistently and completely define
the concept of a total ordering (COMPARABLE) without ever bringing
in an independent definition of equality. This proposal does this
and many abstract math texts do the same. In other words, equality
for the ordering is completely defined in terms of `<' and `<='. So
two items `a' and `b' are "equal" in the sense of the ordering if:
(a <= b) and (not a < b)
It is unneccesary and superfluous to tie the concept of `is_equal'
to the concept of equality defined by the ordering.
3. The return values for three_way_comparison should be either
positive, negative, or 0 rather than 1, -1, or 0. This is because
for many numeric arguments, a.three_way_comparison(b) could be
implemented as
Result := (a-b)
rather than the less efficient
if a > b then
Result := 1
else if a < b then
Result := -1
else
Result := 1
There is no loss of information or correctness with the proposed
change.
4. Several postconditions are strenghtened in this proposal. For
example, the single postcondition on PELKS `<' is
assymetric: Result implies not (other < Current)
this can be strengthened, given the nature of a total ordering, to be
other_not_less_or_equal : Result = (not (other <= Current));
The postcondition in `<=' relies on `is_equal' which is not
desirable for reasons described above, so the postconditions on
`<=' have been modified to eliminate this use of `is_equal'.
The postconditions for `>' and `>=' in this proposal can be found
in PART_COMPARABLE. These two relations are completely defined in
terms of `<' and `<='. Their postconditions are identical to the
ones found in COMPARABLE in PELKS.
The equal_zero postcondition of `three_way_comparison' eliminates
the use of `is_equal' and defines equality in terms of other
relational operators as described in point 2 above..
5. The invariant is removed and used as a postcondition (in an altered
form) on the routine `<'.
SHORT:
------
-------------------------------------------------------------------------------
-- Elements that may be compared for a total order relation. Descendants need
-- only define the behavior of `infix "<"'.
--
-- Inheritance:
-- PART_COMPARABLE
-- redefine
-- infix "<",
-- infix "<="
-- end;
deferred class interface COMPARABLE
ancestors
COMPARABLE
PART_COMPARABLE
feature summary
infix "<" (other : like Current) : BOOLEAN
infix "<=" (other : like Current) : BOOLEAN
infix ">" (other : like Current) : BOOLEAN
infix ">=" (other : like Current) : BOOLEAN
max (other : like Current) : like Current
min (other : like Current) : like Current
three_way_comparison (other : like Current) : INTEGER
inherited features
-- From PART_COMPARABLE:
infix ">", infix ">="
feature specification
-- Features from PART_COMPARABLE
infix "<" (other : like Current) : BOOLEAN
-- Is `Current' strictly less than `other'?
-- This features determines the total ordering.
--
-- Redefined from PART_COMPARABLE to strengthen the
-- postcondition.
require else
other_not_void : other /= void;
deferred
ensure then
other_not_less_or_equal : Result = (not (other <= Current));
irreflexive : (Current = other) implies (not Result);
infix "<=" (other : like Current) : BOOLEAN
-- Is `Current' less than or equal to `other'?
--
-- Effects the deferred feature from PART_COMPARABLE.
require else
other_not_void : other /= void;
ensure then
other_not_less : Result = (not (other < Current));
reflexive : (Current = other) implies Result;
feature specification
-- Other useful features for comparable objects.
three_way_comparison (other : like Current) : INTEGER
-- The relative position of `Current' to `other':
-- `< 0' if `Current < other';
-- `0' if `Current = other';
-- `> 0' if `Current > other'.
require
other_not_void : other /= void;
ensure
equal_zero : (Result = 0) = (not ((Current < other) or (Current > other)));
smaller_negative : (Result < 0) = (Current < other);
greater_positive : (Result > 0) = (Current > other);
min (other : like Current) : like Current
-- The smaller of `Current' and `other';
-- `Current' if thay are comparably equal.
require
other_not_void : other /= void;
ensure
not_void : Result /= void;
current_if_not_greater : (Current <= other) implies (Result = Current);
other_if_greater : (Current > other) implies (Result = other);
max (other : like Current) : like Current
-- The larger of `Current' and `other';
-- `other' if thay are comparably equal.
require
other_not_void : other /= void;
ensure
not_void : Result /= void;
current_if_not_smaller : (Current >= other) implies (Result = Current);
other_if_smaller : (Current < other) implies (Result = other);
end interface -- class COMPARABLE
Date: Fri, 10 Feb 1995 13:29:57 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: LIB95-TWR-HASHABLE2
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
LIB95-TWR-HASHABLE2
-------------------
RATIONALE:
----------
This proposal seeks to eliminate the class HASHABLE and move the
feature `hash_code' to the class GENERAL. The feature specification in
GENERAL is given below. `hash_code' would be an effective routine in
GENERAL with the obvious advantage that all objects would now be
hashable. Of course, a class could always override the default
`hash_code' if necessary (e.g. STRING). The only semantic requirement
on hash_code (which, unfortunately, cannot be expressed as a postcondition)
is that for al objects `a' and `b':
a.is_equal(b) implies (a.hash_code = b.hash_code)
SHORT:
------
-------------------------------------------------------------------------------
feature specification
hash_code : INTEGER
-- Hash_code value
ensure
-- For all objects a and b:
-- a.is_equal(b) implies (a.hash_code = b.hash_code)
non_negative : Result >= 0;
Date: Fri, 10 Feb 1995 13:31:57 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: LIB95-TWR-PART_COMPARABLE
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
LIB95-TWR-PART_COMPARABLE
-------------------------
RATIONALE:
----------
This proposal introduces the class PART_COMPARABLE implementing the
mathematical notion of partial orderings and lattices. Partial
orderings are a natural generalization of total orderings represented
by the class COMPARABLE. PART_COMAPRABLE is, therefore, a natural
ancestor of COMPARABLE. The principal difference between total and
partial orderings is that total orderings require exactly one of the
following to be true for all `a' and `b' that are memebers of the set
over which the order is defined:
a < b, a = b, or a > b
Partial orders relax this requirement and say that at most one of the
above can be true. It is therefore possible for none of the above to
be true for a given `a' and `b' in a partial order.
Examples of partial orders abound in computer science and software
applications. The Eiffel inheritance hierarchy is an example of a
partial ordering. If we view the operator `<' as meaning "properly
descends from", then it is obvious that at most one of the following
is true for classes A and B:
A < B, A = B, A > B
The fact that none of these may be true is a reflection of the fact
that two classes may not have any inheritance relationship at all.
Many other applications for partial orderings abound as well.
PART_COMPARABLE forms a natural ancestor for COMPARABLE. All that is
required is that the post conditions of the routines be strengthened
to indicate that total orders (COMPARABLE) require all pairs of the
relational domain to be comparable.
Addition of this class will not affect existing software that uses
COMPARABLE in any way. It does provide a more complete basis for
writing abstract math classes and graph oriented applications.
Furthermore, ISE's, SIG's, and Tower's existing libraries have a
PART_COMPARABLE class. PART_COMPARABLE was also present in Eiffel 2.X
SHORT:
------
-----------------------------------------------------------------------------
-- Elements that may be compared in a partial order relation. If the elements
-- being compared are not comparable with one another, these features return
-- false. Note that partial equality is not necessarily the same as
-- `is_equal', since `is_equal' is not necessarily tied to the notion of
-- ordering. Therefore the partial ordering is defined in terms of the
-- deferred features, `infix "<"' and `infix "<="'.
--
-- Inheritance:
-- -- none
deferred class interface PART_COMPARABLE
ancestors
PART_COMPARABLE
feature summary
infix "<" (other : like Current) : BOOLEAN
infix "<=" (other : like Current) : BOOLEAN
infix ">" (other : like Current) : BOOLEAN
infix ">=" (other : like Current) : BOOLEAN
feature specification
-- Deferred routines that determine the partial ordering.
infix "<" (other : like Current) : BOOLEAN
-- Is `Current' strictly less than `other'?
require
other_not_void : other /= void;
deferred
ensure
consistent : Result implies (not (other <= Current));
irreflexive : (Current = other) implies (not Result);
infix "<=" (other : like Current) : BOOLEAN
-- Is `Current' less than or equal to `other'?
require
other_not_void : other /= void;
deferred
ensure
consistent : Result implies (not (other < Current));
reflexive : (Current = other) implies Result;
feature specification
-- Effective routines whose behavior are determined by the behavior of
-- `infix "<"' and `infix "<="'.
infix ">" (other : like Current) : BOOLEAN
-- Is `Current' strictly greater than `other'?
require
other_not_void : other /= void;
ensure
defintion : Result = (other < Current);
infix ">=" (other : like Current) : BOOLEAN
-- Is `Current' greater than or equal to `other'?
require
other_not_void : other /= void;
ensure
defintion : Result = (other <= Current);
end interface -- class PART_COMPARABLE
Date: Fri, 10 Feb 1995 13:22:42 +1100 (EST)
From: cmingins@apple.fcit.monash.edu.au (Christine Mingins)
Subject: Tower proposals, PART_COMPARABLE, COMPARABLE and HASHABLE
To: NICE-ESG-Libs@atlanta.twr.com (NICE-esg-libs )
Dear Committee Members,
Tower have submitted four amendment proposals for the group of
classes PART_COMPARABLE, COMPARABLE and HASHABLE.
They are titled:
LIB95-TWR-HASHABLE
LIB95-TWR-HASHABLE2
LIB95-TWR-COMPARABLE
LIB95-TWR-PART-COMPARABLE
Discussion is now open for these classes. The deadline for discussion,
of 20 February, will be extended if anyone requests it, or if there
is still discussion going on.
Best Regards
Christine
|
