Closed nthiery closed 9 years ago
simon-king-jena
commented
10 years ago Replying to @nthiery:
Thanks for all your work on the review of this ticket! I am currently on vacations, so my answers might be slow.
So am I. Perhaps I can try to provide a proof of concept, IF I manage to deal with the scenario that you mentioned.
Have nice holidays!
Simon
simon-king-jena
commented
10 years ago Replying to @nthiery:
The reason to call "join" is indeed to get the correct supercategories for
C.MyAxiom(). Note that, on the other hand and unless I screwed up somewhere, there should be noJoinCategoryproduced (unless of course the end result ofC.MyAxiom()itself is such aJoinCategory).
Really? So, then I was mislead by a couple of doctests that demonstrate that a certain category is in fact a join category, even though it is not printed as such, and also mislead by the code that uses self._with_axiom_categories(...), which I thought does in fact form a join.
simon-king-jena
commented
10 years ago Hi Nicolas,
Replying to @nthiery:
- C is a super category of A and B
A.MyAxiom()impliesA.MyOtherAxiom()B.MyOtherAxiom()is non trivial
I suppose you mean: C is a sub-category of A and B.
What is an axiom?
First of all, I wonder if we have the same understanding of "axiom". For me, an axiom is defined in terms of an algebraic structure that is provided by a certain category without this axiom. In particular A.Associative() is actually not well-defined: One should in theory have A.MultiplicativeAssociative(), where MultiplicativeAssociative is provided by Magmas(), or A.AdditiveAssociative(), where AdditiveAssociative is provided by AdditiveMagmas().
Granted, if A=Algebras(ZZ), then A.Associative() should be synonym of A.MultiplicativeAssociative(). So, we might want to introduce reasonable short-cuts in some cases.
Your Example
Now, in your example, if MyAxiom is defined for both A and B, then the meet of A and B is a sub-category of a category M, for which MyAxiom and MyOtherAxiom are defined. In your example, MyAxiom implies MyOtherAxiom for A but not for B. Hence, A can be written as a sub-category of M.SpecialAxiom(), and SpecialAxiom together with MyAxiom implies MyOtherAxiom.
Now, you consider a category C defined by C.__class__(data), which is a common sub-category of A and B, and you wonder about the super-categories of C.MyAxiom().
Since A satisfies SpecialAxiom, C satisfies it as well. Hence, D = C.MyAxiom()will also satisfy MyOtherAxiom. I guess the logic of this implication is encoded in the way how D.__class__._used_axioms is determined. Hence, D.__class__._used_axioms contains SpecialAxiom, MyAxiom and MyOtherAxiom.
In a previous post, I presented an algorithm for determining D.super_categories(). Let us study what it will return. Recall that it returns D._without_axiom(axiom) for all axiom in D.__class__._used_axioms, after removing duplicates. Hence:
axiom=SpecialAxiom: We go along the mro of D.__class__ until we find something that does not have SpecialAxiom. This will be a certain super-category X of C that is a sub-category of B (supposing that B does not satisfy SpecialAxiom). This will result in X....MyAxiom().MySpecialAxiom(), applying all axioms (except SpecialAxiom) that hold for D but not for X.axiom=MyAxiom: This will yield C.MyOtherAxiom().axiom=MyOtherAxiom: This will yield C.MyAxiom(), which coincides with D and is thus removed as a duplicate.Note that in this explanation I have modified my previous suggestion for D._without_axiom(this_axiom): We can not expect that D.__class__.__mro__ provides something that has the same axioms than D, with just this_axiom omitted. But since applying axioms commutes, it is fine to take the first class in D.__class__.__mro__ that does not have this_axiom, and then create a category from this class (with the known input data of D), and apply all other missing axioms.
Anyway, I think that the above answer to C.MyAxiom().super_categories() looks fine. Or what else would you like to have?
Cheers,
Simon
simon-king-jena
commented
10 years ago I guess I should re-think the above in a more concrete scenario. Let D = DivisionRings(). What do we do with D.Finite()?
Would we agree on D = Rings().WithMultiplicativeInverses()? I guess we would obtain Fields()=D.Commutative(). So, as in the situation above, we have the rule that if WithMultiplicativeInverses() is applied to Rings(), then the additional axiom Finite() implies the axiom Commutative().
Hence, D.Finite() yields Fields().Finite()=FiniteFields(). To be discussed: Should this be created dynamically, or should there be a hard-coded separate class definition?
So, what would FiniteFields().super_categories() return by the algorithm I presented above?
Commutative: We still have the axioms WithMultiplicativeInverses and Finite, hence, we recover FiniteFields(), which is thus a duplicate and not part of FiniteFields().super_categories().Finite: The remaining axioms are those of commutative division rings, which yields Fields().WithMultiplicativeInverses: Yields finite commutative rings.So, FiniteFields().super_categories()returns [Fields(), Rings().Commutative().Finite()]. Do you think this answer makes sense?
simon-king-jena
commented
10 years ago Replying to @simon-king-jena:
So,
FiniteFields().super_categories()returns[Fields(), Rings().Commutative().Finite()]. Do you think this answer makes sense?
Actually I'd like this answer more than the current answers.
Without your patch:
sage: FiniteFields().super_categories()
[Category of fields, Category of finite enumerated sets]With your patch:
sage: FiniteFields().super_categories()
[Category of fields, Category of finite monoids]It seems to me that
sage: FiniteFields().super_categories()
[Category of fields, Category of finite commutative rings]would be more accurate.
nthiery
commented
10 years ago Replying to @simon-king-jena:
It seems to me that
sage: FiniteFields().super_categories() [Category of fields, Category of finite commutative rings]would be more accurate.
But this would mean constructing a trivial category for finite commutative rings (there is currently no category code for finite commutative rings). The point of the axioms infrastructure is precisely to avoid such trivial categories in the category hierarchy in order to prevent the potential combinatorial explosion.
Besides: should this be finite commutative rings? Or finite domains? Or finite euclidean rings? ...
simon-king-jena
commented
10 years ago Replying to @nthiery:
But this would mean constructing a trivial category for finite commutative rings (there is currently no category code for finite commutative rings).
That's the point: In my approach, this category would be constructed on the fly, by means of a dynamic construction.
Besides: should this be finite commutative rings? Or finite domains? Or finite euclidean rings? ...
To be discussed. In the end of the day, this is a matter of what axioms we have for fields that do not hold for all division rings, and which are thus implied by adding Finite() to Rings().Division().
However, I do think that the category of finite commutative rings should be a super-category of the category of finite fields. But (with your patch):
sage: Rings().Commutative().Finite() in Fields().Finite().all_super_categories()
Falseeven though
sage: (Fields().Finite()).is_subcategory(Rings().Commutative().Finite())
TrueReplying to @simon-king-jena:
I suppose you mean: C is a sub-category of A and B.
Oops, yes, sure.
What is an axiom?
First of all, I wonder if we have the same understanding of "axiom". For me, an axiom is defined in terms of an algebraic structure that is provided by a certain category without this axiom.
Yes.
In particular
A.Associative()is actually not well-defined: One should in theory haveA.MultiplicativeAssociative(), whereMultiplicativeAssociativeis provided byMagmas(), orA.AdditiveAssociative(), whereAdditiveAssociativeis provided byAdditiveMagmas(). Granted, ifA=Algebras(ZZ), thenA.Associative()should be synonym ofA.MultiplicativeAssociative(). So, we might want to introduce reasonable short-cuts in some cases.
Of course. But that would be heavy and require to have an infrastructure for shortcuts. So I just followed the previously set convention (as in CommutativeRings w.r.t CommutativeAdditiveMonoids): by default, the associative/commutative/unital/... axioms are about the multiplicative structure, and I think that's ok.
Your Example
Now, in your example, if
MyAxiomis defined for both A and B, then the meet of A and B is a sub-category of a category M, for whichMyAxiomandMyOtherAxiomare defined. In your example,MyAxiomimpliesMyOtherAxiomfor A but not for B. Hence, A can be written as a sub-category ofM.SpecialAxiom(), andSpecialAxiomtogether withMyAxiomimpliesMyOtherAxiom.Now, you consider a category C defined by
C.__class__(data), which is a common sub-category of A and B, and you wonder about the super-categories ofC.MyAxiom().Since A satisfies
SpecialAxiom, C satisfies it as well. Hence,D = C.MyAxiom()will also satisfyMyOtherAxiom. I guess the logic of this implication is encoded in the way howD.__class__._used_axiomsis determined. Hence,D.__class__._used_axiomscontainsSpecialAxiom,MyAxiomandMyOtherAxiom.In a previous post, I presented an algorithm for determining
D.super_categories(). Let us study what it will return. Recall that it returnsD._without_axiom(axiom)for all axiom inD.__class__._used_axioms, after removing duplicates. Hence:
axiom=SpecialAxiom: We go along the mro ofD.__class__until we find something that does not haveSpecialAxiom. This will be a certain super-category X of C that is a sub-category of B (supposing that B does not satisfySpecialAxiom). This will result inX....MyAxiom().MySpecialAxiom(), applying all axioms (exceptSpecialAxiom) that hold for D but not for X.axiom=MyAxiom: This will yieldC.MyOtherAxiom().axiom=MyOtherAxiom: This will yieldC.MyAxiom(), which coincides with D and is thus removed as a duplicate.Note that in this explanation I have modified my previous suggestion for
D._without_axiom(this_axiom): We can not expect thatD.__class__.__mro__provides something that has the same axioms than D, with justthis_axiomomitted. But since applying axioms commutes, it is fine to take the first class inD.__class__.__mro__that does not havethis_axiom, and then create a category from this class (with the known input data of D), and apply all other missing axioms.Anyway, I think that the above answer to
C.MyAxiom().super_categories()looks fine. Or what else would you like to have?
Honestly I don't have the time to check all the details. If you believe that computing A.Axiom() is intrinsically simpler than computing a join (I don't and would favor optimizing join instead), feel free to write a prototype. The test suite in category_with_axiom.py should be a good guide. Just be warned that it took me a good two weeks of solid work to get things right, and that after at least two iterations :-)
Enjoy your vacations too!
nthiery
commented
10 years ago Replying to @simon-king-jena:
Replying to @nthiery:
But this would mean constructing a trivial category for finite commutative rings (there is currently no category code for finite commutative rings).
That's the point: In my approach, this category would be constructed on the fly, by means of a dynamic construction.
We do not even want to construct it on the fly! FiniteFields satisfies at least four axioms that can apply to Magmas (Associative, Finite, Unital, Commutative). We do not want the category hierarchy above FiniteFields to contain {2^4} categories (most of which being trivial) just for Magmas. And that many for additive magmas.
To be discussed. In the end of the day, this is a matter of what axioms we have for fields that do not hold for all division rings, and which are thus implied by adding
Finite()toRings().Division().
Note that this is currently resolved automatically by the current mechanism by looking which axioms are defined/implemented by the various categories.
However, I do think that the category of finite commutative rings should be a super-category of the category of finite fields. But (with your patch):
sage: Rings().Commutative().Finite() in Fields().Finite().all_super_categories() Falseeven though
sage: (Fields().Finite()).is_subcategory(Rings().Commutative().Finite()) True
Which is exactly what I want since finite commutative rings is trivial, and realized as a join category. There is no point in adding join categories in all_super_categories.
Cheers, Nicolas
simon-king-jena
commented
10 years ago Replying to @nthiery:
Replying to @simon-king-jena:
That's the point: In my approach, this category would be constructed on the fly, by means of a dynamic construction.
We do not even want to construct it on the fly! FiniteFields satisfies at least four axioms that can apply to Magmas (Associative, Finite, Unital, Commutative). We do not want the category hierarchy above FiniteFields to contain {2^4} categories (most of which being trivial) just for Magmas.
OK, that's a considerable change. In the "good" old times, a category C was (by definition) a sub-category of another category D, if and only if D was contained in C.all_super_categories(). So, you say this shall change (or already has?).
Which is exactly what I want since finite commutative rings is trivial, and realized as a join category. There is no point in adding join categories in all_super_categories.
OK, it somehow convinces me that we don't want to create categories "on the fly" that do not provide any additional information (methods etc) beyond the categories that were created anyway.
But then, I still don't see why this should be implemented by a plain join category.
Do we agree that there is a category Magmas().Commutative(), such that all information on Algebras(ZZ).Commutative() is provided by Algebras(ZZ) together with Magmas().Commutative()? Sure, we could then implement Algebras(ZZ).Commutative() by a JoinCategory.
But then, I would expect that we can have a class which is similar to JoinCategory but is specially designed and thus faster. After all, creating the join of a list of categories should be more complicated then adding a list of "axiom categories" (such as Magmas().Commutative() and Magmas().Division() and Sets().Finite()) to a given category (such as Rings()).
Anyway, I think my original suggestion of creating classes for categories-with-axiom on the fly was probably not so good. But I think I will try to experiment with the other idea (using a specially designed "mock join" for adding axioms).
simon-king-jena
commented
10 years ago Replying to @simon-king-jena:
After all, creating the join of a list of categories should be more complicated then adding a list of "axiom categories" (such as
Magmas().Commutative()andMagmas().Division()andSets().Finite()) to a given category (such asRings()).
Or perhaps rather Rngs().Division(), because we ask for inverses for all non-zero elements, hence Division() requires a category that has a notion of a zero and is at the same time a multiplicative monoid.
simon-king-jena
commented
10 years ago A question:
Why should we have a hard-coded category Fields(), if all information is encoded in the combination of Rings().Division() and Rings().Commutative()? Should we not aim at removing sage.categories.fields if we take the axiomatic approach serious?
simon-king-jena
commented
10 years ago And a more general question we should answer: What is the semantics of super_categories()?
It used to be like this, if I understood correctly: C.super_categories() should return a list of all categories S1, S2, ... constructible in Sage such that C is a proper sub-category of S1, S2, ... and there is no category D constructible in Sage such that C is a proper sub-category of D and D is a proper sub-category of any of the S1, S2, ....
The problem with this old meaning of C.super_categories() is, of course, that "constructible in Sage" is a moving target, and hence it won't scale.
Now it seems that you want to change the old semantics, and I wonder about the exact definition of the new semantics.
It seems to me that you suggest the following: C.super_categories() shall return categories S1, S2, ... such that C is a proper sub-category of S1, S2, ..., and such that all "named classes" of C (i.e., results of calls to C._make_named_class(...)) can be constructed from the corresponding named classes of S1, S2, ... and from attributes of C.__class__ (for example, from C.__class__.ParentMethods)?
nthiery
commented
10 years ago Replying to @simon-king-jena:
OK, that's a considerable change. In the "good" old times, a category C was (by definition) a sub-category of another category D, if and only if D was contained in
C.all_super_categories(). So, you say this shall change (or already has?).
This was already like this for join categories. E.g. with plain sage 5.11.beta3:
sage: C1 = Category.join([Magmas(), CommutativeAdditiveMonoids()])
sage: C2 = Rings()
sage: C2.is_subcategory(C1)
TrueBut then, I still don't see why this should be implemented by a plain join category.
Do we agree that there is a category
Magmas().Commutative(), such that all information onAlgebras(ZZ).Commutative()is provided byAlgebras(ZZ)together withMagmas().Commutative()?
Those two pieces are indeed sufficient to recover the category:
sage: C = Algebras(ZZ) & Magmas().Commutative(); C
Category of commutative algebras over Integer RingBut the join calculation is non trivial since Sage discovers by introspection that there is a specific category for commutative rings, so we get:
sage: C.super_categories()
[Category of algebras over Integer Ring, Category of commutative rings]Granted, the example is not so great since the commutative rings category is actually currently empty; so we could think about removing it, though it's likely to eventually contain something. For a more interesting example we can look at:
Maybe a better example is:
sage: Rings().Finite().super_categories()
[Category of rings, Category of finite monoids]And some good tests (compare with the sources!):
sage: from sage.categories.category_with_axiom import TestObjectsOverBaseRing
sage: C = TestObjectsOverBaseRing(QQ)
sage: C.Facade().Commutative().FiniteDimensional().Finite().Unital().super_categories()
[Category of finite finite dimensional test objects over base ring over Rational Field,
Category of finite commutative test objects over base ring over Rational Field,
Category of facade commutative test objects over base ring over Rational Field,
Category of finite dimensional commutative unital test objects over base ring over Rational Field]
sage: C.Facade().Commutative().Finite().Unital().super_categories()
[Category of finite commutative test objects over base ring over Rational Field,
Category of facade commutative test objects over base ring over Rational Field,
Category of unital test objects over base ring over Rational Field]Sure, we could then implement
Algebras(ZZ).Commutative()by aJoinCategory.But then, I would expect that we can have a class which is similar to
JoinCategorybut is specially designed and thus faster. After all, creating the join of a list of categories should be more complicated then adding a list of "axiom categories" (such asMagmas().Commutative()andMagmas().Division()andSets().Finite()) to a given category (such asRings()).
I guess I don't see at this point what can be made really simpler/lighter for a join category when it comes from adding axioms to a category. I still believe we can't spare the join calculation.
Cheers, Nicolas
nthiery
commented
10 years ago Replying to @simon-king-jena:
Or perhaps rather
Rngs().Division(), because we ask for inverses for all non-zero elements, henceDivision()requires a category that has a notion of a zero and is at the same time a multiplicative monoid.
Yes; and pushing your argument to its conclusion that could even be DistributiveMagmasAndAssociativeMagmas().AdditiveUnital().Division(). I guess DivisionRing will do for now.
nthiery
commented
10 years ago Replying to @simon-king-jena:
Why should we have a hard-coded category
Fields(), if all information is encoded in the combination ofRings().Division()andRings().Commutative()? Should we not aim at removing sage.categories.fields if we take the axiomatic approach serious?
Fields is already implemented as a CategoryWithAxiom. But it's a non trivial category (there are quite a few parent and element methods), so we want to keep it around.
Cheers, Nicolas
nthiery
commented
10 years ago Replying to @simon-king-jena:
And a more general question we should answer: What is the semantics of
super_categories()?It used to be like this, if I understood correctly:
C.super_categories()should return a list of all categoriesS1, S2, ...constructible in Sage such that C is a proper sub-category ofS1, S2, ...and there is no category D constructible in Sage such that C is a proper sub-category of D and D is a proper sub-category of any of theS1, S2, ....
I very much like this definition, and think it's still perfectly up to date. Maybe one would use "implemented in Sage" rather than "constructible in Sage" to rule out join categories.
(a short rephrasing is that super_cartegories give the covering relations in the poset of implemented categories in Sage).
The only difference after this ticket is that there is a new syntax to
implement a category, e.g. Blahs().Finite(), as:
class Blahs(Category):
class Finite(CategoryWithAxiom):but that's not really different from what we were already doing for
e.g. Blahs().CartesianProducts().
The problem with this old meaning of
C.super_categories()is, of course, that "constructible in Sage" is a moving target, and hence it won't scale.
Let me rephrase this as: since "constructible in Sage" is a moving
target, maintaining by hand the information in super_categories()
often does not scale. So whenever possible, super_categories
should be calculated automatically.
Cheers, Nicolas
simon-king-jena
commented
10 years ago Replying to @nthiery:
Fields is already implemented as a CategoryWithAxiom. But it's a non trivial category (there are quite a few parent and element methods), so we want to keep it around.
Sure it has quite a few parent and element methods. But the point is: Since the category of fields is nothing but Rings().Division().Commutative(), all these methods should be defined somewhere else.
simon-king-jena
commented
10 years ago Replying to @nthiery:
Replying to @simon-king-jena:
OK, that's a considerable change. In the "good" old times, a category C was (by definition) a sub-category of another category D, if and only if D was contained in
C.all_super_categories(). So, you say this shall change (or already has?).This was already like this for join categories.
You're right. But I think this has been the only exception.
simon-king-jena
commented
10 years ago Replying to @nthiery:
Replying to @simon-king-jena:
And a more general question we should answer: What is the semantics of
super_categories()?It used to be like this, if I understood correctly:
C.super_categories()should return a list of all categoriesS1, S2, ...constructible in Sage such that C is a proper sub-category ofS1, S2, ...and there is no category D constructible in Sage such that C is a proper sub-category of D and D is a proper sub-category of any of theS1, S2, ....I very much like this definition, and think it's still perfectly up to date.
This totally surprises me now.
Back to the Fields().Finite().super_categories() example. I have argued that we have a couple of axioms, and keeping all axioms but one gives us a list that (after removing duplicates) gives us a list of super categories that exactly follows the specification above. And in comment:51, I have shown that this definition more or less forces us to have Fields().Finite().super_categories() = [Category of fields, Category of finite commutative rings].
And you argued against this answer (because of having 24 many additional "empty" categories in the list of all super categories). You seemed to be in favour of Fields().Finite().super_categories() = [Category of fields, Category of finite enumerated sets].
Actually, this is why I came up with the other specification of C.super_categories(). That's why it surprises me that you now say you like this specification less.
nthiery
commented
10 years ago Replying to @simon-king-jena:
This totally surprises me now.
Hmm, it feels like there is a rolling confusion here :-) Trac communication is not so easy!
Back to the
Fields().Finite().super_categories()example. I have argued that we have a couple of axioms, and keeping all axioms but one gives us a list that (after removing duplicates) gives us a list of super categories that exactly follows the specification above. And in comment:51, I have shown that this definition more or less forces us to haveFields().Finite().super_categories() = [Category of fields, Category of finite commutative rings].And you argued against this answer (because of having 24 many additional "empty" categories in the list of all super categories). You seemed to be in favour of
Fields().Finite().super_categories() = [Category of fields, Category of finite enumerated sets].
Yes and no: I indeed don't want all 24 potential categories. But I do want those that are implemented in Sage. In the current state, we have no category implemented for finite commutative rings (in other words, Rings().Commutative().Finite() is a join category), but we do have one for finite monoids (in Monoids.Finite). Hence the current answer:
[Category of fields, Category of finite monoids]
Cheers,
nthiery
commented
10 years ago Replying to @simon-king-jena:
You're right. But I think this has been the only exception.
And this still is the only exception: Rings().Commutative().Finite() is a join category.
sage: type(Rings().Finite().Commutative())
<class 'sage.categories.category.JoinCategory_with_category'>Replying to @simon-king-jena:
Sure it has quite a few parent and element methods. But the point is: Since the category of fields is nothing but
Rings().Division().Commutative(), all these methods should be defined somewhere else.
Where else? Of course some of the methods currently in Fields might actually work in a more general setting and could be lifted to some super categories. But others are really about fields (like the trivial is_field :-)), so that's their natural spot, isn't it?
Btw:
sage: Rings.Division.Commutative
<class 'sage.categories.fields.Fields'>Hi Simon!
Back to work after some good vacations :-)
The updated patch includes a complete refactoring of the primer and fixes the continuations in docstrings as reported by the patchbot. The next step is to handle the renaming of NonAssociativeNonUnitalAlgebras.
Did you manage to reproduce the doctest errors reported by the patchbot about recursion loop?
Cheers, Nicolas
nthiery
commented
10 years ago Changed work issues from Reduce startup time by 5%. Avoid "recursion depth exceeded (ignored)". Trivial doctest fixes. to Rename NonAssociativeNonUnitalAlgebras. Reduce startup time by 5%. Avoid "recursion depth exceeded (ignored)".
nthiery
commented
10 years ago What shall we do about #9107 (mangling of nested class names)? The dependency is rather trivial: just a doctests or two to update.
nthiery
commented
10 years ago Changed work issues from Rename NonAssociativeNonUnitalAlgebras. Reduce startup time by 5%. Avoid "recursion depth exceeded (ignored)". to RenReduce startup time by 5%. Avoid "recursion depth exceeded (ignored)".
nthiery
commented
10 years ago The updated patch also fixes doctests in the primer (I had forgotten to run the tests after the revamping).
nthiery
commented
10 years ago Replacing the current Algebras by MagmaticAlgebras is now the follow up #15043.
nthiery
commented
10 years ago Changed work issues from RenReduce startup time by 5%. Avoid "recursion depth exceeded (ignored)". to Rename NoReduce startup time by 5%. Avoid "recursion depth exceeded (ignored)".
nthiery
commented
10 years ago Changed work issues from Rename NoReduce startup time by 5%. Avoid "recursion depth exceeded (ignored)". to Reduce startup time by 5%. Avoid "recursion depth exceeded (ignored)".
nthiery
commented
10 years ago Reworked the renaming: we might as well use directly AssociativeAlgebras rather than AssociativeMagmaticAlgebras. I added appropriate pointers to #15043.
nthiery
commented
10 years ago Description changed:
---
+++
@@ -1,21 +1,40 @@
-The patch under finalization on the Sage-Combinat queue implements:
+This ticket implements:
-- Support for full subcategories defined by a predicate on the objects
- (Finite, Infinite, FiniteDimensional, Commutative, Graded, Facade),
- and joins thereof:
+- Support for full subcategories defined by an axiom (Finite,
+ Infinite, FiniteDimensional, Commutative, Associative, Unital,
+ Inverse, NoZeroDivisors, Division, Facade), and joins thereof:
+- New categories:
Algebras of additive semigroups and monoids
More mathematical rules:
A subquotient of a finite set is a finite set
The algebra of a finite set is finite dimensional
The algebra of a commutative magma is commutative -- Algebras of commutative additive semigroups and monoids
-See http://combinat.sagemath.org/patches/file/tip/trac_10963-more_functorial_constructions-nt.patch and follow ups. +- Complete revamping of sage.categories.primer + +- Use SubcategoryMethods to put the functorial constructions where
+Patch developed on: http://combinat.sagemath.org/patches/file/tip/trac_10963-more_functorial_constructions-nt.patch.
Description changed:
---
+++
@@ -1,8 +1,9 @@
This ticket implements:
- Support for full subcategories defined by an axiom (Finite,
- Infinite, FiniteDimensional, Commutative, Associative, Unital,
- Inverse, NoZeroDivisors, Division, Facade), and joins thereof:
+ Infinite, Facade, Commutative, Associative, Unital,
+ Inverse, NoZeroDivisors, Division, FiniteDimensional, Connected,
+ WithBasis, Irreducible), and joins thereof:
sage: Groups() & Sets().Finite()Description changed:
---
+++
@@ -29,13 +29,16 @@
- A finite division ring is a field
- ...
-- More documentation for IsomorphicObjects and other doc improvements
-
-- Complete revamping of sage.categories.primer
+- Documentation:
+ - More documentation for IsomorphicObjects
+ - Complete revamping of sage.categories.primer
+ - Misc
- Use SubcategoryMethods to put the functorial constructions where
they belong. E.g. DualObjects, TensorProducts, and Graded are now
only defined for subcategories of Modules.
+- More lazy imports, removed a bunch of unused imports, ...
+
Patch developed on: http://combinat.sagemath.org/patches/file/tip/trac_10963-more_functorial_constructions-nt.patch.
Hi Simon,
Let me know when you will be back to reviewing this patch, and I'll be more careful with providing incremental patches.
My recent changes concern:
I am now going to try to investigate the "recursion" errors.
simon-king-jena
commented
10 years ago Hi Nicolas,
concerning the notion of "super_categories":
Replying to @nthiery:
Replying to @simon-king-jena:
You're right. But I think this has been the only exception.
And this still is the only exception:
Rings().Commutative().Finite()is a join category.sage: type(Rings().Finite().Commutative()) <class 'sage.categories.category.JoinCategory_with_category'>
Exactly. And my impression is that your patch drastically increases the use of join categories. Perhaps this is actually not the case, but if I recall correctly, creating a join is the default when adding an axiom.
And this means that you implicitly really change the meaning of C.super_categories(). It used to be "the list of all super-categories of C such that Sage does not implement categories properly between C and the super-category", except in the case of joins. But if joins are ubiquitous, then C.super_categories() will usually (i.e., implicitly by default) be "the list of all super-categories of C, such that all named classes associated with C can be defined by means of the named classes of these super-categories together with attributes of C.__class__."
My question (or even suggestion!) is to make this implicit policy official. Rationale:
super_categories() used in our implementations?super_categories() for two purposes:
Since in future many categories will be join-categories, only the first point remains really relevant. And this means: We seek a notion of super_categories in terms of named classes. That's where my suggestion comes from.
simon-king-jena
commented
10 years ago In some posts (don't find them right now), I said that adding axioms is easier than forming a join category, and thus one should try to find an implementation that does not rely on plain joins. Let me try to elaborate on it.
It seems to me that there are (in Sage) two types of categories. My suggestion boils down to: "Implement two different Python classes for these two types of categories".
Firstly, there are categories that stipulate the existence of certain algebraic operations. Most notably: AdditiveMagmas() (providing the operator "+") and Magmas() (providing the operator ""), but conceivably there should also be something like RightGSets(G) (providing the operator "^" or perhaps another version of "") and LeftGSets(G). Probably one can formulate all of them as the categories of sets with actions by some free operad. Lets call them "free operator categories".
And secondly, there are "axiom categories" that stipulate certain axioms that hold for the operators defined in one of the "free operator categories". For example,
AdditiveCommutative() = AdditiveMagmas().Commutative()is a category which is a sub-category of AdditiveMagmas() in which the "+"-operator is commutative; and the law of (left/right/twosided) distributivity is encoded as a sub-category of the join of AdditiveMagmas() and Magmas().
Hence, an "axiom category" should tell what operations it is referring to, and this can be expressed by a (join of) "free operator categories". Hence, Rings().free_operator_category() would return Category.join([AdditiveMagmas(), Magmas()]).
And I guess the join of such "free operator categories" is trivial: We have one non-join free operator category for each algebraic operation (*, +, /, ...), and forming the join of two free operator categories just amounts to remove duplicates.
What about the join of two "axiom categories"? Well, first of all, we need to form the join of the underlying free operator categories (which is trivial), and then combine the two lists of axioms. Here is where one can implement theorems such as "a finite commutative division ring is a field". But again, the default is to remove duplicate axioms.
Possible approach to an implementation:
class FreeOperatorCategory should provide exactly one operation (multiple operations will be implemented by joins). It should have a method C.operator() returning operator.mul or operator.add or operator.sub and so on, telling what Python operator it corresponds to. And it should request certain abstract methods by which the operation is implemented (i.e., _add_ or _mul_).class CategoryWithAxioms keeps
In addition, it has to provide some _test_... method(s) for parent and/or element classes, testing against the axioms.
Hence, C=Rings() would have C.FOC = [AdditiveMagmas(), SubtractiveMagmas(), Magmas()] and C.EAC = [Distributive(), AdditiveCommutative(), AdditiveAssociative(), AdditiveInverses(), Associative()] (perhaps I forgot some axioms).
Now, about C.super_categegories().
C is a non-join free operator category, then it returns [Objects()], which is the only operator-free category (note that Sets() is a free operator category for the operator "in", requesting an abstract parent method __contains__).C is a join of non-join free operator categories, then it returns the list of these non-join free operator categories.C is an axiom category, then it returns the list C.FOC+C.EAC after removing those items of C.FOC which are already covered by one of the elementary axiom categories from C.EAC.Example
Enumerated rings ER are a join of rings (with FOC and EAC as above) and enumerated sets. The latter is a free operator category with empty operator but requested abstract parent method __iter__. Hence, I would suggest to have
ER.super_categories() == [EnumeratedSets(), Distributive(), AdditiveCommutative(), AdditiveAssociative(), AdditiveInverses(), Associative()]This is because EnumeratedSets() is the only FOC that is not subject to one of the EAC. Further,
AdditiveInverses().super_categories() == [AdditiveMagmas(), SubtractiveMagmas()]i.e., the super categories just state that the axioms are formulated in terms of + and -.
Hm. We also have "0" (zero). Should one say that "0" is a null-ary operator, and thus "0" is defined in a free operator category, and that the axiomatic properties of "0" as additive unit is then defined in an elementary axiom category WithAdditiveUnit()?
Anyway. This is the approach that I would have taken. Do you find anything useful in this approach?
nthiery
commented
10 years ago Hi Simon,
Would you have time for a phone / skype call? It probably would be the quickest to discuss the matter. I am at home and available all afternoon.
Cheers,
simon-king-jena
commented
10 years ago Replying to @nthiery:
Would you have time for a phone / skype call? It probably would be the quickest to discuss the matter. I am at home and available all afternoon.
Yes, but I need to get some late lunch first.
nthiery
commented
10 years ago Replying to @simon-king-jena:
Replying to @nthiery:
Would you have time for a phone / skype call? It probably would be the quickest to discuss the matter. I am at home and available all afternoon.
Yes, but I need to get some late lunch first.
Sure. Call me when you are back.
nthiery
commented
10 years ago Changed dependencies from #11224, #8327, #10193, #12895, #14516, #14722, #13589 to #11224, #8327, #10193, #12895, #14516, #14722, #13589, #14471
nthiery
commented
10 years ago The updated patch has been trivially rebased on top of #14471 which just got merged.
nthiery
commented
10 years ago Attachment: bla.py.gz
Hi Simon,
I am investigating the recursion error. It is definitely caused by the weak reference handling. If you run
sage -tp 8 bla.py bla.pywith the attached extract of pushout.py, you get a bunch of error messages like:
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <sage.structure.coerce_dict.TripleDictEraser object at 0x347af68> ignoredAnd if you comment out the "del" line in TripleDictEraser.call, then the error message disapears.
I am know going to proceed reducing further bla.py to get something that hopefuly would trigger the bug without the functorial construction patch. The hard part is that basically removing any line in bla.py gets the error not to appear.
Let me know if you have ideas ...
nthiery
commented
10 years ago Ok, from Volker's suggestion on Sage-devel, one can raise a similar error message when garbage collecting the entries of a MonoDict (would be the same with a tripledict) involves a big recursion because deleting an entry triggers the deletion of another entry and so on:
from sage.structure.coerce_dict import MonoDict
M = MonoDict(11)
class A: pass
a = A()
prev = a
for i in range(1000):
newA = A()
M[prev] = newA
prev = newA
len(M)
del a
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <sage.structure.coerce_dict.MonoDictEraser object at 0x5a13788> ignoredAt this point, my guess is that our weak dictionary infrastructure currently has an intrisic limitation on the depth of the reference graph, and that all the functioral construction patch does is putting a bit more stress and reach this limitation. So now the question is: is it possible to fix the weak dict infrastructure to let it scale properly by somehow unrolling the recursion as Volker suggests in [1].
Cheers,
[1] https://groups.google.com/d/msg/sage-devel/us0JCrRwGz0/McDlwepFve4J
simon-king-jena
commented
10 years ago Replying to @nthiery:
Ok, from Volker's suggestion on Sage-devel, one can raise a similar error message when garbage collecting the entries of a MonoDict (would be the same with a tripledict) involves a big recursion because deleting an entry triggers the deletion of another entry and so on:
This sounds like we need a different ticket. What do Python's weak dictionaries do? Don't they have similar problems?
simon-king-jena
commented
10 years ago Replying to @nthiery:
len(M) del a Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <sage.structure.coerce_dict.MonoDictEraser object at 0x5a13788> ignored
Are you sure that the error in bla.py is the same as the error reported by the patchbot? After all, the patchbot did not mention MonoDictEraser, but named a function remove(), isn't it?
simon-king-jena
commented
10 years ago Replying to @simon-king-jena:
This sounds like we need a different ticket. What do Python's weak dictionaries do? Don't they have similar problems?
They do. In your example, just replace M = MonoDict(11) by M = weakref.WeakKeyDictionary(), and you get essentially the same error:
sage: del a
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <function remove at 0x5f9d578> ignoredAnd this actually sounds much closer to the error reported by the patchbot.
simon-king-jena
commented
10 years ago Note that for the join, we are using a WeakValueDictionary, and with your patch we are making increased use of joins. Could this be the source of trouble?
But to my surprise, with a WeakValueDictionary, one can not get the same error (here, of course, we need to delete the first value, not the first key):
sage: class A: pass
sage: M = weakref.WeakValueDictionary()
sage: a = A()
....: prev = a
....: for i in range(1000):
....: newA = A()
....: M[newA] = prev
....: prev = newA
....:
sage: len(M)
1000
sage: del a
sage: len(M)
0... and a WeakKeyDictionary is only used in sage.misc.randstate, nowhere else! WeakValueDictionary is used more often.
Hm.
Let me try to summarize:
The patchbot reported
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <function remove at 0x2820668> ignored
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <function remove at 0xfe16e0> ignored
Exception RuntimeError: 'maximum recursion depth exceeded while getting the str of an object' in <function remove at 0x2e03e60> ignored
Exception RuntimeError: 'maximum recursion depth exceeded while getting the str of an object' in <function remove at 0x2e03e60> ignoredYour attachment: bla.py fails with
Exception RuntimeError: 'maximum recursion depth exceeded while calling a Python object' in <sage.structure.coerce_dict.TripleDictEraser object at 0x347af68> ignoredWeakKeyDictionary, but seemingly not by using a WeakValueDictionary. But only the latter is used in Sage.Where shall one start to try and analyse the problem?
This ticket implements:
New categories:
More mathematical rules:
Documentation:
Use SubcategoryMethods to put the functorial constructions where they belong. E.g. DualObjects, TensorProducts, and Graded are now only defined for subcategories of Modules.
More lazy imports, removed a bunch of unused imports, ...
This ticket is dedicated to the town of Megantic where I was so warmly welcomed and a good chunk of this ticket got implemented!
Depends on #11224 Depends on #8327 Depends on #10193 Depends on #12895 Depends on #14516 Depends on #14722 Depends on #13589 Depends on #14471 Depends on #15069 Depends on #15094 Depends on #11688 Depends on #13394 Depends on #15150 Depends on #15506 Depends on #15757 Depends on #15759 Depends on #16244 Depends on #16269
CC: @sagetrac-sage-combinat @simon-king-jena @saliola @anneschilling @vbraun @nbruin @zabrocki
Component: categories
Keywords: days54
Work Issues: To be merged simultaneously with #15801
Author: Nicolas M. Thiéry
Branch:
c16f18bReviewer: Volker Braun, Nils Bruin, Peter Bruin, Frédéric Chapoton, Darij Grinberg, Florent Hivert, Simon King, Travis Scrimshaw
Issue created by migration from https://trac.sagemath.org/ticket/10963