kim@helios.enea.se (Kim Wald`n) (05/05/90)
Some days ago I used an example with sorted lists of airplanes
in an Eiffel course to show how easy it is to introduce meaningful
order relations for high level objects.
Much to my surprise, explaining how this is elegantly achieved
through the standard library immediately revealed several serious errors
in the kernel classes COMPARABLE and PART_COMPAR.
1) The postconditions in COMPARABLE are circularly defined, so when
assertion checking is on, the result is an infinite loop.
The postconditions of "<" and ">=" are each defined in terms of the
other operation, and the same holds for ">" and "<=".
For the first two operators, this might go unnoticed if the postcondition
of the deferred routine "<" is not repeated in descendant classes,
but any use of the last two with full assertion checking bites directly.
Instead, the postcondition for "<" should be dropped in COMPARABLE,
and the postconditions for "<=", ">", and ">=" should all be
expressed in terms of "<".
2) The next error is more serious: the body of "<=" is
Result := (Current < other) or (equal (other))
in both COMPARABLE and PART_COMPAR.
Now "equal" is a feature inherited from class ANY, which makes a
field-by-field comparison of whole objects to find out whether they
are identical in some sense (shallow semantics in this case).
However, this is not the same as "ordering" equality.
When a transport company ranks its trucks by freight capacity,
it doesn't seem reasonable to have the respective hood colors influence
the outcome of "<=" operations. But what is even worse, is that it
will often lead to situations where none of "<", "<=", ">", ">=" holds
for a pair of objects, thus violating the very core of a total order
relation in the case of class COMPARABLE. This may lead to any kind
of strange behavior in applications.
In PART_COMPAR, which implements a partial order relation, there is
no reasonable way to express "ordering" equality only in terms of "<",
so either "<=" or ">=" must also be deferred (and the other expressed
in terms of the deferred one).
For the same reasons, the obsolete routines "eq" and "ne" should be
removed, since they would have to be changed to deferred anyway.
In COMPARABLE, however, it suffices to replace the body of "<=" by
Result := not (other < Current)
Below are the complete context diffs (diff -c) to fix the problems.
If you have access to Larry Walls ``patch'' program, you may simply
goto directory .../Eiffel/library/kernel, and feed this entire article
verbatim on standard input to ``patch'', which will then automatically
update the two classes and leave the originals as ``comparable.e.orig''
and ``part_compar.e.orig'' respectively.
*** comparable.e Fri May 4 18:40:28 1990
--- comparable.e.new Fri May 4 17:33:16 1990
***************
*** 22,37 ****
infix "<" (other: like Current): BOOLEAN is
-- Is current element less than `other'?
deferred
- ensure
- Result implies (not (Current >= other))
end; -- "<"
infix "<=" (other: like Current): BOOLEAN is
-- Is current element less than or equal to `other'?
do
! Result := (Current < other) or (equal (other))
ensure
! Result implies (not (Current > other))
end; -- "<="
infix ">" (other: like Current): BOOLEAN is
--- 22,35 ----
infix "<" (other: like Current): BOOLEAN is
-- Is current element less than `other'?
deferred
end; -- "<"
infix "<=" (other: like Current): BOOLEAN is
-- Is current element less than or equal to `other'?
do
! Result := not (other < Current)
ensure
! Result implies (not (other < Current))
end; -- "<="
infix ">" (other: like Current): BOOLEAN is
***************
*** 39,45 ****
do
Result := other < Current
ensure
! Result implies (not (Current <= other))
end; -- ">"
infix ">=" (other: like Current): BOOLEAN is
--- 37,43 ----
do
Result := other < Current
ensure
! Result implies (other < Current)
end; -- ">"
infix ">=" (other: like Current): BOOLEAN is
*** part_compar.e Fri May 4 21:23:25 1990
--- part_compar.e.new Fri May 4 17:36:30 1990
***************
*** 22,29 ****
infix "<=" (other: like Current): BOOLEAN is
-- Is current element less than or equal to `other'?
! do
! Result := (Current < other) or (equal (other))
end; -- "<="
infix ">" (other: like Current): BOOLEAN is
--- 22,28 ----
infix "<=" (other: like Current): BOOLEAN is
-- Is current element less than or equal to `other'?
! deferred
end; -- "<="
infix ">" (other: like Current): BOOLEAN is
***************
*** 35,41 ****
infix ">=" (other: like Current): BOOLEAN is
-- Is current element greater than or equal to `other'?
do
! Result := (other < Current) or (equal (other))
end; -- ">="
-- obsolete routines
--- 34,40 ----
infix ">=" (other: like Current): BOOLEAN is
-- Is current element greater than or equal to `other'?
do
! Result := other <= Current
end; -- ">="
-- obsolete routines
***************
*** 45,62 ****
do
Result := Current < other
end; -- lt
-
- eq (other: like Current): BOOLEAN
- obsolete "Use ``equal''" is
- do
- Result := equal (other)
- end; -- eq
-
- ne (other: like Current): BOOLEAN
- obsolete "Use negation of ``equal''" is
- do
- Result := not equal (other)
- end; -- ne
le (other: like Current): BOOLEAN
obsolete "Use infix ``<=''" is
--- 44,49 ----
-- Kim Walden
Enea Data, Sweden
kim@enea.sestephan@eiffel.UUCP (Philippe Stephan) (05/08/90)
In response to <KIM.90May5032047@helios.enea.se>, about "Errors in COMPARABLE and PART_COMPAR", 2 things have to be said: 1) The forthcoming version of the compiler allows circularly defined assertions: when assertion checking involves a call to a routine, no assertion check is made on the called routine. What's pointed out is actually a bug in 2.2. 2) The function `equal' from ANY is redefinable. Its default behavior is to do a field by field comparison, but why not? The freight capacity of a truck can of course be the only criterion for a sort, if you want so. Philippe Stephan. stephan@eiffel.com
kim@helios.enea.se (Kim Wald`n) (05/09/90)
In article <325@eiffel.UUCP> stephan@eiffel.UUCP (Philippe Stephan) writes: > 1) The forthcoming version of the compiler allows circularly > defined assertions: when assertion checking involves a call to a > routine, no assertion check is made on the called routine. What's > pointed out is actually a bug in 2.2. Seems reasonable. > 2) The function `equal' from ANY is redefinable. Its default > behavior is to do a field by field comparison, but why not? > The freight capacity of a truck can of course be the only criterion > for a sort, if you want so. You are missing the point. First, class COMPARABLE implements a total order relation. In a total order relation, strict order and equality are not independent. a > b is identical to b < a and a = b is identical to ( not a < b and not a > b ) BY DEFINITION. Any other implementation of "=" breaks the deepest meaning of the class, as fundamental properties, like "For all pairs, exactly one of a < b a > b a = b is true" will no longer hold. This is the worst that can happen to a class. So the current implementation of COMPARABLE is plain wrong, and can easily cause subtle bugs in applications using it. It can only be correct by accident, in cases when ``equal'', whether redefined or not, HAPPENS to coincide with the definition above. Worse still, only "<=" in COMPARABLE uses ``equal'', while ">=" has the correct implementation Result := not (Current < other) so the meanings of the "=" parts in "<=" and ">=" are not even the same! (I'm using "=" as a simple notation for the corresponding concept in order relations here. It is not to be confused with the non-redefineable reserved Eiffel operator "=".) The correct thing is to implement "<=" as Result := not (other < Current) in accordance with the definition of total order relations (as in ">="). There is no reason whatsoever to involve ``equal'' from ANY, which is a feature to check object identity. The equality concept wanted as part of an order relation is something else. When you are ordering trucks by freight capacity, it seems reasonable to consider a yellow 2 ton truck as neither greater nor smaller than a green 2 ton truck. If you get a freight order for 2 tons, any one will do. But you still want a way to distinguish between them, should you ever need to smuggle 2 tons of whisky through the green forrest at the frontier, where a yellow truck is much too conspicuous. Second, class PART_COMPART implements a partial order relation, which means that for some pairs neither of a < b a > b a = b may hold. Therefore, the meaning of "=" cannot be inferred from "<", but their semantics are still closely linked, so a descendant class should define both for consistency. This means that one of "<=" and ">=" should also be deferred. As should be clear from the argumentation above, using ``equal'' from ANY in a default implementation of "<=", even if it is redefineable, is plain wrong for class COMPARABLE, and ad hoc and confusing at best for class PART_COMPAR. This may be corrected by applying the diffs from my previous article. -- Kim Walden Enea Data, Sweden kim@enea.se