Protocols/Interfaces/Traits... or: The "what to implement problem"

FHell · May 25, 2020, 3:40pm

Hello everyone,

I am interested in picking up the “what to implement problem” of defining interfaces/protocols in Julia. In my view the broad issue is: How do I encode invariants and expectations of my code. This is critical both at the point of use of my package, and for reasoning about its internal structure. How do we use this encoding to help the user correctly use it (good error messages, REPL discoverability), and me as author to completely document it (doc strings, tests).

The dynamicism and multiple dispatch of Julia, that enables all the immense goodness and composability we get from it, also makes the above points challenging.

For my research group this is a much bigger issue than, e.g. compilation times right now. Compilation times can be worked around, but this lack of structure in Julia code-bases is often a real showstopper. (And the often inscrutable error messages that I believe are also linked to this are a major issue in teaching it to new students.).

I have no intention to fully solving this issue, that would only be possible with buy-in from the core team and the standard library, and that will probably mean this is something for Julia 2.0 (though i really hope I am wrong about this). But I want to start contributing by prototyping things I think could be useful in this direction. I also hope that by prototyping in this direction we can gain a bit of experience with how protocols et.al. interact with other aspects of Julia.

I wrote up a gist summarizing my thinking on where I want to go with this here.

The basic idea is to build on top of Holy style traits, guaranteeing [1] that a type that has a certain trait also has certain fields and functions defined on it. Further, this should not be automatically detected but require explicit declaration (Rust Traits rather than C++ Concepts).

I would be interested in feedback but also general input and discussion. And I probably overlooked ongoing discussion/prototypes/implementations somewhere, which is another reason why I am posting before having code to show.

[1] In a weak sense: Unless the user manually uses the underlying trait that is not exposed anywhere. But Julia is fully dynamic anyway. The goal is to make the happy path the obvious one, not the only one.

Akatz · May 25, 2020, 4:08pm

I’m glad there is more interest in picking this up! I think further exploration from the community is the way to garner more attention on traits from the core devs. I also think it’s possible to potentially do this in a backwards compatible way, depending on the solution.

One thing that I’d like see solved, on a different axis than knowing what to implement or type safety, is interop between separate type trees. If package x and y have their own types, and I wrap a type from package y in a type from package x, how can I have this wrapper continue to work with dispatches from package y ? What about more complex interactions? But, doing this without method ambiguities.

I’ve included some packages exploring the solution space and a transcript of a related extensive slack discussion here: Slack traits - Google Docs

Another thing, is that there is talk of having some sort of static typing or static type overlay ala typescript. Would be great if in some restricted sense, the same system can be utilized for compile time checking.

Also, I’d check out Swift’s protocol system as inspiration as well, (with the obvious caveat that static solutions can’t be lifted unmodified for a dynamic language.)

cc @schlichtanders and @tk3369

leethargo · May 25, 2020, 7:21pm

One of the issues you mention is that “there is no obvious way to put docstrings to functions without implementation” (paraphrasing).

But, it’s perfectly possible in Julia to define fully generic functions and attach docstrings to them, that is

"Computes foo from bar, should be implemented by user!"
function foo end

Then, if some user code creates new types and implement methods for foo, this docstring will apply to it as well.

It’s also popular to add more (human-readable) function signature information in the docstring. See some examples: MathOptInterface.jl, Diderot.jl.

FHell · May 26, 2020, 7:43am

That’s a nice pattern I didn’t know about, thanks! Indeed for many individual pieces (though I don’t think all) there are individual solutions, and with sufficient coding discipline it’s certainly possible to do everything you want, but discipline is error prone.

FHell · May 26, 2020, 8:35am

Thanks for sharing that discussion! This is very exciting to see. I have to admit that I am not 100% following all the arguments being thrown around. But my impression is (and please correct me if I’m wrong) that most of Traits is concerned with ways of talking about properties of types and dispatching on these properties. Basically nicer/sugared/more powerful versions of what Holy-style traits already do. I personally have no problem with requiring ambiguities to be broken “by hand” if we have good enough error messages. One of the Python design principles is “In the face of ambiguity, refuse the temptation to guess.”

The things I am thinking about here try to be orthogonal to that. I think that none of the traits proposals would solve the main usability issues I am talking about (error messages, documentation, code structure), and conversely I think the protocols thing I am pitching can be built on any of these traits if one of them makes it to . It’s essentially defining traits that have some code locality (impl block) and guaranteed properties (hasmethod, hasfield).

I think this is exactly what would be needed to do composition between packages. If packages would communicate their expectations by saying “the user has to guarantee this behaviour” rather than by saying “please use my types”, it would be trivial to work with several of them.

One of the reasons packages expect users to work with their types right now is that it’s the only way to guarantee anything about the behaviour of what you’re being passed, but really it’s a lie. You don’t need me to use your type, you need me to use a type that hast the following fields, and this list of methods. Any type that has these will do…

Akatz · May 26, 2020, 7:15pm

I agree!

https://github.com/schlichtanders/Traits.jl does have a way of dispatching on methods under " Dispatch on whether functions are defined - using IsDef.jl", although I don’t think it has a protocol system. I agree that the latter is mostly orthogonal and can be combined with a dispatch system.

BinaryTraits.jl/index.md at master · tk3369/BinaryTraits.jl · GitHub allows specifying and enforcing a method interface for traits.

Which I like, but I’m not yet sure if BinaryTraits allows for trait polymorphism in the same way that traits.jl does (as you can dispatch on types and abstract types). Though this might be a bit of a footgun.

also tricks.jl has a static hasmethod that can check for the existence of methods at compile time.

FHell · May 27, 2020, 9:54am

One of the things I consider an explicit design plus is to have to explicitly declare compliance to the protocol through an impl block, and to force the code that implements the protocol to occur under that declaration.

Whereas I see something like IsDef based dispatch instead tries to make things “magical”, react to whatever the user is throwing at us in an optimal way. This is great if it works. If it does then the protocol for using your package doe not require the user to implement a function (so maybe optional functions could be an interesting future feature in protocols…) but I think it would also be valuable to simply state explicitly that you need X. So to me this is still clearly orthogonal… Now the BinaryTraits thing requires a bit more thinking for me…

Edit: So thanks a lot for the really valuable input, pointers to specifics of the traits packages, and insight into what’s been discussed behind the scenes/on slack. I think I will come back when we have a working prototype, which might take some time (about to go on parental leave…).

tk3369 · May 28, 2020, 2:48am

Hi @FHell,

I’m the author of BinaryTraits. Looking over your gist about the requirements, it seems to me that my package is not too far away from reaching your goals. There are still some features that I haven’t had a chance to implement e.g. doc strings, default implementation, etc. However, these gaps are not difficult to close.

Perhaps you can take a closer look at BinaryTraits first. If you want to get your hands dirty, why not contribute to the package?

FHell · May 31, 2020, 10:21am

@tk3369 I think you are right. In fact from a technical point of view it seems that BinaryTraits implements almost all that we want. The difference I see right now is in the design (with the potential that Protocols allows for simpler implementation by doing less). I think I will definitely try to prototype this on top of BinaryTraits and I’ll be in touch when I get time to get started to work on this (which I expect to be some weeks away).

schlichtanders · June 2, 2020, 6:24am

thanks @Akatz for pinging

Hi @FHell,
I am the author of https://github.com/schlichtanders/Traits.jl
Briefly, it is just convenient syntax for what you would write manually as two nested functions when using the Holy-Traits-Pattern.

# some plain julia traits following holy trait pattern
abstract type MyHolyTrait end
struct MyHolyTrait1 end
myholytrait(a::Int) = MyHolyTrait1()
# ----------
func(a) = func_inner(a, myholytrait(a))
func_inner(a, ::MyHolyTrait1) = "dispatched on traits"

With https://github.com/schlichtanders/Traits.jl you can write the last two lines as

@traits func(a) where {myholytrait(a)::MyHolyTrait1} = "dispatched on traits"

With the added benefit that you now can extend the hidden func_inner by specializing for other traits. Note, that this can easily lead to method ambiguities like in general in Julia when using several function arguments, but still it is quite handy.

As you can see, this approach is not magical at all. The mentioned IsDef.jl package just gives you a function isdef(func, ArgumentType1, ArgumentType2, ...) which you can use in traits-based dispatch, however you don’t have to and may better define your custom holy-traits.

Little Checklist

code structure (e.g. using Holy-Traits-Pattern)
Documentation support
precompilation
Good Error Message (this is really hard, as I so far don’t know how to overwrite error messages when a method could not be found…).
explicit declaration like Rust Traits

Note on Rust/Haskell-like Explicit Declaration of Traits/TypeClasses: Julia’s abstract types are mere hierarchical tags and do not enforce any existence of methods. In general you rather rely on the implicit assumption that the methods are correctly implemented for the given types. That may seem suboptimal but in practice is not really an issue:

The best way to guarantee your custom types implement a certain interface is that you test all required methods.
That is anyway best practice and should be done in any production-ready code.
If you miss out a specific function, you get a nicely descriptive MethodError saying that you forgot to implement a certain function for your custom type. E.g. taking the myholytrait() example from above, you would get notified that you forgot to implement myholytrait(a::YourCustomType).

In total that gives you simple, flexible, extendable, easy-to-read and production-ready code.

Typeparameter vs value-based programming

As your main concern is about how to structure your code, here a general tip: Julia works best, when you use a kind of value-based programming style.

E.g. when you would want to construct a method which can flatten a vector of vectors into a single vector, you better do not dispatch on ::Vector{Vector} directly, but rather dispatch on the generic vec::Vector, then iterate through for element in vec, and try to convert every element to Vector by using convert(Vector, element).
The underlying reason is that Julia’s type inference is incomplete, so that some calculation may return a Vector{Any} because type-inference just failed. Your code should always work the same, whether some typeinference failed or not. It may be slower, but not different in behaviour. If you would dispatch on Vector{Vector} you can easily violate this subtle principle. Try to avoid such typeparameter-based approaches.
This applies to everything container-like like Vector. Best Practice: Always break down the container into its underlying plain values, and then continue value-based.

I hope this can be of some help.

Tamas_Papp · June 2, 2020, 2:22pm

Great writeup! I just wish to add that two additional reasons to avoid dispatching on eg Vector{T}:

usually any <:AbstractVector{T} should be a plug-in replacement. Limiting to a particular concrete type is usually neither necessary nor helpful in generic code.
the caller may intentionally use Vector{Any} even when inference could figure it out. Eg collecting objects of heterogeneous types if one has too many for a Tuple or compiling specialized code is to be avoided.

FWIW, I find that the various trait packages add very little in terms of convenience at the cost of another layer. Traits are simple.