Opened 6 years ago
Closed 6 years ago
#20902 closed defect (fixed)
Move Parent.list() method to EnumeratedSets category
Reported by:  Kwankyu Lee  Owned by:  

Priority:  major  Milestone:  sage7.4 
Component:  categories  Keywords:  
Cc:  Johan Rosenkilde, Nils Bruin, Volker Braun, Jeroen Demeyer, Travis Scrimshaw, Nicolas M. Thiéry  Merged in:  
Authors:  Kwankyu Lee  Reviewers:  Travis Scrimshaw 
Report Upstream:  N/A  Work issues:  
Branch:  bdbd034 (Commits, GitHub, GitLab)  Commit:  bdbd034de6d3ebd7d922bcc68165ce18c2112888 
Dependencies:  Stopgaps: 
Description (last modified by )
The methods __len__
, list
, _list_from_iterator_cashed
in the Parent class conflict with those of the FiniteEnumerableSets
category. One symptom is #20743. The proper place for them is the EnumeratedSets
category (#12955), and the three methods are moved to therein.
Along the way, the patch also introduces "Enumerated" axiom into the category framework. The effect is for lots of cases, we get nicer names for the joint category with the enumerated sets category.
Change History (54)
comment:1 Changed 6 years ago by
Branch:  → u/klee/20902 

comment:2 Changed 6 years ago by
Commit:  → 6a36fa0c3c2c058c9dfb9dff74719174838c1a04 

comment:3 Changed 6 years ago by
Status:  new → needs_review 

comment:4 Changed 6 years ago by
The patch introduces a doctest failure, which is not caused by the patch, but just revealed by it. The doctest failure is the issue treated in #20896.
comment:5 Changed 6 years ago by
Authors:  → Kwankyu Lee 

comment:6 followup: 7 Changed 6 years ago by
Cc:  Johan Rosenkilde Nils Bruin Volker Braun Jeroen Demeyer Travis Scrimshaw Nicolas M. Thiéry added 

I have some issues with this:
 You are arguing that these functions should be in
EnumeratedSets
, but you move them toSets
. Why not move them toEnumeratedSets
and start adding parents to that category? At least, you should keep the TODO that this would be best?
 The
list
function now returns a copy of the (cached) list every time. We had a long discussion on sagedevel as well as on #20743 about this, and though complete consensus didn't arise, everyone seemed to think thatlist
should not return a fresh copy every time. Rather we should somehow flag the list as being immutable.
Apart from that it makes sense to move those functions from Parent
.
(I added a few of the debators on #20743 to Cc, hope you're all ok with that).
comment:7 Changed 6 years ago by
First let me thank you for raising these issues, which are legitimate.
 You are arguing that these functions should be in
EnumeratedSets
, but you move them toSets
. Why not move them toEnumeratedSets
and start adding parents to that category? At least, you should keep the TODO that this would be best?
Many parents in Sage do have list
method, but are not declared as in enumerable set category. Some of them seems that their enumerability is determined only at runtime, so cannot be declared so in its defining class. For example, a free module over a ring can be either enumerable or not depending on the ring. So keeping the "list" method only in EnumeratedSets
category is not the way to support list
method for existing parents. For the reason, I doubt that the TODO is really what we have to do. Yes, I am arguing against myself, but the should is for a perfect world.
 The
list
function now returns a copy of the (cached) list every time. We had a long discussion on sagedevel as well as on #20743 about this, and though complete consensus didn't arise, everyone seemed to think thatlist
should not return a fresh copy every time. Rather we should somehow flag the list as being immutable.
I am aware of the discussion. I was one of the proponents that list
method should return a cashed tuple rather than a list. But searching through Sage library, I find that (1) list
method is inconsistently implemented for many parents in Sage; (2) The implementation of list
method for finite sets category returns a fresh copy of a cached list each time (the same is true for list
method of the current Parent
class). My conclusion is that the behavior of the list
method of the parents in the finite sets category is the de facto standard in Sage. So I copied the "standard" implementation to Sets
category.
In the present ticket, I am not taking any position about how the list
method should be implemented, but just move around what is already in Sage. If we all agree on a proper implementation of the list
methods of parents in the category framework, that should be another ticket. Let me just say that for this issue, my present opinion is that the current implementation is reasonable in the category framework, and if a specific parent needs better performance, it can just implement its own list
method.
comment:8 Changed 6 years ago by
Status:  needs_review → needs_work 

Hmm. Now I suspect that I am wrong in the first answer. The category is determined at the parent creation time and need not be hardcoded into the class. Then a free module over a ring can declare itself as either enumerable or not at its creation time. Then the fact that it does not do that in the current Sage is simply a bug. So at least free modules are not a good example for my argument.
comment:9 followup: 10 Changed 6 years ago by
OK, your arguments are compelling. I agree that making the move is orthogonal to changing the implementation of list
.
Since it is possible to dynamically be a member of EnumerableSets
or not, how hard would it be to move the functions into there immediately? It seems a bit wasteful to first make the move of this ticket, and then move them again. In sets_cat.py
there's also a note on line 1368 that cardinality
and other functions are intentionally left out of Sets
to be put in subcategories. It seems a shame to put other functions into Set
which actually belong elsewhere.
About the default implementation of __len__()
: perhaps it could check whether self
has a cardinality
method, in which case it could return that.
comment:10 Changed 6 years ago by
Since it is possible to dynamically be a member of
EnumerableSets
or not, how hard would it be to move the functions into there immediately? It seems a bit wasteful to first make the move of this ticket, and then move them again.
I thought before that it is a daunting task, if at all possible, to put every enumerable parent into EnumerableSets
category. Now I feel that the task can at least be done to such an extent as to avoid doctest failures.
In
sets_cat.py
there's also a note on line 1368 thatcardinality
and other functions are intentionally left out ofSets
to be put in subcategories. It seems a shame to put other functions intoSet
which actually belong elsewhere.
I agree.
About the default implementation of
__len__()
: perhaps it could check whetherself
has acardinality
method, in which case it could return that.
I will consider that while moving the methods again into EnumerableSets
category. For that, now the ticket is in "needs work" status :)
comment:11 Changed 6 years ago by
Sounds great. I'm glad you opened this ticket: I think one of the very confusing things about Sage is that many objects have generic methods that don't do anything sensible on them, exactly because some methods are not placed on the right category/parent object.
comment:12 Changed 6 years ago by
Commit:  6a36fa0c3c2c058c9dfb9dff74719174838c1a04 → 99dc083b75af8adeab1f1677f66e723971d96a2d 

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
99dc083  Move .list() to EnumeratedSets category

comment:13 Changed 6 years ago by
Description:  modified (diff) 

Milestone:  sage7.3 → sage7.4 
Summary:  Move Parent.list() method to Sets category → Move Parent.list() method to EnumeratdSets category 
comment:14 Changed 6 years ago by
Commit:  99dc083b75af8adeab1f1677f66e723971d96a2d → cba4a24f898d1496deedcfe7204d679a9c34e893 

Branch pushed to git repo; I updated commit sha1. New commits:
cba4a24  Fixes some doctest failures

comment:15 Changed 6 years ago by
Commit:  cba4a24f898d1496deedcfe7204d679a9c34e893 → 7a47a865ceab6046111f9e0b50d3a82c68193f74 

Branch pushed to git repo; I updated commit sha1. New commits:
7a47a86  Add a doctest string for Enumerated axiom

comment:16 Changed 6 years ago by
Commit:  7a47a865ceab6046111f9e0b50d3a82c68193f74 → d128a902ad8fae35838465b19ef5c8166118f622 

Branch pushed to git repo; I updated commit sha1. New commits:
d128a90  Patch a doctest failure in jordan algebra

comment:17 Changed 6 years ago by
Description:  modified (diff) 

Status:  needs_work → needs_review 
In the patch, some old parents are modified to avoid doctest failures, but moving parents into enumerated sets cateogy is not attempted.
comment:18 Changed 6 years ago by
Commit:  d128a902ad8fae35838465b19ef5c8166118f622 → 7121e51c8148ebd16579239a82a8fbd63412ab61 

Branch pushed to git repo; I updated commit sha1. New commits:
7121e51  Improve doctest coverage to attract patchbots

comment:19 followup: 20 Changed 6 years ago by
I don't understand why you removed _test_enumerated_set_iter_cardinality
. This is a good check that any code cannot render invalid/redundant.
The change to Jordan algebras is incorrect. You should just let the TypeError
(or whatever the error is from tuple(self.algebra_generators())
) propagate up. Also, you should avoid having a bare except:
statement.
comment:20 followups: 22 23 Changed 6 years ago by
Replying to tscrim:
I don't understand why you removed
_test_enumerated_set_iter_cardinality
. This is a good check that any code cannot render invalid/redundant.
It tests the method _cardinality_from_iterator
, which is removed in the current patch. Now .cardinality()
method is implemented instead just using self.list()
inherited from the enumerated sets category, which itself uses the iterator of self.
So it seemed to me that the _test_enumerated_set_iter_cardinality
lost its point with the current patch. Even the example ("let us now break...") under the test does not work. Would you try that?
But I may have missed the point of the test as intended by the original author. Then would you elaborate on that?
The change to Jordan algebras is incorrect. You should just let the
TypeError
(or whatever the error is fromtuple(self.algebra_generators())
) propagate up.
With the current patch, the original code tuple(self.algebra_generators())
falls into an infinite loop in the case that self.algebra_generators()
is an infinite set. The change is to avoid this. I don't know a better way to deal with this...
Also, you should avoid having a bare
except:
statement.
I see. I will correct that.
comment:21 Changed 6 years ago by
Status:  needs_review → needs_work 

Summary:  Move Parent.list() method to EnumeratdSets category → Move Parent.list() method to EnumeratedSets category 
comment:22 Changed 6 years ago by
Replying to klee:
Replying to tscrim:
I don't understand why you removed
_test_enumerated_set_iter_cardinality
. This is a good check that any code cannot render invalid/redundant.It tests the method
_cardinality_from_iterator
, which is removed in the current patch. Now.cardinality()
method is implemented instead just usingself.list()
inherited from the enumerated sets category, which itself uses the iterator of self.So it seemed to me that the
_test_enumerated_set_iter_cardinality
lost its point with the current patch. Even the example ("let us now break...") under the test does not work. Would you try that?But I may have missed the point of the test as intended by the original author. Then would you elaborate on that?
It is there to test that (X.list()
or) list(X) == X.cardinality()
, which could break anytime a user directly implements cardinality
(such as on the powerset of a finite set).
The change to Jordan algebras is incorrect. You should just let the
TypeError
(or whatever the error is fromtuple(self.algebra_generators())
) propagate up.With the current patch, the original code
tuple(self.algebra_generators())
falls into an infinite loop in the case thatself.algebra_generators()
is an infinite set. The change is to avoid this. I don't know a better way to deal with this...
Previously, if we were calling tuple(X)
when X
was known to be infinite, then this would fail with IIRC a NotImplementedError
(try tuple(ZZ)
). In the example, self.algebra_generators
is known to be infinite:
sage: J = JordanAlgebra(FreeAlgebra(QQ, 3, 'x,y,z')) sage: J.algebra_generators().cardinality() +Infinity
So the error is correct (although the reason was not because the family should know it is in the infinite enumerated sets category). Thus I would propose fixing the category issue of LazyFamily
when the keys are known to be infinite.
Also, I am slightly of the opinion that changing this behavior of enumerated sets with unknown cardinality is a regression. I believe that if the user knows the set is finite, they can do an explicit iteration over the object and we should force them to do that as a safeguard against the infinite loops.
comment:23 followup: 24 Changed 6 years ago by
Hi Kwankyu!
Thanks for your much needed work on cleaning the generic code for enumerated sets. This code is tricky as it aims to cover many different use cases, trying to do "just the right thing" in most of them. It has grown from years of practice and this is all more artwork than science ...
Replying to klee:
Replying to tscrim:
I don't understand why you removed
_test_enumerated_set_iter_cardinality
. This is a good check that any code cannot render invalid/redundant.It tests the method
_cardinality_from_iterator
, which is removed in the current patch. Now.cardinality()
method is implemented instead just usingself.list()
inherited from the enumerated sets category, which itself uses the iterator of self.
1 on removing _cardinality_from_iterator
. This methods
intentionally supports computing the cardinality of very large sets,
without paying the memory overhead of storing all the elements. It has
already been used for sets that just would not fit in memory.
1 on removing _test_enumerated_set_iter_cardinality
: it does not
only test _cardinality_from_iterator
, but also all cases where both
__iter__
and cardinality
are implemented by an enumerated set.
Cheers,
Nicolas
comment:24 followup: 25 Changed 6 years ago by
Replying to nthiery:
1 on removing
_cardinality_from_iterator
. This methods intentionally supports computing the cardinality of very large sets, without paying the memory overhead of storing all the elements. It has already been used for sets that just would not fit in memory.
Good point. I missed this.
1 on removing
_test_enumerated_set_iter_cardinality
: it does not only test_cardinality_from_iterator
, but also all cases where both__iter__
andcardinality
are implemented by an enumerated set.
I agree.
I will recover these and also try to incorporate tscrim's criticisms.
As you will understand, it is quite tricky to accomplish this ticket's task while not failing parents relying on the existing structure...
comment:25 Changed 6 years ago by
Replying to klee:
As you will understand, it is quite tricky to accomplish this ticket's task while not failing parents relying on the existing structure...
You bet; that's why I am particularly grateful someone is taking up the job!
comment:26 Changed 6 years ago by
Commit:  7121e51c8148ebd16579239a82a8fbd63412ab61 → 4da69aaef4f91f0149c74bb710f16692ecca8fd9 

comment:27 Changed 6 years ago by
Status:  needs_work → needs_review 

In the last commits, I tried to make the footprints of the patch as light as possible while accomplishing the task at hand.
comment:28 Changed 6 years ago by
Commit:  4da69aaef4f91f0149c74bb710f16692ecca8fd9 → c57069e9c66ad4f28038744f370fe6aac9c574d0 

Branch pushed to git repo; I updated commit sha1. New commits:
c57069e  Recover still relevant warning message

comment:29 Changed 6 years ago by
Commit:  c57069e9c66ad4f28038744f370fe6aac9c574d0 → b31cfb0da764918d3ef34c23aaed3ec6793cdc18 

Branch pushed to git repo; I updated commit sha1. New commits:
b31cfb0  Make _cardinality_from_... cashed methods

comment:30 Changed 6 years ago by
Commit:  b31cfb0da764918d3ef34c23aaed3ec6793cdc18 → 0d4bc007a1892df12bf8167e2274d26d1422b87f 

Branch pushed to git repo; I updated commit sha1. New commits:
0d4bc00  Fix some doctest failures with optional tag

comment:31 Changed 6 years ago by
Status:  needs_review → needs_work 

comment:32 Changed 6 years ago by
Commit:  0d4bc007a1892df12bf8167e2274d26d1422b87f → 8c35940dec1fd70fcb59f87efabee486a9d44015 

Branch pushed to git repo; I updated commit sha1. This was a forced push. Last 10 new commits:
385f874  Fixes some doctest failures

7d938f4  Add a doctest string for Enumerated axiom

4e149ce  Patch a doctest failure in jordan algebra

9572573  Improve doctest coverage to attract patchbots

ec59bf5  Recover _cardinality_from_iterator and its test

eee9d5a  Remove degrading modifications to finite enumerated sets

be6c9c8  Recover still relevant warning message

e9a67f7  Make _cardinality_from_... cashed methods

10c757d  Fix some doctest failures with optional tag

8c35940  Fix some docstring failures and error messages

comment:33 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:34 Changed 6 years ago by
Commit:  8c35940dec1fd70fcb59f87efabee486a9d44015 → d20e9fc0e4f6dd68bedcf8d9ce0650af6e87617a 

Branch pushed to git repo; I updated commit sha1. New commits:
d20e9fc  Merge Sage 7.5.beta1 into trac20902

comment:35 followups: 37 38 Changed 6 years ago by
From a quick look at things, I don't like all of the @cached_method
's on __len__
because cardinality
should be quick to compute or list
is (generically) cached (and very fast to get the length of).
You should use ``self``
since it is essentially code.
This part of comment:22 is still true:
Also, I am slightly of the opinion that changing this behavior of enumerated sets with unknown cardinality is a regression. I believe that if the user knows the set is finite, they can do an explicit iteration over the object and we should force them to do that as a safeguard against the infinite loops.
Thinking about it a bit more, I am more convinced that this is a definite regression because it can cause infinite loops in cases that it previously did not.
comment:36 Changed 6 years ago by
Commit:  d20e9fc0e4f6dd68bedcf8d9ce0650af6e87617a → aa2fee9580ccbdc69be923f5ffde72ec18e0d4b6 

Branch pushed to git repo; I updated commit sha1. New commits:
aa2fee9  Removed unnecessary cached_methods

comment:37 Changed 6 years ago by
Replying to tscrim:
This part of comment:22 is still true:
Also, I am slightly of the opinion that changing this behavior of enumerated sets with unknown cardinality is a regression. I believe that if the user knows the set is finite, they can do an explicit iteration over the object and we should force them to do that as a safeguard against the infinite loops.
Thinking about it a bit more, I am more convinced that this is a definite regression because it can cause infinite loops in cases that it previously did not.
I don't really understand exactly what change you mean. Would you help me by pinpointing the method where the change was introduced? And a concrete example will also help.. Perhaps I forgot something that I myself have done.
comment:38 Changed 6 years ago by
Replying to tscrim:
Thinking about it a bit more, I am more convinced that this is a definite regression because it can cause infinite loops in cases that it previously did not
I now see that you meant catching TypeError
in the list method of enumerated sets.
comment:39 Changed 6 years ago by
Commit:  aa2fee9580ccbdc69be923f5ffde72ec18e0d4b6 → 2ce8115a0bcab799799cdcff99bb2931d6888a19 

comment:40 Changed 6 years ago by
Status:  needs_review → needs_work 

I made changes reflecting Travis' comments, perhaps except the last one.
comment:41 followup: 42 Changed 6 years ago by
The problem I have is if a set X
has unknown cardinality, then previously, if you call len(X)
, it would error out to prevent you from entering into an infinite loop. If I understand the current code, it will not do that, and instead try to compute the length (which generically would try X.list()
) and run into that infinite loop if X
was indeed infinite.
Before:
sage: R = RecursivelyEnumeratedSet([1], lambda a: [a+1]) sage: R.category() Category of enumerated sets sage: R.list()  NotImplementedError Traceback (most recent call last) ... NotImplementedError: unknown cardinality
With the branch:
sage: R = RecursivelyEnumeratedSet([1], lambda a: [a+1]) sage: R.list() # Still waiting...
Actually, __len__
is defined in RecursivelyEnumeratedSet
to return None
, but the same issue would occur if it was not.
comment:42 Changed 6 years ago by
Replying to tscrim:
The problem I have is if a set
X
has unknown cardinality, then previously, if you calllen(X)
, it would error out to prevent you from entering into an infinite loop. If I understand the current code, it will not do that, and instead try to compute the length (which generically would tryX.list()
) and run into that infinite loop ifX
was indeed infinite.
The current code for list
method and len
method for enumerated sets depend on cardinality
. If cardinality is not defined, it just tries to list all elements (as the doc says). So it falls into an infinite loop when the set is actually infinite, as you said and shown by your example. An easy solution would be to list elements only when the cardinality is known to be finite. I am now experimenting with the solution to see if it breaks other parts of Sage...
comment:43 Changed 6 years ago by
Commit:  2ce8115a0bcab799799cdcff99bb2931d6888a19 → 417a2f6745a57ef807c45e3864e025994772df84 

Branch pushed to git repo; I updated commit sha1. New commits:
417a2f6  Raise an exception for unknown cardinality

comment:44 Changed 6 years ago by
Status:  needs_work → needs_review 

comment:45 followup: 47 Changed 6 years ago by
Some little things:
cashed
>cached
 Add back in the descriptive error message of "unknown cardinality"
 This needs to be changed:
If ``x`` is known to be infinite, then an exception is raised. +If ``x`` is not known to be finite, then an exception is raised.
 I don't see the point of
__len__
insubword_complex.py
. If it is necessary, then it does not need to be cached and theEXAMPLES::
needs a blankline after it.  Same for
abelian_group.py
.  Same for
libgap_mixin.py
.  For
fgp_module.py
, theEXAMPLES::
block and you should use``self``
(although isn't this just_list_from_iterator
?).  In
homset.py
, use``self``
.  Same for
parent.pyx
.
comment:46 Changed 6 years ago by
Commit:  417a2f6745a57ef807c45e3864e025994772df84 → fb1c079703e990840750bca94933c2c2e871d6de 

Branch pushed to git repo; I updated commit sha1. New commits:
fb1c079  Minor fixes of docstrings

comment:47 followup: 48 Changed 6 years ago by
Replying to tscrim:
Some little things:
cashed
>cached
Done.
 Add back in the descriptive error message of "unknown cardinality"
Isn't this already there? Or do you mean somewhere else?
 This needs to be changed:
If ``x`` is known to be infinite, then an exception is raised. +If ``x`` is not known to be finite, then an exception is raised.
Done.
 I don't see the point of
__len__
insubword_complex.py
.
This would not be necessary if subword_complex
are in enumerated sets category (the same for below), but this ticket is not to put parents into proper category. This and removing unnecesary __len__
would be tasks of one who knows subword_complex
well.
 If it is necessary, then it does not need to be cached and the
EXAMPLES::
needs a blankline after it. Same for
abelian_group.py
. Same for
libgap_mixin.py
. For
fgp_module.py
, theEXAMPLES::
block and you should use``self``
(although isn't this just_list_from_iterator
?). In
homset.py
, use``self``
. Same for
parent.pyx
.
Done.
New commits:
fb1c079  Minor fixes of docstrings

comment:48 followup: 49 Changed 6 years ago by
Branch:  u/klee/20902 → public/categories/move_list_to_enumerated_sets20902 

Commit:  fb1c079703e990840750bca94933c2c2e871d6de → 4179fe4b05a8fba63d2ae189a50c1fb2a105e913 
Reviewers:  → Travis Scrimshaw 
Replying to klee:
Replying to tscrim:
 Add back in the descriptive error message of "unknown cardinality"
Isn't this already there? Or do you mean somewhere else?
Sorry, I had misread this diff:
+ sage: R.<t,p> = QQ[] + sage: Q = R.quotient(t^2t+1) + sage: Q.is_finite() Traceback (most recent call last): ...  NotImplementedError: unknown cardinality + NotImplementedError
 I don't see the point of
__len__
insubword_complex.py
.This would not be necessary if
subword_complex
are in enumerated sets category (the same for below), but this ticket is not to put parents into proper category. This and removing unnecesary__len__
would be tasks of one who knowssubword_complex
well.
The issue is that SubwordComplex
is a SimplicialComplex
, and while the latter is not an enumerated set, the former considers itself to be. However, SimplicialComplex
does not take a category as input. So I added this and put SubwordComplex
in the enumerated finite simplicial complexes category.
I also pushed some other improvements to the abelian groups and the libgap mixin groups. Although infinite abelian groups do not iterate properly, but that is a bug for another ticket.
New commits:
d5a8399  Making subword complex be an enumerated set.

4179fe4  Fixing some things exposed in abelian groups and libgap mixin.

comment:49 Changed 6 years ago by
Replying to tscrim:
The issue is that
SubwordComplex
is aSimplicialComplex
, and while the latter is not an enumerated set, the former considers itself to be. However,SimplicialComplex
does not take a category as input. So I added this and putSubwordComplex
in the enumerated finite simplicial complexes category.I also pushed some other improvements to the abelian groups and the libgap mixin groups. Although infinite abelian groups do not iterate properly, but that is a bug for another ticket.
The patch looks good to me. Thank you.
comment:51 Changed 6 years ago by
comment:52 Changed 6 years ago by
Commit:  4179fe4b05a8fba63d2ae189a50c1fb2a105e913 → bdbd034de6d3ebd7d922bcc68165ce18c2112888 

Branch pushed to git repo; I updated commit sha1. New commits:
bdbd034  Fixing some doctests due to changes of categories.

comment:53 Changed 6 years ago by
Status:  needs_review → positive_review 

Everything else looks good. I just did some trivial fixes from the patchbot report, so I'm allowing myself to set a positive review.
comment:54 Changed 6 years ago by
Branch:  public/categories/move_list_to_enumerated_sets20902 → bdbd034de6d3ebd7d922bcc68165ce18c2112888 

Resolution:  → fixed 
Status:  positive_review → closed 
Branch pushed to git repo; I updated commit sha1. New commits:
Move .list() to Sets category