Unique representation for homsets

[nthiery]

The unique representation of homsets is taken care of by Hom. What's missing is:

• Fast hash and comparison by id. This can be implemented by having Homset inherit from WithEqualityById
• Pickling by construction, calling back Hom(domain, codomain, category)

CC: @sagetrac-sage-combinat @simon-king-jena @jpflori

Component: categories

Author: Simon King

Branch/Commit: e2d2f16

Reviewer: Travis Scrimshaw

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

[nthiery]

comment:1

To discuss: the exact semantic for homsets of non unique parents

[simon-king-jena]

comment:2

Observation: If one uses WithEqualityById, many tests in sage.modular and sage.schemes fail with unprintable assertion errors.

We need to discuss whether we "simply" fix them, or better continue to compare homsets by equality (not identity) of domain and codomain.

In other words, we might end up with just providing a default pickling for homsets, which is currently missing.

[simon-king-jena]

comment:3

When using WithEqualityByid and a default __reduce__ method, we'd get (sorted by "section"):

Schemes:

sage -t sage/schemes/elliptic_curves/padic_lseries.py  # 1 doctest failed
sage -t sage/schemes/elliptic_curves/ell_curve_isogeny.py  # 18 doctests failed
sage -t sage/schemes/elliptic_curves/ell_point.py  # 8 doctests failed
sage -t sage/schemes/elliptic_curves/ell_finite_field.py  # 1 doctest failed
sage -t sage/schemes/projective/projective_space.py  # 2 doctests failed
sage -t sage/schemes/elliptic_curves/isogeny_class.py  # 1 doctest failed
sage -t sage/schemes/affine/affine_space.py  # 1 doctest failed
sage -t sage/schemes/generic/homset.py  # 2 doctests failed

Modular:

sage -t sage/modular/local_comp/local_comp.py  # 5 doctests failed
sage -t sage/modular/abvar/abvar.py  # 2 doctests failed
sage -t sage/modular/hecke/submodule.py  # 1 doctest failed
sage -t sage/modular/abvar/homspace.py  # 1 doctest failed
sage -t sage/modular/modsym/subspace.py  # 2 doctests failed
sage -t sage/modular/hecke/ambient_module.py  # 1 doctest failed
sage -t sage/modular/abvar/finite_subgroup.py  # 2 doctests failed
sage -t sage/modular/modform/cuspidal_submodule.py  # 1 doctest failed
sage -t sage/modular/abvar/homology.py  # 2 doctests failed
sage -t sage/modular/abvar/abvar_newform.py  # 1 doctest failed
sage -t sage/modular/abvar/cuspidal_subgroup.py  # 2 doctests failed
sage -t sage/modular/hecke/degenmap.py  # 1 doctest failed
sage -t sage/modular/modsym/element.py  # 1 doctest failed
sage -t sage/modular/hecke/homspace.py  # 1 doctest failed
sage -t sage/modular/abvar/lseries.py  # 2 doctests failed
sage -t sage/modular/hecke/morphism.py  # 1 doctest failed

Rings:

sage -t sage/rings/morphism.pyx  # 7 doctests failed
sage -t sage/rings/quotient_ring.py  # 1 doctest failed
sage -t sage/rings/finite_rings/homset.py  # 3 doctests failed
sage -t sage/rings/number_field/morphism.py  # 4 doctests failed
sage -t sage/rings/homset.py  # 2 doctests failed

Modules

sage -t sage/modules/fg_pid/fgp_morphism.py  # 4 doctests failed
sage -t sage/modules/quotient_module.py  # 2 doctests failed
sage -t sage/modules/vector_space_homspace.py  # 1 doctest failed

Others:

sage -t sage/doctest/forker.py  # 1 doctest failed
sage -t sage/doctest/control.py  # 1 doctest failed
sage -t sage/structure/parent.pyx  # 1 doctest failed
sage -t sage/categories/hecke_modules.py  # 1 doctest failed
sage -t sage/homology/simplicial_complex_homset.py  # 1 doctest failed

Getting failures in sage/doctest seems amazing.

What to do?

[simon-king-jena]

comment:4

Just a crazy idea (brain storm):

We do not want WithEqualityById by default, because it makes no sense to have Homset be a unique parent, if domain and codomain are no unique parents.

However, if both domain and codomain are unique parents, it is a good idea to use WithEqualityById.

So, we could check whether both domain and codomain inherit from UniqueRepresentation. If they do, then they are unique parents, and then we could create a dynamic class out of WithEqualityById and the class of the homset, and overload the __class__ of the homset.

In that way, we would automatically have fast homset comparison and hash, for those parts of sage that use unique representation.

I am running tests with an according patch now...

[simon-king-jena]

comment:5

With what I described in my previous post, I get these errors.

sage -t sage/schemes/elliptic_curves/padic_lseries.py  # 1 doctest failed
sage -t sage/schemes/elliptic_curves/ell_point.py  # 8 doctests failed
sage -t sage/schemes/generic/homset.py  # 1 doctest failed
sage -t sage/schemes/elliptic_curves/ell_curve_isogeny.py  # 8 doctests failed
sage -t sage/schemes/elliptic_curves/ell_finite_field.py  # 1 doctest failed
sage -t sage/schemes/elliptic_curves/isogeny_class.py  # 1 doctest failed
sage -t sage/schemes/projective/projective_space.py  # 2 doctests failed
sage -t sage/schemes/affine/affine_space.py  # 1 doctest failed

Modular:

sage -t sage/modular/hecke/morphism.py  # 1 doctest failed
sage -t sage/modular/modsym/element.py  # 1 doctest failed
sage -t sage/modules/quotient_module.py  # 2 doctests failed
sage -t sage/modular/abvar/lseries.py  # 2 doctests failed
sage -t sage/modular/abvar/homology.py  # 2 doctests failed
sage -t sage/modular/abvar/abvar_newform.py  # 1 doctest failed
sage -t sage/modular/abvar/cuspidal_subgroup.py  # 2 doctests failed
sage -t sage/modular/abvar/finite_subgroup.py  # 2 doctests failed
sage -t sage/modular/modform/cuspidal_submodule.py  # 1 doctest failed
sage -t sage/modular/abvar/abvar.py  # 2 doctests failed
sage -t sage/modular/local_comp/local_comp.py  # 5 doctests failed
sage -t sage/modular/hecke/submodule.py  # 1 doctest failed
sage -t sage/modular/abvar/homspace.py  # 1 doctest failed
sage -t sage/modular/modsym/subspace.py  # 2 doctests failed
sage -t sage/modular/hecke/ambient_module.py  # 1 doctest failed
sage -t sage/modular/hecke/degenmap.py  # 1 doctest failed

and others:

sage -t sage/structure/parent.pyx  # 1 doctest failed
sage -t sage/rings/quotient_ring.py  # 1 doctest failed
sage -t sage/modules/fg_pid/fgp_morphism.py  # 3 doctests failed
sage -t sage/rings/morphism.pyx  # 3 doctests failed
sage -t sage/rings/homset.py  # 1 doctest failed

Are these less than before?

[simon-king-jena]

comment:6

Let's look at the errors more closely:

sage -t sage/modular/hecke/morphism.py
**********************************************************************
File "sage/modular/hecke/morphism.py", line 110, in sage.modular.hecke.morphism.HeckeModuleMorphism_matrix.__init__
Failed example:
    t == loads(dumps(t))
Exception raised:
    Traceback (most recent call last):
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 486, in _run
        self.execute(example, compiled, test.globs)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/doctest/forker.py", line 845, in execute
        exec compiled in globs
      File "<doctest sage.modular.hecke.morphism.HeckeModuleMorphism_matrix.__init__[2]>", line 1, in <module>
        t == loads(dumps(t))
      File "sage_object.pyx", line 1236, in sage.structure.sage_object.loads (build/cythonized/sage/structure/sage_object.c:11044)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/homset.py", line 291, in Hom
        cat_X = X.category()
      File "module.pyx", line 45, in sage.modules.module.Module_old.category (build/cythonized/sage/modules/module.c:1501)
      File "classcall_metaclass.pyx", line 330, in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1224)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/modules.py", line 108, in __classcall_private__
        result = super(Modules, cls).__classcall__(cls, base_ring)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/category.py", line 468, in __classcall__
        return super(Category, cls).__classcall__(cls, *args, **options)
      File "cachefunc.pyx", line 992, in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:5394)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/structure/unique_representation.py", line 447, in __classcall__
        instance = typecall(cls, *args, **options)
      File "classcall_metaclass.pyx", line 518, in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1586)
      File "/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/category_types.py", line 326, in __init__
        assert base in Rings(), "base must be a ring"
    AssertionError: <unprintable AssertionError object>
**********************************************************************
1 item had failures:
   1 of   4 in sage.modular.hecke.morphism.HeckeModuleMorphism_matrix.__init__
    [19 tests, 1 failure, 0.23 s]
----------------------------------------------------------------------
sage -t sage/modular/hecke/morphism.py  # 1 doctest failed
----------------------------------------------------------------------
Total time for all tests: 0.3 seconds
    cpu time: 0.2 seconds
    cumulative wall time: 0.2 seconds

and this actually looks like it is due to the __reduce__ method, not due to the WithEqualityById.

[simon-king-jena]

comment:7

Interesting! This

            sage: M = ModularSymbols(6)
            sage: t = M.Hom(M)(matrix(QQ,3,3,srange(9)), name="spam"); t
            Hecke module morphism spam defined by the matrix
            [0 1 2]
            [3 4 5]
            [6 7 8]
            Domain: Modular Symbols space of dimension 3 for Gamma_0(6) of weight ...
            Codomain: Modular Symbols space of dimension 3 for Gamma_0(6) of weight ...
            sage: t == loads(dumps(t))
            True

works on the command line, but fails in a doctest. :-/

[simon-king-jena]

comment:8

I think I've hit this one before when working on homsets. Perhaps I'll find my old solution somewhere.

[simon-king-jena]

comment:9

No, I did not find the solution.

The problem seems to be that the modular symbols space M is pickled the OLD python way, hence, its __dict__ is pickled. When M is unpickled, some homspace accessible from an attribute of M is unpickled. Codomain and domain of this homspace happen to be M --- and if the Hom function is called with an uninitialised version of M, then stuff fails.

Solution: Provide a "proper" pickling for modular symbols.
Problem: I don't understand the modular symbols code.

[simon-king-jena]

comment:10

If I recall correctly, people do explicitly not want to use a cache (such as: UniqueRepresentation) on modular symbols. They have some cache, but make a point of being able to disable it.

Here is a minimal example, that fails when using a proper __reduce__ method for homsets:

            sage: sage.modular.hecke.morphism.is_HeckeModuleMorphism_matrix(ModularSymbols(6).hecke_operator(7).matrix_form().hecke_module_morphism())
            True
            sage: M = ModularSymbols(6)
            sage: t = M.Hom(M)(matrix(QQ,3,3,srange(9)), name="spam"); t
            Hecke module morphism spam defined by the matrix
            [0 1 2]
            [3 4 5]
            [6 7 8]
            Domain: Modular Symbols space of dimension 3 for Gamma_0(6) of weight ...
            Codomain: Modular Symbols space of dimension 3 for Gamma_0(6) of weight ...
            sage: t == loads(dumps(t))
            True

The first line actually is important. With the first line, we get this error in the last line:

Traceback (most recent call last)
<ipython-input-11-a4f55210dece> in <module>()
----> 1 t == loads(dumps(t))

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/structure/sage_object.so in sage.structure.sage_object.loads (build/cythonized/sage/structure/sage_object.c:11044)()

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/homset.pyc in Hom(X, Y, category)
    289 
    290     # Determines the category
--> 291     cat_X = X.category()
    292     cat_Y = Y.category()
    293     if category is None:

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/modules/module.so in sage.modules.module.Module_old.category (build/cythonized/sage/modules/module.c:1501)()

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.ClasscallMetaclass.__call__ (build/cythonized/sage/misc/classcall_metaclass.c:1224)()                                                                                                                                                                                 

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/modules.pyc in __classcall_private__(cls, base_ring, dispatch)
    106             if base_ring in _Fields:
    107                 return VectorSpaces(base_ring, check=False)
--> 108         result = super(Modules, cls).__classcall__(cls, base_ring)
    109         result._reduction[2]['dispatch'] = False
    110         return result

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/category.pyc in __classcall__(cls, *args, **options)
    466         if isinstance(cls, DynamicMetaclass):
    467             cls = cls.__base__
--> 468         return super(Category, cls).__classcall__(cls, *args, **options)
    469 
    470     def __init__(self, s=None):

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/misc/cachefunc.so in sage.misc.cachefunc.WeakCachedFunction.__call__ (build/cythonized/sage/misc/cachefunc.c:5394)()

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/structure/unique_representation.pyc in __classcall__(cls, *args, **options)
    445 
    446         """
--> 447         instance = typecall(cls, *args, **options)
    448         assert isinstance( instance, cls )
    449         if instance.__class__.__reduce__ == CachedRepresentation.__reduce__:

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/misc/classcall_metaclass.so in sage.misc.classcall_metaclass.typecall (build/cythonized/sage/misc/classcall_metaclass.c:1586)()                                                                                                                                                                                                    

/home/simon/SAGE/prerelease/sage-5.10.rc1/local/lib/python2.7/site-packages/sage/categories/category_types.pyc in __init__(self, base, name)
    324     def __init__(self, base, name=None):
    325         from sage.categories.rings import Rings
--> 326         assert base in Rings(), "base must be a ring"
    327         Category_over_base.__init__(self, base, name)
    328 

<type 'str'>: (<type 'exceptions.AttributeError'>, AttributeError('ModularSymbolsAmbient_wt2_g0_with_category' object has no attribute '_HeckeModule_generic__level',))

Hooray, we have a reproducible failure.