🚀 go-pugleaf

In article <1992Dec14.075853.3399@lth.se> dag@bellman.control.lth.se (Dag Bruck) writes:
>In the recent discussion on pointer comparisons, Fergus Hendersson
>suggested adding a standard library function ptrcmp() instead of
>extending the definitions of "<" and ">" for pointers.  I think we
>also agreed on a reasonable relationship between ptrcmp() and the
>relational operators.

	I'm not sure we've all agreed on the relationship, if any,
between < and ptrcmp, but I think we agree that

	"there will be a library function ptrcmp(void*,void*)
	which defines a total order"

unless you can convince us the < is worth more  than
making assumptions about all future machine architectures.

>
>Now, here's the problem: this implementation works fine for all
>element types that have an "operator < ()" including plain built-in
>types and many user-defined types.  

	No...see below...

>However, it is not guaranteed to
>work with pointer elements for reasons we have discussed before.

	So clearly it doenst work with arbitrary user defined types
either for precisely the same reason. The user defined type
need not be a total order.

	Imagine my suprise when qsort failed! I couldnt
understand it until I realised by definition of < was wrong!

	The only way to fix this is to have a proper assertion
mechanism so you  can state that < for type T is a total order.
Gee,   T::operator< could return anything!

>
>3.  The programmer using class Tree must remember to use a different
>class for pointers.  There is no type checking that prevents the user
>from using Tree<Foo*> -- it will compile fine but produce the wrong
>results on some machines.

>I regard (3) is biggest problem, in particular as there is no way (as
>far as I know) to diagnose the problem.   It may work fine on some
>machines, and then break when you port the code to a new machine or a
>new memory model on the same machine.

	There are no constraints on templates that will ensure anything
except the existance of operator <. 

	You could always write the progam in terms of cmp(T,T),
not <. The it would work for pointers too, you would just
have to define cmp(T,T) for each type, including pointers,


	template<class T> int cmp(T a1, T a2){return a1<a2;}
	int cmp(void* a1, void* a2){return ptrcmp(a1,a2)<0;}

>
>Any comments or suggestions would be welcome.  I would be particularly
>happy if you could show that I have described a problem that in fact
>does not exist if you use a suitable programming style.

	The problem you mention might be solved with 'cmp'.

	The real problem cannot be solved at all, namely, for
a user define < or cmp, ensuring it is a total order.
Except of course by paper and pencil proof for each case.

-- 
;----------------------------------------------------------------------
        JOHN (MAX) SKALLER,         maxtal@extro.ucc.su.oz.au
	Maxtal Pty Ltd, 6 MacKay St ASHFIELD, NSW 2131, AUSTRALIA
;--------------- SCIENTIFIC AND ENGINEERING SOFTWARE ------------------