major improvements to lazy power series

[Mike Hansen]

Some re-structuring of the streams / series code fixes many issues and makes the code quite a bit simpler.

Fixes #15249, #15248, #10084, #10085, #10086, #13433, #14685, #12648, #12649.

[Mike Hansen]

One thing that should be done (maybe not on this ticket) is to deprecate the code in sage.combinat.species.stream.

---

Last 10 new commits:

​b7afcd7	Simplifications to new_stream.py
​69b55ab	Add documentation / doctests
​13c5a49	Remove TODO in cycle_species.py
​bdad7a3	#12648: Species do not support renaming
​d2d753e	Fix bug in SeriesStream.is_constant()
​fea9eb0	#15248: Convert LazyPowerSeriesRing (and friends) to new coercion model
​6525200	Remove dependence on sage.combinat.species.stream
​ed19baa	Add doctests to new_stream.py
​654a89d	Add doctests to generating_series.py
​bd7527c	More work on doctests for series_stream.py

[git]

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

​f4157f7

Remove dead code in GenericCombinatorialSpecies._series_helper

[Martin Rubey]

Hi Mike! Thank you for uploading the new code!

I have one immediate question: if I understand correctly, you chose to introduce a new class for every operation on streams, eg. SumStream?, ProductStream?, TailStream?, DerivativeStream?, etc.

Could you explain why...? I would have thought that these things fit more natural into various generating series classes, but I'm sure you have thought quite a lot about this...

Thanks again,

Martin

[Mike Hansen]

The main idea is to have the streams know about their (approximate) order. That way we don't have to worry about initializing generators with the correct approximate order. We can also do some improvements w.r.t. caching if the streams are a bit more structured.

[Martin Rubey]

Thanks for the explanation!

I am currently compiling sage to try your code. In case you have enough time: I recently reviewed ticket #14846, which is based on the old code... Unfortunately, it is still not in the develop branch, so maybe it's better to wait until it is.

[Martin Rubey]

Mike, Are you sure that #12659 is related?

[Mike Hansen]

Oops, I meant #12649.

[Martin Rubey]

I'm slowly digging through the new code. I cannot yet decide whether I like it or not, because I really care about it, so I'd like to understand it first :-)

Questions so far:

1) would it be feasible (and not too much work) to put the new code for streams and formal power series into a new directory (or perhaps even into two, a separate one for streams)? After all, it's an accident that it's in the species directory. Species can do without formal power series (in principle), and streams have other uses.

2) I think I mostly like new_stream. However, from a user's perspective I would rather expect to create streams with

sage: s=Stream([1,2,3,4]); t=Stream(lambda l: len(l))

and moreover, I'd expect s[4] to give an error. That is, possibly we should have also finite streams. To create a stream which is constant, we could have something like Stream(constantly="bla"), and streams would have to support concatenation.

If we don't, then this behaviour has to be documented very LOUDLY. (I do see that s=Stream([1,2,3,4,0]) is very convenient.)

Minor details:

• StreamFromFunc should be StreamFromFunction and it might be nice if it wouldn't inherit from ListCachedStream, i.e., support for streams where only some coefficients are computed.

• number_computed maybe should be length_of_cache.

3) I don't understand the difference between SeriesStream and a formal power series yet.

Would it be possible to use the category framework to export operations depending on what the base_ring is? In particular, as pointed out in #14846, one should be careful with providing certain default implementations. Perhaps related: ideally I would like to be able to say,

sage: h = SymmetricFunctions(QQ).h()
sage: t = SetSpecies().cycle_index_series(); h(t)

to do change of basis.

Minor details:

• I would replace aorder everywhere with order_approximation

• I somehow dislike the idea of children, but cannot really say why.

• the doc for IntegralStream mentions derivative instead of integral.

[Mike Hansen]

Replying to mantepse:

I'm slowly digging through the new code. I cannot yet decide whether I like it or not, because I really care about it, so I'd like to understand it first :-)

Questions so far:

1) would it be feasible (and not too much work) to put the new code for streams and formal power series into a new directory (or perhaps even into two, a separate one for streams)? After all, it's an accident that it's in the species directory. Species can do without formal power series (in principle), and streams have other uses.

Sure -- I'm not sure the best place for streams to go at the moment.

2) I think I mostly like new_stream. However, from a user's perspective I would rather expect to create streams with

sage: s=Stream([1,2,3,4]); t=Stream(lambda l: len(l))

and moreover, I'd expect s[4] to give an error. That is, possibly we should have also finite streams. To create a stream which is constant, we could have something like Stream(constantly="bla"), and streams would have to support concatenation.

You can basically do that with the "OldStreamBehavior?" class.

If we don't, then this behaviour has to be documented very LOUDLY. (I do see that s=Stream([1,2,3,4,0]) is very convenient.)

Agreed.

Minor details:

• StreamFromFunc should be StreamFromFunction and it might be nice if it wouldn't inherit from ListCachedStream, i.e., support for streams where only some coefficients are computed.

The current semantics of StreamFromFunc basically require that it be a "ListCachedStream?". We can add a MappedStream which applies a function which takes in a coefficient and produces a new one.

• number_computed maybe should be length_of_cache.

3) I don't understand the difference between SeriesStream and a formal power series yet.

The distinction is pretty fine and in fact they could probably be merged. The main thing would be just be dealing with the class situation as if you had class ProductSeries(LazyPowerSeries) which implemented the things in ProductStream, then you'd also have to deal with "OrdinaryProductSeries", IsotypeProductSeries", and "CycleIndexProductSeries". They could be created on the fly say in ._new(), but I wasn't sure if that added complexity was worth it.

For now, the best way to think of a difference between a SeriesStream and a LazyPowerSeries (and friends) is that the latter adds some sort of semantics / meaning to the list of coefficients (for example, .count().

Would it be possible to use the category framework to export operations depending on what the base_ring is? In particular, as pointed out in #14846, one should be careful with providing certain default implementations. Perhaps related: ideally I would like to be able to say,

sage: h = SymmetricFunctions(QQ).h()
sage: t = SetSpecies().cycle_index_series(); h(t)

to do change of basis.

Since many of the (internal) operations need to work with the power-sum basis, you'd mainly just wanting to be converting the coefficients "at the edges". Or would you want them to always convert to the powersum basis when they needed to?

Minor details:

• I would replace aorder everywhere with order_approximation

That's fine -- I mainly kept aorder for backwards compatibility, but we don't need that on the new streams.

• I somehow dislike the idea of children, but cannot really say why.

In terms of the name? Or in terms of being able to access "sub-streams"?

• the doc for IntegralStream mentions derivative instead of integral.

Will fix.

[git]

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

​927ff83

#15673: Minor changes from Martin Rubey's coments

[Martin Rubey]

Replying to mhansen:

2) I think I mostly like new_stream. However, from a user's perspective I would rather expect to create streams with

sage: s=Stream([1,2,3,4]); t=Stream(lambda l: len(l))

and moreover, I'd expect s[4] to give an error. That is, possibly we should have also finite streams. To create a stream which is constant, we could have something like Stream(constantly="bla"), and streams would have to support concatenation.

You can basically do that with the "OldStreamBehavior?" class.

Well, we certainly do not want to keep two implementations for the same thing, do we? To put it bluntly, I'm not sure whether this design decision is a good one. Let's make the decisions clear:

A) do we want to create streams using Stream(thing_to_concert_into_a_stream or StreamFromList, StreamFromIterator, etc.

I am sure I want the first behaviour. Is there any sage object that you create using the second model at all?

B) do we want finite streams?

I'm not so sure here. However, if we don't we agree on LOUD documentation.

The current semantics of StreamFromFunc basically require that it be a "ListCachedStream?". We can add a MappedStream which applies a function which takes in a coefficient and produces a new one.

Yes, it may be good to have both. But then the semantics should be precisely the other way round.

3) I don't understand the difference between SeriesStream and a formal power series yet.

[...] For now, the best way to think of a difference between a SeriesStream and a LazyPowerSeries (and friends) is that the latter adds some sort of semantics / meaning to the list of coefficients (for example, .count().

I dislike at least the choice for the names here. LazyPowerSeries should be an element of the algebra of formal power series over a ring, I'd say. I think we should eliminate .count entirely. If we don't, then this should go into ExponentialGeneratingSeries, OrdinaryGeneratingSeries, DirichletGeneratingSeries, etc. CycleIndexSeries is special and I need to think before having an opinion :-)

Would it be possible to use the category framework to export operations depending on what the base_ring is? In particular, as pointed out in #14846, one should be careful with providing certain default implementations.

It would be great if you could give your opinion on that, I don't know the category framework well enough. In Axiom/FriCAS/Aldor it was extremely useful especially for formal power series. NB, Ralf implemented the lazy series in aldor from scratch only because he wanted to be independent from Axiom/FriCAS.

Need to run. All the best,

Martin

---

New commits:

​927ff83

#15673: Minor changes from Martin Rubey's coments

[Martin Rubey]

Hi Mike,

one minor further issue: we still have

sage: from sage.combinat.species.series_order import unk
sage: min(1,unk)
Unknown series order
sage: min(unk,1)
1

While I was unable to produce an actual bug using this, it might be possible. I think we should have a simple linear order unk < 1 < 2 < ... < inf . Do you know how to do this?

[Mike Hansen]

Yes, that's still an issue when using Integers as series orders due to the way Python works. One way to do it would be to make sure that ".aorder" is an element of a special ordered set so that we can make sure the current comparison is being used.

[Martin Rubey]

(Off topic) Mike, there's something I do not understand about trac: in the change history here on the ticket I see two identical commits:

​927ff83 #15673: Minor changes from Martin Rubey's coments

should I expect this?

[Ralf Stephan]

The branch does not merge cleanly into 6.2.beta2 but it's a one line change. Tests within species are good. Docs build fine.

I also think that stream is another word for infinite sequence, and so a finite stream implementation already exists in structure.sequence, which is also fast (there are however problems in that Sequence doesn't have a parent, see #15852).

[Vincent Delecroix]

Replying to rws:

The branch does not merge cleanly into 6.2.beta2 but it's a one line change. Tests within species are good. Docs build fine.

I also think that stream is another word for infinite sequence, and so a finite stream implementation already exists in structure.sequence, which is also fast (there are however problems in that Sequence doesn't have a parent, see #15852).

Note that there is also sage.misc.lazy_list which is a cython implementation of a lazy list and there are several interesting implementations of lazy words in sage.combinat.words...

[Frédéric Chapoton]

I have rebased on 6.2.beta6 : here is a git branch

Is this considered to be "needs review" ?

---

New commits:

​8ff4acc

Merge branch 'u/mhansen/species_stream' of trac.sagemath.org:sage into 15673

[Matthieu Dien]

Hello,

I can help to improve and review this ticket. I also explore the way to use it to deal with multivariate lazy series

[Martin Rubey]

Replying to chapoton:

I have rebased on 6.2.beta6 : here is a git branch

Is this considered to be "needs review" ?

No, I'd say it needs work. At least the proposed way to create streams doesn't look right from a user's perspective. However, it's a huge improvement over the old code!

[Matthieu Dien]

I updated tests and documentation

[git]

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

​5d3dfc2

add tests and improve documentation

[Ralf Stephan]

#16107 depends on this.

[Nicolas M. Thiéry]

Hi Mike!

The is_constant protocol seems somewhat convoluted; from profiling, Matthieu is telling me that it's taking a non trivial portion of the time. Could it be possibly simplified? In particular, could we just get rid of is_constant, and handle everything with a cached method "get_constant_position" which would return infinity when appropriate?

Cheers,

Nicolas

[Martin Rubey]

I just had a very brief look at lazy lists. Is there any reason not to use them? There may be some work involved to allow for recursively defined lists, I'm not sure.

[Matthieu Dien]

Replying to mantepse:

I just had a very brief look at lazy lists. Is there any reason not to use them? There may be some work involved to allow for recursively defined lists, I'm not sure.

I'm working on it, I should propose an implementation soon

[Matthieu Dien]

We opened a new ticket about lazy_list (#16137) with the idea to replace the sage.combinat.species.new_stream backend (slower than lazy_list).

[git]

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

​34ceae0	Merge branch 'public/ticket/15673' of trac.sagemath.org:sage into 6.4.beta6
​8e004ea	trac #15673 correct doctests

[Martin Rubey]

Is there any intention to pursue #16137? I'm not sure, but it seems to me that my comments 11 and 13 above were not taken into account so far (in fact, 13 was not answered at all), and the design decisions taken here seem to contradict the ideas of #16137. This is partially about terminology: from a user's perspective, I wouldn't expect a stream to carry any semantics except that it is a possibly infinite sequence of things. In particular, it should work also for things other than numbers and polynomials. However, then things like IntegralStream doesn't make sense, this is confusing formal power series with streams.

That said, I tried to read the code, and found that I'm completely lost. I have no way to adapt it as to provide an alternative implementation. Thus, in case you think my concerns are of minor importance, please go ahead!

[git]

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

​f8815da	Merge branch 'public/ticket/15673' into 6.5.rc0
​5478a2d	trac #15673 put raise statements into py3 standard

[Frédéric Chapoton]

This has rotten. Too bad. Needs rebase, and not an easy one.

[Vincent Delecroix]

Hello,

#16137 is in the process of being reviewed. Note that it will just be a fast and flexible data structures for (finite or infinite) list like objects. Features:

• it is very lazy (zero computation at instanciation)
• it is a tiny Cython wrapper above list and is hence very fast to access the cached values
• definition can be recursive and involve other lazy lists
• there is no such thing as "ultimately constant lazy list" or "compute with no cache lazy list"
• they are currently immutable (which allows to share memory for slices)

Vincent

[Martin Rubey]

I looked again at the code by Mike Hansen, I believe I understand it a little bit better than 2 years ago. I try to give a summary, and hope to get some feedback.

The code in this ticket consists of three parts: streams (with similar intentions to lazy_list), power series, and the adaptation of the species code.

The code for streams (only roughly 500 lines) is in new_stream.py. It introduces different classes depending on how the stream is to be produced: StreamFromIterator, StreamFromList, StreamFromFunction (unused), and an "abstract base class" ListCachedStream.

The code for series is mainly in series_stream.py and series.py. The main class is SeriesStream (which is a misnomer, I'd say). Its main purpose is to set up the protocol that enables recursive definitions, by keeping track of the so called approximate order of a series, which is a lower bound on the exponent of the monomials in the series with non-vanishing coefficient.

For each operation on series (binary, like addition, multiplication, composition; unary, like derivative, etc.) introduces a new class, where the above mentioned order and the actual terms are computed.

Finally, the classes LazyPowerSeriesRing and LazyPowerSeries in series.py put this into the algebraic framework.

There are many things I do not completely understand. For example, for the species code yet another class, SpeciesSeriesStream, is introduced, rather than just using LazyPowerSeries. I have no idea why this is so complicated. (It wasn't complicated in the original aldor code, and it's somehow hard to believe that python would need so much more code.)

Assuming that the code is OK I guess it's best if I rebase it and see what happens.

[Martin Rubey]

So far I have rebased the files new_stream.py, series.py and generating_series.py. I guess it's best to push to a new branch, right?

One thing I'd like to note here is that many tests in generating_series.py depend on species, which I haven't rebased yet, and thus fail :-(

[git]

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

​aa8fd83

rebase Mike Hansen's code

[Martin Rubey]

I have now completed the rebase. All tests pass. It would be great if someone more versed in python than me could look at the design...

[Vincent Delecroix]

Well done for the rebase!

Some personal feelings about the code

1. There are public method that should not be there. For example Stream.compute. The documentation mentions Do not use this method. In such case, the method should be private, i.e. starting with an underscore like _compute. Might apply as well to SeriesStream.refine_order, SeriesStream.compute_order, RecursiveStream.not_defined_check, ...

2. The check_constant_decorator is really ugly. I would implement it directly in the __getitem__.

3. You should seriously consider replacing new_stream.py with lazy_list.pyx which is currently about 5x faster for __getitem__ and provide more or less the same functionality

   sage: from sage.combinat.species.new_stream import StreamFromFunction
   sage: h = lambda l: 1 if len(l) < 2 else l[-1] + l[-2]
   sage: s = StreamFromFunction(h)
   sage: from sage.misc.lazy_list import lazy_list
   sage: def h2(l): l.append(l[-1]+l[-2])
   sage: s2 = lazy_list(initial_values=[1,1],update_function=h2)
   

   Then

   sage: %timeit s[0]
   1000000 loops, best of 3: 942 ns per loop
   sage: %timeit s2[0]
   10000000 loops, best of 3: 148 ns per loop
   

   Though there are missing features. For example, current lazy_list do not care about being periodic or constant after a certain point. But I would be happy to implement needed stuff from this side.

This series code would be a good test case to see whether lazy_list are as flexible as they claim to be.

4. In many situations it would be much faster to use Newton's method rather than an intricated tree of streams.

[Martin Rubey]

Thanks for your comments!

ad 1. and 3.: yes, that's what I want to do. I'm currently trying to figure out whether I should let SeriesStream inherit from lazy_list. I guess that Stream, ListCachedStream, etc. should be eliminated entirely.

ad 4.: I guess that you are referring to the examples in the species code - I do not think there is any recursive definition used in library code. Of course Newton would be faster. The point of the recursive facility is only to create a species easily, for example to check the first few terms of the cycle index series. In case one needs more speed, one will have to "really" implement the species.

ad 2.: unfortunately, I do not really know what it does. I'll try to figure out.

[Jean-Baptiste Priez]

Hello,

Thanks to update and improve this code! ;-)

I have a stupid question: the lazy thing is a trick to compute efficiently the coefficient of the product of series or some other operations on series, right?

About the code, why does LazyPowerSeries only inherit of AlgebraElement and not of Stream? It seems not so python/object to define a lazy series as a capsule of a stream so I want to understand.

All I read in the code look like this

class LazyPowerSeries(...):
      ....
      def get_order(self):
        return self._stream.get_order()
     ....

so it seems better to inherit of Stream.

Jean-Baptiste Priez

[Martin Rubey]

Replying to elixyre:

I have a stupid question: the lazy thing is a trick to compute efficiently the coefficient of the product of series or some other operations on series, right?

No. The laziness is for having potentially infinite sequences.

About the code, why does LazyPowerSeries only inherit of AlgebraElement and not of Stream?

Unless I misunderstand python's inheritance, the point is that a LazyPowerSeries should not have the methods of it's stream of coefficients.

My current plan is to remove Stream entirely, rename SeriesStream to CoefficientStream and make the latter into a ring module, which uses the new lazy_list, or, once that is in place, Daniel Krenn's InfiniteSequence.

[Frédéric Chapoton]

There is a bad INPUT:: that should be replaced by INPUT:

and doc does not build, see patchbot report

[Martin Rubey]

Replying to chapoton:

There is a bad INPUT:: that should be replaced by INPUT:

and doc does not build, see patchbot report

Thanks, I changed this locally. However, I will not take care of the documentation at the moment, because I'm currently (really!) working on the design.

Right now I think that I want a class CoefficientStream to model the algebraic structure of the sequence of coefficients of a formal power series with coefficients in a ring, i.e., inheriting from ModuleElement.

I am not yet sure whether the computation of the approximate order really belongs here: after all, we want to recursively specify formal power series, not coefficient streams. The design decision is not completely clear, because formal power series and coefficient streams are almost the same thing - except that most operations feel more natural on the level of formal power series.

Suggestions and comments very welcome!

[Jean-Baptiste Priez]

Replying to mantepse:

I'm currently (really!) working on the design. I am not yet sure whether the computation of the approximate order really belongs here: after all, we want to recursively specify formal power series, not coefficient streams. The design decision is not completely clear, because formal power series and coefficient streams are almost the same thing - except that most operations feel more natural on the level of formal power series.

Suggestions and comments very welcome!

I will be happy to discuss code design with you.

I have some code (about species) on the branch u/elixyre/species (not associated to any ticket). I was trying to redesign the species with the goal to use the current Permutations, Partitions, etc ... I don't used the design Parent-Element, I was to lazy to update this code but I can do it easily...

Whatever I recode my own Series on this branch (as a simple exercice to understand operations on series). There is a lot of really simple code that I assume to be a draft of a good (code) design. My code was thought to be simple to improve and understand.

(Specially I have a nice simple tool to compute the valuation.)

Do you have some branch where you try your own design that I could pull?

[Martin Rubey]

I will be happy to discuss code design with you.

Great!

I have some code (about species) on the branch u/elixyre/species (not associated to any ticket). I was trying to redesign the species with the goal to use the current Permutations, Partitions, etc ... I don't used the design Parent-Element, I was to lazy to update this code but I can do it easily...

Is this in the species2 directory?

Whatever I recode my own Series on this branch (as a simple exercice to understand operations on series). There is a lot of really simple code that I assume to be a draft of a good (code) design. My code was thought to be simple to improve and understand.

(Specially I have a nice simple tool to compute the valuation.)

So, very likely it makes sense to start from your branch?

Do you have some branch where you try your own design that I could pull?

No, because I'm doing this with pencil and paper...

Eventually we could talk, too, I have webcam + whiteboard.

[Martin Rubey]

This is no longer relevant, since #32367. (essentially, a similar approach was used)