JuliaLang / julia

The Julia Programming Language
https://julialang.org/
MIT License
45.69k stars 5.48k forks source link

More correct inference for the return type of exponentiation #53504

Closed brainandforce closed 3 weeks ago

brainandforce commented 8 months ago

The function Base.to_power_type(x) is found here and defined below:

to_power_type(x) = convert(Base._return_type(*, Tuple{typeof(x), typeof(x)}), x)

This function is used in Base.power_by_squaring to determine what type the result should be. I think the definition above is flawed, and we should be using this:

power_type(::Type{T}) where T = promote_type(Base._return_type(*, Tuple{T, T}), T, Base._return_type(one, Tuple{T}))

to_power_type(x::T) where T = convert(power_type(T), x)

But why, you ask?

In the general case, to maintain type stability, the output of Base.power_by_squaring(x, n) needs to be a type that can store x^0, x, and x^2. However, one(x), which is used to calculate x^0, may be a different type from x or x*x:

If possible, one(x) returns a value of the same type as x, and one(T) returns a value of type T. However, this may not be the case for types representing dimensionful quantities (e.g. time in days), since the multiplicative identity must be dimensionless. In that case, one(x) should return an identity value of the same precision (and shape, for matrices) as x.

I am currently writing a package, CliffordNumbers.jl, which has some data types T (such as KVector{K} when K is odd) for which neither typeof(one(T)) nor Base._return_type(*, Tuple{T, T}) are T. This causes exponentiation to fail without some workarounds because the input is not always convertable to the result of Base._return_type(*, Tuple{T, T}).

The problem I faced might be a really niche edge case, but I think the way integer powers of types are handled in cases where they are not equivalent to the type itself is worth discussing and refining. The solution I present would completely solve my issues (though I have already solved them within the package), but I'm not sure if it's too much of a breaking change.

nsajko commented 2 months ago

The proper fix is not to use type inference at all from ^.

xref #24151

mbauman commented 2 months ago

Why are we even trying to do this in the first place? I get the idea — it's trying to ensure type stability — but does it even work more often than it fails? What are the datatypes for which typeof(x) != typeof(x*x) but typeof(x*x) == typeof(x*x*x)?

OK, two cases are im and Char. Are there more? Maybe this is more common than I first thought. In the Char case, there's not even a one(::Char) method defined.

nsajko commented 2 months ago

@mbauman this was initially introduced to fix #11383, for Irrational

That said, I'm pretty sure the right thing to do here is to use promote. Testing that fix rn.