Opened 6 years ago
Closed 6 years ago
#22561 closed defect (fixed)
Implement __iter__ for PARI Gen
Reported by: | culler | Owned by: | |
---|---|---|---|
Priority: | major | Milestone: | sage-7.6 |
Component: | interfaces | Keywords: | cypari2, days85 |
Cc: | defeo, vdelecroix | 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: | defeo vdelecroix 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 follow-ups: 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 more 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 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.
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 follow-up: 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 follow-up: 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