Make parent/element classes independent of base rings

[simon-king-jena]

At #11900 and sage-combinat-devel, as well as in some comments in sage/categories/category.py, the idea was discussed to make, for example, Algebras(GF(3)).parent_class==Algebras(GF(5)).parent_class - hence, make the parent/element classes as independent from the base of a category as possible.

This is implemented in this patch by introducing an abstract class
CategoryWithParameters which uses pickling by "weak construction" for
its element and parent classes. Now:

• For a join category, the parent/element class depend only on the
  parent/element class of its super categories.
• For a Category_over_base (e.g. Modules, Algebras, Schemes, ...), the
  parent/element class depend only on the category of the base.
• For a bimodule, the parent/element class depend only on the category
  of the left and right bases.

In the process, this patch also:

• Adds a method Category._make_named_class providing a unified way to
  create parent and element classes (and later on morphism classes)
• Extends the interface of dynamic_class to customize caching and pickling
• Rename the experimental class IdempotentSemigroups.ElementMethods
  and remove its super class, and discards unused code there.

Apply

• attachment: trac11935_weak_pickling_by_construction-nt.patch
• attachment: trac_11935-weak_pickling_by_construction-review-ts.patch

Depends on #9138
Depends on #11900
Depends on #11943
Depends on #12875
Depends on #12876
Depends on #12877

CC: @jdemeyer @sagetrac-sage-combinat

Component: categories

Keywords: parent class, element class

Author: Simon King

Reviewer: Nicolas M. Thiéry, Travis Scrimshaw

Merged: sage-5.11.beta1

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

[simon-king-jena]

comment:1

Concerning uniqueness of the parent class: In at least one case (namely Algebras(R)), the super categories depend on whether the base ring is a field or not. We would like to have

sage: Algebras(ZZ).parent_class != Algebras(GF(3)).parent_class == Algebras(QQ).parent_class
True

The idea is that the parent and element classes should only depend on the super categories, but otherwise should be independent from the base ring. Working at #11900, I found that this would drastically improve the performance of some elliptic curve computation.

[simon-king-jena]

comment:2

A problem may be seen in pickling. Before explaining the problem, let me remark that I don't see a big concern for "pickling a parent class": What we actually want to pickle is a parent, not just a naked class. The serialisation data of a polynomial ring, for example, will comprise the base ring, the generator names and the term order, but certainly the class of the polynomial ring will not be part of the pickle.

However, if we do want to serialise a naked parent or element class, we have the following problems:

Currently, C.parent_class is pickled by getattr, (C,"parent_class"). The pickling data (hence, C) is part of the cache key of a dynamic class. With that, the parent class of different categories C1 and C2 can't be the same.

I see three approaches to get rid of it.

1. Remove the pickling data from the cache key of dynamic classes
2. Make pickling of C.parent_class just rely on the default way of pickling a dynamic class
3. Work around the cache of dynamic classes, but still use getattr,(C,"parent_class") for pickling.

I think 1. is not gonna happen. It would break a lot of code, I suppose.

I had tested 2. and 3. while working on #11900. Both would work, but there are different conerns concerning long-term stability.

2. means:

   The pickle of a parent class will only depend on the category graph as it was on the time of pickling. If the category graph changes between pickling and unpickling the parent class, you would get a different class.

3. would be a bit more stable.

   The idea is:

   (i) In the lazy attribute parent_class(), the dynamic class is first created without providing the reduction data (as in approach 2.).
   (ii) Before returning that dynamic class, it is tested whether the reduction data is still none. If it is, the getattr, (C,"parent_class") thingy is inserted.

   Consequence: Algebras(QQ).parent_class could, for example, be unpickled as Algebras(GF(2)).parent_class - which is not a big problem, since we want them to be the same. However, if in a distant future we want them to be different again, we'd be in trouble...

I suggest that I create patches for both 2. and 3., and then people can tell what they think about it. The method resolution will then be taken care of by another patch.

[nthiery]

comment:3

Replying to @simon-king-jena:

A problem may be seen in pickling. Before explaining the problem, let me remark that I don't see a big concern for "pickling a parent class":

True: all parents ought to be pickled "by construction" rather than by
"class + internal data", in order to encapsulate as much as possible
of the data structure. This probably ought to be true as well for
elements. I don't know how far we are from this.

A good thing to do at this point would be to search through the sage
pickle jar for how many parent_class's and element_class's are pickled
there. And why. I don't know how complicated it is to do this search
though.

Among the three propositions, I like 3 best. I have trouble evaluating
how big the risks are to get stuck in the future. It does not seem too
big.

Thanks Simon for investigating this!

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -1,7 +1,2 @@
-At #11900 and [sage-combinat-devel](http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/99c74827d704e677), as well as in some comments in sage/categories/category.py, the idea was discussed to make
+At #11900 and [sage-combinat-devel](http://groups.google.com/group/sage-combinat-devel/browse_thread/thread/99c74827d704e677), as well as in some comments in sage/categories/category.py, the idea was discussed to make, for example, `Algebras(GF(3)).parent_class==Algebras(GF(5)).parent_class` - hence, make the parent/element classes as independent from the base of a category as possible.
 
-* `C.all_super_categories()` consistent with `C.parent_class.mro()` and `C.element_class.mro()`.
-* `Algebras(GF(3)).parent_class==Algebras(GF(5)).parent_class` - hence, make the parent/element classes as independent from the base of a category as possible.
-
-I think it should be fine to have both in one ticket.
-

[simon-king-jena]

comment:4

Replying to @simon-king-jena:

I suggest that I create patches for both 2. and 3., and then people can tell what they think about it. The method resolution will then be taken care of by another patch.

I just argued myself into splitting the ticket: This here will be for the base ring independent parent/element classes, and another one will be for method resolution order.

[simon-king-jena]

comment:5

Replying to @nthiery:

A good thing to do at this point would be to search through the sage
pickle jar for how many parent_class's and element_class's are pickled
there.

Old pickles will not break, I believe. Let P3 = Algebras(GF(3)).parent_class and PQ = Algebras(QQ).parent_class. Here are a few scenarios:

1. P3 and PQ have been created and pickled with an old version of Sage

In the old version of Sage, P3!=PQ. They are pickled by construction. Hence, after applying my yet-to-be-submitted patches, they are unpickled as Algebras(GF(3)).parent_class and Algebras(QQ).parent_class - which is the same class after applying the patch.

Conclusion: An old pickle will not break, with either approach 2. or 3. The worst what could happen is P3!=PQ before pickling and P3==PQ after unpickling. But the defining property P3==Algebras(GF(3)).parent_class and PQ==Algebras(QQ).parent_class is preserved.

2. P3 and PQ are created and pickled according to approach 2. from above

Of course, P3==PQ at the time of pickling. The pickle will only depend on the parent classes of the super categories of Algebras(GF(3)) and Algebras(QQ). If there was a change in the super categories between pickling and unpickling, we would have P3!=Algebras(GF(3)).parent_class after unpickling.

Conclusion: A new pickle of P3 and PQ can be unpickled after a change in the category graph, but a change in the category graph will destroy the defining property P3==Algebras(GF(3)).parent_class.

3. P3 and PQ are created and pickled according to approach 3. from above

Of course, P3==PQ at the time of pickling. PQ and P3 will both be pickled by construction. In particular, a change in the category graph would not matter, as long as the super categories of Algebras(QQ) and Algebras(GF(3)) still coincide (up to the base ring) after the change in the category graph.

A problem would arise if, in a distant future, the super categories of Algebras(QQ) and Algebras(GF(3)) would become essentially different. Say, some algebra person finds that vector spaces over fraction fields should have their own category, different from the usual category of vector spaces. Then, Algebras(QQ).parent_class!=Algebras(GF(3)).parent_class. In particular, after such change, unpickling P3 or PQ would result in either PQ!=Algebras(QQ).parent_class or P3!=Algebras(GF(3)).parent_class.

Conclusion: A new pickle of P3 and PQ can be unpickled after a change in the category graph. Most changes in the category graph will preserve the defining property P3==Algebras(GF(3)).parent_class and PQ==Algebras(QQ).parent_class after unpickling. However, if the super categories will depend on the base ring in a different way as it is now, then either P3 or PQ will lose the defining property after unpickling, while the other will keep the defining property - and we don't know which of the two will break.

---

It seems to me that approach 3. is less fragile than 2. But I believe that in applications (hence, for pickling parents) both should be fine. So, I'll prepare patches for both approaches.

[simon-king-jena]

Use default pickling for parent/element classes, making them base ring independent.

[simon-king-jena]

comment:6

Attachment: trac11935_use_default_pickling.patch.gz

The patch that I just attached implements approach 2., hence, it uses the default pickling of dynamic classes. By consequence, the parent class of a category C will only depend on C.ParentMethods and on the parent classes of the super categories of C, but it will only depend on the base ring of C if the base ring changes the super categories (which holds for algebras, e.g.).

Note the effect on the computation time for elliptic curves. With sage-4.7.2.alpha3 plus #11900, we have

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.97 s, sys: 0.07 s, total: 4.04 s
Wall time: 4.18 s

but with the new patch on top of it, we have

sage: %time L = EllipticCurve('960d1').prove_BSD()
CPU times: user 3.11 s, sys: 0.06 s, total: 3.17 s
Wall time: 3.31 s