Opened 8 years ago
Closed 3 months ago
#17965 closed defect (fixed)
Uniformize the API to compute the inverse of an element
Reported by:  Nicolas M. Thiéry  Owned by:  

Priority:  major  Milestone:  sage9.8 
Component:  categories  Keywords:  
Cc:  Franco Saliola, Vincent Delecroix, Simon King, Samuel Lelièvre, Travis Scrimshaw  Merged in:  
Authors:  Frédéric Chapoton  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  312a91d (Commits, GitHub, GitLab)  Commit:  312a91d4f327802ca1e6d48975cd1d221128833e 
Dependencies:  Stopgaps: 
Description (last modified by )
Some classes in Sage implement the inverse of an element through the inverse method:
mistral/opt/sage/src/sage>grep "def inverse(" **/*.py algebras/finite_dimensional_algebras/finite_dimensional_algebra_element.py: def inverse(self): algebras/iwahori_hecke_algebra.py: def inverse(self): categories/coxeter_groups.py: def inverse(self): combinat/affine_permutation.py: def inverse(self): combinat/permutation.py: def inverse(self): combinat/tableau_tuple.py: def inverse(self,k): crypto/classical_cipher.py: def inverse(self): crypto/classical_cipher.py: def inverse(self): crypto/classical_cipher.py: def inverse(self): crypto/classical_cipher.py: def inverse(self): dynamics/interval_exchanges/iet.py: def inverse(self): groups/abelian_gps/element_base.py: def inverse(self): groups/abelian_gps/values.py: def inverse(self): groups/affine_gps/group_element.py: def inverse(self): modules/matrix_morphism.py: def inverse(self): rings/number_field/class_group.py: def inverse(self): rings/universal_cyclotomic_field/universal_cyclotomic_field.py: def inverse(self): schemes/elliptic_curves/formal_group.py: def inverse(self, prec=20): schemes/elliptic_curves/weierstrass_transform.py: def inverse(self):
Some other through the __invert__
method:
mistral/opt/sage/src/sage>grep "def __invert__(" **/*.py categories/algebras_with_basis.py: def __invert__(self): categories/magmas.py: def __invert__(self): categories/modules_with_basis.py: def __invert__(self): categories/modules_with_basis.py: def __invert__(self): combinat/combinatorial_algebra.py: def __invert__(self): combinat/sf/dual.py: def __invert__(self): combinat/species/generating_series.py: def __invert__(self): groups/indexed_free_group.py: def __invert__(self): groups/indexed_free_group.py: def __invert__(self): groups/matrix_gps/group_element.py: def __invert__(self): groups/raag.py: def __invert__(self): libs/coxeter3/coxeter_group.py: def __invert__(self): logic/boolformula.py: def __invert__(self): misc/sage_input.py: def __invert__(self): modular/dirichlet.py: def __invert__(self): modular/local_comp/smoothchar.py: def __invert__(self): modules/matrix_morphism.py: def __invert__(self): rings/continued_fraction.py: def __invert__(self): rings/finite_rings/element_ext_pari.py: def __invert__(self): rings/function_field/function_field_ideal.py: def __invert__(self): rings/infinity.py: def __invert__(self): rings/multi_power_series_ring_element.py: def __invert__(self): rings/number_field/morphism.py: def __invert__(self): rings/number_field/number_field_ideal.py: def __invert__(self): rings/number_field/number_field_ideal_rel.py: def __invert__(self): rings/pari_ring.py: def __invert__(self): rings/polynomial/polynomial_quotient_ring_element.py: def __invert__(self): rings/qqbar.py: def __invert__(self): rings/quotient_ring_element.py: def __invert__(self): rings/universal_cyclotomic_field/universal_cyclotomic_field.py: def __invert__(self): sandpiles/sandpile.py: def __invert__(self): schemes/elliptic_curves/heegner.py: def __invert__(self): schemes/elliptic_curves/height.py: def __invert__(self): schemes/elliptic_curves/weierstrass_morphism.py: def __invert__(self): schemes/elliptic_curves/weierstrass_morphism.py: def __invert__(self): schemes/hyperelliptic_curves/monsky_washnitzer.py: def __invert__(self): structure/factorization.py: def __invert__(self):
Usually they provide a crosslink so that __invert__
and
inverse
are equivalent, but this is done on a case by case bases,
so of course such links are missing here and there:
sage: ~AA(sqrt(~2)) 1.414213562373095? sage: AA(sqrt(~2)).inverse() ... AttributeError: 'AlgebraicReal' object has no attribute 'inverse'
sage: R.<u,v,w> = QQ[] sage: f = EllipticCurve_from_cubic(u^3 + v^3 + w^3, [1,1,0], morphism=True) sage: f.inverse() Scheme morphism: ... sage: ~f ... TypeError: bad operand type for unary ~: 'WeierstrassTransformationWithInverse_class'
Shall we change the code to systematically implement __invert__
as
per Python's convention, and then implement the cross link inverse
> __invert__
once for all high up in the class hierarchy,
typically in Magmas.ElementMethods
?
Caveat: this won't cover all cases since we have invertible elements that don't belong to a magma; e.g. a isomorphisms between two different parents; so it will still be necessary to handle a couple special cases by hand.
See also comment about __inverse__
in
sage.categories.coxeter_groups.py around line 699.
Note: the default implementation ~f = 1/f provided by Element should
probably be implemented in Monoids.ElementMethods
; see also #17692.
Note: the qqbar classes also implement an invert
method, but that's
for a slightly different use case. So we may, or not, want to make
this uniform too. invert
does not fit Sage's usual verb/noun
convention since it's a verb while it is not inplace.
Change History (59)
comment:1 Changed 8 years ago by
Description:  modified (diff) 

comment:2 Changed 2 years ago by
Authors:  → Frédéric Chapoton 

Branch:  → u/chapoton/17965 
Commit:  → 99d9b6cbb562c87e87ca0fc2a6465b387e486157 
Status:  new → needs_review 
comment:3 Changed 2 years ago by
Commit:  99d9b6cbb562c87e87ca0fc2a6465b387e486157 → 1a1ec14fcae40bc98284b74ef3a2d3d5e55461a6 

Branch pushed to git repo; I updated commit sha1. New commits:
1a1ec14  fix some details

comment:4 Changed 2 years ago by
In general I think unifying this is a good idea. Something to keep in mind is that __invert__
will not show up in the documentation, by default. If in some cases there are extensive examples, it could be added to the documentation using automethod
, though. Probably this is not needed for most of the elements, but in #29723 (inverses of ring homomorphisms) this is the reason why I linked __invert__
to inverse
.
comment:5 Changed 2 years ago by
Commit:  1a1ec14fcae40bc98284b74ef3a2d3d5e55461a6 → 9d5692d26c4bf8ad4aa8eb1a9f2cbaab5f35b842 

Branch pushed to git repo; I updated commit sha1. New commits:
9d5692d  fix some doctests in polynomial quotient rings

comment:6 Changed 2 years ago by
Milestone:  sage6.6 → sage9.2 

comment:7 Changed 2 years ago by
Commit:  9d5692d26c4bf8ad4aa8eb1a9f2cbaab5f35b842 → fbc929ef8a01b017641838c47287e141ea96f8f4 

Branch pushed to git repo; I updated commit sha1. New commits:
fbc929e  some pycodestyle details (breaking some lines after : and ;)

comment:8 Changed 2 years ago by
Commit:  fbc929ef8a01b017641838c47287e141ea96f8f4 → 2962668d234c07498c652c66f8b2de44479dcd21 

Branch pushed to git repo; I updated commit sha1. New commits:
2962668  fix one wrong use of parent

comment:9 Changed 2 years ago by
oh, boy, now with an infinite loop in
sage t long warnlong 61.5 src/sage/monoids/free_monoid_element.py
comment:10 Changed 2 years ago by
Status:  needs_review → needs_work 

comment:11 Changed 2 years ago by
Commit:  2962668d234c07498c652c66f8b2de44479dcd21 → 5e7e19afded220ad7e88b6362e7f98448a46df04 

comment:12 Changed 2 years ago by
Milestone:  sage9.2 → sage9.3 

comment:13 Changed 2 years ago by
Commit:  5e7e19afded220ad7e88b6362e7f98448a46df04 → dc2e65f80dbd67279f37e07f24b861c0cc7d7e27 

Branch pushed to git repo; I updated commit sha1. New commits:
dc2e65f  Merge branch 'u/chapoton/17965' in 9.3.b0

comment:14 Changed 2 years ago by
Commit:  dc2e65f80dbd67279f37e07f24b861c0cc7d7e27 → bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68 

comment:15 Changed 2 years ago by
I am thinking to move the "Inverse" axioms from magmas to monoids.
Because the notion of inverse does not really make sense in magmas, where left and right inverses can be different.
src/sage/categories/magmas.py: class Inverse(CategoryWithAxiom):
comment:16 Changed 2 years ago by
We may eventually need to have weaker axioms LeftInverses? and RightInverses?. But is there an inconvenient in having an axiom that states the existence of both a left and right inverse that coïncide?
comment:17 Changed 2 years ago by
Hé, salut. J'essaye juste de démeler la situation, et j'ai une boucle infinie magma>monoid>magma etc etc
comment:18 Changed 2 years ago by
Salut Frédéric :)
Ah I see; things like this indeed happen, though hopefully there is a way out. If it can help, we could have a live chat about it, though not before Tuesday.
Amitiés,
comment:19 Changed 22 months ago by
Milestone:  sage9.3 → sage9.4 

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.
comment:20 Changed 17 months ago by
Milestone:  sage9.4 → sage9.5 

Setting a new milestone for this ticket based on a cursory review.
comment:21 Changed 12 months ago by
Milestone:  sage9.5 → sage9.6 

comment:22 Changed 8 months ago by
Milestone:  sage9.6 → sage9.7 

comment:23 Changed 7 months ago by
Commit:  bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68 → a4f176d870fb79a8a82a7bfb7b5c24b6d302e947 

Branch pushed to git repo; I updated commit sha1. New commits:
a4f176d  Merge branch 'u/chapoton/17965' in 9.7.b0

comment:24 Changed 7 months ago by
Commit:  a4f176d870fb79a8a82a7bfb7b5c24b6d302e947 → b5402d06f7a69f2580d7120cb760d199648046d6 

Branch pushed to git repo; I updated commit sha1. New commits:
b5402d0  fix typos in errors

comment:25 Changed 6 months ago by
Commit:  b5402d06f7a69f2580d7120cb760d199648046d6 → e092bef62df70a3dd3144318aa65e67db2da828a 

Branch pushed to git repo; I updated commit sha1. New commits:
e092bef  Merge branch 'u/chapoton/17965' in 9.7.b1

comment:26 Changed 6 months ago by
Cc:  Samuel Lelièvre added 

Summary:  Uniformization of the API to compute the inverse of an element. → Uniformize the API to compute the inverse of an element 
comment:27 Changed 3 months ago by
Commit:  e092bef62df70a3dd3144318aa65e67db2da828a → de510a5732c108d8f916857d9e7af3f8b50754a5 

comment:28 Changed 3 months ago by
Commit:  de510a5732c108d8f916857d9e7af3f8b50754a5 → 0e19786c4715fa582ec87121592595626c4a56ec 

Branch pushed to git repo; I updated commit sha1. New commits:
0e19786  add doctest

comment:29 Changed 3 months ago by
almost ready to go. I hope that somebody will accept to review this longawaited ticket.
comment:30 Changed 3 months ago by
Commit:  0e19786c4715fa582ec87121592595626c4a56ec → 24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6 

Branch pushed to git repo; I updated commit sha1. New commits:
24b88a5  fix doc

comment:31 Changed 3 months ago by
Cc:  Travis Scrimshaw added 

Status:  needs_work → needs_review 
and the patchbot is now green ! comments welcome
comment:32 Changed 3 months ago by
+ def inverse(self): + """ + Return the inverse of ``self``. + + This an alias for inversion, defined in ``__invert__``. +
"is" is missing
comment:34 Changed 3 months ago by
Commit:  24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6 → b6a5773fc8c6b861150dc9e03d241ddf41741c24 

Branch pushed to git repo; I updated commit sha1. New commits:
b6a5773  fix typo

comment:35 Changed 3 months ago by
I am not so sure about this question about documentation. It is true that the doc inside __invert__
will be hidden from view.
comment:36 followup: 38 Changed 3 months ago by
I don't think too many people are going to be looking at the documentation of __invert__
or inverse()
as that is generally pretty clear.
That being said, I am not really a fan of putting technical implementation details in public documentation:
 This is an alias for inversion, defined in ``__invert__``. + This is an alias for inversion, which can be invoked by ``~x`` + for an instance ``x``.   Element classes should implement ``__invert__`` only.
I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.
What about for additive monoids? Perhaps we need to add "multiplicative" to the documentation above.
I am not sure how I feel about removing the generic 1 / self
for inverse in Element
. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?
comment:37 Changed 3 months ago by
Commit:  b6a5773fc8c6b861150dc9e03d241ddf41741c24 → e08cd7a4e9fb5d6492e8a611040dd562bdddf6cb 

comment:38 followup: 39 Changed 3 months ago by
Replying to Travis Scrimshaw:
I don't think too many people are going to be looking at the documentation of
__invert__
orinverse()
as that is generally pretty clear.
I agree on that point.
That being said, I am not really a fan of putting technical implementation details in public documentation:
 This is an alias for inversion, defined in ``__invert__``. + This is an alias for inversion, which can be invoked by ``~x`` + for an instance ``x``.   Element classes should implement ``__invert__`` only.I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.
I have changed that according to your suggestion. Implementation detail is now a comment in the code.
What about for additive monoids? Perhaps we need to add "multiplicative" to the documentation above.
I have no idea. I thought that there was another category for additive monoids ?
I am not sure how I feel about removing the generic
1 / self
for inverse inElement
. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?
This is indeed a delicate point. Having both that and the division defined using product by the inverse easily leads to infinite loops. It seems safer to break the possibility of this kind of loop.
comment:39 Changed 3 months ago by
Replying to Frédéric Chapoton:
Replying to Travis Scrimshaw:
That being said, I am not really a fan of putting technical implementation details in public documentation:
 This is an alias for inversion, defined in ``__invert__``. + This is an alias for inversion, which can be invoked by ``~x`` + for an instance ``x``.   Element classes should implement ``__invert__`` only.I would probably put the last part as a code comment. However, in this case, because it is specifications for implementors, it could be okay. The change in the first part is to indicate how a more casual user can use this.
I have changed that according to your suggestion. Implementation detail is now a comment in the code.
Thank you.
What about for additive monoids? Perhaps we need to add "multiplicative" to the documentation above.
I have no idea. I thought that there was another category for additive monoids ?
There is, but we try to keep the two somewhat consistent. There is also the join category, where "inverse" becomes slightly vague.
I am not sure how I feel about removing the generic
1 / self
for inverse inElement
. Is that implemented in one of the categories? Should we be worried about a slowdown with it no longer being Cython?This is indeed a delicate point. Having both that and the division defined using product by the inverse easily leads to infinite loops. It seems safer to break the possibility of this kind of loop.
I would rather have the infinite loop (which there are protections against) and leave the choice of implementation to the developer. If it does go into an infinite loop, it is indicating that something needs to be implemented (unfortunately, I don't know a good mechanism for checking this). At the very least it is a backwards incompatible change.
comment:40 Changed 3 months ago by
Commit:  e08cd7a4e9fb5d6492e8a611040dd562bdddf6cb → d0fbe93d4de3b38b40034b4c1743399f37393a59 

Branch pushed to git repo; I updated commit sha1. New commits:
d0fbe93  tweak doc again

comment:41 Changed 3 months ago by
I see no way out other than removing the invert
in element.pyx. It is not a cdef method there, by the way. I agree that this is rather backwardincompatible..
comment:42 Changed 3 months ago by
But basically you want to remove the 1 / self
default implementation to never have an infinite loop? In particular, if we had some sort of @implement_this_or_that
type decorator, you would be fine with it? Or is there a technical issue with having it defined in the category?
I am particularly worried about someone could have implemented an algebraic structure just through _div_
, and there are things in Sage that use ~x
that are subsequently being called with this algebraic structure. I could imagine something like this for polynomials (without going to the fraction field).
comment:43 Changed 3 months ago by
Branch:  u/chapoton/17965 → public/ticket17965experiment 

Commit:  d0fbe93d4de3b38b40034b4c1743399f37393a59 → 312a91d4f327802ca1e6d48975cd1d221128833e 
here is an experimental branch with the default inverse reactivated, let us see what happens.
New commits:
312a91d  reintroduce default inversion

comment:46 Changed 3 months ago by
the failure is #33161 ; the tests in this file pass with other random seeds
comment:47 Changed 3 months ago by
I am basically ready to flip the switch. The last thing I probably would like (although not fully convinced) is to have an alias inverse = __invert__
in the classes that implemented an inverse
in order to keep the documentation there visible.
comment:48 Changed 3 months ago by
But this would basically contradict the fact that there is a unique global alias that maps inverse
to __invert__
?
comment:49 Changed 3 months ago by
It isn't an alias in the Python sense. However, I didn't think your proposal said there should be a unique such redirect.
I don't see any advantages of trying to impose that (it isn't really enforceable either). I think if we are consistent about using __invert__
, then we won't get a user saying "I get to chose which one I want to do" (not to mention generic division would not work). On the other hand, I don't think this documentation is generally useful though, and not having it would mean that there is a near 0% chance of confusion.
comment:50 Changed 3 months ago by
Sorry, I am now confused and not sure what you would like me to change.
comment:51 Changed 3 months ago by
For example, in algebras/hecke_algebras/ariki_koike_algebra.py
, you are removing the inverse
function. So it will no longer appear in the documentation and x.inverse?
will be the generic documentation. I am think is adding a
inverse = __invert__
alias there so the documentation won't change.
Anyways, it sounds like you don't really like it and I wasn't convinced of how useful it would be, so we can move on.
comment:53 Changed 3 months ago by
Reviewers:  → Travis Scrimshaw 

Status:  needs_review → positive_review 
Yes.
comment:55 followup: 56 Changed 3 months ago by
#17692 is independent of these changes (and the main proposal has already been done somewhere else).
The issue of whether __invert__
and the (very embedded) ~x
should not be bitwise inverse (compare ~int(5)
to ~Integer(5)
) is not impacted by this change (other than it might be slightly more work to make such a change, but it is now at least applied uniformly, so it is less likely we miss something IMO).
comment:56 followup: 57 Changed 3 months ago by
Replying to Travis Scrimshaw:
#17692 is independent of these changes (and the main proposal has already been done somewhere else).
The issue of whether
__invert__
and the (very embedded)~x
should not be bitwise inverse (compare~int(5)
to~Integer(5)
) is not impacted by this change
No, the bitwise complement question is not the topic of #17692 (it is only mentioned in the very last comment)
comment:57 Changed 3 months ago by
Replying to Matthias Köppe:
Replying to Travis Scrimshaw:
#17692 is independent of these changes (and the main proposal has already been done somewhere else).
The issue of whether
__invert__
and the (very embedded)~x
should not be bitwise inverse (compare~int(5)
to~Integer(5)
) is not impacted by this changeNo, the bitwise complement question is not the topic of #17692 (it is only mentioned in the very last comment)
Either way, #17692 is independent of this ticket. (It probably should be closed (again, the main change has been implemented elsewhere) or converted into a bitwise issue ticket.)
comment:58 Changed 3 months ago by
Milestone:  sage9.7 → sage9.8 

comment:59 Changed 3 months ago by
Branch:  public/ticket17965experiment → 312a91d4f327802ca1e6d48975cd1d221128833e 

Resolution:  → fixed 
Status:  positive_review → closed 
Here is a first attempt. Opinions ?
New commits:
convert some .inverse to .__invert__ and make a global alias in magmas cat