Opened 6 years ago
Closed 6 years ago
#22561 closed defect (fixed)
Implement __iter__ for PARI Gen
Reported by:  Marc Culler  Owned by:  

Priority:  major  Milestone:  sage7.6 
Component:  interfaces  Keywords:  cypari2, days85 
Cc:  Luca De Feo, Vincent Delecroix  Merged in:  
Authors:  Jeroen Demeyer  Reviewers:  Marc Culler, Vincent Delecroix, Luca De Feo 
Report Upstream:  N/A  Work issues:  
Branch:  9bd903b (Commits, GitHub, GitLab)  Commit:  9bd903b23c6f30274ecaa14bb45a8725a90fe762 
Dependencies:  #22471  Stopgaps: 
Description (last modified by )
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__
.
Attachments (1)
Change History (24)
Changed 6 years ago by
Attachment:  gen_pyx.patch added 

comment:1 Changed 6 years ago by
Authors:  → Jeroen Demeyer 

Component:  number fields → interfaces 
Description:  modified (diff) 
I think it would be better to implement __iter__
instead.
comment:2 Changed 6 years ago by
Summary:  iterating over a Pari t_POL creates an infinite loop. → Implement __iter__ for PARI Gen 

comment:3 Changed 6 years ago by
Cc:  Luca De Feo Vincent Delecroix added 

comment:6 Changed 6 years ago by
Branch:  → u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_ 

comment:7 Changed 6 years ago by
Commit:  → 0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b 

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

comment:8 Changed 6 years ago by
Commit:  0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b → 9bd903b23c6f30274ecaa14bb45a8725a90fe762 

Branch pushed to git repo; I updated commit sha1. New commits:
9bd903b  Special cases for iterating t_VECSMALL and t_STR

comment:9 Changed 6 years ago by
Status:  new → needs_review 

comment:10 followups: 11 12 Changed 6 years ago by
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.
comment:11 Changed 6 years ago by
Replying to culler:
Although it is wonderful to have
__iter__
, I still think that__getitem__
should raise anIndexError
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 most appropriate to me.
comment:12 Changed 6 years ago by
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 doublecheck that this was indeed using Cython 0.25.2 and not some earlier version? Support for f
strings was added only recently to Cython.
comment:13 Changed 6 years ago by
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.
comment:14 followup: 15 Changed 6 years ago by
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)
??
comment:15 Changed 6 years ago by
Replying to culler:
Can you give an example of a Python container which allows
X[n]
forn > len(X)
??
A polynomial is not a container.
comment:16 Changed 6 years ago by
IMHO, when you say len(p) or p[5] you are treating p as if it were a container for its coefficients.
comment:17 Changed 6 years ago by
Replying to culler:
Can you give an example of a Python container which allows
X[n]
forn > 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
comment:18 followup: 20 Changed 6 years ago by
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))
).
comment:19 Changed 6 years ago by
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
comment:20 Changed 6 years ago by
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. :^{) }
comment:21 Changed 6 years ago by
Reviewers:  → Marc Culler, Vincent Delecroix, Luca De Feo 

Status:  needs_review → positive_review 
Seems to me there are no more objections to this ticket. Thanks everyone.
comment:22 Changed 6 years ago by
Keywords:  days85 added 

comment:23 Changed 6 years ago by
Branch:  u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_ → 9bd903b23c6f30274ecaa14bb45a8725a90fe762 

Resolution:  → fixed 
Status:  positive_review → closed 
patch