Opened 6 years ago

Closed 5 years ago

Implement indexed monoids

Reported by: Owned by: tscrim sage-combinat major sage-6.3 algebra days54 sage-combinat, nthiery, mshimo, SimonKing Travis Scrimshaw Nicolas M. Thiéry N/A 69ec7b2 (Commits) #15309, #15169, #16349

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.

comment:1 Changed 6 years ago by tscrim

• Status changed from new to needs_review

Initial version. I might add a _basis_keys attribute to CombinatorialFreeModule for backwards compatibility...

comment:2 Changed 6 years ago by nthiery

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 tscrim

• 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 tscrim

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

comment:5 Changed 6 years ago by tscrim

• Dependencies set to #15309

Rebased to 5.13.beta2.

comment:6 Changed 6 years ago by tscrim

• Dependencies changed from #15309 to #15309 #15169

comment:7 Changed 6 years ago by tscrim

• Branch set to public/monoids/15289-indexed
• Commit set to c1b5afea143f80ce6d68a4386ed6b410f8fcbb17

New commits:

 ​c1b5afe #15289: Implemented indexed monoids and groups. ​6fd33b2 #15169: Fix FreeAlgebra? element constructor from a base field.

comment:9 Changed 6 years ago by git

• Commit changed from c1b5afea143f80ce6d68a4386ed6b410f8fcbb17 to 9dca526f5ab91f7d2777ba4f4e945a869b169bb9

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

 ​9dca526 Added comparison operations. ​a493bee Merge branch 'master' into public/monoids/15289-indexed

comment:10 Changed 6 years ago by vbraun_spam

• Milestone changed from sage-6.1 to sage-6.2

comment:11 Changed 6 years ago by git

• Commit changed from 9dca526f5ab91f7d2777ba4f4e945a869b169bb9 to 991953a60536c9532590270183cfa100d3577b39

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

 ​545a8df Merge branch 'develop' into public/monoids/15289-indexed ​2975c87 Merge branch 'develop' into public/monoids/15289-indexed ​4002b0d Merge branch 'develop' into public/monoids/15289-indexed ​9e9b769 Merge branch 'develop' into public/monoids/15289-indexed ​a278afa Added cardinality methods. ​f681606 Added cardinality to free abelian monoid for consistancy. ​3a0e50b Merge branch 'develop' into public/monoids/15289-indexed ​d4606cc Added more robustness to element creation. ​991953a Merge branch 'develop' into public/monoids/15289-indexed

comment:12 Changed 6 years ago by git

• Commit changed from 991953a60536c9532590270183cfa100d3577b39 to 163df6e7f6b29e53c0844995389f52c198cffcc1

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

 ​56703eb Made Indexed* have entry points through Free*. ​163df6e Changed more _basis_keys to _indices, deprecated the former.

comment:13 Changed 6 years ago by git

• 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 follow-up: ↓ 21 Changed 6 years ago by tscrim

Hey Nicolas,

• All Indexed* now goes through Free*, but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?
• I want to leave __pow__ alone since they are more specialized for the data structures.
• The __contains__, are you suggesting putting it into Parent? 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:16 Changed 6 years ago by git

• Commit changed from 8db8e0a07605c801a9a9974e043312061ee375c1 to 03057a45e8ea5db1e95622f5e889915be2e8d024

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

 ​bd82ed8 Merge branch 'develop' into public/monoids/15289-indexed ​760c939 Merge branch 'public/monoids/15289-indexed' of trac.sagemath.org:sage into public/monoids/15289-indexed ​03057a4 Merge branch 'develop' into public/monoids/15289-indexed

comment:17 Changed 6 years ago by git

• Commit changed from 03057a45e8ea5db1e95622f5e889915be2e8d024 to a2996e0772eb50f4f973b04c2a85c8bb33cf3aa6

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

 ​a2996e0 Merge branch 'develop' into public/monoids/15289-indexed

comment:18 Changed 6 years ago by git

• Commit changed from a2996e0772eb50f4f973b04c2a85c8bb33cf3aa6 to 49068b2389e4eae6d207288d14be466d95f84966

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

 ​c1cc341 Merge branch 'develop' into public/monoids/15289-indexed ​49068b2 Merge branch 'develop' into public/monoids/15289-indexed

comment:19 Changed 6 years ago by git

• Commit changed from 49068b2389e4eae6d207288d14be466d95f84966 to 6875cfbae0f2fd90475e4ae1170fcf2444db03fb

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

 ​6875cfb Merge branch 'develop' into public/monoids/15289-indexed

comment:20 Changed 6 years ago by git

• Commit changed from 6875cfbae0f2fd90475e4ae1170fcf2444db03fb to 1818a3efc4e4b28a005a833a05a66e7765280966

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

 ​1818a3e Merge branch 'develop' into public/monoids/15289-indexed

comment:21 in reply to: ↑ 14 ; follow-up: ↓ 22 Changed 6 years ago by nthiery

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 through Free*,

Nice! Thanks!

but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?

It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sage-devel?

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: Algebras(QQ).free(index_set={...})


Then we could remove all the Free* from the global name space.

• The __contains__, are you suggesting putting it into Parent?

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

• 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 ; follow-up: ↓ 23 Changed 6 years ago by tscrim

but as a special case, I have IndexedFreeAbelianGroup as FreeGroup(index_set=X, abelian=True). Should we do the same for FreeMonoid?

It would be nice to be consistent indeed, but I have no preference for one idiom or the other. Maybe ask on sage-devel?

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: Algebras(QQ).free(index_set={...})


Then we could remove all the Free* from the global name space.

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

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 nthiery

• 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 sage-devel.

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:25 Changed 6 years ago by git

• 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/15289-indexed ​23301a8 Misc fixes and tweaks.

comment:26 Changed 6 years ago by tscrim

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 git

• 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 nthiery

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?

More later tonight!

Cheers,

Nicolas

comment:29 Changed 6 years ago by git

• 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 nthiery

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.
• 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.
• 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
• 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) of self, sorted for printing." is misleading, as it's not only used for printing.
• 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

• Construction of the generator indexed by i with F(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 nthiery

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 for index_set=[0,...,n-1] (or the equivalent IntegerRange?)
• index_set='x,y,z' is a short hand for names='x,y,z'
• names can either be a string like 'x,y,z' or a list or iterables of names.

• This supports simultaneously C.free(I), C.free('x,y,z'), and C.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) and CombinatorialFreeModule(QQ, I), as well as with the upcoming FreeModule(QQ,I) which will call IndexedFreeModule(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 nthiery

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 vbraun_spam

• Milestone changed from sage-6.2 to sage-6.3

comment:34 Changed 6 years ago by rws

• 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 git

• Commit changed from 7d27baacb4721ee041162cb280b7ee48d2b0da34 to 1ff1a0483f5e61959a432371b701f593a5dee599

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

 ​6589a09 Merge branch 'develop' into public/monoids/15289-indexed ​27cbf34 Merge branch 'develop' into public/monoids/15289-indexed ​3f667f4 Merge branch 'public/monoids/15289-indexed' of trac.sagemath.org:sage into public/monoids/15289-indexed ​90f339f Doing some of the changes Nicolas requested. ​fabaaf1 Merge branch 'develop' into public/monoids/15289-indexed ​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 follow-ups: ↓ 37 ↓ 44 Changed 6 years ago by tscrim

Fixed everything mentioned above except I've run into a major pickling issue with UniqueFactory (which is why I've cc-ed 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.

Last edited 6 years ago by tscrim (previous) (diff)

comment:37 in reply to: ↑ 36 Changed 6 years ago by nthiery

Fixed everything mentioned above except I've run into a major pickling issue with UniqueFactory (which is why I've cc-ed 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 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.

Fair enough.

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.

Ok.

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.

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 follow-up: ↓ 39 Changed 6 years ago by tscrim

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 ; follow-up: ↓ 40 Changed 6 years ago by nthiery

The FreeMonoid in the global namespace must be the UniqueFactory 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 tscrim

The FreeMonoid in the global namespace must be the UniqueFactory 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 nthiery

Yeah. Not sure it's a good idea though. Do as you feel is right.

comment:42 Changed 6 years ago by SimonKing

• Dependencies changed from #15309 #15169 to #15309, #15169

comment:43 Changed 6 years ago by SimonKing

In order to checkout this ticket, I had to fix the list of dependencies (which is supposed to be comma-separated).

comment:44 in reply to: ↑ 36 Changed 6 years ago by SimonKing

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.

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 use register_unpickle_override or see anyway to redirect that specific pickle without changing the behavior of generic_factory_unpickle().

I don't really understand how register_unpickle_override is working. It seems that it can only work if unpickle_global is involved---and 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 a UniqueFactory, 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).

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

comment:45 Changed 6 years ago by SimonKing

PS: The documentation breaks. After repeated attempts of make doc-clean 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 tscrim

• Dependencies changed from #15309, #15169 to #15309, #15169, #16349

This is now #16349. Try sage -sync-build (there's probably the old file in the lib build folder which is getting picked up).

comment:47 Changed 6 years ago by git

• Commit changed from 1ff1a0483f5e61959a432371b701f593a5dee599 to bf161359d4c73aa81aa60cb77ea1d4a7a2c0473d

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

 ​d570dda Merge branch 'develop' into public/monoids/15289-indexed ​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_factories-16349 ​2df09ed Implemented an unpickle override for UniqueFactory. ​c7646c1 Fixed doctest caused by me forgetting the registration is global. ​d0c9eb3 Merge branch 'public/pickling/unique_factories-16349' into public/monoids/15289-indexed ​bf16135 Fixed pickling issues and now using index_set as 1st arg to Free*Monoid().

comment:48 Changed 6 years ago by tscrim

• Status changed from needs_work to needs_review

comment:49 Changed 6 years ago by git

• 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 tscrim

Sorry that actually is my fault, I forgot to move the file over in the doc index.rst files.

Last edited 6 years ago by tscrim (previous) (diff)

comment:51 Changed 6 years ago by rws

• Status changed from needs_review to needs_work
    AttributeError: 'FreeAbelianMonoid_class' object has no attribute 'monoid_generators'
**********************************************************************
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 git

• 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 tscrim

• Status changed from needs_work to needs_review

comment:54 Changed 6 years ago by git

• Commit changed from ecdc00fd1e7edf706d8acfadc6325bed93e37843 to 909196eb2cd8311897437f7212c6470cba80ee84

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

 ​909196e Merge branch 'develop' into public/monoids/15289-indexed

comment:55 follow-up: ↓ 57 Changed 6 years ago by nthiery

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 than Groups().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 git

• Commit changed from 909196eb2cd8311897437f7212c6470cba80ee84 to 73a4e48f890a31cafbf4e8d176ac69c3b3171cbb

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

 ​1db7c1d Merge branch 'develop' into public/monoids/15289-indexed ​73a4e48 Implemented other changes/improvements Nicolas suggested.

comment:57 in reply to: ↑ 55 Changed 6 years ago by tscrim

Hey Nicolas,

Thanks for getting back to this ticket. I know how hard it can be to find time.

• Using dict_addition whenever meaningful

Done.

• Implementing Groups().Commutative().free() rather than Groups().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 not-so-humble) 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 heavy-handed? However I don't think it would be difficult to do (following your comment).

Best,
Travis

comment:58 Changed 5 years ago by git

• Commit changed from 73a4e48f890a31cafbf4e8d176ac69c3b3171cbb to d4fe805fa2a815b902d8aa3809d4be9d362af7c6

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

 ​b9f6f18 Merge branch 'develop' into public/monoids/15289-indexed ​d4fe805 Fixed documentation links.

comment:59 Changed 5 years ago by git

• 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 git

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

 ​f1f5547 Fixed category issue.

comment:61 Changed 5 years ago by git

• 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 nthiery

• 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 nthiery

• Reviewers set to Nicolas M. Thiéry

comment:64 Changed 5 years ago by tscrim

Thank you for doing the review Nicolas.

comment:65 Changed 5 years ago by git

• 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 tscrim

• Status changed from needs_review to positive_review

comment:67 Changed 5 years ago by vbraun

• Branch changed from public/monoids/15289-indexed to 69ec7b219d799ffa9263bc83364bc91bf07a8065
• Resolution set to fixed
• Status changed from positive_review to closed

comment:68 Changed 5 years ago by kcrisman

• Commit 69ec7b219d799ffa9263bc83364bc91bf07a8065 deleted

Hi guys, please see http://ask.sagemath.org/question/25763/incorrect-parsing-of-docstring-of-sagestructureindexed_generatorsindexedgenerators/ where it seems that putting "\left" becomes something quite different in html. I assume this is not desired; see #17745.

Note: See TracTickets for help on using tickets.