Opened 7 years ago

Last modified 4 years ago

#18756 needs_work defect

Use coerce actions in the category framework

Reported by: SimonKing Owned by:
Priority: major Milestone: sage-6.10
Component: coercion Keywords: cython, coercion, actions, categories
Cc: nthiery, combinat Merged in:
Authors: Simon King Reviewers: Travis Scrimshaw
Report Upstream: N/A Work issues:
Branch: u/SimonKing/combinatorial_free_module_cython_coercion (Commits, GitHub, GitLab) Commit: a5bdbf6f85ea0d732a13ebc7d8e91dbd28c92ef0
Dependencies: Stopgaps:

Status badges

Description (last modified by SimonKing)

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!

Change History (52)

comment:1 follow-up: Changed 7 years ago by SimonKing

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.

comment:2 follow-up: Changed 7 years ago by nthiery

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?

comment:3 in reply to: ↑ 1 Changed 7 years ago by nthiery

Replying to SimonKing:

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.

comment:4 in reply to: ↑ 2 ; follow-up: Changed 7 years ago by SimonKing

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.

comment:5 follow-up: Changed 7 years ago by SimonKing

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?

comment:6 in reply to: ↑ 4 ; follow-ups: Changed 7 years ago by nthiery

Replying to SimonKing:

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

comment:7 in reply to: ↑ 5 Changed 7 years ago by nthiery

Replying to SimonKing:

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.

comment:8 in reply to: ↑ 6 Changed 7 years ago by SimonKing

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.

comment:9 Changed 7 years ago by SimonKing

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_fancy_multiplication_. Hence, there would be no need to override _mul_ just to make things work. There are other paths to achieve the same aim.

comment:10 Changed 7 years ago by SimonKing

  • Description modified (diff)
  • Keywords actions categories added; CombinatorialFreeModule removed
  • Summary changed from Use cython and coercion for CombinatorialFreeModule to Use coerce actions in the category framework

comment:11 Changed 7 years ago by SimonKing

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

comment:12 Changed 7 years ago by SimonKing

  • Branch set to u/SimonKing/combinatorial_free_module_cython_coercion

comment:13 follow-up: Changed 7 years ago by SimonKing

  • Branch u/SimonKing/combinatorial_free_module_cython_coercion deleted
  • Component changed from algebra to coercion

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.

comment:14 Changed 7 years ago by SimonKing

  • Branch set to u/SimonKing/combinatorial_free_module_cython_coercion
  • Commit set to e1111c346a82639bb41161469754d45008117801

WTF?? Why has the branch been automatically deleted?

comment:15 in reply to: ↑ 13 Changed 7 years ago by SimonKing

Replying to SimonKing:

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.

comment:16 Changed 7 years ago by nthiery

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!

comment:17 in reply to: ↑ 6 Changed 7 years ago by jdemeyer

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.

comment:18 Changed 7 years ago by SimonKing

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.

comment:19 Changed 7 years ago by SimonKing

See #18758.

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

comment:20 Changed 7 years ago by nborie

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...

comment:21 Changed 7 years ago by tscrim

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.

comment:22 Changed 7 years ago by nborie

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?).

comment:23 follow-up: Changed 7 years ago by SimonKing

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!

comment:24 Changed 7 years ago by SimonKing

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.

comment:25 Changed 7 years ago by git

  • Commit changed from e1111c346a82639bb41161469754d45008117801 to 6c3e7830a14a2467258faabce767367cfe4b4acc

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

6c3e783Allow definition of coerce actions via Category.ParentMethods

comment:26 Changed 7 years ago by SimonKing

  • Authors set to Simon King
  • Status changed from new to needs_review

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?

comment:27 Changed 7 years ago by git

  • Commit changed from 6c3e7830a14a2467258faabce767367cfe4b4acc to dfba8b8dfcaf23f76d4f62f575b862aba48b0be8

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

dfba8b8correcting a typo

comment:28 follow-up: Changed 7 years ago by tscrim

  • Reviewers set to Travis Scrimshaw

+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).

comment:29 Changed 7 years ago by git

  • Commit changed from dfba8b8dfcaf23f76d4f62f575b862aba48b0be8 to fe7226d9e28d1dbf4130e8b57fb09885bd76226c

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

fe7226dUse proper format for a NOTE section

comment:30 in reply to: ↑ 28 Changed 7 years ago by SimonKing

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:

fe7226dUse proper format for a NOTE section

comment:31 in reply to: ↑ 23 ; follow-up: Changed 7 years ago by nthiery

Hi Simon!

Replying to SimonKing:

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

comment:32 in reply to: ↑ 31 Changed 7 years ago by SimonKing

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).

comment:33 Changed 7 years ago by git

  • Commit changed from fe7226d9e28d1dbf4130e8b57fb09885bd76226c to c855ebce6eabb7e0189a585ed1849a68ba98f041

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

c855ebcDetect definition of actions along MRO and category hierarchy

comment:34 Changed 7 years ago by SimonKing

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).

comment:35 follow-up: Changed 7 years ago by 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).

comment:36 Changed 7 years ago by git

  • Commit changed from c855ebce6eabb7e0189a585ed1849a68ba98f041 to 42cb88a3b55547931ec037a44fec5857f8f5e58f

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

42cb88aFixing another typo

comment:37 in reply to: ↑ 35 Changed 7 years ago by SimonKing

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.

comment:38 Changed 7 years ago by SimonKing

  • Status changed from needs_review to needs_work

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.

comment:39 Changed 7 years ago by git

  • Commit changed from 42cb88a3b55547931ec037a44fec5857f8f5e58f to a5bdbf6f85ea0d732a13ebc7d8e91dbd28c92ef0

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

a5bdbf6Fix a doctest

comment:40 follow-up: Changed 7 years ago by SimonKing

Meanwhile I think it is essential to ascend the MRO resp. the category hierarchy.

Rationale: The plan for #18758 is to let Magmas().parent_class provide a _get_action_ method returning a multiplicative action of self on self, while AdditiveMagmas().parent_class._get_action_ yields an additive action of self on self. Hence, in order to get a ring structure, it is essential that Parent.get_action has access to both categorical _get_action_ methods.

To be fixed (here or in #18758?) is the issue with wrongly initialised parents. By this, I mean isinstance(P, C.parent_class) and not isinstance(P, P.category().parent_class) for a proper super-category C of P.category().

One could easily work around, but this would involve a little slow-down. So, better fix the issue rather than working around!

comment:41 Changed 7 years ago by SimonKing

Got it: FormalSums(ZZ).base_extend(GF(7)) returns a wrongly initialised parent.

comment:42 Changed 7 years ago by SimonKing

  • Dependencies set to #18795

comment:43 Changed 7 years ago by SimonKing

  • Status changed from needs_work to needs_review

I believe this is ready for review now. The dependency #18795 is ready, too, but isn't merged here, which I believe is the correct thing to do, or should I merge it?

Concerning the question on whether or not we should go up the mro and the categories: I think it makes sense to do it. Different algebraic structure / categories have different stories to tell about different actions. Hence, either it is requested to explicitly call "super(...)._get_action_" resp. hardcode all specific situations when implementing _get_action_, or we do the super call automatically. And I believe automatically is the more stable solution.

There remains the question if it slows down one or another computation. Do you have ideas for suitable benchmarks? They would involve lots of different parents engaged in actions, since Parent.get_action is cached and thus won't slow down when repeatedly requesting an action for always the same parents.

Last edited 7 years ago by SimonKing (previous) (diff)

comment:44 Changed 7 years ago by SimonKing

<the previous text was posted on the wrong ticket>

Last edited 7 years ago by SimonKing (previous) (diff)

comment:45 Changed 7 years ago by SimonKing

  • Description modified (diff)

comment:46 Changed 7 years ago by SimonKing

  • Description modified (diff)

Argh! I was posting on the wrong ticket. What I wrote should go to #18758...

comment:47 Changed 6 years ago by jdemeyer

  • Dependencies #18795 deleted
  • Milestone changed from sage-6.8 to sage-6.10

comment:48 Changed 5 years ago by jdemeyer

It is hard for me to understand what this ticket is really about and how #20767 would affect it.

comment:49 Changed 5 years ago by jdemeyer

  • Status changed from needs_review to needs_work

Does not build anymore due to #20686.

comment:50 in reply to: ↑ 40 Changed 5 years ago by jdemeyer

Replying to SimonKing:

Meanwhile I think it is essential to ascend the MRO resp. the category hierarchy.

Rationale: The plan for #18758 is to let Magmas().parent_class provide a _get_action_ method returning a multiplicative action of self on self, while AdditiveMagmas().parent_class._get_action_ yields an additive action of self on self. Hence, in order to get a ring structure, it is essential that Parent.get_action has access to both categorical _get_action_ methods.

I don't quite get why you need to manually play with the MRO. Why not use super() calls in the _get_action_ implementations (instead of returning None) for that?

comment:51 Changed 4 years ago by SimonKing

In the meantime, a lot of things have changed in sage.structure.element. Thus, it might be worthwhile to see what points raised in the ticket description are still valid, and then start from scratch addressing these points.

comment:52 Changed 4 years ago by jdemeyer

Indeed. Now there is much less difference between Element and the derived classes like ModuleElement.

Note: See TracTickets for help on using tickets.