Categories for the working mathematics programmer

[nthiery]

This (series of) patch(es) extends the Sage category framework as a
design pattern for organizing generic code.

Latest version of the patches:

• categories-framework-nt.patch (reviewer: David Roe; review essentially complete up to some doctests)
• categories-categories-nt.patch (reviewer: Florent Hivert, Javier, David Kohel, Anne Schilling, ...) See CategoriesCategoriesReview
• categories-fixsagelib-nt.patch (positive review: Robert Bradshaw)
  updates to the sage library (import fixes, ...)
• categories-fix-combinat-nt.patch (positive review: Florent)
• categories-numberfield_homset-nt.patch (reviewer: William)
• categories-unpickle_backward_compatibility_aliases-nt.patch (positive review: Florent)

Status and roadmap: http://trac.sagemath.org/sage_trac/wiki/CategoriesRoadMap

Some of the things done in this ticket:

• Categories:

  • Infrastructure:
    • sage.categories.category (500 lines of code)
    • sage.structure.parent (100 lines of code)
    • class manipulation: (25 lines of code)
  • All the mathematical categories of Axiom and MuPAD (Courtesy of Teresa Gomez Diaz)
    (except *WithSeveralBases which are not needed anymore; see .abstract_category())
    See the category graph: attachment: sage-category-graph.pdf
  • (Infinite/Finite)EnumeratedSets (with example) (Courtesy of Florent Hivert)
  • Semigroups (with example, basic methods, subquotients)
  • FiniteSemigroups (with example, cayley graphs, basic representation theory, ...)
  • ModulesWithBasis (with example, morphisms)
  • HopfAlgebras & friends (with a couple examples)
  • Cleanup:
    • Have unique representation by default (no need to inherit from Category_uniq)
    • Have construction / reduce by default
    • Can systematically use the idiom P in Rings()
  • Lattice structure (join, meet); meet needs cleanup; join and meet
    should be swapped.

• Reorganization of the Sage library to start using the category framework:

  • Groups:
    • AbelianGroup_class.init was missing a call to Groups.init
    • Support for Group.init(category = ...)
    • AbelianGroups was renamed to CommutativeAdditiveGroups (idem for Semigroups, ...)
      (note: AbelianGroup are about commutative multiplicative groups)
  • NumberFields: bug fix (categories-numberfield_homset-nt.patch):
    Hom(SomeNumberField,SomeVectorSpace) returned a numberfield homset
  • Fixed some import loops
  • Square MatrixSpace in Algebras(...)
  • Added temporary list() methods to:
    • FreeModule_generic
    • MatrixSpace_generic
    • Set_object_enumerated
    • ParentWithAdditiveAbelianGens
    • ParentWithMultiplicativeAbelianGens
      They should eventually be inherited from the EnumeratedSets() category
  • Added sage.sets.finite_enumerated_set
  • Naming conventions and cleanup:

    • parent.product(x,y) parent.product parent.product_on_basis
      (was: multiply, _multiply, multiply_basis, _multiply_basis)

    • parent.summation(x,y) parent.summation # risk of confusion with infinite summation / ...

    • parent.sum ([x,y,z,y])

    • parent.prod([x,y,z,y])

    • parent.coproduct, parent.coproduct_on_basis, parent.coproduct_on_generators

    • parent.antipode, parent.antipode_on_basis, parent.antipode_on_generators

    • cat.example() cat.counter_example()

    • A.one() A.zero() a.is_one() a.is_zero() A(1) A(0) when it makes sense
      A.one_element() A.zero_element() deprecated in the doc; fully deprecated later
      Transitional aliases one = one_element, zero = zero_element

    • Use class.an_instance() whenever meaningful

    • parent.an_element() parent.some_elements(); possibly parent.example() parent.counterexample()

    • all_weakly_super_categories -> all_super_categories(proper=False)

CC: @sagetrac-sage-combinat @roed314 @saliola

Component: categories

Keywords: categories parents

Author: Nicolas M. Thiéry, Teresa Gomez-Diaz

Reviewer: Robert Bradshaw, Craig Citro, Florent Hivert, David Kohel, David Roe, Anne Schilling, William Stein, Javier Vengoroso

Merged: sage-4.3.alpha0

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

[robertwb]

comment:8

Where is categories-nt.patch itself?

[nthiery]

comment:11

Replying to @robertwb:

Where is categories-nt.patch itself?

On the sage-combinat patch server. It changes too often to keep it updated on trac.
I highlighted the link on top of the description (and improved the ReSTing)

[nthiery]

Attachment: categories-framework-nt.patch.gz

[nthiery]

Attachment: categories-categories-nt.patch.gz

Attachment: categories-fixsagelib-nt.patch.gz

[nthiery]

Attachment: categories-enumeratedsets-nt.patch.gz

[nthiery]

Attachment: categories-combinat-nt.patch.gz

[nthiery]

Attachment: categories-numberfield_homset-nt.patch.gz

[nthiery]

comment:15

There are the patches. They are file-orthogonal, so they should apply in any order.

[nthiery]

comment:16

Note: to get the latest version, please use the patch server.

[williamstein]

comment:17

NOTES:

(1) Post the latest version here -- I don't want to mess with the patch server.

(2) It says "Experts: please redefine this properly and/or put CC/RR/... in NumberFields()". I number field is by definition a finite extension of QQ, but CC and RR are infinite extensions of QQ. So we can't put them in that category. Having a function is_NumberFieldHomsetCodomain does seem like a good workaround for now.

(3) The function is_NumberFieldHomsetCodomain in the patch posted here doesn't have any documentation or doctests. Please add them.

(4) I would change these two lines:

        143	        if is_Field(codomain): 
 	144	            return True 

to the single line

        143	        return is_Field(codomain)

which should be functionally the same, and clearer to read.

(5) in a similar spirit, I would change

        145	    except: 
 	146	        pass     
 	147	    return False 

to just

        145	    except: 
 	146	        return False

which is again clearer and equivalent.

(6) I'm puzzled by this in your number_field_rel.py patch:

	543	            return NotImplemented 

What is NotImplemented? It's not defined in the number_field_rel.py file in sage-4.2.

[nthiery]

Reviewer: Robert Bradshaw, Florent Hivert, David Kohel, David Roe, Anne Schilling, Javier Vengoroso

[nthiery]

comment:19

Replying to @williamstein:

NOTES:

(1) Post the latest version here -- I don't want to mess with the patch server.

I just added direct links in the description. I will post the patches shortly when they will be final.

(2) It says "Experts: please redefine this properly and/or put CC/RR/... in NumberFields()". I number field is by definition a finite extension of QQ, but CC and RR are infinite extensions of QQ. So we can't put them in that category. Having a function is_NumberFieldHomsetCodomain does seem like a good workaround for now.

Ok.

(3) The function is_NumberFieldHomsetCodomain in the patch posted here doesn't have any documentation or doctests. Please add them.

Oops. Will do.

(4) (5) (6)

Yes better. Will do.

(6) I'm puzzled by this in your number_field_rel.py patch:

	543	            return NotImplemented 

What is NotImplemented? It's not defined in the number_field_rel.py file in sage-4.2.

It's a builtin python object. Anyway, the function now raises a TypeError, per the latest _Hom_ protocol.

[nthiery]

Author: Nicolas M. Thiéry

[mwhansen]

comment:26

Merged the patches from changeset e70487186111. They'll be posted on here in a bit.

[mwhansen]

Merged: sage-4.3.alpha0

[nthiery]

Changed author from Nicolas M. Thiéry to Nicolas M. Thiéry, Teresa Gomez-Diaz

[jdemeyer]

comment:31

Does anybody here remember the reason for the is_extension_type() condition in

    def __make_element_class__(self, cls, name = None, inherit = None):
        """
        A utility to construct classes for the elements of this
        parent, with appropriate inheritance from the element class of
        the category (only for pure python types so far).
        """
        if name is None:
            name = "%s_with_category"%cls.__name__
        # By default, don't fiddle with extension types yet; inheritance from
        # categories will probably be achieved in a different way
        if inherit is None:
            inherit = not is_extension_type(cls)
        if inherit:
            return dynamic_class(name, (cls, self.category().element_class))
        else:
            return cls

I just tried replacing inherit = not is_extension_type(cls) by inherit = True and there is almost nothing which breaks.