Opened 8 years ago
Last modified 8 years ago
#18383 needs_work enhancement
Coercion and comparison for alternating sign matrices
Reported by:  Vincent Delecroix  Owned by:  

Priority:  major  Milestone:  sage6.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: 
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 8 years ago by
Branch:  → u/vdelecroix/18383 

Commit:  → 390e2d7cf57899cde4c7b096ef5b97f0be909574 
Status:  new → needs_review 
comment:2 followup: 3 Changed 8 years ago by
Status:  needs_review → 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 Changed 8 years ago by
Status:  needs_work → 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 followup: 5 Changed 8 years ago by
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 followup: 6 Changed 8 years ago by
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). Alsocmp
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:
 the embedding
ASM > MatrixSpace
 the fact that coercion takes place in comparisons
 the fact that
cmp(a1,a2)
answers something whena1
anda2
are bothASM
instead of raising aNotImplementedError
.
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 Changed 8 years ago by
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:
 the embedding
ASM > MatrixSpace
Good.
 the fact that coercion takes place in comparisons
This was already done (at least up to comparing the matrices).
 the fact that
cmp(a1,a2)
answers something whena1
anda2
are bothASM
instead of raising aNotImplementedError
.
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 persay, 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 followup: 9 Changed 8 years ago by
Also #18322 looks like it will fix point 3 without having to use _cmp_
.
comment:8 Changed 8 years ago by
Status:  needs_review → needs_work 

comment:9 Changed 8 years ago by
comment:10 followup: 11 Changed 8 years ago by
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 Changed 8 years ago by
Replying to tscrim:
Surely we aren't forcing everything to have a total ordering via a
_cmp_
(and are telling people to usecmp
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:13 followup: 14 Changed 8 years ago by
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 sagedevel and I think there's already discussions about this).
comment:14 followup: 15 Changed 8 years ago by
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 generalElement
level, which gets called by thecmp
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 sagedevel 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 followup: 16 Changed 8 years ago by
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 generalElement
level, which gets called by thecmp
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 sagedevel 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__
inElement
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 followup: 17 Changed 8 years ago by
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 generalElement
level, which gets called by thecmp
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 sagedevel 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 usegetattr
. Moreover, this is only a problem for doing comparisons withcmp
, 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__
inElement
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 followup: 18 Changed 8 years ago by
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 usegetattr
. Moreover, this is only a problem for doing comparisons withcmp
, 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__
inElement
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 followup: 19 Changed 8 years ago by
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 usegetattr
. Moreover, this is only a problem for doing comparisons withcmp
, 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__
inElement
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 followup: 20 Changed 8 years ago by
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 asis (even for matrices IMO, where they are just considered as 2dim arrays). So now I'm completely convinced they should be rewritten to use the lattice.
comment:20 Changed 8 years ago by
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 followup: 22 Changed 8 years ago by
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 Changed 8 years ago by
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 followup: 24 Changed 8 years ago by
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 Changed 8 years ago by
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 8 years ago by
Branch:  u/vdelecroix/18383 → u/tscrim/18383 

Commit:  390e2d7cf57899cde4c7b096ef5b97f0be909574 → 807bc9c27622f1d5a8185626b39d327a1ec8d1eb 
Reviewers:  → Travis Scrimshaw 
Status:  needs_work → 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:
807bc9c  Implementing coercion from ASM to matrices.

comment:26 Changed 8 years ago by
Status:  needs_review → 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.
New commits:
Trac 18383: coercion/comparison for ASM