Move generic ring methods to category

[mjungmath]

All generic methods such as ìs_field or is_integral_domain, which are commonly used all over Sage, are part of rings/ring.pyx. But not every ring inherits from it.

I suggest to move those method to categories/rings.py. This allows to replace any _Fields = Fields() allocation and if R in _Fields clauses by a simpler and quicker R.is_field() check.

sage-devel discussion: https://groups.google.com/g/sage-devel/c/H0lih8_3_o4

CC: @tscrim @mkoeppe @videlec @slel

Component: categories

Branch/Commit: u/gh-mjungmath/move_generic_ring_methods_to_category @ 1af973d

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

[mjungmath]

Branch: u/gh-mjungmath/move_generic_ring_methods_to_category

[tscrim]

Commit: 04f0ec6

[tscrim]

comment:4

I am a -1 on doing this. You are changing a Cython function into a Python function (which can be further called indirectly) and this check is done in some parts that need to be fast. The is_field check is currently quicker because of this. However, I am not opposed to having some generic method somewhere about this.

This is suggesting that more rings inherit from Ring when possible rather than lifting stuff up to the category.

---

New commits:

04f0ec6

first draft

[mjungmath]

comment:7

Replying to @tscrim:

I am a -1 on doing this. You are changing a Cython function into a Python function (which can be further called indirectly) and this check is done in some parts that need to be fast. The is_field check is currently quicker because of this. However, I am not opposed to having some generic method somewhere about this.

Wait a second...but is_field is currently a pure Python function via def in ring.pyx. Then I don't understand what you mean.

[tscrim]

comment:8

Methods in a Cython file are faster than those in plain python files.

[mjungmath]

comment:9

But then we can still overwrite the category's class and obtain the same speed, no?

[sagetrac-git]

Changed commit from 04f0ec6 to 1af973d

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

078162b	Trac #31722: turn is_field and is_integral_domain into cpdef functions (completely doctested)
1af973d	Trac #31722: add is_field and is_integral_domain to category of rings (tests on magmas fail)

[mjungmath]

comment:11

I turned is_field and is_integral_domain into cpdef functions now. Doctests work all over Sage except for sage: S.is_field = lambda : False in line 4149 in structure/element.pyx which I really don't understand to be there...

After that, I added is_field and is_integral_domain to the ring category, doctests run fine except for magmas. Even though magmas have their own is_field method, Sage prioritizes the one from rings which causes an error in line 380 of categories/magmas.py.

I mean, this cannot only happen to magmas. Is there any way to handle this properly?

[mjungmath]

comment:12

Next steps: reduce the usage of _Fields and _IntegralDomains as much as possible and/or rather import from rings/ring.pyx.

[videlec]

comment:14

What is the point of reducing the usage of _Fields and _IntegralDomains (which I believe mean the categories Fields() and IntegralDomains())? The idiom my_parent in Fields() and my_parent in IntegralDomains() are the ways to test the parents. The methods is_field() and is_integral_domain() are convenience methods randomly defined on some parents (note that rings are not forced to inherit from Ring).

[videlec]

comment:15

See eg #28189

[videlec]

comment:16

Typical example

sage: A = ZZ.cartesian_product(ZZ)
sage: A in Fields()
False
sage: A.is_field()
Traceback (most recent call last):
...
AttributeError: 'CartesianProduct_with_category' object has no attribute 'is_field'

[mjungmath]

comment:17

Replying to @videlec:

What is the point of reducing the usage of _Fields and _IntegralDomains (which I believe mean the categories Fields() and IntegralDomains())? The idiom my_parent in Fields() and my_parent in IntegralDomains() are the ways to test the parents. The methods is_field() and is_integral_domain() are convenience methods randomly defined on some parents (note that rings are not forced to inherit from Ring).

See Travis's comment: #31713 comment:17.

There are a lot of files that nail _Fields into memory whereas other files call is_field even though that ring does not admit this method (e.g. free_module). I think this should be unified together with a clear guideline for future developments.

[videlec]

comment:18

Replying to @mjungmath:

Replying to @videlec:

What is the point of reducing the usage of _Fields and _IntegralDomains (which I believe mean the categories Fields() and IntegralDomains())? The idiom my_parent in Fields() and my_parent in IntegralDomains() are the ways to test the parents. The methods is_field() and is_integral_domain() are convenience methods randomly defined on some parents (note that rings are not forced to inherit from Ring).

See Travis's comment: #31713 comment:17.

There are a lot of files that nail _Fields into memory whereas other files call is_field even though that ring does not admit this method (e.g. free_module). I think this should be unified together with a clear guideline for future developments.

I strongly agree that unification is required. I don't see why is_field has to be prefered.

[mjungmath]

comment:19

Alright. Could you elaborate on this a bit more? I naively thought is_field might be faster and avoids these memory cluttering entirely.

[videlec]

comment:20

I just think that this requires more thoughts. It is good to have your branch as a "proof of concept" but I think this would be better discussed on sage-devel.

Note that your implementation of is_integral_domain basically return NotImplementedError in most cases. What is the point of having such method? Also you are using the proof flag in the opposite way people would do: namely use randomized primality testing for Zmod(n) (does give (very rarely) false positives but never false negatives).

[mjungmath]

comment:21

Replying to @videlec:

I just think that this requires more thoughts. It is good to have your branch as a "proof of concept" but I think this would be better discussed on sage-devel.

Alright, I'll open a thread.

Note that your implementation of is_integral_domain basically return NotImplementedError in most cases. What is the point of having such method? Also you are using the proof flag in the opposite way people would do: namely use randomized primality testing for Zmod(n) (does give (very rarely) false positives but never false negatives).

I agree, and I am not satisfied with that either. But for now I just copied the code from ring.pyx.

[mjungmath]

comment:22

What I could imagine is that is_field returns False in categories/rings.py by default and gets overridden by concrete implementations such as parents and other categories. Moreover I like the idea of _is_Field in rings/ring.pyx that checks is_field and refines the category if it returns True.

[videlec]

comment:23

Replying to @mjungmath:

What I could imagine is that is_field returns False in categories/rings.py by default and gets overridden by concrete implementations such as parents and other categories. Moreover I like the idea of _is_Field in rings/ring.pyx that checks is_field and refines the category if it returns True.

The idea is nice but the realization is less nice. By refining the category you change the classes of parents and elements (except if it is an extension class). Namely, the following construction is not commutative

sage: a = P(...)        # create element
sage: P in Fields()     # refine category
sage: f(a)              # the type P.Element did not change, a inherits from Ring.ElementClass

versus

sage: P in Fields()     # refine category
sage: a = P(...)        # create element
sage: f(a)              # the type P.Element did change, a inherits from Field.ElementClass

Maybe even worse, the following scenario ends up with two elements having different classes

sage: a = P(...)     # inherits from Rings.ElementClass
sage: P in Fields()
sage: b = P(...)     # inherits from Fields.ElementClass

[mjungmath]

comment:24

But that would mean that the parent must already take care of its categories during initialization such that P in Fields() (or is_field respectively) already returns the appropriate result, right?

If that is the case, the implementation of is_field is even easier: just return False for the category of rings and True for the category of Fields.

And the implementation of the category of magmas would be a violation of the above concept, i.e. a flawed implementation.

[videlec]

comment:26

Replying to @mjungmath:

But that would mean that the parent must already take care of its categories during initialization such that P in Fields() (or is_field respectively) already returns the appropriate result, right?

Or at least before any element is created.

If that is the case, the implementation of is_field is even easier: just return False for the category of rings and True for the category of Fields.

That becomes annoying for Zmod(n) for which you do not want to check primality of n until it is strictly required. Maybe that could be an option of the constructor but something has to be done.

And the implementation of the category of magmas would be a violation of the above concept, i.e. a flawed implementation.

[tscrim]

comment:27

Zmod(n) (or anything that does a primality check) is a problem because of the expense of checking it is a field when you might not need it. Note that Zmod(n) does have an is_field argument for this reason (as well as a category argument).

However, that being said, most parents take care of their category correctly.

The foo.is_cat_obj() method is likely generally faster than foo in Cat because no testing of subcategories is needed. Testing many different cases is likely needed here.

[mjungmath]

comment:28

Replying to @videlec:

Replying to @mjungmath:

But that would mean that the parent must already take care of its categories during initialization such that P in Fields() (or is_field respectively) already returns the appropriate result, right?

Or at least before any element is created.

If that is the case, the implementation of is_field is even easier: just return False for the category of rings and True for the category of Fields.

That becomes annoying for Zmod(n) for which you do not want to check primality of n until it is strictly required. Maybe that could be an option of the constructor but something has to be done.

Not a big issue, isn't it? A parent is still allowed to overwrite the category's method.

But honestly, I don't quite get your initial argument. Why can't a parent be in the category of fields and maintain the original ring implementation? Usually, the element class stays the same whereas only the category changes, or do I get something wrong here? As far as I understand the category framework, categories and concrete implementations are entirely decoupled. Do you have a concrete example where this might fail?

[tscrim]

comment:29

Replying to @mjungmath:

Replying to @videlec:

Replying to @mjungmath:
That becomes annoying for Zmod(n) for which you do not want to check primality of n until it is strictly required. Maybe that could be an option of the constructor but something has to be done.

Not a big issue, isn't it? A parent is still allowed to overwrite the category's method.

But honestly, I don't quite get your initial argument. Why can't a parent be in the category of fields and maintain the original ring implementation? Usually, the element class stays the same whereas only the category changes, or do I get something wrong here? As far as I understand the category framework, categories and concrete implementations are entirely decoupled. Do you have a concrete example where this might fail?

As we all know, you need to determine if n is a prime to know if Zmod(n) is a field or not. However, this can be really slow for large n and you may not care that Zmod(n) is a field (say you are looping over all n and checking some formula as n varies). Thus, you only want to trigger the primality test when you want to make sure Zmod(n) is a field (after which, if it is a field, it refines its category to put it in Fields, but this doesn't update the already existing elements).