Elements that are themselves a Parent

[mkoeppe]

(split out from a discussion in #33713)

Sometimes an Element should be simultaneously a Parent. For example I would like to have a semigroup (parent) of polyhedra (element), but each polyhedron is also a parent whose element class is a point. There are 3 separate categories involved:

• Semigroups
• Join of Topological Spaces, Elements of semigroups
• Elements of Topological Spaces

We also clarify the mathematical meaning of Parent.

CC: @tscrim @DavidAyotte

Component: categories

Issue created by migration from https://trac.sagemath.org/ticket/34534

[mkoeppe]

Description changed:

--- 
+++ 
@@ -7,3 +7,8 @@
 - Join of Topological Spaces, Elements of semigroups 
 - Elements of Topological Spaces

+We also clarify the underdocumented mathematical meaning of `Parent`, which is currently only explained by didactical oversimplifications.
+
+Following the central role of morphisms in modern mathematics, we clarify that definitionally, a `Parent` is that which is suitable to be a domain or codomain of a `Morphism`.
+
+

[tscrim]

Description changed:

--- 
+++ 
@@ -7,8 +7,5 @@
 - Join of Topological Spaces, Elements of semigroups 
 - Elements of Topological Spaces

-We also clarify the underdocumented mathematical meaning of `Parent`, which is currently only explained by didactical oversimplifications.
+We also clarify the mathematical meaning of `Parent`.

-Following the central role of morphisms in modern mathematics, we clarify that definitionally, a `Parent` is that which is suitable to be a domain or codomain of a `Morphism`.
-
-

[tscrim]

comment:3

I changed the ticket description to have more neutral languange.

Matthias's definition based on the claim that a Parent has overly simplified its description:

Following the central role of morphisms in modern mathematics, we clarify that definitionally, a Parent is that which is suitable to be a domain or codomain of a Morphism.

The current definition in the docstring:

Parents are the Sage/mathematical analogues of container objects in computer science.

My supporting evidence for this is within Parent there are many things that support the fact that it should be treated as set-like:

• This doc:

      .. TODO::
  
          Eventually, category should be
          :class:`~sage.categories.sets_cat.Sets` by default.

• There are lots of specialized methods and attributes within the class specifically designed for dealing with elements. Including a documented invariant involving the elements.
• _test_category explicitly calls _test_an_element
• The default __call__ returns a NotImplementedError if there is no _element_constructor.
• There is a default __contains__ method.
• It implements the framework for actions on its elements.

Thus, I propose that CategoryObject becomes the new base class for Parent and Element, moving methods down to Parent that do not make sense for general objects in an abstract category.

• Element already has a dedicated category, and CategoryObject's doc says that it is a base class for all objects in a category.
• This would allow for Map to also be defined between elements by replacing Parent _codomain with CategoryObject _codomain and should not affect any time-critical sections of code. (We can already create homsets between elements.)
• It allows for more abstract small categories without reimplementing Parent as a subclass of Category (which is mostly designed for code abstraction). (This is also wanted in #33713.)
• Furthermore, it reinforces the difference between SageObject and a general object in a category.
• It brings the implementation of Element and Parent closer together, which will make it easier for the eventual goal of this ticket.
• It is not an invasive change while separating the concern of a Parent having elements, Category to avoid the combinatorial explosion of classes, and a general object in a category.

One potential thing to discuss (that does not need to be resolved here): Should the result of Element.category() in a small category be the Parent? This would be natural since we want to think of the Parent as also being a (mathematical) category. However, this could have different behavior (and lead to implementation issues with, e.g., Hom) and make it impossible for the category framework to work correctly with something that is both a Parent and Element.

[mkoeppe]

comment:4

Replying to Travis Scrimshaw:

The current definition in the docstring:

Parents are the Sage/mathematical analogues of container objects in computer science.

... which clearly does not attempt to give a definition.

[mkoeppe]

comment:5

Replying to Travis Scrimshaw:

within Parent there are many things that support the fact that it should be treated as set-like:

"set-like" needs clarification. This is a term that is used in Python but it has no clear mathematical meaning.

• This doc:

      .. TODO::
  
          Eventually, category should be
          :class:`~sage.categories.sets_cat.Sets` by default.

• There are lots of specialized methods and attributes within the class specifically designed for dealing with elements. Including a documented invariant involving the elements.
• _test_category explicitly calls _test_an_element
• The default __call__ returns a NotImplementedError if there is no _element_constructor.
• There is a default __contains__ method.
• It implements the framework for actions on its elements.

This looks cherry-picked to me. For example, Parent has:

    # This probably should go into Sets().Parent
    @lazy_attribute
    def element_class(self):

So clearly someone thought that Parent should be suitable for something that is not in Sets.

[tscrim]

comment:6

Some other points:

• Parent is explicitly calling _set_element_constructor in its __init__
• The element-based methods as part of its pickling.
• Many of the methods are related to coercion/conversion that operate on elements of the Parent (we can debate whether or not it should do this (and it maybe shouldn’t), but right now its implementation does depend on this because it uses an_element; see also Parent.coerce), and there are many default methods that make it act set-like (e.e.g, __contains__ and an_element).
• The “how to build a new parent” thematic tutorials, essentially say “copy what these other parents do,” which all have Element.

This should cover at least half of the methods of Parent, if not much more.

Even allowing your argument that it is cherry-picked, that is saying that we should have a subclass for this. Now I agree with your implicit argument that it should be sufficient to inherit from Sets(), which is how you can separate things that should go into Sets() and having a default category of Sets() that isn’t a Sets().or_subcategory(category) (which I would argue is what was intended by that comment since that puts additional mathematical data to the programming object). However, there are many time critical parts of Sage that rely on this being very fast, so we need an explicit Cython subclass rather than a dynamically created Python subclass through the category framework.

[tscrim]

comment:7

Wrong button…

[mkoeppe]

comment:8

Replying to Travis Scrimshaw:

there are many time critical parts of Sage that rely on this being very fast, so we need an explicit Cython subclass rather than a dynamically created Python subclass through the category framework.

The original authors decided to implement the necessary fast Cython stuff via hooks. I wouldn't know why suddenly subclassing would be needed.

[tscrim]

comment:9

Replying to Matthias Köppe:

Replying to Travis Scrimshaw:

there are many time critical parts of Sage that rely on this being very fast, so we need an explicit Cython subclass rather than a dynamically created Python subclass through the category framework.

The original authors decided to implement the necessary fast Cython stuff via hooks. I wouldn't know why suddenly subclassing would be needed.

Let's take a look at the base_ring() method as something very concrete. This is something that is not needed by all Parents (e.g., Partitions) and has a None return type that needs to be checked against:

sage: Partitions().base_ring() is None
True

It is something that should actually be an @abstract_method in the Modules category, but we cannot do that with the default implementation returning self._base, which defaults to None. However, it needs to be very fast as it is called a lot by tight-loop polynomial code, and many times bypassed to get _base with an assumption that it is not None. If I had time, I would separate this out as Parent_with_base and make the necessary class inheritance changes.

Is this refactoring strictly necessary, no. However, it is technical debt and tab completion pollution and we cannot simply test if a class has a base ring (so picking out, say, all modules and Lie groups is more complicated).

While it does make sense for methods to fail, I think that should be input dependent (e.g., trying to construct an element when a scheme has no points), not implementation dependent (Partitions will never have a base ring, no matter what input it takes).

[mkoeppe]

comment:10

I agree that there are many possible plausible redesigns along these lines that could give overall improvements. For example, in addition to your point about _base (which already comes in from CategoryObject!), as discussed elsewhere, it's not clear what CategoryObject really has to do with managing names of generators; and why every parent needs to have a _factory_data etc.

However, to refocus on the goal of this ticket: Currently Element has exactly one cdef attribute, _parent, whereas CategoryObject has 7, and Parent has an additional 17 if I haven't miscounted.

It's clear that Element must remain as lightweight as possible, which I think rules out the idea (comment:3) of making Element a subclass of CategoryObject.

I would instead propose to move the cdef attribute _parent to CategoryObject (or alternatively to Parent -- I don't have a strong opinion on this, given that there are no real current uses of non-Parent CategoryObjects.)

The one additional cdef attribute in CategoryObject or Parent is a very mild change, and it would make the structure layouts compatible, so that we can implement parents that have parents / elements that have elements.

[mkoeppe]

comment:11

Replying to Matthias Köppe:

I would instead propose to move the cdef attribute _parent to CategoryObject

To clarify, after the proposed change, Element would still have the _parent cdef attribute. CategoryObject would be changed so that it has the _parent cdef too. For example, this could be done by having both Element and CategoryObject subclass from a new class SageObjectWithParent that provides this cdef attribute.