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: sage-9.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:

Status badges

Description (last modified by Nicolas M. Thiéry)

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 Nicolas M. Thiéry

Description: modified (diff)

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

Authors: Frédéric Chapoton
Branch: u/chapoton/17965
Commit: 99d9b6cbb562c87e87ca0fc2a6465b387e486157
Status: newneeds_review

Here is a first attempt. Opinions ?


New commits:

99d9b6cconvert some .inverse to .__invert__ and make a global alias in magmas cat

comment:3 Changed 2 years ago by git

Commit: 99d9b6cbb562c87e87ca0fc2a6465b387e4861571a1ec14fcae40bc98284b74ef3a2d3d5e55461a6

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

1a1ec14fix some details

comment:4 Changed 2 years ago by Markus Wageringel

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 git

Commit: 1a1ec14fcae40bc98284b74ef3a2d3d5e55461a69d5692d26c4bf8ad4aa8eb1a9f2cbaab5f35b842

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

9d5692dfix some doctests in polynomial quotient rings

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

Milestone: sage-6.6sage-9.2

comment:7 Changed 2 years ago by git

Commit: 9d5692d26c4bf8ad4aa8eb1a9f2cbaab5f35b842fbc929ef8a01b017641838c47287e141ea96f8f4

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

fbc929esome pycodestyle details (breaking some lines after : and ;)

comment:8 Changed 2 years ago by git

Commit: fbc929ef8a01b017641838c47287e141ea96f8f42962668d234c07498c652c66f8b2de44479dcd21

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

2962668fix one wrong use of parent

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

oh, boy, now with an infinite loop in

sage -t --long --warn-long 61.5 src/sage/monoids/free_monoid_element.py

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

Status: needs_reviewneeds_work

comment:11 Changed 2 years ago by git

Commit: 2962668d234c07498c652c66f8b2de44479dcd215e7e19afded220ad7e88b6362e7f98448a46df04

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

637f8bdMerge branch 'u/chapoton/17965' of ssh://trac.sagemath.org:22/sage in 9.2.b8
5e7e19atentative fix, move inversion to monoids

comment:12 Changed 2 years ago by Matthias Köppe

Milestone: sage-9.2sage-9.3

comment:13 Changed 2 years ago by git

Commit: 5e7e19afded220ad7e88b6362e7f98448a46df04dc2e65f80dbd67279f37e07f24b861c0cc7d7e27

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

dc2e65fMerge branch 'u/chapoton/17965' in 9.3.b0

comment:14 Changed 2 years ago by git

Commit: dc2e65f80dbd67279f37e07f24b861c0cc7d7e27bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68

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

7ddf35eMerge branch 'u/chapoton/17965' in 9.3.b1
bc7fe1eadd doctests in free_monoid_element

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

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 Nicolas M. Thiéry

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 Frédéric Chapoton

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 Nicolas M. Thiéry

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 Matthias Köppe

Milestone: sage-9.3sage-9.4

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

comment:20 Changed 17 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

Setting a new milestone for this ticket based on a cursory review.

comment:21 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

comment:22 Changed 8 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:23 Changed 7 months ago by git

Commit: bc7fe1e67d9788991fdb5f1487d14c3ac44a4f68a4f176d870fb79a8a82a7bfb7b5c24b6d302e947

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

a4f176dMerge branch 'u/chapoton/17965' in 9.7.b0

comment:24 Changed 7 months ago by git

Commit: a4f176d870fb79a8a82a7bfb7b5c24b6d302e947b5402d06f7a69f2580d7120cb760d199648046d6

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

b5402d0fix typos in errors

comment:25 Changed 6 months ago by git

Commit: b5402d06f7a69f2580d7120cb760d199648046d6e092bef62df70a3dd3144318aa65e67db2da828a

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

e092befMerge branch 'u/chapoton/17965' in 9.7.b1

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

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 git

Commit: e092bef62df70a3dd3144318aa65e67db2da828ade510a5732c108d8f916857d9e7af3f8b50754a5

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

711913aMerge branch 'u/chapoton/17965' in 9.7.rc0
de510a5trying to fix things in the categories

comment:28 Changed 3 months ago by git

Commit: de510a5732c108d8f916857d9e7af3f8b50754a50e19786c4715fa582ec87121592595626c4a56ec

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

0e19786add doctest

comment:29 Changed 3 months ago by Frédéric Chapoton

almost ready to go. I hope that somebody will accept to review this long-awaited ticket.

comment:30 Changed 3 months ago by git

Commit: 0e19786c4715fa582ec87121592595626c4a56ec24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6

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

24b88a5fix doc

comment:31 Changed 3 months ago by Frédéric Chapoton

Cc: Travis Scrimshaw added
Status: needs_workneeds_review

and the patchbot is now green ! comments welcome

comment:32 Changed 3 months ago by Matthias Köppe

+        def inverse(self):
+            """
+            Return the inverse of ``self``.
+
+            This an alias for inversion, defined in ``__invert__``.
+

"is" is missing

comment:33 Changed 3 months ago by Matthias Köppe

Do you want to address comment:4 and add some automethod?

comment:34 Changed 3 months ago by git

Commit: 24b88a5991a41d2bf9cf4fe9c2281b05f9fefcf6b6a5773fc8c6b861150dc9e03d241ddf41741c24

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

b6a5773fix typo

comment:35 Changed 3 months ago by Frédéric Chapoton

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 Changed 3 months ago by Travis Scrimshaw

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 git

Commit: b6a5773fc8c6b861150dc9e03d241ddf41741c24e08cd7a4e9fb5d6492e8a611040dd562bdddf6cb

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

9ec90c5Merge branch 'u/chapoton/17965' in 9.7.rc1
e08cd7atweak doc

comment:38 in reply to:  36 ; Changed 3 months ago by Frédéric Chapoton

Replying to Travis Scrimshaw:

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.

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 in Element. 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 in reply to:  38 Changed 3 months ago by Travis Scrimshaw

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 in Element. 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.

Last edited 3 months ago by Travis Scrimshaw (previous) (diff)

comment:40 Changed 3 months ago by git

Commit: e08cd7a4e9fb5d6492e8a611040dd562bdddf6cbd0fbe93d4de3b38b40034b4c1743399f37393a59

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

d0fbe93tweak doc again

comment:41 Changed 3 months ago by Frédéric Chapoton

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 backward-incompatible..

comment:42 Changed 3 months ago by Travis Scrimshaw

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 Frédéric Chapoton

Branch: u/chapoton/17965public/ticket-17965-experiment
Commit: d0fbe93d4de3b38b40034b4c1743399f37393a59312a91d4f327802ca1e6d48975cd1d221128833e

here is an experimental branch with the default inverse re-activated, let us see what happens.


New commits:

312a91dre-introduce default inversion

comment:44 Changed 3 months ago by Frédéric Chapoton

well, this seems to be almost green..

comment:45 Changed 3 months ago by Travis Scrimshaw

It seems like that is unrelated. Have you tested locally?

comment:46 Changed 3 months ago by Frédéric Chapoton

the failure is #33161 ; the tests in this file pass with other random seeds

comment:47 Changed 3 months ago by Travis Scrimshaw

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 Frédéric Chapoton

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 Travis Scrimshaw

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 Frédéric Chapoton

Sorry, I am now confused and not sure what you would like me to change.

comment:51 Changed 3 months ago by Travis Scrimshaw

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:52 Changed 3 months ago by Frédéric Chapoton

So, is this a positive review ?

comment:53 Changed 3 months ago by Travis Scrimshaw

Reviewers: Travis Scrimshaw
Status: needs_reviewpositive_review

Yes.

comment:54 Changed 3 months ago by Matthias Köppe

After these changes, is ticket #17692 still relevant?

comment:55 Changed 3 months ago by 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 (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 in reply to:  55 ; Changed 3 months ago by 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 change

No, the bitwise complement question is not the topic of #17692 (it is only mentioned in the very last comment)

comment:57 in reply to:  56 Changed 3 months ago by Travis Scrimshaw

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 change

No, 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 Matthias Köppe

Milestone: sage-9.7sage-9.8

comment:59 Changed 3 months ago by Volker Braun

Branch: public/ticket-17965-experiment312a91d4f327802ca1e6d48975cd1d221128833e
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.