Use the correct categories for coercion and conversion maps

[pbruin]

The following examples show that some convert_maps are incorrectly assumed to be homomorphisms:

sage: f = ZZ.convert_map_from(QQ)
sage: f.parent()
Set of Homomorphisms from Rational Field to Integer Ring

sage: f = ZZ.convert_map_from(GF(2))
sage: f.parent() 
Set of field embeddings from Finite Field of size 2 to Integer Ring

sage: f = GF(11).convert_map_from(GF(7))
sage: f
Conversion map:
  From: Finite Field of size 7
  To:   Finite Field of size 11
sage: f.parent()
Set of field embeddings from Finite Field of size 7 to Finite Field of size 11

This has the effect of constructing an element of a set that is in fact empty. A conversion map should in general only be a morphisms in the category of sets with partial maps, because it is not necessarily defined everywhere. (In case it is defined everywhere, it may of course be placed in the category of sets.)

This ticket fixes the problem in two steps:

• use SetsWithPartialMaps as the category for DefaultConvertMap;
• make internal ("reference-weakened") coercion and conversion maps remember their category (the fact that this didn't work was revealed by the above change).

See also ​https://groups.google.com/forum/#!topic/sage-devel/Z4iNgVMFoms

[pbruin]

In the attached branch, I tried to make DefaultConvertMap return a morphism in the category of schemes with partial maps. Unfortunately, a recent change in #14711 (where certain references in the coercion system were made into weak references) makes the map forget its parent Homset, and hence in which category it lives.

Example (cf. the code producing the debugging output):

sage: ZZ.convert_map_from(CC)
old parent = Set of Morphisms from Complex Field with 53 bits of precision to Integer Ring in Category of sets with partial maps
new parent = Set of Homomorphisms from Complex Field with 53 bits of precision to Integer Ring
Conversion map:
  From: Complex Field with 53 bits of precision
  To:   Integer Ring

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

​0e48aa9	make DefaultConvertMap a morphism in SetsWithPartialMaps()
​d92ec90	add Map._category_for and Map._set_parent()
​d0e43bc	Trac 15618: fix category of the Q_to_Z morphism

[pbruin]

Basically works, needs documentation and there are various failing doctests.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d96f19e

Trac 15618: do not change category in FiniteDimensionalAlgebra._Hom_()

[pbruin]

Remaining doctest failures (the first is due to #16311):

sage -t --long src/sage/structure/sage_object.pyx  # 1 doctest failed
sage -t --long src/sage/groups/additive_abelian/additive_abelian_wrapper.py  # 2 doctests failed

[pbruin]

This dependency is needed to get the category right for finite field embeddings.

[pbruin]

Needed to get the category right for homesets whose domain is a FGP_Module.

[pbruin]

After #16401 and #16402, the only remaining problem is an unpickling failure of 3 old pickles:

File "src/sage/structure/sage_object.pyx", line 1346, in sage.structure.sage_object.unpickle_all
Failed example:
    sage.structure.sage_object.unpickle_all()  # (4s on sage.math, 2011)
Expected:
    doctest:... DeprecationWarning: This class is replaced by Matrix_modn_dense_float/Matrix_modn_dense_double.
    See http://trac.sagemath.org/4260 for details.
    Successfully unpickled ... objects.
    Failed to unpickle 0 objects.
Got:
    doctest:1: DeprecationWarning: OrderedAlphabet is deprecated; use Alphabet instead.
    See http://trac.sagemath.org/8920 for details.
    doctest:839: DeprecationWarning: This class is replaced by Matrix_modn_dense_float/Matrix_modn_dense_double.
    See http://trac.sagemath.org/4260 for details.
     * unpickle failure: load('/home/pbruin/.sage/temp/selmer/22153/dir_6q6dfL//pickle_jar/_class__sage_modular_hecke_degenmap_DegeneracyMap__.sobj')
     * unpickle failure: load('/home/pbruin/.sage/temp/selmer/22153/dir_6q6dfL//pickle_jar/_type__sage_rings_morphism_RingHomomorphism_cover__.sobj')
     * unpickle failure: load('/home/pbruin/.sage/temp/selmer/22153/dir_6q6dfL//pickle_jar/_type__sage_rings_morphism_RingHomomorphism_from_quotient__.sobj')
    Failed:
    _class__sage_modular_hecke_degenmap_DegeneracyMap__.sobj
    _type__sage_rings_morphism_RingHomomorphism_cover__.sobj
    _type__sage_rings_morphism_RingHomomorphism_from_quotient__.sobj
    ----------------------------------------------------------------------
    ** This error is probably due to an old pickle failing to unpickle.
    ** See sage.structure.sage_object.register_unpickle_override for
    ** how to override the default unpickling methods for (old) pickles.
    ** NOTE: pickles should never be removed from the pickle_jar!
    ----------------------------------------------------------------------
    Successfully unpickled 583 objects.
    Failed to unpickle 3 objects.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​d261a37

Trac 15618: delay setting _category_for to avoid unpickling trouble

[pbruin]

The new commit solves the unpickling problem, all tests now pass. (The pickles weren't necessarily broken, my patch was trying to access the category of partially-unpickled homsets.)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​54a6eca

Trac 15618: add doctests

[pbruin]

Note to reviewer(s): the branches of the dependencies (#16401, #16402) are not merged in this branch.

[pbruin]

In the current branch, there is a new Map._category_for attribute that is always a strong reference. I later thought that instead of this, it might be better to treat category_for in an analogous way to domain, i.e. to make it an attribute that can be either a ConstantFunction or to a weakref. I'm undecided for the moment, so I'm keeping the original branch in the ticket description.

The alternative branch (including #16401 and #16402) is u/pbruin/15618-convert_map_category (​diff, ​commits).

[pbruin]

The dependencies are merged in this branch, for the benefit of reviewers and the patchbot. The current branch is now simply one commit behind the branch u/pbruin/15618-convert_map_category of comment:16.

[pbruin]

(Setting the branch back to u/pbruin/15618-DefaultConvertMap since the dependencies have now been merged into develop and the previous branch would not merge automatically.)

[jpflori]

This looks like an improvement to me.

But it gives me a bunch of failures (on top of 6.5.beta0):

sage -t --long --warn-long 156.2 src/sage/schemes/generic/homset.py  # 1 doctest failed
sage -t --long --warn-long 156.2 src/sage/schemes/generic/scheme.py  # 1 doctest failed
sage -t --long --warn-long 156.2 src/sage/schemes/projective/projective_homset.py  # 1 doctest failed
sage -t --long --warn-long 156.2 src/sage/schemes/generic/spec.py  # 1 doctest failed
sage -t --long --warn-long 156.2 src/sage/schemes/generic/morphism.py  # 19 doctests failed
sage -t --long --warn-long 156.2 src/sage/schemes/affine/affine_homset.py  # 1 doctest failed
sage -t --long --warn-long 156.2 src/sage/categories/schemes.py  # 4 doctests failed

[jpflori]

All errors seem to be of the following form:

f = S(g)
...
ValueError: Set of morphisms
      From: Spectrum of ...
      To:   Spectrum of ... is not in Category of sets with partial maps

[jpflori]

I guess #10668 is the culprit.

@Nicolas: any trivial fix for this?

[pbruin]

The problem seems to be that the category Schemes().Homsets() does not have Sets() as a supercategory:

sage: Sets().Homsets().all_super_categories()
[Category of homsets of sets,
 Category of homsets,
 Category of sets,
 Category of sets with partial maps,
 Category of objects]
sage: Schemes().Homsets().all_super_categories()
[Category of homsets of schemes,
 Category of objects]

[jpflori]

I kind of think the same thing.

For sure, also getting Nicolas' mind would be helpful :)

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​02702bd	Merge branch 'develop' into ticket/15618-DefaultConvertMap
​bb452a7	Trac 15618: remove incorrect class Schemes.Homsets

[pbruin]

The last commit seems to fix the bugs.

Nicolas: I think we can safely remove the Schemes.Homsets class with its extra_super_categories method, as in this commit. However, is it the intended behaviour that the former presence of this class + method caused Schemes().Homsets() to acquire fewer supercategories? What is the explanation for this?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​b3cc973

Trac 15618: fix typesetting

[git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

[pbruin]

I think it is better to solve that problem on a new ticket. This is now #17359.

[pbruin]

Replying to pbruin:

In the current branch, there is a new Map._category_for attribute that is always a strong reference. I later thought that instead of this, it might be better to treat category_for in an analogous way to domain, i.e. to make it an attribute that can be either a ConstantFunction or to a weakref. I'm undecided for the moment, so I'm keeping the original branch in the ticket description.

Since the alternative branch u/pbruin/15618-convert_map_category may still be relevant (to prevent potential memory leaks), I rebased it (​diff, ​commits).

[nbruin]

Just this line:

if category.is_subcategory(FiniteDimensionalAlgebrasWithBasis(self.base_ring()))

is a memory leak:

sage: import gc
sage: from collections import Counter
sage: gc.collect()
93
sage: pre={id(a) for a in gc.get_objects()}
sage: 
sage: for p in prime_range(20000):
....:         A =  FiniteDimensionalAlgebrasWithBasis(GF(p))
....:     
sage: gc.collect()
0
sage: post=Counter(str(type(a)) for a in gc.get_objects() if id(a) not in pre)
sage: post
Counter({"<type 'tuple'>": 314633, "<type 'dict'>": 106360, "<type 'list'>": 88464, "<type 'cell'>": 67894, "<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>": 52032, "<type 'weakref'>": 40733, "<class 'weakref.KeyedRef'>": 36193, "<type 'function'>": 33947, "<type 'staticmethod'>": 33947, "<type 'builtin_function_or_method'>": 33938, "<type 'sage.misc.cachefunc.CachedMethodCaller'>": 33937, "<type 'frozenset'>": 33933, "<class 'sage.structure.dynamic_class.DynamicClasscallMetaclass'>": 33932, "<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>": 25868, "<type 'sage.structure.coerce_dict.MonoDict'>": 4522, "<type 'sage.structure.coerce_dict.MonoDictEraser'>": 4522, "<class 'sage.categories.unital_algebras.UnitalAlgebras_with_category'>": 2262, "<class 'sage.categories.vector_spaces.VectorSpaces.WithBasis_with_category'>": 2262, "<class 'sage.categories.bimodules.Bimodules_with_category'>": 2262, "<class 'sage.categories.unital_algebras.UnitalAlgebras.WithBasis_with_category'>": 2262, "<class 'sage.categories.algebras.Algebras_with_category'>": 2262, "<class 'sage.categories.left_modules.LeftModules_with_category'>": 2262, "<class 'sage.categories.vector_spaces.VectorSpaces_with_category'>": 2262, "<class 'sage.categories.right_modules.RightModules_with_category'>": 2262, "<class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis_with_category'>": 2262, "<class 'sage.categories.modules_with_basis.ModulesWithBasis_with_category'>": 2262, "<class 'sage.categories.algebras_with_basis.AlgebrasWithBasis_with_category'>": 2262, "<class 'sage.categories.magmatic_algebras.MagmaticAlgebras.WithBasis_with_category'>": 2262, "<class 'sage.categories.associative_algebras.AssociativeAlgebras_with_category'>": 2262, "<class 'sage.categories.modules.Modules_with_category'>": 2262, "<type 'sage.structure.coerce_dict.TripleDict'>": 2261, "<class 'sage.rings.ideal.Ideal_pid'>": 2261, "<type 'sage.rings.finite_rings.integer_mod.NativeIntStruct'>": 2261, "<class 'sage.categories.magmatic_algebras.MagmaticAlgebras_with_category'>": 2261, "<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>": 2261, "<type 'sage.structure.coerce_dict.TripleDictEraser'>": 2261, "<type 'instancemethod'>": 2261, "<class 'sage.structure.dynamic_class.DynamicMetaclass'>": 15, "<class '_ast.Call'>": 3, "<type 'sage.misc.constant_function.ConstantFunction'>": 2, "<class '_ast.Name'>": 2, "<type 'frame'>": 1, "<type 'set'>": 1, "<class '_ast.comprehension'>": 1, "<class '_ast.Interactive'>": 1, "<class 'sage.categories.finite_dimensional_modules_with_basis.FiniteDimensionalModulesWithBasis_with_category'>": 1, "<class '_ast.Module'>": 1, "<type 'sage.categories.category_singleton.Category_contains_method_by_parent_class'>": 1, "<type 'listiterator'>": 1, "<type 'generator'>": 1, "<class '_ast.Assign'>": 1, "<class 'sage.categories.modules.Modules.FiniteDimensional_with_category'>": 1})

The problem is that categories themselves have infinite life, so one should not instantiate parametrized categories unless one really has to. To this end we now have:

sage: GF(3)['x'].category()
Join of Category of euclidean domains and Category of commutative algebras over (finite fields and subquotients of monoids and quotients of semigroups)

(as you can see, the category doesn't explicitly link to GF(3) anymore) Admittedly:

sage: FiniteDimensionalAlgebra(GF(3), [Matrix([[1, 0], [0, 1]]), Matrix([[0, 1], [0, 0]])]).category()
Category of finite dimensional algebras with basis over Finite Field of size 3

so the memory leak already exists for FiniteDimensionalAlgebra in general. However, since you're introducing the line here, you should probably argue why you're not making the problem worse and/or open a ticket about the memory leak in general.

[jpflori]

Replying to pbruin:

The last commit seems to fix the bugs.

Nicolas: I think we can safely remove the Schemes.Homsets class with its extra_super_categories method, as in this commit. However, is it the intended behaviour that the former presence of this class + method caused Schemes().Homsets() to acquire fewer supercategories? What is the explanation for this?

Thanks for cc'ing Nicolas as I forgot to do so!

[jpflori]

Replying to nbruin:

Just this line:

if category.is_subcategory(FiniteDimensionalAlgebrasWithBasis(self.base_ring()))

is a memory leak:

sage: import gc
sage: from collections import Counter
sage: gc.collect()
93
sage: pre={id(a) for a in gc.get_objects()}
sage: 
sage: for p in prime_range(20000):
....:         A =  FiniteDimensionalAlgebrasWithBasis(GF(p))
....:     
sage: gc.collect()
0
sage: post=Counter(str(type(a)) for a in gc.get_objects() if id(a) not in pre)
sage: post
Counter({"<type 'tuple'>": 314633, "<type 'dict'>": 106360, "<type 'list'>": 88464, "<type 'cell'>": 67894, "<type 'sage.misc.cachefunc.CachedMethodCallerNoArgs'>": 52032, "<type 'weakref'>": 40733, "<class 'weakref.KeyedRef'>": 36193, "<type 'function'>": 33947, "<type 'staticmethod'>": 33947, "<type 'builtin_function_or_method'>": 33938, "<type 'sage.misc.cachefunc.CachedMethodCaller'>": 33937, "<type 'frozenset'>": 33933, "<class 'sage.structure.dynamic_class.DynamicClasscallMetaclass'>": 33932, "<type 'sage.rings.finite_rings.integer_mod.IntegerMod_int'>": 25868, "<type 'sage.structure.coerce_dict.MonoDict'>": 4522, "<type 'sage.structure.coerce_dict.MonoDictEraser'>": 4522, "<class 'sage.categories.unital_algebras.UnitalAlgebras_with_category'>": 2262, "<class 'sage.categories.vector_spaces.VectorSpaces.WithBasis_with_category'>": 2262, "<class 'sage.categories.bimodules.Bimodules_with_category'>": 2262, "<class 'sage.categories.unital_algebras.UnitalAlgebras.WithBasis_with_category'>": 2262, "<class 'sage.categories.algebras.Algebras_with_category'>": 2262, "<class 'sage.categories.left_modules.LeftModules_with_category'>": 2262, "<class 'sage.categories.vector_spaces.VectorSpaces_with_category'>": 2262, "<class 'sage.categories.right_modules.RightModules_with_category'>": 2262, "<class 'sage.categories.finite_dimensional_algebras_with_basis.FiniteDimensionalAlgebrasWithBasis_with_category'>": 2262, "<class 'sage.categories.modules_with_basis.ModulesWithBasis_with_category'>": 2262, "<class 'sage.categories.algebras_with_basis.AlgebrasWithBasis_with_category'>": 2262, "<class 'sage.categories.magmatic_algebras.MagmaticAlgebras.WithBasis_with_category'>": 2262, "<class 'sage.categories.associative_algebras.AssociativeAlgebras_with_category'>": 2262, "<class 'sage.categories.modules.Modules_with_category'>": 2262, "<type 'sage.structure.coerce_dict.TripleDict'>": 2261, "<class 'sage.rings.ideal.Ideal_pid'>": 2261, "<type 'sage.rings.finite_rings.integer_mod.NativeIntStruct'>": 2261, "<class 'sage.categories.magmatic_algebras.MagmaticAlgebras_with_category'>": 2261, "<class 'sage.rings.finite_rings.finite_field_prime_modn.FiniteField_prime_modn_with_category'>": 2261, "<type 'sage.structure.coerce_dict.TripleDictEraser'>": 2261, "<type 'instancemethod'>": 2261, "<class 'sage.structure.dynamic_class.DynamicMetaclass'>": 15, "<class '_ast.Call'>": 3, "<type 'sage.misc.constant_function.ConstantFunction'>": 2, "<class '_ast.Name'>": 2, "<type 'frame'>": 1, "<type 'set'>": 1, "<class '_ast.comprehension'>": 1, "<class '_ast.Interactive'>": 1, "<class 'sage.categories.finite_dimensional_modules_with_basis.FiniteDimensionalModulesWithBasis_with_category'>": 1, "<class '_ast.Module'>": 1, "<type 'sage.categories.category_singleton.Category_contains_method_by_parent_class'>": 1, "<type 'listiterator'>": 1, "<type 'generator'>": 1, "<class '_ast.Assign'>": 1, "<class 'sage.categories.modules.Modules.FiniteDimensional_with_category'>": 1})

The problem is that categories themselves have infinite life, so one should not instantiate parametrized categories unless one really has to. To this end we now have:

sage: GF(3)['x'].category()
Join of Category of euclidean domains and Category of commutative algebras over (finite fields and subquotients of monoids and quotients of semigroups)

(as you can see, the category doesn't explicitly link to GF(3) anymore) Admittedly:

sage: FiniteDimensionalAlgebra(GF(3), [Matrix([[1, 0], [0, 1]]), Matrix([[0, 1], [0, 0]])]).category()
Category of finite dimensional algebras with basis over Finite Field of size 3

so the memory leak already exists for FiniteDimensionalAlgebra in general. However, since you're introducing the line here, you should probably argue why you're not making the problem worse and/or open a ticket about the memory leak in general.

For clarity, I would suggest to open another ticket for that. And make it a dependency here (or not if we consider the situation is not worsened by the current ticket.)

[jpflori]

Unless it's solved by Peter's alternative branch of course.

[nbruin]

Replying to jpflori:

For clarity, I would suggest to open another ticket for that. And make it a dependency here (or not if we consider the situation is not worsened by the current ticket.)

Perhaps use #17360 for that. Please do glance through the rest of your code to check if similar changes are warranted (which can then be implemented either here, on #17360, or another follow-on ticket)

[nthiery]

Replying to pbruin:

Nicolas: I think we can safely remove the Schemes.Homsets class with its extra_super_categories method, as in this commit.

Cool.

However, is it the intended behaviour that the former presence of this class + method caused Schemes().Homsets() to acquire fewer supercategories? What is the explanation for this?

Thanks for spotting this as this was a bug. See #17364.

[pbruin]

Replying to nbruin:

Just this line:

if category.is_subcategory(FiniteDimensionalAlgebrasWithBasis(self.base_ring()))

is a memory leak:

[...]

Admittedly:

sage: FiniteDimensionalAlgebra(GF(3), [Matrix([[1, 0], [0, 1]]), Matrix([[0, 1], [0, 0]])]).category()
Category of finite dimensional algebras with basis over Finite Field of size 3

so the memory leak already exists for FiniteDimensionalAlgebra in general. However, since you're introducing the line here, you should probably argue why you're not making the problem worse and/or open a ticket about the memory leak in general.

This change is necessary because otherwise we get errors if the provided category (which is SetsWithPartialMaps() in some cases) is not a subcategory of FiniteDimensionalAlgebrasWithBasis(self.base_ring()). Logically, the choice whether the homset should be of type FiniteDimensionalAlgebraHomset should depend on the category, not vice versa.

This ticket does not make the memory leak (much) worse, because in most cases B will be a FiniteDimensionalAlgebra anyway, in which case the same category is constructed.

I also tested (using your example and in addition constructing A.coerce_map_from(GF(p)) for each A in the loop) that the current branch does not cause additional memory leaks, and that the existing leak is fixed by #17360 both before and after applying my branch. Thus the alternative branch (comment:31) doesn't seem to be needed.

[jpflori]

I agree this does not make the leak much worse. And the leak should be fixed in #17360.