Why did Julia choose nominal typing over structural typing/traits?

Internals & Design
, , ,
1

I’ve been thinking about Julia’s type system design, particularly how it uses nominal typing rather than structural typing or a trait-based system. I’m curious about the historical and technical reasons behind this choice, and what challenges might arise if Julia had gone with a more trait-based approach.

To illustrate my question, here’s a classic example in current Julia using nominal typing:

abstract type Pet end

struct Dog <: Pet 
    name :: String 
end

struct Cat <: Pet 
    name :: String 
end

function encounter(a::Pet, b::Pet)
    verb = meets(a,b)
    println("$(a.name) meets $(b.name) and $verb")
end

meets(a::Dog, b::Dog) = "sniffs"
meets(a::Dog, b::Cat) = "chases"
meets(a::Cat, b::Dog) = "hisses"
meets(a::Cat, b::Cat) = "slinks"

fido     = Dog("Fido")
rex      = Dog("Rex")
whiskers = Cat("Whiskers")
spots    = Cat("Spots")

encounter(fido, rex)
encounter(fido, whiskers)
encounter(whiskers, rex)
encounter(whiskers, spots)

I’m wondering how this might look in a hypothetical trait-based version of Julia. Here’s what I envision:

trait Pet begin
    name(a::Self)::String
end
# Self refers to the type implementing the trait

trait Meetable{T} begin
    meets(a::Self, b::T)::String
end

# trait for pets that can meet each other, <: means that MeetablePet requires all the functions defined in Meetable and Pet traits
trait MeetablePet{T} <: Meetable{T} + Pet where T<:Pet

struct Dog
    name::String
end
name(d::Dog) = d.name

struct Cat
    name::String
end
name(c::Cat) = c.name

meets(a::Dog, b::Dog) = "sniffs"
meets(a::Dog, b::Cat) = "chases"
meets(a::Cat, b::Dog) = "hisses"
meets(a::Cat, b::Cat) = "slinks"

# this type constraints guarantee that a and b are pets that can meet each other
function encounter(a::MeetablePet{T}, b::T) where T <: Pet
    verb = meets(a, b)
    println("$(name(a)) meets $(name(b)) and $verb")
end

fido     = Dog("Fido")
rex      = Dog("Rex")
whiskers = Cat("Whiskers")
spots    = Cat("Spots")

encounter(fido, rex)
encounter(fido, whiskers)
encounter(whiskers, rex)
encounter(whiskers, spots)

This trait-based approach is very expressive and replaces the need for abstract types entirely. Here’s a more complex example showing how it might work with mathematical concepts:

trait Field begin
    +(a::Self, b::Self)::Self
    *(a::Self, b::Self)::Self
    -(a::Self)::Self
    /(a::Self, b::Self)::Self
    inv(a::Self)::Self
    zero(::Type{Self})::Self
    one(::Type{Self})::Self
end

trait VectorSpace{F <: Field} begin
    +(a::Self, b::Self)::Self
    *(f::F, v::Self)::Self
    -(v::Self)::Self
    zero(::Type{Self})::Self
end

trait InnerProductSpace{F} <: VectorSpace{F} where F <: Field begin
    dot(a::Self, b::Self)::F
end

# Example implementation for Float32
primitive type Float32 32 end

+(a::Float32, b::Float32) = Base.add_float(a, b)
-(a::Float32) = Base.neg_float(a)
*(a::Float32, b::Float32) = Base.mul_float(a, b)
inv(a::Float32) = Base.inv_float(a)
zero(::Type{Float32}) = Float32(0.0)
one(::Type{Float32}) = Float32(1.0)
# Float32 is a field, also it is a vector space over itself, if we define dot it will be an inner product space as well
dot(a::Float32, b::Float32) = a * b

# Example implementation for Vec2
struct Vec2{F} where F <: Field
    x::F
    y::F
end

+(a::Vec2{F}, b::Vec2{F}) where F <: Field = Vec2(a.x + b.x, a.y + b.y)
*(f::F, v::Vec2{F}) where F <: Field = Vec2(f*v.x, f*v.y)
*(v::Vec2{F}, f::F) where F <: Field = f*v
-(v::Vec2{F}) where F <: Field = Vec2(-v.x, -v.y)
zero(::Type{Vec2{F}}) where F <: Field = Vec2(zero(F), zero(F))
# Vec2 is a vector space over F, if we define dot it will be an inner product space as well
dot(a::Vec2{F}, b::Vec2{F}) where F <: Field = a.x*b.x + a.y*b.y

This would allow for very generic code as in the current version of julia but it is much more clear what the concrete type has to do to be acceptable by the function. For example, in the current version of julia it is impossible to understand what is expected of the nominal abstract type Number.

function do_computation(v1::V1, v2::V2)::F where {V1 <: InnerProductSpace{F}, V2 <: InnerProductSpace{F}, F <: Field}
    return v2 * (dot(v1, v1) / dot(v2, v2))
end

# Works with different types implementing the same traits
do_computation(Float32(2.43), Float32(1.24))
do_computation(
    Vec2(Float32(2.43), Float32(1.24)), 
    Vec2(Float32(1.0), Float32(2.0))
)

Questions:

  1. What were the main technical challenges that led Julia to choose nominal typing over structural typing/traits?
  2. Would a trait-based system like the one shown above introduce performance penalties compared to the current system?
  3. Would multiple dispatch work differently with traits vs. the current system?
5 Likes
2

This isn’t really hypothetical, you can do this today.

Here’s your traits

struct Not{T} end

struct Pet end
function name end
is_pet(x::T) where {T} = hasmethod(name, Tuple{T}) && (Core.Compiler.return_type(name, Tuple{T}) == String)

struct Meetable end
function meets end
are_meetable(x::T, y::U) where {T, U} = hasmethod(meets, Tuple{T, U}) && (Core.Compiler.return_type(name, Tuple{T}) == String)

struct MeetablePets end
are_meetable_pets(x::T, y::U) = is_pet(x) && is_pet(y) && are_meetable(x, y)
AreMeetablePets(x, y) = are_meetable_pets(x, y) ? MeetablePets() : Not{MeetablePets}()

Now our animals:

struct Dog
    name::String
end
name(d::Dog) = d.name

struct Cat
    name::String
end
name(c::Cat) = c.name

meets(a::Dog, b::Dog) = "sniffs"
meets(a::Dog, b::Cat) = "chases"
meets(a::Cat, b::Dog) = "hisses"
meets(a::Cat, b::Cat) = "slinks"

And now a derived function:

encounter(a, b) = encounter(AreMeetablePets(a, b), a, b)
function encounter(::MeetablePets, a, b)
    verb = meets(a, b)
    println("$(name(a)) meets $(name(b)) and $verb")
end

Finally, lets try it out:

fido     = Dog("Fido")
rex      = Dog("Rex")
whiskers = Cat("Whiskers")
spots    = Cat("Spots")

julia> encounter(fido, rex)
Fido meets Rex and sniffs

julia> encounter(fido, whiskers)
Fido meets Whiskers and chases

julia> encounter(whiskers, rex)
Whiskers meets Rex and hisses

julia> encounter(whiskers, spots)
Whiskers meets Spots and slinks
23 Likes
3
  1. Traits are a form of multiple-abstract-inheritance. If we only had traits instead of regular abstract types, then dispatch would hit many many method ambiguities very fast (we already get a ton of these just from regular multiple dispatch in our linear algebra code). Imagine stuff like trying to decide what multiplication method to use when every matrix has like 3 or 4 traits assigned to it, and there’s a big web of specialized methods for specific matrix traits. This is a difficult problem to do well.
  1. No. It can be just as performant as what we currently do (at least at runtime. Traits often have some more compile-time overhead).
  1. Our current 2-tier system where users have to kinda “wire up” the dispatches for traits manually does still just use regular dispatch, but the extra step makes it easier to avoid ambiguities (but has the downside of making it kind annoying to write trait methods).
21 Likes
4

Thank you very much for your response! The approach using Holy traits is clever, though somewhat verbose and I can imagine is not very LSP/IDE-friendly.

I wasn’t able to find an example where dispatch would quickly encounter numerous method ambiguities without nominal abstract types. It appears that things should work smoothly. For instance:

# Basic field operations trait
trait Field
    +(a::Self, b::Self)::Self
    *(a::Self, b::Self)::Self
    -(a::Self)::Self
    zero(::Type{Self})::Self
    one(::Type{Self})::Self
end

# Base vector trait
trait Vector{F} where F <: Field
    length(v::Self)::Int
    get_element(v::Self, i::Int)::F
end

# Trait for vectors that can be multiplied with other vectors
trait DotproductableVector{F, V} <: Vector{F} where {F <: Field, V <: Vector{F}}
    dot(a::Self, b::V)::F
end

# Specialized vector traits
trait OneHotVector{F} <: Vector{F} where F <: Field
    hot_index(v::Self)::Int
end

trait SparseVector{F} <: Vector{F} where F <: Field
    nonzero_indices(v::Self)::Vector{Int}
    nonzero_values(v::Self)::Vector{F}
end

# Concrete implementations
struct DenseVector{F} where F <: Field
    elements::Vector{F}
end

struct OneHotVectorImpl{F} where F <: Field
    length::Int
    index::Int
end

struct SparseVectorImpl{F} where F <: Field
    length::Int
    indices::Vector{Int}
    values::Vector{F}
end

# Implement base Vector trait functions
length(v::DenseVector) = length(v.elements)
get_element(v::DenseVector, i::Int) = v.elements[i]

length(v::OneHotVectorImpl) = v.length
get_element(v::OneHotVectorImpl{F}, i::Int) where F = i == v.index ? one(F) : zero(F)
hot_index(v::OneHotVectorImpl) = v.index

length(v::SparseVectorImpl) = v.length
get_element(v::SparseVectorImpl{F}, i::Int) where F = 
    let idx = findfirst(==(i), v.indices)
        isnothing(idx) ? zero(F) : v.values[idx]
    end
nonzero_indices(v::SparseVectorImpl) = v.indices
nonzero_values(v::SparseVectorImpl) = v.values

# Dot product implementations for all combinations

# DenseVector with general Vector (fallback)
function dot(a::DenseVector{F}, b::V)::F where {F <: Field, V <: Vector{F}}
    @assert length(a) == length(b) "Vector lengths must match"
    result = zero(F)
    for i in 1:length(a)
        result += a.elements[i] * get_element(b, i)
    end
    result
end

# DenseVector with specific types
function dot(a::DenseVector{F}, b::OneHotVectorImpl{F})::F where F <: Field
    @assert length(a) == length(b) "Vector lengths must match"
    a.elements[hot_index(b)]
end

function dot(a::DenseVector{F}, b::SparseVectorImpl{F})::F where F <: Field
    @assert length(a) == length(b) "Vector lengths must match"
    result = zero(F)
    for (idx, val) in zip(nonzero_indices(b), nonzero_values(b))
        result += a.elements[idx] * val
    end
    result
end

# OneHotVectorImpl with general Vector (fallback)
function dot(a::OneHotVectorImpl{F}, b::V)::F where {F <: Field, V <: Vector{F}}
    @assert length(a) == length(b) "Vector lengths must match"
    get_element(b, hot_index(a))
end

# OneHotVectorImpl with specific types
function dot(a::OneHotVectorImpl{F}, b::DenseVector{F})::F where F <: Field
    dot(b, a)
end

function dot(a::OneHotVectorImpl{F}, b::SparseVectorImpl{F})::F where F <: Field
    @assert length(a) == length(b) "Vector lengths must match"
    idx = findfirst(==(hot_index(a)), nonzero_indices(b))
    isnothing(idx) ? zero(F) : nonzero_values(b)[idx]
end

function dot(a::OneHotVectorImpl{F}, b::OneHotVectorImpl{F})::F where F <: Field
    @assert length(a) == length(b) "Vector lengths must match"
    hot_index(a) == hot_index(b) ? one(F) : zero(F)
end

# SparseVectorImpl with general Vector (fallback)
function dot(a::SparseVectorImpl{F}, b::V)::F where {F <: Field, V <: Vector{F}}
    @assert length(a) == length(b) "Vector lengths must match"
    result = zero(F)
    for (idx, val) in zip(nonzero_indices(a), nonzero_values(a))
        result += val * get_element(b, idx)
    end
    result
end

# SparseVectorImpl with specific types
function dot(a::SparseVectorImpl{F}, b::DenseVector{F})::F where F <: Field
    dot(b, a)
end

function dot(a::SparseVectorImpl{F}, b::OneHotVectorImpl{F})::F where F <: Field
    dot(b, a)
end

function dot(a::SparseVectorImpl{F}, b::SparseVectorImpl{F})::F where F <: Field
    @assert length(a) == length(b) "Vector lengths must match"
    result = zero(F)
    i, j = 1, 1
    a_indices, a_values = nonzero_indices(a), nonzero_values(a)
    b_indices, b_values = nonzero_indices(b), nonzero_values(b)
    
    while i ≤ length(a_indices) && j ≤ length(b_indices)
        if a_indices[i] == b_indices[j]
            result += a_values[i] * b_values[j]
            i += 1
            j += 1
        elseif a_indices[i] < b_indices[j]
            i += 1
        else
            j += 1
        end
    end
    result
end

# some algorithm that uses the dot product
function dot_product_based_algoirthm(a::V, b::W) where {V <: DotproductableVector{F, W}, W <: Vector{F}, F <: Field}
    dot(a, b) * one(F) / dot(a * one(F), b)
end


dense = DenseVector([1.0, 0.0, 0.0, 2.0, 0.0])
onehot = OneHotVectorImpl{Float64}(5, 4)  # One-hot at index 4
sparse = SparseVectorImpl{Float64}(5, [1, 4], [1.0, 2.0])  # Sparse with values at indices 1 and 4

dot_product_based_algoirthm(dense, dense)  # Dense with Dense
dot_product_based_algoirthm(onehot, onehot)  # One-hot with One-hot
dot_product_based_algoirthm(sparse, sparse)  # Sparse with Sparse
dot_product_based_algoirthm(dense, onehot)  # Dense with One-hot
dot_product_based_algoirthm(dense, sparse)  # Dense with Sparse
dot_product_based_algoirthm(onehot, sparse)  # One-hot with Sparse

Can you be provide a sketch of an example where you think trait-based dispatch would lead to hitting many method ambiguities very fast?

5

While I do agree that Holy traits are somewhat awkward to use, I’ll point out that my implementation of your pets example had only a few more lines of code than your pseudo-code, so it’s not that verbose. But yes, I too am interested in finding ways to make this stuff easier to use.

From my point of view, this is just a demonstration that the normal ways people use LSP for languages like julia is just insufficient. These plugins try to give you information code without actually understanding code. This may be fine in some languages, but julia has so much capability for metaprogramming and whatnot that I think one really does just simply need plugins that are fully language aware.

It’s really just a problem that appears at scale. We already very much have this problem in LinearAlgebra.jl with single inheritance, where someone tries to add a method for something and then has to spend a bunch of time playing Whack-A-Mole trying to get rid of all the Ambiguous Method errors. Multiple inheritance at least poses the possibility of making it a lot worse.

Personally, I don’t think this is such a big problem that it’d make me not want more trait support in the language though as a core feature, but a lot of people disagree, or at least are skeptical enough that they don’t want to put any time into working on it.

4 Likes
6

Agreed, though if traits were natively supported, reasoning about code would be more straightforward, even with Julia’s dynamic nature. With native trait support, some “static” type checks could be implemented and displayed through LSP, aiding development and debugging without losing flexibility, especially as the project scales. I can definitely see how this approach could help eliminate the 1.5 language problem by getting rid of type instabilities and related issues and making it at least 1.25 language problem.

I still don’t see how structural typing with traits would worsen this issue. At worst, it seems comparable to nominal typing. In fact, by relying on traits instead of nominal types, there might even be fewer Ambiguous Method errors. I would be interested if someone could provide a counterexample; so far, I haven’t been able to come up with one.

Moreover, in the context of these Rust-like traits, we aren’t dealing with multiple inheritance in the traditional sense. Trait3 <: Trait1 + Trait2 is simply a declaration that for a concrete type to be considered as having Trait3, it must implement all methods listed in Trait1 and Trait2. One might even argue that, in a way, there is no inheritance at all; using a: Trait simply requires additional methods for an instance a of a concrete type to qualify as having the trait Trait, making the system more predictable, less prone to ambiguity, and even improving code reusability, as there is no longer a rigid hierarchy of abstract nominal types, one does not need to inherit some abstract type to qualify to work with some general code, having corresponding associated functions is the only requirement.

1 Like
7

Maybe I misunderstood you, but it seemed you originally were advocating for traits which types automatically become members of if they implement their interface, e.g. a type Dog would become a Pet if it had a method name(::Dog)::String.

Reliably detecting cases like this would be quite difficult with a dumb LSP and really would require actual semantic language integration.

I don’t really know what this means.

The problem here is that traits enable multiple inheritance, which further increases the number of possible ways methods can be ambiguous.

Imagine you have a list of traits A, B, C and some methods of a function

f(::A) = ...
f(::B) = ...
f(::C) = ...

Now imagine you have a type Foo that just happens to satisfy the requirements for traits A, B, and C simultaneously, now suddenly f(::Foo) is triply ambiguous.

Now imagine you have a two-argument form

f(::A, ::A) = ...
f(::A, ::B) = ...
f(::A, ::C) = ...
f(::B, ::A) = ...
f(::B, ::B) = ...
f(::B, ::C) = ...
f(::C, ::A) = ...
f(::C, ::B) = ...
f(::C, ::C) = ...

Now imagine you have two different types Foo and Bar, both of which satisfy all three of those traits A, B, C. Any signature involving f(::Union{Foo, Bar}, ::Union{Foo, Bar}) has a 9-fold ambiguity.

If you think this won’t happen, I implore you to go look at all the different types we have in LinearAlgebra.jl and how they interact through complicated methods like *. * alone has 221 methods defined on it in a fresh REPL session for me:

❯ julia -q
julia> length(methods(*))
221

now let me load some packages up:

julia> using LazyArrays, StaticArrays, SparseArrays, ApproxFun

julia> length(methods(*))
1004

now 1004 different methods. If I had to guess, I’d roughly guess that around half to a quarter of these methods involve an abstract type somewhere in the signature. If these methods were replaced with multiple inheritance traits instead of abstract types, the ambiguity challenges here would be greatly exacerbated.

This doesn’t mean there isn’t a way of dealing with this, but our current approach to ambiguities already barely works with abstract types and unionalls, it’d quickly be intolerable with traits.

9 Likes
8

Here are some references regarding 1.5 Language Problem:

Yes, you’re right; this is nontrivial for concrete types but should be relatively straightforward for a hierarchy of traits. It’s easy to check if one set of methods is a subset of another. If the main goal is code reuse (addressing the expression problem and related issues), the general algorithm input should be expressed in terms of behaviours rather than concrete types anyway, otherwise, it isn’t reusable. This kind of ‘static type inference’ can help clarify how different parts of the code interact and make Julia projects more “growable” and “scalable”.

I still disagree that this is an issue. It’s simply a consequence of having an open structural type system. Instead of explicitly declaring that a concrete type implements a specific trait (as in Rust), this is done implicitly, which greatly increases code reusability. However, as a result, one may need to select the appropriate projection from the space of behaviors available to the concrete data when actually calling the function, for example: f(concrete_variable_x as A, concrete_variable_y as C).

Such a trait system is essentially a way to build behaviour hierarchies for a concrete data that are independent of one another, in contrast to a rigid nominal type system. When calling a function f that handles concrete data along different dimensions of these hierarchies, one may need to specify the projection of data behaviour to use in the example you provided, compiler just can’t predict how you want your data to be interpreted if it has several possible orthogonal behaviour hierarchies.

Can such ambiguity occur for ‘trait types’? Certainly. However, Julia could detect this ambiguity statically and suggest further specialization or indicate that you must manually select the structural type subspace you want to use. For instance, if variables a and b are considered to implement a trait LazySparseArray, but f(a, b) only has methods for (LazyArray, SparseArray), (SparseArray, LazyArray), (LazyArray, LazyArray), and (SparseArray, SparseArray), an ambiguity arises. In this case, the user must decide which perspective to adopt to call f(a, b), and due to the ambiguity, there could even be a compile-time hint suggesting that further specialization (potentially more efficient algorithm implementation) for f(LazySparseArray, LazySparseArray) is possible. Arguably, this is beneficial since you get notified of potential issues up front rather than encountering them at runtime.

Please let me know if I’m overlooking anything. I don’t have extensive experience with programming language design, so I may be missing something obvious.

1 Like
9

We already do this with abstract types and unionall. The problem is that it’s extremely burdensome and brittle. Adding one specialization can create a cascade of downstream ambiguities that then have to be fixed.

This is especially problematic when multiple completely independent packages are adding methods to the same function and can create ambiguities that only manifest when those multiple packages are loaded.

You can say “well just don’t be so open” but if that’s actually the solution to this problem then I’d say the medicine is worse than the disease and I’d rather stick with single inheritance + holy traits.

4 Likes
10

I attended both of those talks, but I don’t really get what they have to do with subtyping to be honest. I have a lot of sympathy for the presenter, I don’t think that what he presented showed that something was wrong with the language, I think it showed how enthusiastic advertising for Julia can sometimes give people unreasonable expectations.

11

I guess I wanted to say that, for example, if you want to mix an integer with a float (a classic example of type instability when calculating the sum of an array), you can’t really do this when using traits as types. On the other hand, if you do want to mix them, you’ll have to declare it explicitly upfront. It seems that with traits the julia code overall should be more type stable, but I am not sure about this.

12

Don’t you think the reason for this is that they reuse the same fixed nominal type system of abstract types, which doesn’t provide any behavioural guarantees?

13

Why not? E.g. Int and Float64 are both vector spaces that satisfy addition, so you can still add them together if + was defined on traits like VectorSpace.

We also could just not allow people to add two different types together, e.g.

julia> (+)(x::T, y::T) where {T <: Number} = Base.:(+)(x, y)
+ (generic function with 1 method)

julia> 1 + 1
2

julia> 1.0 + 1.0
2.0

julia> 1 + 1.0
ERROR: MethodError: no method matching +(::Int64, ::Float64)
You may have intended to import Base.:+
The function `+` exists, but no method is defined for this combination of argument types.

Closest candidates are:
  +(::T, ::T) where T<:Number
   @ Main REPL[1]:1

but this would be horrible and nobody would like it.

The lack of guarentees isn’t the problem. These problems arise even when the types fully fulfill whatever interface they’re subtyping. The problem is just that you can have multiple overlapping methods that apply to the same arguments with the same precedence.

3 Likes
14

Because in your function you would specifically mention the trait that implements + for only the same concrete types. There is no need to not allow people to add two different types together globally:

trait Field begin
    +(a::Self, b::Self)::Self
    *(a::Self, b::Self)::Self
    -(a::Self)::Self
    /(a::Self, b::Self)::Self
    inv(a::Self)::Self
    zero(::Type{Self})::Self
    one(::Type{Self})::Self
end
# Self refers to the type implementing the trait


primitive type Float32 32 end

+(a::Float32, b::Float32) = Base.add_float(a, b)
-(a::Float32) = Base.neg_float(a)
*(a::Float32, b::Float32) = Base.mul_float(a, b)
inv(a::Float32) = Base.inv_float(a)
zero(::Type{Float32}) = Float32(0.0)
one(::Type{Float32}) = Float32(1.0)

primitive type Int32 32  end
+(a::Int32, b::Int32) = Base.add_int(a, b)
-(a::Int32) = Base.neg_int(a)
*(a::Int32, b::Int32) = Base.mul_int(a, b)
inv(a::Int32) = Base.inv_int(a)
zero(::Type{Int32}) = Int32(0)
one(::Type{Int32}) = Int32(1)

# we are not restricting + to have only the same type arguments, we can add two different types
# but to use this method one have to define an appropriate Trait and declare it to be a part of that trait
+(a::Int32, b::Float32) = Float32(a) + b
 
function sum_1(a::Vector{F}) where F <: Field
    result = Int32(0)
    for x in a
        result += x
    end
    result
end

function sum_2(a::Vector{F}) where F <: Field
    result = zero(F)
    for x in a
        result += x
    end
    result
end

my_vec = [Float32(1.0), Float32(2.0), Float32(3.0)]
# sum_1 will not work because by declaring an argument type we strip off all the functions and methods that do not conform to the functions and methods associated with the trait `Vector{F}) where F <: Field`
# and in Field trait we declare +(a::Self, b::Self)::Self, so only the same type plus is allowed, meaning +(a::Int32, b::Float32) is simply not available for the elements of a::Vector{F} where F <: Field
sum_1(my_vec)
# this will work
sum_2(my_vec)
15

I fundamentally disagree with this. There are many many cases where it is not only more efficient but also perfectly sensible to add together two different concrete types.

As one of a million random examples, consider rand(1000, 1000) + I. If this only worked on the same concrete type, the only way to do this would be to do rand(1000, 1000) + collect(I(1000)) which is needlessly slow and unexpressive. (and don’t get me started on multiplication!)

julia> let N = 10000
           A = rand(N, N)
           @btime $A + I
           @btime $A + collect(I($N))
       end;
  76.222 ms (3 allocations: 762.94 MiB)
  158.047 ms (9 allocations: 858.32 MiB)

Even something as basic as adding a Float64 to a Complex{Float64} would be needlessly made twice as slow, and for what benefit?

3 Likes
16

I think it is the problem. Currently julia doesn’t perform this behavioural projections and keeps all methods available to the variables nominal type instead of slicing the behavioural hierarchy according to the trait.

1 Like
17

I think you misunderstood what I was saying. Obviously, there are many cases where it is not only more efficient but also perfectly sensible to add together two different concrete types. However, you have to declare this properly using the corresponding trait.

For example in your case to be able to call a function that uses A + I you have to indicate in the corresponding trait for A that it should be able to do this.

18

Isn’t that what we already do though? E.g. we allow things to be addable if there’s a well defined notation of them being addable, and if not, we don’t define the method.

julia> 1 + im
1 + 1im

julia> 1 + 1//4
5//4

julia> 1 + [1 2; 3 4]
ERROR: MethodError: no method matching +(::Int64, ::Matrix{Int64})
For element-wise addition, use broadcasting with dot syntax: scalar .+ array
The function `+` exists, but no method is defined for this combination of argument types.
1 Like
19

Let me clarify this:
When declaring that argument a adheres to the trait ::Vector{Field} we disallow the usage of all the methods that are outside of this trait. In case of my_vec = [Float32(1.0), Float32(2.0), Float32(3.0)] adding element of the vector and Int(0) is simply not available, hence type stability due to the compiler/runtime error, this hypothetical julia version simply will not allow this type instability. Currently it is impossible in julia to make this behavioural slice and discard the methods that don’t follow the interface.

However, if you wish to do int addition, you have to be explicit about this.

trait MyField{OtherField} <: Field where OtherField<:Field begin 
    +(a::OtherField, b::Self)::Self
end

+(a::Int32, b::Float32) = Float32(a) + b

function sum(a::Vector{F}) where F <: MyField
    result = 0
    for x in a
        result += x # now you can do this because +(a::Int32, b::Float32) exists for ::Vector{F} where F <: MyField
    end
    result
end
20

Yes, and my point is that I always want the ability to add an Int to a Float and a design that tried to disallow that by default would be incredibly obnoxious and counterproductive for mathematical work.

I really just think the medicine you’re offering here is orders of magnitude worse than the disease.

2 Likes