lazy_list from various input data

[MatthieuDien]

The lazy_list in sage.misc.lazy_list only deals with infinite list built from iterator. In many situations we want to create infinite list from more various data:

• an iterator (current implementation),
• an explicit form a function n -> n-th term
• an update function: a function that given a buffer of already computed values compute some extra terms (e.g. in the context of words: fixed point of substitutions and in the context of power series: Newton iteration and relaxed multiplication).

Those new lazy lists aim to be very basic Python objects. Their purpose is to be used as fast and reliable data structures in:

• words (sage.combinat.words, see also #19620)
• continued fraction expansions/binary expansions of real numbers
• lazy power series (see #15673)
• ...

See also: rational o.g.f. #15714, hypergeometric e.g.f. part of #2516

In the original proposal there was also ultimately periodic lazy lists (that would simply store two attributes for the pre-period and period). In this ticket we focus on the ones that need a cache mechanism.

[vdelecroix]

Hi Ralf,

I think that our third item also includes CFinite sequences. The difference is about how the function update is written. It might be either

def update1(cache):
    cache.append(cache[-1] + cache[-2])

or

def update2(cache):
    return cache[-1]+cache[-2]

Actually, even a closed form is a special case of update1 as one can call len on the cache. Do you agree or did I miss something?

The main task of this ticket is to write precise specifications of what we need... adapting the current implementation of lazy_list is straightforward.

[rws]

OK then please clarify the scope of the ticket. Also a periodic list is a special case of update.

[mantepse]

I don't think it is a good design decision to have lazy_list include functionality that really belong to formal power series or recursive sequences. I think that this is one of the things Axiom/FriCAS really got right: there is one class (in Axiom-parlance: Stream) which does not require any functionality from the elements. Formal power series and sequences then use this class, and allow access to it via a method coefficients.

In any case, there is quite a large interesting hierarchy of formal power series and sequences, and it is in my opinion a very bad idea to single out rational or hypergeometric functions.

Note that I am not at all against functionality that allows to define lazy lists recursively (on the contrary!), just please do not limit it to sequences built of numbers then.

[vdelecroix]

Replying to mantepse:

I don't think it is a good design decision to have lazy_list include functionality that really belong to formal power series or recursive sequences. I think that this is one of the things Axiom/FriCAS really got right: there is one class (in Axiom-parlance: Stream) which does not require any functionality from the elements. Formal power series and sequences then use this class, and allow access to it via a method coefficients.

In any case, there is quite a large interesting hierarchy of formal power series and sequences, and it is in my opinion a very bad idea to single out rational or hypergeometric functions.

Note that I am not at all against functionality that allows to define lazy lists recursively (on the contrary!), just please do not limit it to sequences built of numbers then.

Hey Martin,

There is no way lazy_list would be made only of numbers! My first goal was to have better data structure for words (sage.combinat.words). I also had in mind its usage in lazy power series. Do you prefer the new description? Please edit it if there is something wrong. The concrete implementation did not start yet. We are waiting for the best possible specifications...

[rws]

I am aware that it looks like we would only look at numbers. But I was only listing what is already available in code. I would like to have an overview of the hierarchy you mention, not the least because it would help with the design of the code planned here. Where could such an overview (of the hierarchy of formal power series and sequences) be found?

[vdelecroix]

Replying to rws:

I am aware that it looks like we would only look at numbers. But I was only listing what is already available in code. I would like to have an overview of the hierarchy you mention, not the least because it would help with the design of the code planned here. Where could such an overview (of the hierarchy of formal power series and sequences) be found?

Ralf,

I do not understand what happened and if you did it on purpose. I modified the description twice and you reverted my changes twice !! It is very annoying.

[rws]

What. No way.

[vdelecroix]

Replying to rws:

What. No way.

Yes you did. But, my mistake, only once. Have a look: ​http://trac.sagemath.org/ticket/16137?action=diff&version=8. It might really be that we were editing the ticket at the same time and something bad happened. I will roll back the previous version.

[rws]

Replying to vdelecroix:

I will roll back the previous version.

Yes, please. Apparently, I opened the 'Modify ticket' form without editing, you saved your change, then (after display of the yellow warning) I saved my comment, and with it the content of the Modify ticket form. Sorry.

[vdelecroix]

Replying to rws:

Replying to vdelecroix:

I will roll back the previous version.

Yes, please. Apparently, I opened the 'Modify ticket' form without editing, you saved your change, then (after display of the yellow warning) I saved my comment, and with it the content of the Modify ticket form. Sorry.

It is a bit strange that there is no warning that forbid you to add changes from version 6 when 7 is the current one... No problem, the previous version is back.

[mantepse]

Replying to rws:

Where could such an overview (of the hierarchy of formal power series and sequences) be found?

You can find some references in ​http://arxiv.org/abs/math/0702086. But this is certainly by no means complete.

[mantepse]

I very much like the new description, nothing to add...

[mantepse]

Hi there! Is there any news on this front? I'm especially interested because of the connection with #15673...

[MatthieuDien]

Replying to mantepse:

Hi there! Is there any news on this front? I'm especially interested because of the connection with #15673...

I should work on it but I did not have much time since the Sage Days :s

I will work on it during September (I hope).

[mantepse]

Great! No hurry, though...

[MatthieuDien]

Hi there !

I propose a draft of code for 'lazy_list_from_iterator' and 'lazy_list_from_fun'. Currently, the file is composed of three class : one abstract class (but I don't know how to precise this more formally in Python / Cython / Sage) to facorize the code between lazy_list_from_iterator and lazy_list_from_fun.

I have to do choices :

• to define lazy list with function I propose to use a fonction which takes 2 arguments : the rank of the element to compute and all the already computed elements
• Currently, the _add_ method force the computation of all the elements : that's very annoying for not finite iterator. I suppressed it, for the moment.

Give me feedback !

Thanks

---

New commits:

​b7a58c2	work in progress
​37e6768	work in progress

[mantepse]

Comments (IMPORTANT: I have hardly any understanding of python/cython necessities, so some of these may be very naive or stupid)

1.) Concerning the *original* lazy_list, I would have expected that

sage: from sage.misc.lazy_list import lazy_list
sage: l = lazy_list(Primes())
sage: l[:100]

returns a list, not a lazy list. (I'm aware of l[:100].list(), but this seems inconsistent: l[0] also returns an element, not a lazy list)

Do you know a reason for this decision? Possibly it's more practical, right?

2.) Concerning the *new* lazy_list some things clearly don't work:

sage: from sage.misc.lazy_list import lazy_list_from_iterator
sage: from itertools import count
sage: l2 = lazy_list_from_iterator(count()); l2
lazy list [0, 1, 2, ...]
sage: l2[:10]
(0, 10, 1)
sage: l2[10]
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-8-02ea92939ca1> in <module>()
----> 1 l2[Integer(10)]

/home/rubey/sage-lazy_list/local/lib/python2.7/site-packages/sage/misc/lazy_list.so in sage.misc.lazy_list.lazy_list_from_iterator.__getitem__ (build/cythonized/sage/misc/lazy_list.c:6074)()

TypeError: 'int' object is not iterable

3.) Yes, I think that lazy_list_from_fun (besides: I would prefer lazy_list_from_function) should do precisely as you say. Currently, it doesn't: I would have expected the following to return a lazy list full of empty lists...

sage: l3 = lazy_list_from_fun(lambda a, b: b); l3
lazy list [[[...], [...], [...], [...]], [[...], [...], [...], [...]], [[...], [...], [...], [...]], ...]

4.) There are now two entry points: lazy_list_from_fun and lazy_list_from_iterator. I would expect that in the end there is also a general purpose constructor which decides what to use depending on the type of the argument, right?

[vdelecroix]

Hello,

Cool. Thanks Matthieu!

1) Please use complete names lazy_list_from_function and not abreviations. (see also item 3 of Martin)

2) For your specifications, I really do not think it is the best way to do. Very often you have functions that update *many* values at a time (think about Newton method, or substitutively defined sequences). I would prefer much more lazy_list_from_function whose argument would be a function f(computed_values) and which would update the list computed_values with one iteration of the algorithm (and return nothing or possibly an error code). And it has no sense to send the size of the cache to that function (since it is a list and a list knows its length).

3) I think we need more classes (I am not convinced by all names). Some of them might be implemented in further tickets

lazy_list: abstract class
 |
 +-- lazy_list_periodic: ultimately periodic lazy list (attributes=two lists)
 |
 +-- lazy_list_explicit: (attribute=function n-> u_n)
 |
 +-- lazy_list_concatenation: a concatenation of a finite liste and a lazy list
 |
 +-- lazy_list_slice: a slice of another lazy list
 |
 +-- lazy_list_with_cache: a cache management
      |
      +-- lazy_list_from_iterator: the old lazy_list
      |
      +-- lazy_list_from_function: update function (basically what you did)

4) we need a unique entry point for all these classes which must be of course lazy_list.

5) In the old implementation lazy_list were immutable. It has the advantage of having shared slices. On the other hand it is annoying because they are immutable and hence it will be forbidden to have operations like "f += 1" without a (light) copy.

Vincent

[mantepse]

Replying to vdelecroix:

Cool. Thanks Matthieu!

a second that! Sorry about not having mentioned that earlier!

2) [...] I would prefer much more lazy_list_from_function whose argument would be a function f(computed_values) and which would update the list computed_values with one iteration of the algorithm (and return nothing or possibly an error code). And it has no sense to send the size of the cache to that function (since it is a list and a list knows its length).

OK, I didn't know that python's lists know their length, so +1

3) I think we need more classes

I think we should try to avoid redundancy. I guess, redundancy will be obvious once coded...

However, I also thought that something like lazy_list_explicit would be very useful. I'm not sure: is turning on caching for a function in python easy enough so that a cached variant of this would not make sense?

5) In the old implementation lazy_list were immutable. It has the advantage of having shared slices. On the other hand it is annoying because they are immutable and hence it will be forbidden to have operations like "f += 1" without a (light) copy.

At least for the applications I have in mind, I think immutability is fine. For example, we will have lazy formal power series, and I certainly do not want to make assignments to those possible. (Think of students who prove to me that exp(z) equals 2 :-)

Martin

[mantepse]

Another comment: I just killed my sage session by asking for the list of all integers. Is there a possibility to make .list() interruptable?

Martin

[mantepse]

I do not understand what normalize_slice does. If I pass an integer, I get that integer plus one. Is this intentional?

[vdelecroix]

Replying to mantepse:

Replying to vdelecroix:

3) I think we need more classes

I think we should try to avoid redundancy. I guess, redundancy will be obvious once coded...

However, I also thought that something like lazy_list_explicit would be very useful. I'm not sure: is turning on caching for a function in python easy enough so that a cached variant of this would not make sense?

yes, but right now only in Sage:

sage: f = lambda n: n*(n+1)/2
sage: f_cached = cached_function(f)
sage: f_cached(10)
55
sage: f_cached.get_cache()
{((10,), ()): 55}

[git]

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

​a2ac160	rename lazy_list_from_fun to lazy_list_from_function
​46503af	fix the __getitem__ method of lazy_list_from_iterator

[mantepse]

Thanks for the update! lazy_list_from_iterator seems fine now. Could you nevertheless say what normalize_slice does?

For lazy_list_from_function I now get:

sage: from sage.misc.lazy_list import lazy_list_from_function
sage: from itertools import count
sage: f = lazy_list_from_function(lambda a, b: a)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-96-f1659b043f2a> in <module>()
----> 1 f = lazy_list_from_function(lambda a, b: a)

/home/rubey/sage-lazy_list/local/lib/python2.7/site-packages/sage/misc/lazy_list.so in sage.misc.lazy_list.lazy_list_from_function.__init__ (build/cythonized/sage/misc/lazy_list.c:6520)()

AttributeError: 'sage.misc.lazy_list.lazy_list_from_function' object has no attribute 'fun'

[mantepse]

For lazy_list_from_function I now get: [...]

OK, that was easy to fix, in the pxd the class was still named lazy_list_from_fun. I actually replaced all occurrences of fun by function in both files, to obtain uniform coding style.

However, it appears that I cannot push my changes. What should I do?

[vdelecroix]

Replying to mantepse:

For lazy_list_from_function I now get: [...]

OK, that was easy to fix, in the pxd the class was still named lazy_list_from_fun. I actually replaced all occurrences of fun by function in both files, to obtain uniform coding style.

However, it appears that I cannot push my changes. What should I do?

What do you mean? One solution is to push to another branch.

Vincent

[mantepse]

Thanks for the hint, I pushed to a new branch public/lazy_list_from_various_input_data. Could you check whether this worked?

[vdelecroix]

Replying to mantepse:

Thanks for the hint, I pushed to a new branch public/lazy_list_from_various_input_data. Could you check whether this worked?

No. The branch does exist but the last commit is ​46503af (i.e. not different from Matthieu's one). Did you forgot to commit your changes? What does git log tell you?

[mantepse]

Oh no! I thought git push would be enough... Could you check again now, please...

[vdelecroix]

You can have a look directly there: ​http://git.sagemath.org/sage.git/log/?h=public/lazy_list_from_various_input_data and see that there is no other commit beyond ​46503af. If after a git log you do not see your commit on your computer, there is no way that something appear after a push on the remote one.

[mantepse]

It worked! Many thanks for your patience! I should have rtfm :-)

[MatthieuDien]

New commits:

​258eee2

replace fun by function

[MatthieuDien]

Thanks for your feedback and your help. I have also set the ticket's branch to the public one.

[mantepse]

Great! I'm now going to make function take one argument only, and I volunteer to clean up the examples there (but probably not right now).

Do you think it's possible to have list comprehensions for lazy_list? FriCAS allows things like:

[i^2 for i in 1.. | prime? i]

Otherwise, we need at least a function that makes a new lazy_list by applying a function (lazy_list_explicit might do) but also a way to select members from a lazy_list.

[git]

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

​530b21b

make function accept only the previous values as argument

[mantepse]

Although less elegant, we can do the following:

sage: m = lazy_list_from_function(len); m
lazy list [0, 1, 2, ...]
sage: m2 = lazy_list_from_iterator(ifilter(is_prime, m)); m2
lazy list [2, 3, 5, ...]
sage: m3 = lazy_list_from_iterator(imap(lambda a: a^2, m2)); m3
lazy list [4, 9, 25, ...]

Now I'm not quite sure anymore what the difference between an iterator and a lazy list is precisely. Is it just the caching? How do we want to interact with itertools?

[mantepse]

From a brief look at itertools, it seems to me that we should revisit the design decisions. If I understand correctly, itertools provides all the operations we might want, except caching and therefore also the functionality of lazy_list_from_function.

Looking at the example in my previous comment, I'm not quite satisfied with the interaction of lazy_list and itertools yet. I'm a bit surprised that itertools provides functions, not methods.

Edit: I just found a long discussion about the design of iterators, ​https://mail.python.org/pipermail/python-3000/2006-November/004301.html.

[mantepse]

Hi there,

I just checked that, in a very rudimentary way, we can define lazy lists recursively, as follows:

sage: from sage.misc.lazy_list import *
sage: from itertools import *
sage: l = lazy_list_recursive(cache = [[]])
sage: l.define(imap(lambda a: [1] + a, l))
sage: l[0], l[1], l[2]
([], [1], [1, 1])

I also had to realise that itertools.product is not particularly intelligent what concerns infinite streams...

I'll take a break now and wait for feedback. In summary, it now seems to me that we want lazy_list to be

• a model for "infinite lists", i.e., support slicing
• play as well as possible with iterators
• provide functionality that itertools cannot provide:
  • next depending on the previous values
  • possibly recursive definitions
  • what else?
• what else?

In particular, should lazy_list additionally provide wrappers for the functionality in itertools? Currently, I don't think so.

[MatthieuDien]

Hi there,

I found the bug that avoid me to connect on Sage trac (I used my phone's connection). So, I copy the message which I sent by email.

@Martin The diference bewteen lazy_list and iterator is not only the caching. There is also the way to compute an element : if you want the nth element of an iterator you have to compute the (n-1) previous ones, for lazy_list (currently the implementation does not do this but it should in close future) the goal is to compute elements only if it obligatory. For example, you don't want to compute all the coeffcients of a serie if at the end, you will only use the odd (or even) part. Concerning recursive definition, we have to allow it but the implementation must not be recursive because recursion is extremly expensive in Python.

@Vincent To implement this, I need to overload the _fit method and pass it in "cdef mode". I just have a question : why, in the iterator's class, do you use update_cache_up_to and not _fit ?

And finally, to answer to Martin about "what is _normalize_slice ?", _normalize_slice means nothing it is just a piece of code that I wanted to factorize. In fact I should factorize directly __getitem__ by adding a method which have to create a slice (last line of code __getitem__).

[MatthieuDien]

Therefore, the answer of Martin :

@Martin The diference bewteen lazy_list and iterator is not only the caching. There is also the way to compute an element : if you want the nth element of an iterator you have to compute the (n-1) previous ones, for lazy_list (currently the implementation does not do this but it should in close future) the goal is to compute elements only if it obligatory.

For example, you don't want to compute all the coeffcients of a serie if at the end, you will only use the odd (or even) part.

Excellent point!

You made me think again about the name - I don't particularly like "lazy_list". Of course, from a math point of view I'd call it "Sequence". However, I just discovered that this is already taken in Sage for something related, although not identical.

I then discovered "Family", which seems the same but a bit more general. In fact, "lazy_list" is a Family having index set natural numbers.

Shouldn't we merge these two concepts, at least in the long run?

Concerning recursive definition, we have to allow it but the implementation must not be recursive because recursion is extremly expensive in Python.

I'm not quite sure what you mean. There is hardly any implementation. I want that definitions like s = f(s), where "s" is a "lazy list" determined by this equation, can be easily typed into sage.

Thus, I think of it as a convenience feature, for rapid prototyping. Its usefulness lies in the fact that it's very general. Thus, from the user's perspective, I wouldn't expect it to do any fancy term-rewriting.

And finally, to answer to Martin about "what is _normalize_slice ? ", _normalize_slice means nothing it is just a piece of code that I wanted to factorize. In fact I should factorize directly `getitem ` by adding a method which have to create a slice (last line of code __getitem__).

OK, thanks!

Best,

Martin

[mantepse]

Should we ask about the desired relationship between Family, Sequence and lazy_list on sage-devel?

[MatthieuDien]

Replying to mantepse:

Should we ask about the desired relationship between Family, Sequence and lazy_list on sage-devel?

There is already a ticket for that #16107 but we can ask on sage-devel for more feedback.

Concerning Family, I read documentation and code. That seems cool but not the same goal that lazy_list, especially concerning the definitions of such objects (Family can only be defined by iterable objects).

[mantepse]

Thanks for pointing out #16107, I added the LazyPowerSeries keyword there!

I don't understand your assessment of Family though, why should it have a different goal? At the very least, lazy_list should inherit from Family, no?

[git]

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

​9b4d3ac	lazy_list_explicit implemented
​daa5652	update docstrings

[git]

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

​2cf1d24	fix list() method for lazy_list_explicit
​0ea1a3e	fix list() method doctest for lazy_list_explicit
​d482706	reogarnisation of class hierarchy

[git]

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

​9790b69

implementation of lazy_list_explicit and its iteratorand some reorganization of the class hierarchy

[git]

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

​19cbfd2

fix a bug with cached lazy_list

[git]

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

​6f7cfd9

concatenation with list implemented

[MatthieuDien]

Hi there,

I implemented almost everyting. I still have to :

• make the factory
• do some factorizations of code
• document and test the code

I think that is the moment to ask you to try this implementation and tell me if there are any problems with the implementations or the design choices.

Best

Matthieu

[mantepse]

Hi Matthieu!

I watched you work :-) THANK YOU!!!

Right now I have only two comments:

1.) I think the naming scheme for the classes should be changed:

a) from_iterator is fine b) from_function is misleading. In fact, in analogy to a) I would expect this class to do precisely what explicit does. Isn't it precisely recursive? c) explicit should in my opinion be named from_function d) periodic is fine

I also would suggest to change stopped to terminating or finite.

2.) I still don't understand the relationship with Family. I guess it's fine not to consider Sequence right now, but I think the relationship with Family should be clarified. As a concrete question: should Family use lazy_list for sequences?

[vdelecroix]

Hi Matthieu,

It would be nice to write documentation in the classes, particularly

• what is the input
• how does it work internally

It would help me to read your code.

Do you really want to keep the start, stop, step for all classes? I would rather add a class lazy_list_slice which does the job.

I do not understand anything to lazy_list_explicit. Why do you use a cache mechanism for it? Moreover, the following

cdef int update_cache_up_to(self, Py_ssize_t i) except -1:
    while PyList_GET_SIZE(self.cache) <= i:
        PyList_Append(self.cache, None)

is definitely useless since you can use the self.cache.extend([None]*length) which would be much faster.

Are you sure you understand the point of Py_INCREF(object)? If you call it when you should not, it implies that the object will *never* be garbage collected. The call to this function is generally not needed in Cython file.

Now Cython supports iterator, i.e. you can write

cdef class MyClass(X):
    def __iter__(self):
        cdef Py_ssize_t i
        for i in range(self.x,self.y,self.z):
            yield self.cache[i]

So I would remove all iterators "XYZ_iterator" and implement directly the methods __iter__ when possible.

If you add the line

include "sage/ext/stdsage.pxi"

at the begining of the file you have access to better then "isinstance" to test the type of an object

PY_TYPE_CHECK(object)
PY_TYPE_CHECK_EXACT(object)

I have much more comments. I could also edit directly the file.

Vincent

[MatthieuDien]

Hi there,

Thanks you very much for the answers. I will try to justify some of my choices and answer to some of your new questions.

Replying to vdelecroix:

Hi Matthieu,

It would be nice to write documentation in the classes, particularly

• what is the input
• how does it work internally

It would help me to read your code.

Yes, I have to do this

Do you really want to keep the start, stop, step for all classes? I would rather add a class lazy_list_slice which does the job.

I agree.

I do not understand anything to lazy_list_explicit. Why do you use a cache mechanism for it? Moreover, the following

cdef int update_cache_up_to(self, Py_ssize_t i) except -1:
    while PyList_GET_SIZE(self.cache) <= i:
        PyList_Append(self.cache, None)

is definitely useless since you can use the self.cache.extend([None]*length) which would be much faster.

Thanks for the hint, I did not know extend. Concerning the usage of a cache mechanism for lazy_list_explicit, it is because the computation of a list's cell can be long (for example when you compute the Cauchy's product during a lazy series' multiplication). Then, the cache mechanism allows to compute only one time the value contained in a cell.

Are you sure you understand the point of Py_INCREF(object)? If you call it when you should not, it implies that the object will *never* be garbage collected. The call to this function is generally not needed in Cython file.

For this point, I have to check that the value is garbage collected, but without this instruction, the value is garbage collected instantly.

Now Cython supports iterator, i.e. you can write

cdef class MyClass(X):
    def __iter__(self):
        cdef Py_ssize_t i
        for i in range(self.x,self.y,self.z):
            yield self.cache[i]

So I would remove all iterators "XYZ_iterator" and implement directly the methods __iter__ when possible.

Ok, I did not know this. I will benchmark the both approaches.

If you add the line

include "sage/ext/stdsage.pxi"

at the begining of the file you have access to better then "isinstance" to test the type of an object

PY_TYPE_CHECK(object)
PY_TYPE_CHECK_EXACT(object)

Thanks for the hint.

I have much more comments. I could also edit directly the file. Vincent

Replying to mantepse:

Hi Matthieu!

I watched you work :-) THANK YOU!!!

Right now I have only two comments:

1.) I think the naming scheme for the classes should be changed:

a) from_iterator is fine b) from_function is misleading. In fact, in analogy to a) I would expect this class to do precisely >what explicit does. Isn't it precisely recursive?

from_function is recursive yes. Do you have an idea about the name (I am really bad to choose name ..) ?

c) explicit should in my opinion be named from_function d) periodic is fine

I also would suggest to change stopped to terminating or finite.

finite looks better to me, if Vincent agrees ?

2.) I still don't understand the relationship with Family. I guess it's fine not to consider >Sequence right now, but I think the relationship with Family should be clarified. As a concrete >question: should Family use lazy_list for sequences?

I think that this question deserves a new ticket because it can involve modification of the code in an other part of Sage. We can work on it if you want.

Matthieu

[git]

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

​8457edf

iterators replaced by generators (yield keyword), isinstance changed by PY_TYPE_CHECK in __getitem__

[git]

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

​1ac24d5

remove 'info' method and rename class lazy_list by abstract_lazy_list

[MatthieuDien]

Hi there,

I did some of the proposed changes :

• I removed the iterators and use 'yield' instead
• I changed is_instance by PY_TYPE_CHECK in the getitem method to be faster
• I removed the "info" method

Concerning "lazy_list_slice", I have changed my mind : I think it is not necessary because almost all the code managing (start, stop, step) are in the abstract class and the remaining code is dependant of the different class.

At the end, what do you think about my explanation of why lazy_list_explicit must have a cache ?

Matthieu

PS : Doctests will be coming ;)

[tmonteil]

Hi, shouldn't this class go to src/sage/data_structures ?

[dkrenn]

What is the plan for/status of this the lazy lists of this ticket? (no progress since 10 month now)

[mantepse]

Although I'd also love to see something like this finally be done (I really miss FriCAS here!), I'm afraid that I'm not able to contribute code here. However, I'm willing to learn, and I'm willing to test.

[vdelecroix]

Hello,

I don't know what Matthieu is currently doing. Note that I have a similar proposal for infinite words in #19620 (with branch whose tests pass). In that case the underlying data is not a list but a char * from C. Though, the idea is exactly the same. It would be nice to have the same conventions in both cases.

I can provide an implementation for this ticket based on the architecture #19620. We might see later on whether power series needs some raw C datatype as well. Are you willing to review Daniel?

Vincent

[vdelecroix]

Other question: do we want a mutability / immutability flag (slice will share memory only if it is set as immutable)?

[dkrenn]

Replying to vdelecroix:

I can provide an implementation for this ticket based on the architecture #19620.

Ok, what does this mean exactly? (I.e., do you drop the branch attached to this ticket completely and use your own code (from #19620)? Or simply "merge" this in some way?)

no drop no merge. Simply follow the same architecture. We can figure out later on if it makes sense to have a common base class.

Are you willing to review Daniel?

Yes. Good!

[dkrenn]

Replying to dkrenn:

Replying to vdelecroix:

I can provide an implementation for this ticket based on the architecture #19620.

Ok, what does this mean exactly? (I.e., do you drop the branch attached to this ticket completely and use your own code (from #19620)? Or simply "merge" this in some way?)

no drop no merge. Simply follow the same architecture. We can figure out later on if it makes sense to have a common base class.

Ok, looking forward to your code (I've already had some look at the existing code of this ticket (and very briefly at #19620)...and I think I like the direction where it is going...)

[vdelecroix]

You can now create lazy lists from iterator and functions. And it is dead simple to create a new class inheriting from lazy_list_abstract (there is an example in the documentation).

[vdelecroix]

New commits:

​1acf92e	Trac 16137: move lazy_list into data_structures
​6d53317	Trac 16137: fix doctests and import
​e9ee148	Trac 16137: refactor and extend lazy lists
​5dac074	Trac 16137: fix class name change lazy_list -> lazy_list_abstract

[dkrenn]

I made a couple of smaller/minor changes during review; need cross-review. Additionally the following should be addressed/discussed:

1. _new_slice and other private methods: _new_slice_ (underscore at the end as well)?

2. description, INPUT/OUTPUT of lazy_list is missing

3. should list(cache) appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant that cache really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description of lazy_list)?

4. _fit, last example: looks incomplete

5. __call__: write oneline description

6. update_cache_up_to everwhere: describe return value

7. :class:`lazy_list` appears a couple of times, but lazy_list is not a class anymore

8. note-block in lazy_list_from_iterator description should (also) be in lazy_list

9. cache in INPUT-blocks: everywhere mention that this is a list (see also above)

10. __reduce__: oneline description missing

11. ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?

12. ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?

Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple yield in __iter__ now does the job. I adapted it so that it works. Please cross-review.

PS: What about the authorship of this ticket now? MatthieuDien created the original code, that was cherry-picked by me; I've integrated it here and made the necessary changes. I would include us two in the ticket-author field unless you think the changes were too small... (I this case I don't mind)

---

New commits:

​40851bd	Trac 16137 review: update doc-indices
​bd68b5a	Trac 16137 review: some smaller changes
​c30746f	return value of _fit
​f092fc3	partial cherr-pick of 8457edf: iterators replaced by generators; make this work
​8cee245	Merge branch 'u/dkrenn/16137' into u/vdelecroix/16137

[dkrenn]

Two more issues:

13. Since the code was moved from sage.misc to sage.data_structures, do we need a deprecation?

14. Since lazy_lists are immutable, wouldn't the name lazy_tuple be more suitable? To rephrase: Help me understand, what makes it a list and not a tuple?

[mantepse]

Concerning 14., I would vote for lazy_stream or even just stream, because of ​https://en.wikipedia.org/wiki/Stream_(computing). There currently is a class Stream in the species code, which is really a relatively poor implementation of what the code in this ticket does, and I'm quite eager to replace it.

[dkrenn]

Replying to mantepse:

Concerning 14., I would vote for lazy_stream or even just stream, because of ​https://en.wikipedia.org/wiki/Stream_(computing). There currently is a class Stream in the species code, which is really a relatively poor implementation of what the code in this ticket does, and I'm quite eager to replace it.

stream sounds good to me (from the definition of stream from your wiki link, it seems that they are lazy by default, so no need to put that into the name).

[vdelecroix]

Lazy lists might implement a mutable/immutable protocol in the future. In which case the reference to the Python data structure would be appropriate. And it is better to not change the name twice.

Stream is a technical computer term mostly used for communications. As it is said on wikipedia this notion is related to time: it is a "flux of information". It has the relevant menaing in the language Scheme (which is as far as I know, marginally used among mathematicians). I strongly disaprove its usage here.

Other name like lazy_sequence are already too mathematical.

Unless you have a strong need (and arguments) to change the name I am opposed to it.

[dkrenn]

Replying to vdelecroix:

Lazy lists might implement a mutable/immutable protocol in the future.

Ok, then let's keep the name.

[vdelecroix]

New commits:

​bd2d1ac	Trac 16137: deprecated import from sage.misc.lazy_list
​0e01c63	Trac 16137: revision 1
​f1b8d64	Trac 16137: revision 2

[vdelecroix]

Hola Daniel,

Thanks!

Replying to dkrenn:

I made a couple of smaller/minor changes during review; need cross-review. Additionally the following should be addressed/discussed:

1. _new_slice and other private methods: _new_slice_ (underscore at the end as well)?

I really don't care. But I do not see why it should be with 2 underscores. For me the double underscore methods are saying "I want to interact with the rest of Sage and cares about coercions". Like _add_, _cmp_ etc. But it might be a personal feeling.

2. description, INPUT/OUTPUT of lazy_list is missing

done.

3. should list(cache) appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant that cache really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description of lazy_list)?

This is a feature you might actually want to use. In the constructors __init__ method we clearly want to use the reference to the same list (I made it clear in the doc). In the factory lazy_list I am in favour of copying and adapted the code accordingly.

4. _fit, last example: looks incomplete

Actually not... I had some non trivial error. This method is subtle as for finite lazy_list you want to avoid the StopIterationbranch. Though I added a _info().

5. __call__: write oneline description

done

[vdelecroix]

6. update_cache_up_to everwhere: describe return value

The return value was not meaningful (except for Python error handling). I now specified a 0/1 code return and used it in _fit.

7. :class:`lazy_list` appears a couple of times, but lazy_list is not a class anymore

done

8. note-block in lazy_list_from_iterator description should (also) be in lazy_list

I moved around a lot of documentation. Tell me if there is still a problem.

9. cache in INPUT-blocks: everywhere mention that this is a list (see also above)

done.

10. __reduce__: oneline description missing

What for? A user should not care about it. A developer knows what this function is.

11. ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?

I reformulated the ticket description. I think this ticket should focus on the lazy lists with a cache.

[vdelecroix]

12. ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?

Actually you could do it by inheritance and implementing _new_slice. There you have access to the cache with the method get. See the Thue-Morse example.

I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?

Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple yield in __iter__ now does the job. I adapted it so that it works. Please cross-review.

Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if i is a Py_ssize_t. I will investigate this and see if I can fix Cython.

[vdelecroix]

Curiously trac freezes when I tried to send all messages in one. Well I splitted it in 3.

[dkrenn]

Replying to vdelecroix:

Curiously trac freezes when I tried to send all messages in one. Well I splitted it in 3.

I also sometimes have this problem and no idea what it is (tried to find out, but failed...)

---

New commits:

​80aad4d

Trac 16137: another reviewer commit

[dkrenn]

Replying to vdelecroix:

Replying to dkrenn:

1. _new_slice and other private methods: _new_slice_ (underscore at the end as well)?

I really don't care. But I do not see why it should be with 2 underscores. For me the double underscore methods are saying "I want to interact with the rest of Sage and cares about coercions". Like _add_, _cmp_ etc. But it might be a personal feeling.

Ok, then let's keep them as they are.

3. should list(cache) appear in the code so that the cache cannot be changed 8accidentally) from outside since only a reference of the list is passed? This would also allow e.g. tuples as well. Or is it meant that cache really specifies the cache itself and not only the cached elements. If so, can we make this clear in the doc somewhere (description of lazy_list)?

This is a feature you might actually want to use. In the constructors __init__ method we clearly want to use the reference to the same list (I made it clear in the doc). In the factory lazy_list I am in favour of copying and adapted the code accordingly.

Good solution.

[dkrenn]

6. update_cache_up_to everwhere: describe return value

The return value was not meaningful (except for Python error handling). I now specified a 0/1 code return and used it in _fit.

0/1 vs. False/True: isn't there a bint or something like that?), in particular, since update_cache_up_to is public. If I would change them...

8. note-block in lazy_list_from_iterator description should (also) be in lazy_list

I moved around a lot of documentation. Tell me if there is still a problem.

Looks good now.

11. ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?

I reformulated the ticket description. I think this ticket should focus on the lazy lists with a cache.

Yes, I think so as well. (I don't see any change in the ticket description)

[dkrenn]

12. ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?

Actually you could do it by inheritance and implementing _new_slice. There you have access to the cache with the method get. See the Thue-Morse example.

I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?

Since it is already there now, I would keep it. However, I won't need this feature (at this point), so I don't mind if it is removed.

Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple yield in __iter__ now does the job. I adapted it so that it works. Please cross-review.

Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if i is a Py_ssize_t. I will investigate this and see if I can fix Cython.

Ok, thank you.

15. lazy_list_abstract vs. for example lazy_list_generic: I find it a bit strange to instantiate something with "abstract" in its name.

16. beginning vs. inital_values: I have a slight (but not strong) preference for the latter.

I've also made some minor changes; please cross-review.

[dkrenn]

Is there a reason, why slices are not a separate class? Is it a design choice? Or simply because the earlier version did so? (I am trying to extend sublist extraction of lazy lists; that's why it comes to my mind).

[vdelecroix]

Replying to dkrenn:

6. update_cache_up_to everwhere: describe return value

The return value was not meaningful (except for Python error handling). I now specified a 0/1 code return and used it in _fit.

0/1 vs. False/True: isn't there a bint or something like that?), in particular, since update_cache_up_to is public. If I would change them...

Nope nope. It can be -1 if a Python error occurrs (but you will not see it). We can not use bint here.

[vdelecroix]

Replying to dkrenn:

12. ticket-description "an update function": this was addressed here, but when I see this correctly with a different interface as in the original code. "a function that given a buffer..." we do not have that here. I am fine with it as it is, but IMHO the description of the ticket does not fit anymore. Should this be a separate ticket as well? Maybe also specifying the old branch there to not forget about it?

Actually you could do it by inheritance and implementing _new_slice. There you have access to the cache with the method get. See the Thue-Morse example.

I added 20 lines of code to do it from a function. There is a Thue-Morse bis example which uses this path. But I really find this version artificial. If you have an "update function" you generally need some extra variables that are not necesseraily easily deduced from the length of the list. Moreover it is very fragile (since the update function might modify the begining of the list without notice). What do you think? Should I remove it?

Since it is already there now, I would keep it. However, I won't need this feature (at this point), so I don't mind if it is removed.

Moreover, I've did a partial cherry picking of part of the old code of this ticket: the two iterators are removed and a simple yield in __iter__ now does the job. I adapted it so that it works. Please cross-review.

Great! Thanks. I modified it though. Cython is somehow confused with the range stuff if i is a Py_ssize_t. I will investigate this and see if I can fix Cython.

Ok, thank you.

15. lazy_list_abstract vs. for example lazy_list_generic: I find it a bit strange to instantiate something with "abstract" in its name.

Much better. I changed it. I was not a fan of the abstract as well.

16. beginning vs. inital_values: I have a slight (but not strong) preference for the latter.

Changed as well.

[vdelecroix]

Replying to dkrenn:

Is there a reason, why slices are not a separate class? Is it a design choice? Or simply because the earlier version did so? (I am trying to extend sublist extraction of lazy lists; that's why it comes to my mind).

That is a good design question. I have two reasons:

• avoid implementing twice __getitem__ and get
• (not supported at the moment) the user might want to inherit from lazy_list_generic in such way that slices are also instances of the inherited object. In that case we could not make it a distinct class.

[vdelecroix]

New commits:

​85d99c0

Trac 16137: revision 3

[dkrenn]

Replying to vdelecroix:

0/1 vs. False/True: isn't there a bint or something like that?), in particular, since update_cache_up_to is public. If I would change them...

Nope nope. It can be -1 if a Python error occurrs (but you will not see it). We can not use bint here.

Ok, thank you for the clearification.

---

New commits:

​72a212c

Trac 16137 review: fix ReST and remove unnecessary iter

[dkrenn]

Replying to vdelecroix:

That is a good design question. I have two reasons:

• avoid implementing twice __getitem__ and get
• (not supported at the moment) the user might want to inherit from lazy_list_generic in such way that slices are also instances of the inherited object. In that case we could not make it a distinct class.

Ok.

[dkrenn]

LGTM, positive whenever a patchbot confirms no errors.

[vdelecroix]

Thanks for the careful review.

@Martin: if you start reimplementing streams using lazy list, please put me in cc.

[mantepse]

This is wonderful!

Yes, today I started to recollect what I want to do. I'm not sure whether there is any need for another object "stream". Rather, I think that the next step is a good lazy power series implementation.

The main complication is that it is useful to define power series recursively, as in

sage: sage: L = LazyPowerSeriesRing(QQ)
sage: one = L(1)
sage: monom = L.gen()
sage: s = L()
sage: s._name = 's'
sage: s.define(one+monom*s*s)
sage: [s.coefficient(i) for i in range(6)]
[1, 1, 2, 5, 14, 42]

In the current code, this is done by keeping track of the "approximate order" of the power series. Note that there are no initial values provided by the user.

An earlier attempt was done by Mike Hansen in #15673, so I guess it's best to continue discussion there. I also have code (for FriCAS, however) that generalizes this using a different approach, via undetermined coefficients and given initial values.

I guess that I am a terrible python programmer, but I think I can give it a try. I would start with what Mike has written, but first I want to recollect how these recursive definitions worked.

[vdelecroix]

It is perfectly fine to use lazy_list recursively. With your example one option is

from sage.data_structures.lazy_list import lazy_list_generic
class MySerie(lazy_list_generic):
    def __init__(self):
        lazy_list_generic.__init__(self, cache=[1])
        self._n = 0
    def _new_slice(self):
        n = self._n
        self._n += 1
        return [sum(self.get(i) * self.get(n-i) for i in range(n+1))]

then

sage: f = MySerie()
sage: f[0]
1
sage: f[1]
1
sage: f[2]
2
sage: f[3]
5
sage: f[4]
14
sage: f[5]
42

[mantepse]

Yes, I know. The point is that the current user interface does this automatically, and with quite a natural syntax.

[jdemeyer]

Why is this moved to data_structures? I don't think that "lazy list" is a data structure. And I don't want data_structures to become yet another "misc".

[jdemeyer]

Minor comments:

1. insert the standard copyright template.

2. remove this ugly commented-out code:

   # in types.pxd
   #    bint PyType_Check(object o)
   #    bint PyType_CheckExact(object o)
   # include "sage/ext/python_iterator.pxi"
   

3. remove the unused

   from cpython.object cimport *
   

4. remove the unused

   from libc import limits
   

[vdelecroix]

Replying to jdemeyer:

Why is this moved to data_structures? I don't think that "lazy list" is a data structure. And I don't want data_structures to become yet another "misc".

I don't care. I did it because of comment:62. What is a data structure? Just excluding lazy list will not help me to know what should I found out there.

---

New commits:

​429be58

Trac 16137: removed import + copyright statement

[dkrenn]

Replying to jdemeyer:

Why is this moved to data_structures? I don't think that "lazy list" is a data structure. And I don't want data_structures to become yet another "misc".

I don't know about what the motivation of moving it was, but I disagree that it is *not* a data structure. list is a data structure for sure, so a variant of it, namely our lazy list, is it as well. The wikipedia says on "data structure" in its first sentence:

In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.

That's what we have, haven't we?

Why do you think it is not a data structure?

[jdemeyer]

Replying to dkrenn:

I don't know about what the motivation of moving it was, but I disagree that it is *not* a data structure. list is a data structure for sure, so a variant of it, namely our lazy list, is it as well.

Well, the "variant" adds something, but not in terms of the data structure. I would say that a lazy list is some kind of wrapper of a data structure, not a new data structure.

The wikipedia says on "data structure" in its first sentence:

In computer science, a data structure is a particular way of organizing data in a computer so that it can be used efficiently.

That's what we have, haven't we?

Not really. I wouldn't call a lazy list "a way of organizing data".

It you think it is, then essentially everything in Sage is a data structure.

[jdemeyer]

Data structures should be very basic low-level things. This "lazy list" is too specific and too much Python to fit that definition in my opinion.

[git]

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

​e2bae5e	Trac 16137: move back lazy lists to misc
​295a870	Trac 16137: fix changes in imports

[vdelecroix]

All right. Let it go back into where it was. Nobody should complain about something not being at its place in misc.

[dkrenn]

Replying to vdelecroix:

All right. Let it go back into where it was. Nobody should complain about something not being at its place in misc.

The two index.rst need to be reverted as well...

[git]

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

​daa9990

forgotten change import

[vbraun]

sage -t --long src/sage/misc/lazy_list.pyx
**********************************************************************
File "src/sage/misc/lazy_list.pyx", line 543, in sage.misc.lazy_list.lazy_list_generic._fit
Failed example:
    l._info()
Expected:
    cache length 0
    start        2
    stop         9223372036854775807
    step         3
Got:
    cache length 0
    start        2
    stop         2147483647
    step         3
**********************************************************************
1 item had failures:
   1 of  10 in sage.misc.lazy_list.lazy_list_generic._fit
    [204 tests, 1 failure, 0.05 s]

[vdelecroix]

right. 32 bits vs 64 bits. I am fixing the corresponding doctests.

[vdelecroix]

New commits:

​f1c6036	Trac 16137: merge Sage-7.0
​55a1918	Trac 16137: fixing a doctest and a constructor

[dkrenn]

Replying to vdelecroix:

right. 32 bits vs 64 bits. I am fixing the corresponding doctests.

As the first number in

stop         9223372036854775807    # 64-bit
stop         2147483648             # 32-bit

2^63-1, I believe that the second should be 2^31-1 = 2147483647. Unfortunately, I don't have a 32-bit system to test.

[dkrenn]

Replying to vdelecroix:

​f1c6036

Trac 16137: merge Sage-7.0

What was the reason for merging? Was there any conflict? BTW: You did not merge 7.0 into the branch but the other way round, i.e., you merged this ticket into 7.0 (like the release manager). This makes seeing the changes much more difficult, since the git specifications like HEAD^ or HEAD~3 all take the first parent, which now is not the original branch of this ticket anymore.

[git]

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

​f7960c1

Trac 16137: fixing a doctest and a constructor

[dkrenn]

Replying to git:

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

​f7960c1

Trac 16137: fixing a doctest and a constructor

Sorry for the delay (for some unknown reason I didn't got a notification about the commit; double-checked). Everything is fine now; thanks.