Implement @traitfn macro

[tk3369]

Fixes #2. See examples/dispatch.jl for some examples.

Status

• [x] implement @holy macro
• [x] implement test cases and ensure test coverage
• [x] update documentation

[codecov[bot]]

Codecov Report

Merging #49 into master will decrease coverage by 0.31%. The diff coverage is 98.46%.

@@             Coverage Diff             @@
##            master      #49      +/-   ##
===========================================
- Coverage   100.00%   99.68%   -0.32%     
===========================================
  Files            7        8       +1     
  Lines          249      313      +64     
===========================================
+ Hits           249      312      +63     
- Misses           0        1       +1     

Impacted Files	Coverage Δ
src/BinaryTraits.jl	100.00% <ø> (ø)
src/traitfn.jl	98.43% <98.43%> (ø)
src/utils.jl	100.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 5d04a88...1c52b65. Read the comment docs.

[tk3369]

The multi-trait dispatch example begs the question whether a separate syntax may be useful 🤔

In the case that there is a priority about the traits during dispatch, then we can provide a pattern matching syntax as follows:

@switch function locate(v::BinaryTrait, i::Integer)
    Is{Indexable}   => v[1]
    Is{Collectable} => collect(v)[1]
end

So, if the argument v is both Indexable and Collectable, then it is dispatched to v[1] because it comes first in the pattern matching list.

The only caveat is that it wouldn't work too well when there's more than one argument that needs traits-based dispatch. Is that a common use case though? I doubt...

[tk3369]

Looks like this could work for https://github.com/zenna/OmegaCore.jl/issues/6?

# OmegaCore example

# basic traits
@trait Err
@trait LogPdf
@trait Mem
@trait Intervene

# composite trait
@trait LogPdfErr with Is{LogPdf}, Is{Err}

# assignments
@assign Vector with Is{LogPdfErr}

# Holy Traits dispatch
@holy f(x::Is{LogPdfErr}) = 2
@holy f(x::Not{LogPdfErr}) = 1.0

# check type inference
@code_warntype f(1)
#=
julia> @code_warntype f(1)
Variables
  #self#::Core.Compiler.Const(f, false)
  x::Int64

Body::Float64
1 ─ %1 = BinaryTraits.trait::Core.Compiler.Const(BinaryTraits.trait, false)
│   %2 = (%1)(LogPdfErr, $(Expr(:static_parameter, 1)))::Core.Compiler.Const(Negative{LogPdfErr}(), false)
│   %3 = Main.f(%2, x)::Core.Compiler.Const(1.0, false)
└──      return %3

julia> @code_warntype f([1,2])
Variables
  #self#::Core.Compiler.Const(f, false)
  x::Array{Int64,1}

Body::Int64
1 ─ %1 = BinaryTraits.trait::Core.Compiler.Const(BinaryTraits.trait, false)
│   %2 = (%1)(LogPdfErr, $(Expr(:static_parameter, 1)))::Core.Compiler.Const(Positive{LogPdfErr}(), false)
│   %3 = Main.f(%2, x)::Core.Compiler.Const(2, false)
└──      return %3
=#

[zenna]

Hi @tk3369.

The last approach I came to in that issue (which was just me thinking out loud, I didn't expect anyone to read it!) has been working quite well for me. One thing it allows me to do is conjunctive traits. So f(x::trait(LogErr, Mem)) is more specific than f(x::trait(LogErr)) in the sense that if the type of x has both traits LogErr and Mem it will dispatch to the first method rather than the second.

Does your approach allow that?

Zenna

[tk3369]

@zenna It currently supports composite traits as shown above.

However, there is no concept of specificity at the moment. In the above example, you cannot do this.

@holy f(x::Is{LogPdf}) = "general"
@holy f(x::Is{LogPdfErr}) = "more specific"

That's because every argument can only be occupied with exactly one trait. In order to dispatch on two different traits, you would have to "distribute" the object to multiple arguments as show in this example: https://github.com/tk3369/BinaryTraits.jl/blob/master/examples/dispatch.jl#L69lL75

How important is this requirement in your use case? Can you elaborate a little more?

[zenna]

The idea is simply that types have many traits, i.e. they can be conjunctive, e.g. TraitA & TraitB & TraitC. And if you remove a clause from a conjunction then it is less specific TraitA & TraitB & TraitC. is more specific than TraitA & TraitB. I want to be able to write methods for conjunctions and the dispatch to work correctly, i.e. it will dispatch to the most specific method. My little system does with a little trick using Unions and it is working for me nicely. I was thinking of generalising it and making it a little trait package but then thought maybe you have already done it.

A not-very-good hypothetical example:

sort(x) = sort(traits(x), x)
sort(::trait(IsIndexable, IsIterable), x) = "super efficient sorting method"
sort(::trait(IsIndexable), x) = "good sorting method"
sort(::trait(isIterable), x) = "ok sorting method"

My particular use case is pretty obscure. In brief, I implement a mini version of Cassette like contextual dispatch (I'm not using Cassette to avoid performance gotchas) where I attach metadata tags to the context. I need to spcialise the contextual execution depending on which combination of tags I have added to the context.

[AriMKatz]

Something like this: https://julialang.zulipchat.com/#narrow/stream/137791-general/topic/Traits.2C.20ambiguities.20and.20multiple.20inheritance/near/201988123 ?

[tk3369]

The slippery slope here is the potential ambiguity that people worry about. Let's say I forgot to define the more efficient sorting method:

sort(x) = sort(traits(x), x)
sort(::trait(IsIndexable), x) = "good sorting method"
sort(::trait(isIterable), x) = "ok sorting method"

Then it becomes ambiguous when an object is both indexable and iterable. It appears to be more convenient to allow the syntax that you mentioned above but it's not without drawbacks.

When you solve it with multiple dispatch as in this example, it would just resort to standard Julia ambiguity rules.

[zenna]

My approach has the same (normal julia) ambiguity rules. Here's a real example:

julia> fakesort(ω) = fakesort(traits(ω), ω)
fakesort (generic function with 1 method)

julia> fakesort(::trait(Rng), ω) = "good sorting method"
fakesort (generic function with 2 methods)

julia> fakesort(::trait(Err), ω) = "ok sorting method"
fakesort (generic function with 3 methods)

# details not important, just creates a value ω whose type has both traits
julia> ω = OmegaCore.tagrng(defΩ()(), Random.MersenneTwister())
julia> ω_ = OmegaCore.tagerror(ω, false)

julia> traits(ω_)
(OmegaCore.Tagging.Rng, OmegaCore.Tagging.Err)
Trait{Union{Err, Rng}}()

julia> fakesort(ω_)
ERROR: MethodError: fakesort(::Trait{Union{Err, Rng}}, ::LazyΩ{NamedTuple{(:rng, :err),Tuple{MersenneTwister,OmegaCore.Util.Box{Bool}}},Dict{Array{Int64,1},Tuple{Any,Any}}}) is ambiguous. Candidates:
  fakesort(::Trait{T} where T>:Rng, ω) in Main at REPL[29]:1
  fakesort(::Trait{T} where T>:Err, ω) in Main at REPL[30]:1
Possible fix, define
  fakesort(::Trait{T} where T>:Union{Rng, Err}, ::Any)
Stacktrace:
 [1] fakesort(::LazyΩ{NamedTuple{(:rng, :err),Tuple{MersenneTwister,OmegaCore.Util.Box{Bool}}},Dict{Array{Int64,1},Tuple{Any,Any}}}) at ./REPL[28]:1
 [2] top-level scope at REPL[40]:1

I think your approach is fine too. The only problem with it is that it means the trait dispatch function needs t be responsible for deciding how many possible traits you might want to dispatch on.

[zenna]

Which is not a trivial point, or matter of syntax only. To make a comparison, much of the power of multiple dispatch is that you can add more and more specific methods afterwards, without having to go back and renegotiate with the central authority. To put it another way, why do specificity rules exist at all? I think the answer is mostly to be able to incrementally add more specialised versions without making changes of global structure.

[tk3369]

It gets complicated though. Which one is most specific here?

foo(x) = foo(traits(x), x)
foo(::trait{A,B}, x) = "cool"
foo(::trait{B,C}, x) = "cooler"
foo(::trait{A,B,C}, x) = "coolest" 
foo(::trait{A,B,C,D,E,F}, x) = "super cool" 

foo(a) # a has traits A,C

[zenna]

Well it's partially ordered.

addA(ω) = OmegaCore.tag(ω, (err = true,))
addB(ω) = OmegaCore.tag(ω, (rng = true,))
addC(ω) = OmegaCore.tag(ω, (intervene = true,))
addD(ω) = OmegaCore.tag(ω, (logpdf = true,))
addE(ω) = OmegaCore.tag(ω, (scope = true,))
ω = defΩ()()

A = OmegaCore.Err
B = OmegaCore.Rng
C = OmegaCore.Intervene
D = OmegaCore.LogPdf
E = OmegaCore.Scope

foo(x) = foo(traits(x), x)
foo(::trait(A,B), x) = "cool"
foo(::trait(B,C), x) = "cooler"
foo(::trait(A,B,C), x) = "coolest" 
foo(::trait(A,B,C,D,E), x) = "super cool" 

julia> foo(ω |> addA)
ERROR: MethodError: no method matching foo(::Trait{OmegaCore.Tagging.Err}, ::LazyΩ{NamedTuple{(:err,),Tuple{Bool}},Dict{Array{Int64,1},Tuple{Any,Any}}})
Closest candidates are:
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Intervene, OmegaCore.Tagging.LogPdf, OmegaCore.Tagging.Rng, OmegaCore.Tagging.Scope}, ::Any) at REPL[58]:1
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Intervene, OmegaCore.Tagging.Rng}, ::Any) at REPL[57]:1
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Rng}, ::Any) at REPL[55]:1
  ...
Stacktrace:
 [1] foo(::LazyΩ{NamedTuple{(:err,),Tuple{Bool}},Dict{Array{Int64,1},Tuple{Any,Any}}}) at ./REPL[54]:1
 [2] top-level scope at REPL[76]:1

julia> foo(ω |> addA |> addB)
"cool"

julia> foo(ω |> addB |> addC)
"cooler"

julia> foo(ω |> addB |> addC |> addD)
"cooler"

julia> foo(ω |> addB)
ERROR: MethodError: no method matching foo(::Trait{OmegaCore.Tagging.Rng}, ::LazyΩ{NamedTuple{(:rng,),Tuple{Bool}},Dict{Array{Int64,1},Tuple{Any,Any}}})
Closest candidates are:
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Intervene, OmegaCore.Tagging.LogPdf, OmegaCore.Tagging.Rng, OmegaCore.Tagging.Scope}, ::Any) at REPL[58]:1
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Intervene, OmegaCore.Tagging.Rng}, ::Any) at REPL[57]:1
  foo(::Trait{T} where T>:Union{OmegaCore.Tagging.Err, OmegaCore.Tagging.Rng}, ::Any) at REPL[55]:1
  ...
Stacktrace:
 [1] foo(::LazyΩ{NamedTuple{(:rng,),Tuple{Bool}},Dict{Array{Int64,1},Tuple{Any,Any}}}) at ./REPL[54]:1
 [2] top-level scope at REPL[80]:1

[zenna]

Almost forgot

julia> foo(ω |> addA |> addB |> addC |> addD |> addE)
(OmegaCore.Tagging.Err, OmegaCore.Tagging.Rng, OmegaCore.Tagging.Intervene, OmegaCore.Tagging.LogPdf, OmegaCore.Tagging.Scope)
"super cool"

[tk3369]

I see. So the order of traits is important e.g.trait(A,B,C) != trait(B,A,C)?

[zenna]

No trait(A,B,C) == trait(B,A,C). Sorry my comment that it is a partial order was not very informative. Trait conjunctions are ordered by inclusion so to answer your question concretely trait(A,B,C,D,E,F) is the most specific in your example. But not every pair of trait conjunctions are comparable in that sense, for instance trait(A, B) is not more or less specific than trait(E, D). Hence it is a partial order. I just want to stress that I haven't made new specificity rules; I am hijacking the ordinary Julia ones.

By your questions, I get the sense that either there is a major flaw in my understanding of my own system or I have failed to communicate the main ideas, so let me just quickly restate them:

1. Each type T can have a conjunction of traits.
2. Internally a trait is just a singleton type struct SomeTrait end
3. Internally a trait conjunction is Trait{Union{TRAIT1, TRAIT2, TRAIT2....}} where TRAIT is a singleton trait type
4. The function traits(T) returns that conjunction of traits. Internally it returns a value (not type) of the trait conjunction e.g. traits(::Vector) = Trait{Union{A, B, C}}().
5. A function foo(::trait(A, B, C)) will apply to only those T whereby traits(T) includes A and B and C. Note that trait and traits are different function; come to think of it, trait would better be named trait_conjunction_dispatch_type or something.
6. If traits(T) contains A and B and C and D and there is another method foo(::trait(A, B, C, D)) then this latter method is more specific and will take precedence over the former one.
7. Internally traits T is a simple function:

@inline trait(x::Type{X}) where X = Trait{T} where {T >: X}
@inline trait(x1, x2) = trait(Union{x1, x2})
@inline trait(x1, x2, x3) = trait(Union{x1, x2, x3})
@inline trait(x1, x2, x3, x4) = trait(Union{x1, x2, x3, x4})
...

[zenna]

What my system lacks is the ability to add traits add-hocly. I don't have anything like your @implement, which is vital for a useful general trait system but not required for Omega. There are a few ways I could think to do this, but I haven't found a way that doesn't require some sorcery with generated functions (basically the same approach they take in https://github.com/cstjean/ConferenceCall.jl).

[tk3369]

Thanks for the excellent explanation. I now understand better how your system works.

Suppose that I define a function foo with a trait A. So, I can happily dispatch to the following function:

foo(::trait(A), x)

Then, if I add a new trait B to the type of x. Do I now need to redefine the function as foo(::trait(A,B), x) even though the foo function doesn't really care about trait B?

[zenna]

no

the function foo(::trait(A), x) will dispatch on x if it has both A and B. If you add another function foo(::trait(A,B), x) then that latter function will take preference since it is more specific.

[tk3369]

That's great! I think your approach is quite solid.

To be honest, my only concern is that the code may be more difficult to read/understand. Let's say I am debugging where foo(x) is dispatched to. Given a set of trait-based foo functions, I would have to reason which one is the most specific. Maybe it's just me, I just need more time to get used to this.

[zenna]

Fair enough! I would only add that which is most specific is what Julia programs do all the time. Admittedly we normally do that with the subtype relation, but Julia also does it for unions.

I have a question for you though; what's the high-level mechanism you use for giving multiple traits to a type. Is it the same as the Holy method?

[tk3369]

It's basically Holy Traits. I'm just adding icing on top.

[tk3369]

@KlausC This is a very interesting discussion. Let us know if you have any thoughts from your perspective.