Opened 12 years ago

Last modified 8 years ago

# Morphisms and Objects of Categories

Reported by: Owned by: Simon King Nicolas M. Thiéry major sage-6.4 categories objects morphisms containment sd34 Niles Johnson, Jean-Pierre Flori Simon King N/A Cope with non-unique number fields #9138, #11115, #11780

### Description

Purpose

Introduce a framework for testing whether or not something is a morphism in a category. See the discussion on sage-algebra. Here is a summary of the discussion.

Methods for categories

Categories `C` should have a method `C.has_morphism(f)` answering whether `f` is a morphism in `C`. By symmetry, we want a method `C.has_object(X)`, answering whether `X` is an object in `C`.

Note that we want `X in C` to be true if and only if `X` is an object of `C` (so, it is synonymous to `C.has_object(X)`). This currently is not always the case:

```sage: P.<x,y> = QQ[]
sage: f = P.hom(reversed(P.gens()))
sage: f in Rings().hom_category()
True
```

but of course `f` is not an object of the hom-category (it is only contained in an object of the hom-category).

Class/Set of objects and morphisms

It would be nice to have container classes for the objects and for the morphisms of a category. Then, `f in C.morphisms()` would be a very natural notation for `C.has_morphism(f)`, and `X in C.objects()` would be another way of saying `X in C`.

Of course, since `f in C.morphisms()` and `f in C.objects()` are nice notations, they should be as fast as possible -- otherwise, people wouldn't use them.

Further discussion should be put in comments to this ticket.

### comment:1 follow-up:  2 Changed 12 years ago by Simon King

If a category has not its own implementation of a hom-category, currently the join of the hom-categories of its super-categories is chosen. Hence, we have

```sage: CommutativeRings().hom_category()
Category of hom sets in Category of rings
sage: WeylGroups().hom_category()
Category of hom sets in Category of sets
```

I don't like that. One problem is that, for test suites, one would like to have a sample object -- but there is no way to create a sample object for a join of arbitrary categories.

Moreover, the "hom sets in the Category of rings" are simply wrong for the category of commutative rings.

Instead, I suggest to walk through the list of all super categories of `self`, take the first that has the attribute `HomCategory` (i.e., has a custom implementation of a hom category), and insert `self` as argument for that `HomCategory`:

```sage: HopfAlgebrasWithBasis(QQ).hom_category()
Category of hom sets in Category of hopf algebras with basis over Rational Field
sage: WeylGroups().hom_category()
Category of hom sets in Category of weyl groups
sage: type(HopfAlgebrasWithBasis(QQ).hom_category())
<class 'sage.categories.modules_with_basis.ModulesWithBasis.HomCategory'>
sage: type(WeylGroups().hom_category())
<class 'sage.categories.sets_cat.Sets.HomCategory'>
```

Of course, it may happen that several super categories have different custom implementation of hom categories, and we pick just one. But I think this should be taken care of manually, as join categories have a serious drawback, IMHO.

### comment:2 in reply to:  1 Changed 12 years ago by Nicolas M. Thiéry

Hi Simon!

Replying to SimonKing:

If a category has not its own implementation of a hom-category, currently the join of the hom-categories of its super-categories is chosen. Hence, we have

```sage: CommutativeRings().hom_category()
Category of hom sets in Category of rings
sage: WeylGroups().hom_category()
Category of hom sets in Category of sets
```

I don't like that. ...

Yeah. As mentioned in the code and in the road map [1], HomCategory? is just plain broken and needs a full refactoring. I just used the occasion to create a ticket with design suggestions: #10668.

If you want to improve things in this direction, please jump right away on #10668; it might actually not be that much work, and every intermediate step would be just a work around and a waste of time.

Thanks again for your continuous motion toward improving Sage in this area!

Cheers,

Nicolas

### comment:3 Changed 12 years ago by Niles Johnson

Cc: Niles Johnson added

cc me! Thanks :)

### comment:4 follow-up:  6 Changed 12 years ago by Simon King

Authors: → Simon King

Depends on #10496, #10659, #8611, #10467

I wont to get the patch finally off my plate. So, here it is, although it isn't finished yet.

My patch provides the following:

```sage: C = Rings()
sage: P.<x,y> = QQ[]
sage: f = P.hom(reversed(P.gens()))
sage: C.has_morphism(f)
True
sage: C.morphisms()
Class of morphisms in category of rings
sage: f in C.morphisms()
True
# Currently, a category is acknowledged as "small"
# iff it is a sub-category of FiniteEnumeratedSets()
sage: FiniteFields().morphisms()
Set of morphisms in category of finite fields
sage: f in FiniteFields().morphisms()
False
sage: P in C
True
sage: C.objects()
Class of objects in category of rings
sage: P in C.objects()
True
sage: FiniteFields().objects()
Set of objects in category of finite fields
```

Note that I interprete `Objects()` (the top-category in Sage) as the "category of all classes", although this definition probably is not water-proof:

```sage: C.objects().category()
Category of objects
sage: FiniteFields().objects().category()
Category of sets
```

Some categories have a custom containment test, e.g., the category of fields. The containment test of `C.objects()` automatically tests whether `C` has a custom containment, and uses it if it is the case:

```sage: PolynomialRing(QQ,[]).category()
Category of commutative rings
sage: PolynomialRing(QQ,[]) in Fields()
True
sage: PolynomialRing(QQ,[]) in Fields().objects()
True
```

The documentation for the new containers for objects and morphisms are added to the Sage reference manual -- please have a look.

`SageObject` versus `CategoryObject`

`SageObject` and `CategoryObject` were almost identical. In particular, `SageObject` provided a method `category()`, that by default returned the "category of objects". In addition, the specifition says that `X` is an object of `X.category()`, i.e., `X in X.category()`.

But that approach yields to quite unnatural constructions. For example, `1.category()` used to be the "category of elements of Integer Ring", whatever that means. Worse, one used to have

```# Unpatched behaviour: Bug
sage: ZZ.hom([1]) in Rings().hom_category()
True
```

In other words, a ring homomorphism is considered a homset of the category of rings - of course, it should just be an element of a homset:

```# With the patch:
sage: ZZ.hom([1]) in Rings().hom_category()
False
sage: ZZ.hom([1]) in ZZ.Hom(ZZ)
True
sage: ZZ.hom([1]) in Rings().morphisms()
True
```

Fixing that bug required to re-structure `SageObject` and `CategoryObject`:

• I removed `category()` and `_test_category()` from `SageObject` and moved it to `CategoryObject` (which directly inherits from `SageObject` anyway).
• I made `Element` and `Map` inherit from `SageObject`, not from `CategoryObject`, and removed the custom `category()` for `Element`. Of course, `Parent` still inherits from `CategoryObject`.

Note that by this change, it is now impossible to define nonsense such as `Hom(2,3)` (2 and 3 used to be objects in a category, so, there was a hom-set!).

Hom-categories

Compare #10668: This part of my patch is not finished, yet. I suppose that eventually this ticket here will depend on #10668.

Just for now, I implemented what I described in my previous post. Otherwise, many tests from the new test suites described below would fail.

Test Suites

The test suites of categories have been extended to test against the specification of the new features. In particular, the containers for morphisms and objects provide a test suite. The test suites for `C.morphisms()` and `C.objects()` and `C.hom_category()` are added to the test suite of `C`.

The patch adds a method `an_object()` to categories, that is used for additional tests. The default is to return `example()`, but this is not provided in all cases. The purpose of `an_object()` is narrower than that of `example()`, which is supposed to provide a concise instructive (but not necessarily very efficient) implementation. In contrast, `an_object()` may return an object of a subcategory, if nothing else is available. The test suite of `C.an_object()` becomes part of the test suite of `C`.

Similarly, I introduce a method `a_morphism`. By default, it takes the output of `an_object()`, tries to create an automorphism by reverting the list of generators, and if that fails then it returns the identity automorphism. The latter sounds trivial, but actually I found several cases where the identity automorphism was provided with the wrong category. This led to the following bug fixes:

• In `sage.categories.homset.Hom`, there was an assymmetry between the categories of the domain and the codomain. I suggest to choose the meet of both categories. However, note that there was a comment like this:
```   To avoid creating superfluous categories, homsets are in the
homset category of the lowest category which currently says
something specific about its homsets.
```
which meant that the endomorphisms of the rational field used to belong to the "Category of hom sets in Category of rings". I didn't observe any problems changing it into the "Category of hom sets in Category of quotient fields".
• Without the patch:
```sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS([1,1,0,1])])
sage: H = MatrixGroup([MS([1,0,1,1])])
sage: phi = G.hom(H.gens())
sage: phi.category_for()
Category of groups
sage: H.category()
Category of finite groups
sage: G.category()
Category of finite groups
```
Hence, the morphism belongs to a category that is too broad. With the patch:
```sage: F = GF(5); MS = MatrixSpace(F,2,2)
sage: G = MatrixGroup([MS([1,1,0,1])])
sage: H = MatrixGroup([MS([1,0,1,1])])
sage: phi = G.hom(H.gens())
sage: phi.category_for()
Category of finite groups
```
In several cases I have not been able to find any proper use case in Sage for a given category. In these cases, I have not been able to provide `an_object()`, so that in these cases I have to skip some tests from the test suites:
• `JoinCategory` (I guess it is impossible to construct a generic object of the join of two arbitrary categories)
• `AbstractCategory` (Do I understand correctly that the abstract category for the category of `ZZ`-modules would be the catogory of modules? I.e., one abstracts the base ring away?)
• `Schemes`:
```# Bug, not fixed in the patch
sage: Spec(QQ).category()
Category of sets
```
• `UniqueFactorizationDomains`
```# Bug, not fixed in the patch
sage: ZZ in UniqueFactorizationDomains()
False
```
• `AlgebraModules`:
```sage: QQ['x'] in Algebras(QQ)
True
# Bug?
sage: QQ['x']^3 in AlgebraModules(QQ['x'])
False
```
• `GSets` (Is there any G-set in Sage that knows that it is a G-set?)
• `DualObjectsCategory`
• `Sets().Subquotients()`
• `FiniteDimensional...`: Most categories whose name starts with `FiniteDimensional` are not in use.
• `PartiallyOrderedMonoids`
• `MonoidAlgebras`
• `TensorProductsCategory`
• I added a minimal implementation of pointed sets:
```sage: from sage.categories.examples.pointed_sets import PointedSet
sage: S = PointedSet([1,2,3],2)
sage: S
{1, 2, 3} -> 2
sage: S is loads(dumps(S))
True
sage: S == PointedSet([1,2,3],3)
False
```
• I fixed the category of partially ordered sets.

Without patch:

```sage: from sage.combinat.posets.posets import Poset
sage: elms = [1,2,3,4,5,6,7]
sage: rels = [[1,2],[3,4],[4,5],[2,5]]
sage: Poset((elms, rels), cover_relations = True).category()
Category of sets
```

With the patch, we obtain `Category of partially ordered sets`.

• The category of matrix algebras has not been used. I added the obvious example:
```sage: MatrixSpace(QQ,2).category()
Category of matrix algebras over Rational Field
```
which used to be the category of algebras (not: matrix algebras).

Groupoids

Groupoids are considered as a category with a single object. However, this object did not exist. The patch provides it, modeled as an empty set:

```sage: G = SymmetricGroup(5)
sage: C = Groupoid(G)
sage: O = C.an_object(); O
Unique object of Groupoid with underlying set SymmetricGroup(5)
sage: len(O)
0
sage: O.an_element()
Traceback (most recent call last):
...
EmptySetError:
```

The elements of `G` correspond to morphisms of its groupoid. I suggest to actually consider them as morphisms (which is stronger than saying they correspond to morphisms):

```sage: G.an_element() in C.morphisms()
True
```

Note that this point of view is needed in order to have a functorial approach towards actions, namely: If we want to view a group action of `G` on a set `S` as a functor from the groupoid of `G` to the category containing `S` as an object, then

1. we need that functors can map morphisms (see #8807), and
1. we need that group elements are considered as morphisms.

Actually, that was the starting point for my work on this ticket.

On the other hand, I do think that considering `G` as a homset of `Groupoid(G)` is not a very clean solution. But I believe this could be addressed on a different ticket, as this one is already too long.

Need for Speed

Of course, testing containment in a category `C` or in `C.objects()` or in `C.morphisms()` should be as fast as possible. I did the following:

• I added a shortpath to `C.__contains__` and `C.objects().__contains__` for the common case that the category of the argument is `C`.
• `C.objects()` and `C.morphisms()` are cached methods. By #8611, the overhead is now pretty small anyway.
• Containment of an object `O` in a category `C` relies on testing whether `O.category()` is a sub-category of `C`. This is cached, by #8611. In addition, I remove the overhead entirely, by directly accessing the cache.
• The containers for objects and morphisms are implemented in Cython. The default containment test is copied from the category, in order to reduce the overhead of calling a Python function. Therefore, `F in O` (where `O = C.objects()`) is sometimes even a little quicker than `F in C`:
```sage: F = GF(5)
sage: C = Rings()
sage: O = C.objects()
sage: F in O
True
sage: timeit('F in O',number=100000)
100000 loops, best of 3: 5.2 µs per loop
sage: timeit('F in C',number=100000)
100000 loops, best of 3: 5.38 µs per loop
```

Here are some timings. Their purpose is to show that `X in C` did not slow down (in fact, there is a speed-up in one special case), and that `X in C.objects()` has almost no overhead compared to `X in C`.

Setting:

```sage: G = SymmetricGroup(5)
sage: P.<x,y> = QQ[]
sage: F = PolynomialRing(QQ,[])
sage: C1 = Rings()
sage: C2 = G.category()
sage: C3 = Fields()
```

Sanity tests:

```# test that X in C.objects() is the same as X in C
# For C1:
sage: P in C1
True
sage: P in C1.objects()
True
sage: G in C1
False
sage: G in C1.objects()
False
sage: F in C1
True
sage: F in C1.objects()
True

# For C2, which is a join (that's a special case):
sage: P in C2
False
sage: P in C2.objects()
False
sage: G in C2
True
sage: G in C2.objects()
True
sage: F in C2
False
sage: F in C2.objects()
False

# For C3 (having a custom containment test):
sage: P in C3
False
sage: P in C3.objects()
False
sage: G in C3
False
sage: G in C3.objects()
False
sage: F in C3
True
sage: F in C3.objects()
True
```

Timings without the new patch (but with #10496, #10659, #8611 and #10467):

```# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 4.32 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 11.9 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 11.1 µs per loop
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 4.2 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 11.5 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 16.1 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 20.5 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 17.9 µs per loop
```

Timings with the patch, including the new syntax `X in C.objects()`:

```# containment in C1
sage: timeit('P in C1',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in C1.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
sage: timeit('G in C1',number=100000)
100000 loops, best of 3: 1.91 µs per loop
sage: timeit('G in C1.objects()',number=100000)
100000 loops, best of 3: 2.45 µs per loop
sage: timeit('F in C1',number=100000)
100000 loops, best of 3: 9.51 µs per loop
sage: timeit('F in C1.objects()',number=100000)
100000 loops, best of 3: 10.2 µs per loop
# containment in C2
sage: timeit('P in C2',number=100000)
100000 loops, best of 3: 9.2 µs per loop
sage: timeit('P in C2.objects()',number=100000)
100000 loops, best of 3: 9.85 µs per loop
# using the shortpath, as G.category() is C2
sage: timeit('G in C2',number=100000)
100000 loops, best of 3: 836 ns per loop
sage: timeit('G in C2.objects()',number=100000)
100000 loops, best of 3: 1.52 µs per loop
sage: timeit('F in C2',number=100000)
100000 loops, best of 3: 9.52 µs per loop
sage: timeit('F in C2.objects()',number=100000)
100000 loops, best of 3: 10.3 µs per loop
# containment in C3 (custom test for fields!)
sage: timeit('P in C3',number=100000)
100000 loops, best of 3: 14 µs per loop
sage: timeit('P in C3.objects()',number=100000)
100000 loops, best of 3: 15.9 µs per loop
sage: timeit('G in C3',number=100000)
100000 loops, best of 3: 15.7 µs per loop
sage: timeit('G in C3.objects()',number=100000)
100000 loops, best of 3: 18.3 µs per loop
sage: timeit('F in C3',number=100000)
100000 loops, best of 3: 15.6 µs per loop
sage: timeit('F in C3.objects()',number=100000)
100000 loops, best of 3: 17.3 µs per loop
```

Or, directly testing containment in the class of objects:

```sage: O1 = C1.objects()
sage: O2 = C2.objects()
sage: O3 = C3.objects()
sage: timeit('P in O1',number=100000)
100000 loops, best of 3: 8.88 µs per loop
sage: timeit('G in O1',number=100000)
100000 loops, best of 3: 1.56 µs per loop
sage: timeit('F in O1',number=100000)
100000 loops, best of 3: 9.31 µs per loop
sage: timeit('P in O2',number=100000)
100000 loops, best of 3: 8.94 µs per loop
sage: timeit('G in O2',number=100000)
100000 loops, best of 3: 704 ns per loop
sage: timeit('F in O2',number=100000)
100000 loops, best of 3: 9.29 µs per loop
sage: timeit('P in O3',number=100000)
100000 loops, best of 3: 14.9 µs per loop
sage: timeit('G in O3',number=100000)
100000 loops, best of 3: 17.1 µs per loop
sage: timeit('F in O3',number=100000)
100000 loops, best of 3: 16.5 µs per loop
```

### comment:5 Changed 12 years ago by Simon King

Status: new → needs_info

So, what's the status of the ticket?

I need more info!

First thing: I am still not happy with the groupoids. But can this perhaps be solved in a different ticket?

Second and more urgent thing? Why does my example of pointed sets not inherit from `PointedSets().parent_class`? What did I do wrong? I asked on sage-support, but didn't receive a reply.

The problem is:

```sage: from sage.categories.examples.pointed_sets import PointedSet
sage: S = PointedSet([1,2,3],2)
sage: S.category()
Category of pointed sets
sage: S.__class__
<class 'sage.categories.examples.pointed_sets.PointedSet_with_category'>
```

So, the category is initialised. But:

```sage: isinstance(S,PointedSets().parent_class)
False
```

What goes wrong in my implementation?

### comment:6 in reply to:  4 Changed 12 years ago by Nicolas M. Thiéry

Hi Simon!

I have only browsed quickly through this yet. I'll try to have a look soon at the broken parent you mention in the other comment. Just some small comments before heading for my bed.

• In `sage.categories.homset.Hom`, there was an assymmetry between the categories of the domain and the codomain. I suggest to choose the meet of both categories. However, note that there was a comment like this:
```   To avoid creating superfluous categories, homsets are in the
homset category of the lowest category which currently says
something specific about its homsets.
```
which meant that the endomorphisms of the rational field used to belong to the "Category of hom sets in Category of rings". I didn't observe any problems changing it into the "Category of hom sets in Category of quotient fields".

I wrote this comment. This won't break indeed, but there might eventually be a penalty in creating that many categories. I need to think back about it, but this comment might become irrelevant since we are going to break the inheritance in-between hom categories.

• `AbstractCategory` (Do I understand correctly that the abstract category for the category of `ZZ`-modules would be the catogory of modules? I.e., one abstracts the base ring away?)

As I said, don't bother understanding: that's going to be removed. If it gets in your way, just kill the beast, and remove right now everything about AbstractCategory? (typically by taking over the appropriate bits of the patch I mentioned).

### comment:7 Changed 12 years ago by Simon King

Status: needs_info → needs_review

Thanks to Nicolas for his comments on sage-algebra explaining why my example of pointed sets didn't work well. It is now fixed. Hence, ready for review!

### comment:8 Changed 12 years ago by Simon King

I updated the patch, so that it now applies to `sage-4.6.2.alpha4`. There are no dependencies.

### comment:9 Changed 12 years ago by Simon King

Since the patchbot keeps complaining that the patch did not apply to good old sage-4.6.1 and since I just verified once again that the patch cleanly applies to sage-4.6.2.alpha4, I replaced the patch by an identical copy and hope that it pushes the patchbot to try it another time with the new sage version.

### comment:10 Changed 11 years ago by Simon King

Status: needs_review → needs_work

On #9054, William expressed his anger about category containment tests being too slow. That reminded me of the ticket here. Since the patches do not apply, it needs work. But I guess it is worth while to resume work on that ticket.

### comment:11 Changed 11 years ago by Simon King

I have updated the patch, so that it should apply against sage-4.7.2.alpha2. I did not run tests, yet. Here are some timings:

```sage: from sage.rings.commutative_ring import is_CommutativeRing
sage: %timeit is_CommutativeRing(QQ)
625 loops, best of 3: 1.09 µs per loop
sage: C = CommutativeRings().objects()
sage: %timeit QQ in C
625 loops, best of 3: 3.82 µs per loop
```

`is_CommutativeRing` simply tests whether `QQ` is an instance of `sage.rings.ring.CommutativeRing`, which is of course very fast (but not very reliable from a mathematical point of view.

Anyway, I try to squeeze `QQ in C` a bit more.

### comment:12 Changed 11 years ago by Simon King

Dependencies: → #9138, #11115 needs_work → needs_review

I created a new version of my patch. The aim is to make the performance of containment tests even better. I did the following, compared with the old patch:

• I make the patch dependent on #9138 and #11115 (both help to come to speed).
• I've put power series rings into the category and coercion framework.
• I introduced base() for join categories: If at least one of the underlying categories has a base and if there is no conflict with different bases, then the join shall have that base as well. That is needed because some algebras have a join category by #9138.
• GroupAlgebras? should not only be Hopf algebras with basis but also group algebras. Hence, I made it a join of the two.
• I implemented is_supercategory (there has only been is_subcategory), and use it to make containment tests even faster. It depends on #11115, because I use the Cython class of cached methods.

I guess the best news is that the containment test via category framework can now compete with a pure class check, if that class check is done in Python. I take, for example, commutative rings:

```sage: from sage.rings.commutative_ring import is_CommutativeRing
sage: is_CommutativeRing??
Type:           function
Base Class:     <type 'function'>
String Form:    <function is_CommutativeRing at 0x118c488>
Namespace:      Interactive
File:           /mnt/local/king/SAGE/sandbox/sage-4.7.2.alpha2/local/lib/python2.6/site-packages/sage/rings/commutative_ring.py
Definition:     is_CommutativeRing(R)
Source:
def is_CommutativeRing(R):
return isinstance(R, CommutativeRing)
sage: is_CommutativeRing(QQ)
True
sage: s = SymmetricGroup(4)
sage: is_CommutativeRing(s)
False
sage: %timeit is_CommutativeRing(QQ)
625 loops, best of 3: 1.09 µs per loop
sage: %timeit is_CommutativeRing(s)
625 loops, best of 3: 3.51 µs per loop
```

Since `is_CommutativeRing` just tests the class, it is supposed to be very fast. But let us compare with the generic containment test in the category of commutative rings and in the class of objects of that category:

```sage: C = CommutativeRings()
sage: O = C.objects()
sage: QQ in C
True
sage: QQ in O
True
sage: s in C
False
sage: s in O
False
sage: %timeit QQ in C
625 loops, best of 3: 4.62 µs per loop
# Timing in sage-4.6.2: 12.9 µs per loop
sage: %timeit QQ in O
625 loops, best of 3: 1.5 µs per loop
sage: %timeit s in C
625 loops, best of 3: 4.69 µs per loop
# Timing in sage-4.6.2: 10.2 µs per loop
sage: %timeit s in O
625 loops, best of 3: 1.46 µs per loop
```

Hence, `is_CommutativeRing(s)` is slower than `s in O`, where `O = CommutativeRings().objects()`.

The reason for that speedup is Cython. While `is_CommutativeRing` is a Python function, the objects of a category are implemented in Cython. Moreover, category containment is tested by the cached method `is_supercategory`, which also is in Cython by #9138.

Caveat: I did not run the full tests, yet, and I would like to try and remove some custom containment tests in the category framework, that tend to be slower than the generic test and might not be needed with #9138.

### comment:13 Changed 11 years ago by Simon King

I forgot to mention that I also improved `is_Ring`.

With sage-4.7.2.alpha1 plus #9138 and #11115:

```sage: from sage.rings.ring import is_Ring
sage: MS = MatrixSpace(QQ,2)
sage: %timeit is_Ring(QQ)
625 loops, best of 3: 5.1 µs per loop
sage: %timeit is_Ring(MS)
625 loops, best of 3: 17.3 µs per loop
sage: C = Rings()
sage: %timeit QQ in C
625 loops, best of 3: 4.18 µs per loop
sage: %timeit MS in C
625 loops, best of 3: 4.31 µs per loop
```

With sage-4.7.2.alpha2 plus #9138 and #11115 and the patch from here:

```sage: from sage.rings.ring import is_Ring
sage: MS = MatrixSpace(QQ,2)
sage: %timeit is_Ring(QQ)
625 loops, best of 3: 259 ns per loop
sage: %timeit is_Ring(MS)
625 loops, best of 3: 17.5 µs per loop
sage: C = Rings().objects()
sage: %timeit QQ in C
625 loops, best of 3: 1.49 µs per loop
sage: %timeit MS in C
625 loops, best of 3: 1.57 µs per loop
```

### comment:14 follow-up:  15 Changed 11 years ago by Simon King

Milestone: → sage-5.0

I leave it as "needs review", but I think I have to adopt the Cython improvements on morphism containment tests as well.

### comment:15 in reply to:  14 Changed 11 years ago by Simon King

Status: needs_review → needs_work → doctests

Replying to SimonKing:

I leave it as "needs review", but I think I have to adopt the Cython improvements on morphism containment tests as well.

Nope, it wouldn't easily work for the morphisms.

It turns out that I have to fix many doctests.

### comment:16 follow-up:  17 Changed 11 years ago by Simon King

It is a very bad error, and I don't know at which point I introduced it. It is about incompatible method resolution orders:

```sage: class Foo(Homset, Objects().HomCategory(Objects()).parent_class): pass
....:
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)

/mnt/local/king/SAGE/sandbox/sage-4.7.2.alpha2/devel/sage-main/<ipython console> in <module>()

TypeError: Error when calling the metaclass bases
Cannot create a consistent method resolution
order (MRO) for bases Homset, Objects.HomCategory.parent_class
```

It seems that the problem is in the order in which the two classes are presented:

```sage: class Foo(Objects().HomCategory(Objects()).parent_class, Homset): pass
....:
sage:
```

### comment:17 in reply to:  16 ; follow-up:  18 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

It is a very bad error, and I don't know at which point I introduced it. It is about incompatible method resolution orders:

```sage: class Foo(Homset, Objects().HomCategory(Objects()).parent_class): pass
order (MRO) for bases Homset, Objects.HomCategory.parent_class
```

Yeah, this kind of error can be quite tricky indeed. This is the very technical bit where I am bit uneasy about the future scaling of categories using dynamic classes. The only way to avoid such errors sanely is to specify general rules about the order of the base classes of a class. There are very minimal comments about that at the end of the primer. Reducing the risk of this kind of issue is also one of the goal of #10963 (the more is done automatically, the higher are the chances of consistency).

It seems that the problem is in the order in which the two classes are presented:

```sage: class Foo(Objects().HomCategory(Objects()).parent_class, Homset): pass
....:
sage:
```

Here, I would say that the rule is that category code (in particular what comes from a_category.parent_class) should always come after concrete classes.

Good luck!

By the way: congrats on all your category optimization work. I love it!

### comment:18 in reply to:  17 Changed 11 years ago by Simon King

Replying to nthiery:

The only way to avoid such errors sanely is to specify general rules about the order of the base classes of a class.

I thought of that. But it could slow things down.

Here, I would say that the rule is that category code (in particular what comes from a_category.parent_class) should always come after concrete classes.

It is not very much concrete. The real error reduces to what I have shown. But in fact, the class Homset comes from `sage.categories.objects.HomCategory.ParentMethods`. To be precise:

```sage: from sage.structure.dynamic_class import dynamic_class
sage: C = Objects().hom_category()
sage: dynamic_class('bla', (C.parent_class,), C.ParentMethods)
```

And going further down, the above is caused by some lines in the parent_class lazy attribute:

```        return dynamic_class("%s.parent_class"%self.__class__.__name__,
tuple(cat.parent_class for cat in self.super_categories()),
self.ParentMethods,
reduction = (getattr, (self, "parent_class")))
```

In my case, `cat.parent_class` is a sub-class of `self.ParentMethods` (self being C above). Here is the relation with my patch:

```sage: C = ChainComplexes(ZZ)
sage: HC = C.hom_category()
sage: HC.super_categories()
[Category of hom sets in Category of objects]
# it was [Category of sets] without my patch!
```

And finally, that comes from

```sage: HC.base_category
Category of chain complexes over Integer Ring
# it used to be Category of objects without my patch
```

Since `[category.hom_category() for category in self.base_category.super_categories()]` is part of the super categories, the change of the base category was the ultimate cause of the error.

However, I wouldn't like to change the base_category. After all, the base_category is the category to which the homsets belong. Here, the homsets belong to the category of chain complexes over Integer Ring. Thus, "category of objects" is plainly wrong.

So, for now, I see two ways to fix it:

1. Change `HomCategory.super_categories`. It should only return `self.extra_super_categories() + Sets()` (after all, homsets are sets), but not `[category.hom_category() for category in self.base_category.super_categories()]`.
1. Change `parent_class`, so that not all of `tuple(cat.parent_class for cat in self.super_categories())` is included, but only the bits that are no sub-classes of `self.ParentMethods`.

Is it really mathematically correct that the hom-category of a category C is a subcategory of the hom-category of any super-category of C?

For example, if C is the category of unital K-algebras (K some field) then C is a subcategory of the category of K-vectorspaces. The homsets of K-vectorspaces are K-vectorspaces. But the homsets of unital K-algebras do not form K-vectorspaces, isn't it?

At least, computationally, option 1 is faster than option 2. And when you confirm that option 2 (which is the status quo!) is actually mathematically wrong then it is clear what I will do.

By the way: congrats on all your category optimization work. I love it!

Thank you!

### comment:19 follow-up:  21 Changed 11 years ago by Simon King

Indeed the hom category of algebras is attributed as a subcategory of the category of vectorspaces:

```sage: Algebras(QQ).hom_category().is_subcategory(VectorSpaces(QQ))
True
```

Isn't that plainly wrong?

### comment:20 Changed 11 years ago by Simon King

It seems to me that the implementation can not so easily be cleaned.

In some cases, we do want that the hom category of a category inherits stuff from the hom category of a super category - simply in order to avoid code duplication. For example, `VectorSpaces(...).hom_category()` does (and should) inherit from `Modules(...).hom_category()`.

In other cases, we do not want that inheritance. For example, we do not want that `Algebras(...).hom_category()` inherits from `VectorSpaces(...).hom_category()`.

Indeed, we currently have

```sage: Algebras(QQ).hom_category().extra_super_categories()
[Category of sets]
```

I tried to understand why we have the above answer. We have

```sage: Algebras(QQ).hom_category().extra_super_categories.__module__
'sage.categories.rings'
```

So, the method is inherited from the hom category of the category of rings.

Why is it (correctly) not inherited from the hom category of the category of Q-modules?

```sage: Modules(QQ).hom_category().extra_super_categories()
[Category of vector spaces over Rational Field]
```

It seems to me that the correct inheritence is just due to the fact that `Algebras(...).super_categories()` returns first `Rings()` and then `Modules(...)`

```sage: Algebras(QQ).super_categories()
[Category of rings, Category of vector spaces over Rational Field]
```

If that list would be returned in the opposite order, then `Algebras(QQ).hom_category()` would pick up the `extra_super_categories` method from `Modules(QQ).hom_category()`, which would not be correct.

I think that inheritance being dependent on the order of a list of super categories is very much error prone and difficult to debug.

### comment:21 in reply to:  19 ; follow-up:  22 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Indeed the hom category of algebras is attributed as a subcategory of the category of vectorspaces:

```sage: Algebras(QQ).hom_category().is_subcategory(VectorSpaces(QQ))
True
```

Isn't that plainly wrong?

Yes it is plain wrong. We had discussed this early this Spring, and we even both have patches fixing this (using a different syntax) :-) See #10668.

This property only holds for full subcategories, and last time we discussed that we were looking for a syntax specifying when a category is a full subcategory of another one.

Cheers,

Nicolas

### comment:22 in reply to:  21 ; follow-up:  24 Changed 11 years ago by Simon King

Replying to nthiery:

Yes it is plain wrong. We had discussed this early this Spring, and we even both have patches fixing this (using a different syntax) :-) See #10668.

Ouch! I completely forgot about that other ticket!

This property only holds for full subcategories, and last time we discussed that we were looking for a syntax specifying when a category is a full subcategory of another one.

OK. Then I wonder what I should do here.

The purpose of this ticket is to provide containers for the morphisms and objects of a category, and to provide an acceptable speed. It is not the purpose to refactor hom categories - because that is to be done in #10668.

Hence, for now, I suggest that I will restrict myself on getting the tests pass. I guess it will be possible in a couple of days, and may require to change `HomCategory.super_categories` in the way I suggested above. But apart from that, I will not aim at refactoring everything.

### comment:23 follow-up:  25 Changed 11 years ago by Simon King

Another mathematical question:

I thought that any hom category is a sub-category of the category of sets.

Currently, `HomCategory(Objects()).super_categories()` returns `Objects()`, which is a bug anyway, because it does not return a list! But should it return `[Sets()]`? The same answer for `HomCategory(SetsWithPartialMaps()).super_categories()`?

### comment:24 in reply to:  22 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

OK. Then I wonder what I should do here.

The purpose of this ticket is to provide containers for the morphisms and objects of a category, and to provide an acceptable speed. It is not the purpose to refactor hom categories - because that is to be done in #10668.

Hence, for now, I suggest that I will restrict myself on getting the tests pass. I guess it will be possible in a couple of days, and may require to change `HomCategory.super_categories` in the way I suggested above. But apart from that, I will not aim at refactoring everything.

This sounds good. I just hope that there are not too many things that currently depends on that (buggy most of the time, but from time to time correct) inheritance.

### comment:25 in reply to:  23 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Another mathematical question:

I thought that any hom category is a sub-category of the category of sets.

Currently, `HomCategory(Objects()).super_categories()` returns `Objects()`, which is a bug anyway, because it does not return a list! But should it return `[Sets()]`? The same answer for `HomCategory(SetsWithPartialMaps()).super_categories()`?

Yes it should definitely be fixed to be a list. Now, I would tend to be safe and stick to [Objects()], unless some abstract category expert is absolutely convinced that [Sets()] is always correct (I doubt it).

### comment:26 Changed 11 years ago by Simon King

Personally, I believe that `Objects()` is not a category in the proper meaning of the word. I think for any category C and any objects A,B of C, then `Hom(A,B)` must by definition be a set.

But you are right, in case of doubt one should use `Objects()`, not `Sets()`.

### comment:27 follow-up:  32 Changed 11 years ago by Simon King

No, after all, I think that Sets() is correct.

We already have

```sage: O = Objects()
sage: H = O.HomCategory(O)
sage: H.super_categories()
[Category of sets]
```

and a comment in the doc string of `H.super_categegories`:

```            """
This declares that any homset `Hom(A, B)` for `A` and `B`
in the category of objects is a set.
This more or less assumes that the category is locally small.
See http://en.wikipedia.org/wiki/Category_(mathematics)

EXAMPLES::

sage: Objects().hom_category().super_categories()
[Category of sets]
"""
```

So, that should be fine.

### comment:28 follow-up:  30 Changed 11 years ago by Simon King

Currently, I'm having trouble with getting an appropriate class for the homsets.

You know that rings have a specially designed class for their homsets:

```sage: Rings().HomCategory
<class 'sage.categories.rings.Rings.HomCategory'>
sage: Rings().HomCategory(Rings()).parent_class.__module__
'sage.categories.rings'
```

By #9944 and #9138, polynomial rings are (commutative) algebras and not just rings. The category of algebras does not define their own `HomCategory` class.

However, two of its super categories have special `HomCategory`, namely

```sage: Modules(ZZ).HomCategory
<class 'sage.categories.modules.Modules.HomCategory'>
sage: Rings().HomCategory
<class 'sage.categories.rings.Rings.HomCategory'>
```

Wouldn't it be a good idea to create a lazy attribute `HomCategory` for `sage.categories.category.Category`, that returns a dynamic class formed by all the hom category classes of the super categories?

Hence, what I suggest means that `Algebras(ZZ).HomCategory` would be a sub-class of both `Rings().HomCategory` and `Modules(ZZ).HomCategory`. At least in this example, it would work, regardless of the order:

```sage: class Foo(Rings().HomCategory, Modules(ZZ).HomCategory): pass
....:
sage: class Foo(Modules(ZZ).HomCategory, Rings().HomCategory): pass
....:
```

As a dynamic class, we would probably have

```sage: from sage.structure.dynamic_class import dynamic_class
sage: from sage.categories.category import HomCategory
sage: dynamic_class('FooHomCategory', (Rings().HomCategory, Modules(ZZ).HomCategory, HomCategory))
<class 'sage.categories.rings.FooHomCategory'>
```

But note that putting `HomCategory` in front of the tuple or providing it as second argument after the tuple will not work.

I think that this would be a very clean solution. The method resolution order of the dynamic class would, if I understand correctly, first pick up the stuff defined for rings, then the stuff defined for modules, and finally the generic stuff of `HomCategory`.

### comment:29 follow-up:  31 Changed 11 years ago by Simon King

Perhaps a related question: In sage/categories/rings.py, we have

```    class HomCategory(HomCategory):
class ParentMethods:
def __new__(cls, X, Y, category):
from sage.rings.homset import RingHomset
return RingHomset(X, Y, category = category)
def __getnewargs__(self):
return (self.domain(), self.codomain(), self.category())
```

Wouldn't it be possible to simply have

```    class HomCategory(HomCategory):
class ParentMethods(RingHomset):
pass
```

?

### comment:30 in reply to:  28 ; follow-ups:  35  37 Changed 11 years ago by Nicolas M. Thiéry

Hi Simon!

Replying to SimonKing:

Wouldn't it be a good idea to create a lazy attribute `HomCategory` for `sage.categories.category.Category`, that returns a dynamic class formed by all the hom category classes of the super categories?

If I remember correctly, that's more or less what you had implemented for #10668 :-) Of course (and you had taken care of this), unless one is having a full subcategory, one should have this inheritance only for elements of the hom category (i.e. morphisms), not for the homsets or the category.

So ... Do you see a temporary quick fix to have #10667 work for the moment, before we go on to #10668?

Cheers,

### comment:31 in reply to:  29 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Perhaps a related question: In sage/categories/rings.py, we have

```    class HomCategory(HomCategory):
class ParentMethods:
def __new__(cls, X, Y, category):
from sage.rings.homset import RingHomset
return RingHomset(X, Y, category = category)
def __getnewargs__(self):
return (self.domain(), self.codomain(), self.category())
```

Wouldn't it be possible to simply have

```    class HomCategory(HomCategory):
class ParentMethods(RingHomset):
pass
```

?

Somehow both are wrong; I had just put that here to make the damn thing work for the moment: the category really should not be dealing with the concrete classes used to implement the Homsets. That's Hom's job at best, but we need to design a proper protocol for this.

### comment:32 in reply to:  27 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

No, after all, I think that Sets() is correct. and a comment in the doc string of `H.super_categegories`:

```            """
This declares that any homset `Hom(A, B)` for `A` and `B`
in the category of objects is a set.
This more or less assumes that the category is locally small.
See http://en.wikipedia.org/wiki/Category_(mathematics)

EXAMPLES::

sage: Objects().hom_category().super_categories()
[Category of sets]
"""
```

ROTFL. I wrote that comment. So I guess I should agree with it :-)

### comment:33 Changed 11 years ago by Simon King

Yes, it seems to work nicely with lazy attribute plus dynamic class!!

I have (to be a doctest):

```            sage: A = Algebras(ZZ)
sage: H = A.hom_category()   #indirect doctest
sage: H
Category of hom sets in Category of algebras over Integer Ring
sage: isinstance(H, Rings().HomCategory)
True
sage: isinstance(H, Modules(ZZ).HomCategory)
True
```

### comment:34 Changed 11 years ago by Simon King

PS:

I forgot to add that the super categories of the hom category are fine as well. We have:

```sage: A = Algebras(ZZ)
sage: H = A.hom_category()   #indirect doctest
sage: H.super_categories()
[Category of hom sets in Category of objects]
sage: H.an_object()
Set of Homomorphisms from Univariate Polynomial Ring in x over Integer Ring to Univariate Polynomial Ring in x over Integer Ring
sage: H.an_object().category()
Category of hom sets in Category of algebras over Integer Ring
sage: H.an_object().category().super_categories()
[Category of hom sets in Category of objects]
```

### comment:35 in reply to:  30 Changed 11 years ago by Simon King

Replying to nthiery:

So ... Do you see a temporary quick fix to have #10667 work for the moment, before we go on to #10668?

I don't know yet. I am still walking my way accross the mine field of doctest errors. For example, the idea to provide a lazy attribute dynamic class for `HomCategory` is simply a means to enable

```sage: R = QQ['z0','z1','z2','z3']
sage: R.hom(R.gens())
Ring endomorphism of Multivariate Polynomial Ring in z0, z1, z2, z3 over Rational Field
Defn: z0 |--> z0
z1 |--> z1
z2 |--> z2
z3 |--> z3
```

That easy example would have failed in the previous version of my patch.

### comment:36 follow-up:  40 Changed 11 years ago by Simon King

The tests in devel/sage/doc pass. That encourages me to post my current patch version, so that you can already have a look at it (when you have the time; I know, probably you don't...).

However, I keep it as "needs work", since I did not run the devel/sage/sage/, and since I need to check whether I really tested and documented all new functionality.

### comment:37 in reply to:  30 Changed 11 years ago by Simon King

Replying to nthiery:

So ... Do you see a temporary quick fix to have #10667 work for the moment, before we go on to #10668?

Meanwhile I think that a quick fix based on a modification of the current patch will be doable. I get 242 doctest errors related with Steenrod algebras. They seem to be caused by a wrong method resolution order, and I suppose that it can be fixed by changing the order on the list of super categories for some category. The remaining test failures seem to be harmless.

### comment:38 follow-up:  39 Changed 11 years ago by Simon King

Well, mostly harmless. Some involve to implement the category framework for uni- and multivariate power series rings. Multivariate power series rings was a recent addition - so, why has it not been done in the first place?

It seems that the 242 Steenrod errors are mostly gone. At least, `TestSuite(SteenrodAlgebra(2)).run()` works.

Time to call it a day...

### comment:39 in reply to:  38 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Well, mostly harmless. Some involve to implement the category framework for uni- and multivariate power series rings. Multivariate power series rings was a recent addition - so, why has it not been done in the first place?

Still way too much code using prehistoric stuff; so devs and reviewers don't take the right examples to start from.

It seems that the 242 Steenrod errors are mostly gone. At least, `TestSuite(SteenrodAlgebra(2)).run()` works.

Yippee!

Time to call it a day...

:-)

### comment:40 in reply to:  36 ; follow-up:  41 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

The tests in devel/sage/doc pass. That encourages me to post my current patch version, so that you can already have a look at it (when you have the time; I know, probably you don't...).

I really should take the time. At this point, I am so much behind with your patches that I am thinking we should have a face to face review sprint. Alas, I don't have yet the schedule for my classes this fall to see whether I could come to the Sage days at KL. Are you planning to come to France anytime soon?

### comment:41 in reply to:  40 Changed 11 years ago by Simon King

Replying to nthiery:

Alas, I don't have yet the schedule for my classes this fall to see whether I could come to the Sage days at KL. Are you planning to come to France anytime soon?

I will be in Kaiserslautern, but apart from that I have no plans at all. But there should be some travel money available from my project...

For the record: Steenrod algebra tests pass fully. I am still having trouble to find the right order of base classes for dynamic classes. Probably it would not be possible at all. Thus, with my current patch (not posted), I catch the resulting type error, and return a generic class (such as `Objects().HomCategory`) for implementing the hom category of a category.

### comment:42 follow-up:  49 Changed 11 years ago by Simon King

I am making some progress.

Testsuites are really a good thing! By adding tests for morphisms, I found a couple of bugs. And that's why my patch can not just be a short work-around (unless I make the Testsuites skip some tests). It will contain fixes in different parts of sage.

Just one example:

```sage: E = CombinatorialFreeModule(ZZ, [1,2,3])
sage: F = CombinatorialFreeModule(ZZ, [2,3,4])
sage: H = Hom(E, F)
sage: TestSuite(H).run()
Failure in _test_additive_associativity:
Traceback (most recent call last):
File "/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
test_method(tester = tester)
File "/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/commutative_additive_semigroups.py", line 80, in _test_additive_associativity
tester.assert_((x + y) + z == x + (y + z))
TypeError: unsupported operand type(s) for +: 'ModuleMorphismByLinearity' and 'ModuleMorphismByLinearity'
------------------------------------------------------------
Failure in _test_an_element:
Traceback (most recent call last):
File "/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/misc/sage_unittest.py", line 275, in run
test_method(tester = tester)
File "/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/categories/sets_cat.py", line 388, in _test_an_element
tester.assertEqual(self(an_element), an_element, "element construction is not idempotent")
...
```

The reason is that `dumps(H.zero())` fails:

```sage: dumps(H.zero())
---------------------------------------------------------------------------
PicklingError                             Traceback (most recent call last)

/home/king/SAGE/work/categories/objects/<ipython console> in <module>()

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/structure/sage_object.so in sage.structure.sage_object.dumps (sage/structure/sage_object.c:8274)()

/mnt/local/king/SAGE/broken/local/lib/python2.6/site-packages/sage/structure/sage_object.so in sage.structure.sage_object.SageObject.dumps (sage/structure/sage_object.c:2183)()

PicklingError: Can't pickle <type 'function'>: attribute lookup __builtin__.function failed
```

There are more of those bugs.

The good news: I think I found a stable way to get the method resolution order of hom category parent classes right.

I even tried to get rid of the odd explicit `__new__` method in `sage.categories.rings.Rings.HomCategory.ParentMethods`. But I am not sure if I will succeed.

### comment:43 follow-up:  50 Changed 11 years ago by Simon King

Work issues: doctests → Cartesian products

Just a status report: I got rid of the `__new__` method. Instead, I produce a `__classcall__` method, similar to what is done in `UniqueRepresentation` (and in fact I make `sage.categories.rings.Rings.HomCategory.ParentClass` inherit from `UniqueRepresentation`).

I have already mentioned that I added some methods to the Cartesian product categories, so that some test suites actually passed. Next, I fixed another problem with Cartesian products: It has not been possible to create Cartesian products of algebras. It neither worked in sage-4.6.2 nor in sage-4.7.2.alpha1+#9138, but failed with different errors.

```sage: C = cartesian_product([ZZ['x'], ZZ['y']])
<BOOM>
```

After my patches and the addition of the base_ring method to Cartesian product categories, the problem arose with `__init_extra__` method in `sage.categories.algebras.Algebras.ParentMethods`: The Cartesian product of algebras over a ring R is an algebra over R (apparently acting diagonally). The `__init_extra__` tries to create a coercion from the R to the cartesian product. However, that ended in an infinite recursion. I solved it by adding a `from_base_ring` method, that is understood by `__init_extra__`.

The remaining problem concerns summation of elements of Cartesian products. Multiplication is defined, via `sage.categories.magmas.Magmas.CartesianProduct.ParentMethods.product`. But summation is missing. I guess it should be implemented in `sage.categories.AdditiveMagmas.CartesianProduct.ParentMethods.summation`.

### comment:44 Changed 11 years ago by Simon King

Helas.

I fixed the Cartesian products, but now I have a couple of hundred errors in elliptic curves. The problem is that non-unique parents occur in `sage.libs.singular.ring.singular_ring_new` when constructing a multivariate polynomial ring over a number field.

I have no idea why that problem is invisible without my patch.

It seems that this ticket is a can of worms. I will keep the current bug fixes in my patch (sorry that I didn't submit it yet), but from now on new bug fixes will give rise to new tickets.

### comment:45 Changed 11 years ago by Simon King

Dependencies: #9138, #11115 → #9138, #11115, #11780

The ticket for the non-unique polynomial rings is #11780.

### Changed 11 years ago by Simon King

Attachment: trac10667-morphisms_and_objects.patch​ added

Implement the classes of morphisms and objects of a category; improve performance; some fixes relating with morphisms; `TestSuite` for all categories; add a `HomCategory` class to any category

### comment:46 Changed 11 years ago by Simon King

I have a patch at #11780 that solves the problem. I am thus also submitting my current patch on morphisms and objects. It contains many new features that I will describe later. It is still "needs work", since the patch contains some uncommented code that should eventually be deleted, and since there will certainly be a couple of "trivial" doctest errors, namely for tests that concern the super categories of a category (I had to re-order the super categories in order to get the method resolution orders right).

But if you want to play with it: Go ahead (and don't forget to apply #11780 first...).

### comment:47 Changed 11 years ago by Simon King

Nicolas, I have a question on the category of schemes. In `sage.categories.schemes.Schemes.HomCategory`, there is a comment saying

```            FIXME: what category structure is there on Homsets of schemes?
The result above is wrong, and should be fixed during the next
homsets overhaul.
```

Is there any answer? What is the category structure?

### comment:48 Changed 11 years ago by Simon King

Helas. The number of errors has decreased with the new patch. However, there remain numerous errors of the same kind ("there is some non-unique parent and thus the coercion system complains"). #11780 fixed many of these errors, but not all.

### comment:49 in reply to:  42 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

I am making some progress.

Testsuites are really a good thing!

:-)

The good news: I think I found a stable way to get the method resolution order of hom category parent classes right.

Nice!

### comment:50 in reply to:  43 ; follow-up:  51 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Just a status report: I got rid of the `__new__` method. Instead, I produce a `__classcall__` method,

Sounds good. I guess I had not yet implemented classcall when I wrote the new workarounds.

similar to what is done in `UniqueRepresentation` (and in fact I make `sage.categories.rings.Rings.HomCategory.ParentClass` inherit from `UniqueRepresentation`).

I am not absolutely sure about this: as for parents, it is recommended for Homsets to have unique representation, but I am not sure this is currently *required* and *enforced*. So this may open a larger can of worm than this ticket can handle. This might be the issue you encountered with polynomials.

After my patches and the addition of the base_ring method to Cartesian product categories, the problem arose with `__init_extra__` method in `sage.categories.algebras.Algebras.ParentMethods`: The Cartesian product of algebras over a ring R is an algebra over R (apparently acting diagonally). The `__init_extra__` tries to create a coercion from the R to the cartesian product. However, that ended in an infinite recursion. I solved it by adding a `from_base_ring` method, that is understood by `__init_extra__`.

Cool!

The remaining problem concerns summation of elements of Cartesian products. Multiplication is defined, via `sage.categories.magmas.Magmas.CartesianProduct.ParentMethods.product`. But summation is missing. I guess it should be implemented in `sage.categories.AdditiveMagmas.CartesianProduct.ParentMethods.summation`.

Thanks for implementing this missing piece!

Cheers,

Nicolas

### comment:51 in reply to:  50 ; follow-up:  52 Changed 11 years ago by Simon King

Replying to nthiery:

Replying to SimonKing: I am not absolutely sure about this: as for parents, it is recommended for Homsets to have unique representation, but I am not sure this is currently *required* and *enforced*.

First of all, Homsets are cached. But using unique representation, it is less easy to break the cache.

And I think that we should use any opportunity to reduce the number of violations of the unique parent assumption. After all, it is a matter of efficiency.

This might be the issue you encountered with polynomials.

Actually it was. The problem was that (for the sake of explicit documentation) some tests create a polynomial ring directly, not using the `PolynomialRing` constructor. My solution: I introduced a parent method for rings, that removes the ring from the homset cache, and use it after any test that creates a non-unique parent. Of course, it is for internal use only.

### comment:52 in reply to:  51 ; follow-up:  53 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

First of all, Homsets are cached. But using unique representation, it is less easy to break the cache.

I am glad that UniqueRepresentation? works well :-)

And I think that we should use any opportunity to reduce the number of violations of the unique parent assumption. After all, it is a matter of efficiency.

Agreed, the more unique parents, the better. But you don't have to fix all of Sage misfeatures in just this patch :-)

Besides, I am still not yet sure that we want to strictly enforce 100% unique parents. There might be occasional exceptions -- I don't know, things like temporarily created parents or what not -- where we might want to not have uniqueness.

Actually it was. The problem was that (for the sake of explicit documentation) some tests create a polynomial ring directly, not using the `PolynomialRing` constructor. My solution: I introduced a parent method for rings, that removes the ring from the homset cache, and use it after any test that creates a non-unique parent. Of course, it is for internal use only.

Ok. I could see other use cases. Should this be a method of UniqueRepresentation? -- of course still for internal use ?

Cheers,

Nicolas

### comment:53 in reply to:  52 ; follow-up:  57 Changed 11 years ago by Simon King

Replying to nthiery:

I am glad that UniqueRepresentation? works well :-)

I am not 100% certain that they work well. At least for getting the tests of elliptic curves pass, we probably need #11670 (uniqueness of number fields). And note that (currently) I only introduce `UniqueRepresentation` to homsets of rings. I did not try to have it for all parents.

Agreed, the more unique parents, the better. But you don't have to fix all of Sage misfeatures in just this patch :-)

But all that were uncovered by new tests introduced with this patch.

Besides, I am still not yet sure that we want to strictly enforce 100% unique parents. There might be occasional exceptions -- I don't know, things like temporarily created parents or what not -- where we might want to not have uniqueness.

Why would one not want uniqueness for temporarily created parents? When the same parent is frequently created, then it is more efficient to just use a cache. Or are you concerned that one creates too many different parents that will stay in cache forever?

Ok. I could see other use cases. Should this be a method of UniqueRepresentation? -- of course still for internal use ?

No, what I just wrote can't be a method of `UniqueRepresentation`. Here is the purpose of what I wrote: Let X be a ring; `X._remove_from_homset_cache()` removes `Hom(X,Y)` and `Hom(Y,X)` from cache, for any ring `Y`.

Hence, it is not `X.__class__.__classcall__.cache` that is cleared, but `X.category().hom_category().parent_class.__classcall__.cache`. And an item is removed from the cache not if X is the value of that item, but if X appears in the key of the item.

But I think it would be a good idea to add a `X._reduce_from_cache()` method to `UniqueRepresentation`: It would remove any item of `X.__class__.__classcall__.cache` whose value is (equal to) X, and then it would try `X._reduce_from_homset_cache()` as well (which would of course only be available for rings).

### comment:54 Changed 11 years ago by Simon King

It turns out that #11670 will not solve the problem. But it seems to me that I come closer to a solution: In contrast to many other cases, hom sets of number fields are not unique parents. With my patch, they are even less unique. Here is a show case:

sage-4.6.2

```sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: Hom(N,N) is Hom(N,N)
False
sage: Hom(N,N) == Hom(N,N)
True
```

With my patch, we still have

```sage: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: Hom(N,N) is Hom(N,N)
False
```

but then

```sage: Hom(N,N) == Hom(N,N)
False
```

I don't know yet why this is the case, because the `__cmp__` function of number field homsets did not change.

### comment:55 follow-up:  58 Changed 11 years ago by Simon King

Aha! I understand!

`Hom(N,N)` reduces to `N._Hom_(N)`, which directly constructs a number field hom set.

By consequence, `Hom(N,N)` does not become a unique parent, even though it inherits from `UniqueRepresentation` via inheritance from the category. But that inheritance takes place after creation of the hom set, so that it is too late for `Rings().HomCategory.ParentMethods.__classcall__`.

In other words: Via category inheritance, `Hom(N,N)` inherits `__eq__` from `UniqueRepresentation`, which is used for comparison and precedes the use of the custom `__cmp__` method of number field homsets. However, `__eq__` expects unique parents.

We thus have:

```age: N = NumberField(x^12 - 4*x^11 + 6*x^10 - 5*x^9 + 5*x^8 - 9*x^7 + 21*x^6 - 9*x^5 + 5*x^4 - 5*x^3 + 6*x^2 - 4*x + 1, 'a')
sage: H = Hom(N,N)
sage: H == Hom(N,N)
False
sage: H > Hom(N,N)
False
sage: H < Hom(N,N)
False
```

I guess, until number fields are truly unique parents, I should add an `__eq__` to number field hom sets, in order to not have it inherited from `UniqueRepresentation`.

### comment:56 Changed 11 years ago by Simon King

Work issues: Cartesian products → Cope with non-unique number fields

I think I found a valid work-around: Sometimes, a number field is created with passing the option `cache=False` to the number field constructor. If that option is used, I suggest to call the new `_remove_from_homset_cache`. It seems to work!

With that change (not yet posted), we have

```sage: E = EllipticCurve('389a'); P = E.heegner_point(-7, 5); P
Heegner point of discriminant -7 and conductor 5 on elliptic curve of conductor 389
sage:  z = P.point_exact(100, optimize=True)
```

With the old patch, one would have the following error:

```AssertionError: BUG in coercion model
Apparently there are two versions of
Number Field in a with defining polynomial x^12 + 4*x^11 + 56*x^10 + 170*x^9 + 1130*x^8 + 2564*x^7 + 10791*x^6 + 18054*x^5 + 51340*x^4 + 57530*x^3 + 102986*x^2 + 53724*x + 35001
in the cache.
```

Running doctests, and then I hope the most serious problems have finally disappeared...

### comment:57 in reply to:  53 ; follow-up:  59 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

Why would one not want uniqueness for temporarily created parents? When the same parent is frequently created, then it is more efficient to just use a cache. Or are you concerned that one creates too many different parents that will stay in cache forever?

Possibly so. Or about creating many different parents that each need a lot of input data, or maybe some non hashable data; and maybe you need each such parent only once. So the overhead in time or code complexity of guaranteeing unique representation would not be worth it.

Honestly, I don't have a specific use case, just a bad feeling about it.

But I think it would be a good idea to add a `X._reduce_from_cache()` method to `UniqueRepresentation`: It would remove any item of `X.__class__.__classcall__.cache` whose value is (equal to) X,

+1. I am not sure about the name though. What about something like _delete_from_cache instead?

and then it would try `X._reduce_from_homset_cache()` as well (which would of course only be available for rings).

UniqueRepresentation? is meant to also be used by non Parents. So I'd rather have nothing Parent-related in it. On the other hand, Parent could overload UniqueRepresentation?'s method to also call that for homsets.

Cheers,

Nicolas

### comment:58 in reply to:  55 ; follow-up:  60 Changed 11 years ago by Nicolas M. Thiéry

Hi Simon,

Replying to SimonKing:

Aha! I understand!

:-)

I guess, until number fields are truly unique parents, I should add an `__eq__` to number field hom sets, in order to not have it inherited from `UniqueRepresentation`.

I am not very keen on having a class inherit (indirectly) from UniqueRepresentation?, and then hacking it's way around to actually not have to implement the unique representation protocole. I'd rather only inherit explicitly from UniqueRepresentation? when I mean it.

Cheers,

### comment:59 in reply to:  57 ; follow-up:  64 Changed 11 years ago by Simon King

Replying to nthiery:

But I think it would be a good idea to add a `X._reduce_from_cache()` method to `UniqueRepresentation`: It would remove any item of `X.__class__.__classcall__.cache` whose value is (equal to) X,

+1. I am not sure about the name though. What about something like _delete_from_cache instead?

Sorry, I meant to write `_remove_from_cache`, not `_reduce_from_cache`.

and then it would try `X._reduce_from_homset_cache()` as well (which would of course only be available for rings).

UniqueRepresentation? is meant to also be used by non Parents.

And `_reduce_from_homset_cache` is only for those parents that happen to belong to the category of rings. That's why I write "try ... (which would ... only be available for rings)". It would not be available for non-rings, and in particular not for non-parents. So, no problem, the attribute error would be caught anyway.

Parent could overload UniqueRepresentation?'s method to also call that for homsets.

No, it could not, because most parents are no `UniqueRepresentation`s.

### comment:60 in reply to:  58 ; follow-up:  63 Changed 11 years ago by Simon King

Replying to nthiery:

I am not very keen on having a class inherit (indirectly) from UniqueRepresentation?, and then hacking it's way around to actually not have to implement the unique representation protocole. I'd rather only inherit explicitly from UniqueRepresentation? when I mean it.

Yes, what I did doesn't fully convince me.

With my patch, the `Rings().HomCategory.ParentMethods` inherits from `UniqueRepresentation`, and since `NumberFields()` is a sub-category of `Rings()`, the default `NumberFields().hom_category().parent_class inherits from `UniqueRepresentation?` as well.

But it would be possible to have a custom `NumberFields().HomCategory.ParentMethods`, similar to the custom `Rings().HomCategory.ParentMethods`.

While `Rings().hom_category().parent_class` with my patch inherits from `UniqueRepresentation` and (via classcall) from either `sage.rings.homset.RingHomset_generic` or `sage.rings.homset.RingHomset_quo_ring`, one could have `NumberFields().hom_category().parent_class` inherit from `sage.rings.number_field.morphism.NumberFieldHomset`, but not from `UniqueRepresentation`.

### comment:61 follow-up:  62 Changed 11 years ago by Simon King

Next: I accidentally found that quotient rings are no unique parents either.

I guess they should be, right?

### comment:62 in reply to:  61 Changed 11 years ago by Simon King

Replying to SimonKing:

Next: I accidentally found that quotient rings are no unique parents either.

I guess they should be, right?

Dealt with on a different ticket, I mean...

### comment:63 in reply to:  60 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

But it would be possible to have a custom `NumberFields().HomCategory.ParentMethods`, similar to the custom `Rings().HomCategory.ParentMethods`.

While `Rings().hom_category().parent_class` with my patch inherits from `UniqueRepresentation` and (via classcall) from either `sage.rings.homset.RingHomset_generic` or `sage.rings.homset.RingHomset_quo_ring`, one could have `NumberFields().hom_category().parent_class` inherit from `sage.rings.number_field.morphism.NumberFieldHomset`, but not from `UniqueRepresentation`.

Sound good.

### comment:64 in reply to:  59 Changed 11 years ago by Nicolas M. Thiéry

Replying to SimonKing:

And `_reduce_from_homset_cache` is only for those parents that

happen to belong to the category of rings. That's why I write "try ... (which would ... only be available for rings)". It would not be available for non-rings, and in particular not for non-parents. So, no problem, the attribute error would be caught anyway.

Yes, it would work. Yet, in a perfect world, UniqueRepresentation? ought to be generalized outside of Sage, as a general purpose Python tool (even though I am not sure anyone will take the time for that). So having some logic in there specifically targetted toward homsets smells. But maybe it's just a question of finding a more general name for this hook.

No, it could not, because most parents are no `UniqueRepresentation`s.

Good point :-)

### comment:65 Changed 11 years ago by Simon King

Keywords: sd34 added

I am not sure if the attached patch is up to date. Unfortunately, applying it to sage-4.7.2.alpha3 gives 5 hunks that fail to apply. I hope that I'll be able to get finally a working version during the upcoming sage days 34.

### comment:66 Changed 9 years ago by Jeroen Demeyer

Milestone: sage-5.11 → sage-5.12

### comment:67 Changed 9 years ago by For batch modifications

Milestone: sage-6.1 → sage-6.2

### comment:68 Changed 9 years ago by For batch modifications

Milestone: sage-6.2 → sage-6.3

### comment:69 Changed 8 years ago by For batch modifications

Milestone: sage-6.3 → sage-6.4

### comment:70 Changed 8 years ago by Simon King

Let us see if anything from this patch could be useful in the current state of the art. See #10668 and #16340.

### comment:71 Changed 8 years ago by Jean-Pierre Flori

Cc: Jean-Pierre Flori added
Note: See TracTickets for help on using tickets.