major improvements to lazy power series

[mwhansen]

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.

CC: @mantepse @videlec

Component: combinatorics

Keywords: LazyPowerSeries, days57

Reviewer: Travis Scrimshaw

Issue created by migration from https://trac.sagemath.org/ticket/15673

[mwhansen]

Branch: u/mhansen/species_stream

[mwhansen]

comment:2

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

[mwhansen]

Commit: a696708

[sagetrac-git]

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

f4157f7

Remove dead code in GenericCombinatorialSpecies._series_helper

[sagetrac-git]

Changed commit from a696708 to f4157f7

[mantepse]

comment:4

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

[mwhansen]

comment:5

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.

[mantepse]

comment:6

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.

[mantepse]

comment:8

Mike, Are you sure that #12659 is related?

[mwhansen]

comment:9

Oops, I meant #12649.

[mantepse]

comment:10

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.

[mwhansen]

comment:11

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.

[sagetrac-git]

Changed commit from f4157f7 to 927ff83

[sagetrac-git]

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

927ff83

#15673: Minor changes from Martin Rubey's coments

[mantepse]

comment:13

Replying to @mwhansen:

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

[mantepse]

comment:14

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?

[mwhansen]

comment:15

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.

[mantepse]

comment:16

(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?

[rwst]

Reviewer: Ralf Stephan

[rwst]

comment:18

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

[videlec]

comment:19

Replying to @rwst:

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

[fchapoton]

comment:20

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

[sagetrac-git]

Commit: aa8fd83

[mantepse]

comment:44

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

[videlec]

comment:45

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.

[mantepse]

comment:46

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.

[sagetrac-elixyre]

comment:47

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

[mantepse]

comment:48

Replying to @sagetrac-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.

[fchapoton]

comment:49

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

and doc does not build, see patchbot report

[mantepse]

comment:50

Replying to @fchapoton:

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!

[sagetrac-elixyre]

comment:51

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?

[mantepse]

comment:52

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.

[mantepse]

comment:53

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

[tscrim]

Changed branch from u/mantepse/15673 to none

[tscrim]

Changed author from Mike Hansen to none

[tscrim]

Changed reviewer from Ralf Stephan, Matthieu Dien to Travis Scrimshaw

[tscrim]

Changed commit from aa8fd83 to none