strange behaviour of compare/3

[Simon Strobl]

Hello,

I have just been fiddling around with a predicate that did the right thing only in the vast majority of cases. Eventually, I found out that my problem was that in a sorting procedure, I sometimes compared integers to floats. It would never have occurred to me that compare(>, 1, 1.0) is true.

Does this really have to be true? Maybe there are good reasons why this should be so. But then a word of warning in the manual entry of compare/3 would be very useful.

Simon

[Ulrich Neumerkel]

Simon Strobl writes:
>                                                                          It
>would never have occurred to me that compare(>, 1, 1.0) is true.
 
>Does this really have to be true? Maybe there are good reasons why this
>should be so. But then a word of warning in the manual entry of compare/3
>would be very useful.
 
compare/3 is a compact way to get the functionality of @< == etc.
ISO Term order (13211-1:7.2) is a total ordering of all kinds of
terms, including variables.  Even X and 3.0 compare - i.e. there is no
instantiation error in X @< 3.0 but there is one in X < 3.0.
 
The ordering is: variables, floats, integers, atoms, compounds.
 
In any case: This kind of ordering is probably not the one you want,
if you expect compare(=, 1, 1.0) to be true.
 
You probably would like to have some numcompare/3 defined with =:= and
<, yielding an instantation error for numcompare(R, 1, X).
Maybe even evaluating its arguments?
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Richard O'Keefe]

On 13 Jun 2009, at 1:09 am, Simon Strobl wrote:

>
> Hello,
>
> I have just been fiddling around with a predicate that did the right  
> thing
> only in the vast majority of cases. Eventually, I found out that my  
> problem
> was that in a sorting procedure, I sometimes compared integers to  
> floats. It
> would never have occurred to me that compare(>, 1, 1.0) is true.

Well, they *CAN'T* compare equal, because they are not the same term.
compare/3 is supposed to be total, so one of them has to be greater
than the other in the term order.

>
> Does this really have to be true?

Well, for one thing, the standard says so:

7.2 Term order
     If X and Y have different types: X term-precedes Y iff
     the type of X precedes the type of Y in the following order:
     variable precedes floating point precedes integer precedes
     atom precedes compound.

> Maybe there are good reasons why this should be so.

(1) compare/3 is supposed to be total.
(2) compare/3 is supposed to be consistent with arithmetic ordering
     for integers compared with integers and for floating point
     numbers compared with floating point numbers.
(3) compare(=, X, Y) may only succeed when X and Y are
     indistinguishable.
(4) 1 and 1.0 are not indistinguishable.  For example, it is
     possible to find an integer X such that X+1 > X but
     X+1.0 =:= X.
(5) From (3 and 4), compare(=, 1, 1.0) may not succeed.
(6) From (1 and 5), either compare(<, 1, 1.0) or compare(>, 1, 1.0).
(7) The choice between those two alternatives is fairly arbitrary,
     but it has to be consistent.  The standard chose float < integer.


> But then a word of warning in the manual entry of compare/3
> would be very useful.

Not a bad idea.   Just because something is standard and pretty
much necessary really doesn't mean it is obvious.

In the mean time, I suggest that mixing integers and floats in
a single sort is problematic in one way or another in most
dynamically typed languages.  For example, in one otherwise
sensible language, it is possible to find numbers X, Y, Z such
that X =:= Y and Y =:= Z but X < Z.


_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Ulrich Neumerkel]

>Not a bad idea.   Just because something is standard and pretty
>much necessary really doesn't mean it is obvious.

>In the mean time, I suggest that mixing integers and floats in
>a single sort is problematic in one way or another in most
>dynamically typed languages.  For example, in one otherwise
>sensible language, it is possible to find numbers X, Y, Z such
>that X =:= Y and Y =:= Z but X < Z.

Is it only the mixing of integers and floats that is problematic?  If
so, a floatcompare/3 nd intcompare/3 might make sense?
Aren't floats in general not the best candidates for compare/3,
as equality is problematic?
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Richard O'Keefe]

On 14 Jun 2009, at 4:08 am, Ulrich Neumerkel wrote:

> Simon Strobl writes:
>>                                                                         It
>> would never have occurred to me that compare(>, 1, 1.0) is true.
>
>> Does this really have to be true? Maybe there are good reasons why  
>> this
>> should be so. But then a word of warning in the manual entry of  
>> compare/3
>> would be very useful.
>
> compare/3 is a compact way to get the functionality of @< == etc.
> ISO Term order (13211-1:7.2) is a total ordering of all kinds of
> terms, including variables.  Even X and 3.0 compare - i.e. there is no
> instantiation error in X @< 3.0 but there is one in X < 3.0.
>
> The ordering is: variables, floats, integers, atoms, compounds.
>
> In any case: This kind of ordering is probably not the one you want,
> if you expect compare(=, 1, 1.0) to be true.
>
> You probably would like to have some numcompare/3 defined with =:= and
> <, yielding an instantation error for numcompare(R, 1, X).\

Remember above all that if you are sorting, you want your
comparison predicate to satisfy these laws:
     for all X, Y that might appear in your list,
(a) compare(R, X, Y) will succeed (where R is a fresh variable)
(b) it will bind R to one of =, <, >
(c) R will be = if and only if X == Y
(d) compare(<, X, Y) <=> compare(>, X, Y)
     for all X, Y, Z that might appear in your list,
(e) compare(<, X, Y) and compare(<, Y, Z) => compare(<, X, Z)

If you mix integers and floats in the same sequence it is
astonishingly tricky.  In fact it's astonishingly tricky to
deal with floating point numbers anyway.  Recall that for
IEEE floating point numbers, there are numbers Z, W such that
        X is -Z => X =:= Z but not X == Z   (±0)
        W == W but not W =:= W              (±NaN)
A programming language *cannot* be consistent with the IEEE
floating point standards AND provide a total order on the
floats under the usual symbols.  Historically, that's not the
reason that the term ordering predicates are distinct from the
numeric ordering ones, but it's a lucky accident that they were,
because otherwise we'd have had to break *something*.

Before defining your own num_compare/3 that mixes integers and
floats, or even just floats, make *very* sure that you know
what you are doing.

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Richard O'Keefe]

On 15 Jun 2009, at 3:05 pm, Ulrich Neumerkel wrote:
> Is it only the mixing of integers and floats that is problematic?  If
> so, a floatcompare/3 nd intcompare/3 might make sense?

Floats are the problem.
There there is something especially dubious about comparing
exact numbers (integers in this case) with inexact ones.

The heart of the problem here is that the original poster
knew that 1 =:= 1.0 (they are numerically) equal
and therefore expected them to be compared = using compare/3.

>
> Aren't floats in general not the best candidates for compare/3,
> as equality is problematic?

TERM-equality is not problematic at all.  Two terms are identical
(==) if and only if they are indistinguishable.  Term ordering is
not problematic except for NaNs:
  -infinity @< -finite @< -0.0 @< +0.0 @< +finite @< +infinity
As for NaNs, it doesn't really matter where term ordering puts
them as long as it is consistent.

I say that term ordering is not problematic.
It isn't.  What _is_ problematic (thank you, IEEE 754 committee)
is expecting _any_ total order on floats to match up with < =:= and >.
We MUST distinguish -0.0 \== 0.0 because they are distinguishable
in several IEEE-conformant ways.  But we must ALSO have -0.0 =:= 0.0.

Sorting floats in C is a pain, because you always have to take care
to segregate the NaNs first.  In fact, when sorting floats in C, I
do a first pass to segregate
  - numbers with negative sign, including -0.0
  - numbers with positive sign, including +0.0
  - NaNs
and then I sort the first two halves separately.

_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Simon Strobl]

Hello,

thank you for the interesting discussion. The most straightforward solution for my problem was to convert all my numbers to floats before comparing them. I suppose an analogous solution can be used in the vast majority of cases in which someone has a problem with compare/3. I just think that programmers could find their solutions quicker, if the Swi manual contained a sentence about the difficulties of comparing numbers (or other entities) of different types.

Simon

[Ulrich Neumerkel]

> The most straightforward solution
> for my problem was to convert all my numbers to floats before comparing
> them.

Where do these integers come from?  Why aren't they floats then in the
first place?
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Nicolas Pelletier-3]

Simon,

On Mon, Jun 15, 2009 at 5:03 PM, Simon Strobl<Simon.Strobl@...> wrote:
>
> thank you for the interesting discussion. The most straightforward solution
> for my problem was to convert all my numbers to floats before comparing
> them. I suppose an analogous solution can be used in the vast majority of
> cases in which someone has a problem with compare/3.

A corollary from the above discussion is: as long as you stick with
small integer values, you will get the illusion that float( X )  == X
for X integer.

Here is what I get on this 64 bit machine:

?- X is integer( 1e+23 ), Y is float( X ), X =:= Y.
X = 99999999999999991611392,
Y = 1e+23.

?- X is integer( 1e+22 ), Y is float( X ), X =:= Y.
X = 10000000000000000000000,
Y = 1e+22.

?- X is integer( 1e+22 ), Y is float( X ), X =:= Y, X == Y.
false.

Shocking, isn't it ? 1e+22 is not *that* big a number. So I would
rather think that if I have a problem with compare/3, then it is a
sign I am attempting to compare oranges to apples.

Regards,

--
Nicolas
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog

[Simon Strobl]

Ulrich Neumerkel wrote:

> Where do these integers come from?  Why aren't they floats then in the
> first place?

My program classifies objects (e.g. words). The classification procedure involves assigning scores. Basically, scores are frequencies, i.e. integers. Some frequencies, but not all, must be normalized. The normalization procedure implicitly creates floats.

[Jeff Schultz]

> Ulrich Neumerkel wrote:
> >
> >> Where do these integers come from?  Why aren't they floats then in the
> >> first place?
> >
> >
>
> My program classifies objects (e.g. words). The classification procedure
> involves assigning scores. Basically, scores are frequencies, i.e. integers.
> Some frequencies, but not all, must be normalized. The normalization
> procedure implicitly creates floats.

It's not clear how normalized and non-normalized "frequencies" end up
in the same collection, but, if they do, it really sounds like they
should all be represented as floats.  As pointed out by others, watch
out for integers with no exact SWI float representation, but on the
plus side, it doesn't sound like you have NaN, Inf, -0, or any
negative numbers at all for that matter, so at least the floats will
be easy to compare.


    Jeff Schultz
_______________________________________________
SWI-Prolog mailing list
SWI-Prolog@...
https://mailbox.iai.uni-bonn.de/mailman/listinfo.cgi/swi-prolog