Version 40 (modified by 8 years ago) (diff)  ,

#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_method5449submitted.patch
 #5783: lazy_attributesfixes5783final.patch
 #5120: unique_representation5120submitted.patch
 #5967: element_wrapper5967submitted.patch
 #6000: transitive_ideal6000submitted.patch
 #5483: explainpicklev1.patch
 #6097: abstract_method6097nt.patch
 #6343: sage_objecttest6343nt.patch (with patch, needs review)
 #5979: parentelement_constructorfix5979submitted.patch
 #6809: abstract_methods_of_class
 #5598: 5598coercedeclare.patch (Robert should polish by 17/10; marked as depending on #5597?)
 #7251: Allow for Integer(3, parent = MyParent?)
Main patches #5891:
 http://combinat.sagemath.org/patches/file/tip/categoriesframeworknt.patch (reviewer: David Roe; review essentially complete up to some doctests)
 http://combinat.sagemath.org/patches/file/tip/categoriescategoriesnt.patch (reviewer: Florent Hivert, Javier, David Kohel, Anne Schilling, ...) See CategoriesCategoriesReview
 http://combinat.sagemath.org/patches/file/tip/categoriesfixsagelibnt.patch (reviewer: Robert) updates to the sage library (import fixes, ...)
 http://combinat.sagemath.org/patches/file/tip/categoriesenumeratedsetsnt.patch (author: Florent, positive review: Nicolas)
 http://combinat.sagemath.org/patches/file/tip/categoriescombinatnt.patch (positive review: Florent)
 http://combinat.sagemath.org/patches/file/tip/categoriesnumberfield_homsetnt.patch (reviewer: David)
Second batch of patches that will need to go in at once (in separate tickets). Up to final polishing, they are ready for inclusion.
 #7208: Refactorisation and categorification of families (author: Florent, positive review: Nicolas)
 http://combinat.sagemath.org/patches/file/tip/enumset_unionsfh.patch (reviewer: Nicolas)
 #6136: http://combinat.sagemath.org/patches/file/tip/categoriesfreemodule6136nt.patch (reviewer: Florent) Updates to combinatorial free modules
 #6137: http://combinat.sagemath.org/patches/file/tip/categoriessf6137nt.patch Categorification of symmetric functions (reviewer: Jason Bandlow)
 #6138: http://combinat.sagemath.org/patches/file/tip/categoriessymmetric_group_algebrant.patch (positive review: Florent)
 #4326: http://combinat.sagemath.org/patches/file/tip/root_systems4326nt.patch (positive review: Dan)
Over patches basically with positive review, and depending on the previous ones:
Later patches using categories:
 http://combinat.sagemath.org/patches/file/tip/categoriesncsfnt.patch Non commutative Symmetric Functions
 http://combinat.sagemath.org/patches/file/tip/automatic_monoidnt.patch
 #6812 Enumerate integer list up to the action of a Permutation Group
 #6889 Algebra of multivariate polynomials invariant under the action of a permutation group
Current status:
 All test pass
 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 sagedevel in November 2009: http://groups.google.com/group/sagedevel/msg/d4065154e2e8cbd9
 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:sagecategorygraph.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()
 Infrastructure:
 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 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. See Todo's in Sets.Parent.check? for possible improvements
 Lazy attributes:
Non essential, and essentially invisible from the user interface
Powerful tool for:
 Conditionally defined methods
 Enriched methods
 Categories and Cython: Proofofconcept for Cython classes to inherit code from categories See: sage.categories.examples.semigroups_cython
 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
 Support for Group.init(category = ...)
 AbelianGroups? was renamed to CommutativeAdditiveGroups? (idem for Semigroups, ...) (note: AbelianGroup? are about commutative multiplicative groups)
 NumberFields?: bug fix (categoriesnumberfield_homsetnt.patch / needs review): Hom(SomeNumberField?,SomeVectorSpace?) returned a numberfield homset
 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
 Added aliases one = one_element, zero = zero_element to start the transition (to be discussed)
 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 / ...
 Combinatorial free modules
 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
 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)
 Todo 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 / ...)
 CommutativeAdditiveSemigroups? (for doctesting add / sub / ...)
 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?
 abstract / isomorphism type / with_several_representations
 Choose, implement, and use systematically a mantra for testing if P is an algebra (over whatever ring):
 P in Algebras
 P in Algebras()
 Add more examples of parents (HELP!):
Ultimately, this should be for all categories,
Those are needed urgently:
 Long run discussions:
 init_add
 Writing and linking to generic documentation
 Standardize the functorial constructions, and streamline with variants (finite / finite dimensional / graded / abstract / ...)
 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.
 What's the right inheritance structure for homsets? Also, how should one specify that a category's homsets are enriched in another category? Via a method like "enriched_in()" on the category? By extra_super_categories() in a custom HomCategory??
Current status: if B is a subcategory of A, we want HomCategory?(B).element_class to inherit from HomCategory?(A), and a coercion Hom(P1, P2, B) > Hom(P1, P2, A). Such coercions cannot be handled well by the standard coercion mechanism, as Hom(P1, P2, Sets) will have *lot* of coercion sources. But Hom sets could have special rules (like tensor products will have).
 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
 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)
 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 (1)

sagecategorygraph.pdf (22.8 KB)  added by 8 years ago.
Sage's category graph
Download all attachments as: .zip