Opened 7 years ago
Last modified 6 years ago
#15475 needs_work defect
Reenable broken doctests in #15473 and #15476 when #10963 is merged
Reported by:  darij  Owned by:  

Priority:  major  Milestone:  sage6.4 
Component:  categories  Keywords:  10963, categories, c3, coercion, transitivity, descent algebras, symmetric functions 
Cc:  nthiery, SimonKing, tscrim, sagecombinat  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 )
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 7 years ago by
comment:1 Changed 7 years ago by
 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:3 Changed 7 years ago by
 Cc tscrim added
comment:4 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:5 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:6 Changed 6 years ago by
 Branch set to public/combinat/15475
 Cc sagecombinat added
 Commit set to a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3
 Description modified (diff)
 Status changed from new to needs_review
 Type changed from task to defect
comment:7 Changed 6 years ago by
Needs_review now (finally). The review is really trivial.
comment:8 Changed 6 years ago by
 Branch changed from public/combinat/15475 to public/categories/15475
 Commit a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3 deleted
comment:9 Changed 6 years ago by
 Commit set to a3c4cf39c3625a311d72bf0c88e9bfbd028d74f3
Branch pushed to git repo; I updated commit sha1. New commits:
comment:10 Changed 6 years ago by
 Branch changed from public/categories/15475 to public/combinat/15475
Branch fixed, but more bughuntery in progress.
comment:11 Changed 6 years ago by
 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 6 years ago by
Here is the bug. First, let us doctest ncsf.py with this branch normally:
darij@travisvirtualbox:~/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/sitepackages/sage6.3.beta2py2.7.egginfo Writing /home/darij/gitsage6.2/local/lib/python2.7/sitepackages/sage6.3.beta2py2.7.egginfo Running doctests with ID 20140525093458fd673a84. 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@travisvirtualbox:~/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/sitepackages/sage6.3.beta2py2.7.egginfo Writing /home/darij/gitsage6.2/local/lib/python2.7/sitepackages/sage6.3.beta2py2.7.egginfo Running doctests with ID 20140525093519947fb6ad. 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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/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/sitepackages/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 6 years ago by
 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 6 years ago by
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 hardcoded coercions (which is the best solution, but the most work) to changing the doctests to mask this.
comment:15 followup: ↓ 16 Changed 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
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 6 years ago by
 Commit changed from ef918e33132d7bf77dd999696a0efd891d831377 to 7637ab232fb2ea5a4901cce4015ec4553eb69ef3
comment:20 Changed 6 years ago by
 Commit changed from 7637ab232fb2ea5a4901cce4015ec4553eb69ef3 to 0763ba5f5bd82948a08ab519f93bbe490d8743c2
Branch pushed to git repo; I updated commit sha1. New commits:
0763ba5  More fixes and doctests.

comment:21 followup: ↓ 23 Changed 6 years ago by
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 6 years ago by
 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 ; followup: ↓ 26 Changed 6 years ago by
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, butDAB
has not been. As such, the new coercion map does not get recreated, so the newSGA4
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 6 years ago by
 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 6 years ago by
 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 6 years ago by
 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 byB.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) byA.register_embedding(phi)
during creation of A, or it should be registered byB.register_coercion(phi)
during creation of B (not A), or should not be registered at all, lettingB._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 6 years ago by
@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 6 years ago by
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 6 years ago by
 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 6 years ago by
 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 6 years ago by
 Commit changed from ff4e546a838e9e9a4be86b3a89d8596658beb3f4 to da61e19ba32e4eb5f2348444df13edba50283b75
Branch pushed to git repo; I updated commit sha1. New commits:
da61e19  reenable SymmetricFunctions doctest

comment:32 followup: ↓ 33 Changed 6 years ago by
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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/sage/categories/category.py", line 2568, in _make_named_class cache=cache, **options) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/sage/categories/category.py", line 1221, in _make_named_class reduction = reduction, cache = cache) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/sage/doctest/forker.py", line 480, in _run self.execute(example, compiled, test.globs) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/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/sitepackages/sage/categories/category.py", line 2568, in _make_named_class cache=cache, **options) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/sage/categories/category.py", line 1221, in _make_named_class reduction = reduction, cache = cache) File "/home/darij/gitsage6.2/local/lib/python2.7/sitepackages/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/sitepackages/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 6 years ago by
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 6 years ago by
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/sitepackages/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/sitepackages/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 6 years ago by
On u/nthiery/15475sym_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 6 years ago by
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 followup: ↓ 38 Changed 6 years ago by
Definitely. Are you also planning to fix the bugs recently posted on sagedevel?
comment:38 in reply to: ↑ 37 Changed 6 years ago by
 Dependencies changed from #10963, #15473, #15476 to #10963, #15473, #15476, #16678
comment:39 Changed 6 years ago by
 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_coercions16678

31c8ac9  Additional fixes noted on sagedevel thread.

e1ff769  Fixed stupid mistake.

bf34154  Merge branch 'public/coercion/fix_sga_coercions16678' into public/categories/15475

comment:40 Changed 6 years ago by
 Milestone changed from sage6.3 to sage6.4
comment:41 followup: ↓ 42 Changed 6 years ago by
 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 years ago by
Replying to aapitzsch:
Currently, the branch
public/categories/15475
doesn't contain any changes compared withorigin/develop
.
Yes it does, it removes the # not tested
. However we do still need to make this handle the category refinement.
comment:43 Changed 6 years ago by
Another pathdependent 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 6 years ago by
We might be able to get a good workaround by finishing #15229.
comment:45 Changed 6 years ago by
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 lowerclass 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 6 years ago by
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 6 years ago by
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