Path: utzoo!utgpu!news-server.csri.toronto.edu!clyde.concordia.ca!uunet!samsung!usc!zaphod.mps.ohio-state.edu!rpi!uupsi!sunic!enea!helios!kim
From: kim@helios.enea.se (Kim Wald`n)
Newsgroups: comp.lang.eiffel
Subject: Errors in COMPARABLE and PART_COMPAR
Message-ID: <KIM.90May5032047@helios.enea.se>
Date: 5 May 90 01:20:47 GMT
Sender: kim@enea.se
Organization: Enea Data AB, Sweden
Lines: 178


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.se