Opened 15 months ago
Last modified 4 months ago
#15475 needs_work defect
Reenable broken doctests in #15473 and #15476 when #10963 is merged
Reported by: | darij | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-6.4 |
Component: | categories | Keywords: | 10963, categories, c3, coercion, transitivity, descent algebras, symmetric functions |
Cc: | nthiery, SimonKing, tscrim, sage-combinat | Merged in: | |
Authors: | Reviewers: | ||
Report Upstream: | N/A | Work issues: | |
Branch: | public/categories/15475 (Commits) | Commit: | bf3415442124b6778afdb799016efa4343c677b8 |
Dependencies: | #10963, #15473, #15476, #16678 | Stopgaps: |
Description (last modified by darij)
This branch activates two combinat doctests which were disabled due to unexplainable bugs that were fixed in #10963:
The following doctest is disabled pending :trac:`10963`:: sage: s = SymmetricFunctions(Zmod(14)).s() # not tested sage: s.is_integral_domain() # not tested False
and
sage: def descent_test(n): ....: DA = DescentAlgebra(QQ, n) ....: NSym = NonCommutativeSymmetricFunctions(QQ) ....: S = NSym.S() ....: DAD = DA.D() ....: w_n = DAD(set(range(1, n))) ....: for I in Compositions(n): ....: if not (S[I].star_involution() ....: == w_n * S[I].to_descent_algebra(n) * w_n): ....: return False ....: return True sage: all( descent_test(i) for i in range(4) ) # not tested True sage: all( descent_test(i) for i in range(6) ) # not tested True .. TODO:: Once :trac:`10963` is in, remove the first "not tested" above, and replace the second one by "long time".
Also, a few typos in the c3_controlled doc are fixed.
Disregard the attachment.
Attachments (1)
Change History (48)
Changed 15 months ago by darij
comment:1 Changed 15 months ago by darij
- Dependencies changed from #10963, #15473 to #10963, #15473, #15476
- Description modified (diff)
- Summary changed from Reenable broken doctest in #15473 when #10963 is merged to Reenable broken doctests in #15473 and #15476 when #10963 is merged
comment:2 Changed 15 months ago by darij
[obsolete]
comment:3 Changed 15 months ago by tscrim
- Cc tscrim added
comment:4 Changed 13 months ago by vbraun_spam
- Milestone changed from sage-6.1 to sage-6.2
comment:5 Changed 10 months ago by vbraun_spam
- Milestone changed from sage-6.2 to sage-6.3
comment:6 Changed 9 months ago by darij
- Branch set to public/combinat/15475
- Cc sage-combinat added
- Commit set to a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3
- Description modified (diff)
- Status changed from new to needs_review
- Type changed from task to defect
comment:7 Changed 9 months ago by darij
Needs_review now (finally). The review is really trivial.
comment:8 Changed 9 months ago by darij
- Branch changed from public/combinat/15475 to public/categories/15475
- Commit a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3 deleted
comment:9 Changed 9 months ago by git
- Commit set to a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3
Branch pushed to git repo; I updated commit sha1. New commits:
comment:10 Changed 9 months ago by darij
- Branch changed from public/categories/15475 to public/combinat/15475
Branch fixed, but more bughuntery in progress.
comment:11 Changed 9 months ago by darij
- Branch changed from public/combinat/15475 to public/categories/15475
- Commit changed from a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3 to ef918e33132d7bf77dd999696a0efd891d831377
- Status changed from needs_review to needs_work
New commits:
ef918e3 | #15475: doc fixes after #10963 |
comment:12 Changed 9 months ago by darij
Here is the bug. First, let us doctest ncsf.py with this branch normally:
darij@travis-virtualbox:~/gitsage6.2$ ./sage -bt src/sage/combinat/ncsf_qsym/ncsf.py scons: `install' is up to date. Updating Cython code.... Finished Cythonizing, time: 3.75 seconds. running install running build running build_py running build_ext Executing 0 commands (using 1 thread) Time to execute 0 commands: 0.00 seconds. Total time spent compiling C/C++ extensions: 0.08 seconds. running install_lib running install_egg_info Removing /home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage-6.3.beta2-py2.7.egg-info Writing /home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage-6.3.beta2-py2.7.egg-info Running doctests with ID 2014-05-25-09-34-58-fd673a84. Doctesting 1 file. sage -t src/sage/combinat/ncsf_qsym/ncsf.py [679 tests, 10.12 s] ---------------------------------------------------------------------- All tests passed! ---------------------------------------------------------------------- Total time for all tests: 10.4 seconds cpu time: 10.1 seconds cumulative wall time: 10.1 seconds
Now, let's do the --long test:
darij@travis-virtualbox:~/gitsage6.2$ ./sage -bt --long src/sage/combinat/ncsf_qsym/ncsf.py scons: `install' is up to date. Updating Cython code.... Finished Cythonizing, time: 3.88 seconds. running install running build running build_py running build_ext Executing 0 commands (using 1 thread) Time to execute 0 commands: 0.00 seconds. Total time spent compiling C/C++ extensions: 0.08 seconds. running install_lib running install_egg_info Removing /home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage-6.3.beta2-py2.7.egg-info Writing /home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage-6.3.beta2-py2.7.egg-info Running doctests with ID 2014-05-25-09-35-19-947fb6ad. Doctesting 1 file. sage -t --long src/sage/combinat/ncsf_qsym/ncsf.py ********************************************************************** File "src/sage/combinat/ncsf_qsym/ncsf.py", line 1520, in sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions.Bases.ElementMethods.to_symmetric_group_algebra Failed example: all( S[C].to_symmetric_group_algebra() == SGA4(D4(S[C].to_descent_algebra(4))) for C in Compositions(4) ) Exception raised: Traceback (most recent call last): File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute exec compiled in globs File "<doctest sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions.Bases.ElementMethods.to_symmetric_group_algebra[6]>", line 3, in <module> for C in Compositions(Integer(4)) ) File "<doctest sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions.Bases.ElementMethods.to_symmetric_group_algebra[6]>", line 3, in <genexpr> for C in Compositions(Integer(4)) ) File "parent.pyx", line 1083, in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8905) File "coerce_maps.pyx", line 95, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:4206) File "coerce_maps.pyx", line 90, in sage.structure.coerce_maps.DefaultConvertMap_unique._call_ (sage/structure/coerce_maps.c:4113) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/free_module.py", line 1577, in _element_constructor_ raise TypeError("do not know how to make x (= %s) an element of self (=%s)"%(x,self)) TypeError: do not know how to make x (= D{} + D{1} + D{1, 2} + D{1, 2, 3} + D{1, 3} + D{2} + D{2, 3} + D{3}) an element of self (=Symmetric group algebra of order 4 over Rational Field) ********************************************************************** 1 item had failures: 1 of 8 in sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions.Bases.ElementMethods.to_symmetric_group_algebra [686 tests, 1 failure, 116.10 s] ---------------------------------------------------------------------- sage -t --long src/sage/combinat/ncsf_qsym/ncsf.py # 1 doctest failed ---------------------------------------------------------------------- Total time for all tests: 116.4 seconds cpu time: 116.0 seconds cumulative wall time: 116.1 seconds
The failure was in a doctest which is not #long time!
There must be some coercion cache poisoning going on, probably similar to #15248, possibly connected to #10906. Any comments are welcome, since I don't have enough time for Sage these days.
comment:13 Changed 9 months ago by darij
- Keywords coercion transitivity descent algebras symmetric functions added
OK, here is a minimal(?) way to cause the bug. Copy this code:
def descent_test(n): DA = DescentAlgebra(QQ, n) DAD = DA.D() DAB = DA.B() DAD([]) for I in Compositions(n): DAD(DAB[I]) def maintest(): descent_test(3) descent_test(4) # you need both 3 and 4, IN THIS ORDER, to break it! SGA4 = SymmetricGroupAlgebra(QQ, 4) DAB = DescentAlgebra(QQ, 4).B() x = DAB[4] SGA4(x)
into a .py file and attach it. Run maintest(). You will get an error:
TypeError: do not know how to make x (= B[4]) an element of self (=Symmetric group algebra of order 4 over Rational Field)
Afterwards, try doing
sage: SGA4 = SymmetricGroupAlgebra(QQ, 4) sage: D4 = DescentAlgebra(QQ, 4).D() sage: SGA4.has_coerce_map_from(D4)
You get False, although in a virgin session it would be True. So it looks like either we have problems with UniqueRepresentation? and coercion, or the coercion graph has become too confusing for Sage to find a way (#15303?).
How do I debug a failed coercion? Is there a method that shows me a local coercion graph?
Also, I am no longer sure if the sfa.py issue has really been fixed or if #10963 has just kicked the can further down the road. Is there a sanity check for coercion graphs?
comment:14 Changed 9 months ago by tscrim
I feel like this is the same issue as #15309, in that calling DAD([]) makes it so that no coercions can be added dynamically (up to doing something extreme like overriding _coerce_map_from_()). So if this is indeed the case, either we need to have better hard-coded coercions (which is the best solution, but the most work) to changing the doctests to mask this.
comment:15 follow-up: ↓ 16 Changed 9 months ago by darij
Indeed...
sage: DAD = DescentAlgebra(QQ, 4).D() sage: DAD._coercions_used False sage: maintest() sage: DAD._coercions_used True
Hmm; what is _coercions_used and what is it good for? Why can't we just remove it?
EDIT: On the other hand, commenting out self._coercions_used = True in parent.pyx does not fix the error. But why do we have this kind of flag anyway? How on earth do we want to know if all coercions from/to a given objects are already known? Why on earth do we want this information?
comment:16 in reply to: ↑ 15 Changed 9 months ago by SimonKing
Replying to darij:
EDIT: On the other hand, commenting out self._coercions_used = True in parent.pyx does not fix the error. But why do we have this kind of flag anyway? How on earth do we want to know if all coercions from/to a given objects are already known? Why on earth do we want this information?
If I understand correctly, this flag is only relevant if we want to explicitly set a new coercion via register_coerce_map_from or something of that kind (can't look into the code right now). The idea is that the explicit registrations happens during initialisation, whereas the automatic discovery of coerce maps by backtracking happens later and is not hampered by self._coercions_used.
comment:17 Changed 9 months ago by tscrim
I believe the purpose of the flag is to try and prevent users from changing coercions dynamically:
sage: C = CombinatorialFreeModule(QQ, ['a','b']) sage: D = CombinatorialFreeModule(QQ, ['a','b']) sage: phi = C.module_morphism(D.monomial, codomain=D) sage: C.register_coercion(phi) sage: # D(C.monomial('a')) 'a' sage: def f(x): ....: if x == 'a': ....: return D.monomial('b') ....: return D.monomial('a') ....: sage: psi = C.module_morphism(f, codomain=D) sage: C.register_coercion(psi) sage: # D(C.monomial('a')) 'b'
comment:18 Changed 9 months ago by darij
Thanks@Simon, Travis.
Can anyone check if it is really this flag which causes the bug I described in comment:13? I still get the error without the flag. Thank you.
comment:19 Changed 8 months ago by git
- Commit changed from ef918e33132d7bf77dd999696a0efd891d831377 to 7637ab232fb2ea5a4901cce4015ec4553eb69ef3
comment:20 Changed 8 months ago by git
- Commit changed from 7637ab232fb2ea5a4901cce4015ec4553eb69ef3 to 0763ba5f5bd82948a08ab519f93bbe490d8743c2
Branch pushed to git repo; I updated commit sha1. New commits:
0763ba5 | More fixes and doctests. |
comment:21 follow-up: ↓ 23 Changed 8 months ago by tscrim
I've figured it out. The issue is that because we are not holding a strong reference to SGA4, it is being garbage collected, but DAB has not been. As such, the new coercion map does not get recreated, so the new SGA4 doesn't know about the (dynamically created) coercion:
sage: SGA4 = SymmetricGroupAlgebra(QQ, 4); DAB = DescentAlgebra(QQ, 4).B() sage: del SGA4 sage: import gc sage: gc.collect() 599 # Some number, not important sage: SGA4 = SymmetricGroupAlgebra(QQ, 4) # Now recreate it sage: x = DAB[4]; SGA4(x)
If you remove the del SGA4, it always works. I think the doctest runner is much more liberal about garbage collection which is why the test we had almost always failed.
Therefore I've fixed this by making the descent algebra hold a strong reference to the SGA (which it probably should irregardless).
This is now #16532.
comment:22 Changed 8 months ago by git
- Commit changed from 0763ba5f5bd82948a08ab519f93bbe490d8743c2 to db24a90327ef510be769d2ca92069037946b5e6e
Branch pushed to git repo; I updated commit sha1. New commits:
db24a90 | Fixed the issue...finally... Also some other minor cleanup. |
comment:23 in reply to: ↑ 21 ; follow-up: ↓ 26 Changed 8 months ago by SimonKing
Replying to tscrim:
I've figured it out. The issue is that because we are not holding a strong reference to SGA4, it is being garbage collected, but DAB has not been. As such, the new coercion map does not get recreated, so the new SGA4 doesn't know about the (dynamically created) coercion:
...
This is now #16532.
I have no time to look at the code now. But from the description at #16532, it seems to be the case that the coercion phi: A -> B is registered by B.register_coercion(phi) during creation of A, which would be a misuse. It should either be registered as the unique coerce embedding of A (if this makes sense) by A.register_embedding(phi) during creation of A, or it should be registered by B.register_coercion(phi) during creation of B (not A), or should not be registered at all, letting B._coerce_map_from_(A) do the job.
comment:24 Changed 8 months ago by git
- Commit changed from db24a90327ef510be769d2ca92069037946b5e6e to fb8c9c912c8c961a2ce983964371b3d04f296180
Branch pushed to git repo; I updated commit sha1. New commits:
fb8c9c9 | Added comment about register_embedding. |
comment:25 Changed 8 months ago by git
- Commit changed from fb8c9c912c8c961a2ce983964371b3d04f296180 to 702e7a19c9ec25f7af538fefb6fc7491a3adebd1
Branch pushed to git repo; I updated commit sha1. New commits:
702e7a1 | Changed to use _coerce_map_from_ and made it more robust/general. |
comment:26 in reply to: ↑ 23 Changed 8 months ago by tscrim
- Priority changed from minor to major
- Status changed from needs_work to needs_review
Replying to SimonKing:
I have no time to look at the code now. But from the description at #16532, it seems to be the case that the coercion phi: A -> B is registered by B.register_coercion(phi) during creation of A, which would be a misuse. It should either be registered as the unique coerce embedding of A (if this makes sense) by A.register_embedding(phi) during creation of A, or it should be registered by B.register_coercion(phi) during creation of B (not A), or should not be registered at all, letting B._coerce_map_from_(A) do the job.
I've changed it to use _coerce_map_from_ as this was the most robust with #15303 not being done (although I had to explicitly do the function composition). Thanks for clarifying.
Darij, final review.
comment:27 Changed 8 months ago by darij
@Travis: You use the canonical_embedding, which gives a module homomorphism, as a coercion in case of coercing but distinct base rings. But is this clean? I thought module homomorphisms would only work over the same base ring. I don't see what should go wrong, but it feels like relying on indefinite behavior...
Great job hunting down the bug! It is scary that these things can make stuff break in Sage, though...
comment:28 Changed 8 months ago by tscrim
Suppose you want phi : M -> N with M an R-module and N an S-module with a coercion R -> S. Then phi is a morphism in the category of R modules. canonical_embedding() takes care of this (albeit somewhat silently) by defining the morphism only on the basis vectors and extending by linearity (over R in this case).
comment:29 Changed 8 months ago by git
- Commit changed from 702e7a19c9ec25f7af538fefb6fc7491a3adebd1 to f662ae375916badfc7b46b2d3cce8a10df8b651e
Branch pushed to git repo; I updated commit sha1. New commits:
f662ae3 | documentation fixes to canonical_embedding of symmetric group algebra (yes, these maps aren't always embeddings, and the inequality was backwards) |
comment:30 Changed 8 months ago by git
- Commit changed from f662ae375916badfc7b46b2d3cce8a10df8b651e to ff4e546a838e9e9a4be86b3a89d8596658beb3f4
Branch pushed to git repo; I updated commit sha1. New commits:
ff4e546 | oops, another doc fix |
comment:31 Changed 8 months ago by git
- Commit changed from ff4e546a838e9e9a4be86b3a89d8596658beb3f4 to da61e19ba32e4eb5f2348444df13edba50283b75
Branch pushed to git repo; I updated commit sha1. New commits:
da61e19 | reenable SymmetricFunctions doctest |
comment:32 follow-up: ↓ 33 Changed 8 months ago by darij
OUCH. I just realized that I forgot to reenable the symmetric functions doctest, and not unexpectedly it is still broken. OK, this thing must be unrelated to #10963 after all. Simon, can you make sense of this?
Doctesting 1 file. sage -t src/sage/combinat/sf/sfa.py ********************************************************************** File "src/sage/combinat/sf/sfa.py", line 752, in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over Failed example: s.corresponding_basis_over(Integers(13)) Exception raised: Traceback (most recent call last): File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute exec compiled in globs File "<doctest sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over[5]>", line 1, in <module> s.corresponding_basis_over(Integers(Integer(13))) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sfa.py", line 814, in corresponding_basis_over return attrcall(self._basis)(SymmetricFunctions(R)) File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1282) File "cachefunc.pyx", line 1077, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6486) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1021, in __classcall__ instance = typecall(cls, *args, **options) File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1665) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py", line 763, in __init__ Parent.__init__(self, category = GradedHopfAlgebras(R).WithRealizations()) File "parent.pyx", line 358, in sage.structure.parent.Parent.__init__ (build/cythonized/sage/structure/parent.c:4247) File "parent.pyx", line 418, in sage.structure.parent.Parent._init_category_ (build/cythonized/sage/structure/parent.c:4797) File "lazy_attribute.pyx", line 127, in sage.misc.lazy_attribute._lazy_attribute.__get__ (build/cythonized/sage/misc/lazy_attribute.c:1353) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1298, in parent_class return self._make_named_class('parent_class', 'ParentMethods') File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 2568, in _make_named_class cache=cache, **options) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1221, in _make_named_class reduction = reduction, cache = cache) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 316, in dynamic_class return dynamic_class_internal.f(name, bases, cls, reduction, doccls, prepend_cls_bases) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 411, in dynamic_class_internal return metaclass(name, bases, methods) TypeError: Cannot create a consistent method resolution order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class ********************************************************************** File "src/sage/combinat/sf/sfa.py", line 758, in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over Failed example: mj.corresponding_basis_over(Integers(13)) Exception raised: Traceback (most recent call last): File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 839, in execute exec compiled in globs File "<doctest sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over[9]>", line 1, in <module> mj.corresponding_basis_over(Integers(Integer(13))) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sfa.py", line 814, in corresponding_basis_over return attrcall(self._basis)(SymmetricFunctions(R)) File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1282) File "cachefunc.pyx", line 1077, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:6486) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 1021, in __classcall__ instance = typecall(cls, *args, **options) File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1665) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/combinat/sf/sf.py", line 763, in __init__ Parent.__init__(self, category = GradedHopfAlgebras(R).WithRealizations()) File "parent.pyx", line 358, in sage.structure.parent.Parent.__init__ (build/cythonized/sage/structure/parent.c:4247) File "parent.pyx", line 418, in sage.structure.parent.Parent._init_category_ (build/cythonized/sage/structure/parent.c:4797) File "lazy_attribute.pyx", line 127, in sage.misc.lazy_attribute._lazy_attribute.__get__ (build/cythonized/sage/misc/lazy_attribute.c:1353) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1298, in parent_class return self._make_named_class('parent_class', 'ParentMethods') File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 2568, in _make_named_class cache=cache, **options) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/categories/category.py", line 1221, in _make_named_class reduction = reduction, cache = cache) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 316, in dynamic_class return dynamic_class_internal.f(name, bases, cls, reduction, doccls, prepend_cls_bases) File "/home/darij/gitsage6.2/local/lib/python2.7/site-packages/sage/structure/dynamic_class.py", line 411, in dynamic_class_internal return metaclass(name, bases, methods) TypeError: Cannot create a consistent method resolution order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class ********************************************************************** 1 item had failures: 2 of 43 in sage.combinat.sf.sfa.SymmetricFunctionsBases.ParentMethods.corresponding_basis_over [881 tests, 2 failures, 19.17 s] ---------------------------------------------------------------------- sage -t src/sage/combinat/sf/sfa.py # 2 doctests failed ----------------------------------------------------------------------
New commits:
da61e19 | reenable SymmetricFunctions doctest |
comment:33 in reply to: ↑ 32 Changed 8 months ago by SimonKing
Replying to darij:
OUCH. I just realized that I forgot to reenable the symmetric functions doctest, and not unexpectedly it is still broken. OK, this thing must be unrelated to #10963 after all. Simon, can you make sense of this?
TypeError: Cannot create a consistent method resolution order (MRO) for bases Algebras.parent_class, Monoids.WithRealizations.parent_class, Bialgebras.parent_class, Coalgebras.WithRealizations.parent_class
Does that mean that the controlled C3 algorithm is not bullet proof, resp. that the global ordering imposed on the categories is not as it should be? Nicolas?
comment:34 Changed 8 months ago by tscrim
I'm pretty sure it's related to the category refinement that occurs for Zmod(13):
sage: SymmetricFunctions(Zmod(14)) Symmetric Functions over Ring of integers modulo 14 sage: SymmetricFunctions(Zmod(12)) # This isn't needed to reproduce the error Symmetric Functions over Ring of integers modulo 12 sage: SymmetricFunctions(Zmod(13)) # Boom sage: Rp = Zmod(13) sage: Rp.category() Join of Category of finite commutative rings and Category of subquotients of monoids and Category of quotients of semigroups sage: Rp in Fields() True sage: Rp.category() Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups sage: SymmetricFunctions(Rp) Symmetric Functions over Ring of integers modulo 13
(You can remove the Rp.category() and it will still work.) Compare this with
sage: SymmetricFunctions(Zmod(12)) Symmetric Functions over Ring of integers modulo 12 sage: SymmetricFunctions(GF(13)) Symmetric Functions over Finite Field of size 13
However, in a fresh Sage:
sage: Rp = Zmod(13) sage: SymmetricFunctions(Rp) Symmetric Functions over Ring of integers modulo 13 sage: Rp.category() Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups
This might be useful info (also in a fresh Sage):
sage: GradedHopfAlgebras(Zmod(14)) Join of Category of hopf algebras over Ring of integers modulo 14 and Category of graded algebras over Ring of integers modulo 14 sage: Rp = Zmod(13) sage: GradedHopfAlgebras(Rp) /home/travis/sage/local/lib/python2.7/site-packages/sage/categories/category.py:858: UserWarning: Inconsistent sorting results for all super categories of <class 'sage.categories.category.JoinCategory'> self.__class__)) /home/travis/sage/local/lib/python2.7/site-packages/sage/categories/category.py:858: UserWarning: Inconsistent sorting results for all super categories of <class 'sage.categories.hopf_algebras.HopfAlgebras_with_category'> self.__class__)) Join of Category of hopf algebras over Ring of integers modulo 13 and Category of graded algebras over Ring of integers modulo 13 sage: Rp.category() Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups
comment:35 Changed 8 months ago by nthiery
On u/nthiery/15475-sym_in_categories_over_base_ring is a tentative workaround the MRO crash by making sym's category more independent of the base ring. Almost all tests pass in sage.combinat.sf, except for trivialities and a test involving QSym (which should probably get the same treatment).
comment:36 Changed 8 months ago by tscrim
Darij, would you be okay separating the current fixes of the descent and symmetric group algebras off as another ticket so we can get that in (everything up to ff4e546)?
comment:37 follow-up: ↓ 38 Changed 8 months ago by darij
Definitely. Are you also planning to fix the bugs recently posted on sage-devel?
comment:38 in reply to: ↑ 37 Changed 8 months ago by tscrim
- Dependencies changed from #10963, #15473, #15476 to #10963, #15473, #15476, #16678
comment:39 Changed 8 months ago by git
- Commit changed from da61e19ba32e4eb5f2348444df13edba50283b75 to bf3415442124b6778afdb799016efa4343c677b8
Branch pushed to git repo; I updated commit sha1. New commits:
7e564f2 | Merge branch 'public/categories/15475' of trac.sagemath.org:sage into public/categories/15475 |
b3d98ba | Merge commit 'ff4e546a838e9e9a4be86b3a89d8596658beb3f4' into public/coercions/fix_sga_coercions-16678 |
31c8ac9 | Additional fixes noted on sage-devel thread. |
e1ff769 | Fixed stupid mistake. |
bf34154 | Merge branch 'public/coercion/fix_sga_coercions-16678' into public/categories/15475 |
comment:40 Changed 7 months ago by vbraun_spam
- Milestone changed from sage-6.3 to sage-6.4
comment:41 follow-up: ↓ 42 Changed 6 months ago by aapitzsch
- Status changed from needs_review to needs_work
Currently, the branch public/categories/15475 doesn't contain any changes compared with origin/develop.
comment:42 in reply to: ↑ 41 Changed 6 months ago by tscrim
Replying to aapitzsch:
Currently, the branch public/categories/15475 doesn't contain any changes compared with origin/develop.
Yes it does, it removes the # not tested. However we do still need to make this handle the category refinement.
comment:43 Changed 4 months ago by darij
Another path-dependent MRO fail related to Hopf algebras over Zmod(n) observed in #11979. This shows that we should fix the category framework or our C3, or whatever else is at fault, rather than try to change Sym into a different category. (Are we actually using our controlled C3 here, or Python's old C3?)
comment:44 Changed 4 months ago by tscrim
We might be able to get a good workaround by finishing #15229.
comment:45 Changed 4 months ago by darij
That's good news! #15229 might actually be a fix for the root cause, not a workaround:
sage: SymmetricFunctions(Zmod(14)) Symmetric Functions over Ring of integers modulo 14 sage: Zmod(13) in Fields() # if not for this "check", then the following would break True sage: SymmetricFunctions(Zmod(13)) Symmetric Functions over Ring of integers modulo 13
and, for #11979:
sage: from sage.algebras.divided_power_algebra import UnivariateDividedPowerAlgebra sage: A = UnivariateDividedPowerAlgebra(Zmod(9)); A The divided power algebra over Ring of integers modulo 9 sage: Zmod(5) in Fields() # if not for this "check", then the following would break True sage: A = UnivariateDividedPowerAlgebra(Zmod(5)); A The divided power algebra over Ring of integers modulo 5
So my guess would be that category refinement doesn't like it when a category changes in the midst of it, and the category of Zmod(n) does change when Zmod(n) is tested for fieldness:
sage: Zmod(17).category() Join of Category of finite commutative rings and Category of subquotients of monoids and Category of quotients of semigroups sage: Zmod(17) in Fields() True sage: Zmod(17).category() Join of Category of finite fields and Category of subquotients of monoids and Category of quotients of semigroups
With #15229 fixing this, I think we can hope to see the end of this issue.
Is this pattern, where an object lazily starts off with a broad category and then refines in when the user checks for properties, common in Sage? Should we get rid of that or tweak the code to allow it? If we are to allow it, we would probably need to establish a hierarchy of categories or classes such that refining a category of some object can only trigger refinements of categories of lower-class objects in its process, and said refinements should be made sure not to interfere or run races with each other?
EDIT: I also wanted to add that this whole tradeoff between "allow several instances of ZZ/nZZ with different properties, and try to somehow ensure that they behave like they are equal, e.g., providing automatic coercion between their polynomial rings" and "force all instances of ZZ/nZZ to be identical, at the cost of having to update and mutate this single instance long after it is created, and try to somehow ensure that these mutations do not break consistency" reminds me a lot of the constructivity problem of Voevodsky's univalent foundations. Looks like equality is the trickiest thing to formalize...
comment:46 Changed 4 months ago by tscrim
This is great to hear. I've rebased #15229, so hopefully that will get in soon so we can (finally) close this.
comment:47 Changed 4 months ago by darij
OK, this actually didn't help. :/ What I meant by #15229 fixing this is that the source of this bug was discussed in the #15229 thread. But it wasn't solved there, because with #15229 I still have:
sage: len(Zmod(5).categories()) 42 sage: Zmod(5).is_field() True sage: len(Zmod(5).categories()) 51
Either this lazy discovery of categories has to be removed, or the category refinement and MRO routines must be hardened against it.
just documentation typos that i fixed when i was reading it