Associativity of promote_type

Internals & Design
1

I found this via a bug report in JuMP: Error vcat(::NonlinearExpr, ::VariableRef, ::Float64) · Issue #3671 · jump-dev/JuMP.jl · GitHub.

promote_type has an implicit assumption of associativity, i.e.:

promote_type(A, promote_type(B, C)) == promote_type(promote_type(A, B), C)

That’s because the implementation is essentially promote_type(A, args...) = promote_type(A, promote_type(args...)).

This causes issues:

julia> struct Foo; x::Int end

julia> struct Bar; x::Int end

julia> Base.convert(::Type{Foo}, b::Bar) = Foo(b.x)

julia> Base.convert(::Type{Bar}, x::Int) = Bar(x)

julia> Base.promote_rule(::Type{Foo}, ::Type{Bar}) = Foo

julia> Base.promote_rule(::Type{Bar}, ::Type{Int}) = Bar

julia> promote_type(Foo, Bar, Int)
Foo

julia> promote_type(Foo, Int, Bar)
Foo

julia> promote_type(Bar, Foo, Int)
Any

julia> promote_type(Bar, Int, Foo)
Any

julia> promote_type(Int, Foo, Bar)
Any

julia> promote_type(Int, Foo, Bar)
Any

julia> promote_type(Int, Bar, Foo)
Any

Depending on the order of arguments, the type might be Foo or Any.

If it is Foo, then we are missing a direct convert method convert(::Type{Foo}, ::Int)

julia> [3, Foo(1), Bar(2)]
3-element Vector{Any}:
3
Foo(1)
Bar(2)

julia> [Foo(1), Bar(2), 3]
ERROR: MethodError: Cannot `convert` an object of type Int64 to an object of type Foo
Closest candidates are:
convert(::Type{Foo}, ::Bar)
@ Main REPL[105]:1
convert(::Type{T}, ::T) where T
@ Base Base.jl:84
Foo(::Int64)
@ Main REPL[103]:1
...
Stacktrace:
[1] setindex!(A::Vector{Foo}, x::Int64, i1::Int64)
@ Base ./array.jl:1021
[2] (::Base.var"#114#115"{Vector{Foo}})(i::Int64, v::Int64)
@ Base ./array.jl:456
[3] afoldl(::Base.var"#114#115"{Vector{Foo}}, ::Int64, ::Foo, ::Bar, ::Int64)
@ Base ./operators.jl:546
[4] getindex(::Type{Foo}, ::Foo, ::Bar, ::Int64)
@ Base ./array.jl:455
[5] vect(::Foo, ::Vararg{Any})
@ Base ./array.jl:187
[6] top-level scope
@ REPL[115]:1

Questions:

  • Am I a fool for not defining the necessary promote_rule and converts needed for associativity? I didn’t really want Int to be promoted to Foo! I wanted the Any. (But I do want Int to be promoted to Bar when needed.)

or in other words:

  • Is it expected behavior? I assume so.
  • How can one ensure that any user-defined promote_rules satisfy associativity? Just manual inspection + tests?
6 Likes
2

FYI, the implementation has changed for the nightly build since March 2024.

Two important things to note here are:

  • We can’t try every pair because of the combinatorial explosion.
  • The change in the order is not considered a so-called breaking change (for now).
1 Like
3

Is this a problem in practice? Your example seems a bit artificial. If one has a non-associative binary operation, it probably wouldn’t be invoked with more than 2 arguments anyway. But maybe 2-argument promote_type wouldn’t be sufficient for operations that inherently take more than 2 arguments.

It makes me wonder if promote_type should dispatch on the function as well as the argument types.

4

Yes, this was a bug in JuMP. See the link in the first post. Ive since fixed by adding the missing convert method.

5

There’s no need for that, because if you want to do something specific to a particular function, you can implement whatever rule you want simply as a method of that function, e.g.

myfunc(x::Number, y::Number) = x + y
myfunc(x::Float16, y::Int) = myfunc(Float64(x), y) # custom promotion rule
1 Like
6

To be honest, I would expect promote_type to be order-independent, i.e., to commute, as well. Fail to see how it could be useful to have the promoted type be different due to ordering?

7

As I wrote above, we do so not because it is useful, but because there is no other way.
Order dependencies can occur even if there are no obvious bugs.

julia> VERSION
v"1.6.7"

julia> [0.0f0, Complex(0,1), pi] |> typeof
Vector{ComplexF64} (alias for Array{Complex{Float64}, 1})

julia> [0.0f0, pi, Complex(0,1)] |> typeof
Vector{ComplexF64} (alias for Array{Complex{Float64}, 1})

julia> [Complex(0,1), 0.0f0, pi] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [Complex(0,1), pi, 0.0f0] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [pi, 0.0f0, Complex(0,1)] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [pi, Complex(0,1), 0.0f0] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> VERSION
v"1.12.0-DEV.283"

julia> [0.0f0, Complex(0,1), pi] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [0.0f0, pi, Complex(0,1)] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [Complex(0,1), 0.0f0, pi] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [Complex(0,1), pi, 0.0f0] |> typeof
Vector{ComplexF64} (alias for Array{Complex{Float64}, 1})

julia> [pi, 0.0f0, Complex(0,1)] |> typeof
Vector{ComplexF32} (alias for Array{Complex{Float32}, 1})

julia> [pi, Complex(0,1), 0.0f0] |> typeof
Vector{ComplexF64} (alias for Array{Complex{Float64}, 1})
1 Like