x in IntegralDomains() should refine category #15183

saraedum · 2013-09-10T19:23:55Z

Currently, IntegerModRing refines its category if asked for membership in Fields():

sage: M = IntegerModRing(3)
sage: M.category()
Join of Category of commutative rings ...
sage: M in Fields()
True
sage: M.category()
Join of Category of fields ...

The same does not happen for IntegralDomains():

sage: M = IntegerModRing(5)
sage: M.category()
Join of Category of commutative rings ...
sage: M in IntegralDomains()
False
sage: M.category()
Join of Category of commutative rings ...

The changes on this ticket copy the logic from fields over to integral domains.

Depends on #14482

CC: @simon-king-jena @nthiery

Component: categories

Author: Julian Rueth

Branch/Commit: u/saraedum/ticket/15183 @ 2282a39

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

The text was updated successfully, but these errors were encountered:

saraedum · 2013-09-10T19:53:11Z

Branch: u/saraedum/ticket/15183

saraedum · 2013-09-10T19:53:13Z

Dependencies: #14482

saraedum · 2013-09-10T19:54:13Z

Author: Julian Rueth

saraedum · 2013-09-10T19:55:05Z

comment:5

Simon, I believe I mostly adapted your code from Fields. Do mind having a look at this?

sagetrac-git · 2013-09-10T21:29:50Z

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

`[changeset:2554616]`	`Added classes for discrete valuations`
`[changeset:5af8f0a]`	`Merge branch 'u/saraedum/ticket/15171' of http://trac.sagemath.org/sage into ticket/15183`
`[changeset:2907216]`	`Fixed a missing assignment in DiscreteValueGroup.`
`[changeset:2249b00]`	`Added DiscreteValueGroup`
`[changeset:23db51b]`	`Merge branch 'u/roed/ticket/14482' of ssh://trac.sagemath.org:2222/sage into ticket/15171`

sagetrac-git · 2013-09-10T21:29:50Z

Commit: 2554616

saraedum · 2013-09-10T21:30:04Z

Changed dependencies from #14482 to #14482, #15171

saraedum · 2013-09-10T21:33:38Z

Changed dependencies from #14482, #15171 to #14482

sagetrac-git · 2013-09-10T21:57:52Z

Changed commit from 2554616 to 2282a39

sagetrac-git · 2013-09-10T21:57:52Z

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


[changeset:2282a39]	Added refinement of categories for IntegralDomains.
[changeset:efa66ca]	Merge branch 'u/saraedum/ticket/14482' of ssh://trac.sagemath.org:2222/sage into ticket/15183
[changeset:c2902bb]	Improve diff() against 'dependencies'
[changeset:9e4a92c]	Added _is_master_uptodate() to dev scripts
[changeset:cc0ba9f]	Made remote_status() more usable.

saraedum · 2013-09-10T21:58:37Z

comment:10

Sorry, I uploaded the wrong branch to this ticket. Should be fixed now.

simon-king-jena · 2013-09-10T22:08:57Z

comment:11

The main problem for me is that it uses git, and as much as I know, the "master" branch in the trac-git version of Sage does not pass tests.

Hence, I currently have no version of Sage which I could use to test your changes. And besides, my knowledge of git is too little to really understand what has changed and what happened in a dependency.

In any case, are you really sure that IntegralDomains() needs the refinement? The reason for introducing the refinement in testing containment in Fields() was the fact that Fields.__contains__ does some pretty custom things, that are really slow, unless the objects's category is properly initialised. Hence, the idea was to "cache" the result of the slow test by refining the category, so that next time the slow test will be avoided.

But IntegralDomains has no custom implementation of __contains__. So, could you elaborate a bit more on the reason of your suggestion?

nbruin · 2013-09-10T22:20:29Z

comment:12

Really, by the time you've established that Z/nZ is an integral domain, you can refine it to field anyway (which is an integral domain).

saraedum · 2013-09-11T10:41:21Z

comment:13

Replying to @simon-king-jena:

The main problem for me is that it uses git, and as much as I know, the "master" branch in the trac-git version of Sage does not pass tests.

I see.

Hence, I currently have no version of Sage which I could use to test your changes. And besides, my knowledge of git is too little to really understand what has changed and what happened in a dependency.

You could use ./sage --dev diff --base=dependencies to see the changes introduced on the ticket itself. (with a recent version of #14482, like the one on this ticket, i.e., do sage -b before using this command)

In any case, are you really sure that IntegralDomains() needs the refinement? The reason for introducing the refinement in testing containment in Fields() was the fact that Fields.__contains__ does some pretty custom things, that are really slow, unless the objects's category is properly initialised. Hence, the idea was to "cache" the result of the slow test by refining the category, so that next time the slow test will be avoided.

What does Fields.__contains__ do? It calls .is_field() which might be expensive (e.g. in the case Z/nZ). Integral domains should do the same, call .is_integral_domain() which is as expensive.

But IntegralDomains has no custom implementation of __contains__. So, could you elaborate a bit more on the reason of your suggestion?

I believe that's why the check IntegerModRing(2) in IntegralDomains() failed, right?

saraedum · 2013-09-11T10:44:13Z

comment:14

Replying to @nbruin:

Really, by the time you've established that Z/nZ is an integral domain, you can refine it to field anyway (which is an integral domain).

Sure, in the case of Z/nZ this is true. However, I tried to implement this on the level of categories, and I don't think that IntegralDomains() should try to refine to Fields(). One could of course implement this in IntegerModRing but I believe it is cleaner like this.

simon-king-jena · 2013-09-11T10:48:35Z

comment:15

Replying to @saraedum:

What does Fields.__contains__ do? It calls .is_field()

No, it calls sage.rings.ring._is_Field, and this is where .is_field() might be called and the refinement might happen.

Integral domains should do the same, call .is_integral_domain() which is as expensive.

But IntegralDomains has no custom implementation of __contains__. So, could you elaborate a bit more on the reason of your suggestion?

I believe that's why the check IntegerModRing(2) in IntegralDomains() failed, right?

Do you suggest to introduce a custom IntegralDomains.__contains__?

saraedum · 2013-09-11T10:59:00Z

comment:16

Replying to @simon-king-jena:

Replying to @saraedum:

What does Fields.__contains__ do? It calls .is_field()

No, it calls sage.rings.ring._is_Field, and this is where .is_field() might be called and the refinement might happen.

Sorry, that's what I meant.

Integral domains should do the same, call .is_integral_domain() which is as expensive.

But IntegralDomains has no custom implementation of __contains__. So, could you elaborate a bit more on the reason of your suggestion?

I believe that's why the check IntegerModRing(2) in IntegralDomains() failed, right?

Do you suggest to introduce a custom IntegralDomains.__contains__?

Yes. This is what my patch does. Here is the diff: changeset:2282a39

simon-king-jena · 2013-09-11T11:06:56Z

comment:17

Can you tell me why the patchbot only found errors in TWO files, namely

sage -t --long src/sage/dev/sagedev.py  # 1 doctest failed
sage -t --long src/sage/dev/patch.py  # 2 doctests failed

??

On my machine, I got many more errors. Or perhaps I am on the wrong branch. I currently have

$ git branch
* master
  public/sage-git/master
  ticket/15120

where #15120 is supposed to fix some remaining tests. But I am not sure, perhaps one of the two branches above is not the sage-trac master. How can I find out whether my current branch pulls from github or from trac?

saraedum · 2013-09-11T11:15:23Z

comment:18

Replying to @simon-king-jena:

Can you tell me why the patchbot only found errors in TWO files, namely
sage -t --long src/sage/dev/sagedev.py  # 1 doctest failed
sage -t --long src/sage/dev/patch.py  # 2 doctests failed
??

I'm not sure what the patchbot does. It might merge in a few changes for the doctests but I don't know.

On my machine, I got many more errors. Or perhaps I am on the wrong branch. I currently have
$ git branch
* master
  public/sage-git/master
  ticket/15120
where #15120 is supposed to fix some remaining tests. But I am not sure, perhaps one of the two branches above is not the sage-trac master. How can I find out whether my current branch pulls from github or from trac?

git branch -vv shows where the branches pull from. You can of course also pull explicitely: git pull http://trac.sagemath.org/sage.git public/sage-git/master.

simon-king-jena · 2013-09-11T12:02:35Z

comment:19

Replying to @saraedum:

git branch -vv shows where the branches pull from.

Not really.

$ git branch -vv
* master                 b890215 [origin/public/sage-git/master] Merge branch 'ticket/14482' into public/sage-git/master
  public/sage-git/master cf14c84 [origin/public/sage-git/master: behind 562] Merge branch 'ticket/14482' into public/sage-git/master
  ticket/15120           6912669 Fix --new option for doctests.

Neither trac nor github are mentioned...

You can of course also pull explicitely: git pull http://trac.sagemath.org/sage.git public/sage-git/master.

Am I correct that this would pull into my "public/sage-git/master" branch, but would not affect the other branch called "master"?

I am sure that one branch was obtained from github and the other from trac, and it is a shame that it can't clearly (at least to my understanding) tell which is which.

saraedum · 2013-09-11T12:17:46Z

comment:20

Replying to @simon-king-jena:

Replying to @saraedum:

git branch -vv shows where the branches pull from.

Not really.

$ git branch -vv
* master                 b890215 [origin/public/sage-git/master] Merge branch 'ticket/14482' into public/sage-git/master
  public/sage-git/master cf14c84 [origin/public/sage-git/master: behind 562] Merge branch 'ticket/14482' into public/sage-git/master
  ticket/15120           6912669 Fix --new option for doctests.

So, master and public/sage-git/master pull from origin. To find out what is origin, type git remote -v.

You can of course also pull explicitely: git pull http://trac.sagemath.org/sage.git public/sage-git/master.

Am I correct that this would pull into my "public/sage-git/master" branch, but would not affect the other branch called "master"?

This would pull into the current branch, the one with the asterisk in git branch.

I am sure that one branch was obtained from github and the other from trac, and it is a shame that it can't clearly (at least to my understanding) tell which is which.

It seems that they both came from trac. At least their latest version does. It does not really matter where they originally came from.

simon-king-jena · 2013-09-11T12:37:27Z

comment:21

Replying to @saraedum:

So, master and public/sage-git/master pull from origin. To find out what is origin, type git remote -v.

git remote -v
origin  ssh://git@trac.sagemath.org:2222/sage.git (fetch)
origin  ssh://git@trac.sagemath.org:2222/sage.git (push)

So, to my surprise, there is no github in it.

nathanncohen · 2013-12-26T19:00:51Z

comment:23

Okay guys, it looks like Nicolas says that category containment should not refine the category, and on the other hand Fields already do it. What do you decide ?

Nathann

nathanncohen · 2013-12-26T19:03:36Z

comment:24

Just in case...

Nathann

simon-king-jena · 2013-12-26T19:55:28Z

comment:25

Replying to @nathanncohen:

Okay guys, it looks like Nicolas says that category containment should not refine the category,

For good reason! Category refinement involves changing the class of an object after creation, and actually after usage! Python lets you do those things, but really it is a dangerous hack.

We have seen cases in which the hash of a parent depends on the class of the parent. Hence, if a category refinement happens after (or while) using a parent P as key of a dictionary, it used to be possible that P was put in the wrong hash bucket of the dictionary. Fortunately, someone (I think it was Volker) added a security layer, so that now changing the class results in an error if it changes the hash.

But apart from hash, one often sees the following in __cmp__ methods:

def __cmp__(self, other):
    c = cmp(type(self),type(other))
    if c:
        return c
    return cmp(<data for self>,<data for other>)

Hence, if you add category refinement, comparison could break: Imagine you originally had cmp(self,other)==0 and then did self in IntegralDomains() (triggering a category refinement) but didn't other in IntegralDomains(). Now, ask cmp(self,other): The result will not be zero any more!

Mathematically, a category refinement should be fine, and one may think that the category framework is designed to be stable against category refinement ("if you refine the category of P, then P may inherit different methods from the category framework than before, but these new methods will fit better."). However, some of these methods do caching. Hence, if P originally belongs to category C1 and it got some method meth() which did some caching, and then you refine P's category to be C2, so that P now inherits a different version of meth() that uses a different cache, then you have a mess.

One could argue that it is a bug if you do get a mess upon category refinement. But perhaps it is wise to not consciously ask for trouble...

and on the other hand Fields already do it.

Yes, I know, I have to take the full blame...

But the situation was different than the situation here!

When I introduced category refinement for fields, Fields.__contains__ used to be custom since a long time. This custom method was very very slow, but the default __contains__ method couldn't be used unless all parents' categories were fully initialised. But then, the initialisation took too much time. Hence, I went for a compromise: Keep initialisation fast, and accept that the first Fields() containment test is slow; but in case of success, make sure that all further containment test will be quick.

I was motivated by a concrete example that was important to a "powerful" Sage sub-community (you know, elliptic curves and so on): This example became way too slow after implementing the category framework for all rings. Reason: Initialisation of these rings took way too long, since for each ring it was needed to test whether the modulus is a prime number. Guided by this example (and a similar example for matrix spaces) I found that a "lazy" category initialisation can avoid certain severe regressions.

However, here, things are different: As much as I understand, the suggestion is to let IntegralDomains() have a custom __contains__ method, just because Fields() has a custom __contains__ method too. But since Category_singleton.__contains__ is very very fast, it should not be overridden by a custom __contains__ without a very very good and compelling reason. It could actually be that some examples will become slower when the containment test will regress.

Put differently: I haven't seen any concrete "real world" example that shows that we need lazy category initialisation for (some) integral domains. Without such example, I'd say we should better not open Pandora's box again.

mezzarobba · 2014-02-11T16:35:12Z

comment:27

So, does this ticket still need review? Should it be closed as wontfix?

saraedum · 2014-02-11T16:45:39Z

comment:28

Simon made a good point. I did this for consistency with Fields. I see now that it is better not to introduce this change.

saraedum added this to the sage-5.12 milestone Sep 10, 2013

saraedum added c: categories labels Sep 10, 2013

saraedum added the s: needs review label Sep 10, 2013

saraedum modified the milestones: sage-5.12, sage-6.0 Sep 10, 2013

sagetrac-vbraun-spam mannequin removed this from the sage-6.0 milestone Dec 17, 2013

sagetrac-vbraun-spam mannequin added this to the sage-6.1 milestone Dec 17, 2013

sagetrac-vbraun-spam mannequin modified the milestones: sage-6.1, sage-6.2 Jan 30, 2014

saraedum removed this from the sage-6.2 milestone Feb 11, 2014

nathanncohen mannequin added s: positive review and removed s: needs review labels Feb 11, 2014

vbraun removed the s: positive review label Feb 11, 2014

vbraun closed this as completed Feb 11, 2014

vbraun added r: wontfix and removed p: minor / 4 labels Feb 11, 2014

mkoeppe mentioned this issue Jan 7, 2023

Categories for piecewise functions #21709

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

x in IntegralDomains() should refine category #15183

x in IntegralDomains() should refine category #15183

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

saraedum commented Sep 10, 2013

simon-king-jena commented Sep 10, 2013

nbruin commented Sep 10, 2013

saraedum commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

nathanncohen mannequin commented Dec 26, 2013

nathanncohen mannequin commented Dec 26, 2013

simon-king-jena commented Dec 26, 2013

mezzarobba commented Feb 11, 2014

saraedum commented Feb 11, 2014

x in IntegralDomains() should refine category #15183

x in IntegralDomains() should refine category #15183

Comments

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

saraedum commented Sep 10, 2013

saraedum commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

sagetrac-git mannequin commented Sep 10, 2013

saraedum commented Sep 10, 2013

simon-king-jena commented Sep 10, 2013

nbruin commented Sep 10, 2013

saraedum commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

saraedum commented Sep 11, 2013

simon-king-jena commented Sep 11, 2013

nathanncohen mannequin commented Dec 26, 2013

nathanncohen mannequin commented Dec 26, 2013

simon-king-jena commented Dec 26, 2013

mezzarobba commented Feb 11, 2014

saraedum commented Feb 11, 2014