Awkward dunders for pow(x, y, z)

I have been recently working on a library python-flint that provides a type fmpz which is a faster version of Python’s int type similar to gmpy2’s `mpz type:

One thing that I needed to implement was 3-arg pow as in:

>>> from flint import fmpz
>>> pow(fmpz(2), fmpz(3), fmpz(5))
3

What I have found doing this is that the __pow__ dunder that is used for this is awkward to implement and that there is no way from Python (rather than Cython) to extend pow with a dunder on the second or third argument if there are mixed types.

This is how __pow__ should be implemented in Python if wanting to support the 3-arg pow:

# integer.py

_val = lambda x: x.val if isinstance(x, Integer) else x

class Integer:

    def __init__(self, val):
        self.val = val

    def __repr__(self):
        return f'Integer({self.val})'

    # Here mod must be an optional argument
    def __pow__(self, other, mod=None):
        print(f'Called: Integer.__pow__({self}, {other}, {mod})')
        return Integer(pow(_val(self), _val(other), _val(mod)))

    def __rpow__(self, other):
        print(f'Called: Integer.__rpow__({self}, {other})')
        return Integer(pow(_val(other), _val(self)))

For the 2-arg case that gives e.g.:

>>> Integer(2) ** Integer(3)
Called: Integer.__pow__(Integer(2), Integer(3), None)
Integer(8)
>>> Integer(2) ** 3
Called: Integer.__pow__(Integer(2), 3, None)
Integer(8)
>>> 2 ** Integer(3)
Called: Integer.__rpow__(Integer(3), 2)
Integer(8)
>>> pow(2, Integer(3))
Called: Integer.__rpow__(Integer(3), 2)
Integer(8)

Note that the third argument to __pow__ is not actually passed so it needs to be an optional argument like mod=None for this to work.

For the 3-arg case we have:

>>> pow(Integer(2), Integer(3), Integer(5))
Called: Integer.__pow__(Integer(2), Integer(3), Integer(5))
Integer(3)
>>> pow(Integer(2), 3, 5)
Called: Integer.__pow__(Integer(2), 3, 5)
Integer(3)
>>> pow(2, Integer(3), Integer(5))
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for pow(): 'int', 'Integer', 'Integer'

What happens here is that in the 3-arg case pow(x, y, z) will always call type(x).__pow__(x, y, z) and there is no way for the other arguments y and z to influence this.

It is however possible to do this using Cython:

# integer.pyx

_val = lambda x: x.x if isinstance(x, CInteger) else x

cdef class CInteger:

    cdef object _x

    def __init__(self, x):
        self._x = x

    @property
    def x(self):
        return self._x

    def __repr__(self):
        return f'CInteger({self.x})'

    # Here mod must be a required argument
    def __pow__(self, other, mod):
        print(f'CInteger.__pow__({self}, {other}, {mod})')
        return CInteger(pow(_val(self), _val(other), _val(mod)))

    def __rpow__(self, other):
        print(f'CInteger.__rpow__({self}, {other})')
        return CInteger(pow(_val(other), _val(self)))

Then we can pass a CInteger as any of the 3 arguments to pow:

>>> pow(CInteger(2), CInteger(3), CInteger(5))
CInteger.__pow__(CInteger(2), CInteger(3), CInteger(5))
CInteger(3)
>>> pow(2, CInteger(3), CInteger(5))
CInteger.__pow__(2, CInteger(3), CInteger(5))
CInteger(3)
>>> pow(2, 3, CInteger(5))
CInteger.__pow__(2, 3, CInteger(5))
CInteger(3)
>>> pow(2, CInteger(3), 5)
CInteger.__pow__(2, CInteger(3), 5)
CInteger(3)

I got a bit lost in the CPython code trying to trace the whole codepath that make this happen but in the end pow(x, y, z) can end up calling type(y).__pow__(x, y, z) or type(z).__pow__(x, y, z) but there does not seem to be any way to implement the same in plain Python.

I think if I was designing this from scratch then I would not use the same __pow__ dunder for both x**y and pow(x, y, z) and instead have something like __pow3__. Of course there are three arguments to potentially dispatch on so it wouldn’t work just to have __pow3__ and __rpow3__. Perhaps instead it could work like in Cython where the same method is just called with differently typed arguments (so that self is not necessarily the expected type).

    def __pow3__(base, exp, mod):
        return Integer(pow(_val(base), _val(exp), _val(mod)))

Then pow(x, y, z) could in turn try:

  1. type(x).__pow3__(x, y, z)
  2. type(y).__pow3__(x, y, z)
  3. type(z).__pow3__(x, y, z)

I am not sure whether or not it is worth it to add a dunder methods like this. There can be more uses of pow(x, y, z) than just integers to be clear e.g. the same reasons that it makes sense to have a special operation for computing x**y mod z apply to polynomials and many other things besides integers. I am not aware of any libraries using 3-arg pow for anything apart from integers though.

The main thing that I dislike about the current situation is just that it does not seem to be possible in plain Python to make a type for y or z that can overload the behaviour of pow(int(x), y, z) when that is a feature that is being used by some popular python packages like gmpy2 already.

It looks like the code in CPython is made complicated by needing to support this ternary dispatch so maybe there is some better way to eliminate that altogether. I might be misunderstanding this but it looks like there is ternary dispatch code that exists purely for the case of handling 3-arg pow:

I imagine that it is also very difficult for other implementations like PyPy to match CPython’s behaviour here.

Perhaps there should instead be some way for other types to signify that they would like to coerce integers in mixed operations like:

class Integer:
    def __coerce__(self, other):
        if isinstance(other, int):
            return Integer(int_value)
        else:
            return NotImplemented

Then it would be possible for the pow builtin to coerce the types in some defined order and then call the appropriate __pow__ (or __pow3__) method. There are lots of other situations where being able to coerce types systematically would be useful.

1 Like

Interestring write-up.

This would be so much easier if multiple dispatch were natively used for binary and ternary operators.

Agreed. The approach of having e.g. __add__ and __radd__ for “coperative dispatch” is awkward and error-prone compared to proper multiple dispatch. The case of 3-arg pow shows where this cooperative dispatch gets pushed clearly beyond its limits.

1 Like

I think this ship has sailed. We can definitely not change the rules around __add__ and __radd__ (and similar) without drastic impact on backward incompatibility, which we are not willing to do.

For 3-arg pow(), I believe the use case is not important enough for the complications that were introduced to __pow__ relative to the other binary operators, decades ago. Again, backwards compatibility makes it essentially impossible to change, but if we could change anything there, I would “solve” the problem by deprecating 3-arg pow().

4 Likes

To be clear there is an open bug report in python-flint related to this with the most recent release of PyPy (7.3.12):

The fact that this feature (pow(2, fmpz(3), 5)) can only be implemented via the C API and (as far as I can tell) only by depending on subtle details of CPython’s type structs probably explains why it is hard to make something like this work across different Python implementations.

Potentially that bug report could be considered just a PyPy bug simply for PyPy not being compatible with CPython but there is no documentation anywhere that explains how any of this is supposed to work so it’s hard to say that PyPy is doing anything incorrect. Alternatively maybe it is a python-flint or Cython bug for depending on some subtle CPython details that were not supposed to be depended on. I am sure that other widely used code (at least gmpy2) depends on this as well though.

There is the same issue in the stdlib. The difference between the C and Python implementations of Decimal:

>>> from decimal import Decimal
>>> pow(10, Decimal(2), 7)
Decimal('2')
>>> pow(10, 2, Decimal(7))
Decimal('2')
>>> from _pydecimal import Decimal
>>> pow(10, Decimal(2), 7)
Traceback (most recent call last):
  File "<python-input-4>", line 1, in <module>
    pow(10, Decimal(2), 7)
    ~~~^^^^^^^^^^^^^^^^^^^
TypeError: unsupported operand type(s) for ** or pow(): 'int', 'Decimal', 'int'
>>> pow(10, 2, Decimal(7))
Traceback (most recent call last):
  File "<python-input-5>", line 1, in <module>
    pow(10, 2, Decimal(7))
    ~~~^^^^^^^^^^^^^^^^^^^
TypeError: unsupported operand type(s) for ** or pow(): 'int', 'int', 'Decimal'

2-argument pow() works with any combination of arguments.

The dispatching code for the second argument in 3-argument pow() can harmonized with 2-argument variant. But for dispatching on the third argument we need a separate special method, e.g. __mpow__(mod, base, exp), if follow tradition of special methods for binary operations.

Alternatively, we could have a single special method for direct and reverse operation, as was proposed above. Actually, extension classes have a single slot nb_subtract while Python classes have __sub__ and __rsub__ methods. The behavior is more complicated than it is described in the documentation, because it is really difficult to document such complicated behavior. It somehow works,… except when it doesn’t, like in this case.

I think that adding the __mpow__ method is simpler solution.

I think we should just follow to the PyNumber_Power() implementation (the only case for ternary_op()). Note that for two first arguments it follows to binary_op1() (gh-130104: Call __rpow__ in ternary pow() if necessary by serhiy-storchaka · Pull Request #130251 · python/cpython · GitHub adds similar behavior for pure-Python analog), but next it just try the last argument slot as a fallback (no checks if other arguments are subtypes of third, etc). So, single dunder seems to be enough to permit dispatching for third argument.

I would like also to bring attention to related issue: PyNumber_InPlacePower ignores o3 if o1 implements __ipow__ · Issue #86069 · python/cpython · GitHub. Per current state, the third argument of __ipow__() is ignored. Even if we add support for third argument in PyNumber_InPlacePower() (see gh-86069: Do not ignore the third argument in slot_nb_inplace_power() by serhiy-storchaka · Pull Request #130225 · python/cpython · GitHub), this will be not available for pure-Python.

I suggest removing the third argument in __ipow__(). Lets not introduce yet another pow()-like beast, even hypothetical.

There are three issues:

  1. __rpow__ in Python class is not called for the three-argument power. It is called for the two-argument power, and nb_power is called for extension classes. So currently there is a disparity between the two-argument and the two-argument power and between Python and extension classes. This can be fixed by calling __rpow__ for the three-argument power in the same way as for the two-argument power.
  2. There is no special in Python classes to dispatch on the third argument for the three-argument power. nb_power is called for extension classes. So currently there is a disparity between Python and extension classes. This can be fixed by introducing a new special method.
  3. The third argument of PyNumber_InPlacePower() (there is no Python equivalent) is ignored for Python classes implementing __ipow__. It is not ignored if the Python class does not implement __ipow__, and it is not ignored for extension classes. This can be fixed by passing the third argument to __ipow__.

Fixes for 1 and 3 can break existing code that does not follow the documentation (including some code in the stdlib), but this is a fault of that code. This is the simplest way to make behavior consistent between all versions of power, between Python and extension classes. Other way (using the same special method for direct and reverse operations) is more destructive.

1 Like

Personally, I would really miss this functionality. The efficient raised-to-mod logic is something that I’ve used many times. And while that isn’t hard to code manually, the case with exp=-1 for computing modular multiplicative inverses is more challenging.

Why break the code of people who use this just to solve a relatively minor irritant? Besides backwards compatibility, I think practicality-beats-purity applies as well.

No one is actually proposing to remove this. In retrospect though it would be better if this was provided by some other mechanism than __pow__ and probably it should be a different function like powmod rather than calling pow with three arguments.

2 Likes

Could you, please, elaborate?

What’s is “this functionality for you”? Do you care only about builtin int’s? Or use this for custom types?

This may require a PEP.

I’d rather pow just be implemented by multiple dispatch rather than try to shoehorn it into the binary dunders __pow__ and __rpow__. It was never going to be a good fit for that.