Implement __iter__ for PARI Gen

[culler]

The following reasonable and apparently innocuous code sends Sage into an infinite loop:

sage: p = pari('x^2 + x + 1')
sage: list(p)

The reason is that the gen object has no __iter__ method, but it has a __getitem__ method which accepts any integer index and returns 0 for indices larger than the degree of the polynomial. Since there is no __iter__ method, python builds an iterator using __getitem__.

[culler]

patch

[jdemeyer]

I think it would be better to implement __iter__ instead.

[vdelecroix]

What about __len__?

[jdemeyer]

__len__ already exists.

[jdemeyer]

There are various doctest failures in src/sage/rings involving Galois permutations. I don't have time to look at those right now, so if somebody else wants to continue, please do.

---

New commits:

​6b65682	Gen: clean up "new_ref" mechanism
​f7bc5b7	Put sig_check() in inner loops
​0f4e30a	Implement __iter__ for PARI Gen

[git]

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

​9bd903b

Special cases for iterating t_VECSMALL and t_STR

[culler]

Implementing __iter__ was definitely the right thing to do, and this implementation works great for me, testing in CyPari. Thanks!

Although it is wonderful to have __iter__, I still think that __getitem__ should raise an IndexError if one tries to access a t_POL coefficient with negative index, or index larger than the degree. This just makes sense, and also is consistent with how it works for power series.

I ran into a minor compatibility issue (i.e. a Cython bug) with Python 3.5 on Ubuntu 16.04: Cython 0.25.2 had trouble parsing the f"..." formatted strings passed to warn or TypeError. The error looks like this:

            from warnings import warn
            warn(f"iterating a PARI {self.type()} is deprecated", DeprecationWarning)
                 ^
------------------------------------------------------------

cypari_src/gen.pyx:320:18: Expected ')', found 'BEGIN_STRING'

This did not happen on macOS using Python 3.6.

[vdelecroix]

Replying to culler:

Although it is wonderful to have __iter__, I still think that __getitem__ should raise an IndexError if one tries to access a t_POL coefficient with negative index, or index larger than the degree. This just makes sense, and also is consistent with how it works for power series.

For the power series 1 + O(x^5), the __getitem__ should only raise IndexError for indices greater or equal than 5. It is not related to the actual degree of the underlying polynomial but the precision. One can think of a polynomial as p + O(x^infinity) and hence no IndexError looks the more appropriate to me.

[jdemeyer]

Replying to culler:

I ran into a minor compatibility issue (i.e. a Cython bug) with Python 3.5 on Ubuntu 16.04: Cython 0.25.2 had trouble parsing the f"..." formatted strings

Sorry to ask, but can you please double-check that this was indeed using Cython 0.25.2 and not some earlier version? Support for f-strings was added only recently to Cython.

[culler]

You are right, Jeroen. Sorry! My build system had cython 0.25.2 installed. But Python 3 uses cython3, not cython, and cython3 was an older version.

[culler]

Vincent, I am having trouble following your logic. Why should it be correct to ask for the coefficient of x^-3 in a polynomial? I agree that if a polynomial were a special case of a power series (with infinite precision) then it might make sense to pretend that there were coefficients of all positive degrees. You might similarly argue that a polynomial is a special case of a Laurent polynomial, or Laurent series. But we are talking about how to model these concepts as Python objects. We expect Python subclasses to override methods of their parent class in a way which reflects how the structure of the subclass differs from that of the parent. So we should expect polynomials to override __getitem__ and __len__ in a way which reflects the differences between a polynomial and a power series or Laurent polynomial or Laurent series.

Can you give an example of a Python container which allows X[n] for n > len(X)??

[jdemeyer]

Replying to culler:

Can you give an example of a Python container which allows X[n] for n > len(X)??

A polynomial is not a container.

[culler]

IMHO, when you say len(p) or p[5] you are treating p as if it were a container for its coefficients.

[vdelecroix]

Replying to culler:

Can you give an example of a Python container which allows X[n] for n > len(X)??

The dictionary {2: 'hello'} :-P. More seriously, polynomials in GP behave that way

? p = x^3 + 2
%1 = x^3 + 2
? length(p)
%2 = 4
? polcoeff(p, 5) 
%3 = 0
? polcoeff(p, -3)
%4 = 0

[vdelecroix]

On a related note, see that integers have numerators and denominators!

sage: 12.numerator()
12
sage: 12.denominator()
1

In a CAS, you certainly want some combatibility between embeddings of structures (like ZZ c QQ or R[x] c R((X))).

[culler]

True, GP does handle polynomial coefficients that way. But the job of modeling GP belongs to the pari object, and its behavior would not be changed.

sage: p = pari('x^2 + x + 1')
sage: p.polcoeff(25)
0

>>> from cypari import *
>>> p = pari('x^2 + x + 1')
>>> p.polcoeff(25)
0

[culler]

I guess the bottom line here is that Sage's polynomial ring handles polynomial coefficients that way:

sage: R.<x> = PolynomialRing(ZZ)
sage: p = R(x^2 - 3*x + 2)
sage: p[25]
0
sage: p[-2]
0

To me, that is a convincing argument for why pari polynomials should behave the same way. Components of Sage should certainly be consistent with Sage itself. So I will stop clogging up trac with discussions of this. :⁾

[defeo]

Seems to me there are no more objections to this ticket. Thanks everyone.