Opened 6 years ago

Closed 4 years ago

#14982 closed defect (fixed)

When a parent is equipped with an embedding, consider coercions that don't go through the embedding

Reported by: mmezzarobba Owned by:
Priority: major Milestone: sage-6.4
Component: coercion Keywords: embedding
Cc: robertwb, SimonKing, jpflori Merged in:
Authors: Marc Mezzarobba, Vincent Delecroix Reviewers: Vincent Delecroix
Report Upstream: N/A Work issues:
Branch: a0ac11b (Commits) Commit: a0ac11b26f4ded7bbcbef5bb6a1f81ae8ed354f6
Dependencies: Stopgaps:

Description (last modified by mmezzarobba)

Parent.discover_coerce_map_from used to always give priority to coercions that start with applying an embedding over those provided by _coerce_map_from_. This leads to coercion failures such as the following:

sage: K.<a> = NumberField(x^2+1/2, embedding=CC(0,1))
sage: L = NumberField(x^2+2, 'b', embedding=1/a)     
sage: R = PolynomialRing(L, 'x')                     
sage: R.coerce_map_from(R.base_ring())               
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-8-fb89bb074d92> in <module>()
----> 1 R.coerce_map_from(R.base_ring())
...
AttributeError: 'NoneType' object has no attribute 'domain'

This patch series modifies the coercion discovery algorithm to fix the issue, and fixes or works around a few weaknesses in existing code exposed by the change. See the individual commit messages for details.

Change History (67)

comment:1 Changed 6 years ago by mmezzarobba

  • Cc robertwb SimonKing added

Apparently, the problem is more general stems from the policy of Parent.discover_coerce_map_from of always giving priority to coercions that start with applying an embedding over those provided by _coerce_map_from_.

In the special case of this ticket, a workaround would be to revert part of a3c5958b8e6983a3ef8466d0bd0b6ce09fd32d41 so that the BaseringInjection gets registered as early as possible:

--- a/src/sage/rings/polynomial/polynomial_ring.py
+++ b/src/sage/rings/polynomial/polynomial_ring.py
@@ -283,9 +283,11 @@ class PolynomialRing_general(sage.algebras.algebra.Algebra):
         # since we want to use PolynomialBaseringInjection.
         sage.algebras.algebra.Algebra.__init__(self, base_ring, names=name, normalize=True, category=category)
         self.__generator = self._polynomial_class(self, [0,1], is_gen=True)
+        base_inject = PolynomialBaseringInjection(base_ring, self)
+        self._unset_coercions_used()
         self._populate_coercion_lists_(
-                #coerce_list = [base_inject],
-                #convert_list = [list, base_inject],
+                coerce_list = [base_inject],
+                convert_list = [list, base_inject],
                 convert_method_name = '_polynomial_')
 
 
@@ -552,8 +554,8 @@ class PolynomialRing_general(sage.algebras.algebra.Algebra):
         """
         # In the first place, handle the base ring
         base_ring = self.base_ring()
-        if P is base_ring:
-            return PolynomialBaseringInjection(base_ring, self)
+        #if P is base_ring:
+        #    return PolynomialBaseringInjection(base_ring, self)
         # handle constants that canonically coerce into self.base_ring()
         # first, if possible
         try:

(I didn't check whether this breaks anything else.)

But the same issue potentially affects anything constructed over a base ring with coerce_embedding. At best, a suboptimal coercion is found:

sage: M = MatrixSpace(L, 2, 2)
sage: M.coerce_map_from(L)
Composite map:
  From: Number Field in b with defining polynomial x^2 + 2
  To:   Full MatrixSpace of 2 by 2 dense matrices over Number Field in b with defining polynomial x^2 + 2
  Defn:   Generic morphism:
          From: Number Field in b with defining polynomial x^2 + 2
          To:   Number Field in a with defining polynomial x^2 + 1/2
          Defn: b -> -2*a
        then
          Call morphism:
          From: Number Field in a with defining polynomial x^2 + 1/2
          To:   Full MatrixSpace of 2 by 2 dense matrices over Number Field in b with defining polynomial x^2 + 2
sage: PowerSeriesRing(L, 'x').coerce_map_from(L)
Composite map:
  From: Number Field in b with defining polynomial x^2 + 2
  To:   Power Series Ring in x over Number Field in b with defining polynomial x^2 + 2
  Defn:   Generic morphism:
          From: Number Field in b with defining polynomial x^2 + 2
          To:   Number Field in a with defining polynomial x^2 + 1/2
          Defn: b -> -2*a
        then
          Conversion map:
          From: Number Field in a with defining polynomial x^2 + 1/2
          To:   Power Series Ring in x over Number Field in b with defining polynomial x^2 + 2

and at worst the construction itself fails (well, I'm assuming it's the same issue as above, but I didn't check in detail):

sage: L.extension(x^3+x+1, 'c')
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-28-b42564719919> in <module>()
----> 1 L.extension(x**Integer(3)+x+Integer(1), 'c')

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/rings/number_field/number_field.pyc in extension(self, poly, name, names, check, embedding)
   4173             raise TypeError, "the variable name must be specified."
   4174         from sage.rings.number_field.number_field_rel import NumberField_relative
-> 4175         return NumberField_relative(self, poly, str(name), check=check, embedding=embedding)
   4176 
   4177     def factor(self, n):

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/rings/number_field/number_field_rel.pyc in __init__(self, base, polynomial, name, latex_name, names, check, embedding)
    301 
    302         v[0] = self._gen_relative()
--> 303         v = [self(x) for x in v]
    304         self.__gens = tuple(v)
    305         self._zero_element = self(0)

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.__call__ (sage/structure/parent.c:8078)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.convert_map_from (sage/structure/parent.c:15826)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_convert_map_from (sage/structure/parent.c:15991)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:14563)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_coerce_map_from (sage/structure/parent.c:14932)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.coerce_map_from (sage/structure/parent.c:14563)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent.so in sage.structure.parent.Parent.discover_coerce_map_from (sage/structure/parent.c:14985)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/structure/parent_old.so in sage.structure.parent_old.Parent._coerce_map_from_ (sage/structure/parent_old.c:6658)()

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/rings/number_field/number_field_rel.pyc in _coerce_map_from_(self, R)
   1031         mor = self.base_field().coerce_map_from(R)
   1032         if mor is not None:
-> 1033             return self.coerce_map_from(self.base_field()) * mor
   1034 
   1035     def _rnfeltreltoabs(self, element, check=False):

/home/marc/co/sage/local/lib/python2.7/site-packages/sage/categories/map.so in sage.categories.map.Map.__mul__ (sage/categories/map.c:4796)()

AttributeError: 'NoneType' object has no attribute 'domain'

comment:2 Changed 6 years ago by mmezzarobba

  • Summary changed from Coercion from base ring fails for some polynomial rings over number fields with embeddings to Coercion from rings with coerce_embedding into constructions over those rings is broken

comment:3 follow-up: Changed 6 years ago by mmezzarobba

  • Authors set to Marc Mezzarobba
  • Branch set to u/mmezzarobba/coerce_embeddings
  • Keywords embedding added
  • Status changed from new to needs_review

Here's an attempt to fix the problem with a small change to the coercion discovery algorithm. It does break a few things, but I'd argue it only does so by exposing weaknesses in existing code. The other patches in the series fix (or, in one case, work around) these weaknesses.

See the commit messages for details.

What do the experts say?

comment:4 Changed 6 years ago by mmezzarobba

  • Milestone changed from sage-5.12 to sage-6.0

comment:5 in reply to: ↑ 3 ; follow-up: Changed 6 years ago by SimonKing

Replying to mmezzarobba:

Here's an attempt to fix the problem with a small change to the coercion discovery algorithm. It does break a few things, but I'd argue it only does so by exposing weaknesses in existing code. The other patches in the series fix (or, in one case, work around) these weaknesses.

See the commit messages for details.

What do the experts say?

I couldn't tell, unless you give me a pointer to the new workfow. What do I need to do, when not a patch but a brunch (aaahm, branch...) is given?

comment:6 in reply to: ↑ 5 ; follow-up: Changed 6 years ago by SimonKing

Replying to SimonKing:

I couldn't tell, unless you give me a pointer to the new workfow. What do I need to do, when not a patch but a brunch (aaahm, branch...) is given?

For example, when I look at the "commits" link, I see that there are three commits, and only one of them seems to refer to this ticket. So, what do I do with the other commits, review-wise? I see that there is a discussion on sage-git on the question what exactly is to be reviewed. Would I only review the last commit (since its commit message refers to this ticket)? Would I review all three commits (but then I would potentially also review dependencies that are reviewed elsewhere!)?

comment:7 in reply to: ↑ 6 ; follow-ups: Changed 6 years ago by mmezzarobba

Replying to SimonKing:

Replying to SimonKing:

I couldn't tell, unless you give me a pointer to the new workfow. What do I need to do, when not a patch but a brunch (aaahm, branch...) is given?

If you already have a git-based installation of sage (i.e. you once did something like git clone https://github.com/sagemath/sage.git && git checkout -b origin/build_system && make build) and a remote that refers to the trac server, you just need to fetch and checkout the branch u/mmezzarobba/coerce_embeddings from trac and review the three commits on top of build_system just like you would if they were patches you just applied.

Otherwise, hmm, I guess it is easier to set up a git-based installation than to try to do the review with Mercurial... See http://sagemath.github.io/git-developer-guide/ (or ask!) in case you need more information on how to do that.

If the branch was based off an old version of sage, I guess you might also want to check that it merges cleanly, but here it is already a descendant of the last beta.

For example, when I look at the "commits" link, I see that there are three commits, and only one of them seems to refer to this ticket. So, what do I do with the other commits, review-wise? I see that there is a discussion on sage-git on the question what exactly is to be reviewed. Would I only review the last commit (since its commit message refers to this ticket)? Would I review all three commits (but then I would potentially also review dependencies that are reviewed elsewhere!)?

All three commits need review, and none of them is part of any other ticket. I am not sure if/where the ticket number should go in the commit logs (perhaps it would make more sense to put it in the message associated to the merge commit?). The last commit of the branch is also the one that fixes the issue the ticket is about, so I put it here, but I can rewrite history to add it to the two other commits if you want.

comment:8 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by SimonKing

Replying to mmezzarobba:

If you already have a git-based installation of sage (i.e. you once did something like git clone https://github.com/sagemath/sage.git && git checkout -b origin/build_system && make build)

I have. But at least on one of my machines I get several doctest errors with the latest git version.

and a remote that refers to the trac server,

I did store my ssh keys on trac. But "having a remote" sounds like I need to inform git about the existence of the trac server.

you just need to fetch and checkout the branch u/mmezzarobba/coerce_embeddings from trac

I hope the meaning and how-to of "fetch" and "checkout" will be clear to me from the git-developer-guide.

http://sagemath.github.io/git-developer-guide/ (or ask!) in case you need more information on how to do that.

I saw this (or an old version) before, which made me register my ssh keys, for example.

All three commits need review, and none of them is part of any other ticket. I am not sure if/where the ticket number should go in the commit logs (perhaps it would make more sense to put it in the message associated to the merge commit?). The last commit of the branch is also the one that fixes the issue the ticket is about, so I put it here, but I can rewrite history to add it to the two other commits if you want.

No idea about this. From the discussion on sage-git, it seems to me that the git branches can be totally orthogonal to what one used to do with patches. A branch may span over different tickets, and it is totally unclear from the commits themselves which of them belong to a ticket and which of them belong to a dependency. That's bad for reviewing. In the old model, one would talk about a list of patches attached to the ticket, which makes it crystal clear what ticket a patch belongs to.

comment:9 in reply to: ↑ 7 ; follow-up: Changed 6 years ago by SimonKing

Replying to mmezzarobba:

Otherwise, hmm, I guess it is easier to set up a git-based installation than to try to do the review with Mercurial... See http://sagemath.github.io/git-developer-guide/ (or ask!) in case you need more information on how to do that.

It fails totally, it seems.

Namely, in my git install of sage (which I kept up to date by git pull followed by make), I tried

simon@linux-sqwp:~/SAGE/GIT/sage> ./sage -dev create-ticket
sage-run received unknown option: -dev 
usage: sage [options]
Try 'sage -h' for more information.

sage -dev create-ticket is about the first example of using the development scripts in the development guide!

comment:10 in reply to: ↑ 9 Changed 6 years ago by mmezzarobba

Replying to SimonKing:

It fails totally, it seems.

Sorry, I always use git directly and didn't realize that de developer guide presented the custom devel scripts first.

comment:11 in reply to: ↑ 8 Changed 6 years ago by mmezzarobba

(It looks like you got most of this sorted out, based on you posts on sage-git. I'm replying anyway just in case; please feel free to ask for more detail!)

Replying to SimonKing:

Replying to mmezzarobba:

If you already have a git-based installation of sage (i.e. you once did something like git clone https://github.com/sagemath/sage.git && git checkout -b origin/build_system && make build)

I have. But at least on one of my machines I get several doctest errors with the latest git version.

Yes. These are rather minor issues that are handled elsewhere.

and a remote that refers to the trac server,

I did store my ssh keys on trac. But "having a remote" sounds like I need to inform git about the existence of the trac server.

Yes:

git remote add trac ssh://git@trac.sagemath.org:2222/sage.git

(With this setup, git fetch trac will automatically download copies of all branches available on the trac server. This will likely mean hundreds of branches when everyone switches to git. They don't live in the same namespace as your local branches and don't pollute the output of most commands. But if you don't like that behaviour, you can use -t to limit the subset of branches to track.)

you just need to fetch and checkout the branch u/mmezzarobba/coerce_embeddings from trac

I hope the meaning and how-to of "fetch" and "checkout" will be clear to me from the git-developer-guide.

  • fetch = synchronize your local repository's view of the branches on trac (!= your local branches) with their remote state:
    git fetch trac
    
  • checkout = get the contents of a given revision in the form of actual files in your working directory:
    git checkout -b my_local_review_branch -t trac/u/mmezzarobba/coerce_embeddings
    
  • The last command also sets up a local branch for you to work on (e.g., to prepare a reviewer patch). If you only want to have a look at some remote branch, you can omit the -b and -t options. git will issue a scary warning about detached heads. That "detached head state" is when you don't have anywhere to commit your changes if you make any.

If you want to prepare a reviewer patch, you will need to:

  • Make your changes.
  • Commit them to your local review branch (git commit -a to commit everything).
  • (Repeat if there are several unrelated changes.)
  • Once you are happy with your local changes, push them somewhere on trac:
    git push trac my_local_review_branch:trac/u/SimonKing/coerce_embeddings
    
  • Tell me about the new branch you created on trac, or just put its name in the Branch: field.

No idea about this. From the discussion on sage-git, it seems to me that the git branches can be totally orthogonal to what one used to do with patches. A branch may span over different tickets,

A git branch is just a pointer to a commit (and thus implicitly to everything that precedes it history-wise). So in some sense it every branch spans the whole history of sage, but otherwise a branch cannot really span several tickets.

(There are several other kinds of "pointers to commits" in git. Branches are pointers to commit that move up automatically when new commits are added "on" them.)

and it is totally unclear from the commits themselves which of them belong to a ticket and which of them belong to a dependency. That's bad for reviewing. In the old model, one would talk about a list of patches attached to the ticket, which makes it crystal clear what ticket a patch belongs to.

I agree, and that's why I started this thread...

comment:12 Changed 6 years ago by jpflori

  • Cc jpflori added
  • Commit set to 0869e9aae81cc0174ca7151a724cc30489bb4bac

New commits:

[changeset:0869e9a]14982: consider coercions of parents with embeddings that do not use the embedding
[changeset:cd982ae]Make coercions that go through lazy fields more robust
[changeset:110dd48]Cleanup after querying the coercion system with a temporary element_class in NumberField_cyclotomic

comment:13 follow-up: Changed 6 years ago by SimonKing

Is this branch compatible with #15303?

comment:14 in reply to: ↑ 13 ; follow-up: Changed 6 years ago by mmezzarobba

Replying to SimonKing:

Is this branch compatible with #15303?

The issues do look related, but otherwise I have no idea: I stopped working on it weeks before the discussion on #15303 started, and I haven't have time to read that thread yet. I hope to be able to work on this some time next week.

comment:15 in reply to: ↑ 14 ; follow-up: Changed 6 years ago by SimonKing

Replying to mmezzarobba:

Replying to SimonKing:

Is this branch compatible with #15303?

The issues do look related, but otherwise I have no idea: I stopped working on it weeks before the discussion on #15303 started, and I haven't have time to read that thread yet. I hope to be able to work on this some time next week.

I have tested that #15303 does not fix the bug from your ticket description. What I meant was: Are there merge conflicts?

comment:16 Changed 6 years ago by git

  • Commit changed from 0869e9aae81cc0174ca7151a724cc30489bb4bac to 4cf3ca5d71b4a701e5ac19e413fc4b1ab50eb851

Branch pushed to git repo; I updated commit sha1. Last 10 new commits:

4cf3ca5Fix gross bug in Map.domains(), add missing docstrings
17832a0Merge coercion transitivity fixes (#15303)
528a035Merge branch 'ticket/13394' into ticket/15303, to make weak caches safer
851cc95Avoid some pointer casts in WeakValueDict? callbacks
246518fUse <dict>'s internals in WeakValueDictionary? and do not reinvent the bucket.
fab0ed4Use WeakValueDict?'s iteration guard more consequently
e4adaebImplement copy and deepcopy for WeakValueDictionary?
70a7b8aGuard WeakValueDictionary? against deletions during iteration
c3dba98Replace weakref.WeakValueDictionary? by sage.misc.weak_dict.WeakValueDictionary?
17b0236Documentation for WeakValueDictionary?

comment:17 in reply to: ↑ 15 ; follow-up: Changed 6 years ago by mmezzarobba

Replying to SimonKing:

I have tested that #15303 does not fix the bug from your ticket description. What I meant was: Are there merge conflicts?

Sorry for the late reply. There were a few conflicts indeed. I did the merge, and the tests still pass, except that I'm getting a timeout with sage/rings/number_field/number_field.py and random segfaults with some other files.

For instance:

$ sage -t -a
...
----------------------------------------------------------------------
sage -t src/sage/rings/number_field/number_field.py  # Time out
sage -t src/sage/rings/number_field/number_field_element_quadratic.pyx  # Killed due to segmentation fault
sage -t src/sage/groups/abelian_gps/values.py  # Killed due to segmentation fault
----------------------------------------------------------------------

but then:

$ sage -t src/sage/rings/number_field/number_field_element_quadratic.pyx
Running doctests with ID 2013-11-27-23-09-47-2b207575.
Doctesting 1 file.
sage -t src/sage/rings/number_field/number_field_element_quadratic.pyx
    [420 tests, 7.97 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------
$ sage -t src/sage/groups/abelian_gps/values.py
Running doctests with ID 2013-11-27-23-10-03-7a10efd7.
Doctesting 1 file.
sage -t src/sage/groups/abelian_gps/values.py
    [81 tests, 0.11 s]
----------------------------------------------------------------------
All tests passed!
----------------------------------------------------------------------

comment:18 in reply to: ↑ 17 ; follow-up: Changed 6 years ago by mmezzarobba

Replying to mmezzarobba:

random segfaults with some other files.

It looks like the crashes happen in __pyx_pf_4sage_10categories_3map_3Map_6domain___get__, called from sage/structure/parent.pyx:2536...

comment:19 in reply to: ↑ 18 Changed 6 years ago by mmezzarobba

Replying to mmezzarobba:

Replying to mmezzarobba:

random segfaults with some other files.

It looks like the crashes happen in __pyx_pf_4sage_10categories_3map_3Map_6domain___get__, called from sage/structure/parent.pyx:2536...

I tried again with a clean build, and I am unable to reproduce the crashes. I guess it was only a compilation problem...

comment:20 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.0 to sage-6.1

comment:21 Changed 6 years ago by git

  • Commit changed from 4cf3ca5d71b4a701e5ac19e413fc4b1ab50eb851 to 7e8d4aa5ad04fa2b6536508efefcf69776d6d160

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

7e8d4aaMerge coercion transitivity fixes (#15303) again
858cd39typo
12e8055Merge branch 'ticket/14711' into ticket/15303
ee30c20Address the "check" keyword of scheme morphisms by name, not position
d68c5dfMinor fixes, that became needed since #14711 was not merged quickly enough
c42b539Merge branch 'master' into ticket/14711
2712c53Merge 'trac/master' into ticket/15303
23f18f2Merge branch 'master' into ticket/14711

comment:22 Changed 6 years ago by mmezzarobba

  • Branch changed from u/mmezzarobba/coerce_embeddings to u/mmezzarobba/14982-coerce_embeddings
  • Commit changed from 7e8d4aa5ad04fa2b6536508efefcf69776d6d160 to 2fcc47300d619cd8c0c96ab57686096993e64e5d
  • Description modified (diff)

(git-)Rebased on top of 6.1.rc0, removed dependency on #15303.


New commits:

0faffdeCleanup after querying the coercion system with a temporary element_class in NumberField_cyclotomic
bd4f772Make coercions that go through lazy fields more robust
2fcc47314982: consider coercions of parents with embeddings that do not use the embedding
Last edited 6 years ago by mmezzarobba (previous) (diff)

comment:23 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:24 Changed 6 years ago by mmezzarobba

  • Summary changed from Coercion from rings with coerce_embedding into constructions over those rings is broken to Consider coercions of embedded parents that do not use the embedding

comment:25 follow-up: Changed 5 years ago by git

  • Commit changed from 2fcc47300d619cd8c0c96ab57686096993e64e5d to b7816788a46fe54990c1f80d89836dc8674b1f89

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

693dfc1Cleanup after querying the coercion system with a temporary element_class in NumberField_cyclotomic
372553aMake coercions that go through lazy fields more robust
b78167814982: consider coercions of parents with embeddings that do not use the embedding

comment:26 in reply to: ↑ 25 Changed 5 years ago by mmezzarobba

Replying to git:

Branch pushed to git repo; I updated commit sha1. This was a forced push.

Rebased. Tests pass.

comment:27 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:28 Changed 5 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:29 Changed 5 years ago by git

  • Commit changed from b7816788a46fe54990c1f80d89836dc8674b1f89 to 873e359f39632b76dc4179db73a355563fc33e07

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

d73e507Cleanup after querying the coercion system with a temporary element_class in NumberField_cyclotomic
8318f0cMake coercions that go through lazy fields more robust
873e35914982: consider coercions of parents with embeddings that do not use the embedding

comment:30 Changed 5 years ago by mmezzarobba

  • Summary changed from Consider coercions of embedded parents that do not use the embedding to When a parent is equipped with an embedding, consider coercions that don't go through the embedding

Rebased. (Tests are still running.)


New commits:

d73e507Cleanup after querying the coercion system with a temporary element_class in NumberField_cyclotomic
8318f0cMake coercions that go through lazy fields more robust
873e35914982: consider coercions of parents with embeddings that do not use the embedding

comment:31 Changed 5 years ago by mmezzarobba

  • Status changed from needs_review to needs_work

comment:32 follow-up: Changed 5 years ago by jpflori

Needs work for what?

comment:33 in reply to: ↑ 32 Changed 5 years ago by mmezzarobba

Replying to jpflori:

Needs work for what?

There are new test failures with the rebase. I haven't had time to fix them yet...

comment:34 Changed 4 years ago by git

  • Commit changed from 873e359f39632b76dc4179db73a355563fc33e07 to 3cfa5436266dcab268c98ac9627ecbb47c11415b

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

3d7d823#14982 Clean up after querying the coercion system with a temporary element_class in NumberField_cyclotomic
434c73d#14982 Make coercions that go through lazy fields more robust
749ec1f#14982 Consider coercions of parents with embeddings that do not use the embedding
3cfa543#14982 Workaround for q_binomial doctest

comment:35 Changed 4 years ago by git

  • Commit changed from 3cfa5436266dcab268c98ac9627ecbb47c11415b to b40ed6c6aafe4301a81213e6b581f89b4d6d2930

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

b40ed6c#14982 Robustify PolynomialRing_general._coerce_map_from_()

comment:36 Changed 4 years ago by mmezzarobba

  • Status changed from needs_work to needs_review

comment:37 Changed 4 years ago by mmezzarobba

(I haven't had time to run all tests with the last commit yet, only those that failed before plus modules related to things that changed.)

comment:38 Changed 4 years ago by mmezzarobba

  • Description modified (diff)

comment:39 Changed 4 years ago by mmezzarobba

All tests pass.

comment:40 Changed 4 years ago by git

  • Commit changed from b40ed6c6aafe4301a81213e6b581f89b4d6d2930 to f32b52f4176684d57e4e6b83f80c2c553ffcc8eb

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

ce4e0a8#14982 Clean up after querying the coercion system with a temporary element_class in NumberField_cyclotomic
ce34b1e#14982 Make coercions that go through lazy fields more robust
16df502#14982 Consider coercions of parents with embeddings that do not use the embedding
3f9b096#14982 Workaround for q_binomial doctest
f32b52f#14982 Robustify PolynomialRing_general._coerce_map_from_()

comment:41 follow-up: Changed 4 years ago by vdelecroix

Hello,

I have a question related to number fields (in particular #18226 and #17830). I do want a direct coercion number field -> RIF based on the (future) _mpfr_ method of elements. Right now, the route is long as the discoevery algorithm tells me that I need to do number field -> RLF -> RIF (and actually there is QQbar hidden in the middle). I guess that the proposition here would solve this issue! That would be fantastic.

Vincent

comment:42 in reply to: ↑ 41 Changed 4 years ago by mmezzarobba

Replying to vdelecroix:

I have a question related to number fields (in particular #18226 and #17830). I do want a direct coercion number field -> RIF based on the (future) _mpfr_ method of elements. Right now, the route is long as the discoevery algorithm tells me that I need to do number field -> RLF -> RIF (and actually there is QQbar hidden in the middle). I guess that the proposition here would solve this issue! That would be fantastic.

I don't know if the changes in this ticket would suffice to discover the right coercion path, but at least they make it possible to select a coercion path that doesn't use the embedding even when there is another path that uses it!

comment:43 follow-up: Changed 4 years ago by vdelecroix

Hello,

In this comment

+            # As a consequence, a value of __an_element with the wrong class
+            # is cached during the call to has_coerce_map_from. We reset the
+            # cache afterwards.

you refer to __an_element. But you changed the attribute's name to _cache_an_element.

The hack for quadratic number field is horrible... At least could we replace

  • src/sage/rings/number_field/number_field_element_quadratic.pyx

    diff --git a/src/sage/rings/number_field/number_field_element_quadratic.pyx b/src/sage/rings/number_field/number_field_element_quadratic.pyx
    index 32e1acc..692bae1 100644
    a b cdef class NumberFieldElement_quadratic(NumberFieldElement_absolute): 
    210210            self._reduce_c_()
    211211
    212212        # set the attribute standard embedding which is used in the method
    213         # __cmp__
    214         try:
    215             self.standard_embedding = parent._standard_embedding
    216         except AttributeError:
    217             emb = parent.coerce_embedding()
    218             if emb is None:
    219                 self.standard_embedding = True
    220                 try:
    221                     parent._standard_embedding = True
    222                 except AttributeError:
    223                     pass
    224             else:
    225                 raise ValueError("A parent of NumberFieldElement_quadratic with "
    226                                  "a canonical embedding should have an attribute "
    227                                  "_standard_embedding (used for comparisons of elements)")
     213        # __cmp__, sign, real, imag, floor, ceil, ...
     214        self.standard_embedding = parent._standard_embedding

Vincent

comment:44 in reply to: ↑ 43 ; follow-up: Changed 4 years ago by mmezzarobba

Replying to vdelecroix:

In this comment

+            # As a consequence, a value of __an_element with the wrong class
+            # is cached during the call to has_coerce_map_from. We reset the
+            # cache afterwards.

you refer to __an_element. But you changed the attribute's name to _cache_an_element.

Thanks, fixed.

The hack for quadratic number field is horrible...

You are the one who introduced it, aren't you? ;-) So I guess you understand what it is for better than I do. In any case I just tested the change you suggested (on top of my branch + the current master) and it doesn't seem to break anything.

comment:45 Changed 4 years ago by git

  • Commit changed from f32b52f4176684d57e4e6b83f80c2c553ffcc8eb to 4b55415e1dd476e6010fb82b174d5fa455f963bd

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

7baf9d6#14982 fix comment
4b55415#14982 simplify NFE_quadratic.__init__

comment:46 in reply to: ↑ 44 ; follow-ups: Changed 4 years ago by vdelecroix

Replying to mmezzarobba:

Replying to vdelecroix:

The hack for quadratic number field is horrible...

You are the one who introduced it, aren't you? ;-) So I guess you understand what it is for better than I do. In any case I just tested the change you suggested (on top of my branch + the current master) and it doesn't seem to break anything.

I am ;-(. Thanks for fixing it! I really do not like the loop here: coercion needs an element, but the elements need to know coercion... (certainly out of the scope of the ticket).

I fixed the q_binomial issue (see the commit on top public/14982, WARNING: it is merged with 6.7.beta2). If you like it just cherry-pick it on top of your branch. Otherwise, I will open a new ticket. I actually found another bug:

sage: Sym = SymmetricFunctions(QQ)
sage: s = Sym.schur()
sage: 1 - s[2]
s[] - s[2]
sage: 1r - s[2]
Traceback (most recent call last):
...
TypeError: unsupported operand type(s) for -: 'int' and
'SymmetricFunctionAlgebra_schur_with_category.element_class'

Vincent

comment:47 in reply to: ↑ 46 Changed 4 years ago by SimonKing

Replying to vdelecroix:

I am ;-(. Thanks for fixing it! I really do not like the loop here: coercion needs an element, but the elements need to know coercion... (certainly out of the scope of the ticket).

It used to be worse in the past. You want to multiply an element x of parent P with an element y of parent Q. During multiplication, a coercion relating P and Q is sought, which used to involve a call to P.an_element() and Q.an_element(). But for some parents, this was not implemented or (worse) itself relied on coercion.

Today, the fact is used that one already has elements of P and Q in the situation above (namely x and y).

So, don't complain, as it could be worse ;-)

comment:48 in reply to: ↑ 46 Changed 4 years ago by mmezzarobba

Replying to vdelecroix:

I fixed the q_binomial issue (see the commit on top public/14982, WARNING: it is merged with 6.7.beta2).

Thanks, your fix is much better than what I did (even though the particular issue would probably have been solved by the ticket about I). Just one question: why are you doing

    try:
        zero = R.zero()
    except AttributeError:
        zero = R(0)
    try:
        one = R.one()
    except AttributeError:
        one = R(1)

instead of just

    zero = R(0)
    one = R(1)

(Are there cases where R.zero() would work but not R(0)? Or is it faster that way when R is a Parent, despite the try/catch block? And then, does speed matter?)

If you like it just cherry-pick it on top of your branch.

I guess I will even rebase the whole thing and merge related commits when we're done talking about it.

I actually found another bug:

sage: Sym = SymmetricFunctions(QQ)
sage: s = Sym.schur()
sage: 1 - s[2]
s[] - s[2]
sage: 1r - s[2]
Traceback (most recent call last):
...
TypeError: unsupported operand type(s) for -: 'int' and
'SymmetricFunctionAlgebra_schur_with_category.element_class'

But this example already didn't work before this ticket, did it?

comment:49 in reply to: ↑ 46 Changed 4 years ago by mmezzarobba

Replying to vdelecroix:

The hack for quadratic number field is horrible...

You are the one who introduced it, aren't you? ;-) So I guess you understand what it is for better than I do. In any case I just tested the change you suggested (on top of my branch + the current master) and it doesn't seem to break anything.

I am ;-(. Thanks for fixing it!

Well, I didn't really fix it: I just made it slightly less fragile...

comment:50 Changed 4 years ago by git

  • Commit changed from 4b55415e1dd476e6010fb82b174d5fa455f963bd to ee261a37a06b53106c1640c7ef13b913f7cc2532

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

ee261a3Trac 14982: fix q_binomial

comment:51 Changed 4 years ago by mmezzarobba

  • Authors changed from Marc Mezzarobba to Marc Mezzarobba, Vincent Delecroix

comment:52 Changed 4 years ago by vdelecroix

Replying to mmezzarobba:

Replying to vdelecroix:

I fixed the q_binomial issue (see the commit on top public/14982, WARNING: it is merged with 6.7.beta2).

Thanks, your fix is much better than what I did (even though the particular issue would probably have been solved by the ticket about I). Just one question: why are you doing ... instead of just

...

(Are there cases where R.zero() would work but not R(0)? Or is it faster that way when R is a Parent, despite the try/catch block? And then, does speed matter?)

Here is an example:

sage: C = GF(5).cartesian_product(GF(5))
sage: C(0)
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
sage: C(1)
Traceback (most recent call last):
...
TypeError: 'sage.rings.integer.Integer' object is not iterable
sage: C.zero()
(0, 0)
sage: C.one()
(1, 1)

But I guess that it should work because there always is a canonical morphism ZZ -> ring. And here not

sage: C.has_coerce_map_from(ZZ)
False

So do not worry about this example. The version with zero = R(0) and one = R(1) is much simpler. And anyway it is completely broken

sage: cyclotomic_value(4, C.one())
Traceback (most recent call last):
...
TypeError: unsupported operand parent(s) for '-':
'The cartesian product of (Finite Field of size 5, Finite Field of size 5)'
and '<type 'int'>'
sage: q_binomial(4, 2, C.one())
Traceback (most recent call last):
..
RuntimeError: maximum recursion depth exceeded while calling a Python object

Actually, this last example with infinite recursion is related to coercions... so potentially there is something to dig further.

But this example already didn't work before this ticket, did it?

Nope. Completely unrelated. Actually, it is related in the sense that the was appearing in prod(1 - q**i ...). And apparently it was the unique reason of this huge try/except block that is removed by my commit.

Vincent

comment:53 Changed 4 years ago by vdelecroix

Haha

sage: one = C.one()
sage: one - one
Traceback (most recent call last):
...
RuntimeError: maximum recursion depth exceeded in __instancecheck__

see #18275

comment:54 Changed 4 years ago by git

  • Commit changed from ee261a37a06b53106c1640c7ef13b913f7cc2532 to d99564520a5fd599c0fea62b86d0bdbfbd35c1a4

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

47b6a0e#14982 Clean up after querying the coercion system with a temporary element_class in NumberField_cyclotomic
61c73bb#14982 Make coercions that go through lazy fields more robust
0aa11af#14982 fix q_binomial
a3227dd#14982 Robustify PolynomialRing_general._coerce_map_from_()
d995645#14982 Consider coercions of parents with embeddings that do not use the embedding

comment:55 Changed 4 years ago by mmezzarobba

Vincent, do your comments count as a review? (If so, you may want to check that I didn't do anything wrong with my last rebase.) Or are there still things to be checked/addressed?

comment:56 follow-up: Changed 4 years ago by vdelecroix

Hello,

I am not sure I am the best person to do the complete review. But...

  1. Is this really the example you wanted to show MatrixSpace(L, 2, 2).coerce_map_from(L). Wouldn't be better to test MatrixSpace(K, 2, 2).coerce_map_from(L)? Idem for the one with PowerSeriesRing that follows.
  1. With your modifications the following changes. Old version:
    sage: C12.<zeta12> = CyclotomicField(12)
    sage: C4.<zeta4> = CyclotomicField(4, embedding=zeta12**3)
    sage: PowerSeriesRing(C12, 'x').coerce_map_from(C4)
    Composite map:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Power Series Ring in x over Cyclotomic Field of order 12 and degree 4
      Defn:   Generic morphism:
              From: Cyclotomic Field of order 4 and degree 2
              To:   Cyclotomic Field of order 12 and degree 4
              Defn: zeta4 -> zeta12^3
            then
              Conversion map:
              From: Cyclotomic Field of order 12 and degree 4
              To:   Power Series Ring in x over Cyclotomic Field of order 12 and degree 4
    
    Versus new version:
    sage: PowerSeriesRing(C12, 'x').coerce_map_from(C4)
    Conversion map:
      From: Cyclotomic Field of order 4 and degree 2
      To:   Power Series Ring in x over Cyclotomic Field of order 12 and degree 4
    sage: timeit("mor(a)", number=5000, repeat=6)
    5000 loops, best of 6: 120 µs per loop
    
    whereas for PolynomialRing the behavior is identical (similar to the "old version" above). Is it the kind of thing that you expected?

Vincent

comment:57 Changed 4 years ago by vdelecroix

  • Status changed from needs_review to needs_info

comment:58 in reply to: ↑ 56 ; follow-up: Changed 4 years ago by mmezzarobba

  • Status changed from needs_info to needs_review

Replying to vdelecroix:

  1. Is this really the example you wanted to show MatrixSpace(L, 2, 2).coerce_map_from(L). Wouldn't be better to test MatrixSpace(K, 2, 2).coerce_map_from(L)? Idem for the one with PowerSeriesRing that follows.

Yes, I think it is, because I wanted to illustrate that the way coercions are discovered in the presence of an embedding makes it difficult to work with structures that have the “embedded” parent as a base ring, even if the parent into which it is embedded plays no role in the construction. But I wrote this comment more than 1½ years ago, so I'm not sure I remember correctly!

  1. With your modifications the following changes. [...] whereas for PolynomialRing the behavior is identical (similar to the "old version" above). Is it the kind of thing that you expected?

Sorry, I'm not sure I understand the question. Let me try to answer it anyway: the goal of these patches is to make the coercion discovery algorithm consider paths that don't start with the embedding. These paths may or may not be selected depending on each particular case.

sage: timeit("mor(a)", number=5000, repeat=6)
5000 loops, best of 6: 120 µs per loop

Are these lines a copy-paste error, or did you observe a speed regression with some coercions? (On my machine, applying the morphism returned by PowerSeriesRing(C12, 'x').coerce_map_from(C4) takes almost exactly as much time before and after my patches.)

comment:59 in reply to: ↑ 58 Changed 4 years ago by vdelecroix

Replying to mmezzarobba:

Replying to vdelecroix:

sage: timeit("mor(a)", number=5000, repeat=6)
5000 loops, best of 6: 120 µs per loop

Are these lines a copy-paste error, or did you observe a speed regression with some coercions? (On my machine, applying the morphism returned by PowerSeriesRing(C12, 'x').coerce_map_from(C4) takes almost exactly as much time before and after my patches.)

Oops sorry. Yes, I observed a tiny regression speed of roughly 4% (120 µs vs 115 µs). Not very significant and that's the reason why I erased half of it.

comment:60 follow-up: Changed 4 years ago by vdelecroix

Salut Marc,

I am quite confused by the following

sage: K = QuadraticField(2)
sage: RR.coerce_map_from(K)
Composite map:
  From: Number Field in a with defining polynomial x^2 - 2
  To:   Real Field with 53 bits of precision
  Defn:   Generic morphism:
          From: Number Field in a with defining polynomial x^2 - 2
          To:   Real Lazy Field
          Defn: a -> 1.414213562373095?
        then
          Conversion via _mpfr_ method map:
          From: Real Lazy Field
          To:   Real Field with 53 bits of precision

But elements of K do implement directly an _mpfr_ method

sage: K.an_element()._mpfr_
<built-in method _mpfr_ of sage.rings.number_field.number_field_element_quadratic.NumberFieldElement_quadratic object at 0x7f3e3d94ff68>

So why the discovery does not choose this direct conversion map instead of going through the real lazy field? (note: this method _mpfr_ is completely broken, but it does not change anything to the story)

Vincent

comment:61 in reply to: ↑ 60 Changed 4 years ago by mmezzarobba

Salut Vincent,

Replying to vdelecroix:

So why the discovery does not choose this direct conversion map instead of going through the real lazy field? (note: this method _mpfr_ is completely broken, but it does not change anything to the story)

I think the reason is that RR explicitly asks for coercions into it through RLF (see the very last line of RealField_class._coerce_map_from_. So the step of the coercion discovery algorithm that calls _coerce_map_from_ (step 2 with my patch) succeeds. The map it finds is of type FormalCompositeMap, so the next step (which would consider the coercions defined using _populate_coercion_lists_, including _mpfr_) is not even tried.

As far as I understand, this is the intended behavior from the point of view of the coercion discovery algorithm—_coerce_map_from_ “knows better”, do as it says. In any case the fact that the coercion from K to RLF is an embedding doesn't come into play. (But this ticket should make it possible to chose the coercion via _mpfr_ by modifying RealField_class._coerce_map_from_, while this wouldn't work now due to the special treatment of embeddings.)

comment:62 follow-up: Changed 4 years ago by vdelecroix

  • Reviewers set to Vincent Delecroix
  • Status changed from needs_review to needs_work

Final remark: I understand what you are doing with the newly defined method domains but I found the specifications rather unclear

Yield the domain of self. In general, iterate over the domains of
the factors of a composite map.

Could you be more precise in the documentation and precise why is it here?

Vincent

comment:63 Changed 4 years ago by git

  • Commit changed from d99564520a5fd599c0fea62b86d0bdbfbd35c1a4 to a0ac11b26f4ded7bbcbef5bb6a1f81ae8ed354f6

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

a0ac11b#14982 Map.domains(): improve documentation

comment:64 in reply to: ↑ 62 Changed 4 years ago by mmezzarobba

  • Status changed from needs_work to needs_review

Thanks again for your comments!

Replying to vdelecroix:

Final remark: I understand what you are doing with the newly defined method domains but I found the specifications rather unclear

Is it better now?

comment:65 follow-up: Changed 4 years ago by vdelecroix

  • Status changed from needs_review to positive_review

Yep. Good for me!

comment:66 in reply to: ↑ 65 Changed 4 years ago by mmezzarobba

Replying to vdelecroix:

Yep. Good for me!

Thanks a lot!

comment:67 Changed 4 years ago by vbraun

  • Branch changed from u/mmezzarobba/14982-coerce_embeddings to a0ac11b26f4ded7bbcbef5bb6a1f81ae8ed354f6
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.