Comparison between str and sage.rings.integer.Integer depends on whether doctest called directly or via Makefile

[Clemens Heuberger]

Can anyone help me understanding the following behaviour:

A doctest (0 < 'I'; see below) passes when called directly and fails when called
via a Makefile, reproduced under sage 6.3.beta6, 6.2, 5.10 (running Linux Mint).

As pointed out in
https://groups.google.com/d/topic/sage-support/KNSzU0JpZgQ/discussion ,
comparison between str and Integer falls back to comparison between the types.

Does that simply mean that cmp(str, sage.rings.integer.Integer) is random?

Is the behaviour reproducible on other systems?

This problem turned up when trying to find out why Volker Braun has problems
with doctests in #16580 which I cannot reproduce. There, we need to somehow sort
transitions in a finite state machine; the order itself does not really matter,
but for doctests, it is important to always have the same order.


$ cat test-cmp.sage
"""
::
sage: a = 0
sage: b = 'I'
sage: type(a)
<type 'sage.rings.integer.Integer'>
sage: type(b)
<type 'str'>
sage: cmp(type(a), type(b))
-1
sage: a < b
True
"""
$ cat Makefile

doctest:
sage -t test-cmp.sage

$ LANG=C make
sage -t test-cmp.sage
Running doctests with ID 2014-07-22-18-46-45-0e337b53.
Doctesting 1 file.
sage -t test-cmp.sage
**********************************************************************
File "test-cmp.sage", line 9, in test-cmp
Failed example:
cmp(type(a), type(b))
Expected:
-1
Got:
1
**********************************************************************
File "test-cmp.sage", line 11, in test-cmp
Failed example:
a < b
Expected:
True
Got:
False
**********************************************************************
1 item had failures:
2 of 7 in test-cmp
[6 tests, 2 failures, 0.00 s]
----------------------------------------------------------------------
sage -t test-cmp.sage # 2 doctests failed
----------------------------------------------------------------------
Total time for all tests: 0.0 seconds
cpu time: 0.0 seconds
cumulative wall time: 0.0 seconds
make: *** [doctest] Error 1

$ sage -t test-cmp.sage
Running doctests with ID 2014-07-22-18-47-10-577db6a3.
Doctesting 1 file.
sage -t test-cmp.sage
[6 tests, 0.00 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
Total time for all tests: 0.0 seconds
cpu time: 0.0 seconds
cumulative wall time: 0.0 seconds

[Nils Bruin]

On Tuesday, July 22, 2014 9:57:13 AM UTC-7, Clemens Heuberger wrote:

Does that simply mean that cmp(str, sage.rings.integer.Integer) is random?

My guess is that it would be. However, I have not found a type on my system that compares as less than str and I haven't found a type that has id(str) > id(<other type) [and I expect that this is the comparison done], and this is understandable: "str" is one of the most fundamental types in python, because it's used as keys in dicts for any other type (including itself). So I'd expect it to sit somewhere very low in memory. Would you be working on a 32-bit system by any chance? There it's quite conceivable that an id ends up being a negative number once your addresses have the most significant bit set.
 

Is the behaviour reproducible on other systems?

Not on my 64 bit machine.
 

This problem turned up when trying to find out why Volker Braun has problems
with doctests in #16580 which I cannot reproduce. There, we need to somehow sort
transitions in a finite state machine; the order itself does not really matter,
but for doctests, it is important to always have the same order.

It's not important to have the object itself ordered; you should just make sure that the string that is doctested against is sorted. So rather than doctesting the, say, dictionary, you doctest a sorted list of items from the dict, i.e.,

sage: T=dict( (a^2,a) for a in range(10))
sage: T # random
{0: 0, 1: 1, 4: 2, 9: 3, 16: 4, 25: 5, 36: 6, 49: 7, 64: 8, 81: 9}
sage: sorted( T.items(), key = str)
[(0, 0),
 (1, 1),
 (16, 4),
 (25, 5),
 (36, 6),
 (4, 2),
 (49, 7),
 (64, 8),
 (81, 9),
 (9, 3)]

This sorts the items according to their str representations, so the sort only compares strings with strings, which has a well-defined (lexicographical) result. Don't hobble your implementation with arbitrary fixed orders just to satisfy a doctest requirement. Instead, write the doctest to take care of possible arbitrariness.

[Clemens Heuberger]

Am 2014-07-22 20:34, schrieb Nils Bruin:
> Would you be working on a 32-bit system by any chance?

no, 64-bit system.

> Is the behaviour reproducible on other systems?
>
> Not on my 64 bit machine.

May I ask on which system?

My problem is that I need to sort anyway---there, the exact order does not
matter, but it does matter to distinguish between 0 and '0' because of a
follow-up groupby. So I cannot use key=str there (and that would be hobbling
according your outlined policy).

The closest I could do to follow your suggestion would be a doctest
for line in sorted(latex(F).split("\n"))
print line
and I'd hate to do that (compared to latex(F), as it is now): it is ugly
and would result in a code which is not compilable by latex.

But if cmp(type(0), type('I')) is indeed random: why not using str at this
place in sage.structure.element.Element._richcmp ? (and see what doctests break
then)?

[Nils Bruin]

On Tuesday, July 22, 2014 11:51:29 AM UTC-7, Clemens Heuberger wrote:

May I ask on which system?

Fedora 19 x86_64. I tried your makefile trick and I got consistent results, so I haven't been able to nudge sage or python into the comparison behaviour you described (for any type, really). Since modern systems try to randomize the memory layout of executables, it's very well possible that you're just observing a rare event.
 

My problem is that I need to sort anyway---there, the exact order does not
matter, but it does matter to distinguish between 0 and '0' because of a
follow-up groupby.

Then you need to make sure that your key-space has an ordering. That means you should not be using both 0 and '0'. Sage tried to have "universal ordering" of all objects, but I think by now it's recognized that this was misguided. It seems to be not possible to have a "<" that agrees with mathematical intuition in cases where there is an ordering and is consistent across the whole system. Python used to try to have universal comparison (which is nice because that meant arbitrary lists could be sorted), but this was abandoned for complex numbers and is completely abandoned in Python 3.0 (where comparison tends to raise an exception for incompatible arguments).
 

So I cannot use key=str there (and that would be hobbling  according your outlined policy).

Indeed, I would not suggest putting any "sorted(... , key = str )" *in the code*, but in doctests it would be fine. If you want '0' to sort differently from 0, you might try "sorted( ..., key = repr)" instead?

The closest I could do to follow your suggestion would be a doctest
        for line in sorted(latex(F).split("\n"))
            print line

Do you want to doctest the "latex" routine? and do you need F to have a well-defined ordering only to be able to doctest "latex(F)"? In that case our doctest procedure is broken. I'd solve that by putting a "#random" on the thing or by putting "..." wildcards in the output template to test some of the non-varying bits of the output (in particular, that it doesn't produce an error).
 

But if cmp(type(0), type('I')) is indeed random: why not using str at this
place in sage.structure.element.Element._richcmp ? (and see what doctests break
then)?

Because that's fixing something that's very broken already. If anything, we should be throwing an exception when it comes to this. I'm sure we'll slowly get rid of the universal ordering attempt eventually, perhaps if/when we transition to Python 3, since there it's not expected anyway. There comparing types indeed raises an exception.

[Volker Braun]

There is no coercion from string and Integer to a common structure. That should be obvious, but we can also check it explicitly:

sage: cm = get_coercion_model()

sage: cm.explain('i', ZZ(0), operator.eq)

Left operand is not Sage element, will try _sage_.

Unknown result parent.

Hence the comparison is by memory position, which is essentially random (and very much platform-dependent).