Uniformize the API to compute the inverse of an element

[nthiery]

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.

CC: @saliola @videlec @simon-king-jena @slel @tscrim

Component: categories

Author: Frédéric Chapoton

Branch/Commit: 312a91d

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/17965

[fchapoton]

Commit: 99d9b6c

[fchapoton]

Author: Frédéric Chapoton

[fchapoton]

Branch: u/chapoton/17965

[fchapoton]

comment:2

Here is a first attempt. Opinions ?

---

New commits:

99d9b6c

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

[sagetrac-git]

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

1a1ec14

fix some details

[sagetrac-git]

Changed commit from 99d9b6c to 1a1ec14

[mwageringel]

comment:4

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.

[sagetrac-git]

Changed commit from 1a1ec14 to 9d5692d

[sagetrac-git]

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

9d5692d

fix some doctests in polynomial quotient rings

[sagetrac-git]

Changed commit from 9d5692d to fbc929e

[sagetrac-git]

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

fbc929e

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

[sagetrac-git]

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

2962668

fix one wrong use of parent

[sagetrac-git]

Changed commit from fbc929e to 2962668

[fchapoton]

comment:9

oh, boy, now with an infinite loop in

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

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from 2962668 to 5e7e19a

[sagetrac-git]

Changed commit from 5e7e19a to dc2e65f

[sagetrac-git]

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

dc2e65f

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

[sagetrac-git]

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

d0fbe93

tweak doc again

[fchapoton]

comment:41

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

[tscrim]

comment:42

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).

[fchapoton]

comment:43

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

---

New commits:

312a91d

re-introduce default inversion

[fchapoton]

Changed commit from d0fbe93 to 312a91d

[fchapoton]

Changed branch from u/chapoton/17965 to public/ticket-17965-experiment

[fchapoton]

comment:44

well, this seems to be almost green..

[tscrim]

comment:45

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

[fchapoton]

comment:46

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

[tscrim]

comment:47

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.

[fchapoton]

comment:48

But this would basically contradict the fact that there is a unique global alias that maps inverse to __invert__ ?

[tscrim]

comment:49

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.

[fchapoton]

comment:50

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

[tscrim]

comment:51

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.

[fchapoton]

comment:52

So, is this a positive review ?

[tscrim]

Reviewer: Travis Scrimshaw

[tscrim]

comment:53

Yes.

[mkoeppe]

comment:54

After these changes, is ticket #17692 still relevant?

[tscrim]

comment:55

#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).

[mkoeppe]

comment:56

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)

[tscrim]

comment:57

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.)

[vbraun]

Changed branch from public/ticket-17965-experiment to 312a91d