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:  sage6.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: 
Description (last modified by )
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 betterRingElement
, 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 returnsage.structure.coerce_actions....
to provide multiplication.  These actions can be implemented in Cythonwhile the categories stay in Python!
Change History (52)
comment:1 followup: ↓ 3 Changed 7 years ago by
comment:2 followup: ↓ 4 Changed 7 years ago by
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
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 multiplicationnot just for backward compatibility! Moreover, in_lmul_/_rmul_
one can assume that the second argument comes from the base ringin 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 ; followup: ↓ 6 Changed 7 years ago by
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 fromElement
) and a special path for scalar multiplication (_lmul_/_rmul_
). Problem: You can not implement a ring multiplication when you just inherit fromModuleElement
, sinceModuleElement.__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 speeup 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 subcategory of Rings()
or not.
comment:5 followup: ↓ 7 Changed 7 years ago by
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 ; followups: ↓ 8 ↓ 17 Changed 7 years ago by
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 ofCombinatorialFreeModule
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 fromElement
) and a special path for scalar multiplication (_lmul_/_rmul_
). Problem: You can not implement a ring multiplication when you just inherit fromModuleElement
, sinceModuleElement.__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 fromRingElement
, and then theCombinatorialFreeModule.Element
attribute is assigned during initialisation, according to whether the category is a subcategory ofRings()
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
Replying to SimonKing:
Another question: What is the reason for having
CombinatorialFreeModule
insage.combinat
? Is it just since the author is a "combinat guy"? I actually never understood the adjective "combinatorial" inCombinatorialFreeModule
what is it, in contrast to just anyFreeModule
, and is there a compelling reason for not having it insage.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
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 fromElement
) and a special path for scalar multiplication (_lmul_/_rmul_
). Problem: You can not implement a ring multiplication when you just inherit fromModuleElement
, sinceModuleElement.__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 fromCombinatorialFreeModuleElement
.
Right. In contrast to the category framework, where the element class of a supercategory is mixed in, the .Element
attribute of a superclass 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 FreeModuleElement
s. 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
callsself.parent().product
.product
callsproduct_on_basis
.
These are many indirectionstoo 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
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:Apparently, the line "if have_same_parent_c..." is to break a recursion. Instead, I suggest thatdef __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)
coercion_model.bin_op
should be changed, so that the parent has the possibility to define an action ON ITSELF (usingParent._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
 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
Based on the above discussion, I changed the aim of the ticket.
comment:12 Changed 7 years ago by
 Branch set to u/SimonKing/combinatorial_free_module_cython_coercion
comment:13 followup: ↓ 15 Changed 7 years ago by
 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 casebycase 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
:
 A parent should be able to provide an action on ANY parent, including itself.
 The possibility to use any action should be implemented on the level of
Element.__mul__
(similarlyElement.__add__
etc).  The only thing that
ModuleElement.__mul__
andRingElement.__mul__
should contribute is a shortcut. 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 thecoercion_model
; andRingElement.__mul__
deals with the special case that the two elements have identical parents, which again is faster than calling thecoercion_model
.
comment:14 Changed 7 years ago by
 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
Replying to SimonKing:
The commit that I just pushed moves
CombinatorialFreeModule
to Cython and lets it useRingElement
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
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 linksage.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
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
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 subcategories 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
See #18758.
Nicolas, can you announce the new ticket on sagecombinatdevel? I really have to leave now...
comment:20 Changed 7 years ago by
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 sagedevel : 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
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
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 followup: ↓ 31 Changed 7 years ago by
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
 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.  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.  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
comment:25 Changed 7 years ago by
 Commit changed from e1111c346a82639bb41161469754d45008117801 to 6c3e7830a14a2467258faabce767367cfe4b4acc
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

comment:26 Changed 7 years ago by
 Status changed from new to needs_review
The old branch on the cython version of CombinatorialFreeModule became obsolete. Hence, I forcepushed 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
 Commit changed from 6c3e7830a14a2467258faabce767367cfe4b4acc to dfba8b8dfcaf23f76d4f62f575b862aba48b0be8
Branch pushed to git repo; I updated commit sha1. New commits:
dfba8b8  correcting a typo

comment:28 followup: ↓ 30 Changed 7 years ago by
 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
 Commit changed from dfba8b8dfcaf23f76d4f62f575b862aba48b0be8 to fe7226d9e28d1dbf4130e8b57fb09885bd76226c
Branch pushed to git repo; I updated commit sha1. New commits:
fe7226d  Use proper format for a NOTE section

comment:30 in reply to: ↑ 28 Changed 7 years ago by
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

comment:31 in reply to: ↑ 23 ; followup: ↓ 32 Changed 7 years ago by
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
 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. 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. 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_
toSets.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 thanNone
?
Cheers,
Nicolas
comment:32 in reply to: ↑ 31 Changed 7 years ago by
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 returnsNone
. Or a classB
inheriting fromA
itself inheriting fromParent
, whereB._get_action_
may want to returnNone
to specify: useA._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_
toSets.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 thanNone
?
I am not so sure. But it would be easy to implement (as I have explained above).
comment:33 Changed 7 years ago by
 Commit changed from fe7226d9e28d1dbf4130e8b57fb09885bd76226c to c855ebce6eabb7e0189a585ed1849a68ba98f041
Branch pushed to git repo; I updated commit sha1. New commits:
c855ebc  Detect definition of actions along MRO and category hierarchy

comment:34 Changed 7 years ago by
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 followup: ↓ 37 Changed 7 years ago by
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
 Commit changed from c855ebce6eabb7e0189a585ed1849a68ba98f041 to 42cb88a3b55547931ec037a44fec5857f8f5e58f
Branch pushed to git repo; I updated commit sha1. New commits:
42cb88a  Fixing another typo

comment:37 in reply to: ↑ 35 Changed 7 years ago by
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
 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 Qvector 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
 Commit changed from 42cb88a3b55547931ec037a44fec5857f8f5e58f to a5bdbf6f85ea0d732a13ebc7d8e91dbd28c92ef0
Branch pushed to git repo; I updated commit sha1. New commits:
a5bdbf6  Fix a doctest

comment:40 followup: ↓ 50 Changed 7 years ago by
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 supercategory C of P.category()
.
One could easily work around, but this would involve a little slowdown. So, better fix the issue rather than working around!
comment:41 Changed 7 years ago by
Got it: FormalSums(ZZ).base_extend(GF(7))
returns a wrongly initialised parent.
comment:42 Changed 7 years ago by
 Dependencies set to #18795
comment:43 Changed 7 years ago by
 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.
comment:44 Changed 7 years ago by
<the previous text was posted on the wrong ticket>
comment:45 Changed 7 years ago by
 Description modified (diff)
comment:46 Changed 7 years ago by
 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
 Dependencies #18795 deleted
 Milestone changed from sage6.8 to sage6.10
comment:48 Changed 5 years ago by
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
 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
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, whileAdditiveMagmas().parent_class._get_action_
yields an additive action of self on self. Hence, in order to get a ring structure, it is essential thatParent.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
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
Indeed. Now there is much less difference between Element
and the derived classes like ModuleElement
.
Here is how
CombinatorialFreeModuleElement
fails to use the coercion framework properly.It uses the method
_acted_upon_
to implement multiplication by scalars, and then doesHowever, it is clearly the job of
_lmul_/_rmul_
to implement a scalar multiplicationnot just for backward compatibility! Moreover, in_lmul_/_rmul_
one can assume that the second argument comes from the base ringin 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.