Opened 5 years ago

Closed 5 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:

Status badges

Description (last modified by jdemeyer)

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)

gen_pyx.patch (716 bytes) - added by culler 5 years ago.
patch

Download all attachments as: .zip

Change History (24)

Changed 5 years ago by culler

patch

comment:1 Changed 5 years ago by jdemeyer

  • Authors set to Jeroen Demeyer
  • Component changed from number fields to interfaces
  • Description modified (diff)

I think it would be better to implement __iter__ instead.

comment:2 Changed 5 years ago by jdemeyer

  • Summary changed from iterating over a Pari t_POL creates an infinite loop. to Implement __iter__ for PARI Gen

comment:3 Changed 5 years ago by jdemeyer

  • Cc defeo vdelecroix added

comment:4 Changed 5 years ago by vdelecroix

What about __len__?

comment:5 Changed 5 years ago by jdemeyer

  • Dependencies set to #22471

__len__ already exists.

comment:6 Changed 5 years ago by jdemeyer

  • Branch set to u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_

comment:7 Changed 5 years ago by jdemeyer

  • Commit set to 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:

6b65682Gen: clean up "new_ref" mechanism
f7bc5b7Put sig_check() in inner loops
0f4e30aImplement __iter__ for PARI Gen

comment:8 Changed 5 years ago by git

  • Commit changed from 0f4e30a902ffed54b0217e6d5bff9d5fe7d4e78b to 9bd903b23c6f30274ecaa14bb45a8725a90fe762

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

9bd903bSpecial cases for iterating t_VECSMALL and t_STR

comment:9 Changed 5 years ago by jdemeyer

  • Status changed from new to needs_review

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

comment:11 in reply to: ↑ 10 Changed 5 years ago by 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 most appropriate to me.

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

comment:12 in reply to: ↑ 10 Changed 5 years ago by 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.

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

comment:14 follow-up: Changed 5 years ago by 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)??

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

comment:16 Changed 5 years ago by culler

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 5 years ago by 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
Last edited 5 years ago by vdelecroix (previous) (diff)

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

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

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

comment:21 Changed 5 years ago by defeo

  • Reviewers set to Marc Culler, Vincent Delecroix, Luca De Feo
  • Status changed from needs_review to positive_review

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

comment:22 Changed 5 years ago by defeo

  • Keywords days85 added

comment:23 Changed 5 years ago by vbraun

  • Branch changed from u/jdemeyer/iterating_over_a_pari_t_pol_creates_an_infinite_loop_ to 9bd903b23c6f30274ecaa14bb45a8725a90fe762
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.