wiki:CategoriesRoadMap

Categories for the working mathematics programmer (status and roadmap)

This page describes the status and roadmap for the category framework in Sage

With special thanks to Robert Bradshaw, Volker Braun, Nils Bruin, Peter Bruin, Teresa Gomez-Diaz, Darij Grinberg, Mike Hansen, Florent Hivert, Simon King, David Roe, Travis Scrimshaw, William Stein, and so many others ... for design discussions. Special kudos go to Simon King for all his work on the category infrastructure, in particular toward optimizations.

References

Design discussions:

Technical dependencies

Original ticket: #5891 (2009)

Typical use cases

  • Combinatorial Hopf algebras and generalizations of symmetric functions: #8899, #11929, #15150, #6889
  • #6812 Enumerate integer list up to the action of a Permutation Group
  • Semigroups (upcoming), #11111

Categorification tickets

TODO:

  • make a census of the parents that are not yet categorified
  • Document that the old hierarchy of abstract classes (Ring, Field, ...) is deprecated (except for some of the element classes whose presence is critical for the performance of arithmetic)
  • Actually start deprecating it. This requires all/most parents to be categorified.
  • Move a lot of methods like base_ring, list, ... from Parent, Element, SageObject? to the categories #????

Category hierarchy

The current hierarchy includes all the mathematical categories of Axiom and MuPAD (courtesy of Teresa Gomez Diaz)

TODO: add link to there + to the category graph

  • #15696 Implement an_instance for more categories, and extend category_sample. This could benefit from #15801.
  • 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 / ...)

Functorial constructions

Axioms

primer

    sage: Groups() & Sets().Finite()
	Category of finite groups
	sage: (CommutativeAdditiveGroups() & Monoids()).Distributive().Division()
	Category of division rings
	sage: _ & Sets().Finite()
	Category of finite fields

Morphisms, homsets

  • favor *_generators over gens(): #15381

use cached_function for handling the cache of Hom?

  • Hom is *not* a covariant functorial construction. This kind of 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

Handling of the category hierarchy

  • Support for subcategory methods: #12895
  • Refinement of the category of a parent: ..., #14471
  • Support for full subcategories: #16340
  • Improve the terminology for the hierarchy relation between categories: #16183
  • 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.

As a first step, #10963 implements the shortcuts & and | for join and meet.

Containment

  • Clarify in the doc and implement systematically the distinction between P in MyCategory() and P.is_...()

Support for modules and algebras

  • Mantra P in Algebras for testing if P is an algebra (over whatever ring): done; TODO: find the ticket that implemented that!
  • Categories over base ring categories: #15801
  • Make modules, algebras, polynomial algebra (free commutative algebra?), free algebra, exterior algebras, ... into covariant functorial constructions.
  • Clarification of the specifications of modules: #16247
    • 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??
  • #15043: Rename MagmaticAlgebras?? to Algebras and Algebras to AssociativeUnitalAlgebras??
  • The handling of multiplication (mul, ...) should be lifted to left / right modules
  • Rings() could be a subcategory of Algebras(ZZ) (or coincide with it). CommutativeAdditiveGroups?() could coincide with 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(), Modules(Rings())...) independent of any parent. This should probably be fixable later on by introducing more lazyness.
  • #11068 Basic implementation of one- and twosided ideals of non-commutative rings, and quotients by twosided ideals. Since there are rings that do not inherit from sage.rings.rings.Ring, it involves moving stuff to sage.categories.rings.Rings.ParentMethods (depends on #9138 and #11115)

TODO: reference the related discussions on sage-devel

Optimization of the infrastructre

Support for extension types

Works, up to some caveats (isinstance checks, ...). See also sage.categories.examples.semigroups_cython for further experiments.

  • #7921: Original approach via getattr
  • #20686: optimizing
  • Better would-be approach: treat extension types like the others

This would require to add support for multiple inheritance from abstract classes in Cython (Robert Bradshaw: there is no theoretical obstructions; just someone needs to take care of it).

  • #15718: init_extra for Cython classes

Documentation

  • Main index page: #7443 TODO: refactor it (maybe as in #16256); in particular emphasize the quickref
  • Primer: #5891, #10963
  • Make sure that ? and ?? on categories / examples / ... point to the right place e.g.: Semigroups??, Semigroups().example()?? Semigroups().parent_class?, Semigroups.element_class?
  • Improve the documentation of the implementation of axioms: #15643
  • Explain category: Autogenerated overview documentation of a category: #16363
  • Writing and linking to generic documentation???

Misc

  • Allow for super classes to also provide .Element?
  • Infrastructure for sharing code between the following features:
  • Calculating whether an object provably belongs to a category (is_* methods)
  • Testing whether an object is in the category it claims to belong to (_test_* methods)
  • Inheritance from existing parents
  • How to specify the category of a parent (overloading of method / argument to init) See #7921
  • #15303 Coercion discovery fails to be transitive
Last modified 18 months ago Last modified on 05/26/16 15:19:46

Attachments (1)

Download all attachments as: .zip