Opened 7 years ago

Closed 5 years ago

#16137 closed enhancement (fixed)

lazy_list from various input data

Reported by: MatthieuDien Owned by:
Priority: major Milestone: sage-7.1
Component: misc Keywords: LazyPowerSeries, lazy_list, days57
Cc: MatthieuDien, vdelecroix, nthiery, mantepse, rws Merged in:
Authors: Matthieu Dien, Vincent Delecroix, Daniel Krenn Reviewers: Daniel Krenn
Report Upstream: N/A Work issues:
Branch: f7960c1 (Commits, GitHub, GitLab) Commit: f7960c1038c1498eca8995a3e39e7c3a4f76e99e
Dependencies: Stopgaps:

Status badges

Description (last modified by vdelecroix)

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.

Change History (122)

comment:1 Changed 7 years ago by mantepse

  • Cc mantepse added

comment:2 follow-up: Changed 7 years ago by rws

  • Cc rws added
  • Description modified (diff)

comment:3 in reply to: ↑ 2 Changed 7 years ago by vdelecroix

  • Description modified (diff)

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.

comment:4 Changed 7 years ago by rws

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

comment:5 follow-ups: Changed 7 years ago by 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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 7 years ago by vdelecroix

  • Description modified (diff)

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

comment:7 Changed 7 years ago by vdelecroix

  • Description modified (diff)

comment:8 in reply to: ↑ 5 ; follow-ups: Changed 7 years ago by rws

  • Description modified (diff)

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?

comment:9 in reply to: ↑ 8 Changed 7 years ago by 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.

comment:10 follow-up: Changed 7 years ago by rws

What. No way.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 7 years ago by 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.

comment:12 in reply to: ↑ 11 ; follow-up: Changed 7 years ago by 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.

comment:13 in reply to: ↑ 12 Changed 7 years ago by vdelecroix

  • Description modified (diff)

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.

comment:14 in reply to: ↑ 8 Changed 7 years ago by 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.

comment:15 in reply to: ↑ 6 Changed 7 years ago by mantepse

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

comment:16 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:17 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:18 follow-up: Changed 7 years ago by mantepse

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

comment:19 in reply to: ↑ 18 Changed 7 years ago by 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).

comment:20 Changed 7 years ago by mantepse

Great! No hurry, though...

comment:21 Changed 7 years ago by MatthieuDien

  • Branch set to u/MatthieuDien/lazy_list_from_various_input_data

comment:22 Changed 7 years ago by MatthieuDien

  • Commit set to 37e67683e7a2f10152ba3a01b8aed508fe92f0f1

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:

b7a58c2work in progress
37e6768work in progress

comment:23 Changed 7 years ago by 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?

comment:24 follow-up: Changed 7 years ago by 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

comment:25 in reply to: ↑ 24 ; follow-up: Changed 7 years ago by 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

comment:26 Changed 7 years ago by 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

comment:27 Changed 7 years ago by mantepse

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

comment:28 in reply to: ↑ 25 Changed 7 years ago by 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}

comment:29 Changed 7 years ago by git

  • Commit changed from 37e67683e7a2f10152ba3a01b8aed508fe92f0f1 to 46503af91c0fb4b28f0b37b83182055734c6f0d9

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

a2ac160rename lazy_list_from_fun to lazy_list_from_function
46503affix the __getitem__ method of lazy_list_from_iterator

comment:30 follow-up: Changed 7 years ago by 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'

comment:31 in reply to: ↑ 30 ; follow-up: Changed 7 years ago by 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?

Last edited 7 years ago by mantepse (previous) (diff)

comment:32 in reply to: ↑ 31 Changed 7 years ago by 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

comment:33 follow-up: Changed 7 years ago by mantepse

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

comment:34 in reply to: ↑ 33 Changed 7 years ago by 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?

comment:35 Changed 7 years ago by mantepse

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

comment:36 Changed 7 years ago by 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.

comment:37 Changed 7 years ago by mantepse

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

comment:38 Changed 7 years ago by MatthieuDien

  • Branch changed from u/MatthieuDien/lazy_list_from_various_input_data to public/lazy_list_from_various_input_data
  • Commit changed from 46503af91c0fb4b28f0b37b83182055734c6f0d9 to 258eee2b4f14f42c2e7ac65d62e1d7fef66ed2a2

New commits:

258eee2replace fun by function

comment:39 Changed 7 years ago by MatthieuDien

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

comment:40 Changed 7 years ago by 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.

comment:41 Changed 7 years ago by git

  • Commit changed from 258eee2b4f14f42c2e7ac65d62e1d7fef66ed2a2 to 530b21b1a97012b1adfc244dad57250922f4f46c

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

530b21bmake function accept only the previous values as argument

comment:42 Changed 7 years ago by 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?

comment:43 Changed 7 years ago by 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.

Last edited 7 years ago by mantepse (previous) (diff)

comment:44 Changed 7 years ago by 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.

comment:45 Changed 7 years ago by 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__).

comment:46 Changed 7 years ago by 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

comment:47 follow-up: Changed 7 years ago by mantepse

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

comment:48 in reply to: ↑ 47 Changed 7 years ago by 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).

comment:49 Changed 7 years ago by 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?

comment:50 Changed 7 years ago by git

  • Commit changed from 530b21b1a97012b1adfc244dad57250922f4f46c to daa5652df3933bf1dc374bfcdfadb4707d0c2723

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

9b4d3aclazy_list_explicit implemented
daa5652update docstrings

comment:51 Changed 7 years ago by git

  • Commit changed from daa5652df3933bf1dc374bfcdfadb4707d0c2723 to d4827065218788bd6990aed6293536a29396fd54

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

2cf1d24fix list() method for lazy_list_explicit
0ea1a3efix list() method doctest for lazy_list_explicit
d482706reogarnisation of class hierarchy

comment:52 Changed 7 years ago by git

  • Commit changed from d4827065218788bd6990aed6293536a29396fd54 to 9790b69bc62f00af0bb6a2c4d49649ba6a835bd5

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

9790b69implementation of lazy_list_explicit and its iteratorand some reorganization of the class hierarchy

comment:53 Changed 7 years ago by git

  • Commit changed from 9790b69bc62f00af0bb6a2c4d49649ba6a835bd5 to 19cbfd225f597b50114a0def322f40b3a5a848cd

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

19cbfd2fix a bug with cached lazy_list

comment:54 Changed 7 years ago by git

  • Commit changed from 19cbfd225f597b50114a0def322f40b3a5a848cd to 6f7cfd949cc0956c0490813a7024cb7a8182324e

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

6f7cfd9concatenation with list implemented

comment:55 Changed 7 years ago by 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

comment:56 Changed 7 years ago by 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?

comment:57 follow-up: Changed 7 years ago by 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

comment:58 in reply to: ↑ 57 Changed 7 years ago by 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

comment:59 Changed 6 years ago by git

  • Commit changed from 6f7cfd949cc0956c0490813a7024cb7a8182324e to 8457edfb98b43d55d73f949860326f30e67a5bf4

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

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

comment:60 Changed 6 years ago by git

  • Commit changed from 8457edfb98b43d55d73f949860326f30e67a5bf4 to 1ac24d5075f1b9060309c4ab02a2bd73a5217d6d

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

1ac24d5remove 'info' method and rename class lazy_list by abstract_lazy_list

comment:61 Changed 6 years ago by 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 ;)

comment:62 Changed 6 years ago by tmonteil

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

comment:63 Changed 6 years ago by dkrenn

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

comment:64 Changed 6 years ago by 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.

comment:65 follow-up: Changed 6 years ago by 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

comment:66 Changed 6 years ago by vdelecroix

  • Description modified (diff)

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

comment:67 in reply to: ↑ 65 ; follow-up: Changed 6 years ago by 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!

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

comment:68 in reply to: ↑ 67 Changed 6 years ago by 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...)

comment:69 Changed 6 years ago by vdelecroix

  • Authors changed from Vincent Delecroix, Matthieu Dien to Vincent Delecroix
  • Branch changed from public/lazy_list_from_various_input_data to vdelecroix/16137
  • Commit 1ac24d5075f1b9060309c4ab02a2bd73a5217d6d deleted
  • Milestone changed from sage-6.4 to sage-7.0
  • Status changed from new to needs_review

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

comment:70 Changed 6 years ago by vdelecroix

  • Branch changed from vdelecroix/16137 to u/vdelecroix/16137
  • Commit set to 5dac074dc5fce5de34818c30e0564d4c35dc1d42

New commits:

1acf92eTrac 16137: move lazy_list into data_structures
6d53317Trac 16137: fix doctests and import
e9ee148Trac 16137: refactor and extend lazy lists
5dac074Trac 16137: fix class name change lazy_list -> lazy_list_abstract

comment:71 Changed 6 years ago by dkrenn

  • Branch changed from u/vdelecroix/16137 to u/dkrenn/16137

comment:72 follow-up: Changed 6 years ago by dkrenn

  • Commit changed from 5dac074dc5fce5de34818c30e0564d4c35dc1d42 to 8cee245894c11639eac8a6756ce35170041713df
  • Status changed from needs_review to needs_work

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)?
  1. description, INPUT/OUTPUT of lazy_list is missing
  1. 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)?
  1. _fit, last example: looks incomplete
  1. __call__: write oneline description
  1. update_cache_up_to everwhere: describe return value
  1. :class:`lazy_list` appears a couple of times, but lazy_list is not a class anymore
  1. note-block in lazy_list_from_iterator description should (also) be in lazy_list
  1. cache in INPUT-blocks: everywhere mention that this is a list (see also above)
  1. __reduce__: oneline description missing
  1. ticket-description "a pair of finite lists (pre-period, period)": remove from description and create separate ticket for this issue?
  1. 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:

40851bdTrac 16137 review: update doc-indices
bd68b5aTrac 16137 review: some smaller changes
c30746freturn value of _fit
f092fc3partial cherr-pick of 8457edf: iterators replaced by generators; make this work
8cee245Merge branch 'u/dkrenn/16137' into u/vdelecroix/16137

comment:73 Changed 6 years ago by dkrenn

Two more issues:

  1. Since the code was moved from sage.misc to sage.data_structures, do we need a deprecation?
  1. 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?

comment:74 follow-up: Changed 6 years ago by 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.

comment:75 in reply to: ↑ 74 Changed 6 years ago by 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).

comment:76 follow-up: Changed 6 years ago by 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.

comment:77 in reply to: ↑ 76 Changed 6 years ago by dkrenn

Replying to vdelecroix:

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

Ok, then let's keep the name.

comment:78 Changed 6 years ago by vdelecroix

  • Authors changed from Vincent Delecroix to Matthieu Dien, Vincent Delecroix
  • Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
  • Commit changed from 8cee245894c11639eac8a6756ce35170041713df to f1b8d64889eeface3f2ee18472f18a97e654ae5a
  • Status changed from needs_work to needs_review

New commits:

bd2d1acTrac 16137: deprecated import from sage.misc.lazy_list
0e01c63Trac 16137: revision 1
f1b8d64Trac 16137: revision 2

comment:79 follow-up: Changed 6 years ago by 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.

  1. description, INPUT/OUTPUT of lazy_list is missing

done.

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

  1. _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().

  1. __call__: write oneline description

done

comment:80 follow-up: Changed 6 years ago by vdelecroix

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

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

done

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

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

done.

  1. __reduce__: oneline description missing

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

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

comment:81 follow-up: Changed 6 years ago by vdelecroix

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

comment:82 follow-up: Changed 6 years ago by vdelecroix

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

comment:83 Changed 6 years ago by dkrenn

  • Branch changed from u/vdelecroix/16137 to u/dkrenn/16137

comment:84 in reply to: ↑ 82 Changed 6 years ago by dkrenn

  • Commit changed from f1b8d64889eeface3f2ee18472f18a97e654ae5a to 80aad4d9dbc02333435477173ad98871d40625b8

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:

80aad4dTrac 16137: another reviewer commit

comment:85 in reply to: ↑ 79 Changed 6 years ago by 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.

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

comment:86 in reply to: ↑ 80 ; follow-up: Changed 6 years ago by dkrenn

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

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

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

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

comment:87 in reply to: ↑ 81 ; follow-up: Changed 6 years ago by dkrenn

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

  1. lazy_list_abstract vs. for example lazy_list_generic: I find it a bit strange to instantiate something with "abstract" in its name.
  1. 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.

comment:88 follow-up: Changed 6 years ago by 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).

comment:89 Changed 6 years ago by vdelecroix

  • Description modified (diff)

comment:90 in reply to: ↑ 86 ; follow-up: Changed 6 years ago by vdelecroix

Replying to dkrenn:

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

comment:91 in reply to: ↑ 87 Changed 6 years ago by vdelecroix

Replying to dkrenn:

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

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

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

Changed as well.

comment:92 in reply to: ↑ 88 ; follow-up: Changed 6 years ago by 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.

comment:93 Changed 6 years ago by vdelecroix

  • Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
  • Commit changed from 80aad4d9dbc02333435477173ad98871d40625b8 to 85d99c03e0f03bfa23950cc807f28a467259fbc6

New commits:

85d99c0Trac 16137: revision 3

comment:94 Changed 6 years ago by dkrenn

  • Branch changed from u/vdelecroix/16137 to u/dkrenn/16137

comment:95 in reply to: ↑ 90 Changed 6 years ago by dkrenn

  • Commit changed from 85d99c03e0f03bfa23950cc807f28a467259fbc6 to 72a212c34c0f2a172b9d7ac95d11f24d254a86c3

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:

72a212cTrac 16137 review: fix ReST and remove unnecessary iter

comment:96 in reply to: ↑ 92 Changed 6 years ago by 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.

comment:97 in reply to: ↑ 72 Changed 6 years ago by dkrenn

  • Authors changed from Matthieu Dien, Vincent Delecroix to Matthieu Dien, Vincent Delecroix, Daniel Krenn
  • Reviewers set to Daniel Krenn

LGTM, positive whenever a patchbot confirms no errors.

comment:98 Changed 6 years ago by vdelecroix

Thanks for the careful review.

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

comment:99 Changed 6 years ago by 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.

comment:100 Changed 6 years ago by 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

comment:101 Changed 6 years ago by mantepse

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

comment:102 follow-ups: Changed 6 years ago by 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".

comment:103 Changed 6 years ago by jdemeyer

Minor comments:

  1. insert the standard copyright template.
  1. 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"
    
  1. remove the unused
    from cpython.object cimport *
    
  1. remove the unused
    from libc import limits
    

comment:104 Changed 6 years ago by jdemeyer

  • Status changed from needs_review to needs_work

comment:105 in reply to: ↑ 102 Changed 6 years ago by vdelecroix

  • Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
  • Commit changed from 72a212c34c0f2a172b9d7ac95d11f24d254a86c3 to 429be5821297d6dd542c48a5ce1e2db7b4d2c44c
  • Status changed from needs_work to needs_info

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:

429be58Trac 16137: removed import + copyright statement

comment:106 in reply to: ↑ 102 ; follow-up: Changed 6 years ago by 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?

comment:107 in reply to: ↑ 106 Changed 6 years ago by 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.

comment:108 Changed 6 years ago by 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.

comment:109 Changed 6 years ago by git

  • Commit changed from 429be5821297d6dd542c48a5ce1e2db7b4d2c44c to 295a870b43132d8c7e5c4f3c086b6280d2781a1f

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

e2bae5eTrac 16137: move back lazy lists to misc
295a870Trac 16137: fix changes in imports

comment:110 follow-up: Changed 6 years ago by vdelecroix

  • Status changed from needs_info to needs_review

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

comment:111 in reply to: ↑ 110 Changed 6 years ago by dkrenn

  • Status changed from needs_review to needs_work

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

comment:112 Changed 6 years ago by dkrenn

  • Branch changed from u/vdelecroix/16137 to u/dkrenn/16137

comment:113 Changed 6 years ago by git

  • Commit changed from 295a870b43132d8c7e5c4f3c086b6280d2781a1f to daa99905c661d199975c01bf39a98b7bb9b7e2ea

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

daa9990forgotten change import

comment:114 Changed 6 years ago by dkrenn

  • Status changed from needs_work to positive_review

comment:115 Changed 6 years ago by vbraun

  • Status changed from positive_review to needs_work
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]

comment:116 follow-up: Changed 6 years ago by vdelecroix

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

comment:117 follow-up: Changed 6 years ago by vdelecroix

  • Branch changed from u/dkrenn/16137 to u/vdelecroix/16137
  • Commit changed from daa99905c661d199975c01bf39a98b7bb9b7e2ea to 55a19187320c8aeca6adfb7b5d98acd3274ae207
  • Milestone changed from sage-7.0 to sage-7.1
  • Status changed from needs_work to needs_review

New commits:

f1c6036Trac 16137: merge Sage-7.0
55a1918Trac 16137: fixing a doctest and a constructor

comment:118 in reply to: ↑ 116 Changed 6 years ago by 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.

comment:119 in reply to: ↑ 117 Changed 6 years ago by dkrenn

Replying to vdelecroix:

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

comment:120 follow-up: Changed 6 years ago by git

  • Commit changed from 55a19187320c8aeca6adfb7b5d98acd3274ae207 to f7960c1038c1498eca8995a3e39e7c3a4f76e99e

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

f7960c1Trac 16137: fixing a doctest and a constructor

comment:121 in reply to: ↑ 120 Changed 5 years ago by dkrenn

  • Status changed from needs_review to positive_review

Replying to git:

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

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

comment:122 Changed 5 years ago by vbraun

  • Branch changed from u/vdelecroix/16137 to f7960c1038c1498eca8995a3e39e7c3a4f76e99e
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.