Archive Survey Sage Category System

Survey — Sage's category system

Carried over from the earlier enumeratio. Sage's Parent/category framework is still the closest external analogue to how a collection here declares a floor and gets the rest generated — now via compute-engine symbol declarations rather than SQL codegen. Sage's naming already informs current precedence (CE > Wolfram ≈ Sage > self-consistency); the maps/Hom-set transplant this survey argues for is now built as CombinatorialMap, see Speculative Statistics and Maps.

Ecosystem survey (see spikes.md → Ecosystem surveys → Sage category system). What to steal, what to avoid, mapped onto enumeratio's base_category / base_trait / base_map and the maps + random-sampling threads. Sources: the Sage categories/primer, enumerated_sets, finite_enumerated_sets, infinite_enumerated_sets, sets_with_grading, homset, and coercion reference pages (doc.sagemath.org), plus prior knowledge of sage.combinat.

TL;DR

Sage and enumeratio solve the same problem the same way: declare a little, generate the surface. In Sage a Parent declares its category and a few primitives (__iter__ / unrank / cardinality); the category framework grants the rest (random_element, list, rank, an_element, first/next) as default methods. In enumeratio a collection declares a row + a floor (fiber_elements + optional fiber_count / contains_in_fiber); the realizer grants the rest (elements, cardinality, unrank, contains, random_element [backlog #8]). The realizer is Sage's dynamic parent_class builder — done at build time in SQL codegen instead of at runtime in Python.

So the useful output of this survey is not "adopt the category framework" — it's three precise transplants:

• (a) maps: morphisms are first-class objects with explicit domain + codomain + invertibility (Hom-sets), and a separate canonical/automatic layer (coercions). That resolves the roadmap's "carrier-inherited vs first-class" question.
• (b) random-sampling + enumeration traits (backlog #8): random_element = draw a uniform rank, unrank it; the Finite/Infinite axiom split dictates the finite/unknown behaviour; a capability tier makes O(1)-unrank vs floor-scan explicit.
• (c) base_category/base_trait: keep the light implies/requires closure; do not build Sage's join/deduction engine or its runtime class generation — those are its known heaviness.

Part 1 — How Sage is built

1.1 Categories + axioms (the "what it IS" lattice)

A Category declares its super-categories (super_categories()); all_super_categories() walks the DAG. Mathematical knowledge is stated once — "groups are monoids" lives only in Groups.super_categories(), never duplicated.

Axioms refine a category into a subcategory. Cs().A() is the objects of Cs satisfying axiom A. Axioms are cardinality (Finite, Infinite, Enumerated), structural (Associative, Unital, Commutative, Inverse), or algebraic (FiniteDimensional, WithBasis, Graded). Two heavyweight mechanisms sit on top:

• Deduction: adding axioms selects a known named category. Magmas().Associative() is Semigroups(); Magmas().Associative().Unital().Inverse() is Groups(). Theorems are encoded — DivisionRings() & Sets().Finite() returns finite fields (Wedderburn).
• Join: categories combine by intersection (& / Category.join), merging axioms; axioms commute.

Adding Finite to EnumeratedSets selects FiniteEnumeratedSets, which swaps in different default methods (§1.3). This is the key move: an axiom changes which implementations you inherit. enumeratio's traits do not do this yet (§2.3).

1.2 Parent / Element, and the parent-in-a-category pattern

Every combinatorial family is a Parent; its members are Elements. A category carries nested ParentMethods / ElementMethods / MorphismMethods classes. At runtime Sage builds a dynamic class parent_class (and element_class) for each parent by collecting the ParentMethods from every super-category and composing them with the right MRO — via _make_named_class. Groups().element_class.__bases__ is literally (Monoids.element_class, Magmas.Unital.Inverse.element_class).

class Groups(Category):
    def super_categories(self): return [Monoids(), ...]
    class ParentMethods:   ...   # generic methods every group parent gets
    class ElementMethods:  ...   # generic methods every group element gets
    class MorphismMethods: ...   # generic methods every group morphism gets

A family becomes usable by: subclass Parent, pass category=FiniteEnumeratedSets() (or InfiniteEnumeratedSets()) to __init__, implement the primitives, done. Partitions(4) is a FiniteEnumeratedSets() parent that implements cardinality (closed form) + __iter__; Partitions() (all) is an InfiniteEnumeratedSets() parent. Categories also carry required_methods() and generic test suites (_test_associativity, …) that check the axioms hold.

1.3 Where the capabilities live — enumeration

This is the directly relevant part. Capabilities are default methods on the category, derived from a minimal primitive.

Category	Required primitive	Granted default methods (ParentMethods)	Strategy
EnumeratedSets	__iter__ (or first+next)	list, tuple, unrank(n), rank(e), first, next, random_element, an_element, some_elements (≤100), iterator_range, unrank_range	brute-force O(r) iteration
FiniteEnumeratedSets	+ Finite axiom	cardinality (_cardinality_from_iterator), random_element (_random_element_from_unrank: uniform, draw rank ∈ [0,cardinality), unrank), last, unrank_range	count by iterating; sample by unrank
InfiniteEnumeratedSets	+ Infinite axiom	cardinality → +Infinity; random_element → NotImplementedError("infinite set"); list/tuple → raise	refuse the finite-only ops

Two facts to carry into backlog #8:

• random_element on a finite set = draw a uniform integer in [0, cardinality) and unrank it. That is exactly the plan already written in backlog #8 — Sage confirms the recipe and the name (_random_element_from_unrank).
• Infinite ⇒ refuse. InfiniteEnumeratedSets.random_element raises rather than guessing. That answers the open "infinite / unknown-count behaviour" question directly: refuse by default (a bounded-prefix sample is a deliberate opt-in, not the default).

SetsWithGrading is Sage's base_grade: a set S = ⊔_{i∈I} S_i with grading_set() (the index I), grading(e), graded_component(grade) (= a fiber), and generating_series() (= the counting q-series — ties straight to the dimensions-&-measures "distribution" thread). The unbounded whole is assembled as DisjointUnionEnumeratedSets(Family(index, n → component)) — precisely enumeratio's unbounded collection = the disjoint union of fiber_elements(fiber) over the grade chain. Sage's contract "if the graded set is enumerated, each graded component is enumerated" is enumeratio's "the floor enumerates one fiber; the realizer flat-maps fibers."

1.4 Hom-sets, Map / Morphism

A morphism is a first-class object with an explicit domain and codomain, and it is an element of a Parent — the homset Hom(X, Y, category). Homset subclasses Set_generic; domain(), codomain(), identity()/one() (endos), natural_map(), reversed(). End(X) is the endomorphism homset. Class split: sage.categories.map.Map (base), sage.categories.morphism.Morphism (category-aware), SetMorphism (wraps a Python function), FormalCompositeMap (composition). Categories customize morphism behaviour via MorphismMethods and homset construction via _Hom_.

The lesson for enumeratio's maps thread: domain + codomain + invertibility + composition are the primitives of a map, and a map is a relation between two named parents, not a property smeared over a carrier.

1.5 Coercion (the automatic/canonical layer)

Sage separates two things enumeratio currently conflates in base_map:

• Coercion — a canonical, total, automatic morphism, "obvious and natural," discovered by the system. Registered via _coerce_map_from_(S) / _populate_coercion_lists_; found by a coercion graph + pushout over construction functors; get_coercion_model().canonical_coercion(a, b) finds a common parent for a + b. has_coerce_map_from, coerce_map_from.
• Conversion — an explicit, may-fail, choice-bearing map, R(x) via _element_constructor_.

Coercion is what makes ZZ(2) + QQ(1/2) just work. It is powerful and it is Sage's most notorious source of subtle bugs (surprising common-parents, discovery loops). The transplant is the distinction, not the discovery engine (§3, avoid).

Part 2 — Mapping onto enumeratio

2.1 Vocabulary correspondence

Sage	enumeratio	Notes
Parent (a family)	a collection (base_collection row)	one carrier per collection ≈ one element_class per parent
Element	a carrier value / <coll>_element (located)
category's ParentMethods (default methods)	the realizer's emitted generic surface	granted by membership vs granted by realize
dynamic parent_class (_make_named_class)	base_realize(coll) codegen	runtime class-build vs build-time SQL codegen
required primitive (__iter__/unrank/cardinality)	the floor (fiber_elements req; fiber_count, contains_in_fiber opt)	"the math that can't be eliminated"
axiom (Finite, Infinite)	a prescriptive trait (does not exist yet)	Sage's axioms swap the method table; our traits only classify
SetsWithGrading (graded_component, grading_set)	base_grade chain, fibers(handle), a fiber	direct hit
generating_series()	fiber-count q-series / distribution	dimensions-&-measures thread
DisjointUnionEnumeratedSets(Family(…))	an unbounded collection = ⊔ fibers	direct hit
Hom(X,Y) element / Morphism (domain+codomain)	a first-class base_map (proposed)	§2.2
coercion (canonical, auto, by carrier)	base_map_resolved inherited by carrier	§2.2
WithRealizations + change-of-basis coercion	order-iso sibling collections + borrowed ranking	lehmer_codes ↔ permutations
EnumeratedSets.random_element via unrank	random_element(handle) (backlog #8)	§2.3
base_trait.implies closure	(no Sage single name) axiom implication	our closure is the light version of Sage's deduction
base_category.requires → traits	a category entailing its axioms	already the right shape

2.2 The maps / bijection layer (roadmap thread)

The roadmap asks: is a bijection carrier-inherited (like conjugate, sprayed onto every collection with that carrier by base_map_resolved) or a first-class relation between two named collections? Sage answers: both, and they are different kinds.

• Carrier-level canonical ops = coercions. perm_inverse, perm_reverse, partition_conjugate are endomorphisms of a carrier — total, canonical, "obvious." Keeping them inherited-by-carrier (base_map_resolved) is exactly Sage's coercion posture: automatic, defined on the whole domain. Keep this.
• Named bijections between two collections = Hom elements. Euler distinct↔odd, RSK, crossing↔nesting are relations between named endpoints, often bijective only on a restriction, and the endpoints may not even share a carrier (distinct_partitions has its own carrier; odd_partitions is a base_restrict of integer_partitions). These want the homset treatment: explicit domain + codomain, an invertible flag + inverse_fn, and composition.

Concrete: base_map already has mapping_fn, codomain, findstat. Add, for the first-class kind: an explicit domain (collection, not carrier), invertible boolean + optional inverse_fn, and treat these as elements of a Hom(domain, codomain) conceptually. Then base_map_resolved's carrier-inheritance stays only for the coercion-like carrier ops; it should not spray a named bijection onto every collection sharing the codomain carrier (the roadmap's exact complaint). Composition of maps (Sage's FormalCompositeMap) gives crossing↔nesting-via-RSK-style chains for free, and the --through permutohedron-motion composition already in maps.sql is the same idea. The lehmer↔permutation "borrow" is Sage's WithRealizations + change-of-basis coercion: two realizations of one object, connected by a canonical iso — model the borrow as an invertible map flagged canonical, not as a duplicated floor.

2.3 Random-sampling + enumeration-capability traits (backlog #8)

Steal the Sage shape wholesale, because backlog #8 already independently arrived at it:

1. random_element(handle) / random_element(fiber) = unrank(handle, random_int(0, cardinality-1)), uniform, iff the count is finite + known. This is FiniteEnumeratedSets._random_element_from_unrank.

2. Finite/unknown behaviour = the Finite vs Infinite axiom split: unbounded (or unknown count) ⇒ refuse by default (InfiniteEnumeratedSets raises NotImplementedError("infinite set")); a bounded-prefix sample is an opt-in mode, never the default. (For a per-fiber sample of an unbounded collection, a fiber is finite even when the collection isn't — sample within a bound-picked fiber; that's the natural escape hatch, and it falls straight out of the grade chain.)

3. The capability taxonomy backlog #8 wants = Sage's axiom + implementation-cost distinction made explicit as data. Sage knows Finite/Infinite from the axiom; it knows fast-unrank vs brute-force only implicitly (whether the parent overrode unrank). enumeratio can do better by recording it. Add a prescriptive enumeration-capability trait per collection:

   field	meaning	source
   bounded	finite total / unbounded	NOT base_collection.unbounded
   counts_closed_form	O(1)-ish cardinality vs count-the-floor	fiber_count engine present
   unrank_efficient	better-than-scan random access vs floor-scan	declared (or derived from a borrowed sibling)
   size_hint	asymptotic growth / size estimate	per-collection hint (ties the pagination-batch thread)

   The sampler — and any caller — dispatches on this: an O(1)-unrank collection samples cheaply; a scan-only one is flagged so the cost is a choice, never a silent O(n) surprise (§3, Sage's trap). This is the "support-function taxonomy" (which capability each ranking exposes: next/prev/unrank ⇒ random access) named in backlog #8.

The trait-model insight: enumeratio's current traits (finite, graded, has_stats, …) are derived — observations computed from the registries, closed over implies. Sage's axioms are prescriptive — they change which engine runs. Backlog #8 needs the prescriptive kind. So name the split: keep the derived traits for classification/filtering (the explorer chips), and add a capability layer the realizer/sampler actually dispatches on. base_category.requires already models "a category entails these axioms"; the enumeration-capability trait is the first axiom that does work rather than just labels.

2.4 base_category / base_trait hierarchy

Current state is right-shaped and deliberately flat: base_trait(id, description, implies) with a recursive implies closure; base_category(id, description, parents, requires) with requires naming the traits (axioms) a category entails; base_collection_trait derives assignments and closes them — "the way a Sage object's category memberships follow from its axioms" (already the comment in traits.sql). This is the light version of Sage's design and it is the correct amount.

What Sage has that we should adopt later, as data: the algebraic "what it IS" lattice — Posets, Lattices, Groups, Monoids — with base_map as the morphisms of those categories, and parents giving the super-category DAG. Rows + closure, exactly like now; no engine. What we should not adopt: everything in §3.

Part 3 — What to avoid (Sage's known heaviness)

Sage's primer itself says the machinery "may feel like overdesigning." For a SQL-in-PGlite catalog it is — these are the parts to consciously not build:

• Runtime dynamic class generation (_make_named_class, per-parent parent_class/element_class MRO composition). It is slow to import, hard to debug, and reflection-heavy. enumeratio's build-time SQL codegen (base_realize) is the same idea done statically — the emitted DDL is inspectable and there is no runtime metaclass magic. Keep it; do not chase Sage's runtime flexibility.
• The axiom join / deduction engine (Category.join, &, "adding axioms selects a named category," category pushout). It is combinatorially subtle and a perennial maintenance sink. enumeratio's transitive implies/requires closure in SQL is enough; do not build deduction (do not make graded & finite resolve to a named category).
• Silent brute-force defaults. FiniteEnumeratedSets.cardinality iterates every element; random_element computes that cardinality then unranks by iteration — an innocent call can be O(n) or worse with no warning. This is Sage's most-felt performance trap. enumeratio's fix is already latent: make the cost explicit via the capability trait (§2.3), so scan-only vs O(1) is visible before the call. Never ship a random_element/cardinality whose cost is invisible.
• Coercion's automatic discovery graph + pushout. Powerful, and a well-known bug farm (surprising common parents, discovery recursion). enumeratio's borrows are manifest in the SQL (explicit, not discovered) — keep that. Adopt the coercion-vs-conversion distinction (§2.2) as a modeling idea; do not build auto-discovery.
• Legacy churn. Sage still carries the deprecated CombinatorialClass alongside Parent-in-a-category. A clean single model (collection + floor + realizer) with no parallel legacy path is a feature — protect it.

Recommendations (actionable)

1. Maps: split base_map semantics into carrier-inherited canonical ops (coercion posture — keep base_map_resolved by carrier, for endomorphisms only) and first-class named maps (Hom elements — explicit domain collection, codomain, invertible + inverse_fn, composable). Stop base_map_resolved from spraying named bijections across a shared codomain carrier. Unblocks Euler / crossing↔nesting / RSK-as-a-map (backlog #11).
2. Random sampling (backlog #8): realize random_element(handle)/(fiber) = draw uniform rank + unrank; refuse when unbounded/unknown (Infinite-axiom posture), bounded-prefix sample only as opt-in, per-fiber sampling as the escape hatch. Back it with a prescriptive enumeration-capability trait (bounded, counts_closed_form, unrank_efficient, size_hint) the sampler dispatches on — making Sage's silent-O(n) trap an explicit, visible choice.
3. Traits: name the derived vs prescriptive split. Keep derived traits for classification; add the capability layer as the first prescriptive axiom that changes engine dispatch. Keep implies/requires closure; do not build join/deduction.
4. Grading: adopt SetsWithGrading vocabulary confidence — graded_component = fiber, grading_set = the grade-axis index, generating_series = the fiber-count distribution. It confirms the base_grade + dimensions-&-measures model is on the canonical path; the disjoint-union-of-finite-components framing is the right mental model for unbounded collections.
5. Categories: hold the flat mathematical/internal split now; grow the algebraic "what it IS" lattice (Poset/Lattice/Group…) later as base_category rows with base_map morphisms and parents DAG — data + closure, never a class-generation or deduction engine.