[WIP] first stab at parametrically-typed trait (e.g. monad)

[tonyhffong]

Very experimental. Do not merge.

Just trying to get this out to get some feedback.

The key new thing is that trait definition allows another layer of curly, i.e.

@traitdef MyParamTrait{X{Y}} begin
...
end

So that any datatype supplied must be parametric. How do we get Y in actual usage? we have two choices

• tpar1. First non-TypeVar parameters in X.parameters
• tparlast. Last non-TypeVar parameters in X.parameters

I'm not sure which one is more kosher, and how to switch to the other one if we want to (a syntax issue).

Also, istrait currently cannot successfully test if a parametric datatype can satisfy a trait. There is still work to do.

I have made a simple "Nullable monad" example using this framework.

[mauro3]

Cool that you're having a stab at this! I haven't read up on monads yet but couldn't this be done with associated types within the current framework of Traits.jl? Like so:

@traitdef Monad{X,Y} begin
    XY = X{Y} # this is an associated type
    mreturn(::X, Y) -> XY # we cannot infer X so we have to supply it
    bind( XY, FuncFullSig{Y, XY} ) -> XY
end

[tonyhffong]

Yes, you are probably right in this case, but I can imagine when we need to coordinate a few parametric types to interact in a specific ways, like so

@traitdef FastIndexable{C{X}, I{X}} begin
# contracts requiring the same parametric data type supplied to both C and I
end

In any case, I don't really have all the answers but this is kind of fun.

[mauro3]

I agree that it might be nice to have some sugar to get at type parameters but probably not just now until things settle down a bit. Unless, of course, it turns out it's not sugar but an essential nutrient. I look forward to the completed monad example...

[tonyhffong]

Actually, after thinking some more about the frame work, I can make the following distinction

• a multi-typed trait, MyTr{X,Y} is to establish a contract between type X and Y. For example, we have istrait( Arith{Int,Int} ) to establish arithmetic rules between two Ints.
• a parametric-typed trait, MyParaTr{X{Y}} does not establish a contract between X and Y. It establishes a contract on X itself that it must take at least one type parameter Y and there are some rules on how X uses Y. For example, Nullable{Int} should not establish a contract between Nullable and Int at all, and we should never have to ask istrait( MyParaTr{Nullable,Int} ) which seems silly. Rather we should either ask istrait( MyParaTr{Nullable} ) which just means, for all type parameter Nullable takes, do we have all the methods in place to satisfy the trait rules? (A very hard question to answer); or istrait( MyParaTr{Nullable{Int} } ), which asks if specifically, when Int is provided, that we satisfy the stipulated trait rules of a MyParaTr. (a simpler question to answer).

The rest of Traits.jl mechanism probably warrants this viewpoint. I probably want to do this

@traitfn tf{ X; MyParaTr{X} }( x::X ) = ...

So X could be Set{Int}, for instance, and the package figures out if istrait( MyPara{Set{Int} } ) is true.

I probably don't want to spell it out here for Trait.jl that X is actually parametric, like this:

@traitfn tf{ X,Y; MyParaTr{X,Y} }( x::X{Y} ) = ...

That'd be very unwieldy.

[mauro3]

I think what you spell out with your second bullet point is exactly the use-case for associated types. I can try to dig up my old internet searches on those, here one link: http://nattermorphisms.blogspot.ch/2008/10/2-minute-intro-to-associated-types-type.html Traits.jl has "Associated (Data) Type" in his classification. But rust has some better descriptions.

The way to implement it then is:

@traitdef Monad{XY} begin # so XY could be Nullable{Int}, Nullable by itself does not work!
    X = Traits.deparameterize_type(XY)
    Y = XY.parameters[1]
    mreturn(::X, Y) -> XY # we cannot infer X so we have to supply it
    bind( XY, FuncFullSig{Y, XY} ) -> XY
end
@assert istrait(Monad{Array{Int,1}})

Note that istrait( MyParaTr{Nullable} ) without a type parameter cannot be used in Traits.jl at the moment. This will probably stay like this as, as you pointed out, figuring out whether MyParaTr is satisfied for all parameters is hard and, I think, also brittle.

[tonyhffong]

Yes on the @traitdef side the handling of extra curly would macroexpand into pretty much your code, so it is essentially just a syntactic sugar. That said, I think an improved book-keeping of the intermediate type variables is certainly handy in expressing the signatures

ex = :( @traitdef Monad{X{Y}} begin
    mreturn(::X, Y) -> X{Y}
    bind( X{Y}, FuncFullSig{Y, X{Y}} ) -> X{Y}
end )
macroexpand(ex)
# note the popping of type parameters, and curly can be chained e.g. MyType{X}{Y} == Mytype{X,Y}
:(immutable Monad{X} <: Traits.Trait{()} # /Users/tonyfong/.julia/v0.4/Traits/src/traitdef.jl, line 321:
        methods::Dict{Union(Function,DataType),Tuple} # line 322:
        constraints::Vector{Bool} # line 323:
        assoctyps::Vector{TypeVar} # line 324:
        function Monad() # /Users/tonyfong/.julia/v0.4/Traits/src/traitdef.jl, line 325:
            begin
                X0 = Traits.tparpop(X)
                Y = Traits.tparlast(X)
                assoctyps = TypeVar[TypeVar(symbol("X0"),X0),TypeVar(symbol("Y"),Y)]
            end # line 326:
            new($(Expr(:dict, :(mreturn => ((Type{X0},Y),(X0{Y},))), :(bind => ((X0{Y},FuncFullSig{Y,X0{Y}}),(X0{Y},))))),Bool[],assoctyps)
        end
    end)

Also, since we cannot test traitimpl MyParaTr{X{Y}} out of a vacuum, I have added a sugar @sample_params Dict(:T=>[Int,Float64]) inside @trailtimpl to at least test a few type parameters.

[mauro3]

I don't quite understand @sample_params, can you document it? Maybe in traitimpl.jl? (Aside, I need to come up with a better way to do documentation than just the README.md but that might have to wait for a wee bit.)

On one hand I am a bit hesitant to add sugar for something which can perfectly fine be written using associated types. However, I suspect that this might be one of the most common uses of associated types so nicer syntax would be good.

Let me know when you think this becomes mergable, also could you add tests?

[tonyhffong]

I will definitely add test and docs, as I want to also fresh out Functor trait as an example, so that we have more fulsome illustrations around the concept.

[mauro3]

Sounds good, thanks!

[tonyhffong]

I have added some very simple tests for a start. I also cleanup some existing tests as the func method_exists_tvars may have "duct-taped" one of the bugs you have alerted in your tests. In some cases the generated code has a regression relative to hand-written code, but in BigFloat there seems to see an improvement, go figure.

[tonyhffong]

One more thing, as I'm working my way through traitfn:

Does it make sense to define a way to get the "base type" and the parameter inside a traitfn? For example,

@traitfn f{X,Y; Tr1{X}, Tr{Y}, @tbase(X) == @tbase(Y), @tparam(X) <: @tparam(Y) }( x::X, y::Y ) = ...

or is it easier to put the burden on a combo trait like so:

@traitdef ComboTr{X{Z1},Y{Z2}} begin
    ...
    @constraints begin
        istrait( Tr{X{Z1}} )
        istrait( Tr{Y{Z2}} )
        X == Y
        Z1 <: Z2
    end
end
@traitfn f{X,Y; CombTr{X,Y}}( x::X, y::Y ) ...

It also feels to me that scoring on the match against ComboTr should be higher than what its 2 arguments would imply. Perhaps the scoring mechanism could be generated as part of @traitdef.

[mauro3]

I think your example is equivalent to:

@traitdef ComboTr{X{Z1},Y{Z2}} <: Tr{X{Z1}},Tr{Y{Z2}} begin
    ...
    @constraints begin
        X == Y
        Z1 <: Z2
    end
end

I've pondered syntax for making traits on the fly inside @traitfn but I can't quite remember what my use-case was. However, to me the your proposed syntax is not so readable. But anyway, I think we should just go with the more verbose combo-trait definition for now. If we end up doing this a lot we can always add extra syntax later.

[mauro3]

In essence listing several traits in a @traitfn definition is a way to make an ad-hoc trait. So there is one way already...

[tonyhffong]

Yes, I agree. Thanks for pointing out the better syntax.

[mauro3]

Thanks for working on this :-)

[tonyhffong]

With parametric traits, ambiguous matching can be quite severe if we stick to the parameter count scheme. I'm making the following proposal:

• The base score is 1.0 + the maximum score of supertrait. This is the dominant driver, assuming that each layer of trait inheritance adds a significant notion of "specificity" to the match.
• each constraint in the trait definition, including the number of supertraits (since it is just a constraint of istrait(SuperTr{X}) in disguise) would add 0.1 to the score.
• each number of parameters above 1 would add 0.01 to the score

I think the script examples/monads.jl is quite interesting as it shows how Array{Nullable{Float64},1} has both CollectionM and IterM trait but the mequal on CollectionM is picked because of its higher specificity from the inheritance hierarchy.

The scale factors are clearly arbitrary, but so far I'm happy with the result.

[mauro3]

Do the old tests all pass with your new dispatch rules? Can you elaborate a bit more on the example in monads.jl?

Old rules:

a) find all matching traits
b) discriminate using subtraits, i.e. a subtrait will win over its supertrait
c) score all traits according to:
   1 point for all single parameter traits,
   2 points for all two parameter traits,
    etc.
    Now pick the highest scoring method.
d) if still ambiguous throw an error

Your first rule is almost equivalent to a) because of the large point gap between your first and second rule. I'm not sure I like your second rule because: supertraits are already rated in the first rule; and because not only constraints add to the specificity of the trait but also the methods (but I don't think those should be rated). Your third rule is essentially about associated types: the more associated types there are, the more specific it is.

One of my observations was that it is indeed easy to get trait ambiguities. I am not sure that resolving them all automatically with very fine-grained rules is necessarily the best approach (but then again, I'm also not sure of the opposite).

[mauro3]

Let's keep that comment of yours more visible: https://github.com/JuliaLang/julia/pull/7474#issuecomment-69329613

[tonyhffong]

Under the current tests, there is one ambiguity test that is resolved in the new dispatch rules. See tf7465 with trait TrTr22 in test/traitdispatch.jl around line 178. TrTr22 derives from TrTr1{X} and TrTr2{Y}. Previous total score would be the same but under the new rules the subtrait TrTr22 wins. All other ambiguities stay as-is.

In the monads.jl example, I have defined:

@traitdef CollectionM{X{Y}} <: Collection{X} begin
    @constraints begin
        istrait( SemiMonad{Y} ) # we cannot put it in the header
    end
end
@traitdef IterM{X{Y}} <: Iter{X} begin
    @constraints begin
        istrait( SemiMonad{Y} ) # we cannot put it in the header
    end
end

Most array of monads would satisfy both traits, but collection presumably is more efficient, and that Collection <: Iter. We need a way to increase the match score for Collection and thus CollectionM. Scoring based on parameter count is not sufficient.

[mauro3]

I think the TrTr22 example should be ambigous because TrTr22 is equivalent to TrTr1{X}, TrTr1{Y}, therefore choosing one above the other seems too arbitrary.

In your example, I think the defining difference should be Collection <: Iter. I thought that trait-dispatch does that already (rule b), but if not, then I think that would be the one to implement.

[tonyhffong]

But Collection doesn't add more constraints (it adds new behavior) other than it derives from Iter, in as much TrTr22 derives from TrTr1{X}, and TrTr1{Y} so I don't see the distinction between the two cases, unless the "amount of additional behavior" should count to the score.

[mauro3]

Your example above does indeed not work. I just pushed a test for it. That would be great to fix but maybe not that easy as one would need to walk the traits-graph.

[mauro3]

And added another test case in commit 5e543b98be which I think should be ambiguous as there is no (edit) direct inheritance involved. What are your thoughts on those two cases?

[tonyhffong]

I don't think we need to walk the trait graph every time. My proposal is that the trait score is a static number known at traitdef time. As long as we guarantee that a trait will always score higher than any of its supertraits, and we have a mechanism to differentiate based on constraints and parameter count, we should be in good shape. So the scoring at dispatch is really just a simple dictionary lookup and addition (of all the traits used in a traitfn). In fact, perhaps we could even short circuit some method test if we know the ultimate score will be lower than the best matched score so far. Something to ponder.

[mauro3]

I don't think we can score traits independent of each other nor do I think a trait which has parent traits should count higher than a parentless trait (unless they are linked by inheritance, as in your above example). I'll try and come up with a good example.

[tonyhffong]

You have a good point, but this makes me realize that the situation is much worse than I thought. All these scores have no relationship with practical reality whatsoever! Who is to say the trait from collection has to be better than iter? Perhaps there are intermediate trait constraints and implementations that make the iter trait ancestor more useful in some cases.

The dumb but transparent thing to do is to accept a precedence score manually in traitdef like so

@traitfn score=5 f{;Tr1{X}}(x::X) = ...

so we quite literally express our preferences. The strongest justification for this dumb approach is that it gives the user flexibility to test out alternative algorithms on the same data based on its satisfaction of different trait combinations.

But boy, aint it ugly.

[mauro3]

haha! It sure is a tricky business.

Concerning your statement: "Who is to say the trait from collection has to be better than iter? Perhaps there are intermediate trait constraints and implementations that make the iter trait ancestor more useful in some cases."

I guess the usual situation would be that if you define a trait-fn for both iter and collection (where collection<:iter) then that means that a collection can somehow be used advantageously in the algorithm. Most of the time, 99.9%, this should be fine. For the corner cases, if they are important, we'll need a invoke for traits.

[mauro3]

Having thought a bit more about the current rules: rule c needs to be adjusted: several one-parameter traits using the same parameter should not be scored higher than just one, as we could define a new trait including those.

@traitfn f1{X; Tr1{X}, Tr2{X}}(...) = ...
# and
@traitfn f2{X; Tr3{X}}(...) = ...
# should get the same score as 
@traitdef Tr3{X} <: Tr1{X}, Tr2{X} begin end

Similarly for several parameter traits (but there commuting traits may make it more complicated...)

Edit: Hmm, or maybe I'm wrong because if they are the same then trait inheritance comes in. This is a confounding problem!

[tonyhffong]

It is good that we are getting closer to the crux of the dispatch preference issue. Perhaps we should merge the status quo first and then explore the dispatch preference issue separately. wdyt?

[mauro3]

Yep, I also thought that this issue is getting a bit out of hand. Does your Monad stuff work without the new dispatch rules? If so, could you clear the rest out and just leave that in. Which I can then merge.

For the dispatch related stuff I opened #5, let's move the discussion and your dispatch code to there.

[tonyhffong]

Well, it won't work well, but I'm happy to revert to the existing dispatch rule and then go from there. I'll let you know when I'm done.

[mauro3]

Cool, thanks!

[tonyhffong]

The example/monads.jl will fail because of dispatch ambiguities. But the basics of the parametric trait is tested out in test/paramtraits.jl. This PR should be ready to merge.

[mauro3]

Thanks a lot Tony for your work! Sorry but it will probably be early next week before I can properly review it.

[tonyhffong]

My pleasure! Nothing like learning something by diving into it.

[mauro3]

Tony, I started looking at the code, finally... (sorry this is taking so long). I updated Traits and rebased your branch, its here: https://github.com/mauro3/Traits.jl/tree/tf/monads + one extra commit from me. Maybe take it from there, saves you doing the rebase.

I encountered a few questions:

What do the ... mean:

@traitimpl SemiMonad{ Array{Y...} } begin
    mreturn{Y}( ::Type{Array}, x::Y ) = Y[x]
    bind{Y}( f::Function, x::Array{Y,1} ) = [ f(_) for _ in x ]
end

What is the difference between SemiMonad{ Array{Y...}} and SemiMonad{ Array{Y}}? Can the ... also be used in definitions?

What is the purpose of the X0_ type variable? Shouldn't it go into the assoctype storage too? If there is a suffix, what about the prefix?

trait_use1st_reg stores something. What? Could this not be achieved with a function or even a trait?

Other notes:

• could you add documentation to the new functions in helpers.jl?

[mauro3]

Probably the ... mean that we don't care about those parameter. Would it maybe make sense to be more explicit about it?

@traitimpl SemiMonad{ TypeWith5Paras{_,_,Y,_,_} } begin
    mreturn{Y}( ::Type{Array}, x::Y ) = Y[x]
    bind{Y}( f::Function, x::Array{Y,1} ) = [ f(_) for _ in x ]
end

I recall that traits on types without all their parameters specified are very fiddly, so maybe forcing the user to be specific is good?

[tonyhffong]

The way I think about this is that in a context of a trait, a parametric type can be decomposed as

• a root, which could be itself parametric, e.g. Associative{K} is the root of Associative{K,V}, in the sense that this holds in Julia ( Associative{K} ){V} == Associative{K,V}
• A type parameter, default being the last concrete parameter in a type. So it is V in Associative{K,V}, unless explicitly specified otherwise, using MyTrait{Array{T...}}
• A Suffix list, default empty. When we use the ellipsis notation above, it'd be the type parameters after the first one. So generally, we think of a type in a parametric trait as TypeRoot{T}{Suffix...} with T being the associated type in the context of the Trait being considered. The associated types are T0 for the root, and T0_ the the suffix list of types. They exist in the @traitdef and can be referenced.

The SemiMonad for Array{T,N} requires the first parameter, not the default last one, being the relevant type for satisfying the trait requirements, therefore we have to have a new notation to drive that behavior. And trait_use1st_reg, is the mechanism to remembers which is which. I don't think it matters too much since its usage is in the compile/staging time, not repeatedly in runtime.

I don't have a strong reason not to use explicit TypeWith5Params{_,_,T,_,_}. When we start to see more 3+ parameter types that should satisfy certain traits, we can certainly add them later. When that is the case, the trait_use1st_reg should be revisited.

I'll revert with further documentation.

[mauro3]

I see, that's clever! Thanks for the explanation.

One thing about the syntax: in Julia A... usually means something along the line "bundle (or splat) all that follows into (or out of) A" but here it means "ignore all that follows". So I think we need something else eventually.

[tonyhffong]

That is a good point. We should strive for consistency. Let's consider some alternatives:

• MyTrait{Array{T,:}} colon
• MyTrait{Array{T,_}} single underscore. Perhaps not so good if we need it to mean a single parameter only.
• MyTrait{Array{T,_...}} underscore + ellipsis
• MyTrait{Array{T,__}} double underscore

what do you think?

[mauro3]

Also, so far it was not necessary to use @traitimpl to actually implement a trait for a datatype. However for parametric traits, if the parameter is not the last in the in the datatype, it must be implemented through @traitimpl. (As you mention in `test/parameters.jl, I'm catching up...) Is this good or bad?

[tonyhffong]

@traitimpl provides a convenient registration mechanism. We can register the position some other way, but it adds a cognitive distance between the "first/last/in-between" with the implementation.

So I'm leaning toward "good".

[mauro3]

If we take _ to mean "I don't care about this parameter then the _... would be consistent with current use of ... in Julia. So, maybe go for that?

[mauro3]

I thought some more about this. What happens if you actually want to specify some concrete type-parameters?

Say I want parameter a to correspond to Y and also set b and c to something concrete? Then any of above variations of the ... does not work, right?

@traitdef Tr{X{Y}} ... end
type A{a,b,c} end
@traitimpl Tr{A{_Int_, Int, 3}}
    ...
end

So besides a "I don't care at all" _ we'd also need a way to signal which one of the parameters is the one.

Anyway, as a somewhat related side-note: until parameterized types cannot be specified more precisely, Traits.jl will struggle. Because the contracts between types are encoded in methods, which have richer possibilities to talk about types than types themselves. This might change if https://github.com/JuliaLang/julia/issues/6984 gets off the ground.

[tonyhffong]

Not sure I follow. The way I understood the framework, a,b,c should be all type variables that are left unspecified in @traitimpl. In fact, since the trait Tr{X{Y}} only needs one parameter, the @traitimpl only needs to know which of the 3 needs to correspond to the trait. The default is c with T,_... syntax we could specify a. Right now it's impossible to state it's b.

[mauro3]

I can implement a non-parametric trait in a few ways for a parametric type:

@traitimpl Tr{Array}...
@traitimpl Tr{Array{Int}}...
@traitimpl Tr{Array{Int,1}}...

Whereas (as implemented currently) for a parametric trait only the parameter before the special parameter can be given. Not saying that we need to implement that as well, just musing.

[mauro3]

@tonyhffong, I did some major updates with #10. I'm not sure how that impacts on this PR. I'll try and look into it, although just now I probably used up my Traits.jl time for a wee while.

I saw over in Lint.jl that you will not have so much time to spend on Julia anymore, this is a shame, I was hoping to have you on board here!

[tonyhffong]

Don't worry about it. I'll take a look, though no promises on timing.

[mauro3]

As discussed today at JuliaCon:

@traitdef Tr1{X{Y}} begin
    f(..) = ...
end

# the X{Y} is essentially sugar for
@traitdef Tr1{X} begin
    Y = traitpara(X)

end

# and would need to be defined like so
traitpara{K,N}(::Tr1, ::Array{K,N}) = K
traitpara{K,N}(::Tr1, ::Dict{K,V}) = V

# Example:
@traitdef IsIndexable{X{I}} begin
    getindex(X, I)
end

traitpara{K,N}(::Tr1, ::Dict{K,N}) = K
traitpara(::Tr1, ::Array) = Int

# implement macro:
@traitimpl Tr1{Vector} begin
    @traitpara{T}(::Array{T,1}) = T
    f{T}(A) = 1
end

[tonyhffong]

Hi @mauro3 , as I hack through the code, I think there's an even better way, using -> inside the @traitimpl

using Traits

@traitdef Functor{X{Y}} begin
    fmap(Function,Y) -> X
end

@traitimpl Functor{ Array{T,N} -> T } begin
    fmap{T}( f::Function, x::Array{T,1} ) = map( f, x )
end

With the arrow construct, we solve the problem of multiple-parameters in a trait, the order of the parameters, AND the flexibility to define "diagonal parametric trait" such as

@traitdef Tr{X{Y,Z}} begin
    f(X,Y) -> Z
end

# note the repeated parameters in (T,T) which satisfy Y,Z above
@traitimpl Tr{ Array{T,N} -> (T,T) } begin
    f{T}( x::Array{T,1}, y::T ) = sum(x)+y
end