Why use subtypes instead of traits and duck typing?

I have been tinkering with Julia and I am now trying to design a moderate-sized project. However, I have been struggling to come up with a type hierarchy and I realized that, in Julia, I don’t know why you should subtype at all. I’m hoping someone can provide me design advice on when to make subtypes, or at least prompt a discussion over the use of subtypes in Julia code.

As far as I can tell, the subtype relationship is a poor fit for both standard interpretations of inheritance. The Gang of Four book distinguishes between two kinds of inheritance: class inheritance and interface inheritance. Class inheritance is when a subclass shares “the definitions of all the data and operations that the parent class defines.” Since Julia supertypes are abstract, there is no data to share, so Julia subtyping is not class inheritance. I have seen repeatedly in the Julia forums the advice to use composition in place of class inheritance, and there are several good reasons to do so even in languages with class inheritance.

The other kind of inheritance defined by the Gang of 4 book is interface inheritance. An interface of a type is everything that type can do, which in Julia means all the methods defined for a type. By this definition, interface inheritance would be when a subtype can run all the same methods, which Julia lets you do. But from my understanding of Julia, you should not use subtyping for interface inheritance for many reasons:

  • All modern languages that I know of support multiple inheritance of interfaces, including C++, Python, Java, Haskell, and Rust. I realize the single inheritance is important for dispatch, which enables many other important features of Julia, but this is a large problem for interface inheritance.
  • Julia is a dynamic language, so predefined interfaces are less important. A large part of the “magic” of Julia is that the code of two unrelated packages can usually work together, like the famous plotting of solutions to differential equations with uncertainties example. To achieve this code composability, Julia encourages us to define functions with as few defined types as possible, effectively making the function duck-typed based on what methods you call with that argument (see the first point in the style guide). This is how the iterator interface in Julia works, for example. As long as you implement the specified methods, it doesn’t matter what type something actually is.
  • If you need a stronger interface contract than “implements a method,” such as bundling methods together or certain properties for performance, Julia has traits that suffer none of these problems and are more extensible - types can have multiple traits, traits can be implemented after the type declaration, and it still works well with multiple dispatch.

So if I can achieve interface inheritance through traits and duck typing and use composition over inheritance for code reuse, why should I bother to put any types in a hierarchy at all? Well, there is one other interpretation of subtyping in Julia: an enumeration of values. If you think of all subtypes of a common parent as values in an enum from a language like Java or C and method dispatch as a switch statement (or equivalently pattern matching in functional languages), then you can see that the behavior is nearly the same. However, there is one key difference: Julia’s setup is open to extension. Another programmer in another package can add a new value to the enumeration, which would be impossible in C because all enum values must be defined together. Likewise, adding new methods is the same as adding new case statements to a switch block in a different file, an impossible feat in other languages that manages to keep the program open to composition and extension by other programs.

This “subtype as enumeration” model is how Julia traits types work, and it’s quite a powerful system. But outside of traits, I don’t see many places where this kind of setup is useful. Furthermore, there is something strange here: in most cases, enumerations aren’t types at all. If all the “subtypes” of an enumeration are singleton types (that is, structs with no fields, which is what I have seen for all trait examples I have looked at), then they are values, not types. Just like a C enum, these values can be replaced with an integer assigned by the compiler corresponding to which value it is (in Julia, this is probably a pointer to the singleton instance of the type, but I am not certain on the internals). And if these enumerations are values, then the type of these values is the supertype. Something seems fundamentally strange about using the subtype operation to instantiate different values for a type, but that is exactly what this pattern does.

So in conclusion, I have found that Julia subtyping is not class inheritance, could be interpreted as interface inheritance (but there are better alternatives), and is great for extensible enumerations (where they are not really subtypes at all). So why do you use subtypes in Julia? And what advice to you have for designing a type hierarchy for a project? My Julia experience is limited so I welcome corrections on my points here.

13 Likes

If I were you, I would probably not create many new Abstract types when starting development. Instead, I would first consider whether the class you are creating is a type of Number, AbstractArray, or AbstractString. If it is one of those, give it the right subtype within that hierarchy. Otherwise, I would probably not give it an abstract type unless and until you realize that your code has a few structs that all seem to be doing the same “thing”. At that point, I would sit down and think about the nature of that “thing” and whether creating an abstract type would help. Specifically, think about whether you could write methods that could have the same code for all the different types of structs you are considering. If so, you might want to consider defining an abstract type for them.

14 Likes

You’re correct that subtyping in Julia represents inheritance of behaviour, not structure. You are also correct that Julia encourages minimal constraints on type signatures and duck typing (though I tend to use exact type annotations all over the place for internal non-package code).

It’s probably most useful to think of Julia’s type system as “the thing that controls dispatch”. That is, you only need types in order to define multiple methods of the same function. And when you do define these methods, you should pick the broadest possible type where the new method applies.

My advice would be that, if you are creating a package that exports generally useful types, you should define an abstract supertype, specify its interface in the documentation, and then implement as much of the functionality of your concrete types using methods that take the abstract type. This allows users to subtype your abstract type, implement the interface for their new type, and use most of the code in your package.

If you are creating a package that exports functions, you should pick unique function names and avoid using types in the signature altogether. This allows your users to use your function with custom data types. If your functions only conceivably apply to one type (e.g. you made a BTree package with just a concrete implementation of AbstractDict), then you can restrict your signature.

Edit: Finally, if you’re creating an “application”, e.g. end-user code for some project, anything goes, because it’s not going to be re-used. I tend to fully specify the relevant types (e.g. AbstractVector{<:Integer} for all arguments of all functions, and also the function output type in this case. This makes the code more rigid and less general, but is also useful to catch bugs, for refactoring, and to write self-documenting code.

21 Likes

But, in principle, traits would also do the job, right? I agree with you in practice, but aren’t traits just strictly more powerful in some sense? Of course, they lack some first class syntax / support but that could be added I guess.

(Just to be clear, for me this is interesting in a conceptual level. In practice, I work similar to what @jakobnissen and @Oscar_Smith have said above.)

1 Like

Traits are strictly more powerful, but as far as I’m aware, no one has figured out how to do multiple dispatch with only traits.

3 Likes

Traits/structural typing/duck typing by themselves don’t provide specialization. Subtyping does.

Specialization is the key thing that Julia’s subtypes provide. You can define a method on AbstractType, override it in AbstractSubType and further override it for specific concrete subtypes.

Specialization is used a lot in Julia to make generic programming a zero cost abstraction. If you don’t have it, then you run into the problem of generic programming having a concrete cost whenever there is a more optimal implementation in specific subcases.

3 Likes

I kinda disagree with this. This may lead to the following scenario:

  1. A second package is created to make useful operations over types of the abstract supertype exported by the first package (i.e., the package you describe).
  2. Some user imports this second package and wants to use it on their own type but their type already subtype an abstract type needed by other interface, or it wants to create a glue package that implements second package interface for a concrete type of a third-party package.
  3. If the abstract type did not exist, it would only be a question of defining some primitive operations over the type, and letting the second package do its magic.
  4. However, as the second package expects subtypes of some abstract class, and you cannot add those to an already existing type (or to a type that already needs to have another parent type) you need to create a type wrapper, and the process may become much more annoying.

I agree with the feeling shared by @regier2302, it is something that was already in my mind for some time. I even write these first and second answers to an user with similar but much more applied doubts. I recognize that the type hierarchy is very nice for dispatch on some “set-on-stone” relations like Number (Real, Float64, Integer, Int, and so on) it creates a great family of fallbacks for operations over generic numbers.

However, in general, my to-go design is to create modules that just describe an interface, without creating any abstract type and without, therefore, dispatching on abstract types. The interface can be separated in primitive functions, for which there is no fallback; fallback functions for which there is a fallback calling primitive functions, but you can also implement your own behavior; and purpose functions that call both previous types and you often do not want to re-implement because otherwise you have no need for the package, the package’s purpose is to provide them (sometimes those will be in a different package, and a Base package will have both primitive and fallback functions). Then anybody can implement as many interfaces they want for their own types, and glue packages can provide the interface of Package X to types of Package Y. Those interface packages can provide some abstract types (or even concrete, in fact), but only to be used trait-style (functions dispatch on them, but they are just a way passing a flag on type-space). The only thing a tree of abstract types adds to this idea is a hierarchy of fallbacks, that sometimes is nice, but at the cost of incompatibilities between interfaces, because a type cannot subtype multiple types and therefore cannot implement multiple interfaces.

Right, most of the time you want to declare methods, not types. If you just want to restrict a method to a class of valid input types, use the holy traits pattern or make it a @traitfn with SimpleTraits.jl .

If you want it to be generic, type restrictions should be minimal. Inheritance comes in when you specifically want to have multiple different generic methods for a function where one generic implementation applies to a subset of another. You should declare an abstract type only if you’ve already ruled out letting your functions take Any as a parameter.

Traits are an is-a relationship. Composition are a has-a relationship. Abstract type Inheritance is an is-an-important-special-case-of relationship.

3 Likes

I think you’re right that the only reason to use a type hierarchy instead of Holy traits is to avoid a bit of typing. The one place I’m not sure if Holy traits are as capable as a type hierarchy is when using parametric types (e.g. the AbstractArray interface). But I haven’t thought about it very much; maybe a trait-based array interface would be just as capable. Dispatching on e.g. AbstractArray{Float64) seems like it would be uglier with a trait-based solution.

Traits can’t support functions with two different generic implementations (unless they are mutually exclusive)

I.e. if you have
@traitfn foo(x::T) where {T;IsNice{T} } = ...impl A... and @traitfn foo(x::T) where {T;IsNeat{T} } = ...impl B... , then the second one will just override the first one completely afaik, because they have the same set of generic parameters and only have different bounds. Haskell typeclasses and Rust traits have the exact same problem and will give you a compiler error instead. This is an example of a problem that Rust and Haskell are simply not expressive enough to solve well.

By contrast, foo(x::AbstractArray) and foo(x::AbstractDict) will not overlap. That’s an example of specialization, which allows two different specific generic implementations.

What you should not do on the other hand, is use inheritance for type safety or to bound a generic parameter to types for which some specific methods are implemented. Traits (or just taking anything and letting the called methods return errors) do that better. Subtyping is there primarily for subtype polymorphism, which is one of the main reasons why Julia is so ridiculously expressive for generic code.

Julia has all three different kinds of polymorphism. Parametric, ad-hoc polymorphism (via duck typed multimethods and traits), and subtype polymorphism (through inheritance). None of the three can completely replace each other.

1 Like

I wrote a little while ago on Zulip about how I think about the difference between a trait / typeclass system and julia’s inheritance model. Perhaps this will be helpful for people familiar with julia, but not languages designed around ‘typeclasses’ (which are not the same as OO classes!):

Personally, while I love julia, I actually do kinda think that a lot of the time, this subtyping model where a package is supposed to predict the ‘most general abstract form’ of something ahead of time, and then come up with concrete examples of it next, is not as good as coming up with limited interfaces and then generalizing up from there, rather refining down.

That said, it’s hard to argue with the real world results in julia. I just feel like we can do better.

12 Likes

I recognize that the type hierarchy is very nice for dispatch on some “set-on-stone” relations like Number ( Real , Float64 , Integer , Int , and so on) it creates a great family of fallbacks for operations over generic numbers.

I’m even a bit skeptical of this, because where does the taxonomy end? Real and complex numbers are also fields, fields are also groups, and there are a whole host of other mathematical distinctions we could make that define exactly what properties these have and what operations we can perform. And from this perspective, it makes less and less sense to ever have a function that works on an argument of type Number.

For example, polynomials are not numbers, but in many ways they act like them because you can perform addition, subtraction, multiplication, and division. So I suspect there are many functions which require a Number as an argument that would work perfectly well with polynomials, and consequently the function probably should have left the type off all together. Sure, you cannot do some operations like square root, but you can’t square root negative numbers anyway so it isn’t like all Number types need to be able to perform all operations like this. And if the function requires a missing operation then it will complain, which is how duck typing is supposed to work.

I looked (briefly) for any official documentation of what assumptions are made for a subtype of Number but couldn’t find anything. From my perspective, the distinction over whether a type is a number or not is vague. Having an Int type where the only differences between the subtypes being the number of bits makes sense. But I am skeptical that Julia really needs a Number type at all.

7 Likes

Julia has a Number type more for practical reasons than ideological reasons. Practically, we’ve found it very useful to have Number because Numbers are familiar and easy to think about. They’ve generalized well to things like quaternions and clifford algebras too.

That said, it’s entirely believable to me that a trait system would have worked better.

2 Likes

This is a great point, but I think the example is a bit backwards. Isn’t this trait progression going in the same direction as the type-hierarchy example, from more general to more specific? The type-hierarchy example goes Any > Number > Real > Integer > Int. The trait example goes Additive >Algebra > DivisionAlgebra. IIUC the trait example can be recited in any order, whereas the type-hierarchy example cannot.

Do traits support hierarchies? E.g. can I say “SpecialAdditive <: Additive” for traits?

Yes, you’re right. Now that you point it out, I see the traits in my example are getting more specific, not less.

I guess the more interesting and distinct difference though is that traits are based on behaviour, what an object does, whereas subtyping is all about an object’s structure and identity.

I think this is one thing that really makes me skeptical about the value of subtyping. It was recognized a while ago that concrete inheritance is a bad idea, so Julia only allows abstract inheritance, but then it almost feels like the point of subtyping gets defeated.

If sub-typing is all about the shared structure and identity of a set of types, but you also have no mechanism to make them share data layouts, only methods, why bother structuring your type system around the idea of shared identity at all? Why not base it around behaviour like traits do?

5 Likes

I guess if I was to amend this:

I’d say that it’s less about getting more general as you up the tower, but that you can build the tower and then attach concrete types anywhere on the tower, and the concrete types can be defined before or after the traits are defined.

1 Like

I think the general diagnostic here is on point.

To my knowledge the main reason subtyping is used instead of traits is that the syntax is more convenient in many cases. If you just want several types to use the same method implementation, it is clearly the most straightforward solution.

Honnestly I have no idea how custom traits would interact across packages and if there would be a risk to break a function while you are trying to extend it with your own types/traits. Keeping it to subtyping is a safe choice in this case.

So at the end of the day I think subtypes are used mostly for convenience.

I personnaly am in favor of removing (or converting to mere type annotation for documentation purpose) many abstract types like Number or Real as they have caused me problem in the past due to over specificity in some module method definitions.

If sub-typing is all about the shared structure

Isn’t the shared structure the job of UnionAlls?

2 Likes

There is a JuliaCon keynote by Guy Steele on the Fortress programming language (developed 2003-2012), which had a lot of the features that Julia has. However, it had a much more complicated type system, e.g. here:

But one of his comments is that if he were to do it again, he’d do it with a less complicated type system:

“but we got stuck in the swamp of this extremely general type
system and as I say we were learning about ways to back off and
make it more tractable and more implementable and if I were to do
this over again I would back off and try to exploit a subset of
these ideas using a less complex type system”

So, maybe Julia’s type system not being able to express everything is a feature and not a bug.

7 Likes

I guess I’m not actually sure if a typeclass based typesystem is actually more complicated in the way Fortress’ type system was. Julia’s current system is pretty complicated too :wink:

1 Like