The default call method of maps does not do as promised by the documentation

[simon-king-jena]

The documentation of sage.categories.map.Map.__call__ states:

- If ``x`` can be coerced into the domain of ``self``, then the 
  method ``_call_`` (single underscore) is called after
  coercion.
- Otherwise, it is tried to call the method ``pushout`` to ``x``
  (which may be provided in subclasses); in that way, ``self``
  could be applied to objects like ideals.

However, in the code, we had

            if not PY_TYPE_CHECK(x, Element):
                return self._call_(x)
            elif (<Element>x)._parent is not self._domain:
                try:
                    x = self._domain(x)
                except TypeError:
                    try:
                        return self.pushforward(x)
                    except (TypeError, NotImplementedError):
                        raise ...

Hence, there is a typo in the documentation (it is pushforward, not pushout):

1. If the argument is no element, one should expect that pushforward rather than _call_ is called. This is a problem if the argument happens to be a sub-module. Sub-modules are no elements (this is incontrast to ideals). Hence, currently, module morphisms have to implement a custom __call__ method.

2. In contrast to the statement of the documentation, the code is only about conversion, but not about coercion. I think this is a problem, as in the following example. There is no coercion from the abstract number field to the embedded number field, but no error is raised when calling the coerce embedding of the embedded field with an element of the abstract field:

  sage: K.<a>=NumberField(x^2-3,embedding=1)
  sage: L.<b>=NumberField(x^2-3)
  sage: K.has_coerce_map_from(L)
  False
  sage: K.coerce_embedding()(b)
  1.732050807568878? 

3. I was told that in the _call_ (single underscore) and _call_with_args methods one can assume that the argument belongs to the domain of the map. This is, however, not the case, since an argument that is not an element (like a python int, for example!) will not be converted into the domain before passing it to _call_.

I propose the following:

• If parent(x) does not coerce into the map's domain, pushforward is called on x together with the additional arguments. If it is not implemented or produces a TypeError, proceed with the next step.
• Try to convert x into the domain; this is now either a coercion, or it is a back-up solution for the failing pushfoward. If the conversion fails, raise an error that mentions the pushforward method.
• Call _call_ resp. _call_with_args.

There is a new doc test, demonstrating _call_, _call_with_args and pushforward. Apart from that, only small changes were needed in the doctests: Some error messages have changed.

I have no idea about the proper component. I hope "coercion" is fine.

Component: coercion

Keywords: generic call map

Author: Simon King

Reviewer: David Roe

Merged: sage-4.6.2.alpha1

Issue created by migration from https://trac.sagemath.org/ticket/10496

[simon-king-jena]

Author: Simon King

[roed314]

Reviewer: David Roe

[roed314]

comment:2

I approve of the design and goals, but I'm worried about the implementation speed. The current implementation does not introduce much overhead over _call_, but

if not self._domain.has_coerce_map_from(parent_c(x)): 
    if hasattr(self,'pushforward'): 

are both pretty costly calls. I think you need to add some fast pathways for common cases, such as x actually lying in the domain.

Similarly, use PY_TYPE_CHECK in cython files, rather than isinstance.

[simon-king-jena]

comment:3

Replying to @roed314:

I think you need to add some fast pathways for common cases, such as x actually lying in the domain.

Right, I'll do so. Note that I use parent_c (copied from sage.structure.parent) in order to speed things up.

What common cases, apart from parent_c(x) is self._domain, do you have in mind?

Similarly, use PY_TYPE_CHECK in cython files, rather than isinstance.

My patch introduces only one "isinstance", namely in the call method of Set_Python_class. The updated patch (hopefully being submitted in an hour or so) will use PY_TYPE_CHECK instead.

A propos: I was not aware of that Cython alternative to is_instance. Can you point me to a documentation of these and similar PY_... Cython functions?

I also found another way to speed the generic call method up: The current implementation does

if len(args) == 0 and len(kwds) == 0:
    return self._call_(x)

Using timeit", I found that if not(args) and not(kwds)` would be much faster:

sage: args=tuple(ZZ.random_element() for i in range(3))
sage: kwds=dict((i,ZZ.random_element()) for i in range(3))
sage: args0=()
sage: kwds0={}
sage: timeit("if len(args)==0 and len(kwds)==0: a=2")
625 loops, best of 3: 3.37 µs per loop
sage: timeit("if len(args0)==0 and len(kwds)==0: a=2")
625 loops, best of 3: 6.76 µs per loop
sage: timeit("if len(args0)==0 and len(kwds0)==0: a=2")
625 loops, best of 3: 7.21 µs per loop
sage: timeit("if not args and not kwds: a=2")
625 loops, best of 3: 129 ns per loop
sage: timeit("if not args0 and not kwds: a=2")
625 loops, best of 3: 275 ns per loop
sage: timeit("if not args0 and not kwds0: a=2")
625 loops, best of 3: 597 ns per loop

So, I'll change the patch accordingly.

[simon-king-jena]

comment:4

I updated my patch. Here are some timings for different situations.

With the patch:

sage: R.<x,y> = QQ[]; phi=R.hom([y,x])
# Element in domain
sage: timeit("a=phi(y)")
625 loops, best of 3: 32.3 µs per loop
# Element coerces into domain
sage: timeit("a=phi(5)")
625 loops, best of 3: 51.3 µs per loop
# non-Element that converts into domain
sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3}
sage: phi(D)
-x^2 + 7*x*y + 1/3*y^2 - 1
sage: timeit("a=phi(D)")
625 loops, best of 3: 119 µs per loop
# use pushforward
sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3]
sage: phi(I)
Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field
sage: timeit("a=phi(I)")
625 loops, best of 3: 164 µs per loop

The same examples without my patch:

sage: R.<x,y> = QQ[]; phi=R.hom([y,x])
sage: timeit("a=phi(y)")
625 loops, best of 3: 32.3 µs per loop
sage: timeit("a=phi(5)")
625 loops, best of 3: 37.1 µs per loop
sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3}
sage: phi(D)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)

/home/king/SAGE/work/modules/<ipython console> in <module>()

/mnt/local/king/SAGE/sage-4.6/local/lib/python2.6/site-packages/sage/categories/map.so in sage.categories.map.Map.__call__ (sage/categories/map.c:3145)()

/mnt/local/king/SAGE/sage-4.6/local/lib/python2.6/site-packages/sage/rings/morphism.so in sage.rings.morphism.RingHomomorphism_im_gens._call_ (sage/rings/morphism.c:5761)()

AttributeError: 'dict' object has no attribute '_im_gens_'
sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3]
sage: phi(I)
Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field
sage: timeit("a=phi(I)")
625 loops, best of 3: 492 µs per loop

Hence:

• If the argument has the right parent, it is as quick as before.
• If the argument coerces into the domain, it is slower. That is no surprise, because "not doing coercion" is certainly faster than "doing coercion", but "not doing coercion" is a bug IMO.
• If the argument is not an element and is not dealt with by pushforward but converts into the domain, my patch fixes a bug (it is now added as doctest).
• Calling pushforward works a lot quicker with my patch.

So, I do think that overall it is a progress. I am now starting doctests, but I think it is ready for review again.

[simon-king-jena]

comment:5

I think there is yet another way to speed things slightly up.

If there is coercion then there is a coerce map. Hence, rather than testing "self._domain.has_coerce_map_from(P)", one could directly request "caller=self._domain.coerce_map_from(P)", and then do "caller(x)" if it is not None. That should be faster than doing "self._domain(x)", because the call method of "self._domain" would request a coerce map as well!

I'll test a bit later. So, it will be "needs work" for two hours or so.

[simon-king-jena]

Work Issues: speed things up

[simon-king-jena]

Attachment: 10496default_call.patch.gz

[simon-king-jena]

comment:6

Here are the same tests again, with the updated patch:

sage: R.<x,y> = QQ[]; phi=R.hom([y,x])
sage: timeit("a=phi(y)")
625 loops, best of 3: 33 µs per loop
sage: timeit("a=phi(5)")
625 loops, best of 3: 39.2 µs per loop
sage: D={(0, 2): -1, (0, 0): -1, (1, 1): 7, (2, 0): 1/3}
sage: phi(D)
-x^2 + 7*x*y + 1/3*y^2 - 1
sage: timeit("a=phi(D)")
625 loops, best of 3: 121 µs per loop
sage: I = R*[x^2*y^4-2*y^2, 3*x*y-y^3]
sage: phi(I)
Ideal (x^4*y^2 - 2*x^2, -x^3 + 3*x*y) of Multivariate Polynomial Ring in x, y over Rational Field
sage: timeit("a=phi(I)")
625 loops, best of 3: 163 µs per loop

I think that are acceptable timings: No significant slowdown, but a significant speedup in one case, and some bug fixes. Back to "needs review", modulo passing doctests...

[simon-king-jena]

comment:7

Doctests do pass for me.

[roed314]

comment:8

Looks good in general. I'm traveling today, but once I have a bit of time I'll take a look at your changes.

[roed314]

comment:9

Looks good to me. You asked about documentation for PY_TYPE_CHECK earlier; I'm not sure where to find documentation, but the functions are included in sage/ext/stdsage.pxi and you can find a list of them there. The other files in that directory are also worth looking at, especially if you're dealing with python objects.

Anyway, positive review.

[jdemeyer]

Changed work issues from speed things up to none

[jdemeyer]

Merged: sage-4.6.2.alpha1