#15289 closed enhancement (fixed)
Implement indexed monoids
Reported by:  tscrim  Owned by:  sagecombinat 

Priority:  major  Milestone:  sage6.3 
Component:  algebra  Keywords:  days54 
Cc:  sagecombinat, nthiery, mshimo, SimonKing  Merged in:  
Authors:  Travis Scrimshaw  Reviewers:  Nicolas M. Thiéry 
Report Upstream:  N/A  Work issues:  
Branch:  69ec7b2 (Commits)  Commit:  
Dependencies:  #15309, #15169, #16349  Stopgaps: 
Description (last modified by )
Implements free (abelian) monoids whose generators are indexed by an arbitrary set. This also moves common code from CombinatorialFreeModule
into a new class sage.misc.indexed_generators.IndexedGenerators
. With this we can now create (noncommutative) polynomials whose generators are given by a combinatorial object.
Also implements a very crude and basic version for groups.
Attachments (1)
Change History (69)
comment:1 Changed 6 years ago by
 Status changed from new to needs_review
comment:2 Changed 6 years ago by
Hi Travis,
Thanks for working on this feature! I'll try to look at it, but that won't be immediately. I would have thought we already had a ticket about that, but I might be wrong. For the record, here is a link to a discussion we had (a long time ago) about such features:
Thanks again!
Cheers,
Nicolas
comment:3 Changed 6 years ago by
 Description modified (diff)
Hey Nicolas,
I believe there is a ticket about making free abelian groups as ZZ
modules, and another one about converting between additive and multiplicative groups. However they currently don't apply to CombinatorialFreeModule
, and none of the tickets on CombinatorialFreeModule
would apply here as far as I remember.
Here's a new version which gives a groups version so we can do Laurent polynomials. This is not are fancy as the discussion would like, but it serves my purposes for now.
Best,
Travis
comment:4 Changed 6 years ago by
Here's with some more functionality additions. I did make one major change and made the iterator return (generator, exp)
, as opposed to (index, exp)
and similar to how FreeMonoid
works.
Frequently I'm finding myself calling _sorted_items()
, but I'm needing to manipulate the indices of the generators. I'm wondering if we should make it into a public method (perhaps with a better name since there is no true sorting occurring when it is not free).
Changed 6 years ago by
comment:6 Changed 6 years ago by
 Dependencies changed from #15309 to #15309 #15169
comment:7 Changed 6 years ago by
 Branch set to public/monoids/15289indexed
 Commit set to c1b5afea143f80ce6d68a4386ed6b410f8fcbb17
Added git version.
New commits:
c1b5afe  #15289: Implemented indexed monoids and groups. 
6fd33b2  #15169: Fix FreeAlgebra? element constructor from a base field. 
comment:8 Changed 6 years ago by
 Keywords days54 added
comment:9 Changed 6 years ago by
 Commit changed from c1b5afea143f80ce6d68a4386ed6b410f8fcbb17 to 9dca526f5ab91f7d2777ba4f4e945a869b169bb9
comment:10 Changed 6 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:11 Changed 6 years ago by
 Commit changed from 9dca526f5ab91f7d2777ba4f4e945a869b169bb9 to 991953a60536c9532590270183cfa100d3577b39
Branch pushed to git repo; I updated commit sha1. New commits:
545a8df  Merge branch 'develop' into public/monoids/15289indexed

2975c87  Merge branch 'develop' into public/monoids/15289indexed

4002b0d  Merge branch 'develop' into public/monoids/15289indexed

9e9b769  Merge branch 'develop' into public/monoids/15289indexed

a278afa  Added cardinality methods.

f681606  Added cardinality to free abelian monoid for consistancy.

3a0e50b  Merge branch 'develop' into public/monoids/15289indexed

d4606cc  Added more robustness to element creation.

991953a  Merge branch 'develop' into public/monoids/15289indexed

comment:12 Changed 6 years ago by
 Commit changed from 991953a60536c9532590270183cfa100d3577b39 to 163df6e7f6b29e53c0844995389f52c198cffcc1
comment:13 Changed 6 years ago by
 Commit changed from 163df6e7f6b29e53c0844995389f52c198cffcc1 to 8db8e0a07605c801a9a9974e043312061ee375c1
Branch pushed to git repo; I updated commit sha1. New commits:
8db8e0a  Changed _an_element_ to indexed_monoid.py.

comment:14 followup: ↓ 21 Changed 6 years ago by
Hey Nicolas,
From your comments on #15726, I've made the appropriate changes here.
 All
Indexed*
now goes throughFree*
, but as a special case, I haveIndexedFreeAbelianGroup
asFreeGroup(index_set=X, abelian=True)
. Should we do the same forFreeMonoid
?
 I want to leave
__pow__
alone since they are more specialized for the data structures.
 The
__contains__
, are you suggesting putting it intoParent
? If so, that might be a can of worms and should be done on another ticket.
 I'd like to keep
IndexedFreeAbelianGroup
as multiplicative since I want to use them as a basis indexing set for polynomials.
 Similarly, the comparisons are using lex ordering, so it gives a nice default order on terms when modeling polynomial rings with indexed generators.
Thank you for looking at this (and #15726). As always, I appreciate your wisdom and insight.
Best,
Travis
New commits:
8db8e0a  Changed _an_element_ to indexed_monoid.py.

comment:15 Changed 6 years ago by
 Cc mshimo added
comment:16 Changed 6 years ago by
 Commit changed from 8db8e0a07605c801a9a9974e043312061ee375c1 to 03057a45e8ea5db1e95622f5e889915be2e8d024
Branch pushed to git repo; I updated commit sha1. New commits:
bd82ed8  Merge branch 'develop' into public/monoids/15289indexed

760c939  Merge branch 'public/monoids/15289indexed' of trac.sagemath.org:sage into public/monoids/15289indexed

03057a4  Merge branch 'develop' into public/monoids/15289indexed

comment:17 Changed 6 years ago by
 Commit changed from 03057a45e8ea5db1e95622f5e889915be2e8d024 to a2996e0772eb50f4f973b04c2a85c8bb33cf3aa6
Branch pushed to git repo; I updated commit sha1. New commits:
a2996e0  Merge branch 'develop' into public/monoids/15289indexed

comment:18 Changed 6 years ago by
 Commit changed from a2996e0772eb50f4f973b04c2a85c8bb33cf3aa6 to 49068b2389e4eae6d207288d14be466d95f84966
comment:19 Changed 6 years ago by
 Commit changed from 49068b2389e4eae6d207288d14be466d95f84966 to 6875cfbae0f2fd90475e4ae1170fcf2444db03fb
Branch pushed to git repo; I updated commit sha1. New commits:
6875cfb  Merge branch 'develop' into public/monoids/15289indexed

comment:20 Changed 6 years ago by
 Commit changed from 6875cfbae0f2fd90475e4ae1170fcf2444db03fb to 1818a3efc4e4b28a005a833a05a66e7765280966
Branch pushed to git repo; I updated commit sha1. New commits:
1818a3e  Merge branch 'develop' into public/monoids/15289indexed

comment:21 in reply to: ↑ 14 ; followup: ↓ 22 Changed 6 years ago by
Replying to tscrim:
From your comments on #15726, I've made the appropriate changes here.
Argl, two months already ... sorry for lagging behind so much. I know how painful it is to get suggestions late in the process when everything is in a clean state ...
 All
Indexed*
now goes throughFree*
,
Nice! Thanks!
but as a special case, I have
IndexedFreeAbelianGroup
asFreeGroup(index_set=X, abelian=True)
. Should we do the same forFreeMonoid
?
It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sagedevel?
By the way, for this ticket or later, I have been desiring for a long time to have some systematic idiom like:
sage: Groups().free(index_set={...}) sage: CommutativeAdditiveGroups().free(index_set={...}) sage: Algebras(QQ).free(index_set={...})
Then we could remove all the Free* from the global name space.
 The
__contains__
, are you suggesting putting it intoParent
?If so, that might be a can of worms and should be done on another ticket.
I was thinking of putting it in the categories, but you are right,
given the mro Parent.__contains__
will take over.
In fact do you have a specific reason to override
Parent.__contains__
? Granted, the policy implemented in
Parent.__contains__
is unsatisfactory (it's doing too much stuff to
my taste, in particular stuff that can potentially be costly). And
fixing it could indeed be a can of worm. On the other hand, having
many parents define their own containment policy is unsatisfactory as
well.
 I'd like to keep
IndexedFreeAbelianGroup
as multiplicative since I want to use them as a basis indexing set for polynomials.
It's customary as well to index polynomials by exponent vectors in the
additive group NN^n
. Actually I would tend to prefer it. But that's
probably something to ask on sagedevel.
 Similarly, the comparisons are using lex ordering, so it gives a nice default order on terms when modeling polynomial rings with indexed generators.
As long as it's easy to customize it, I guess that's fine.
In term of code review, what should I look at at this point? Were some commits already reviewed, or should I just look at the diff w.r.t develop?
Cheers,
Nicolas
comment:22 in reply to: ↑ 21 ; followup: ↓ 23 Changed 6 years ago by
Replying to nthiery:
but as a special case, I have
IndexedFreeAbelianGroup
asFreeGroup(index_set=X, abelian=True)
. Should we do the same forFreeMonoid
?It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sagedevel?
I will do so.
By the way, for this ticket or later, I have been desiring for a long time to have some systematic idiom like:
sage: Groups().free(index_set={...}) sage: CommutativeAdditiveGroups().free(index_set={...}) sage: Algebras(QQ).free(index_set={...})Then we could remove all the Free* from the global name space.
I'll also ask about this on sagedevel, and will start the process here if there's no resistance.
I was thinking of putting it in the categories, but you are right, given the mro
Parent.__contains__
will take over.In fact do you have a specific reason to override
Parent.__contains__
? Granted, the policy implemented inParent.__contains__
is unsatisfactory (it's doing too much stuff to my taste, in particular stuff that can potentially be costly). And fixing it could indeed be a can of worm. On the other hand, having many parents define their own containment policy is unsatisfactory as well.
I don't have a good reason (the annoyance is the self(x)
calls the coercion framework and makes it so we can't register any coercions thereafter, but that's not a problem in how I'm using these), so I'm fine with scraping it.
 I'd like to keep
IndexedFreeAbelianGroup
as multiplicative since I want to use them as a basis indexing set for polynomials.It's customary as well to index polynomials by exponent vectors in the additive group
NN^n
. Actually I would tend to prefer it. But that's probably something to ask on sagedevel.
I'm not quite sure what you're suggesting here.
As long as it's easy to customize it, I guess that's fine.
Yes it is by passing a parameter (monomial_cmp
, which should be renamed to generator_cmp
) with a cmp function.
In term of code review, what should I look at at this point? Were some commits already reviewed, or should I just look at the diff w.r.t develop?
You're the only one who's really looked at this code, so a diff w.r.t. develop.
Thank you!
comment:23 in reply to: ↑ 22 Changed 6 years ago by
Replying to tscrim:
 I'd like to keep
IndexedFreeAbelianGroup
as multiplicative since I want to use them as a basis indexing set for polynomials.It's customary as well to index polynomials by exponent vectors in the additive group
NN^n
. Actually I would tend to prefer it. But that's probably something to ask on sagedevel.I'm not quite sure what you're suggesting here.
I guess I mean that I lean toward IndexedFreeAbelianGroup? being additive. But that's definitely debatable. Opinion anyone?
Btw, for consistency with the naming of hte categories maybe a better name for the class could be IndexedFreeCommutativeGroup? (or IndexedFreeCommutativeAdditiveGroup? if we opt for additive).
You're the only one who's really looked at this code, so a diff w.r.t. develop.
Ok!
comment:24 Changed 6 years ago by
sagedevel thread: https://groups.google.com/forum/#!topic/sagedevel/yAvIvWxNgXE
comment:25 Changed 6 years ago by
 Commit changed from 1818a3efc4e4b28a005a833a05a66e7765280966 to 23301a86c56549062b6441c7b2ac6336da0d1001
Branch pushed to git repo; I updated commit sha1. New commits:
1c1b4eb  Changed monomial_cmp to generator_cmp and added free (static)method to monoids and groups category.

47b5be7  Removed __contains__ and fix monomial_cmp in indexed_monoid.py

4097a8c  Merge branch 'develop' into public/monoids/15289indexed

23301a8  Misc fixes and tweaks.

comment:26 Changed 6 years ago by
Hey Nicolas,
I've changed monomial_cmp
to generator_cmp
and made some other fixes I encountered along the way (after merging in 6.2.rc0
). I've started adding in our idiom of Category.free
for groups and monoids, the rest will be done in #16218 (along with possible deprecations). Back to ready for review.
Thanks,
Travis
comment:27 Changed 6 years ago by
 Commit changed from 23301a86c56549062b6441c7b2ac6336da0d1001 to 81eede490c2d46a5875145b5ba1138e08605ffdd
Branch pushed to git repo; I updated commit sha1. New commits:
81eede4  15289: Proofreading

comment:28 Changed 6 years ago by
Hi Travis,
Finally working on the review! Besides the little tidying I just committed here are some comments for the files I have been checking so far:
 «if specified then the optional keyword
abelian
can be used»
And not otherwise?
 Rename indexed_group.py to indexed_free_group.py
 Define group_generators rather than gens (or at the minimum define group_generators as an alias to gens) and use it whenever possible.
 Element.pow: better use standard binary powering:
sage: pow = x.__class__.__pow__ sage: pow_generic = Monoids().element_class.__pow__ sage: pow_generic(x,1000) == pow(x,1000) True sage: %timeit pow(x,1) 1000000 loops, best of 3: 827 ns per loop sage: %timeit pow_generic(x,1) 1000000 loops, best of 3: 521 ns per loop sage: %timeit pow(x,1) 100000 loops, best of 3: 6.45 µs per loop sage: %timeit pow_generic(x,1) 100000 loops, best of 3: 6.85 µs per loop sage: %timeit pow(x,2) 100000 loops, best of 3: 11.5 µs per loop sage: %timeit pow_generic(x,2) 100000 loops, best of 3: 6.07 µs per loop sage: %timeit pow(x,50) 1000 loops, best of 3: 844 µs per loop sage: %timeit pow_generic(x,50) 10000 loops, best of 3: 80.2 µs per loop sage: %timeit pow(x,1000) 10 loops, best of 3: 181 ms per loop sage: %timeit pow_generic(x,1000) 1000 loops, best of 3: 1.04 ms per loop
 len, ... all the calls to sorted_items suggest that some sorting is involved when this is not the case.
 order, rank, is_finite are identical in all the free (abelian) monoids/groups. Could we avoid the duplication?
 Element._mul_ could use sage.combinat.dict_addition
More later tonight!
Cheers,
Nicolas
comment:29 Changed 6 years ago by
 Commit changed from 81eede490c2d46a5875145b5ba1138e08605ffdd to 7d27baacb4721ee041162cb280b7ee48d2b0da34
Branch pushed to git repo; I updated commit sha1. New commits:
7d27baa  #15289: misc minor improvements to the doc

comment:30 Changed 6 years ago by
Back to work!
I have been through the whole diff. Thanks for this big chunk of work! Some more comments:
 Move to sage/structure
 Detailed description of what the options do: this is probably best done in the EXAMPLES section, with illustrations.
 Avoid the duplication in the documentation for the print options, (in CombinatorialFreeModule? and IndexedGenerators?). I probably would put it in IndexedGenerators?.
 Side note: since the
cmp
function is phased out by Python 3, we will have to start thinking about what would be the most natural way to specify a total order in the context of Python 3.
FreeAbelianMonoid? / FreeMonoid?:
 Now or later: for consistency, could we use a class with UniqueRepresentation? and classcall instead of a factory function?
If you decide for later, please open a ticket. Same for the items below.
 Now or later:
__repr__
>_repr_
,__call__
>_element_constructor_
. The custom__contains__
might not be needed.
 Now or later: initialize the category
 is_FreeAbelianMonoid will return False for an IndexedFreeAbelianMonoid?. Do we care?
 cardinality should be 1 for n=0. Same for all the following cardinality methods later in the diff
 TODO: same docstring changes as in my commit (e.g. for the description of 'abelian')
 The description is useful; I now see the point of
sorted_items
. We should search for a better name though. In particular the description "Return the items (i.e terms) ofself
, sorted for printing." is misleading, as it's not only used for printing.
 Same remarks as for IndexedGroups?.
 cancel: shouldn't this be ?
 Special cases for converting 1 or testing equality with 1: don't bother for new monoids. That's an ugly habit in Sage and we should steer away of it.
 In _element_constructor_:
 The following line is not needed; this is already taken care of by
__call__
:if isinstance(x, IndexedFreeAbelianMonoidElement) and x.parent() is self: return x
 The following line is not needed; this is already taken care of by
 Construction of the generator indexed by
i
withF(i)
: I'd rather not enable this unless users come crying loud for it. F.gen(i) is fine, and it's just an endless can of worm since, as you point out later, it can be ambiguous. Besides containment testing can be expensive.
 Add an example in
_element_constructor_
illustrating the construction from a dictionary.
 Don't we want to always call dict on
x
so as to avoid a reference effect in case of a dict, throw appropriate errors if it can't be made into a dict, and accept, e.g. iterables?
comment:31 Changed 6 years ago by
Remaining two questions about the user interface.
Currently, the arguments passed to construct a free * are:
def free(n=None, names='x', index_set=None, ...):
Here is a proposal for a variant:
def free(index_set=None, names=None, prefix='x', ...)
where:
index_set=n
is a short hand forindex_set=[0,...,n1]
(or the equivalentIntegerRange
?)index_set='x,y,z'
is a short hand fornames='x,y,z'
names
can either be a string like'x,y,z'
or a list or iterables ofnames
.
Advantages:
 This supports simultaneously
C.free(I)
,C.free('x,y,z')
, andC.free(3)
, which are the most common use cases.
 This still supports
F.<x,y,z> = C.free()
.
 This is consistent with both
FreeModule(QQ, 3)
andCombinatorialFreeModule(QQ, I)
, as well as with the upcomingFreeModule(QQ,I)
which will callIndexedFreeModule(QQ, I)
.
 There is a clear distinction between the prefix and the names.
Otherwise
names='x'
is ambiguous: a singleton list of names, or a prefix?
Second point: I am hesitant about the abelian
argument. With #10963,
I definitely would prefer:
Groups().Commutative().free()
to
Groups().free(abelian=True)
Maybe, as a more consistent temporary measure, we could use:
Groups().free(commutative=True)
Once the above is settled, I guess this ticket is good to go!
Cheers,
Nicolas
comment:32 Changed 6 years ago by
Btw, I am wondering whether there would be a way to obtain, with minimum duplication of code, the additive versions? After all, it's just about the names of few methods (_add_
vs _mul_
, intmul
vs _pow_
, _neg_
vs __invert__
).
comment:33 Changed 6 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:34 Changed 6 years ago by
 Status changed from needs_review to needs_work
patchbot:
sage t long src/sage/structure/sage_object.pyx # 1 doctest failed sage t long src/sage/misc/indexed_generators.py # 1 doctest failed
comment:35 Changed 6 years ago by
 Commit changed from 7d27baacb4721ee041162cb280b7ee48d2b0da34 to 1ff1a0483f5e61959a432371b701f593a5dee599
Branch pushed to git repo; I updated commit sha1. New commits:
6589a09  Merge branch 'develop' into public/monoids/15289indexed

27cbf34  Merge branch 'develop' into public/monoids/15289indexed

3f667f4  Merge branch 'public/monoids/15289indexed' of trac.sagemath.org:sage into public/monoids/15289indexed

90f339f  Doing some of the changes Nicolas requested.

fabaaf1  Merge branch 'develop' into public/monoids/15289indexed

4cca67e  Some more fixes; still not done yet.

0231f73  Fixed the categories interface.

0d86682  Fixed all doctests except for the pickling.

db57ef3  More fixes for cardinality methods.

1ff1a04  Some whitespace fixes.

comment:36 followups: ↓ 37 ↓ 44 Changed 6 years ago by
 Cc SimonKing added
Fixed everything mentioned above except I've run into a major pickling issue with UniqueFactory
(which is why I've cced Simon).
There is some precedence for creating a generator from an index:
sage: C = CombinatorialFree Module(ZZ, ['a','b','c']) sage: C('a') B['a']
So I'd like to leave that in for now. However I made things like F(1)
only return F[1]
.
I changed the input for Monoids().free(...)
but I left FreeMonoid(...)
as I had it before because I don't want to deal with deprecations there in this ticket (this is #16330). I'll do the cleanup of the factory functions in the followup #16329.
I'm not doing anything to FreeMonoid
or FreeAbelianMonoid
other than redirecting input, so I'm not going to make these changes here:
 Now or later:
__repr__ > _repr_
,__call__ > _element_constructor_
. The custom__contains__
might not be needed. Now or later: initialize the category
We could probably also fit that in #16329 or another followup.
Simon, so I've changed the UniqueFactory
object FreeMonoid
to a new factory function since it returns a class which I've designed as a UniqueRepresentation
. However unpickling old FreeMonoid
objects fails because of the unpickling mechanism of UniqueFactory
redirects to generic_factory_unpickle()
and has FreeMonoid
from the global namespace as the first object. It is expecting it to be a UniqueFactory
instance, so it errors out here. Furthermore because of the structure of the pickle, I'm unable to use register_unpickle_override
or see anyway to redirect that specific pickle without changing the behavior of generic_factory_unpickle()
.
I'm thinking the best thing to do is to change generic_factory_unpickle()
to accept a general object as input and if the first input is no longer a UniqueFactory
, then call it with the arguments given as part of the pickle. Another option I see is to override UniqueFactory.__call__
, but I really don't want to do that. The last option I see, and I absolutely don't like this, is to make my new factory function into a different name temporarily (or deprecate FreeMonoid
construction altogether). Any ideas?
I'm also thinking we should change this behavior so we don't keep running into this problem.
comment:37 in reply to: ↑ 36 Changed 6 years ago by
Replying to tscrim:
Fixed everything mentioned above except I've run into a major pickling issue with
UniqueFactory
(which is why I've cced Simon).
Cool, thanks!
There is some precedence for creating a generator from an index:
sage: C = CombinatorialFree Module(ZZ, ['a','b','c']) sage: C('a') B['a']So I'd like to leave that in for now.
Precisely: we have made that mistake once, and been bitten by it. So I'd rather not redo it!
I changed the input for
Monoids().free(...)
but I leftFreeMonoid(...)
as I had it before because I don't want to deal with deprecations there in this ticket (this is #16330). I'll do the cleanup of the factory functions in the followup #16329.
Fair enough.
I'm not doing anything to
FreeMonoid
orFreeAbelianMonoid
other than redirecting input, so I'm not going to make these changes here:
 Now or later:
__repr__ > _repr_
,__call__ > _element_constructor_
. The custom__contains__
might not be needed. Now or later: initialize the category
We could probably also fit that in #16329 or another followup.
Ok.
Simon, so I've changed the
UniqueFactory
objectFreeMonoid
to a new factory function since it returns a class which I've designed as aUniqueRepresentation
. However unpickling oldFreeMonoid
objects fails because of the unpickling mechanism ofUniqueFactory
redirects togeneric_factory_unpickle()
and hasFreeMonoid
from the global namespace as the first object. It is expecting it to be aUniqueFactory
instance, so it errors out here. Furthermore because of the structure of the pickle, I'm unable to useregister_unpickle_override
or see anyway to redirect that specific pickle without changing the behavior ofgeneric_factory_unpickle()
.I'm thinking the best thing to do is to change
generic_factory_unpickle()
to accept a general object as input and if the first input is no longer aUniqueFactory
, then call it with the arguments given as part of the pickle. Another option I see is to overrideUniqueFactory.__call__
, but I really don't want to do that. The last option I see, and I absolutely don't like this, is to make my new factory function into a different name temporarily (or deprecateFreeMonoid
construction altogether). Any ideas?I'm also thinking we should change this behavior so we don't keep running into this problem.
Maybe, at least as a temporary solution, the FreeMonoid? object from the global namespace could remain a trivial factory function delegating to a class, also called FreeMonoid?, but in its own module?
Cheers,
Nicolas
comment:38 followup: ↓ 39 Changed 6 years ago by
The FreeMonoid
in the global namespace must be the UniqueFactory
instance for the old pickles to work, irregardless of which module or the name of the class. That's the big problem. Or are you suggesting to just leave FreeMonoid
alone (or perhaps give it some warnings and redirections when given other types of input)?
There is one other thing I thought of today, to implement a custom unpickle override for UniqueFactory
. I'm thinking this might be the best way to work around this (and could easily create this on a separate ticket). Thoughts?
comment:39 in reply to: ↑ 38 ; followup: ↓ 40 Changed 6 years ago by
Replying to tscrim:
The
FreeMonoid
in the global namespace must be theUniqueFactory
instance for the old pickles to work,
Yes. But this UniqueFactory? instance can probably be a fake one and just act as a delegator
to whichever new class now implements FreeMonoid
.
There is one other thing I thought of today, to implement a custom unpickle override for
UniqueFactory
. I'm thinking this might be the best way to work around this (and could easily create this on a separate ticket). Thoughts?
I am not sure I see what you mean, but I can live with that if someone else answers :)
comment:40 in reply to: ↑ 39 Changed 6 years ago by
Replying to nthiery:
Replying to tscrim:
The
FreeMonoid
in the global namespace must be theUniqueFactory
instance for the old pickles to work,Yes. But this UniqueFactory? instance can probably be a fake one and just act as a delegator to whichever new class now implements
FreeMonoid
.
So do you mean doing something like this:
class DummyFactory(UniqueFactory): def __call__(self, *args, **kwds): return factory_function(*args, **kwds) def get_object(self, the, ..., args): return OriginalFactoryInstance.get_object(the, ..., args)
and DummyFactory
would become the object in the global namespace?
comment:41 Changed 6 years ago by
Yeah. Not sure it's a good idea though. Do as you feel is right.
comment:42 Changed 6 years ago by
 Dependencies changed from #15309 #15169 to #15309, #15169
comment:43 Changed 6 years ago by
In order to checkout this ticket, I had to fix the list of dependencies (which is supposed to be commaseparated).
comment:44 in reply to: ↑ 36 Changed 6 years ago by
Replying to tscrim:
Simon, so I've changed the
UniqueFactory
objectFreeMonoid
to a new factory function since it returns a class which I've designed as aUniqueRepresentation
. However unpickling oldFreeMonoid
objects fails because of the unpickling mechanism ofUniqueFactory
redirects togeneric_factory_unpickle()
and hasFreeMonoid
from the global namespace as the first object.
First thing I wonder: Why is that statically typed? Just to shave off a little calling overhead?
It is expecting it to be a
UniqueFactory
instance, so it errors out here. Furthermore because of the structure of the pickle, I'm unable to useregister_unpickle_override
or see anyway to redirect that specific pickle without changing the behavior ofgeneric_factory_unpickle()
.
I don't really understand how register_unpickle_override
is working. It seems that it can only work if unpickle_global
is involvedand it is not clear to me if this is involved everywhere or only if there is no __reduce__
method around.
I'm thinking the best thing to do is to change
generic_factory_unpickle()
to accept a general object as input and if the first input is no longer aUniqueFactory
, then call it with the arguments given as part of the pickle.
Makes sense to me. And I even think the following idiom would not be slower in terms of calling overhead than the current implementation:
def generic_factory_unpickle(factory, *args): cdef UniqueFactory F try: F = factory except TypeError: return factory(*args[1:]) return F.get_object(*args)
Note that I wrote factory(*args[1:])
, since the first argument is the version information. So, either we need to shave it off here, or the new class (or function) replacing the old factory is required to take care of this.
I'm also thinking we should change this behavior so we don't keep running into this problem.
I think with my suggestion above, unpickling of using factory would work as quickly as it used to, and it would relatively easily allow to replace the factory by something else (provided that this "something else" takes care of the argument mangling and the version information that is involved in the factory pickle).
comment:45 Changed 6 years ago by
PS: The documentation breaks. After repeated attempts of make docclean
and make
, I keep getting
OSError: [misc ] /home/king/Sage/git/sage/src/doc/en/reference/misc/sage/misc/indexed_generators.rst:11: WARNING: autodoc can't import/find module 'sage.misc.indexed_generators', it reported error: "No module named indexed_generators", please check your spelling and sys.path
comment:46 Changed 6 years ago by
 Dependencies changed from #15309, #15169 to #15309, #15169, #16349
This is now #16349. Try sage syncbuild
(there's probably the old file in the lib build folder which is getting picked up).
comment:47 Changed 6 years ago by
 Commit changed from 1ff1a0483f5e61959a432371b701f593a5dee599 to bf161359d4c73aa81aa60cb77ea1d4a7a2c0473d
Branch pushed to git repo; I updated commit sha1. New commits:
d570dda  Merge branch 'develop' into public/monoids/15289indexed

321a9e4  Unpickling when replacing an old UniqueFactory by something new

187d1aa  Fix arguments passed to the constructor that replaces an old UniqueFactory

83c79ef  Merge branch 'u/SimonKing/ticket/16349' of trac.sagemath.org:sage into public/pickling/unique_factories16349

2df09ed  Implemented an unpickle override for UniqueFactory.

c7646c1  Fixed doctest caused by me forgetting the registration is global.

d0c9eb3  Merge branch 'public/pickling/unique_factories16349' into public/monoids/15289indexed

bf16135  Fixed pickling issues and now using index_set as 1st arg to Free*Monoid().

comment:48 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:49 Changed 6 years ago by
 Commit changed from bf161359d4c73aa81aa60cb77ea1d4a7a2c0473d to 164fb4beee6ce00064da5c59591cc5ecc94ef095
Branch pushed to git repo; I updated commit sha1. New commits:
164fb4b  Fixed documentation.

comment:50 Changed 6 years ago by
Sorry that actually is my fault, I forgot to move the file over in the doc index.rst
files.
comment:51 Changed 6 years ago by
 Status changed from needs_review to needs_work
AttributeError: 'FreeAbelianMonoid_class' object has no attribute 'monoid_generators' ********************************************************************** 6 items had failures: 3 of 7 in sage.monoids.indexed_free_monoid.IndexedFreeMonoidElement.__init__ 1 of 8 in sage.monoids.indexed_free_monoid.IndexedMonoid.__classcall__ 1 of 9 in sage.monoids.indexed_free_monoid.IndexedMonoid.__init__ 1 of 5 in sage.monoids.indexed_free_monoid.IndexedMonoid._an_element_ 1 of 5 in sage.monoids.indexed_free_monoid.IndexedMonoid.monoid_generators 3 of 11 in sage.monoids.indexed_free_monoid.IndexedMonoidElement.__init__ [213 tests, 10 failures, 0.29 s]  sage t src/sage/monoids/indexed_free_monoid.py # 10 doctests failed
comment:52 Changed 6 years ago by
 Commit changed from 164fb4beee6ce00064da5c59591cc5ecc94ef095 to ecdc00fd1e7edf706d8acfadc6325bed93e37843
Branch pushed to git repo; I updated commit sha1. New commits:
ecdc00f  Fixed doctests because of different processing of input.

comment:53 Changed 6 years ago by
 Status changed from needs_work to needs_review
comment:54 Changed 6 years ago by
 Commit changed from ecdc00fd1e7edf706d8acfadc6325bed93e37843 to 909196eb2cd8311897437f7212c6470cba80ee84
Branch pushed to git repo; I updated commit sha1. New commits:
909196e  Merge branch 'develop' into public/monoids/15289indexed

comment:55 followup: ↓ 57 Changed 6 years ago by
Hi Travis,
Sorry for being slow once again. Unless I missed it, you haven't commented on my suggestions for:
 Using
dict_addition
whenever meaningful  Implementing
Groups().Commutative().free()
rather thanGroups().free(commutative=True)
now that #10963 is in (I can do that if you want)  Putting index_set as first argument to the
free
methods to make the following work properly:sage: C.free([1,2,3]) Free monoid indexed by None
By the way, with no argument there should either be some reasonable default, or an error:sage: C.free() Free monoid indexed by None
 Construction of the generators by
F(i)
(see 37).  32
Cheers,
Nicolas
comment:56 Changed 6 years ago by
 Commit changed from 909196eb2cd8311897437f7212c6470cba80ee84 to 73a4e48f890a31cafbf4e8d176ac69c3b3171cbb
comment:57 in reply to: ↑ 55 Changed 6 years ago by
Hey Nicolas,
Thanks for getting back to this ticket. I know how hard it can be to find time.
Replying to nthiery:
 Using
dict_addition
whenever meaningful
Done.
 Implementing
Groups().Commutative().free()
rather thanGroups().free(commutative=True)
now that #10963 is in (I can do that if you want)
Done (now that #10963 is in; big yay!). I also cleaned up some of the logic and made the *.free()
always return the indexed monoid/group except for Groups.free(n, names)
since IMO (perhaps notsohumble) the indexed version is better since it's a proper parent and more general. I can revert this if desired.
 Putting index_set as first argument to the
free
methods to make the following work properly:sage: C.free([1,2,3]) Free monoid indexed by None
I had missed this somehow for monoids (but I had done it for groups).
By the way, with no argument there should either be some reasonable default, or an error:
sage: C.free() Free monoid indexed by None
Now it raises an error.
 Construction of the generators by
F(i)
(see 37).
I've made it a forbidden construction.
I think we should just use CombinatorialFreeModule
over ZZ
for this, or do you think it would be too heavyhanded? However I don't think it would be difficult to do (following your comment).
Best,
Travis
comment:58 Changed 5 years ago by
 Commit changed from 73a4e48f890a31cafbf4e8d176ac69c3b3171cbb to d4fe805fa2a815b902d8aa3809d4be9d362af7c6
comment:59 Changed 5 years ago by
 Commit changed from d4fe805fa2a815b902d8aa3809d4be9d362af7c6 to 56cd05d2e6802c6c4359317b0c680eec3ad0a70f
Branch pushed to git repo; I updated commit sha1. New commits:
56cd05d  Some fixes discussed.

comment:60 Changed 5 years ago by
 Commit changed from 56cd05d2e6802c6c4359317b0c680eec3ad0a70f to f1f5547fc531b78522ad51ba094414594fe69ee2
Branch pushed to git repo; I updated commit sha1. New commits:
f1f5547  Fixed category issue.

comment:61 Changed 5 years ago by
 Commit changed from f1f5547fc531b78522ad51ba094414594fe69ee2 to f6a73fd57fdcb739ddf7ac4907fb3d67117af908
Branch pushed to git repo; I updated commit sha1. New commits:
f6a73fd  Fixed failing doctests in categories due to new intermediate categories.

comment:62 Changed 5 years ago by
 Status changed from needs_review to positive_review
I checked the recent commits, and we have been discussing side by side for the last ones today. doc and pdf doc compiles. Positive review assuming all long tests pass (running them now).
Thanks Travis!
Cheers,
Nicolas
comment:63 Changed 5 years ago by
 Reviewers set to Nicolas M. Thiéry
comment:64 Changed 5 years ago by
Thank you for doing the review Nicolas.
comment:65 Changed 5 years ago by
 Commit changed from f6a73fd57fdcb739ddf7ac4907fb3d67117af908 to 69ec7b219d799ffa9263bc83364bc91bf07a8065
 Status changed from positive_review to needs_review
Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. New commits:
69ec7b2  Fixed c3_controlled.pyx doctests.

comment:66 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:67 Changed 5 years ago by
 Branch changed from public/monoids/15289indexed to 69ec7b219d799ffa9263bc83364bc91bf07a8065
 Resolution set to fixed
 Status changed from positive_review to closed
comment:68 Changed 5 years ago by
 Commit 69ec7b219d799ffa9263bc83364bc91bf07a8065 deleted
Hi guys, please see http://ask.sagemath.org/question/25763/incorrectparsingofdocstringofsagestructureindexed_generatorsindexedgenerators/ where it seems that putting "\left"
becomes something quite different in html. I assume this is not desired; see #17745.
Initial version. I might add a
_basis_keys
attribute toCombinatorialFreeModule
for backwards compatibility...