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.

(with special thanks to Robert Bradshaw, Mike Hansen, Florent Hivert, William Stein, ... for design discussions).

Under development on combinat.sagemath.org/patches:

• #5891: categories-nt.patch: the category framework itself + updates to the sage library (import fixes, ... see below) + updates to combinatorial free modules (will be split before submission)

Related patches (will need to be applied after to recover 100% doctest pass):

• categories-combinat-nt.patch
• categories-numberfield_homset-nt.patch
• family_enumset-fh.patch
• enumset_unions-fh.patch
• categories-sf-nt.patch Symmetric functions
• categories-symmetric_group_algebra-nt.patch
• ncsf-nt.patch Non commutative Symmetric Functions
• #4326: root_systems-4326-nt.patch

Small technical patches the category patch depends on:

• #5449: cached_in_parent_method-5449-submitted.patch
• #5783: lazy_attributes-fixes-5783-final.patch
• #5120: unique_representation-5120-submitted.patch
• #5967: element_wrapper-5967-submitted.patch
• #5979: parent-element_constructor-fix-5979-submitted.patch
• #5985: cPickle-5985-import-submitted.patch, cPickle-5985-copy_reg_classes-submitted.patch
• #5986: cPickle-5986-nested-classes-submitted.patch
• #5991: dynamic_class-5991-submitted.patch
• #5598: 5598-coerce-declare.patch
• #5483: explain-pickle-v1.patch # probably can get rid of this dependency
• #6000: transitive_ideal-6000-submitted.patch

Current status:

• All test pass except for: sage -t "devel/sage/sage/geometry/lattice_polytope.py" (apparently caused by categories, though I don't see how) sage -t "devel/sage/sage/structure/sage_object.pyx" (unpickling of old stuff)

• Documentation: sage.categories? Category quickref card sage.categories.primer? Element/Parent/Category? primer (in writing) Category? Technical background on categories Semigroups().example()?? A template of semigroup See also the discussion on sage-devel in November 2009: ​http://groups.google.com/group/sage-devel/msg/d4065154e2e8cbd9

• Real life applications: see related patches, automatic monoids, ...

• Categories:
  • All the mathematical categories of Axiom and MuPAD (Courtesy of Teresa Gomez Diaz)
  • (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 example)
  • Cleanup:
    • Have unique representation by default (no need to inherit from Category_uniq)
    • Have construction / reduce by default

• Functorial constructions:
  • direct sum
  • tensor product
  • cartesian product (todo)
  • dual (in progress)
  • subquotient, subset, quotient (in progress)
  • isomorphism type (todo)

• Homomorphisms
  • Integrates with current sage morphisms
  • Adds morphisms for some categories
  • Some general infrastructure
  • Hom:
    • Simplification of the logic. Hopefuly completely compatible.
    • X._Hom_(Y, category) may now return NotImplemented?
    • failed attempt at using cached_function (to be pursued)
  • Systematic use of category = ... instead of cat = This may be backward incompatible.

• Generic test framework
  • Functional, final design clear, needs cleanup (2/3 hours)

• Reorganization of the Sage library to start using the category framework:
  • Combinatorial free modules
    • Have unique representation, use coercion, are more robust
    • Improved _repr_
    • Handle combinatorial classes that can't be sorted as indices
  • Groups:
    • AbelianGroup_class.init was missing a call to Groups.init
    • NAME CONFLICT: AbelianGroups? are *not* in AbelianGroups?() With the current conventions:
      • AbelianGroups? is about additive abelian groups
      • AbelianGroup? is about multiplicative abelian group
    • Support for Group.init(category = ...)
  • Fixed some import loops
  • 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

• Todo:
  • Naming cleanup:
    • Parent -> ParentMethods? (or _ParentMethods? or ?)
    • Element -> ElementMethods? + move them as a nested class of ParentMethods?
    • super_categories should be a method
    • zero, one should be methods
    • standardize the names: mult / product / multiplication / multiply?
    • check -> test
    • self.tester(keywords)
    • intrusive cat.tensor_category / ...
    • cat.example() -> /an_example/an_object/... ?
    • class.an_instance() ?
    • all_weakly_super_categories -> ?
    • move all examples in examples/
    • AbelianGroups?() versus CommutativeGroups?()

• Category graph picture

• Fixes:
  • Pickling: essentially works; polish the remaining
  • Integration in the Sage library: some tests are broken. Help welcome!
  • Pickling from old sage: technically feasible. Need help!
  • Inheritance from category for Cython classes: technically feasible. Need help!

• Hom is *not* a functorial construction, the design and user interface needs to be discussed

• Support for multivariate morphims, i.e. morphisms A x B -> C where the specializations A x b -> C are morphisms for a given category and a x B -> C are morphisms for a possibly different category

• Discussion:
  • Defining new inline operators, at least within the sage interpreter