wiki:CategoriesRoadMap
Last modified 2 years ago

#5891: Categories for the working mathematics programmer (status and roadmap)

This page describes the status and roadmap for the category patches.

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, David Roe, William Stein, ... for design discussions).

The latest version of all the patches are available from:  http://combinat.sagemath.org/patches/file/ -> browse Please review them from there!

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
  • #6000: transitive_ideal-6000-submitted.patch
  • #5483: explain-pickle-v1.patch
  • #6097: abstract_method-6097-nt.patch
  • #6343: sage_object-test-6343-nt.patch (with patch, needs review)
  • #5979: parent-element_constructor-fix-5979-submitted.patch
  • #6809: abstract_methods_of_class
  • #5985: customized class pickling
  • #5986: pickling of nested classes
  • #5991: dynamic_class
  • #5598: 5598-coerce-declare.patch
  • #7251: Allow for Integer(3, parent = MyParent?)
  • #7259: Revert Sets().category() from Sets() to Objects()
  • #7420: Fix uncaught infinite loop in coercion discovery (positive review)
  • #7421: Weaker precondition for registering a new coercion (positive review)

Main patches: #5891

Second batch of patches that will need to go in at once:

  • #7403: Adds FiniteEnumeratedSet? (author: Florent, positive review: Nicolas)
  • #7208: Refactorisation and categorification of families (author: Florent, positive review: Nicolas)
  • #7395: The enumerated set of non negative integers (author: Florent, positive review: Nicolas)
  • #7396: Disjoint unions of enumerated sets (author: Florent, positive review: Nicolas)
  • #7397: Updated Primes to the category system (author: Florent, positive review: Nicolas)
  • #6136: (Combinatorial) Free modules: cleanup, abstraction into categories, and functorial constructions (positive review: Florent) Updates to combinatorial free modules
  • #6137:  http://combinat.sagemath.org/patches/file/tip/categories-sf-6137-nt.patch Categorification of symmetric functions (positive review: Jason Bandlow)
  • #6138: SymmetricGroupAlgebra?: updates w.r.t. categories and free modules (positive review: Florent)
  • #4326: Root systems improvements (positive review: Dan)
  • #7443: List all categories in the reference manual (positive review: Nicolas)
  • #7478: TestSuite? improvements (?)
  • #3663 (affine crystals) (positive review: Dan Bump)
  • #5794 branching rules (positive review: Brant Jones)

Later patches related with or using categories:

Current status:

  • All test pass on sage-4.2.1-alpha0
  • 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 Download
    • (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.
  • Functorial constructions:
    • cartesian product, tensor_product
    • subquotient, subset, quotient (in progress)
    • dual (very preliminary)
    • isomorphism type / abstract (very preliminary)
  • Homomorphisms:
    • Integrates with current sage morphisms
    • Adds morphisms for some categories
    • Some general infrastructure
    • Hom:
      • Simplification of the logic. Hopefully completely compatible.
      • X._Hom_(Y, category) may now raise TypeError? if it does not know how to handle the case
      • failed attempt at using cached_function (to be pursued)
    • Systematic use of category = ... instead of cat = This may be backward incompatible.
  • Lazy attributes: Non essential, and essentially invisible from the user interface Powerful tool for:
    • Conditionally defined methods
    • Enriched methods
  • Categories for extension types: works up to some caveats (see #5921) See also sage.categories.examples.semigroups_cython for further experiments
  • Reorganization of the Sage library to start using the category framework:
  • 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)
  • Roadmap for after:
    • Add more examples of parents (HELP!): Ultimately, this should be for all categories. Those are needed urgently:
      • Modules (for doctests for mul / rmul / ...)
      • Algebras (for doctests for mul / rmul / ...)
    • Allow for super classes to also provide .Element
    • Make sure that ? and ?? on categories / examples / ... point to the right place e.g.: Semigroups??, Semigroups().example()?? Semigroups().parent_class?, Semigroups.element_class?
    • Add ObjectMethods? for category objects that are not parents?
    • Choose, implement, and use systematically a mantra for testing if P is an algebra (over whatever ring):
      • P in Algebras
      • P in Algebras()
    • Cleanup Algebras and modules (see discussion on sage-devel)
      • Modules(R) should be restricted to R commutative, with r * m = m * r
      • Algebras(R) should be a subcategory of Bimodules, not Modules
      • What about ModulesWithBasis??
      • The handling of multiplication (mul, ...) should be lifted to left / right modules
      • Modules(field) should return VectorSpaces?(field) (handled by #8881)
    • Make all parents inherit from categories, and use TestSuite?(...).run() (See #7921, #8001, #8044, #8562, #8576, #8911, #9138...)
    • #8881: Refactored framework for functorial constructions, with support for: TensorProducts?, CartesianProducts?, Algebras, Quotients, Subquotients, Subobjects, IsomorphiscImages?, Dual; upcoming: WithRealizations? (#7980), CharacterRings?, ...
    • Parents with multiple realizations (#7980; depends on #8881)
  • Long run discussions:
    • init_add
    • Writing and linking to generic documentation
  • Add support for automatic join for full subcategories (finite / finite dimensional / graded / ...). E.g. join(FiniteSets?() and Groups()) should be FiniteGroups?().
  • join and meet are misnomers: since we speak of subcategories, then the implicit order is A <= B if A is a subcategory of B. So join and meet should be exchanged. Maybe it's too late for backward compatibility. Then maybe we could use "intersect" instead of join. For meet, there does not seem to be an obvious name, but it's also very seldom used at the user interface, so the backward compatibility issue is not that relevant.
  • Hom is *not* a functorial construction. This works for now, but the design and user interface needs to be discussed for the long run implementation. See #10668.
  • Support for multivariate morphisms, i.e. morphisms (A x B) -> C where the specializations (A x b) -> C and and (a x B) -> C are morphisms for possibly different categories (see also #8900)
  • Defining new inline operators, at least within the sage interpreter
  • Convention for the order in super_categories (see primer)
  • Cythonification, and merging of the code with sage.structure.element.*Element?
  • Inheritance from existing parents
  • How to specify the category of a parent (overloading of method / argument to init) See #7921
  • Rings() could be a subcategory of Algebras(ZZ) (or coincide with it?), Groups() of Modules(ZZ). In a similar vein, a field F could be in the category Modules(F). However, this can cause some trouble by introducing cross dependencies: ZZ involves constructing the category Rings() which uses Modules(ZZ) which itself uses ZZ. To avoid this, the current setup makes the basic categories (Groups(), Rings(), ...) independent of any parent. This should probably be fixable later on by introducing more lazyness.

Attachments