Opened 7 years ago

Last modified 7 years ago

#18383 needs_work enhancement

Coercion and comparison for alternating sign matrices

Reported by: vdelecroix Owned by:
Priority: major Milestone: sage-6.7
Component: combinatorics Keywords:
Cc: Merged in:
Authors: Vincent Delecroix Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: u/tscrim/18383 (Commits, GitHub, GitLab) Commit: 807bc9c27622f1d5a8185626b39d327a1ec8d1eb
Dependencies: Stopgaps:

Status badges

Description

With this this ticket we declare an embedding from the set of alternating sign matrices (sage.combinat.alternating_sign_matrix.AlternatingSignMatrices) to the set of matrices. We also implement comparisons using _cmp_ that will take care of coercions.

Change History (26)

comment:1 Changed 7 years ago by vdelecroix

  • Branch set to u/vdelecroix/18383
  • Commit set to 390e2d7cf57899cde4c7b096ef5b97f0be909574
  • Status changed from new to needs_review

New commits:

390e2d7Trac 18383: coercion/comparison for ASM

comment:2 follow-up: Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_work

We should not remove the rich comparisons as this makes us less python3 compatible. If you want to deal with the comparisons via coercion, then it should be done without using _cmp_/__cmp__.

comment:3 in reply to: ↑ 2 Changed 7 years ago by vdelecroix

  • Status changed from needs_work to needs_review

Replying to tscrim:

We should not remove the rich comparisons as this makes us less python3 compatible. If you want to deal with the comparisons via coercion, then it should be done without using _cmp_/__cmp__.

__richcmp__ does call _cmp_?! Could you explain the problem? No doctest has been removed.

comment:4 follow-up: Changed 7 years ago by tscrim

Because it assumes the existence of a total order (which may not be reasonable for matrices in the future as, IIRC, when they were first implemented, we only had __cmp__ in Python). Also cmp is going away in Python3 and __richcmp__ only calls _cmp_ as a generic fallback. Plus the current implementation already acts as how you're intending it to (which might change as the ASM people might want the comparisons to be the natural lattice and they would need to revert your changes).

comment:5 in reply to: ↑ 4 ; follow-up: Changed 7 years ago by vdelecroix

Replying to tscrim:

Because it assumes the existence of a total order (which may not be reasonable for matrices in the future as, IIRC, when they were first implemented, we only had __cmp__ in Python). Also cmp is going away in Python3 and __richcmp__ only calls _cmp_ as a generic fallback. Plus the current implementation already acts as how you're intending it to (which might change as the ASM people might want the comparisons to be the natural lattice and they would need to revert your changes).

I assumed that there is a total order on -1,0,1. Right. The only things that change with this ticket are:

  1. the embedding ASM -> MatrixSpace
  2. the fact that coercion takes place in comparisons
  3. the fact that cmp(a1,a2) answers something when a1 and a2 are both ASM instead of raising a NotImplementedError.

I will not do anything more complicated as I do not know anything about ASM. If you think that the previous implementation was wrong then open a follow up ticket (and I might possibly close this one as duplicate). If you think that some of the three points above are wrong then please be clearer.

Vincent

comment:6 in reply to: ↑ 5 Changed 7 years ago by tscrim

Replying to vdelecroix:

I assumed that there is a total order on -1,0,1. Right.

However that doesn't make a good ordering on ASM's.

The only things that change with this ticket are:

  1. the embedding ASM -> MatrixSpace

Good.

  1. the fact that coercion takes place in comparisons

This was already done (at least up to comparing the matrices).

  1. the fact that cmp(a1,a2) answers something when a1 and a2 are both ASM instead of raising a NotImplementedError.

This is an indicator of something which we are doing wrong further up the chain, in the sense of being both 2&3 compatible, as rich comparisons should override the behavior of __cmp__ (see the rich comparisons part of http://docs.python.org/2/reference/datamodel.html). Again, cmp and related methods are gone in Python3, so let's not step backwards by removing the rich comparisons.

I will not do anything more complicated as I do not know anything about ASM. If you think that the previous implementation was wrong then open a follow up ticket (and I might possibly close this one as duplicate). If you think that some of the three points above are wrong then please be clearer.

I'm not saying its wrong per-say, but it might carry more meaning than it currently does. I can ask the ASM people what they want, but it's tangential to my main objection that it is removing Python3 compatibility.

comment:7 follow-up: Changed 7 years ago by tscrim

Also #18322 looks like it will fix point 3 without having to use _cmp_.

comment:8 Changed 7 years ago by tscrim

  • Status changed from needs_review to needs_work

comment:9 in reply to: ↑ 7 Changed 7 years ago by vdelecroix

Replying to tscrim:

Also #18322 looks like it will fix point 3 without having to use _cmp_.

Nope. To fit into the new infrastructure of comparison, you need to either implement _cmp_ or _richcmp_. The methods __eq__, __ne__, __lt__, ... will never be called.

comment:10 follow-up: Changed 7 years ago by tscrim

Surely we aren't forcing everything to have a total ordering via a _cmp_ (and are telling people to use cmp to do comparisons)? If so, then we'll never be able to switch to Python3.

comment:11 in reply to: ↑ 10 Changed 7 years ago by vdelecroix

Replying to tscrim:

Surely we aren't forcing everything to have a total ordering via a _cmp_ (and are telling people to use cmp to do comparisons)? If so, then we'll never be able to switch to Python3.

Please, stop talking about Python 3 since Cython is very different from Python from that point of view. To handle comparisons of elements in Sage and if you want the coercion to be involved then you should either implement:

  • _cmp_(self, other) (the simplest option)
  • _richcmp_(self, other, op)

This is a choice for the programmer and he/she can even implement both. I am not forcing anybody to use one or the other, but the first one is by far easier. This is independent of whatever Python version.

The subtle difference that you seem to care about between rich comparisons and cmp does not exists even in Python 2

class A:
    def __init__(self, value):
        self.x = value
    def __lt__(self, other):
        print "LT"
        return self.x < other.x
    def __le__(self, other):
        print "LE"
        return self.x <= other.x
    def __eq__(self, other):
        print "EQ"
        return self.x == other.x
    def __ne__(self, other):
        print "NE"
        return self.x != other.x
    def __ge__(self, other):
        print "GE"
        return self.x >= other.x
    def __gt__(self, other):
        print "GT"
        return self.x > other.x

Then

sage: a = A(1)
sage: b = A(2)
sage: cmp(a,b)
EQ
LT
-1

This difference is just a Cython feature that we are not using much.

comment:12 Changed 7 years ago by vdelecroix

But _cmp_ does necessarily provide a total order... this is true.

comment:13 follow-up: Changed 7 years ago by tscrim

We have to care about Python3 because it is the way going forward. The subtlety has come from us implementing a __cmp__ at the general Element level, which gets called by the cmp first, and then instead of the default Python implementation of checking __eq__ and __lt__, it tries to call _cmp_ and then _richcmp_. This is a subtly caused by the current machinery in Sage. We need a mechanism which falls back to the usual Python rich comparisons for compatibility (although perhaps we need to make a single underscored version to work with coercion, but that is a question for sage-devel and I think there's already discussions about this).

comment:14 in reply to: ↑ 13 ; follow-up: Changed 7 years ago by vdelecroix

Replying to tscrim:

We have to care about Python3 because it is the way going forward. The subtlety has come from us implementing a __cmp__ at the general Element level, which gets called by the cmp first, and then instead of the default Python implementation of checking __eq__ and __lt__, it tries to call _cmp_ and then _richcmp_. This is a subtly caused by the current machinery in Sage. We need a mechanism which falls back to the usual Python rich comparisons for compatibility (although perhaps we need to make a single underscored version to work with coercion, but that is a question for sage-devel and I think there's already discussions about this).

This is not that simple because at the level of the C API __eq__, __lt__ etc does not exist. So there will be a huge difference between extension classes (ie Cython) and Python classes (ie Python). The uniform way that is proposed is precisely to use _cmp_ or _richcmp_ and avoid __eq__, etc.

The fact that there is a global __cmp__ in Element might be a problem but this is rather disjoint from the present ticket: for ASM we want coercion to be involved.

Vincent

comment:15 in reply to: ↑ 14 ; follow-up: Changed 7 years ago by tscrim

Replying to vdelecroix:

Replying to tscrim:

We have to care about Python3 because it is the way going forward. The subtlety has come from us implementing a __cmp__ at the general Element level, which gets called by the cmp first, and then instead of the default Python implementation of checking __eq__ and __lt__, it tries to call _cmp_ and then _richcmp_. This is a subtly caused by the current machinery in Sage. We need a mechanism which falls back to the usual Python rich comparisons for compatibility (although perhaps we need to make a single underscored version to work with coercion, but that is a question for sage-devel and I think there's already discussions about this).

This is not that simple because at the level of the C API __eq__, __lt__ etc does not exist. So there will be a huge difference between extension classes (ie Cython) and Python classes (ie Python). The uniform way that is proposed is precisely to use _cmp_ or _richcmp_ and avoid __eq__, etc.

The uniform way would be to have the generic _richcmp_ default back to using the python __eq__, etc. It may not be simple to implement, but it is the IMO correct way to do things as we should not be making ourselves less Python3 compliant. Plus I thought by having _richcmp_ being a Python method, we could then call the __lt__, or at least use getattr. Moreover, this is only a problem for doing comparisons with cmp, which will be moot once we do switch.

The fact that there is a global __cmp__ in Element might be a problem but this is rather disjoint from the present ticket: for ASM we want coercion to be involved.

It's quite relevant because it is part of your proposal. In the current version of Sage, if the other element is not an ASM, then it lifts itself to the matrix space and does the comparison there (in that it compares against its defining matrix).

comment:16 in reply to: ↑ 15 ; follow-up: Changed 7 years ago by vdelecroix

Replying to tscrim:

Replying to vdelecroix:

Replying to tscrim:

We have to care about Python3 because it is the way going forward. The subtlety has come from us implementing a __cmp__ at the general Element level, which gets called by the cmp first, and then instead of the default Python implementation of checking __eq__ and __lt__, it tries to call _cmp_ and then _richcmp_. This is a subtly caused by the current machinery in Sage. We need a mechanism which falls back to the usual Python rich comparisons for compatibility (although perhaps we need to make a single underscored version to work with coercion, but that is a question for sage-devel and I think there's already discussions about this).

This is not that simple because at the level of the C API __eq__, __lt__ etc does not exist. So there will be a huge difference between extension classes (ie Cython) and Python classes (ie Python). The uniform way that is proposed is precisely to use _cmp_ or _richcmp_ and avoid __eq__, etc.

The uniform way would be to have the generic _richcmp_ default back to using the python __eq__, etc. It may not be simple to implement, but it is the IMO correct way to do things as we should not be making ourselves less Python3 compliant. Plus I thought by having _richcmp_ being a Python method, we could then call the __lt__, or at least use getattr. Moreover, this is only a problem for doing comparisons with cmp, which will be moot once we do switch.

We can not do that. The method __richcmp__ (and hence _richcmp_) is not used at all if __eq__, __lt__, etc are implemented in a Python class.

The fact that there is a global __cmp__ in Element might be a problem but this is rather disjoint from the present ticket: for ASM we want coercion to be involved.

It's quite relevant because it is part of your proposal. In the current version of Sage, if the other element is not an ASM, then it lifts itself to the matrix space and does the comparison there (in that it compares against its defining matrix).

Do you have an example involving rich comparisons that differ?

Vincent

comment:17 in reply to: ↑ 16 ; follow-up: Changed 7 years ago by tscrim

Replying to vdelecroix:

Replying to tscrim:

The uniform way would be to have the generic _richcmp_ default back to using the python __eq__, etc. It may not be simple to implement, but it is the IMO correct way to do things as we should not be making ourselves less Python3 compliant. Plus I thought by having _richcmp_ being a Python method, we could then call the __lt__, or at least use getattr. Moreover, this is only a problem for doing comparisons with cmp, which will be moot once we do switch.

We can not do that. The method __richcmp__ (and hence _richcmp_) is not used at all if __eq__, __lt__, etc are implemented in a Python class.

For rich comparisons, yes. However for cmp, the code path currently completely bypasses the rich comparisons because it calls __cmp__ (which calls _cmp which calls _cmp_ and errors out).

The fact that there is a global __cmp__ in Element might be a problem but this is rather disjoint from the present ticket: for ASM we want coercion to be involved.

It's quite relevant because it is part of your proposal. In the current version of Sage, if the other element is not an ASM, then it lifts itself to the matrix space and does the comparison there (in that it compares against its defining matrix).

Do you have an example involving rich comparisons that differ?

I'm not sure what you're asking for. If you do an equality comparison between an ASM and a regular matrix, then the comparison lifts the ASM to a matrix and then does the comparison.

sage: ASM = AlternatingSignMatrices(3)
sage: x = ASM[3]
sage: x == x._matrix
True

Otherwise it returns False, which is a fair thing to do since these are combinatorial objects, not honest matrices (or 2D arrays). (I think I misread the code when I first looked.) I'm actually becoming more convinced that the inequality comparisons should be done in the corresponding lattices. Is this perhaps what you're asking about?

sage: ASM[1] < ASM[3]   # Is True in the latice
False

comment:18 in reply to: ↑ 17 ; follow-up: Changed 7 years ago by vdelecroix

Replying to tscrim:

Replying to vdelecroix:

Replying to tscrim:

The uniform way would be to have the generic _richcmp_ default back to using the python __eq__, etc. It may not be simple to implement, but it is the IMO correct way to do things as we should not be making ourselves less Python3 compliant. Plus I thought by having _richcmp_ being a Python method, we could then call the __lt__, or at least use getattr. Moreover, this is only a problem for doing comparisons with cmp, which will be moot once we do switch.

We can not do that. The method __richcmp__ (and hence _richcmp_) is not used at all if __eq__, __lt__, etc are implemented in a Python class.

For rich comparisons, yes. However for cmp, the code path currently completely bypasses the rich comparisons because it calls __cmp__ (which calls _cmp which calls _cmp_ and errors out).

This has been fixed in #18322.

The fact that there is a global __cmp__ in Element might be a problem but this is rather disjoint from the present ticket: for ASM we want coercion to be involved.

It's quite relevant because it is part of your proposal. In the current version of Sage, if the other element is not an ASM, then it lifts itself to the matrix space and does the comparison there (in that it compares against its defining matrix).

Do you have an example involving rich comparisons that differ?

I'm not sure what you're asking for.

I wanted an example of a comparison that is different before and after my branch.

comment:19 in reply to: ↑ 18 ; follow-up: Changed 7 years ago by tscrim

Replying to vdelecroix:

Replying to tscrim:

For rich comparisons, yes. However for cmp, the code path currently completely bypasses the rich comparisons because it calls __cmp__ (which calls _cmp which calls _cmp_ and errors out).

This has been fixed in #18322.

If that does have the rich comparisons in the code path, then it should fix the issue without having to define a _cmp_.

Do you have an example involving rich comparisons that differ?

I'm not sure what you're asking for.

I wanted an example of a comparison that is different before and after my branch.

Here is one:

sage: ASM = AlternatingSignMatrices(3)
sage: x = ASM[3]
sage: x
[ 0  1  0]
[ 1 -1  1]
[ 0  1  0]
sage: x < matrix.identity(3)   # True with this branch
False

and it is because the coercion framework gets involved. Although ASM's only have the inequality comparisons for plotting due to the digraph calling sorted in vertices() which fails (#15372, which was a quick hack around the problem IMO) rather than just choosing some order. So the inequality comparisons are not mathematically defined as-is (even for matrices IMO, where they are just considered as 2-dim arrays). So now I'm completely convinced they should be rewritten to use the lattice.

comment:20 in reply to: ↑ 19 Changed 7 years ago by vdelecroix

Replying to tscrim:

I understand your objections but I will not do anything like that. So I propose to close this ticket as a won't fix.

Vincent

comment:21 follow-up: Changed 7 years ago by tscrim

I would like to include your changes adding the coercion and the _matrix_ method though. I can separate this out if you want.

comment:22 in reply to: ↑ 21 Changed 7 years ago by vdelecroix

Replying to tscrim:

I would like to include your changes adding the coercion and the _matrix_ method though. I can separate this out if you want.

No no no. Let us do it here. I can provide a commit where I do not modify the comparisons. Just provide the coercion. Is that ok?

comment:23 follow-up: Changed 7 years ago by tscrim

I think we had a miscommunication, by separate out I meant of your previous commit and do it here, not a separate ticket. I was asking if you wanted me to do such a commit (on a new branch).

comment:24 in reply to: ↑ 23 Changed 7 years ago by vdelecroix

Replying to tscrim:

I think we had a miscommunication, by separate out I meant of your previous commit and do it here, not a separate ticket. I was asking if you wanted me to do such a commit (on a new branch).

I thought you want me to replace my commit by another one. What you propose is even simpler for me, so it is even better...

Vincent

comment:25 Changed 7 years ago by tscrim

  • Branch changed from u/vdelecroix/18383 to u/tscrim/18383
  • Commit changed from 390e2d7cf57899cde4c7b096ef5b97f0be909574 to 807bc9c27622f1d5a8185626b39d327a1ec8d1eb
  • Reviewers set to Travis Scrimshaw
  • Status changed from needs_work to needs_review

If you could just double check that I pulled out everything correctly, then we can set this to positive review. I'll also do followup tickets for the change for the plotting issue and ordering of the ASM's.


New commits:

807bc9cImplementing coercion from ASM to matrices.

comment:26 Changed 7 years ago by jdemeyer

  • Status changed from needs_review to needs_work

I really don't like this solution because whether or not coercion is used depends on the order of the arguments (A < B does something completely different than B > A). You cannot say that you want coercion and then not use coercion for comparisons.

sage: A = AlternatingSignMatrices(3)[1]
sage: A < B
False
sage: B > A
True

I actually think that you don't want coercion for ASM's. You don't want to consider them as matrices with extra structure, you want to consider them as mathematical objects which happen to be written as a matrix.

Note: See TracTickets for help on using tickets.