Use coerce actions in the category framework

[simon-king-jena]

The starting point of this ticket was:

CombinatorialFreeModule

• is written in Python (hence, is too slow at least for my applications),
• its elements just inherit from Element and not from a more appropriate base class (ModuleElement or even better RingElement, since the former for some reason raises an error on an inner multiplication), and
• it is not conforming to Sage's coercion model, which really is bad, since I have seen many people who would start with CombinatorialFreeModule when implementing new algebraic stuff.

Early in the discussion, it was found that using RingElement isn't really a solution. Instead, the aim of this ticket was broadened:

• It should be possible to define a multiplication action of a parent on itself; this require changing ModuleElement.__mul__.
• Instead of overriding __mul__ and _mul_ for element classes, the category framework should instead return sage.structure.coerce_actions.... to provide multiplication.
• These actions can be implemented in Cython---while the categories stay in Python!

CC: @nthiery @sagetrac-sage-combinat

Component: coercion

Keywords: actions

Author: Simon King

Branch/Commit: u/SimonKing/combinatorial_free_module_cython_coercion @ a5bdbf6

Reviewer: Travis Scrimshaw

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

[simon-king-jena]

comment:1

Here is how CombinatorialFreeModuleElement fails to use the coercion framework properly.

It uses the method _acted_upon_ to implement multiplication by scalars, and then does

    # For backward compatibility
    _lmul_ = _acted_upon_
    _rmul_ = _acted_upon_

However, it is clearly the job of _lmul_/_rmul_ to implement a scalar multiplication---not just for backward compatibility! Moreover, in _lmul_/_rmul_ one can assume that the second argument comes from the base ring---in the current implementation, this has to be explicitly tested, simply since there is no such assumption for _acted_upon_.

And what is worst: Using _acted_upon_ is one way to implement a general action that goes BEYOND the action of the base ring. If one wants to implement an action of, say, a path algebra on a free module over a path algebra, then one would "of course" use _acted_upon_---but by the current design, it would break scalar multiplication.

[nthiery]

comment:2

Dear Simon,

+1 on cythonizing CombinatorialFreeModuleElement (but not CombinatorialFreeModule unless there is a compelling reason)

ok on inheriting from ModuleElement.

-1 on inheriting from RingElement. It's too much of an abuse.

Can you elaborate on the speed issue?

[nthiery]

comment:3

Replying to @simon-king-jena:

Here is how CombinatorialFreeModuleElement fails to use the coercion framework properly.

It uses the method _acted_upon_ to implement multiplication by scalars, and then does

    # For backward compatibility
    _lmul_ = _acted_upon_
    _rmul_ = _acted_upon_

However, it is clearly the job of _lmul_/_rmul_ to implement a scalar multiplication---not just for backward compatibility! Moreover, in _lmul_/_rmul_ one can assume that the second argument comes from the base ring---in the current implementation, this has to be explicitly tested, simply since there is no such assumption for _acted_upon_.

And what is worst: Using _acted_upon_ is one way to implement a general action that goes BEYOND the action of the base ring. If one wants to implement an action of, say, a path algebra on a free module over a path algebra, then one would "of course" use _acted_upon_---but by the current design, it would break scalar multiplication.

I don't remember exactly the rationale behind this comment. It could well be that it was the fact of implementing _acted_upon_ rather than _lmul_ / _rmul_ which was for backward compatibility. Feel free to clean this up.

[simon-king-jena]

comment:4

Replying to @nthiery:

+1 on cythonizing CombinatorialFreeModuleElement (but not CombinatorialFreeModule unless there is a compelling reason)

I was talking about cythoning the elements and the helper functions. I plan to turn CombinatorialFreeModule into a Python class in a cython file (i.e., keeping parent and element in one file), which means that some generic code in the methods of CombinatorialFreeModule would become faster. But the class would NOT be cdef.

ok on inheriting from ModuleElement.

-1 on inheriting from RingElement. It's too much of an abuse.

I disagree. Actually I believe the current structure is an abuse.

• ELement uses _acted_on_/_acted_upon_ to implement actions. It has no _lmul_, which means that the comment "for backward compatibility" fails entirely.
• ModuleElement provides the infrastructure for both general actions (inherited from Element) and a special path for scalar multiplication (_lmul_/_rmul_). Problem: You can not implement a ring multiplication when you just inherit from ModuleElement, since ModuleElement.__mul__ raises an error if both arguments belong to the same parent.
• RingElement provides the infrastructure for general actions, scalar multiplication, and ring multiplication (via _mul_).

I have seen that people use CombinatorialFreeModule as a starting points for implementing algebras. That's an abuse, since it works around the existing infrastructure.

Can you elaborate on the speed issue?

The old implementation of path algebras used CombinatorialFreeModule (by the way: For ALGEBRAS, hence, one needs ring multiplication!). Granted, in this case the actual spee-up comes from using special data types.

It is of course not ideal when one uses RingElement to implement elements of a module. However, we must not forget that CombinatorialFreeModule is applied in a wider range, not just to implement modules but also rings.

Alternatively, one could create two base classes for elements: One inherits from ModuleElement, the other from RingElement, and then the CombinatorialFreeModule.Element attribute is assigned during initialisation, according to whether the category is a sub-category of Rings() or not.

[simon-king-jena]

comment:5

Another question: What is the reason for having CombinatorialFreeModule in sage.combinat? Is it just since the author is a "combinat guy"? I actually never understood the adjective "combinatorial" in CombinatorialFreeModule---what is it, in contrast to just any FreeModule, and is there a compelling reason for not having it in sage.modules?

[nthiery]

comment:6

Replying to @simon-king-jena:

I was talking about cythoning the elements and the helper functions.

Good.

I plan to turn CombinatorialFreeModule into a Python class in a cython file (i.e., keeping parent and element in one file), which means that some generic code in the methods of CombinatorialFreeModule would become faster. But the class would NOT be cdef.

Putting CombinatorialFreeModule in a Cython file would mean that we could not use the Python debugger on it and that any change would require a recompilation. That's not necessarily a show stopper, but this has to be weighted against the expected gains.

I have seen that people use CombinatorialFreeModule as a starting points for implementing algebras. That's an abuse, since it works around the existing infrastructure.

It's possible that the technical implementation of the multiplication by scalars is incorrect, and I'd be happy if you fixed that.

But CombinatorialFreeModule is -- by original design -- meant to be used to implement both modules and algebras. And it has been used intensively both ways. No abuse here.

• ELement uses _acted_on_/_acted_upon_ to implement actions. It has no _lmul_, which means that the comment "for backward compatibility" fails entirely.
• ModuleElement provides the infrastructure for both general actions (inherited from Element) and a special path for scalar multiplication (_lmul_/_rmul_). Problem: You can not implement a ring multiplication when you just inherit from ModuleElement, since ModuleElement.__mul__ raises an error if both arguments belong to the same parent.
• RingElement provides the infrastructure for general actions, scalar multiplication, and ring multiplication (via _mul_).

Yup, the single inheritance of Cython is a very strong constraint. It pushes us to do crap.

Now assume that we consider acceptable to inherit from RingElement for non rings, why do we need RingElement in the first place? Could not we just merge its features into ModuleElement?

Alternatively, one could create two base classes for elements: One inherits from ModuleElement, the other from RingElement, and then the CombinatorialFreeModule.Element attribute is assigned during initialisation, according to whether the category is a sub-category of Rings() or not.

This would make things complicated for subclasses of CombinatorialModule that have an Element class that inherits from CombinatorialFreeModuleElement.

Now a question: what are the speed critical things that we really need to be Cythonized? If it's just the __mul__ methods and friends, it would be worth experimenting with replacing their Python implementations in the Modules/Rings/Algebras categories by Cythonized methods (with recent versions of Cython, this is possible). Maybe this would be sufficient.

Cheers, Nicolas

[nthiery]

comment:7

Replying to @simon-king-jena:

Another question: What is the reason for having CombinatorialFreeModule in sage.combinat? Is it just since the author is a "combinat guy"? I actually never understood the adjective "combinatorial" in CombinatorialFreeModule---what is it, in contrast to just any FreeModule, and is there a compelling reason for not having it in sage.modules?

It's just how Mike Hansen named it back in 2008. It definitely should be in sage.modules (typically in sage.modules.with_basis) and be called FreeModule(QQ, I). See #10673.

[simon-king-jena]

comment:8

Replying to @nthiery:

• ELement uses _acted_on_/_acted_upon_ to implement actions. It has no _lmul_, which means that the comment "for backward compatibility" fails entirely.
• ModuleElement provides the infrastructure for both general actions (inherited from Element) and a special path for scalar multiplication (_lmul_/_rmul_). Problem: You can not implement a ring multiplication when you just inherit from ModuleElement, since ModuleElement.__mul__ raises an error if both arguments belong to the same parent.
• RingElement provides the infrastructure for general actions, scalar multiplication, and ring multiplication (via _mul_).

Yup, the single inheritance of Cython is a very strong constraint. It pushes us to do crap.

Perhaps it would really be better to change ModuleElement.__mul__? The fact that it raises an error if both parents are equal is not good. It may haVe been motivated by an attempt to break an infinite recursion (namely: To test existence of an action, you would try to multiply elements, but to multiply elements, you need to know of there is an action). Perhaps that cycle should be broken in a different way?

This would make things complicated for subclasses of CombinatorialModule that have an Element class that inherits from CombinatorialFreeModuleElement.

Right. In contrast to the category framework, where the element class of a super-category is mixed in, the .Element attribute of a super-class is not mixed in :-/. Perhaps this could be implemented? Perhaps the .element_class lazy attribute could also have a look at super(self,type(self)).Element or so?

Now a question: what are the speed critical things that we really need to be Cythonized? If it's just the __mul__ methods and friends, it would be worth experimenting with replacing their Python implementations in the Modules/Rings/Algebras categories by Cythonized methods (with recent versions of Cython, this is possible). Maybe this would be sufficient.

If I understand the general pattern: To implement an algebraic structure using CombinatorialFreeModule, one implements methods such as product_on_basis or degree_on_basis.

I must admit that by searching the code for the past 30 minutes, I did not really succeed to find out at what place "product_on_basis" is actually turned into a __mul__ method for FreeModuleElements. But after searching 60 minutes, I found:

• Magmas().element_class provides a __mul__ method that mimics the __mul__ method of ring elements. Fine, but Python.
• Magmas().parent_class.__init_extra__ assigns a _mul_ method for the element class by setting it to _mul_parent
• _mul_parent calls self.parent().product
• .product calls product_on_basis.

These are many indirections---too many python calls for a single multiplication in high performance code, I'd say.

One detail: Apparently, setting _mul_ to an attribute of the class results in slower access than what is possible when providing a method during creation of the class (such as _mul_parent):

sage: A = DiGraph({1:{2:['a']}, 2:{3:['b']}, 3:{1:['c'], 4:['m']}, 4:{5:['n']}, 5:{6:['x'],7:['y']}, 6:{7:['z']}}).path_semigroup().algebra
(QQ)
sage: A.inject_variables()
Defining e_1, e_2, e_3, e_4, e_5, e_6, e_7, a, b, c, m, n, x, y, z
sage: %timeit x.__mul__
The slowest run took 122.24 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 50.7 ns per loop
sage: %timeit x._mul_parent
The slowest run took 100.65 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 61.6 ns per loop
sage: %timeit x._mul_
The slowest run took 41.40 times longer than the fastest. This could mean that an intermediate result is being cached
10000000 loops, best of 3: 121 ns per loop

Hence, we would already gain a tiny bit by providing _mul_ during creation of the element class, not afterwards.

By the way, why is all this in Magmas()? It uses "product_on_basis", hence, it uses the notion of a basis, which isn't defined for magmas, right? In fact, I first searched in AlgebrasWithBasis to find the definition of multiplication with product_on_basis.

[simon-king-jena]

comment:9

Sage provides the possibility to define arbitrary actions. See sage.structure.coerce_actions.

As much as I can see, the only action that currently can not be defined is an action of a parent on itself. I suggest to change it, as follows.

• RingElement.__mul__ should stay as it is. Since we have a ring element, we can assume that there is a multiplication among elements of the same parent, which is to be implemented with _mul_.

• ModuleElement.__mul__ currently does the following:

  def __mul__(left, right):
      if PyInt_CheckExact(right):
          return (<ModuleElement>left)._mul_long(PyInt_AS_LONG(right))
      if PyInt_CheckExact(left):
          return (<ModuleElement>right)._mul_long(PyInt_AS_LONG(left))
      if have_same_parent_c(left, right):
          raise TypeError(arith_error_message(left, right, mul))
      return coercion_model.bin_op(left, right, mul)

  Apparently, the line "if have_same_parent_c..." is to break a recursion. Instead, I suggest that coercion_model.bin_op should be changed, so that the parent has the possibility to define an action ON ITSELF (using Parent._get_action_).

The first point is that it would be easy to implement _get_action_ as a parent method of a category:

• The parent method could first test if it inherits an action (e.g. an sage.structure.coerce_action.LeftModuleAction in the case of a module), and if not then it should see if an action of the parent on itself may be implemented using product_on_basis and friends.

The second point is:

• The action could be implemented in Cython, which is already the case for sage.structure.coerce_action.LeftModuleAction.

The third point is:

• The approach is very flexible. _get_action_ can return an action that relies on product_on_basis or that relies on _mul_ or on _lmul_ or on _my_fancymultiplication. Hence, there would be no need to override _mul_ just to make things work. There are other paths to achieve the same aim.

[simon-king-jena]

Changed keywords from CombinatorialFreeModule to actions

[simon-king-jena]

Description changed:

--- 
+++ 
@@ -1,6 +1,12 @@
+The starting point of this ticket was:
+
 `CombinatorialFreeModule`
 - is written in Python (hence, is too slow at least for my applications),
 - its elements just inherit from `Element` and not from a more appropriate base class (`ModuleElement` or even better `RingElement`, since the former for some reason raises an error on an inner multiplication), and
 - it is not conforming to Sage's coercion model, which really is bad, since I have seen many people who would start with `CombinatorialFreeModule` when implementing new algebraic stuff.

-The aim of this ticket is to fix these issues.
+Early in the discussion, it was found that using `RingElement` isn't really a solution. Instead, the aim of this ticket was broadened:
+
+- It should be possible to define a multiplication action of a parent on itself; this require changing `ModuleElement.__mul__`.
+- Instead of overriding `__mul__` and `_mul_` for element classes, the category framework should instead return `sage.structure.coerce_actions....` to provide multiplication.
+- These actions can be implemented in Cython---while the categories stay in Python!

[simon-king-jena]

comment:11

Based on the above discussion, I changed the aim of the ticket.

[simon-king-jena]

Branch: u/SimonKing/combinatorial_free_module_cython_coercion

[simon-king-jena]

comment:13

The commit that I just pushed moves CombinatorialFreeModule to Cython and lets it use RingElement and _l/rmul_ instead of the current approach to work around the coercion framework.

Note that an action only depends on the parents involved and is cached. Hence, it is better faster to invoke the category framework to use the action to do a multiplication, than to let __mul__ decide on the implementation of multiplication in each single instance. Hence, we should NOT do

class Modules:
    class ElementMethods:
        def __mul__(self, other):
            if self.base_ring().has_coerce_map_from(parent(other)):
                # Bad case-by-case behaviour
                return self._mul_(other)
            return coercion_model.bin_op(self, other, operator.mul)

and its counterpart in Magmas.ElementMethods. Instead, one should have a ParentMethod returning an action.

However, my plan is to first sanitise the code of [Ring/Module]Element:

1. A parent should be able to provide an action on ANY parent, including itself.
2. The possibility to use any action should be implemented on the level of Element.__mul__ (similarly Element.__add__ etc).
3. The only thing that ModuleElement.__mul__ and RingElement.__mul__ should contribute is a short-cut. That's basically what is already done: ModuleElement.__mul__ treats python int in a special way, since I guess the typecheck involved is faster than calling the coercion_model; and RingElement.__mul__ deals with the special case that the two elements have identical parents, which again is faster than calling the coercion_model.

[simon-king-jena]

Changed branch from u/SimonKing/combinatorial_free_module_cython_coercion to none

[simon-king-jena]

comment:14

WTF?? Why has the branch been automatically deleted?

[simon-king-jena]

Branch: u/SimonKing/combinatorial_free_module_cython_coercion

[simon-king-jena]

Commit: e1111c3

[simon-king-jena]

comment:15

Replying to @simon-king-jena:

The commit that I just pushed moves CombinatorialFreeModule to Cython and lets it use RingElement and _l/rmul_ instead of the current approach to work around the coercion framework.

To be clear: The aim is to make it ModuleElement, not RingElement, after sanitising the __mul__ methods in sage.structure.element.

[nthiery]

comment:16

I very much like the declarative approach.

Just wondering:

• Should there be two separate tickets: one for better support for coercions in categories, and the other for the Cythonizing of CFM (the two are relatively independent of each other)?

• Since there is some file moving anyway, what about using the occasion to move the .pyx file directly in sage.modules.with_basis.free_module (with just a link sage.combinat.free_module.CombinatorialFreeModule -> sage.modules.with_basis.free_module.FreeModule for backward compatibility)?

Thanks!

[jdemeyer]

comment:17

Replying to @nthiery:

Yup, the single inheritance of Cython is a very strong constraint.

Just a comment on this: one thing which is possible is inheriting from an extension type (a.k.a. cdef class) and a Python class, the result being a Python class. For example, in src/sage/rings/number_field/number_field_ideal.py, there is

class NumberFieldFractionalIdeal(MultiplicativeGroupElement, NumberFieldIdeal):

where MultiplicativeGroupElement is an extension type and NumberFieldIdeal is a Python class (the extension type must be first in the MRO). Of course, you lose the advantage of a fast Cython _mul_ call.

I also agree with SimonKing that inheriting from RingElement is not really a problem and that the current design of having a huge number of ...Element types might not have been the best design.

[simon-king-jena]

comment:18

Today I had a discussion with Nicolas, and the plan now is to connect category and action framework more tightly.

To define an action of G on S, either S._get_action_(G, op, self_on_left=...) should return an action (which is not an action in the mathematical sense; it is just something that is callable on a pair of elements) or G._get_action_(S,op,self_on_left=...) should return something.

It would be good to make it easier for the category framework to override that method. But methods inherited from Parent have precedence over ParentMethods. Hence, Parent._get_action_ (which just returns None) should be moved to Sets.ParentMethods._get_action_. Concrete parents can still override _get_action_, and sub-categories could override it as well.

In addition to that, Magmas.ParentMethods.__init_extra__ could use Parent.register_action to register actions.

However, all that would require that actions of a parent on ITSELF are possible. I guess technically they are possible. However, ModuleElement.__mul__ would refuse to use them: It raises an error, if both elements have the same parents, which means that a ring structure can really only be implemented by either inheriting from Element and providing a custom __mul__, or by inheriting from RingElement.

The framework for "actions on self" should be provided on a new ticket.

[simon-king-jena]

comment:19

See #18758.

Nicolas, can you announce the new ticket on sage-combinat-devel? I really have to leave now...

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:20

Hello,

I don't know if the following point is partially/not/completely related with this ticket. But you will be my heroes for three or four years if you solve that :

Matrix and MatrixSpace over ALL rings (not using RingElement...) #15160

sorry for the noise, to precise that, I would add a quote from an old topic from sage-devel : What we are unable to do right now ?

---

Hello,

Computing the inverse of the identity matrix is not possible. Ok, it works for rings using RingElement class for the elements (like ZZ, QQ, RR, CC, ...).

```
sage: SF = SymmetricFunctions(QQ).schur(); SF
Symmetric Functions over Rational Field in the Schur basis
sage: one = SF.one()
sage: zero = SF.zero()
sage: M = Matrix([[one, zero], [zero, one]])
sage: M
[s[]   0]
[  0 s[]]
sage: M.det()
s[]
sage: M.is_invertible()
True
sage: M.inverse()
...
AttributeError: 'SymmetricFunctionAlgebra_schur_with_category' object
has no attribute 'fraction_field'
sage: M = Matrix([[one]])
...
AttributeError: 'tuple' object has no attribute 'parent'
sage: M*M
[s[]   0]
[  0 s[]]
sage: SteenrodAlgebra(7)
mod 7 Steenrod algebra, milnor basis
sage: A = SteenrodAlgebra(7)
sage: M = Matrix([[A.one(), A.zero()], [A.zero(), A.one()]])
sage: M^2
[1 0]
[0 1]
sage: M.inverse()
AttributeError: 'SteenrodAlgebra_generic_with_category' object has no
attribute 'fraction_field'
```

For the curious, defining a fraction_field for these rings is not enought. The good fix should be more serious than that.

---

Fixing the scalar multiplication will perhaps fix linear algebra... Its works when I defined my own action of the coefficients on linear combination but It did break the rest of Sage (all parts of Sage using the RingElement class).

Currently I manage linear algebra on Combinatorial Free Modules just with horrible hacks.

Good chance since It goes further than my current skills with Sage core features...

[tscrim]

comment:21

This also seems like it might solve #15947. Although perhaps we could use the idea that we can specify a class in the category that all elements of that category inherit from?

However I'm not sure about the initial post about overriding _acted_upon_ would break scalar multiplication. Couldn't we just require that the user makes a super call at the end if they still want the scalar multiplication (such as for _get_action_ or _coerce_map_from_)? IMO, this would hardly an extraordinary requirement, and currently seems like a requirement for _get_action_ in the current proposal.

[0f5ae6f6-e03a-45d9-b571-4ce01615e676]

comment:22

I can confirm that in the mercurial patch attached to #15160 , I defined a _get_action_ method for MatrixSpace that did break all Sage linear algebra using RingElement since it did break the scalar multiplication between vector and matrix. I do not think this very old patch still apply but the very ugly code can still be read from the trac. I did not keep the error messages, I just remember it did go very far from my knowledge about coercion and like...

Anyway, with this old patch which break a large part of Sage, I did manage to invert bases change matrices of symmetric functions (matrix whose element live in a CombinatorialFreeModule).

[simon-king-jena]

comment:23

On my way to the next conference, I thought that a "minimally invasive" approach would perhaps be best.

By that, I mean:

I plan to NOT MOVE the current _get_action_ method from sage.structure.parent to sage.categories. After all, it is a cpdef function, probably for a reason.

Consequence of that approach is that the category framework will not be able to provide _get_action_ as a method of the parents. I want to point out that this is actually an advantage.

I plan to change Parent.get_action (without underscore), so that

1. the output of self._get_action_(...) is taken into account; this agrees with the general idea that methods specially written for a parent have precedence over the categorical general nonsense. If it returns something not None, then it is used.
2. if None was obtained in the first step, super(Parent, self)._get_action_ is taken into account. THIS can be obtained from the category framework. If it returns something not None, then it is used.
3. discover_action is called.

Only the second step is new. The advantages of my approach are:

• The category framework CAN provide an action via ParentMethods._get_action_. So, it is not needed to learn something new. One simply does for ParentMethods what one has previously done for Parent.
• It is conceivable that we have a parent P such that P._get_action_(S, ...) returns None for a specific parent S. but the category framework actually knows an action. In that situation, the category framework can provide that action, even though a method defined for the parent has precedence in the method resolution order over a method obtained from the category.
• There is no need to change existing implementations of _get_action_ (this is what I mean by "minimally invasive")

Let's see if that works!

[simon-king-jena]

comment:24

PS: I think the above should be done first, and then comes #18758. In that order, since the ticket here will make it possible to define actions via the category framework, while #18758 would provide a nice application of that possibility.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

6c3e783

Allow definition of coerce actions via Category.ParentMethods

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from e1111c3 to 6c3e783

[simon-king-jena]

comment:26

The old branch on the cython version of CombinatorialFreeModule became obsolete. Hence, I force-pushed a new branch.

It allows to define actions via a ParentMethods _get_action_, which is also demonstrated by a new doctest. What do you think?

[simon-king-jena]

Author: Simon King

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6c3e783 to dfba8b8

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

dfba8b8

correcting a typo

[tscrim]

comment:28

+1 to including category support for actions. So I'm happy with this patch modulo this change:

-        NOTE:
-
-        If a parent implements :meth:`_get_action_` then it has precedence
-        over an implementation obtained from the category framework.
-        However, if :meth:`_get_action_` returns None, then
-        ``self.category().parent_class._get_action_`` has a chance to give
-        a better answer.
+        .. NOTE::
+
+            If a parent implements :meth:`_get_action_` then it has precedence
+            over an implementation obtained from the category framework.
+            However, if :meth:`_get_action_` returns ``None``, then
+            ``self.category().parent_class._get_action_`` has a chance to give
+            a better answer.

Also +1 to cythonizing (key components of) CombinatorialFreeModule(Element).

[tscrim]

Reviewer: Travis Scrimshaw

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

fe7226d

Use proper format for a NOTE section

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from dfba8b8 to fe7226d

[simon-king-jena]

comment:30

Replying to @tscrim:

+1 to including category support for actions. So I'm happy with this patch modulo this change:

Done.

Also +1 to cythonizing (key components of) CombinatorialFreeModule(Element).

That has been the original purpose of the ticket. Shall we do that here or on a different ticket?

---

New commits:

fe7226d

Use proper format for a NOTE section

[nthiery]

comment:31

Hi Simon!

Replying to @simon-king-jena:

On my way to the next conference, I thought that a "minimally invasive" approach would perhaps be best.

By that, I mean:

I plan to NOT MOVE the current _get_action_ method from sage.structure.parent to sage.categories. After all, it is a cpdef function, probably for a reason.

Consequence of that approach is that the category framework will not be able to provide _get_action_ as a method of the parents. I want to point out that this is actually an advantage.

I plan to change Parent.get_action (without underscore), so that

1. the output of self._get_action_(...) is taken into account; this agrees with the general idea that methods specially written for a parent have precedence over the categorical general nonsense. If it returns something not None, then it is used.
2. if None was obtained in the first step, super(Parent, self)._get_action_ is taken into account. THIS can be obtained from the category framework. If it returns something not None, then it is used.
3. discover_action is called.

Only the second step is new. The advantages of my approach are:

• The category framework CAN provide an action via ParentMethods._get_action_. So, it is not needed to learn something new. One simply does for ParentMethods what one has previously done for Parent.
• It is conceivable that we have a parent P such that P._get_action_(S, ...) returns None for a specific parent S. but the category framework actually knows an action. In that situation, the category framework can provide that action, even though a method defined for the parent has precedence in the method resolution order over a method obtained from the category.
• There is no need to change existing implementations of _get_action_ (this is what I mean by "minimally invasive")

Let's see if that works!

Thanks for investigating!

I definitely see the point of having a protocol allowing for a _get_action_ method to state in certain cases "oh, never mind; I actually have nothing to say in this case, just do the usual stuff from super".

However the above implementation is not uniform: we could imagine use cases where a category may want to implement such a _get_action_ that occasionally returns None. Or a class B inheriting from A itself inheriting from Parent, where B._get_action_ may want to return None to specify: use A._get_action_.

So, to weight the pros and cons my questions are:

• How invasive would it really be to move Parent._get_action_ to Sets.ParentMethods? Does it actually requires to update anything else in the Sage code?

• super calls would be the natural thing to do here. Alas super and categories don't work so well together. Still, could we find a reasonable enough syntax for this that we could advertise in the documentation of _get_action_.

• Shall we investigate for a more uniform protocol where get_action would try each _get_action_ method along the MRO until one returns something else than None?

Cheers, Nicolas

[simon-king-jena]

comment:32

Replying to @nthiery:

However the above implementation is not uniform: we could imagine use cases where a category may want to implement such a _get_action_ that occasionally returns None. Or a class B inheriting from A itself inheriting from Parent, where B._get_action_ may want to return None to specify: use A._get_action_.

OK. But in the past, it has never been implemented to do this automatically. It has never been the case that Parent.get_action went up the MRO to test several ._get_action_ outputs until one of them returns something interesting.

So, to weight the pros and cons my questions are:

• How invasive would it really be to move Parent._get_action_ to Sets.ParentMethods? Does it actually requires to update anything else in the Sage code?

Yes. Everything that uses it in its cpdef form.

• super calls would be the natural thing to do here. Alas super and categories don't work so well together. Still, could we find a reasonable enough syntax for this that we could advertise in the documentation of _get_action_.

Why "syntax"? If we would really want to go up the MRO/category hierarchy, then we could in principle do so in Parent.get_action. I just don't know if that makes much sense, but assume we have

class MyFirstParent(Parent):
    def _get_action_(self, S,...):
        return something when S is a ring
class MySecondParent(MyFirstParent):
    def _get_action_(self, S,...):
        return something when S is a field

We COULD make it so that MySecondParent().get_action(S) would automatically first test the output of MySecondParent._get_action_ and then on MyFirstParent._get_action_ --- there would be no special syntax involved.

I only wonder if we WANT that to happen automatically.

• Shall we investigate for a more uniform protocol where get_action would try each _get_action_ method along the MRO until one returns something else than None?

I am not so sure. But it would be easy to implement (as I have explained above).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

c855ebc

Detect definition of actions along MRO and category hierarchy

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from fe7226d to c855ebc

[simon-king-jena]

comment:34

The new commit implements what I have proposed above. I am not convinced whether it is a good thing to have. Walking along the class AND the category hierarchy can be costly, I suppose, although it will happen only once for each S (the result is cached).

[tscrim]

comment:35

I don't necessarily like walking along the MRO as there might be times when we don't want to walk up (relatively expensive tests).

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Branch pushed to git repo; I updated commit sha1. New commits:

42cb88a

Fixing another typo

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from c855ebc to 42cb88a

[simon-king-jena]

comment:37

Replying to @tscrim:

I don't necessarily like walking along the MRO as there might be times when we don't want to walk up (relatively expensive tests).

I agree. I do believe that having two sources for _get_action_ (the parent and the category parent class) is a good thing. But I am less convinced about commit c855ebc.

[simon-king-jena]

comment:38

There is a trivial doctest error that needs to be fixed.

Other than that, it seems that somewhere in sage.modular, a Q-vector space is created whose class is an instance of Modules.parent_class but not of VectorSpaces.parent_class. That's what is creating problems in #18758. I need to find out where that is happening.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 42cb88a to a5bdbf6