Sage: Ticket #22561: Implement __iter__ for PARI Gen
https://trac.sagemath.org/ticket/22561
<p>
The following reasonable and apparently innocuous code sends Sage into an infinite loop:
</p>
<pre class="wiki">sage: p = pari('x^2 + x + 1')
sage: list(p)
</pre><p>
The reason is that the gen object has no <code>__iter__</code> method, but it has a <code>__getitem__</code> method which accepts any integer index and returns 0 for indices larger than the degree of the polynomial. Since there is no <code>__iter__</code> method, python builds an iterator using <code>__getitem__</code>.
</p>
en-usSagehttps://trac.sagemath.org/chrome/site/logo_sagemath_trac.png
https://trac.sagemath.org/ticket/22561
Trac 1.1.6cullerThu, 09 Mar 2017 23:15:53 GMTattachment set
https://trac.sagemath.org/ticket/22561
https://trac.sagemath.org/ticket/22561
<ul>
<li><strong>attachment</strong>
set to <em>gen_pyx.patch</em>
</li>
</ul>
<p>
patch
</p>
TicketjdemeyerFri, 10 Mar 2017 10:55:30 GMTcomponent, description changed; author set
https://trac.sagemath.org/ticket/22561#comment:1
https://trac.sagemath.org/ticket/22561#comment:1
<ul>
<li><strong>component</strong>
changed from <em>number fields</em> to <em>interfaces</em>
</li>
<li><strong>description</strong>
modified (<a href="/ticket/22561?action=diff&version=1">diff</a>)
</li>
<li><strong>author</strong>
set to <em>Jeroen Demeyer</em>
</li>
</ul>
<p>
I think it would be better to implement <code>__iter__</code> instead.
</p>
TicketjdemeyerFri, 10 Mar 2017 10:55:54 GMTsummary changed
https://trac.sagemath.org/ticket/22561#comment:2
https://trac.sagemath.org/ticket/22561#comment:2
<ul>
<li><strong>summary</strong>
changed from <em>iterating over a Pari t_POL creates an infinite loop.</em> to <em>Implement __iter__ for PARI Gen</em>
</li>
</ul>
TicketjdemeyerFri, 10 Mar 2017 10:56:36 GMTcc set
https://trac.sagemath.org/ticket/22561#comment:3
https://trac.sagemath.org/ticket/22561#comment:3
<ul>
<li><strong>cc</strong>
<em>defeo</em> <em>vdelecroix</em> added
</li>
</ul>
TicketvdelecroixFri, 10 Mar 2017 10:59:07 GMT
https://trac.sagemath.org/ticket/22561#comment:4
https://trac.sagemath.org/ticket/22561#comment:4
<p>
What about <code>__len__</code>?
</p>
TicketjdemeyerFri, 10 Mar 2017 11:11:09 GMTdependencies set
https://trac.sagemath.org/ticket/22561#comment:5
https://trac.sagemath.org/ticket/22561#comment:5
<ul>
<li><strong>dependencies</strong>
set to <em>#22471</em>
</li>
</ul>
<p>
<code>__len__</code> already exists.
</p>
TicketjdemeyerFri, 10 Mar 2017 13:47:31 GMTbranch set
https://trac.sagemath.org/ticket/22561#comment:6
https://trac.sagemath.org/ticket/22561#comment:6
<ul>
<li><strong>branch</strong>
set to <em>u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_</em>
</li>
</ul>
TicketjdemeyerFri, 10 Mar 2017 13:48:33 GMTcommit set
https://trac.sagemath.org/ticket/22561#comment:7
https://trac.sagemath.org/ticket/22561#comment:7
<ul>
<li><strong>commit</strong>
set to <em>0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b</em>
</li>
</ul>
<p>
There are various doctest failures in <code>src/sage/rings</code> involving Galois permutations. I don't have time to look at those right now, so if somebody else wants to continue, please do.
</p>
<hr />
<p>
New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=6b65682846416c83883250b492305588b19c33c0"><span class="icon"></span>6b65682</a></td><td><code>Gen: clean up "new_ref" mechanism</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=f7bc5b7ea8205e31ef4d98928d289c79c0f9e893"><span class="icon"></span>f7bc5b7</a></td><td><code>Put sig_check() in inner loops</code>
</td></tr><tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit?id=0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b"><span class="icon"></span>0f4e30a</a></td><td><code>Implement __iter__ for PARI Gen</code>
</td></tr></table>
TicketgitSat, 11 Mar 2017 21:42:05 GMTcommit changed
https://trac.sagemath.org/ticket/22561#comment:8
https://trac.sagemath.org/ticket/22561#comment:8
<ul>
<li><strong>commit</strong>
changed from <em>0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b</em> to <em>9bd903b23c6f30274ecaa14bb45a8725a90fe762</em>
</li>
</ul>
<p>
Branch pushed to git repo; I updated commit sha1. New commits:
</p>
<table class="wiki">
<tr><td><a class="ext-link" href="https://git.sagemath.org/sage.git/commit/?id=9bd903b23c6f30274ecaa14bb45a8725a90fe762"><span class="icon"></span>9bd903b</a></td><td><code>Special cases for iterating t_VECSMALL and t_STR</code>
</td></tr></table>
TicketjdemeyerSat, 11 Mar 2017 21:50:30 GMTstatus changed
https://trac.sagemath.org/ticket/22561#comment:9
https://trac.sagemath.org/ticket/22561#comment:9
<ul>
<li><strong>status</strong>
changed from <em>new</em> to <em>needs_review</em>
</li>
</ul>
TicketcullerMon, 13 Mar 2017 22:40:58 GMT
https://trac.sagemath.org/ticket/22561#comment:10
https://trac.sagemath.org/ticket/22561#comment:10
<p>
Implementing <code>__iter__</code> was definitely the right thing to do, and this implementation works great for me, testing in <code>CyPari</code>. Thanks!
</p>
<p>
Although it is wonderful to have <code>__iter__</code>, I still think that <code>__getitem__</code> should raise an <code>IndexError</code> 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.
</p>
<p>
I ran into a minor compatibility issue (i.e. a Cython bug) with Python 3.5 on Ubuntu 16.04: <code>Cython 0.25.2</code> had trouble parsing the f"..." formatted strings passed to warn or <code>TypeError</code>. The error looks like this:
</p>
<pre class="wiki"> from warnings import warn
warn(f"iterating a PARI {self.type()} is deprecated", DeprecationWarning)
^
------------------------------------------------------------
cypari_src/gen.pyx:320:18: Expected ')', found 'BEGIN_STRING'
</pre><p>
This did not happen on macOS using Python 3.6.
</p>
TicketvdelecroixTue, 14 Mar 2017 09:22:42 GMT
https://trac.sagemath.org/ticket/22561#comment:11
https://trac.sagemath.org/ticket/22561#comment:11
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22561#comment:10" title="Comment 10">culler</a>:
</p>
<blockquote class="citation">
<p>
Although it is wonderful to have <code>__iter__</code>, I still think that <code>__getitem__</code> should raise an <code>IndexError</code> 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.
</p>
</blockquote>
<p>
For the power series <code>1 + O(x^5)</code>, the <code>__getitem__</code> should only raise <code>IndexError</code> for indices greater or equal than <code>5</code>. It is not related to the actual degree of the underlying polynomial but the precision. One can think of a polynomial as <code>p + O(x^infinity)</code> and hence no <code>IndexError</code> looks the most appropriate to me.
</p>
TicketjdemeyerTue, 14 Mar 2017 09:55:26 GMT
https://trac.sagemath.org/ticket/22561#comment:12
https://trac.sagemath.org/ticket/22561#comment:12
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22561#comment:10" title="Comment 10">culler</a>:
</p>
<blockquote class="citation">
<p>
I ran into a minor compatibility issue (i.e. a Cython bug) with Python 3.5 on Ubuntu 16.04: <code>Cython 0.25.2</code> had trouble parsing the f"..." formatted strings
</p>
</blockquote>
<p>
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 <code>f</code>-strings was added only recently to Cython.
</p>
TicketcullerTue, 14 Mar 2017 14:00:34 GMT
https://trac.sagemath.org/ticket/22561#comment:13
https://trac.sagemath.org/ticket/22561#comment:13
<p>
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.
</p>
TicketcullerTue, 14 Mar 2017 14:24:46 GMT
https://trac.sagemath.org/ticket/22561#comment:14
https://trac.sagemath.org/ticket/22561#comment:14
<p>
Vincent, I am having trouble following your logic. Why should it be correct to ask for the coefficient of <code>x^-3</code> 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 <code>__getitem__</code> and <code>__len__</code> in a way which reflects the differences between a polynomial and a power series or Laurent polynomial or Laurent series.
</p>
<p>
Can you give an example of a Python container which allows <code>X[n]</code> for <code>n > len(X)</code>??
</p>
TicketjdemeyerTue, 14 Mar 2017 14:27:16 GMT
https://trac.sagemath.org/ticket/22561#comment:15
https://trac.sagemath.org/ticket/22561#comment:15
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22561#comment:14" title="Comment 14">culler</a>:
</p>
<blockquote class="citation">
<p>
Can you give an example of a Python container which allows <code>X[n]</code> for <code>n > len(X)</code>??
</p>
</blockquote>
<p>
A polynomial is not a container.
</p>
TicketcullerTue, 14 Mar 2017 14:40:21 GMT
https://trac.sagemath.org/ticket/22561#comment:16
https://trac.sagemath.org/ticket/22561#comment:16
<p>
IMHO, when you say len(p) or p[5] you are treating p as if it were a container for its coefficients.
</p>
TicketvdelecroixTue, 14 Mar 2017 14:42:39 GMT
https://trac.sagemath.org/ticket/22561#comment:17
https://trac.sagemath.org/ticket/22561#comment:17
<p>
Replying to <a class="ticket" href="https://trac.sagemath.org/ticket/22561#comment:14" title="Comment 14">culler</a>:
</p>
<blockquote class="citation">
<p>
Can you give an example of a Python container which allows <code>X[n]</code> for <code>n > len(X)</code>??
</p>
</blockquote>
<p>
The dictionary <code>{2: 'hello'}</code> :-P. More seriously, polynomials in GP behave that way
</p>
<pre class="wiki">? p = x^3 + 2
%1 = x^3 + 2
? length(p)
%2 = 4
? polcoeff(p, 5)
%3 = 0
? polcoeff(p, -3)
%4 = 0
</pre>
TicketvdelecroixTue, 14 Mar 2017 14:49:12 GMT
https://trac.sagemath.org/ticket/22561#comment:18
https://trac.sagemath.org/ticket/22561#comment:18
<p>
On a related note, see that integers have numerators and denominators!
</p>
<pre class="wiki">sage: 12.numerator()
12
sage: 12.denominator()
1
</pre><p>
In a CAS, you certainly want some combatibility between embeddings of structures (like <code>ZZ c QQ</code> or <code>R[x] c R((X))</code>).
</p>
TicketcullerTue, 14 Mar 2017 14:57:36 GMT
https://trac.sagemath.org/ticket/22561#comment:19
https://trac.sagemath.org/ticket/22561#comment:19
<p>
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.
</p>
<pre class="wiki">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
</pre>
TicketcullerTue, 14 Mar 2017 15:13:22 GMT
https://trac.sagemath.org/ticket/22561#comment:20
https://trac.sagemath.org/ticket/22561#comment:20
<p>
I guess the bottom line here is that Sage's polynomial ring handles polynomial coefficients that way:
</p>
<pre class="wiki">sage: R.<x> = PolynomialRing(ZZ)
sage: p = R(x^2 - 3*x + 2)
sage: p[25]
0
sage: p[-2]
0
</pre><p>
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. :<sup>)
</sup></p>
TicketdefeoTue, 14 Mar 2017 19:21:31 GMTstatus changed; reviewer set
https://trac.sagemath.org/ticket/22561#comment:21
https://trac.sagemath.org/ticket/22561#comment:21
<ul>
<li><strong>status</strong>
changed from <em>needs_review</em> to <em>positive_review</em>
</li>
<li><strong>reviewer</strong>
set to <em>Marc Culler, Vincent Delecroix, Luca De Feo</em>
</li>
</ul>
<p>
Seems to me there are no more objections to this ticket. Thanks everyone.
</p>
TicketdefeoTue, 14 Mar 2017 19:56:02 GMTkeywords changed
https://trac.sagemath.org/ticket/22561#comment:22
https://trac.sagemath.org/ticket/22561#comment:22
<ul>
<li><strong>keywords</strong>
<em>days85</em> added
</li>
</ul>
TicketvbraunMon, 27 Mar 2017 20:41:53 GMTstatus, branch changed; resolution set
https://trac.sagemath.org/ticket/22561#comment:23
https://trac.sagemath.org/ticket/22561#comment:23
<ul>
<li><strong>status</strong>
changed from <em>positive_review</em> to <em>closed</em>
</li>
<li><strong>resolution</strong>
set to <em>fixed</em>
</li>
<li><strong>branch</strong>
changed from <em>u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_</em> to <em>9bd903b23c6f30274ecaa14bb45a8725a90fe762</em>
</li>
</ul>
Ticket