Opened 7 years ago
Last modified 5 years ago
#18758 needs_work enhancement
Allow actions of a parent on itself
Reported by:  SimonKing  Owned by:  

Priority:  major  Milestone:  sage6.8 
Component:  coercion  Keywords:  actions on itself 
Cc:  nthiery, combinat  Merged in:  
Authors:  Simon King  Reviewers:  
Report Upstream:  N/A  Work issues:  
Branch:  u/SimonKing/allow_actions_of_parent_on_itself (Commits, GitHub, GitLab)  Commit:  d71a456dbd312980490f17d39ed97d3df6ccdcb9 
Dependencies:  #18756  Stopgaps: 
Description (last modified by )
Currently, ModuleElement.__mul__
raises an error when both elements have the same parent. Hence, in order to define a ring structure, one must not start with ModuleElement
, which is bad, since sometimes the concrete structure only depends on the category (see CombinatorialFreeModule).
The approach to be implemented here: ModuleElement.__mul__
and RingElement.__mul__
should provide shortcuts in cases where there is an obvious way to be faster than calling the coercion model, and otherwise it is the job of the coercion model (NOT of ModuleElement.__mul__
) to complain if the two elements come from the same parent without an action being defined.
Hence, it should be possible to start with ModuleElement
and get a ring structure on top of it by an appropriate action of the parent on itself. Here is an example that should be made work:
sage: from sage.categories.action import Action sage: class RingStructure(Action): ....: def __init__(self, R): ....: Action.__init__(self, R, R, True, operator.mul) ....: def _call_(self, g, a): ....: return g._mul_(a) ....: sage: from sage.structure.element import ModuleElement sage: class MyElement(ModuleElement): ....: def __init__(self, P, L): ....: ModuleElement.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) ....: sage: class MyParent(Parent): ....: Element = MyElement ....: def _get_action_(self, S, op, self_on_left): ....: if S is self and op == operator.mul and self_on_left: ....: return RingStructure(self) ....: sage: P = MyParent(category=Rings()) sage: l1 = P([1,2]) sage: l2 = P([3,4]) sage: l1+l2 <[(1, 3), (2, 4)]> sage: l1*l2 <[1, 2, 3, 4]>
Moreover, it should be possible to define the actions using ParentMethods in the category framework. I.e., _get_action_
should be moved from Parent to Sets.ParentMethods. This is why #18756 (where the whole idea started) is a dependency.
More precisely: The above RingStructure
(perhaps with some sanity test similar to sage.structure.coerce_action.ModuleAction
) should be defined in sage.structure.coerce_actions and used by Rings.ParentMethods._get_action_
.
Summary
 multiplication can still be defined by category initialisation in
Magmas()
. However, it should become faster and it should in future be easier to import the multiplication from a fast cython module.  The way to define an internal multiplication should be more uniform throughout Sage: One simply defines
_mul_
and initialises inMagmas()
. Overriding__mul__
(which in some situations was still needed) should in future be even more useless.  Similar statements hold for
_add_
.
Change History (22)
comment:1 Changed 7 years ago by
 Dependencies set to #18756
comment:2 Changed 7 years ago by
 Description modified (diff)
comment:3 Changed 7 years ago by
 Description modified (diff)
comment:4 Changed 7 years ago by
More precisely: The example from the ticket description shouldn't be called RingStructure but MagmaStructure, it should be defined in Magmas.ParentMethods._get_action_
, and it should have an additive counterpart.
comment:5 Changed 7 years ago by
Remark: Magmas.ElementMethods
does provide a generic multiplication using _mul_
(when present) and using coercion otherwise.
Two problems: There is an import statement in the multiplication method, which, if I recall correctly, is not for free. And it first checks the presence of a _mul_
attribute, which also slows things down.
So, it would be interesting to see if the following approach yields faster code:
 ALL element classes should have generic
__mul__
and__add__
methods. Those ofsage.structure.elements.Element
will just rely on coercion, whereasModuleElement
andRingElement
first try a shortcut via_mul_
resp._add_
. So, the hierarchy of algebraic base classes would be reflected in the usage of shortcuts.  The proposed actions
MagmaStructure
andAdditiveMagmaStructure
should test the presence of the attributes_mul_
resp._add_
during initialisation, ONCE. Henceforth, the presence of the attribute does not need to be tested any longer.
So, rather than providing a __mul__
methods, Magmas()
would provide an action, and there should be a __mul__
method for Element instead. Really, we need to test and get timings.
comment:6 followups: ↓ 7 ↓ 8 Changed 7 years ago by
I haven't pushed my branch yet. Anyway, what I can do is the following:
sage: class MyElement(Element): ....: def __init__(self, P, L): ....: Element.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyMElement(ModuleElement): ....: def __init__(self, P, L): ....: ModuleElement.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyRElement(RingElement): ....: def __init__(self, P, L): ....: RingElement.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyParent(Parent): ....: Element = MyElement sage: class MyMParent(Parent): ....: Element = MyMElement sage: class MyRParent(Parent): ....: Element = MyRElement sage: P = MyParent(category=Rings()) sage: l = P([1,2]) sage: l*l <[1, 2, 1, 2]> sage: PM = MyMParent(category=Rings()) sage: lM = PM([1,2]) sage: lM*lM <[1, 2, 1, 2]> sage: PR = MyRParent(category=Rings()) sage: lR = PR([1,2]) sage: lR*lR <[1, 2, 1, 2]> sage: %timeit l*l The slowest run took 4.68 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 8.77 µs per loop sage: %timeit lM*lM The slowest run took 6.35 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.89 µs per loop sage: %timeit lR*lR The slowest run took 7.06 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.22 µs per loop
Explanation:
 In P, we use Element as starting point. It has no
__mul__
, hence,__mul__
is obtained from some element method of the category of rings.  In PM, we use ModuleElement as starting point.
 It has a
__mul__
method that in vanilla Sage would refuse to carry a ring structure. Hence, the above wouldn't work in vanilla Sage. I have changed the coercion framework so that it does not complain about a ring structure.  Since it has a
__mul__
method, it cannot inherit a ring multiplication from the category element methods. Instead, the parent inherits_get_action_
from category parent methods, as per #18756.
 It has a
 This would be the "classical" way to define a ring structure.
As you can see, of course a specialised cythoned __mul__
method for rings is fastest. The first approach is taken in CombinatorialFreeModule
, if I understand correctly, and is slowest (not by much, but it is). The new approach to use an action of self on itself somehow is in the middle, speedwise.
Before I push my branch, I'll see what happens if I provide Element
with a default __mul__
method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speedup the second (i.e., new) approach.
comment:7 in reply to: ↑ 6 Changed 7 years ago by
Replying to SimonKing:
Before I push my branch, I'll see what happens if I provide
Element
with a default__mul__
method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speedup the second (i.e., new) approach.
To be clear: It would still be the case that CombinatorialFreeModuleElement
would be based on Element
, and it would still be the case that it obtains _mul_
(single underscore) from the category, and it would still be the case that it obtains multiplication from the category. The difference is that it does not obtain the multiplication by inheriting a __mul__
(double underscore) method from the category, but by using a coerce action obtained from the category.
In particular, the existing user code will not change.
comment:8 in reply to: ↑ 6 Changed 7 years ago by
Replying to SimonKing:
Before I push my branch, I'll see what happens if I provide
Element
with a default__mul__
method that simply calls the coercion model. It will of course make the first approach impossible, but I guess it would speedup the second (i.e., new) approach.
This is what happens:
sage: %timeit l*l The slowest run took 6.49 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.71 µs per loop sage: %timeit lM*lM The slowest run took 5.82 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.91 µs per loop sage: %timeit lR*lR The slowest run took 4.27 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.03 µs per loop
In other words, using Element
becomes faster when defining a ring structure than ModuleElement
. Probable reason: The default Element.__mul__
that I am suggesting will immediately use coercion, whereas ModuleElement.__mul__
first tries some shortcut that is not available in my example.
Of course, RingElement.__mul__
is still fastest, as it uses the right shortcut.
Before pushing my branch, I plan to add tests and documentation. The documentation will go to sage.structure.element
and sage.structure.parent
. However, it is my experience that people using sage.combinat
have a tendency to work around coercion (see for example sage.combinat.permutation.Permutation.__mul__
).
Can you suggest a place to put documentation on coercion so that it is actually found by sage.combinat users?
comment:9 Changed 7 years ago by
I had a look at sage.combinat, and it turns out that the situation is not sooooo bad as I thought.
Permutation
needs to be sanitised. It inherits fromElement
. Since here I plan to introduce a defaultElement.__mul__
using coercion model,Permutation.__mul__
needs to be removed, and instead we need an action. It would be easy to implement, and I bet it is faster.Word
does not even inherit fromElement
, but it mimics the elementparent scheme (by providing a cdef_parent
attribute and aparent()
method). It should be possible to determine the result of multiplication by looking at the involved parents. Hence: It would be a good idea to implement something like pushouts for families of words. Thus:
 It would make sense to have a
WordFunctor
construction functor fromSets()
to an appropriate category. The appropriate category could beMonoids()
in the case of finite or infinite words, but could beSets()
in the case of "words avoiding 12" and those things (i.e., the product of two pattern avoiding words is not necessarily pattern avoiding).
Then, one could finally take advantage of Sage's coercion framework for words.
I suggest to sanitise Permutation here, but keep Word for a later ticket.
comment:10 Changed 7 years ago by
PS: Having a pushout construction for permutations would also be nice. Again, it would be for a later ticket.
comment:11 Changed 7 years ago by
PPS: Is it actually Monoids()
in the case of infinite words? I guess one cannot multiply an infinite word with a finite or infinite word. One can only multiply a finite with a finite or infinite word. So, it is "Monoidoids()" (i.e., we have a partial multiplication that is associative when defined and has a unit).
comment:12 Changed 7 years ago by
It will not be easy to make my proposed changes work throughout the sage library. There are zillions of errors in sage.modular (I am sure this is because it was previously worked around coercion...). Well, we will see.
comment:13 Changed 7 years ago by
 Description modified (diff)
comment:14 Changed 7 years ago by
With the branch, that I have still not pushed, I get
sage t src/sage/monoids/free_abelian_monoid.py # 1 doctest failed sage t src/sage/categories/primer.py # 1 doctest failed sage t src/sage/categories/rings.py # 1 doctest failed sage t src/sage/tests/gap_packages.py # 1 doctest failed sage t src/sage/tests/book_schilling_zabrocki_kschur_primer.py # 2 doctests failed sage t src/sage/groups/matrix_gps/group_element.py # 1 doctest failed sage t src/sage/groups/semimonomial_transformations/semimonomial_transformation.pyx # 1 doctest failed sage t src/sage/groups/perm_gps/permgroup_named.py # 2 doctests failed sage t src/sage/sets/finite_set_maps.py # 3 doctests failed sage t src/sage/dev/sagedev.py # 2 doctests failed sage t src/sage/combinat/posets/posets.py # 1 doctest failed sage t src/sage/combinat/sf/sf.py # 3 doctests failed sage t src/sage/combinat/sf/new_kschur.py # 10 doctests failed sage t src/sage/schemes/toric/morphism.py # 3 doctests failed sage t src/sage/geometry/fan_morphism.py # 6 doctests failed sage t src/sage/geometry/hyperplane_arrangement/hyperplane.py # 1 doctest failed
Not so bad, actually...
comment:15 Changed 7 years ago by
 Branch set to u/SimonKing/allow_actions_of_parent_on_itself
comment:16 Changed 7 years ago by
 Commit set to b57a6e35380933f429215a351fb2ade01c9d29c9
 Status changed from new to needs_review
I have changed the logic in the bin_op()
method of the coercion model, so that it is safer against infinite recursion. The error messages in most cases do not just say that the operation "+" is unsupported, but say that a common parent has not been found. Changing the expected error messages is the hardest part of the latest commit.
Most important change: The coercion model now makes actual use of single underscore methods!
You may be surprised by the implied statement that previously the coercion model did not use them. In fact, it didn't. Up to now, the single underscore methods have only been used as shortcuts in RingElement.__mul__
and friends. I have changed it, so that the shortcut still works, but additionally the coercion model explicitly calls the single underscore methods (when available) if both operands belong to the same parent.
comment:17 Changed 7 years ago by
 Commit changed from b57a6e35380933f429215a351fb2ade01c9d29c9 to d71a456dbd312980490f17d39ed97d3df6ccdcb9
Branch pushed to git repo; I updated commit sha1. New commits:
d71a456  forgotten changes of expected error messages in tests

comment:18 Changed 7 years ago by
Here are some timings. The code used:
sage: from sage.structure.element import Element, ModuleElement, RingElement sage: class MyElement(Element): ....: def __init__(self, P, L): ....: Element.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyMElement(ModuleElement): ....: def __init__(self, P, L): ....: ModuleElement.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyRElement(RingElement): ....: def __init__(self, P, L): ....: RingElement.__init__(self, P) ....: self.l = L ....: def _repr_(self): ....: return "<{}>".format(self.l) ....: def _add_(self, other): ....: return self.parent()(zip(self.l, other.l)) ....: def _mul_(self, other): ....: return self.parent()(self.l+other.l) sage: class MyParent(Parent): ....: Element = MyElement sage: class MyMParent(Parent): ....: Element = MyMElement sage: class MyRParent(Parent): ....: Element = MyRElement
Here are different settings, where in each case I also compare with vanilla sage6.8.beta5.
 Action obtained from the category:
sage: P = MyParent(category=Rings()) sage: l = P([1,2]) sage: %timeit l*l The slowest run took 64.43 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.82 µs per loop # 8.87 µs in beta5 sage: %timeit l+l The slowest run took 24.53 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 8.44 µs per loop # 9.49 µs in beta5
 The coercion model using single underscore methods. Both examples won't work in beta5
sage: P = MyParent(category=Sets()) sage: l = P([1,2]) sage: %timeit l*l The slowest run took 15.44 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 10.3 µs per loop sage: %timeit l+l The slowest run took 11.54 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 10.7 µs per loop
 ModuleElement using a shortcut for "+" and not complaining about a multiplication action obtained from the category:
sage: P = MyMParent(category=Rings()) sage: l = P([1,2]) sage: %timeit l*l The slowest run took 108.72 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.88 µs per loop # won't work in beta5 sage: %timeit l+l The slowest run took 5.98 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 8.05 µs per loop # 8.01 µs in beta5 (of course no significant change)
 ModuleElement using a shortcut for "+" and allowing the coercion model to use single underscore methods for "*":
sage: P = MyMParent(category=Sets()) sage: l = P([1,2]) sage: %timeit l*l The slowest run took 14.45 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 10.7 µs per loop # won't work in beta5 sage: %timeit l+l The slowest run took 4.25 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 8.69 µs per loop # 8.02 µs in beta5. Should actually be the same time! This branch hasn't changed!
 RingElement using shortcuts for "+" and for "*". Of course there are no significant changes wrt. beta5, as the shortcut didn't change.
sage: P = MyRParent(category=Sets()) sage: l = P([1,2]) sage: %timeit l*l The slowest run took 4.75 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 7.12 µs per loop # 7.02 µs with beta5 sage: %timeit l+l The slowest run took 4.58 times longer than the fastest. This could mean that an intermediate result is being cached 100000 loops, best of 3: 8.07 µs per loop # 7.98 µs with beta5
comment:19 followup: ↓ 21 Changed 6 years ago by
 Status changed from needs_review to needs_work
Hello,
There are some clear troubles with the patchbot... some elements do not know how to multiply anymore.
Vincent
comment:20 Changed 6 years ago by
Also, the doctest coverage is not 100%.
comment:21 in reply to: ↑ 19 Changed 6 years ago by
Replying to vdelecroix:
There are some clear troubles with the patchbot... some elements do not know how to multiply anymore.
In two of the failing tests, it is just the error message that has changed. In the third, it could be that something needs to be done.
comment:22 Changed 5 years ago by
If I recall correctly, some people have worked on similar issues. But I am not sure about the ticket numbers. Hence, is what I propose here done already?
See comment 24 at #18756 for why I think we should have a dependency.