Restructure IntegerListLex code

[vdelecroix]

Split up IntegerListsLex in a fast Cython back-end and a (slower) Python front-end. Restructure with multiple implementations (like #17920) in mind.

This ticket will not change anything to the public interface of IntegerListsLex.

[nthiery]

• I believe we should rephrase this ticket as "extract the IntegerListsLex *iterator* as a standalone tool that depends on nothing but Python/Cython". In fact this could go as far as making it a standalone library in e.g. C++.

We want to keep the parent to model the set itself, ask questions like cardinality or building the polyhedron, do constructions on top of it (e.g. use it as indexing set for a vector space), etc.

#18056 would be a good occasion to handle this part.

• Being able to specify an element constructor is a useful feature as well. What we need to discuss here is whether we want to switch to using lists (or tuples!) by default.

• To remove __classcall__ we need to wait until the end of the deprecation period. To remove global_options we need to wait for the subclasses using it to be refactored to not impose this burden on IntegerListsLex.

[ncohen]

We want to keep the parent to model the set itself, ask questions like cardinality or building the polyhedron, do constructions on top of it (e.g. use it as indexing set for a vector space), etc.

The 'Lex' there seems a bit too much for the mathematical object that you want to represent. You describe things that could be a method of an 'IntegerLists?' object (or more specifically methods of 'Compositions' or 'Partitions').

• Being able to specify an element constructor is a useful feature as well. What we need to discuss here is whether we want to switch to using lists (or tuples!) by default.

There should be a way to enumerate these objects without paying this cost, however. A way to have both is to implement the iterator to return a copy of the current list, or a tuple (or even the current list itself, with big 'read only' warnings), and then implement in IntegerListsLex an __iter__ that wraps every element returned by that iterator with <whatever you need>.

Nathann

[jdemeyer]

Replying to ncohen:

There should be a way to enumerate these objects without paying this cost, however. A way to have both is to implement the iterator to return a copy of the current list, or a tuple (or even the current list itself, with big 'read only' warnings), and then implement in IntegerListsLex an __iter__ that wraps every element returned by that iterator with <whatever you need>.

That's also what I have in mind: a low-level class designed to be clean and fast implemented in Cython without overhead. And then a class on top of that which can implement whatever extra Python features that you want.

[git]

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

​8d5ca55

Restructure IntegerListsLex code

[vdelecroix]

Hi Jeroen,

As a matter of fact, if you isolate the commit that just move a file, the diff looks much nicer. I am not able to get something reasonable with the options -B, -C, -M or -D. Do you know what to do?

Vincent

[jdemeyer]

Replying to vdelecroix:

Hi Jeroen,

As a matter of fact, if you isolate the commit that just move a file, the diff looks much nicer. I am not able to get something reasonable with the options -B, -C, -M or -D. Do you know what to do?

Sorry no. I don't know how to nicely show diffs which split up a file in two (interestingly, hg has better support for this!)

[git]

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

​f648443	Move IntegerListsLex._Iter out of IntegerListsLex
​d8fd440	Restructure IntegerListsLex code

[git]

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

​9fbbd3c

Restructure IntegerListsLex code

[vdelecroix]

A comment on the design... Should we really support +Infinity in the iterator? I would go for unsigned int variables and UINT_MAX as a synonmyous for Infinity. Of course it makes sense for the higher classes (e.g. to give a proper answer to .cardinality()).

[jdemeyer]

Replying to vdelecroix:

A comment on the design... Should we really support +Infinity in the iterator?

Yes.

I would go for unsigned int variables and UINT_MAX as a synonmyous for Infinity.

And not support IntegerLists(10^100)?

[vdelecroix]

Replying to jdemeyer:

Replying to vdelecroix:

A comment on the design... Should we really support +Infinity in the iterator?

Yes.

I would go for unsigned int variables and UINT_MAX as a synonmyous for Infinity.

And not support IntegerLists(10^100)?

I said for the iterator. Not for the main class. I would not bother if iter(IntegerLists(10^100)) just failed. It should be very fast for small entries. I guess that one option would be to use Nathann strategy in #18137 with fused Cython type (here unsigned int and mpz_t). But I remember that it was nearly impossible to make it work as attributes of an extension class.

[jdemeyer]

Replying to vdelecroix:

But I remember that it was nearly impossible to make it work as attributes of an extension class.

For attributes of an extension class, no. I guess you could have two classes (one for some C type and one for mpz_t) on top of a common base class. But I have never done this.

[jdemeyer]

Replying to vdelecroix:

Replying to jdemeyer:

Replying to vdelecroix:

A comment on the design... Should we really support +Infinity in the iterator?

Yes.

I would go for unsigned int variables and UINT_MAX as a synonmyous for Infinity.

And not support IntegerLists(10^100)?

I said for the iterator. Not for the main class. I would not bother if iter(IntegerLists(10^100)) just failed. It should be very fast for small entries. I guess that one option would be to use Nathann strategy in #18137 with fused Cython type (here unsigned int and mpz_t).

I think that we really should support list(IntegerLists(10^100, length=1)) because in Sage, we always support large integers if possible.

In any case, changing this is certainly outside the scope of this ticket (it could be done in #18055 or #18056). Here, I just want to reorganize the code without changing the implementation.

[git]

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

​e39566a

Restructure IntegerListsLex code

[git]

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

​cda4b75

Restructure IntegerListsLex code

[nthiery]

Replying to jdemeyer:

I think that we really should support list(IntegerLists(10^100, length=1)) because in Sage, we always support large integers if possible.

That's part of why I am thinking of C++; then we can just have a templated iterator, and depending on the input we can choose one instantiation or the other.

In any case, changing this is certainly outside the scope of this ticket (it could be done in #18055 or #18056). Here, I just want to reorganize the code without changing the implementation.

Sounds reasonable indeed.

---

New commits:

​cda4b75

Restructure IntegerListsLex code

[git]

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

​e03140a	CombinatorialObject constructor should copy input
​e7bc348	Merge commit 'e03140a761586bf64f01aceba324abd1eece813b' into HEAD
​7f8c40a	Restructure IntegerListsLex code

[git]

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

​2b88b64

Restructure IntegerListsLex code

[jdemeyer]

Replying to vdelecroix:

I am not able to get something reasonable with the options -B, -C, -M or -D. Do you know what to do?

Actually, the following will show everything as copied from integer_list.py:

git show -D -B -C01

[git]

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

​e67e71c

Restructure IntegerListsLex code

[jdemeyer]

This now passes all doctests except for the pickle jar.

[git]

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

​8c587d3

Restructure IntegerListsLex code

[jdemeyer]

Passes all doctests and documentation builds.

[git]

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

​2be6ad0

Restructure IntegerListsLex code

[aschilling]

Hi Jeroen!

Since you seem to have cythonized the code already, could you add some timings compared to the old code?

Anne

PS: I was under the impression that it is harder to debug code in cython, which might make life a little harder for the new features in #18055.

[jdemeyer]

Replying to aschilling:

Since you seem to have cythonized the code already, could you add some timings compared to the old code?

My goal certainly was not to gain speed, but I could check...

I was under the impression that it is harder to debug code in cython, which might make life a little harder for the new features in #18055.

I have no idea really. A lot of the code I write for Sage is Cython and it hasn't bothered me.

On the other hand, I on purpose did not Cythonize IntegerListsLexIter (it's in a Cython source file, but doesn't use any Cython features). So if it makes your life easier, just move that one class to a Python file.

[jdemeyer]

Replying to aschilling:

you seem to have cythonized the code already

Depends what you mean. I moved the files to a Cython source file and I created extension types instead of Python classes. But I didn't optimize the loops for example.

[jdemeyer]

There is a small but significant speed-up (again: this is without really trying to speed up the code).

---

Before:

sage: timeit('list(IntegerListsLex(14, min_part=1))')
5 loops, best of 3: 1.18 s per loop

After:

sage: timeit('list(IntegerListsLex(14, min_part=1))')
5 loops, best of 3: 986 ms per loop

---

Before:

sage: timeit('list(IntegerListsLex(28, length=8, floor=lambda i:i, check=False))')
5 loops, best of 3: 1.11 s per loop

After:

sage: timeit('list(IntegerListsLex(28, length=8, floor=lambda i:i, check=False))')
5 loops, best of 3: 852 ms per loop

[aschilling]

Nice that there is a slight speedup without even trying hard!

FYI, I rebased this branch on top of sage-6.7.beta0 and everything looks clean.

I noticed that in nn.y in sage.combinat.integer_lists it currently says

    .. WARNING:: this function is likely to disappear in :trac:`17927`.

Briefly looking at 17927 this seems no longer the case.

[git]

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

​2188082

Remove references to #17927

[aschilling]

In principle this branch looks good to me; I guess it needs to be rebased to the latest development version, however.

Just to check: are you planning to reuse the Envelope class also for #17920? The planned changes there involving backward smoothing etc will be ok, right?

[jdemeyer]

Replying to aschilling:

Just to check: are you planning to reuse the Envelope class also for #17920? The planned changes there involving backward smoothing etc will be ok, right?

Sure. The only risk is that errors in Envelope will make both implementations wrong.

[jdemeyer]

Replying to aschilling:

In principle this branch looks good to me; I guess it needs to be rebased to the latest development version, however.

Despite the red link on Trac, it actually merges cleanly with 6.7.beta1

[aschilling]

Hi Jeroen,

Could you please rebase this patch on the latest development version, so I can do the final review? Nicolas never made a comment, so I assume he is ok with it!

Best,

Anne

[git]

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

​9582a7a

Merge tag '6.7.beta3' into t/18109/ticket/18109

[aschilling]

I went through the code and the restructuring looks good to me. All tests pass and the documentation builds. One question I have though is about the comparison functions in base.py and lists.py. The tests look almost identical. So which one is actually used for IntegerListsLex?

[nthiery]

Hi Jeroen,

Sorry, I got sidetracked reviewing other tickets. Thanks Anne for the reminder, and for checking the code and the documentation!

I have just been through the code myself (not checking the fine details though).

Altogether, I believe it's correct. Cythonizing the envelope function and making the iterator into a Cython class that depends on little of the Sage infrastructure was in our long term plans, so that's great (I would have done it after the algorithm refactorisation, but since it's done, let's move forward). Generalizing a base IntegerLists? class is useful as well.

On the other hand, is it absolutely necessary to have this separation between frontend and backend classes? It introduces some complexity and in fact some duplication (e.g. in the tests). In particular, I am worried that it might introduce complexity in the construction of new special case classes based on IntegerListsLex, when the primary goal is to make this as trivial as possible. I'd need to actually implement such new classes to qualify this worry.

If it's just a question of avoiding calls to the element constructor, could not this be done just locally in __iter__ (returning directly an IntegerListsLexIter object, or mapping the constructor on it)? If it's a question of making the iterator code independent of Parent, well, it already is: it only uses the IntegerListsLex object as a data holder for the constraints, right? As long as we don't have a specific use case (backed up by benchmarks if speed is the motivation), there may not be much point in maintaining additional code for this.

At the very least, there should be some entry point (typically in the module description) listing all the classes, and clarifying their respective roles. Maybe slightly more systematic class names could help; say: IntegerLists, IntegerListsLex, IntegerListsBackend, IntegerListsLexBackend.

Some small suggestions:

• some of the cdef attributes could be declared as int's. E.g. Envelope.min_length.

• maybe we could use the occasion to rename the attribute IntegerListsLexIter.parent especially if it's not a parent anymore.

• Another small complication is having to handle pickling by hand each time. At least, would there be a way to implement XXX.__reduce__ to return (XXX, *) rather than having to implement an unpickle_XXX function each time?

Cheers,

Nicolas

[jdemeyer]

Replying to nthiery:

On the other hand, is it absolutely necessary to have this separation between frontend and backend classes? If it's a question of making the iterator code independent of Parent

It's a question of making the backend class independent of Parent yes. I think it's good to have a fast simple Cython backend and a proper Sage Parent front-end.

Some small suggestions:

• some of the cdef attributes could be declared as int's. E.g. Envelope.min_length.

I consider that out of the scope of this ticket. These are micro-optimizations which can be done after we have a clearer view of the final design.

• maybe we could use the occasion to rename the attribute IntegerListsLexIter.parent especially if it's not a parent anymore.

Sure, fine for me.

• Another small complication is having to handle pickling by hand each time. At least, would there be a way to implement XXX.__reduce__ to return (XXX, *) rather than having to implement an unpickle_XXX function each time?

It's certainly annoying, but that's because Cython cannot automatically (un)pickle extension types. I have to check if it can be simplified.

[nthiery]

Hi Jeroen,

Replying to jdemeyer:

It's a question of making the backend class independent of Parent yes. I think it's good to have a fast simple Cython backend and a proper Sage Parent front-end.

I agree its good in theory. But if it makes things more complicated, then it's only good in practice if we have an actual use case.

A main point being: unless we create millions of small IntegerListsLex? objects, I don't see why having it be a (facade) parent makes things slower.

I consider that out of the scope of this ticket. These are micro-optimizations which can be done after we have a clearer view of the final design.

Fair enough.

It's certainly annoying, but that's because Cython cannot automatically (un)pickle extension types. I have to check if it can be simplified.

Thanks!

Cheers,

Nicolas

PS: I forgot to word my appreciation for the hard work!

[vdelecroix]

Replying to nthiery:

Hi Jeroen,

Replying to jdemeyer:

It's a question of making the backend class independent of Parent yes. I think it's good to have a fast simple Cython backend and a proper Sage Parent front-end.

I agree its good in theory. But if it makes things more complicated, then it's only good in practice if we have an actual use case.

A main point being: unless we create millions of small IntegerListsLex? objects, I don't see why having it be a (facade) parent makes things slower.

A use case is in MatrixSpace.__iter__ and I also have others intensive usage for building so-called square tiled surfaces (if you care, look at u/vdelecroix/flat_surfaces-6.5). I would be grateful if the iterator could be accessible without initializing any parent.

Vincent

[ncohen]

A main point being: unless we create millions of small IntegerListsLex? objects, I don't see why having it be a (facade) parent makes things slower.

Wouldn't this happen if somebody wants, for all n between 10 and 1000, one instance of a partition of n satisfying <a specific set of constraints> ?

There is a (trivial) case at least which makes sense to me, i.e. for a fixed k find some partition of n into integers between floor(n/k) and ceil(n/k). I agree that this can be done manually without this iterator, but I expect that it can happen with more complicated set of constraints too.

Nathann

[nthiery]

Replying to vdelecroix:

A use case is in MatrixSpace.__iter__ and I also have others intensive usage for building so-called square tiled surfaces (if you care, look at u/vdelecroix/flat_surfaces-6.5). I would be grateful if the iterator could be accessible without initializing any parent.

Thanks for the feedback.

Do you mind running a concrete benchmark in one of those situations, comparing a facade parent IntegerListLex and a non-parent IntegerListsLex as provided by this ticket? Then we coud evaluate on solid ground what the overhead actually is, and whether it's worth the additional complexity?

[vdelecroix]

sage: class A:
....:     pass
....: 
sage: class B(Parent):
....:     pass
....: 
sage: timeit("A()")
625 loops, best of 3: 413 ns per loop
sage: timeit("B()")
625 loops, best of 3: 13.2 µs per loop

[jdemeyer]

That's not a fair benchmark, since that's Python, not Cython. The real benchmark is this:

sage: cython("cdef class A(object): pass")
sage: cython("from sage.structure.parent cimport Parent\ncdef class B(Parent): pass")
sage: timeit("A()", number=10^4, repeat=20)
10000 loops, best of 20: 68.9 ns per loop
sage: timeit("B()", number=10^4, repeat=20)
10000 loops, best of 20: 14.5 µs per loop

[nthiery]

Replying to jdemeyer:

That's not a fair benchmark, since that's Python, not Cython. The real benchmark is this:

sage: cython("cdef class A(object): pass")
sage: cython("from sage.structure.parent cimport Parent\ncdef class B(Parent): pass")
sage: timeit("A()", number=10^4, repeat=20)
10000 loops, best of 20: 68.9 ns per loop
sage: timeit("B()", number=10^4, repeat=20)
10000 loops, best of 20: 14.5 µs per loop

Thanks Vincent and Jeroen. For fairness, we should also initialize the category. Here it is:

sage: %timeit B()
The slowest run took 4.13 times longer than the fastest. This could mean that an intermediate result is being cached 
100000 loops, best of 3: 13.3 µs per loop
sage: %timeit B(category=C)
The slowest run took 7.14 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 21.7 µs per loop

Those benchmarks teach us that constructing a Parent costs 200 times more than an empty object. Not quite surprising, but it's a start. Now what I really had in mind was a benchmark in a real use case, to estimate what's the relative overhead in a typical situation.

Let's take something really trivial:

sage: sage: %timeit IntegerListsLex(n=1, max_length=1).an_element()
The slowest run took 6.67 times longer than the fastest. This could mean that an intermediate result is being cached 
10000 loops, best of 3: 113 µs per loop

Now we start to have some concrete ground to start discussions: what we are speaking about is an overhead of 13% in the case of the most trivial operation. There probably is some room for improvements in the initialization of IntegerListsLex objects; but not so much either: there is some unavoidable option parsing and initialization work to do. Similarly, there may be room for improvement in the initialization of a Parent (I am surprised that initializing the category is costly, since for a Cython parent it does nothing but set an attribute). Altogether, the 13% has to be taken with a grain of salt at this point.

For additional insight, I believe we would be need to have some typical concrete use case, like the one Vincent has for matrices or flat surfaces. And see, then, what's the actual overhead. With that, we will be able to take an informed decision; not just out of fear that "parents are slow".

Vincent, could you pickup such a situation and make a benchmark?

In general I would like to follow this rule of thumb for our enumerated sets:

• On one hand, implement super optimized standalone iterators with bare bone API, whenever there is a proven need for them.

• On the other hand, when modeling an enumerated set, implement it as a Parents with nice input parsing and a full fledged API; and typically using the above iterators under the hood.

• Avoid half measures with iterables that are not Parent.

Here the situation is a bit delicate since we are in between the shores: the iterator needs some non trivial parsing and internal data. Which calls for an intermediate class handling the parsing and the data storage; is this class meant to model the enumerated set itself or not?

All that being said, just make your call. I am fine with additional complexity when there is a proven and worthwhile need for it. And when someone is willing to pay for the maintenance overhead ...

Cheers,

Nicolas

[jdemeyer]

Replying to nthiery:

In general I would like to follow this rule of thumb for our enumerated sets:

• On one hand, implement super optimized standalone iterators with bare bone API, whenever there is a proven need for them.

• On the other hand, when modeling an enumerated set, implement it as a Parents with nice input parsing and a full fledged API; and typically using the above iterators under the hood.

• Avoid half measures with iterables that are not Parent.

Why do you think that the current implementation is a "half measure"? I would say it fits your "super optimized standalone iterators with bare bone API" (except that it's currently not yet super optimized, see #18055 and #18056).

[nthiery]

Good morning Jeroen,

Replying to jdemeyer:

Why do you think that the current implementation is a "half measure"? I would say it fits your "super optimized standalone iterators with bare bone API" (except that it's currently not yet super optimized, see #18055 and #18056).

Yes, I am very happy with the Cython iterator (and its upcoming optimizations) and the Parent enumerated sets (IntegerLists*). What I am wondering about are the intermediate classes (IntegerLists*Impl). What's their precise role? Do we really need them?

• Are there situations where an iterator is not enough (we really need to model the enumerated set itself), yet we can't afford the overhead of having a Parent?

And / or

• Are the *Impl just utility classes that are mandatory to construct the iterator?

Maybe we should have a short video conference at some point; it would be much easier to discuss!

[jdemeyer]

Replying to nthiery:

Yes, I am very happy with the Cython iterator (and its upcoming optimizations) and the Parent enumerated sets (IntegerLists*). What I am wondering about are the intermediate classes (IntegerLists*Impl). What's their precise role?

Well, I can see two main use cases:

1. if you need to iterate twice over the same set.
2. to check containment.

In the future, point counting could be added as an extra algorithm in the Impl class, not in the iterator.

[jdemeyer]

Replying to nthiery:

• At least, would there be a way to implement XXX.__reduce__ to return (XXX, *) rather than having to implement an unpickle_XXX function each time?

That's not quite possible because of ​https://groups.google.com/forum/#!topic/sage-devel/limDRGuep34

[ncohen]

That's not quite possible because of ​https://groups.google.com/forum/#!topic/sage-devel/limDRGuep34

... which was also solved with an 'unpickle' function T_T

[jdemeyer]

Actually, pickling can be implemented better using __getstate__ and __setstate__.

[git]

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

​c940857

Simplify pickling for IntegerListsImpl

[jdemeyer]

For Envelope, this is harder since __init__ really does some non-trivial stuff like the sign handling.

[git]

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

​d46541f

Fix __richcmp__ doctests

[jdemeyer]

Replying to aschilling:

One question I have though is about the comparison functions in base.py and lists.py. The tests look almost identical.

Right, I fixed the tests.

[jdemeyer]

Replying to nthiery:

Maybe slightly more systematic class names could help; say: IntegerLists, IntegerListsLex, IntegerListsBackend, IntegerListsLexBackend.

Do you find ...Backend more clear than ...Impl? If you care a lot, I can change it, but it smells like bike-shedding.

[git]

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

​5f7a883

Rename attribute "_parent" to "impl"

[nthiery]

Replying to jdemeyer:

Replying to nthiery:

Maybe slightly more systematic class names could help; say: IntegerLists, IntegerListsLex, IntegerListsBackend, IntegerListsLexBackend.

Do you find ...Backend more clear than ...Impl? If you care a lot, I can change it, but it smells like bike-shedding.

I have a preference for Backend since we use this vocable elsewhere in Sage (e.g. in the graph library), but don't really care otherwise; you choose. My comment was more about having a consistent naming scheme. It could be enough to e.g. rename IntegerListsImpl_invlex to IntegerListsLexImpl.

Thanks by the way for investigating how to better do the pickling!

[jdemeyer]

Replying to nthiery:

Replying to jdemeyer:

Replying to nthiery:

Maybe slightly more systematic class names could help; say: IntegerLists, IntegerListsLex, IntegerListsBackend, IntegerListsLexBackend.

Do you find ...Backend more clear than ...Impl? If you care a lot, I can change it, but it smells like bike-shedding.

I have a preference for Backend since we use this vocable elsewhere in Sage (e.g. in the graph library), but don't really care otherwise; you choose. My comment was more about having a consistent naming scheme. It could be enough to e.g. rename IntegerListsImpl_invlex to IntegerListsLexImpl.

Well, I actually prefer IntegerListsImpl_invlex over IntegerListsLexImpl.

I intentionally do not want IntegerListsImpl_invlex to be associated too much with IntegerListsLex: people should not think that there must be a 1-to-1 correspondence between IntegerLists classes and IntegerListsImpl classes.

[jdemeyer]

After replacing Impl by Backend:

Error compiling Cython file:
------------------------------------------------------------
...
        IntegerListsBackend.__init__(self, *args, **kwds)

        self.check = check

        if self.min_part < 0:
            raise NotBackendementedError("strictly negative min_part")
                                       ^
------------------------------------------------------------

sage/combinat/integer_lists/invlex.pyx:848:40: undeclared name not builtin: NotBackendementedError

[vdelecroix]

What is your strategy, defining NotBackendementedError?

[git]

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

​434a152

Rename Impl -> Backend

[nthiery]

Replying to jdemeyer:

Well, I actually prefer IntegerListsImpl_invlex over IntegerListsLexImpl.

I intentionally do not want IntegerListsImpl_invlex to be associated too much with IntegerListsLex: people should not think that there must be a 1-to-1 correspondence between IntegerLists classes and IntegerListsImpl classes.

I see your point. Still I find useful to give the reader a hint that, in this case, there is such a correspondence. When reading the code, I had to dig around to make sure I was getting it right.

So I'd rather have a consistent naming scheme, and a note to the developers, in the overview documentation of the module, that there need not be in general such a 1-to-1 correspondence.

Cheers,

Nicolas

PS: fun error message :-)

[jdemeyer]

Replying to nthiery:

I see your point. Still I find useful to give the reader a hint that, in this case, there is such a correspondence.

There is not, even in this case. Note that IntegerListsLex is just IntegerLists with a classcall method and a default backend. I can easily create an IntegerLists instance with a IntegerListsBackend_invlex backend or an IntegerListsLex instance with a different backend.

[git]

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

​6ae2e22

Some doc improvement

[chapoton]

needs rebase, does not apply

[jdemeyer]

Do you have an intention to review the ticket once I rebase it? I'm just asking since there is no point in rebasing if it just continues to bitrot.

[nthiery]

Thanks for asking. The review is on my todo list for the last week of August.

[git]

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

​35e2e50

Restructure IntegerListsLex code

[jdemeyer]

Rebased and squashed, testing now...

[git]

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

​3ebbb65

Workaround for Trac #18192

[git]

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

​88a100a

Fix one more import of IntegerListsLex

[kdilks]

Merge conflict.

[jdemeyer]

Do you actually plan to review this ticket? If you do, then I'll rebase immediately.

[tscrim]

I will review this ticket once rebased.

[git]

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

​6fcd10a

Merge tag '6.9' into t/18109/ticket/18109

[tscrim]

I made some doc tweaks while we are moving everything around. Everything works and since we aren't actually changing the functionality, I'm not looking at that closely. In short, it looks goods.

In writing this comment, I've convinced myself that having a frontend class for each backend will likely be a good thing in practice as it can be used to distinguish different iteration orders without having to look at the backend (which may not be python visible at the end of the day). It also makes it easier to define string representations and natural extensions to subclasses.

In particular, #15525, which we will probably need to tweak some of those changes to support this new framework (and at least correct the imports, which is why I listed it as a dependency).

---

New commits:

​2e5e969

Some minor reviewer tweaks and doc changes.

[jdemeyer]

Two details:

1. an set should be a set

2. Why this change? I find the old version more readable.

   -        good_sum = (nu >= p.min_sum and nu <= p.max_sum)
   -        good_length = (l >= p.min_length and l <= p.max_length)
   -        no_trailing_zeros = (l <= max(p.min_length,0) or mu[-1] != 0)
   -        return good_sum and good_length and no_trailing_zeros
   +        return (nu >= p.min_sum and nu <= p.max_sum # Good sum
   +                 and l >= p.min_length and l <= p.max_length # Good length
   +                 and (l <= max(p.min_length,0) or mu[-1] != 0)) # No trailing zeros
   

If this is for performance reasons, you can instead cdef bint the variables good_sum, good_length and no_trailing_zeros.

[jdemeyer]

Replying to tscrim:

In writing this comment, I've convinced myself that having a frontend class for each backend will likely be a good thing in practice as it can be used to distinguish different iteration orders without having to look at the backend

But why would you need to "distinguish different iteration orders" in the first place?

In the few cases (maybe invlex is the only one?) where the iteration algorithm really matters, I understand that you want a separate front-end. However, it should be possible for a backend to iterate in an arbitrary order.

I really want to see the front-end and back-end as orthogonal: I can see use cases for different front-ends with the same back-end and use cases for different back-ends for the same front-end.

[tscrim]

Replying to jdemeyer:

Two details:

2. Why this change? I find the old version more readable.

   -        good_sum = (nu >= p.min_sum and nu <= p.max_sum)
   -        good_length = (l >= p.min_length and l <= p.max_length)
   -        no_trailing_zeros = (l <= max(p.min_length,0) or mu[-1] != 0)
   -        return good_sum and good_length and no_trailing_zeros
   +        return (nu >= p.min_sum and nu <= p.max_sum # Good sum
   +                 and l >= p.min_length and l <= p.max_length # Good length
   +                 and (l <= max(p.min_length,0) or mu[-1] != 0)) # No trailing zeros
   

If this is for performance reasons, you can instead cdef bint the variables good_sum, good_length and no_trailing_zeros.

It was for performance reasonings, but not the reason you're thinking of: short circuiting.

[tscrim]

Replying to jdemeyer:

Replying to tscrim:

In writing this comment, I've convinced myself that having a frontend class for each backend will likely be a good thing in practice as it can be used to distinguish different iteration orders without having to look at the backend

But why would you need to "distinguish different iteration orders" in the first place?

In the few cases (maybe invlex is the only one?) where the iteration algorithm really matters, I understand that you want a separate front-end. However, it should be possible for a backend to iterate in an arbitrary order.

I don't need this flexibility, but it comes as an added bonus. Right now we can check backends explicitly, but this allows us to separate that off into a completely separate package and still retain a differentiation.

I really want to see the front-end and back-end as orthogonal: I can see use cases for different front-ends with the same back-end and use cases for different back-ends for the same front-end.

I can see both use cases as well, but chances are there will be a coupling between base classes and backend. However I don't think it is really useful to continue this discussion because we both have our reasons for liking it. We just need to take care of the additions from #15525 (and the doc tweak above). Do you want me to do that (since that was my ticket) or will you?

[jdemeyer]

Replying to tscrim:

Do you want me to do that (since that was my ticket) or will you?

Go ahead. But please don't rewrite history, just merge #15525 and add extra commits.

[git]

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

​7982d3a	Iniital fix and added regular partitions.
​4143c96	Merge branch 'develop' into public/combinat/partitions_constraints-15525
​1adb368	Added deprecation to IntegerListLex global_options arg. Fixed doctests.
​c477d6c	Merge branch 'public/combinat/partitions_constraints-15525' of trac.sagemath.org:sage into public/combinat/partitions_constraints-15525
​03dcda9	Merge branch 'public/combinat/partitions_constraints-15525' of trac.sagemath.org:sage into public/combinat/partitions_constraints-15525
​82f4fd5	Merge branch 'public/combinat/partitions_constraints-15525' of trac.sagemath.org:sage into public/combinat/partitions_constraints-15525
​0cc28a0	Fixing some things.
​1ec481d	Addressing Kevin's comments.
​7760c71	Merge branch 'public/combinat/partitions_constraints-15525' of trac.sagemath.org:sage into u/tscrim/refactor_integer_lists_lex-18109
​8b96bb5	Adding changes from #15525.

[tscrim]

Replying to jdemeyer:

Replying to tscrim:

Do you want me to do that (since that was my ticket) or will you?

Go ahead. But please don't rewrite history, just merge #15525 and add extra commits.

Done. So if you're okay with my changes, then we can set a positive review.

[vbraun]

Doctests fail, try with the next beta

[jdemeyer]

I'm testing this now...

---

New commits:

​8244983

Merge tag '6.10.beta0' into t/18109/refactor_integer_lists_lex-18109

[git]

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

​65025ab

Fix IntegerListsLex import

[tscrim]

LGTM.